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 Information Theory Workshop (ITW)

Complexity-Adaptive Maximum-Likelihood Decoding of Modified GN-Coset Codes

Peihong Yuan, Mustafa Cemil Coşkun

Published Oct 17, 2021• 8 citations
Publisher

Abstract

A complexity-adaptive tree search algorithm is proposed for $G_{N}$-coset codes that implements maximum-likelihood (ML) decoding by using a successive decoding schedule. The average complexity is close to that of the successive cancellation (SC) decoding for practical error rates when applied to polar codes and short Reed-Muller (RM) codes, e.g., block lengths up to N = 128. By modifying the algorithm to limit the worstcase complexity, one obtains a near-ML decoder for longer RM codes and their subcodes. Unlike other bit-flip decoders, no outer code is needed to terminate decoding. The algorithm can thus be applied to modified $G_{N}$-coset code constructions with dynamic frozen bits. One advantage over sequential decoders is that there is no need to optimize a separate parameter.

DOI
10.1109/itw48936.2021.9611445

Related papers

Complexity-Adaptive Maximum-Likelihood Decoding of Modified $\boldsymbol{G}_N$-Coset Codes

Peihong Yuan, Mustafa Cemil Coşkun

A complexity-adaptive tree search algorithm is proposed for $\boldsymbol{G}_N$-coset codes that implements maximum-likelihood (ML) decoding by using a successive decoding schedule. The average complexity is close to that of the successive cancellation (SC) decoding for practical error rates when applied to polar codes and short Reed-Muller (RM) codes, e.g., block lengths up to $N=128$. By modifying the algorithm to limit the worst-case complexity, one obtains a near-ML decoder for longer RM codes and their subcodes. Unlike other bit-flip decoders, no outer code is needed to terminate decoding. The algorithm can thus be applied to modified $\boldsymbol{G}_N$-coset code constructions with dynamic frozen bits. One advantage over sequential decoders is that there is no need to optimize a separate parameter.

arXiv:2105.04048•May 9, 2021•0 citations

Successive Cancellation Ordered Search Decoding of Modified $\boldsymbol{G}_N$-Coset Codes

Peihong Yuan, Mustafa Cemil Coşkun

A tree search algorithm called successive cancellation ordered search (SCOS) is proposed for $\boldsymbol{G}_N$-coset codes that implements maximum-likelihood (ML) decoding with adaptive complexity for transmission over binary-input AWGN channels. Unlike bit-flip decoders, no outer code is needed to terminate decoding; therefore, SCOS also applies to $\boldsymbol{G}_N$-coset codes modified with dynamic frozen bits. The average complexity is close to that of successive cancellation (SC) decoding at practical frame error rates (FERs) for codes with wide ranges of rate and lengths up to $512$ bits, which perform within $0.25$ dB or less from the random coding union bound and outperform Reed--Muller codes under ML decoding by up to $0.5$ dB. Simulations illustrate simultaneous gains for SCOS over SC-Fano, SC stack (SCS) and SC list (SCL) decoding in FER and the average complexity at various SNR regimes. SCOS is further extended by forcing it to look for candidates satisfying a threshold, thereby outperforming basic SCOS under complexity constraints. The modified SCOS enables strong error-detection capability without the need for an outer code. In particular, the $(128, 64)$ polarization-adjusted convolutional code under modified SCOS provides gains in overall and undetected FER compared to CRC-aided polar codes under SCL/dynamic SC flip decoding at high SNR.

arXiv:2112.10735•Dec 20, 2021•0 citations

A Tree Search Approach for Maximum-Likelihood Decoding of Reed-Muller Codes

Seyyed Ali Hashemi, Nghia Doan, Warren J. Gross +2 more

A low-complexity tree search approach is presented that is equivalent to the maximum-likelihood (ML) decoding of Reed-Muller (RM) codes. The proposed approach generates a bit-flipping tree that is traversed to find the ML decoding result by performing successive-cancellation decoding after each node visit. A depth-first search (DFS) and a breadth-first search (BFS) scheme are developed and a log-likelihood-ratio-based bit-flipping metric is utilized to avoid redundant node visits in the tree. Several enhancements to the proposed algorithm are presented to further reduce the number of node visits. Simulation results confirm that the BFS scheme provides a lower average number of node visits than the existing tree search approach to decode RM codes.

