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 Access

Decoding Algorithms for Binary U-UV Codes: A Unified Survey of Performance and Complexity

Feodosii Kotov, Fedor I. Ivanov

Published Jan 1, 2026• 0 citations
Publisher

Abstract

U-UV codes, based on the Plotkin (U, U + V) construction, provide a unified framework that includes polar and Reed–Muller codes and enables flexible design through the choice of component codes. While modern capacity-approaching codes achieve excellent performance at large block lengths, their efficiency at short and moderate lengths remains limited, especially under low-latency constraints. Due to their recursive structure, U-UV codes offer improved performance at short and moderate block lengths, while maintaining low decoding latency. Despite this potential, a unified comparison of decoding methods has been lacking. This paper provides a comprehensive survey of decoding methods for binary U-UV codes based on the Plotkin $(U, U+V)$ construction. We review the principles of the U-UV construction and summarize the development of decoding algorithms, from classical successive cancellation and multistage decoding to modern list-based approaches. To the best of our knowledge, no comprehensive survey of decoding methods for U-UV codes has been published to date. This paper fills this gap by providing a unified comparison of decoding algorithms in terms of both error-correction performance and computational complexity. The analysis shows that list-based decoding methods significantly outperform classical successive cancellation decoding at moderate code lengths, while hybrid approaches offer favorable complexity-performance trade-offs. These results highlight the importance of decoder selection depending on application constraints.

DOI
10.1109/access.2026.3710842

Related papers

List decoding for concatenated codes based on the Plotkin construction with BCH component codes

Daniel Nicolas Bailon, Jürgen Freudenberger

Reed-Muller codes are a popular code family based on the Plotkin construction. Recently, these codes have regained some interest due to their close relation to polar codes and their low-complexity decoding. We consider a similar code family, i.e., the Plotkin concatenation with binary BCH component codes. This construction is more flexible regarding the attainable code parameters. In this work, we consider a list-based decoding algorithm for the Plotkin concatenation with BCH component codes. The proposed list decoding leads to a significant coding gain with only a small increase in computational complexity. Simulation results demonstrate that the Plotkin concatenation with the proposed decoding achieves near maximum likelihood decoding performance. This coding scheme can outperform polar codes for moderate code lengths.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 30, 2021•0 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

Partial Superposition Reed-Muller Codes

Weiye Ren, Wenyi Zhang

Reed-Muller (RM) codes can be constructed by Plotkin ($u, u \oplus v$) construction. When recursively decoding RM codes based on Plotkin construction, the superposition of component codes u on v acts as interference to the decoding of v, and it has hence been pointed out in the literature that the decoding error is dominated by v. Therefore, in this study we propose a variant of RM codes, leveraging the idea of partial superposition in Plotkin construction. Specifically, only a subset of the bits in u is superposed on v. We call the resulting codes Partial Superposition RM (PS-RM) codes. A superposition pattern design based on row weights of generator matrix is provided. Regarding decoding, we modify Dumer’s recursive list decoding algorithm and Constituent Automorphism Decoding (CAD) algorithm, to render them applicable to PS-RM codes. Simulation results show that the idea of partial superposition leads to evident performance improvements over RM codes, particularly for long code lengths and low/medium Signal-toNoise Ratios (SNRs). We remark that the performance gains of the proposed PS-RM codes are achieved without increasing complexity.

IEEE/CIC International Conference on Communications in China (ICCC)•Aug 10, 2025•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

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

From Polar to Reed-Muller Codes: a Technique to Improve the Finite-Length Performance

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that "interpolates" between RM and polar codes, call this family ${\mathcal C}_{\rm inter} = \{C_α : α\in [0, 1]\}$, where $C_α \big |_{α= 1}$ is the original polar code, and $C_α \big |_{α= 0}$ is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of $α$. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family ${\mathcal C}_{\rm inter}$ even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

arXiv:1401.3127•Jan 14, 2014•0 citations
U-UV codes, based on the Plotkin (U, U + V) construction, provide a unified framework that includes polar and Reed–Muller codes and enables flexible design through the choice of component codes. While modern capacity-approaching codes achieve excellent performance at large block lengths, their efficiency at short and moderate lengths remains limited, especially under low-latency constraints. Due to their recursive structure, U-UV codes offer improved performance at short and moderate block lengths, while maintaining low decoding latency. Despite this potential, a unified comparison of decoding methods has been lacking. This paper provides a comprehensive survey of decoding methods for binary U-UV codes based on the Plotkin (U,U+V)(U, U+V)(U,U+V) construction. We review the principles of the U-UV construction and summarize the development of decoding algorithms, from classical successive cancellation and multistage decoding to modern list-based approaches. To the best of our knowledge, no comprehensive survey of decoding methods for U-UV codes has been published to date. This paper fills this gap by providing a unified comparison of decoding algorithms in terms of both error-correction performance and computational complexity. The analysis shows that list-based decoding methods significantly outperform classical successive cancellation decoding at moderate code lengths, while hybrid approaches offer favorable complexity-performance trade-offs. These results highlight the importance of decoder selection depending on application constraints.
Reed-Muller codes are a popular code family based on the Plotkin construction. Recently, these codes have regained some interest due to their close relation to polar codes and their low-complexity decoding. We consider a similar code family, i.e., the Plotkin concatenation with binary BCH component codes. This construction is more flexible regarding the attainable code parameters. In this work, we consider a list-based decoding algorithm for the Plotkin concatenation with BCH component codes. The proposed list decoding leads to a significant coding gain with only a small increase in computational complexity. Simulation results demonstrate that the Plotkin concatenation with the proposed decoding achieves near maximum likelihood decoding performance. This coding scheme can outperform polar codes for moderate code lengths.
Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length(≤256)(\leq 256)(≤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 length2m2^{m}2mand orderm−3m-3m−3with reasonable complexity.
Reed-Muller (RM) codes can be constructed by Plotkin (u,u⊕vu, u \oplus vu,u⊕v) construction. When recursively decoding RM codes based on Plotkin construction, the superposition of component codes u on v acts as interference to the decoding of v, and it has hence been pointed out in the literature that the decoding error is dominated by v. Therefore, in this study we propose a variant of RM codes, leveraging the idea of partial superposition in Plotkin construction. Specifically, only a subset of the bits in u is superposed on v. We call the resulting codes Partial Superposition RM (PS-RM) codes. A superposition pattern design based on row weights of generator matrix is provided. Regarding decoding, we modify Dumer’s recursive list decoding algorithm and Constituent Automorphism Decoding (CAD) algorithm, to render them applicable to PS-RM codes. Simulation results show that the idea of partial superposition leads to evident performance improvements over RM codes, particularly for long code lengths and low/medium Signal-toNoise Ratios (SNRs). We remark that the performance gains of the proposed PS-RM codes are achieved without increasing complexity.
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.
We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that "interpolates" between RM and polar codes, call this family Cinter={Cα:α∈[0,1]}{\mathcal C}_{\rm inter} = \{C_α : α\in [0, 1]\}Cinter​={Cα​:α∈[0,1]}, where Cα∣α=1C_α \big |_{α= 1}Cα​​α=1​ is the original polar code, and Cα∣α=0C_α \big |_{α= 0}Cα​​α=0​ is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of ααα. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cinter{\mathcal C}_{\rm inter}Cinter​ even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.