Consider a binary linear code of length N, minimum distance dmin, transmission over the binary erasure channel with parameter 00 if the minimum distance is large. In particular the width of the transition is of order O(1/√dmin). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as O(1/N1/2-κ), for any κ > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since O(1/N1/2) is the smallest transition possible for any code, we speak of “almost” optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma.
Consider a binary linear code of length N, minimum distance dmin, transmission over the binary erasure channel with parameter 00 if the minimum distance is large. In particular the width of the transition is of order O(1/√dmin). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as O(1/N1/2-κ), for any κ > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since O(1/N1/2) is the smallest transition possible for any code, we speak of “almost” optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma.
Consider a binary linear code of length N, minimum distance d-{\min}, transmission over the binary erasure channel with parameter 0 < \epsilon < 1 or the binary symmetric channel with parameter 0 < \epsilon < \frac{1}{2}, and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions 'quickly' from \delta to 1-\delta for any \delta > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/\sqrt{d-{\min}}). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as \Theta(1/N^{\frac{1}{2}-\kappa}), for any \kappa > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since \Theta(1/N^{\frac{1}{2}}) is the smallest transition possible for any code, we speak of 'almost' optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma.
We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In other words, we show that symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing blocklength and converging rate achieves capacity. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proof are the sharp threshold property for symmetric monotone boolean functions and the area theorem for extrinsic information transfer functions.
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⊆F2N: 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 Ec∈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 2N, 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.
The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N−δ, for some δ > 0. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.
Recently, sequences of error-correcting codes with doubly-transitive permutation groups were shown to achieve capacity on erasure channels under symbol-wise maximum a posteriori (MAP) decoding. From this, it follows that Reed-Muller and primitive narrow-sense BCH codes achieve capacity in the same setting. In this article, we extend this result to a large family of cyclic codes by considering codes whose permutation groups satisfy a condition weaker than double transitivity. The article combines two simple technical contributions. First, we show that the transition width of a monotone boolean function is O(1/log k), where k is the size of the smallest orbit induced by its symmetry group. The proof is based on Talagrand's lower bound on influences for monotone boolean functions. Second, we consider the extrinsic information transfer (EXIT) function of an Fq-linear cyclic code whose blocklength N divides qt- 1 and is coprime with q - 1. We show that this EXIT function is a monotone boolean function whose symmetry group contains no orbits of size smaller than the smallest prime divisor of t. Combining these, we show that sequences of cyclic codes, whose blocklengths satisfy the above conditions, achieve capacity on the q-ary erasure channel if all prime divisors of t tend to infinity.
We provide a general framework for bounding the block error threshold of a linear codeC⊆F2Nover the erasure channel in terms of its bit error threshold. Our approach relies on understanding the minimum support weight of anyr-dimensional subcode ofC, for all small values ofr. As a proof of concept, we use our machinery to obtain a new proof of the celebrated result that Reed-Muller codes achieve capacity on the erasure channel with respect to block error probability.