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

Journal of Complexity

On Viterbi-like algorithms and their application to Reed–Muller codes

Yuansheng Tang, San Ling

Published Mar 20, 2004• 0 citations
Publisher
DOI
10.1016/j.jco.2004.01.003

Related papers

New majority logic decoding algorithm for Reed-Muller codes

Danyo Danev, Daniel Puaca

•Jan 1, 2007•0 citations

The Optimal Sectionalized Trellises for the Generalized Version of Viterbi Algorithm of Linear Block Codes and Its Application to Reed-Muller Codes

Yuansheng Tang, Toru Fujiwara, Tadao Kasami

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Nov 25, 2000•1 citation

Quantum punctured Reed-Muller codes

Robin Sinurat, Khoirul Anwar, Muhammad Reza Kahar Aziz

AIP conference proceedings•Jan 1, 2023•2 citations

On the Number of Errors Which Can Be Corrected by the Reed-Muller Code

R.E. Krichevskii

Soviet physics. Doklady•Sep 1, 1970•3 citations

Recursive error correction for general Reed–Muller codes

Ilya I. Dumer, Kirill Shabunov

Discrete Applied Mathematics•Sep 20, 2005•17 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
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.