arXiv:2107.08991•IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2021•8 citations

Soft-Decision Adaptive Recursive Maximum Likelihood Decoding Algorithm for Non-binary Codes

Yingtao Zhou, Yuichi Kaji

Maximum likelihood (ML) decoding is the optimal error-correction method but is NP-hard in general, implying that there would be no polynomial-time ML decoding algorithm that capable of decoding arbitrary linear codes. Consequently, researchers have developed a variety of ML decoding algorithms with different characteristics so that they can be used in a complementary manner. Although many modern codes such as Turbo, LDPC, and Polar codes, can be efficiently decoded without ML algorithms, there remains continual demand for developing new ML decoding algorithms and evaluating ML decoding performance in various contexts. In this study, we propose an ML decoding algorithm applicable to general non-binary linear codes, formulated as a generalization of the adaptive and recursive ML decoding algorithm previously developed for binary codes. The proposed algorithm is implemented and applied to Generalized Reed-Muller codes, and its computational complexity of soft-decision ML decoding is discussed and compared with the complexity of the Viterbi decoder, in terms of the number of addition-equivalent operations, to demonstrate the efficiency of the approach. The substantial reduction in decoding complexity enables us performing practical decoding simulation of some classes of Generalized Reed-Muller codes. This paper also shows numerical evaluation results of the error-correcting capabilities of the codes, providing insights into their performance under optimal decoding conditions.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2026•0 citations

Reducing Search Complexity of Dynamic SC-Flip Decoding for Polar Codes

Xinyuan Qiao, Hangxuan Cui, Jun Ting Lin +1 more

Polar codes are the first error-correcting codes that achieve the Shannon limit under successive cancellation (SC) decoding when the code length is infinite. However, the error-correcting performance of SC decoding is mediocre for short and moderate code lengths. Dynamic successive cancellation flip (DSCF) decoding has been proposed that performs extra SC decoding trails with multi-bit flipping to improve the performance of short and moderate polar codes. The DSCF decoding suffers from high computational complexity and decoding latency since all information bits are tested when searching for the flipping candidates, which leads to intensive metric calculations. To reduce the search complexity of the DSCF, a method based on the critical set (CS) is proposed in this paper to narrow the search range and two types of special nodes, rate-0 nodes and repetition nodes, are incorporated for further complexity reduction. Simulation results show that the proposed method can achieve more than 70% reduction in calculations on metrics, and up to 22.79% reduction in calculations on nodes without performance loss compared to the original DSCF decoding.

