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.
WOS:000297465100038
2011
978-1-4577-0595-3
184
188
NON-REVIEWED
Event name | Event place | Event date |
St Petersburg, RUSSIA | Jul 31-Aug 05, 2011 | |