Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

On unequal error protection Reed-Muller codes

Do Jun Rhee

Published Nov 7, 2002• 0 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2000.866297

Related papers

On Unequal Error Protection Reed-Muller Codes

Dojun Rheel

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.

•Jan 1, 2000•0 citations

Recursive decoding of Reed-Muller codes

Ilya I. Dumer, Kirill Shabunov

We use the Plotkin (u,u+v)-construction for general Reed-Muller codes (m,r) and relegate decoding to the two constituent RM codes. First, we use the better protected code (m-1,r-1) to find a subblock v. Then we proceed with the block u from the code (m-l,r). We repeat this recursion on both halves and recalculate the reliabilities of the received symbols. In the end, we perform maximum likelihood decoding on the biorthogonal codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•20 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•7 citations

Reed-Muller Codes: Spherically-Punctured Codes and Decoding Algorithms

Olga Kapralova

Reed-Muller (RM) codes are classical codes that have enjoyed unabated interest since their introduction in 1954 due to their simple recursive structure and low-complexity decoding. The main goal of the thesis is to develop new coding techniques that can improve the performance of RM codes. In this work, we wish to keep the recursive low-complexity structure of RM codes while extending the sets of possible parameters and decoding algorithms. We address this task using two different methods. First, we consider new code constructions that extend code parameters using puncturing. Second, we design new decoding algorithms that repeatedly use the gradient properties of the classic recursive structure to improve code performance of RM codes. In the first part of the thesis, we propose a new class of codes that enjoy the recursive structure of RM codes, but reduce the exponential length of RM codes to a polynomial in m. These codes are obtained by puncturing classical RM codes, i.e. by restricting binary RM codes to small subsets of their positions. We study new recursive properties of these codes and analyze their parameters. In the second part of the thesis we develop new decoding algorithms for binary RM codes of second order that achieve near optimal performance for short and moderate code lengths. RM codes enjoy some simple decoding procedures; however, these algorithms fall short of optimal performance on moderate block lengths. We propose a suboptimal algorithm that reduces the complexity of maximum-likelihood decoding from super-polynomial order O(n(m+1)/2) to polynomial order O(mn2). At the same time, our numerical simulations show that the new algorithm performs very closely to its maximum-likelihood counterpart for blocks of up to several thousand bits.

•Jan 1, 2013•1 citation

Efficiently Decoding Reed–Muller Codes From Random Errors

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Reed-Muller (RM) codes encode an m-variate polynomial of degree at most r by evaluating it on all points in {0,1}m. We denote this code by RM(r,m). The minimum distance of RM(r,m) is 2m-rand so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this paper we give an efficient algorithm (in the block length n=2m) for decoding random errors in RM codes far beyond the minimum distance. Specifically, for low-rate codes (of degree r=o(√m)), we can correct a random set of (1/2-o(1))n errors with high probability. For high rate codes (of degree m-r for r=o(√m/log m)), we can correct roughly mr/2errors. More generally, for any integer r, our algorithm can correct any error pattern in RM(m-(2r+2),m), for which the same erasure pattern can be corrected in RM(m-(r+1),m). The results above are obtained by applying recent results of Abbe, Shpilka, and Wigderson (STOC, 2015) and Kudekar et al. (STOC, 2016) regarding the ability of RM codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding RM codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the error-locating pair method of Pellikaan, Duursma, and Kötter that generalizes the Berlekamp-Welch algorithm for decoding Reed-Solomon codes.

arXiv:1503.09092•IEEE Transactions on Information Theory•Feb 17, 2017•30 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•IEEE Transactions on Information Theory•Mar 1, 2006•161 citations
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.
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.
New soft- and hard decision decoding algorithms are presented for general Reed-Muller codes $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ of length 2m2^{m}2m and distance 2m−r2^{m-r}2m−r. We use Plotkin (u,u+v)(u,u+v)(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∈{m−1r−1}.v\in\left\{\genfrac{}{}{0pt}{}{m-1}{r-1}\right\} .v∈{r−1m−1​}. In decoding, we first try to find a subblock vvv from the better protected code and then proceed with the block uuu. 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 nlog⁡n.n\log n.nlogn. 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 dln⁡d/2.d\ln d/2.dlnd/2.
Reed-Muller (RM) codes are classical codes that have enjoyed unabated interest since their introduction in 1954 due to their simple recursive structure and low-complexity decoding. The main goal of the thesis is to develop new coding techniques that can improve the performance of RM codes. In this work, we wish to keep the recursive low-complexity structure of RM codes while extending the sets of possible parameters and decoding algorithms. We address this task using two different methods. First, we consider new code constructions that extend code parameters using puncturing. Second, we design new decoding algorithms that repeatedly use the gradient properties of the classic recursive structure to improve code performance of RM codes. In the first part of the thesis, we propose a new class of codes that enjoy the recursive structure of RM codes, but reduce the exponential length of RM codes to a polynomial in m. These codes are obtained by puncturing classical RM codes, i.e. by restricting binary RM codes to small subsets of their positions. We study new recursive properties of these codes and analyze their parameters. In the second part of the thesis we develop new decoding algorithms for binary RM codes of second order that achieve near optimal performance for short and moderate code lengths. RM codes enjoy some simple decoding procedures; however, these algorithms fall short of optimal performance on moderate block lengths. We propose a suboptimal algorithm that reduces the complexity of maximum-likelihood decoding from super-polynomial order O(n(m+1)/2) to polynomial order O(mn2). At the same time, our numerical simulations show that the new algorithm performs very closely to its maximum-likelihood counterpart for blocks of up to several thousand bits.
Reed-Muller (RM) codes encode an m-variate polynomial of degree at most r by evaluating it on all points in {0,1}m. We denote this code by RM(r,m). The minimum distance of RM(r,m) is 2m-rand so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this paper we give an efficient algorithm (in the block length n=2m) for decoding random errors in RM codes far beyond the minimum distance. Specifically, for low-rate codes (of degree r=o(√m)), we can correct a random set of (1/2-o(1))n errors with high probability. For high rate codes (of degree m-r for r=o(√m/log m)), we can correct roughly mr/2errors. More generally, for any integer r, our algorithm can correct any error pattern in RM(m-(2r+2),m), for which the same erasure pattern can be corrected in RM(m-(r+1),m). The results above are obtained by applying recent results of Abbe, Shpilka, and Wigderson (STOC, 2015) and Kudekar et al. (STOC, 2016) regarding the ability of RM codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding RM codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the error-locating pair method of Pellikaan, Duursma, and Kötter that generalizes the Berlekamp-Welch algorithm for decoding Reed-Solomon 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