论文标题
在BSC上解码的标准
A Criterion for Decoding on the BSC
论文作者
论文摘要
我们提出了一种表明线性代码对随机错误有弹性的方法。我们使用这种方法来获得及其及其及其及其透视码的解码结果。我们总体上提供了三种有关线性代码的结果，尤其是瞬态线性代码。 1）我们对每个传递线性代码的重量分布都紧密绑定=αn] \ leq 2^{ - （1-H（α））\ Mathsf {dim}（c）} $。 2）我们提供一个标准，该标准证明可以在二进制对称频道上解码线性代码$ c $。令$ k_s（x）$表示度$ s $的krawtchouk多项式，让$ c^\ perp $表示$ c $的双代码。我们显示，在$ \ mathbb {e} _ {c \ in c^{\ perp}}} [k__ {εn}（| c |）^2] $上的界限表示，$ c $暗示$ c $从具有参数$ε$的二进制对称性通道上的错误中恢复。较弱的边界可用于使用类似方法获得列表编码结果。我们标准的结果是，每当$ c^\ perp $的重量分布在$ \ frac {n} {2} $附近的某个间隔内足够接近二项式分布时，$ c $就可以抵抗$ε$ -ERRORS。 3）我们将KRAWTCHOUK多项式的已知估计值与用于及时代码的重量结合，并具有有关芦苇毛刺代码的已知权重界，以获得这两个代码家族的列表编码结果。在某些制度中，我们针对Reed-Muller代码的界限实现了速率和列表规模之间的信息理论最佳权衡。
We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive codes and Reed-Muller codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular. 1) We give a tight bound on the weight distribution of every transitive linear code $C \subseteq \mathbb{F}_2^N$: $\Pr_{c \in C}[|c| = αN] \leq 2^{-(1-h(α)) \mathsf{dim}(C)}$. 2) We give a criterion that certifies that a linear code $C$ can be decoded on the binary symmetric channel. Let $K_s(x)$ denote the Krawtchouk polynomial of degree $s$, and let $C^\perp$ denote the dual code of $C$. We show that bounds on $\mathbb{E}_{c \in C^{\perp}}[ K_{εN}(|c|)^2]$ imply that $C$ recovers from errors on the binary symmetric channel with parameter $ε$. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $C^\perp$ is sufficiently close to the binomial distribution in some interval around $\frac{N}{2}$, $C$ is resilient to $ε$-errors. 3) We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for Reed-Muller codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for Reed-Muller codes achieve the information-theoretic optimal trade-off between rate and list size.