IEEE International Conference on Computer and Communications (ICCC)•Dec 10, 2021•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
A complexity-adaptive tree search algorithm is proposed for GNG_{N}GN​-coset codes that implements maximum-likelihood (ML) decoding by using a successive decoding schedule. The average complexity is close to that of the successive cancellation (SC) decoding for practical error rates when applied to polar codes and short Reed-Muller (RM) codes, e.g., block lengths up to N = 128. By modifying the algorithm to limit the worstcase complexity, one obtains a near-ML decoder for longer RM codes and their subcodes. Unlike other bit-flip decoders, no outer code is needed to terminate decoding. The algorithm can thus be applied to modified GNG_{N}GN​-coset code constructions with dynamic frozen bits. One advantage over sequential decoders is that there is no need to optimize a separate parameter.
Complexity-Adaptive Maximum-Likelihood Decoding of Modified GN\boldsymbol{G}_NGN​-Coset Codes
A complexity-adaptive tree search algorithm is proposed for GN\boldsymbol{G}_NGN​-coset codes that implements maximum-likelihood (ML) decoding by using a successive decoding schedule. The average complexity is close to that of the successive cancellation (SC) decoding for practical error rates when applied to polar codes and short Reed-Muller (RM) codes, e.g., block lengths up to N=128N=128N=128. By modifying the algorithm to limit the worst-case complexity, one obtains a near-ML decoder for longer RM codes and their subcodes. Unlike other bit-flip decoders, no outer code is needed to terminate decoding. The algorithm can thus be applied to modified GN\boldsymbol{G}_NGN​-coset code constructions with dynamic frozen bits. One advantage over sequential decoders is that there is no need to optimize a separate parameter.
Successive Cancellation Ordered Search Decoding of Modified GN\boldsymbol{G}_NGN​-Coset Codes
A tree search algorithm called successive cancellation ordered search (SCOS) is proposed for GN\boldsymbol{G}_NGN​-coset codes that implements maximum-likelihood (ML) decoding with adaptive complexity for transmission over binary-input AWGN channels. Unlike bit-flip decoders, no outer code is needed to terminate decoding; therefore, SCOS also applies to GN\boldsymbol{G}_NGN​-coset codes modified with dynamic frozen bits. The average complexity is close to that of successive cancellation (SC) decoding at practical frame error rates (FERs) for codes with wide ranges of rate and lengths up to 512512512 bits, which perform within 0.250.250.25 dB or less from the random coding union bound and outperform Reed--Muller codes under ML decoding by up to 0.50.50.5 dB. Simulations illustrate simultaneous gains for SCOS over SC-Fano, SC stack (SCS) and SC list (SCL) decoding in FER and the average complexity at various SNR regimes. SCOS is further extended by forcing it to look for candidates satisfying a threshold, thereby outperforming basic SCOS under complexity constraints. The modified SCOS enables strong error-detection capability without the need for an outer code. In particular, the (128,64)(128, 64)(128,64) polarization-adjusted convolutional code under modified SCOS provides gains in overall and undetected FER compared to CRC-aided polar codes under SCL/dynamic SC flip decoding at high SNR.
A low-complexity tree search approach is presented that is equivalent to the maximum-likelihood (ML) decoding of Reed-Muller (RM) codes. The proposed approach generates a bit-flipping tree that is traversed to find the ML decoding result by performing successive-cancellation decoding after each node visit. A depth-first search (DFS) and a breadth-first search (BFS) scheme are developed and a log-likelihood-ratio-based bit-flipping metric is utilized to avoid redundant node visits in the tree. Several enhancements to the proposed algorithm are presented to further reduce the number of node visits. Simulation results confirm that the BFS scheme provides a lower average number of node visits than the existing tree search approach to decode RM codes.
Maximum likelihood (ML) decoding is the optimal error-correction method but is NP-hard in general, implying that there would be no polynomial-time ML decoding algorithm that capable of decoding arbitrary linear codes. Consequently, researchers have developed a variety of ML decoding algorithms with different characteristics so that they can be used in a complementary manner. Although many modern codes such as Turbo, LDPC, and Polar codes, can be efficiently decoded without ML algorithms, there remains continual demand for developing new ML decoding algorithms and evaluating ML decoding performance in various contexts. In this study, we propose an ML decoding algorithm applicable to general non-binary linear codes, formulated as a generalization of the adaptive and recursive ML decoding algorithm previously developed for binary codes. The proposed algorithm is implemented and applied to Generalized Reed-Muller codes, and its computational complexity of soft-decision ML decoding is discussed and compared with the complexity of the Viterbi decoder, in terms of the number of addition-equivalent operations, to demonstrate the efficiency of the approach. The substantial reduction in decoding complexity enables us performing practical decoding simulation of some classes of Generalized Reed-Muller codes. This paper also shows numerical evaluation results of the error-correcting capabilities of the codes, providing insights into their performance under optimal decoding conditions.
Polar codes are the first error-correcting codes that achieve the Shannon limit under successive cancellation (SC) decoding when the code length is infinite. However, the error-correcting performance of SC decoding is mediocre for short and moderate code lengths. Dynamic successive cancellation flip (DSCF) decoding has been proposed that performs extra SC decoding trails with multi-bit flipping to improve the performance of short and moderate polar codes. The DSCF decoding suffers from high computational complexity and decoding latency since all information bits are tested when searching for the flipping candidates, which leads to intensive metric calculations. To reduce the search complexity of the DSCF, a method based on the critical set (CS) is proposed in this paper to narrow the search range and two types of special nodes, rate-0 nodes and repetition nodes, are incorporated for further complexity reduction. Simulation results show that the proposed method can achieve more than 70% reduction in calculations on metrics, and up to 22.79% reduction in calculations on nodes without performance loss compared to the original DSCF 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.