Polarization and randomness extraction

This paper explores a connection between randomness extraction and channel (source) coding problems. It is explained how efficient extractors can be used to define efficient coding schemes and reciprocally, a new deterministic extractor based on a polar coding scheme is proposed. Since the source model used in extractors for computer science (cryptography) do not assume i.i.d. or known distributions, a generalized polarization phenomenon for sources with block memory and unknown distributions is developed. It is shown that in this setting, the min-entropy (as usual in extractors) rather than Shannon entropy can be efficiently extracted. The derived polar coding results also apply to compound channels with memory.


Published in:
2011 Ieee International Symposium On Information Theory Proceedings (Isit), 184-188
Presented at:
IEEE International Symposium on Information Theory (ISIT), St Petersburg, RUSSIA, Jul 31-Aug 05, 2011
Year:
2011
Publisher:
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa
ISBN:
978-1-4577-0595-3
Laboratories:




 Record created 2012-06-25, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)