We identify a large family of abelian codes that achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding. The codes in this family have rich automorphism groups, their lengths are odd integers, and they can asymptotically (in the block length) achieve any code rate. This family contains codes of prime power block lengths that were originally identified by Berman (1967) and later inves-tigated by Blackmore and Norton (2001), and also contains their generalization to any odd block length. We use Rajan and Siddiqi's (1992) characterization of abelian codes using discrete Fourier transform (DFT) to identify our code family and study their automorphism groups. We then use a result of Kumar, Calderbank and Pfister (2016) that relates the automorphism group of a code to its performance in the BEC to show that this code family achieves BEC capacity. The full version of this paper including the proofs of all claims and simulation results is available online [1]
We identify a large family of abelian codes that achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding. The codes in this family have rich automorphism groups, their lengths are odd integers, and they can asymptotically (in the block length) achieve any code rate. This family contains codes of prime power block lengths that were originally identified by Berman (1967) and later inves-tigated by Blackmore and Norton (2001), and also contains their generalization to any odd block length. We use Rajan and Siddiqi's (1992) characterization of abelian codes using discrete Fourier transform (DFT) to identify our code family and study their automorphism groups. We then use a result of Kumar, Calderbank and Pfister (2016) that relates the automorphism group of a code to its performance in the BEC to show that this code family achieves BEC capacity. The full version of this paper including the proofs of all claims and simulation results is available online [1]
A pruned variant of polar coding is proposed for binary erasure channel (BEC). Fix any BEC. For sufficiently small ε > 0, we construct a series of capacity achieving codes with block length N = ε-4.9, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. The given per-bit complexity bC is log-logarithmic in N, in Capacity - R, and in P. Beyond BEC, there is a generalization: Fix a prime q and fix a symmetric, q-ary-input, discrete-output memoryless channel. For sufficiently small ε > 0, we construct a series of error correction codes with block length N = ε-constant, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. Over general channels, this family of codes has the lowest per-bit time complexity among all capacity-achieving codes known to date.
In this paper, we consider the finite-length performance of a capacity-achieving sequence of irregular repeat-accumulate (IRA) code ensembles. We focus on a sequence of bit-regular ensembles with degree 3 which was shown to achieve capacity with bounded complexity [Pfister, 2005]. To characterize how fast the block length of the code must grow with respect to the truncation point of the degree distribution (i.e., maximum check degree), we compute an upper bound on the average weight enumerator. Based on this analysis, we present a particular truncation sequence that could achieve a minimum distance which grows like n/sup 1/3/ even as the gap to capacity goes to zero. We also consider the performance of these codes in the waterfall region by extending the finite-length scaling law [Amraoui] from low-density parity-check codes to IRA codes. This shows that the performance near the iterative decoding threshold is well characterized by a suitably scaled Q-function for large enough block length. Numerical results are given for the scaling parameters of this ensemble sequence and for a few other IRA codes. Unfortunately, the simulation results for the capacity-achieving sequence start to match the scaling law only for very large block lengths.
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.
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.
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.
The past decade has seen notable advances in our understanding of structured error-correcting codes, particularly binary Reed-Muller (RM) codes. While initial breakthroughs were for erasure channels based on symmetry, extending these results to the binary symmetric channel (BSC) and other binary memoryless symmetric (BMS) channels required new tools and conditions. Recent work uses nesting to obtain multiple weakly correlated looks at each code bit to establish capacity-achieving performance under bit-MAP and block-MAP decoding. This paper revisits and extends past approaches, aiming to simplify proofs, unify insights, remove unnecessary conditions, and provide new results. By leveraging powerful results from the analysis of boolean functions, we derive recursive bounds using two or three looks at each stage. This gives bounds on the bit-error probability that decay exponentially in the number of stages. For the BSC, we incorporate level-k inequalities and hypercontractive techniques to achieve the faster decay rate required for vanishing block-error probability. The same ideas also extend to product codes with RM component codes, which are transitive but not doubly-transitive in general, and yield vanishing bit-error and block-error probability at rates arbitrarily close to capacity. The results are presented in a semi-tutorial style, providing both theoretical insights and practical implications for future research on structured codes.