An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets
复制标题
所有字母表上的熵和集不等式和多项式快速收敛于香农容量
DOI：
10.4230/lipics.ccc.2015.42
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Velingker
中科院分区：
文献类型：
--
作者：
V. Guruswami;A. Velingker
我们证明了当条件随机变量X的两个副本|Y，其中X在Zq = {0，1，...，q − 1}对于素数q，取模q求和。具体来说，两个静脉注射.一对随机变量（X，Y）的拷贝（X1，Y1）和（X2，Y2），其中X取Zq中的值，我们证明：
H（X1 + X2| Y1，Y2）- H（X| Y）≥ α（q）· H（X| Y）（1 - H（X| Y））的
对于某个α（q）> 0，其中H（·）是归一化（因子log 2 q）熵。特别是，如果X| Y不接近于完全随机或完全确定，并且H（X| Y）∈（γ，1-γ），则和的熵增加Ωq（γ）。我们的动机是对极化码的有限长度行为进行有效分析，其中对γ的线性依赖性在定量上很重要。q是素数的假设是必要的：对于X在Zq的一个真子群上一致支撑，我们有H（X + X）= H（X）。对于X支撑在没有有限子群（无挠情况）和无条件的无限群上，Tao在[20]中证明了（非归一化）熵绝对增加的和集不等式。
我们使用我们的和集不等式来分析Arikan的极化码构造，并证明对于任何q元源X，其中q是任何固定素数，并且任何e > 0，极化码允许N i.i.d.的有效数据压缩。将X复制成（H（X）+ e）N个q进制符号，只要N在1/e中多项式大。我们可以通过将q分解为素数并在分解中为每个素数组合不同的极化码来获得具有类似复合字母保证的容量实现源代码。
噪声信道编码的结果的一个后果是，对于所有离散无记忆信道，有明确的代码，使可靠的通信在e > 0的对称香农容量的块长度和解码复杂度由1/e中的多项式界定。之前针对二进制输入通道的特殊情况显示了该结果[7，9]，而这项工作将该结果扩展到任何字母表上的通道。
We prove a lower estimate on the increase in entropy when two copies of a conditional random variable X|Y, with X supported on Zq = {0,1,..., q − 1} for prime q, are summed modulo q. Specifically, given two i.i.d. copies (X1, Y1) and (X2, Y2) of a pair of random variables (X, Y), with X taking values in Zq, we show
H(X1 + X2 | Y1, Y2) - H(X|Y ) ≥ α(q) · H(X|Y)(1 - H(X|Y))
for some α(q) > 0, where H (·) is the normalized (by factor log2q) entropy. In particular, if X|Y is not close to being fully random or fully deterministic and H(X|Y) ∈ (γ, 1-γ), then the entropy of the sum increases by Ωq (γ). Our motivation is an effective analysis of the finite-length behavior of polar codes, for which the linear dependence on γ is quantitatively important. The assumption of q being prime is necessary: for X supported uniformly on a proper subgroup of Zq we have H(X + X) = H(X). For X supported on infinite groups without a finite subgroup (the torsion-free case) and no conditioning, a sumset inequality for the absolute increase in (unnormalized) entropy was shown by Tao in [20].
We use our sumset inequality to analyze Arikan's construction of polar codes and prove that for any q-ary source X, where q is any fixed prime, and any e > 0, polar codes allow efficient data compression of N i.i.d. copies of X into (H(X) + e)N q-ary symbols, as soon as N is polynomially large in 1/e. We can get capacity-achieving source codes with similar guarantees for composite alphabets, by factoring q into primes and combining different polar codes for each prime in factorization.
A consequence of our result for noisy channel coding is that for all discrete memoryless channels, there are explicit codes enabling reliable communication within e > 0 of the symmetric Shannon capacity for a block length and decoding complexity bounded by a polynomial in 1/e. The result was previously shown for the special case of binary-input channels [7, 9], and this work extends the result to channels over any alphabet.