论文标题
关于随机和伪辅助代码的某些属性
On some properties of random and pseudorandom codes
论文作者
论文摘要
我们描述了在位图解码下二进制擦除通道上实现二进制线性代码的一些伪界特性（如Kudekar等人所示，其中包括双重传递代码，尤其是芦苇毛器代码）。我们表明，对于所有整数$ q \ ge 2 $，在噪声操作员的操作下，此类“伪兰多姆”代码的特征功能的$ \ ell_q $ norm降低了任何相同速率（和随机代码的快速）的快速降低。用信息理论术语，这意味着此代码的$ q^{th} $rényi熵在二进制对称频道上尽可能快地增加。特别是（服用$ q = \ infty $）这表明，对于一定的参数，此类代码在BSC上具有最小的渐近错误概率（等于随机代码的误差概率（等于随机代码）。 我们还研究了一定的局部模式的次数，即“菱形” $ 4 $ - 组成的代码，并以线性代码出现，并表明，对于一定范围的参数，对于随机代码而言，对于伪随机代码，该数字与该数字相似。
We describe some pseudorandom properties of binary linear codes achieving capacity on the binary erasure channel under bit-MAP decoding (as shown in Kudekar et al this includes doubly transitive codes and, in particular, Reed-Muller codes). We show that for all integer $q \ge 2$ the $\ell_q$ norm of the characteristic function of such 'pseudorandom' code decreases as fast as that of any code of the same rate (and equally fast as that of a random code) under the action of the noise operator. In information-theoretic terms this means that the $q^{th}$ Rényi entropy of this code increases as fast as possible over the binary symmetric channel. In particular (taking $q = \infty$) this shows that such codes have the smallest asymptotic undetected error probability (equal to that of a random code) over the BSC, for a certain range of parameters. We also study the number of times a certain local pattern, a 'rhombic' $4$-tuple of codewords, appears in a linear code, and show that for a certain range of parameters this number for pseudorandom codes is similar to that for a random code.
