论文标题
在解码BSC上恒定错误的代码上
On codes decoding a constant fraction of errors on the BSC
论文作者
论文摘要
使用Kudekar等人的技术和结果。我们加强了线性代码在BEC上实现能力的重量分布的界限，这是第一作者所展示的。特别是，我们表明，对于任何偶然的二进制二进制线性代码$ c \ subseteq \ {0,1 \}^n $ as速率的$ 0 <r <1 $，重量分布$ \ left（a_0，...，a_n \ right）$ \ min \ {i，n-i \}} $。 对于具有最小距离的双传递代码，至少$ω\ left（n^c \ right）$，$ 0 <c \ le 1 $，在此限制中的$ 2^{o（n）} $的错误因素可以以$ 1-r $替换为$ 1-r $的费用，而用较小的常数$ a = a（r，c）<1-1- <1- r $。此外，在芦苇毛刺代码的特殊情况下，由于这些代码的额外对称性，该错误因素可以基本上不成本去除。 This implies that for any doubly transitive code $C$ of rate $R$ with minimal distance at least $Ω\left(n^c\right)$, there exists a positive constant $p = p(R,c)$ such that $C$ decodes errors on $\mathrm{BSC}(p)$ with high probability if $p < p(R,c)$.对于双重速率（小于某些绝对常数）的双重传递代码，可以省略最小距离的要求，因此，此关键概率$ p（r）$仅取决于$ r $。此外，$ p（r）\ rightarrow \ frac12 $ as $ r \ rightarrow 0 $。 特别是，如果\ [r〜 <〜1- \ big（4p（1-p）\ big）^{\ frac {\ frac {1} {1} {1} {4 \ ln 2}} anch和一个问题。
Using techniques and results from Kudekar et al. we strengthen the bounds on the weight distribution of linear codes achieving capacity on the BEC, which were shown by the first author. In particular, we show that for any doubly transitive binary linear code $C \subseteq \{0,1\}^n$ of rate $0 < R < 1$ with weight distribution $\left(a_0,...,a_n\right)$ holds $a_i \le 2^{o(n)} \cdot (1-R)^{-2 \ln 2 \cdot \min\{i, n-i\}}$. For doubly transitive codes with minimal distance at least $Ω\left(n^c\right)$, $0 < c \le 1$, the error factor of $2^{o(n)}$ in this bound can be removed at the cost of replacing $1-R$ with a smaller constant $a = a(R,c) < 1- R$. Moreover, in the special case of Reed-Muller codes, due to the additional symmetries of these codes, this error factor can be removed at essentially no cost. This implies that for any doubly transitive code $C$ of rate $R$ with minimal distance at least $Ω\left(n^c\right)$, there exists a positive constant $p = p(R,c)$ such that $C$ decodes errors on $\mathrm{BSC}(p)$ with high probability if $p < p(R,c)$. For doubly transitive codes of a sufficiently low rate (smaller than some absolute constant) the requirement on the minimal distance can be omitted, and hence this critical probability $p(R)$ depends only on $R$. Furthermore, $p(R) \rightarrow \frac12$ as $R \rightarrow 0$. In particular, a Reed-Muller code $C$ of rate $R$ decodes errors on $\mathrm{BSC}(p)$ with high probability if \[ R ~<~ 1 - \big(4p(1-p)\big)^{\frac{1}{4 \ln 2}}, \] answering a question of Abbe, Hazla, and Nachum.
