Reed-Muller codes: Thresholds and weight distribution
Mondelli, Marco
Kudekar, Shrinivas
Kumar, Santosh
Pfister, Henry D.
Şaşoğlu, Eren
Urbanke, Rüdiger
We describe a new method to compare the bit-MAP and block-MAP decoding thresholds of Reed-Muller (RM) codes for transmission over a binary memoryless symmetric channel. The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory and it has recently been answered in the affirmative for transmission over
erasure channels. 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. A natural question is what happens under block-MAP decoding. If the minimum distance of the code family is close to linear (e.g., of order N/ log(N)), then one can combine an upper bound on the bit-MAP error probability with a lower bound on the minimum distance to show that the code family is also capacity-achieving under block-MAP decoding. This strategy is successful for BCH codes. Unfortunately, the minimum distance of RM codes scales only as √N, which does not suffice to obtain the desired result. Then, one can exploit further symmetries of RM codes to show that the bit-MAP threshold is sharp enough so that the block erasure probability also tends 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 the 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.
ETH Zürich
2016
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/6770
Mondelli M, Kudekar S, Kumar S, Pfister HD, Şaşoğlu E, Urbanke R. Reed-Muller codes: Thresholds and weight distribution. In: <i>24th International Zurich Seminar on Communications</i>. ETH Zürich; 2016:50. doi:<a href="https://doi.org/10.3929/ETHZ-A-010646484">10.3929/ETHZ-A-010646484</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.3929/ETHZ-A-010646484
info:eu-repo/semantics/closedAccess