Linear extractors for extracting randomness from noisy sources
- Creators
- Zhou, Hongchao
- Bruck, Jehoshua
Abstract
Linear transformations have many applications in information theory, like data compression and error-correcting codes design. In this paper, we study the power of linear transformations in randomness extraction, namely linear extractors, as another important application. Comparing to most existing methods for randomness extraction, linear extractors (especially those constructed with sparse matrices) are computationally fast and can be simply implemented with hardware like FPGAs, which makes them very attractive in practical use. We mainly focus on simple, efficient and sparse constructions of linear extractors. Specifically, we demonstrate that random matrices can generate random bits very efficiently from a variety of noisy sources, including noisy coin sources, bit-fixing sources, noisy (hidden) Markov sources, as well as their mixtures. It shows that low-density random matrices have almost the same efficiency as high-density random matrices when the input sequence is long, which provides a way to simplify hardware/software implementation. Note that although we constructed matrices with randomness, they are deterministic (seedless) extractors - once we constructed them, the same construction can be used for any number of times without using any seeds. Another way to construct linear extractors is based on generator matrices of primitive BCH codes. This method is more explicit, but less practical due to its computational complexity and dimensional constraints.
Additional Information
© 2011 IEEE. Date of Current Version: 03 October 2011. This work was supported in part by the Molecular Programming Project funded by the NSF Expeditions in Computing Program under grant CCF-0832824.Attached Files
Submitted - 1209.0732.pdf
Files
Name | Size | Download all |
---|---|---|
md5:efa031392467920e5c458007830f51f8
|
234.1 kB | Preview Download |
Additional details
- Alternative title
- Linear Transformations for Randomness Extraction
- Eprint ID
- 29915
- DOI
- 10.1109/ISIT.2011.6033845
- Resolver ID
- CaltechAUTHORS:20120330-134402245
- CCF-0832824
- NSF
- Created
-
2012-04-11Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field