Polarization and randomness extraction
Polarization and randomness extraction
复制标题
极化和随机性提取
DOI：
10.1109/isit.2011.6033870
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
E. Abbe
中科院分区：
文献类型：
--
作者：
E. Abbe
本文探讨了随机提取与通道（源）编码问题之间的联系。解释了如何使用有效的提取器来定义有效的编码方案，并相互地提出了一种基于极地编码方案的新确定性提取器。由于用于计算机科学的提取器（密码学）中使用的源模型不假定I.I.D。或已知的分布，开发了具有块记忆和未知分布的源的广义极化现象。结果表明，在这种情况下，可以有效地提取最小肠道（如提取器中的往常）而不是香农熵。派生的极性编码结果也适用于具有内存的化合物通道。
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.