A Criterion for Decoding on the BSC

Our weight distribution bound for transitive linear codes (Theorem 1) is proven by showing that the entropy of a uniformly random codeword of weight $\alpha N$ is small. To do this, we analyze the entropy of the coordinates corresponding to linearly independent columns of the generator matrix. Transitivity implies that every coordinate in the code has the same entropy, and subadditivity of entropy can then be used to bound the entropy of the entire distribution.

To obtain our decoding criterion, we make use of a connection between the probability of a decoding error and the $\ell_{2}$ norm of the coset distribution of the code. To explain the intuition, let us start by assuming that exactly $\epsilon N$ of the coordinates in the codeword are flipped, although our results actually hold over the BSC as well. Let $z$ be the vector in $\mathbb{F}_{2}^{N}$ that represents the errors introduced by the channel, and let $H$ be the parity check matrix of the code. Then by standard arguments, if $z$ can be recovered from $Hz^{\intercal}$, the codeword can be decoded. In the case where $z$ is uniformly distributed on vectors of weight $\epsilon N$, this amounts to showing that with high probability, the coset of $z$ does not contain any string of weight $\epsilon N$ (in other words, there is no $w\in\mathbb{F}_{2}^{N}$ of weight $|w|=\epsilon N$ such that $Hz^{\perp}=Hw^{\perp}$). This can be understood by computing the norm

$$\|f\|_{2}^{2}=\frac{1}{2^{N}}\sum_{y}f(y)^{2}=\frac{1}{2^{N}}\sum_{y}\Pr[Hz^{\intercal}=y^{\intercal}]^{2},$$

where $f(y)=\Pr[Hz^{\intercal}=y^{\intercal}]$. The norm above is always at least $2^{-N}\binom{N}{\epsilon N}^{-1}$, and if it is close to $2^{-N}\binom{N}{\epsilon N}^{-1}$ then the code can be decoded with high probability. If $\|f\|_{2}^{2}$ is larger than $2^{-N}\binom{N}{\epsilon N}^{-1}$, then we show that the code can be list-decoded with high probability, where the size of the list is related to $2^{N}\binom{N}{\epsilon N}\|f\|_{2}^{2}$.

Thus, to understand decoding, we need to understand $\|f\|_{2}^{2}$. Using Fourier analysis, we express this quantity as

$\displaystyle\|f\|_{2}^{2}=\sum_{j=0}^{N}\Pr[|c^{\perp}|=j]\cdot K_{\epsilon N}(j)^{2},$

(2)

where $c^{\perp}$ is a uniformly random codeword in the dual code and $K_{\epsilon N}$ is the Krawtchouk polynomial of degree $\epsilon N$. We note that such relations for the coset weight distribution have been used to understand the discrepancy of subsets of the sphere, as well as subsets of other homogeneous spaces. In particular, (2) was proven in a slightly different form in [Bar21] (see Theorem 2.1 and Lemma 4.1), whereas over $\mathbb{R}^{N}$ results of this type had previously been derived in [BDM18, Skr19].

Using estimates for the magnitude of Krawtchouk polynomials and bounds for the weight distribution of the dual code $C^{\perp}$, one can thus bound the norm $\|f\|_{2}^{2}$ in the set-up where the error string $z$ is a random vector of weight exactly $\epsilon N$. Using essentially the same techniques, one can also bound the norm $\|f\|_{2}^{2}$ when the error string $z$ is a random vector of weight $\approx\epsilon N$, i.e. $z$ is taken uniformly at random from the set $S=\{x\in\mathbb{F}_{2}^{N}:|x|=\epsilon N\pm N^{3/4}\}$.

Our next step is then to show that the $\ell_{2}$ norm corresponding to the $\epsilon$-biased distribution is very similar to the $\ell_{2}$ norm corresponding to the uniform distribution over $S$. Intuitively, this is because $S$ only contains a very small range of weights, so the $\epsilon$-biased distribution and the uniform distribution must behave very similarly over strings of weight in $S$. It then follows that their corresponding $\ell_{2}$ norms must be similar as well.

Our decoding criteria (Theorem 2, Corollary 3) are thus obtained by bounding the norm $\|f\|_{2}^{2}$ using estimates for Krawtchouk polynomials and for the weight distribution of the dual code $C^{\perp}$. Our list-decoding results (Theorems 4 and 5) then follow from our weight bound for transitive codes (Theorem 1) and from a weight bound of Samorodnitsky for Reed-Muller codes (Theorem 6).

