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

International Symposium on Turbo Codes and Iterative Information Processing

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

Daniel Nicolas Bailon, Jürgen Freudenberger

Published Aug 30, 2021• 0 citations
Publisher

Abstract

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.

DOI
10.1109/istc49272.2021.9594194

Related papers

Soft-input decoding of concatenated codes based on the Plotkin construction and BCH component codes

Daniel Nicolas Bailon, Johann-Philipp Thiers, Jürgen Freudenberger

Low latency communication requires soft-input decoding of binary block codes with small to medium block lengths. In this work, we consider generalized multiple concatenated (GMC) codes based on the Plotkin construction. These codes are similar to Reed-Muller (RM) codes. In contrast to RM codes, BCH codes are employed as component codes. This leads to improved code parameters. Moreover, a decoding algorithm is proposed that exploits the recursive structure of the concatenation. This algorithm enables efficient soft-input decoding of binary block codes with small to medium lengths. The proposed codes and their decoding achieve significant performance gains compared with RM codes and recursive GMC decoding.

International Conference on Consumer Electronics•Nov 9, 2020•2 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

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

Feodosii Kotov, Fedor I. Ivanov

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.

IEEE Access•Jan 1, 2026•0 citations

Soft Decision Decoding of Recursive Plotkin Constructions Based on Hidden Code Words

Martin Bossert

The Plotkin construction combines two codes to a code of doubled length. It can be applied recursively. The class of Reed-Muller (RM) codes is a particular example. Exploiting a property of the code words constructed by the recursive Plotkin construction, we present novel soft-decision decoders. These are based on the decoding of hidden code words which are inherent contained in the constructed code words and can be uncovered by adding particular parts of the overall code word. The main idea is to use more than one decoding variant where each variant starts with the decoding of a different hidden code word. Given the decision of this first hidden code word allows error cancellation for the remaining decoding. The final decoding decision selects the best of the decisions of the used variants. The more variants are used the closer the performance gets to the maximum-likelihood (ML) decoding performance. This is verified by an ML-bound for the cases where the ML performance is not known. The decoding algorithms use only additions, comparisons, and sign operations. Further, due to the recursive structure, only relatively short codes have to be decoded, thus, the decoding complexity is very low. We also present a new decoder for first-order RM codes with low complexity. In addition, we introduce two novel classes of half-rate codes based on recursive Plotkin constructions with RM codes. We show that the novel soft decision decoders can also be applied to recursive Plotkin constructions with BCH codes and to particular classes of generalized concatenated codes (GCC).

arXiv:2408.12946•IEEE Transactions on Information Theory•Apr 1, 2025•1 citation

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 projection-aggregation decoding of Reed-Muller codes

Min Ye, Emmanuel A. Abbe

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms based on list-decoding algorithms and code concatenation. We run our main algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) and low code rate (≤ 0.5) regime. Simulation results show that the new algorithm not only outperforms the previous decoding algorithms for RM codes, it also outperforms the optimal decoder for polar codes (SCL+CRC) with the same parameters by a wide margin. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•22 citations
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.
Low latency communication requires soft-input decoding of binary block codes with small to medium block lengths. In this work, we consider generalized multiple concatenated (GMC) codes based on the Plotkin construction. These codes are similar to Reed-Muller (RM) codes. In contrast to RM codes, BCH codes are employed as component codes. This leads to improved code parameters. Moreover, a decoding algorithm is proposed that exploits the recursive structure of the concatenation. This algorithm enables efficient soft-input decoding of binary block codes with small to medium lengths. The proposed codes and their decoding achieve significant performance gains compared with RM codes and recursive GMC decoding.
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.
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.
The Plotkin construction combines two codes to a code of doubled length. It can be applied recursively. The class of Reed-Muller (RM) codes is a particular example. Exploiting a property of the code words constructed by the recursive Plotkin construction, we present novel soft-decision decoders. These are based on the decoding of hidden code words which are inherent contained in the constructed code words and can be uncovered by adding particular parts of the overall code word. The main idea is to use more than one decoding variant where each variant starts with the decoding of a different hidden code word. Given the decision of this first hidden code word allows error cancellation for the remaining decoding. The final decoding decision selects the best of the decisions of the used variants. The more variants are used the closer the performance gets to the maximum-likelihood (ML) decoding performance. This is verified by an ML-bound for the cases where the ML performance is not known. The decoding algorithms use only additions, comparisons, and sign operations. Further, due to the recursive structure, only relatively short codes have to be decoded, thus, the decoding complexity is very low. We also present a new decoder for first-order RM codes with low complexity. In addition, we introduce two novel classes of half-rate codes based on recursive Plotkin constructions with RM codes. We show that the novel soft decision decoders can also be applied to recursive Plotkin constructions with BCH codes and to particular classes of generalized concatenated codes (GCC).
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.
We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms based on list-decoding algorithms and code concatenation. We run our main algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) and low code rate (≤ 0.5) regime. Simulation results show that the new algorithm not only outperforms the previous decoding algorithms for RM codes, it also outperforms the optimal decoder for polar codes (SCL+CRC) with the same parameters by a wide margin. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.