On some properties of random and pseudorandom codes

arXiv2206.05135MaRDI QIDQ6401698FDOQ6401698

Authors: Alex Samorodnitsky 

Publication date: 10 June 2022

Abstract: 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 $qge2$ the $el{l}_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'enyi 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.

This page was built for publication: On some properties of random and pseudorandom codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6401698)