© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

On Unequal Error Protection Reed-Muller Codes

Dojun Rheel

Published Jan 1, 2000• 0 citations

Abstract

It is well known that Reed-Muller (RM) codes are not an linear unequal error protec- tion (LUEP) code because the set of minimum-weight vectors span Reed-Muller codes (punctured or not) (1,2). In this paper, we showed that most of RM codes are LUEP codes if RM codes are encoded with recursively decomposed trellis oriented generator ma- trix (TOGM) and maximum-likelihood trellis decod- ing (MLTD) is used. I. INTRODUCTION Uneqaul error protection codes protect some information bits against a great number of errors than other information bits. LUEP codes were first introduced by Masnick and Wolf (3). Boyarinov and Katsman (4) found conditions for linear codes to be LUEP. Let C be and (n, IC, d) linear code. It is shown in (l) that if the minimum-weight vectors of a linear code C does not span it, then C is an LUEP code. It is well known that their set of minimum-weight vectors span RM codes (punctured or not) (2). Therefore, RM codes are not LUEP codes in algebraic decoding. In the soft-decision maxi- mum likelihood decoding, bit-error-rate of RM code depends on the weight distribution of code. If non-systematic GM is used for encoding the RM code and soft-decision maximum likelohood decoding is used in decoding, different set of in- formation bits has a different bit-error-rate since each other has different weight distribution. Therefore, even though RM code is not an LUEP code in algebraci decoding, RM code is an LUEP code in soft-decision maximum likelihood decoding if systematic GM is not used for encoding. Especially, in this paper, LUEP RM codes are constructed by using recursively decomposed TOGM for encoding. Sim- ulations show that bit-error-rate of some information bits is almost twice better than that of the other information bits. By using the recursive decomposition, a simple trellis diagram with parallel structure for the RM code is devised. In ML trellis decoding, information bits are retrieved directly from the labeling of the trellis.

Related papers

On unequal error protection Reed-Muller codes

Do Jun Rhee

It is well known that Reed-Muller (RM) codes are not linear unequal error protection (LUEP) codes because the set of minimum-weight vectors span Reed-Muller codes (punctured or not). In this paper, we show that most RM codes are LUEP codes if RM codes are encoded with a recursively decomposed trellis oriented generator matrix (TOGM) and maximum-likelihood trellis decoding is used.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•0 citations

Soft-decision decoding of Reed-Muller codes: recursive lists

Ilya I. Dumer, Kirill Shabunov

Recursive list decoding is considered for Reed-Muller (RM) codes. The algorithm repeatedly relegates itself to the shorter RM codes by recalculating the posterior probabilities of their symbols. Intermediate decodings are only performed when these recalculations reach the trivial RM codes. In turn, the updated lists of most plausible codewords are used in subsequent decodings. The algorithm is further improved by using permutation techniques on code positions and by eliminating the most error-prone information bits. Simulation results show that for all RM codes of length 256 and many subcodes of length 512, these algorithms approach maximum-likelihood (ML) performance within a margin of 0.1 dB. As a result, we present tight experimental bounds on ML performance for these codes

IEEE Transactions on Information Theory•Mar 1, 2006•163 citations

Soft decision decoding of Reed-Muller codes: recursive lists

Ilya I. Dumer, Kirill Shabunov

Recursive list decoding is considered for Reed-Muller (RM) codes. The algorithm repeatedly relegates itself to the shorter RM codes by recalculating the posterior probabilities of their symbols. Intermediate decodings are only performed when these recalculations reach the trivial RM codes. In turn, the updated lists of most plausible codewords are used in subsequent decodings. The algorithm is further improved by using permutation techniques on code positions and by eliminating the most error-prone information bits. Simulation results show that for all RM codes of length 256 and many subcodes of length 512, these algorithms approach maximum-likelihood (ML) performance within a margin of 0.1 dB. As a result, we present tight experimental bounds on ML performance for these codes.

arXiv:1703.05305•Mar 14, 2017•0 citations

Recursive decoding of Reed-Muller codes

Ilya I. Dumer

New soft- and hard decision decoding algorithms are presented for general Reed-Muller codes $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ of length $2^{m}$ and distance $2^{m-r}$. We use Plotkin $(u,u+v)$ construction and decompose code $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ onto subblocks $u\in\left\{\genfrac{}{}{0pt}{}{m-1}{r}\right\} $ and $v\in\left\{\genfrac{}{}{0pt}{}{m-1}{r-1}\right\} .$ In decoding, we first try to find a subblock $v$ from the better protected code and then proceed with the block $u$. The likelihoods of the received symbols are recalculated in a way similar to belief propagation. Thus, decoding is relegated to the two constituent codes. We repeat this recursion and execute decoding only at the end nodes $\left\{\genfrac{}{}{0pt}{}{j}{1}\right\} $ and $\left\{\genfrac{}{}{0pt}{}{j}{j-1}\right\} $. The overall complexity has low order of $n\log n.$ It is shown that this decoding substantially outperforms other algorithms of polynomial complexity known for RM codes. In particular, for medium and high code rates, the algorithm corrects most error patterns of weight $d\ln d/2.$

arXiv:1703.05303•Mar 14, 2017•4 citations

Soft-decision majority decoding of Reed-Muller codes

Ilya I. Dumer, R.E. Krichevskiy

