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