It has been shown that LDPC codes achieve capacity over Binary Memoryless Symmetric Channels (BMS) [LMS⁺97, KRU13, Gal62], which includes both the BSC and the BEC. These constructions are not deterministic, and it is only with the advent of polar codes [Ari09] that we obtained capacity-achieving codes with both a deterministic constructions and efficient encoding and decoding algorithms.

Polar codes are closely related to Reed-Muller codes, in the sense that they also consist of subspaces that correspond to polynomials over $\mathbb{F}_{2}\cite[cite]{[\@@bibref{}{arikan2009polar}{}{}]}$. In [Ari09] it was shown that Polar codes achieve capacity over the BSC, and algorithms were given to both encode and decode them.

It has long been believed that Reed-Muller codes achieve capacity, and significant progress has been made in that direction over the last few years. (See [ASY21] for a discussion on the subject, as well as a thorough exposition to Reed-Muller codes). Abbe, Shpilka and Wigderson first showed that Reed-Muller codes achieve capacity over the BSC and the BEC for sub-constant and super-constant rates [ASW15]. Kudekar, Kumar, Mondelli, Pfister, Sasoglu and Urbanke then proved that in the constant rate regime, Reed-Muller codes achieve capacity over the BEC channel [KKM⁺16]. Abbe and Ye showed that the Reed-Muller transform polarizes the conditional mutual information, and proved that some non-explicit variant of the Reed-Muller code achieves capacity [AY19]. (They conjecture that this variant is in fact the Reed-Muller code itself). Hazla, Samorodnitsky and Sberlo then proved that Reed-Muller codes of constant rates can decode a constant fraction of errors on the BSC [HSS21]; this had previously been shown for Almost-Reed-Muller codes by Abbe, Hazla and Nachum [AHN21]. Most recently, Reeves and Pfister showed that Reed-Muller codes achieve capacity over all BMS channels under bit-MAP decoding [RP21], i.e. that one can with high probability recover any single bit of the original codeword (but not with high enough probability that one could take a union bound). Despite these breakthroughs, the conjecture that Reed-Muller codes achieve capacity over all BMS channels under block-MAP decoding (i.e. recover the whole codeword with high probability) is ultimately still open.

Weight Bounds for Reed-Muller Codes
Several past works have proven bounds on the weight distribution of Reed-Muller codes. Kaufman, Lovett and Porat gave asymptotically tight bounds on the weight distribution of Reed-Muller codes of constant degree [KLP12]. Abbe, Shpilka and Wigderson then built on these techniques to obtain bounds for all degrees smaller than $\frac{n}{4}$ [ASW15], before Sberlo and Shpilka again improved the approach and obtained bounds for all degrees [SS20]. Most recently, Samorodnitsky used completely different ideas to obtain weight bounds in the regime where both the rate of the code and the normalized weight of the codeword are $\Theta(1)$ [Sam20]. We will later use his following result in our list-decoding arguments:

These bounds are strong when $\alpha\ll 1/2$. For $\alpha$ close to $1/2$, the first results we are aware of are due to Ben-Eliezer, Hod and Lovett [BHL12]. Their bounds, which were extended to Reed-Muller codes over prime fields by Beame, Oveis Gharan and Yang [BGY20], are strongest when the degree is sublinear. Sberlo and Shpilka then obtained bounds for all degrees in [SS20], while Samorodnitsky again obtained bounds in the regime where both $\alpha$ and $\eta$ are $\Theta(1)$ [Sam20].

We note that in some regimes (for e.g. when the degree satisfies $0.38n<d<0.499n$ and $\alpha$ is larger than some constant depending on $d/n$), our Theorem 1 improves on all the aforementioned weight bounds. See Appendix A for some details.

List Decoding
List decoding was proposed by Elias in 1957 as an alternative to unique decoding [Eli57]. In the list decoding framework, the receiver of a corrupted codeword is asked to output a list of potential codewords, with the guarantee that with high probability one of these codewords is the original one. This of course allows for a greater fraction of errors to be tolerated.