We present a new soft-decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of 2/sup m/ transmitted symbols are recalculated into the reliabilities of 2/sup m-r/ parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft-decision algorithm outperforms its conventional hard-decision counterpart by 10 log/sub 10/(/spl pi//2)/spl ap/2 dB at any given output error probability. For fixed code rate R and m/spl rarr//spl infin/, our algorithm increases almost 2/sup r/2/ times the correcting capability of soft-decision bounded distance decoding.

IEEE Transactions on Information Theory•Jan 1, 2000•31 citations

Recursive Decoding of Reed-Muller Codes Starting With the Higher-Rate Constituent Code

Mikhail Kamenev

Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length$(\leq 256)$RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length$2^{m}$and order$m-3$with reasonable complexity.

arXiv:2101.11328•IEEE Transactions on Information Theory•Jul 29, 2022•5 citations

It is well known that Reed-Muller (RM) codes are not an linear unequal error protec- tion (LUEP) code because the set of minimum-weight vectors span Reed-Muller codes (punctured or not) (1,2). In this paper, we showed that most of RM codes are LUEP codes if RM codes are encoded with recursively decomposed trellis oriented generator ma- trix (TOGM) and maximum-likelihood trellis decod- ing (MLTD) is used. I. INTRODUCTION Uneqaul error protection codes protect some information bits against a great number of errors than other information bits. LUEP codes were first introduced by Masnick and Wolf (3). Boyarinov and Katsman (4) found conditions for linear codes to be LUEP. Let C be and (n, IC, d) linear code. It is shown in (l) that if the minimum-weight vectors of a linear code C does not span it, then C is an LUEP code. It is well known that their set of minimum-weight vectors span RM codes (punctured or not) (2). Therefore, RM codes are not LUEP codes in algebraic decoding. In the soft-decision maxi- mum likelihood decoding, bit-error-rate of RM code depends on the weight distribution of code. If non-systematic GM is used for encoding the RM code and soft-decision maximum likelohood decoding is used in decoding, different set of in- formation bits has a different bit-error-rate since each other has different weight distribution. Therefore, even though RM code is not an LUEP code in algebraci decoding, RM code is an LUEP code in soft-decision maximum likelihood decoding if systematic GM is not used for encoding. Especially, in this paper, LUEP RM codes are constructed by using recursively decomposed TOGM for encoding. Sim- ulations show that bit-error-rate of some information bits is almost twice better than that of the other information bits. By using the recursive decomposition, a simple trellis diagram with parallel structure for the RM code is devised. In ML trellis decoding, information bits are retrieved directly from the labeling of the trellis.

Recursive list decoding is considered for Reed-Muller (RM) codes. The algorithm repeatedly relegates itself to the shorter RM codes by recalculating the posterior probabilities of their symbols. Intermediate decodings are only performed when these recalculations reach the trivial RM codes. In turn, the updated lists of most plausible codewords are used in subsequent decodings. The algorithm is further improved by using permutation techniques on code positions and by eliminating the most error-prone information bits. Simulation results show that for all RM codes of length 256 and many subcodes of length 512, these algorithms approach maximum-likelihood (ML) performance within a margin of 0.1 dB. As a result, we present tight experimental bounds on ML performance for these codes

Recursive list decoding is considered for Reed-Muller (RM) codes. The algorithm repeatedly relegates itself to the shorter RM codes by recalculating the posterior probabilities of their symbols. Intermediate decodings are only performed when these recalculations reach the trivial RM codes. In turn, the updated lists of most plausible codewords are used in subsequent decodings. The algorithm is further improved by using permutation techniques on code positions and by eliminating the most error-prone information bits. Simulation results show that for all RM codes of length 256 and many subcodes of length 512, these algorithms approach maximum-likelihood (ML) performance within a margin of 0.1 dB. As a result, we present tight experimental bounds on ML performance for these codes.

New soft- and hard decision decoding algorithms are presented for general Reed-Muller codes $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ of length

2^{m}

and distance

2^{m-r}

. We use Plotkin

(u,u+v)

construction and decompose code $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ onto subblocks $u\in\left\{\genfrac{}{}{0pt}{}{m-1}{r}\right\} $ and

v\in\left\{\genfrac{}{}{0pt}{}{m-1}{r-1}\right\} .

In decoding, we first try to find a subblock

v

from the better protected code and then proceed with the block

u

. The likelihoods of the received symbols are recalculated in a way similar to belief propagation. Thus, decoding is relegated to the two constituent codes. We repeat this recursion and execute decoding only at the end nodes $\left\{\genfrac{}{}{0pt}{}{j}{1}\right\} $ and $\left\{\genfrac{}{}{0pt}{}{j}{j-1}\right\} $. The overall complexity has low order of

n\log n.

It is shown that this decoding substantially outperforms other algorithms of polynomial complexity known for RM codes. In particular, for medium and high code rates, the algorithm corrects most error patterns of weight

d\ln d/2.

We present a new soft-decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of 2/sup m/ transmitted symbols are recalculated into the reliabilities of 2/sup m-r/ parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft-decision algorithm outperforms its conventional hard-decision counterpart by 10 log/sub 10/(/spl pi//2)/spl ap/2 dB at any given output error probability. For fixed code rate R and m/spl rarr//spl infin/, our algorithm increases almost 2/sup r/2/ times the correcting capability of soft-decision bounded distance decoding.

Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length

(\leq 256)

RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length

2^{m}

and order

m-3

with reasonable complexity.