Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userReed-Muller Codes Achieve Capacity on Erasure Channels
156
0
0.0
(
0
)
Added by
Santhosh Kumar
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We show that Reed-Muller codes achieve capacity under maximum a posteriori bit decoding for transmission over the binary erasure channel for all rates $0 < R < 1$. The proof is generic and applies to other codes with sufficient amount of symmetry as well. The main idea is to combine the following observations: (i) monotone functions experience a sharp threshold behavior, (ii) the extrinsic information transfer (EXIT) functions are monotone, (iii) Reed--Muller codes are 2-transitive and thus the EXIT functions associated with their codeword bits are all equal, and (iv) therefore the Area Theorem for the average EXIT functions implies that RM codes threshold is at channel capacity.
Consider a binary linear code of length $N$, minimum distance $d_{text{min}}$, transmission over the binary erasure channel with parameter $0 < epsilon < 1$ or the binary symmetric channel with parameter $0 < epsilon < frac12$, 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_{text{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^{frac12-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^{frac12})$ 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 well known Plotkin construction is, in the current paper, generalized and used to yield new families of Z2Z4-additive codes, whose length, dimension as well as minimum distance are studied. These new constructions enable us to obtain families of Z2Z4-additive codes such that, under the Gray map, the corresponding binary codes have the same parameters and properties as the usual binary linear Reed-Muller codes. Moreover, the first family is the usual binary linear Reed-Muller family.
The famous Barnes-Wall lattices can be obtained by applying Construction D to a chain of Reed-Muller codes. By applying Construction ${{D}}^{{(cyc)}}$ to a chain of extended cyclic codes sandwiched between Reed-Muller codes, Hu and Nebe (J. London Math. Soc. (2) 101 (2020) 1068-1089) constructed new series of universally strongly perfect lattices sandwiched between Barnes-Wall lattices. In this paper, we explicitly determine the minimum weight codewords of those codes for some special cases.
New quaternary Plotkin constructions are given and are used to obtain new families of quaternary codes. The parameters of the obtained codes, such as the length, the dimension and the minimum distance are studied. Using these constructions new families of quaternary Reed-Muller codes are built with the peculiarity that after using the Gray map the obtained Z4-linear codes have the same parameters and fundamental properties as the codes in the usual binary linear Reed-Muller family. To make more evident the duality relationships in the constructed families the concept of Kronecker inner product is introduced.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