The list decoding community has largely focused on proving results for the adversarial noise model, and many codes are now known to achieve list-decoding capacity. For example uniformly random codes achieve capacity, as do uniformly random linear codes [GHSZ02, LW18, GHK11]. Folded Reed-Solomon codes were the first explicit codes to provably achieve list-decoding capacity [GR08], followed by several others a few years later [GX12, Kop15, HRW17, MRR⁺20]. For the rest of this paper however, we will exclusively work in the model where the errors are stochastic. In this model, the strongest known list decoding bound for the code $\mathsf{RM}(n,d)$ with $\binom{n}{\leq d}=\eta N>N-N\log(1+2\sqrt{\epsilon(1-\epsilon)})$ is, to our knowledge, that one can output a list $T$ of size

$\displaystyle|T|=2^{\epsilon N\log\frac{4\epsilon(1-\epsilon)}{(1-\eta)^{4\ln 2}}+o(N)}$

(3)

and succeed with high probability in decoding $\epsilon$-errors. This result, although not explicitly stated in [Sam20], can be obtained from his weight bound of Theorem 6 by bounding the expected number of codewords that end up closer to the received string than the original codeword, and then applying Markov’s inequality. We note that the expression in (3) stays strictly below the optimal size of $2^{h(\epsilon)N-(1-\eta)N+o(N)}$ (see Appendix D.1 for a proof of this).

Krawtchouk polynomials
The Krawtchouk polynomial of degree $s$ is the polynomial

$$K_{s}(x)=\sum_{j=0}^{s}(-1)^{j}\binom{x}{j}\binom{N-x}{s-j}.$$

For any subset $S\subseteq\{0,...,N\}$, we will be interested in the corresponding polynomial $K_{S}(x):=\sum_{s\in S}K_{s}(x)$. For $v\in\mathbb{F}_{2}^{N}$, we will sometimes abuse notation and use $K_{s}(v)$ to mean $K_{S}(|v|)$. The following proposition follows from standard results (see for instance [KL99], or Theorem 16 in [MS77]).

Good estimates for Krawtchouk polynomials of any degree were obtained in [KL95, IS98, Pol19] (see for e.g. [Pol19], Lemma 2.1). These estimates are asymptotically tight in the exponent. Note that $|K_{s}(x)|=|K_{s}(N-x)|=|K_{N-s}(x)|$, so it suffices to understand the case $x,s\leq\frac{N}{2}$.

As the second expression can be somewhat cumbersome to use, [Pol19] also gives the following weaker bound (see Lemma 2.2 and equation 2.10 in [Pol19]):

We will need the above estimates when using our Theorem 2 to obtain list-decoding results for transitive codes and Reed-Muller codes.

An $N$-bit code is a subset $C\subseteq\mathbb{F}_{2}^{N}$. Whenever $C$ is a subspace of $\mathbb{F}_{2}^{N}$, we say that $C$ is a linear code. Any linear code $C\subseteq\mathbb{F}_{2}^{N}$ can be represented by its generator matrix, which is a $\dim\textnormal{ C}\times N$ matrix $G$ whose rows form a basis for $C$. The matrix $G$ generates all codewords of $C$ in the sense that

$$C=\{vG:v\in\mathbb{F}_{2}^{\textnormal{dim }C}\}.$$

Another useful way to describe a linear code $C\subseteq\mathbb{F}_{2}^{N}$ is via its parity-check matrix, which is an $(N-\dim\textnormal{ C})\times N$ matrix $H$ whose rows span the orthogonal complement of $C$. The linear code $C$ can then be expressed as

$$C=\{c\in\mathbb{F}_{2}^{N}:Hc^{\intercal}=0\}.$$

One property that will play an important role is transitivity, which we define below:

We note that the dual code of a transitive code is also transitive (see Appendix D.2 for the proof).

We will denote by $\mathsf{RM}(n,d)$ the Reed-Muller code with $n$ variables and degree $d$. Throughout this section, we let $M$ be the generator matrix of $\mathsf{RM}(n,d)$; this is an $\binom{n}{\leq d}\times N$ matrix whose rows correspond to sets of size at most $d$, ordered lexicographically, and whose columns correspond to elements of $\mathbb{F}_{2}^{n}$. For $S\subseteq[n],|S|\leq d$ and $x\in\mathbb{F}_{2}^{n}$, the corresponding entry is $M_{S,x}=\prod_{j\in S}x_{j}$. If $S$ is empty, this entry is set to $1$.

