A Caltech Library Service

Linear extractors for extracting randomness from noisy sources

Zhou, Hongchao and Bruck, Jehoshua (2011) Linear extractors for extracting randomness from noisy sources. In: 2011 IEEE International Symposium on Information Theory, Proceedings. IEEE , Piscataway, NJ, pp. 1738-1742. ISBN 978-1-4577-0596-0.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Bruck, Jehoshua0000-0001-8474-0812
Alternate Title:Linear Transformations for Randomness Extraction
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.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20120330-134402245
Persistent URL:
Official Citation:Hongchao Zhou; Bruck, J.; , "Linear extractors for extracting randomness from noisy sources," Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on , vol., no., pp.1738-1742, July 31 2011-Aug. 5 2011 doi: 10.1109/ISIT.2011.6033845 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29915
Deposited By: Tony Diaz
Deposited On:11 Apr 2012 21:15
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page