Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComparing the Bit-MAP and Block-MAP Decoding Thresholds of Reed-Muller Codes on BMS Channels
83
0
0.0
(
0
)
Added by
Marco Mondelli
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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^{-delta}$, for some $delta>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.
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.
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.
This paper presents a novel successive factor-graph permutation (SFP) scheme that significantly improves the error-correction performance of Reed-Muller (RM) codes under successive-cancellation list (SCL) decoding. In particular, we perform maximum-likelihood decoding on the symmetry group of RM codes to carefully select a good factor-graph permutation on the fly. We further propose an SFP-aided fast SCL decoding that significantly reduces the decoding latency while preserving the error-correction performance of the code. The simulation results show that for the third and fourth order RM codes of length $256$, the proposed decoder reduces up to $85%$ of the memory consumption, $78%$ of the decoding latency, and more than $99%$ of the computational complexity of the state-of-the-art recursive projection-aggregation decoder at the frame error rate of $10^{-3}$.
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.
In this paper we propose efficient decoding techniques to significantly improve the error-correction performance of fast successive-cancellation (FSC) and FSC list (FSCL) decoding algorithms for short low-order Reed-Muller (RM) codes. In particular, we first integrate Fast Hadamard Transform (FHT) into FSC (FHT-FSC) and FSCL (FHT-FSCL) decoding algorithms to optimally decode the first-order RM subcodes. We then utilize the rich permutation group of RM codes by independently running the FHT-FSC and the FHT-FSCL decoders on a list of random bit-index permutations of the codes. The simulation results show that the error-correction performance of the FHT-FSC decoders on a list of $L$ random code permutations outperforms that of the FSCL decoder with list size $L$, while requiring lower memory requirement and computational complexity for various configurations of the RM codes. In addition, when compared with the state-of-the-art recursive projection-aggregation (RPA) decoding, the permuted FHT-FSCL decoder can obtain a similar error probability for the RM codes of lengths $128$, $256$, and $512$ at various code rates, while requiring several orders of magnitude lower computational complexity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
