A Criterion for Decoding on the BSC

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| = \alpha N] \leq 2^{-(1-h(\alpha)) $\mathsf{d}\mathsf{i}\mathsf{m}$©}$.
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}(\mathrm{\mid }c\mathrm{\mid }{)}^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.