2022/02/01 by Anup Rao, Rao, Anup, Oscar Sprumont +1
Computer Science · Engineering · #Coding theory and cryptography #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2202.00240
openalex publication_date 2022/02/01 · openalex created_date 2022/06/19 · openalex updated_date 2026/07/28
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 ⊆ \mathbbF2N: Prc ∈ C[|c| = αN] ≤ 2-(1-h(α)) dim(C). 2) We give a criterion that certifies that a linear code C can be decoded on the binary symmetric channel. Let Ks(x) denote the Krawtchouk polynomial of degree s, and let C^⊥ denote the dual code of C. We show that bounds on 𝔼c ∈ C⊥[ 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^⊥ is sufficiently close to the binomial distribution in some interval around (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.