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 Information Theory and its Applications

Recursive Algorithm for Maximum Likelihood Decoding of Non-Binary Codes

Yingtao Zhou, Yuichi Kaji

Published Nov 10, 2024• 0 citations
Publisher

Abstract

The maximum likelihood (ML) decoding is essential for error-correcting codes, but the ML decoding problem is NP-hard in general. This suggests that there is no single universal ML decoding algorithm that works efficiently for an arbitrary code. Therefore researchers developed many ML decoding algorithms with different characteristics so that they can be used complementary. This study is intended to propose an ML decoding algorithm that can be used for general non-binary linear codes. The algorithm proposed in this paper is a generalization of the adaptive and recursive ML decoding algorithm that was studied for binary codes. This paper shows that the structure and properties of linear codes that helped realizing the decoding algorithm for binary codes can be generalized to nonbinary cases, and reports the implementation results of the soft-decision ML decoding alogorithm for several non-binary linear codes.

DOI
10.23919/isita60732.2024.10858262

Related papers

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

Applications of linear programming to coding theory

Nathan Axvig

Maximum-likelihood decoding is often the optimal decoding rule one can use, but it is very costly to implement in a general setting. Much effort has therefore been dedicated to find efficient decoding algorithms that either achieve or approximate the error-correcting performance of the maximum-likelihood decoder. This dissertation examines two approaches to this problem. In 2003 Feldman and his collaborators defined the linear programming decoder, which operates by solving a linear programming relaxation of the maximum-likelihood decoding problem. As with many modern decoding algorithms, is possible for the linear programming decoder to output vectors that do not correspond to codewords; such vectors are known as pseudocodewords. In this work, we completely classify the set of linear programming pseudocodewords for the family of cycle codes. For the case of the binary symmetric channel, another approximation of maximum-likelihood decoding was introduced by Omura in 1972. This decoder employs an iterative algorithm whose behavior closely mimics that of the simplex algorithm. We generalize Omura's decoder to operate on any binary-input memoryless channel, thus obtaining a soft-decision decoding algorithm. Further, we prove that the probability of the generalized algorithm returning the maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity.

•Jan 1, 2010•3 citations

A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel

Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.

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

On maximum likelihood soft-decision decoding of binary linear codes

N.J.C. Lous, P.A.H. Bours, Henk C. A. van Tilborg

Two new implementations of a maximum-likelihood soft-decision decoding algorithm for binary linear codes are derived. Instead of checking only error patterns yielding a codeword when added to the rounded-off version of the received vector, these implementations principally consider all possible column patterns. Compared to known implementations, this allows a more efficient use of branching and bounding techniques.>

IEEE Transactions on Information Theory•Jan 1, 1993•28 citations

Towards Practical Near-Maximum-Likelihood Decoding of Error-Correcting Codes: An Overview

Thibaud Tonnellier, Marzieh Hashemipour, Nghia Doan +2 more

While in the past several decades the trend to go towards increasing error-correcting code lengths was predominant to get closer to the Shannon limit, applications that require short block length are developing. Therefore, decoding techniques that can achieve near-maximum-likelihood (near-ML) are gaining momentum. This overview paper surveys recent progress in this emerging field by reviewing the GRAND algorithm, linear programming decoding, machine-learning aided decoding and the recursive projection-aggregation decoding algorithm. For each of the decoding algorithms, both algorithmic and hardware implementations are considered, and future research directions are outlined.

IEEE International Conference on Acoustics Speech and Signal Processing•May 13, 2021•11 citations

Maximum-likelihood Soft-decision Decoding for Binary Linear Block Codes Based on Their Supercodes

Yunghsiang Sam Han, Hung-Ta Pai, Po‐Ning Chen +1 more

Based on the notion of supercodes, we propose a two-phase maximum-likelihood soft-decision decoding (tpMLSD) algorithm for binary linear block codes in this work. The first phase applies the Viterbi algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority-first search algorithm to the trellis corresponding to the linear block code itself, which guarantees finding the ML decision. Simulations on Reed-Muller codes show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the recursive maximum-likelihood decoding (RMLD) [1] when the signal-to-noise ratio per information bit is 4.5 dB.

arXiv:1408.1310•Aug 6, 2014•0 citations
The maximum likelihood (ML) decoding is essential for error-correcting codes, but the ML decoding problem is NP-hard in general. This suggests that there is no single universal ML decoding algorithm that works efficiently for an arbitrary code. Therefore researchers developed many ML decoding algorithms with different characteristics so that they can be used complementary. This study is intended to propose an ML decoding algorithm that can be used for general non-binary linear codes. The algorithm proposed in this paper is a generalization of the adaptive and recursive ML decoding algorithm that was studied for binary codes. This paper shows that the structure and properties of linear codes that helped realizing the decoding algorithm for binary codes can be generalized to nonbinary cases, and reports the implementation results of the soft-decision ML decoding alogorithm for several non-binary linear 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.
Maximum-likelihood decoding is often the optimal decoding rule one can use, but it is very costly to implement in a general setting. Much effort has therefore been dedicated to find efficient decoding algorithms that either achieve or approximate the error-correcting performance of the maximum-likelihood decoder. This dissertation examines two approaches to this problem. In 2003 Feldman and his collaborators defined the linear programming decoder, which operates by solving a linear programming relaxation of the maximum-likelihood decoding problem. As with many modern decoding algorithms, is possible for the linear programming decoder to output vectors that do not correspond to codewords; such vectors are known as pseudocodewords. In this work, we completely classify the set of linear programming pseudocodewords for the family of cycle codes. For the case of the binary symmetric channel, another approximation of maximum-likelihood decoding was introduced by Omura in 1972. This decoder employs an iterative algorithm whose behavior closely mimics that of the simplex algorithm. We generalize Omura's decoder to operate on any binary-input memoryless channel, thus obtaining a soft-decision decoding algorithm. Further, we prove that the probability of the generalized algorithm returning the maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity.
In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.
While in the past several decades the trend to go towards increasing error-correcting code lengths was predominant to get closer to the Shannon limit, applications that require short block length are developing. Therefore, decoding techniques that can achieve near-maximum-likelihood (near-ML) are gaining momentum. This overview paper surveys recent progress in this emerging field by reviewing the GRAND algorithm, linear programming decoding, machine-learning aided decoding and the recursive projection-aggregation decoding algorithm. For each of the decoding algorithms, both algorithmic and hardware implementations are considered, and future research directions are outlined.
Based on the notion of supercodes, we propose a two-phase maximum-likelihood soft-decision decoding (tpMLSD) algorithm for binary linear block codes in this work. The first phase applies the Viterbi algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority-first search algorithm to the trellis corresponding to the linear block code itself, which guarantees finding the ML decision. Simulations on Reed-Muller codes show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the recursive maximum-likelihood decoding (RMLD) [1] when the signal-to-noise ratio per information bit is 4.5 dB.