If $v\in\mathbb{F}_{2}^{\binom{n}{\leq d}}$ is a row vector, $v$ can be thought of as describing the coefficients of a multilinear polynomial in $\mathbb{F}_{2}[X_{1},\dotsc,X_{n}]$ of degree at most $d$. The row vector $vM$ is then the evaluations of this polynomial on all inputs from $\mathbb{F}_{2}^{n}$. It is well known that $M$ has full rank, $\binom{n}{\leq d}$. In fact we have the following standard fact (see Appendix D.3 for the proof):

The parity-check matrix of the Reed-Muller code is known to be the same as the generator matrix of a different Reed-Muller code. Namely, let $H$ be the $\binom{n}{\leq n-d-1}\times N$ generator matrix for the code $\mathsf{RM}(n,n-d-1)$. Then $H$ has full rank, and $MH^{\intercal}=0$. So, the rows of $H$ are a basis for the orthogonal complement of the span of the rows of $M$. Reed-Muller codes also have useful algebraic features, notably transitivity:

See Appendix D.3 for the proof.

The binary entropy function $h:[0,1]\rightarrow\mathbb{R}$ is defined to be

$$h(\epsilon)=\epsilon\cdot\log\frac{1}{\epsilon}+(1-\epsilon)\cdot\log\frac{1}{1-\epsilon}.$$

The following fact allows us to approximate binomial coefficients using the entropy function:

The leftmost inequality is a consequence of Stirling’s approximation for the binomial coefficients, and the rightmost is a consequence of the sub-additivity of entropy.

The following lemma, which is essentially a 2-way version of Pinsker’s inequality, gives a useful way to control the entropy function near $1/2$.

See Appendix D.4 for the proof.

There are two types of probability distributions that we will use frequently. The first one is the $\epsilon$-Bernoulli distribution over $\mathbb{F}_{2}^{N}$, which we will denote by

$$P_{\epsilon}(z)=\epsilon^{|z|}(1-\epsilon)^{N-|z|}.$$

The second one is the uniformly random distribution over some set $T$, which we will denote by

$$\mathcal{D}(T)(z)=\begin{cases}\frac{1}{|T|}&\text{if $z\in T$,}\\ 0&\text{otherwise.}\end{cases}.$$

There are two particular cases for the uniform distribution that will occur often enough that we attribute them their own notation. The first one is the uniform distribution over $\mathbb{F}_{2}^{t}$, which we will denote by

$$\mu_{t}=\mathcal{D}(\mathbb{F}_{2}^{t}).$$

The second one is the uniform distribution over all vectors $z\in\mathbb{F}_{2}^{N}$ of weight $|z|\in S$, for some $S\subseteq\{0,...,N\}$. We will denote this probability distribution by

$$\lambda_{S}=\mathcal{D}(\{z\in\mathbb{F}_{2}^{N}:|z|\in S\}).$$

We will need two very standard results of probability theory (see for e.g. [BLM13]): Markov’s inequality and Chernoff’s bound. We start with Markov’s inequality.

We will also need Chernoff’s bound:

The Fourier basis is a useful basis for the space of functions mapping $\mathbb{F}_{2}^{N}$ to the real numbers. We recall some of its properties below (see for e.g. [dW08]). For $f,g\in\mathbb{F}_{2}^{N}\rightarrow\mathbb{R}$, define the inner product

$$\langle f,g\rangle=\frac{1}{2^{N}}\sum_{x\in\mathbb{F}_{2}^{N}}f(x)g(x).$$

For every $x,y\in\mathbb{F}_{2}^{N}$, define the character

$$\chi_{y}(x)=(-1)^{\sum_{j=1}^{N}x_{j}y_{j}}.$$

These functions form an orthonormal basis, namely for $y,y^{\prime}\in\mathbb{F}_{2}^{N}$,

$\displaystyle\langle\chi_{y},\chi_{y^{\prime}}\rangle=\begin{cases}1&\text{if $y=y^{\prime}$,}\\ 0&\text{otherwise.}\end{cases}$

We define the Fourier coefficients $\hat{f}(y)=\langle f,\chi_{y}\rangle$. Then for $f,g:\mathbb{F}_{2}^{N}\rightarrow\mathbb{R}$, we have

$$\langle f,g\rangle=\sum_{y\in\mathbb{F}_{2}^{N}}\hat{f}(y)\cdot\hat{g}(y).$$

In particular,

$$\|f\|^{2}_{2}=\langle f,f\rangle=\sum_{y}\hat{f}(y)^{2}.$$