A RECURSIVE MAXIMUM-LIKELIHOOD DECODING ALGORITHM FOR SOME TRANSITIVEINVARIANT BINARY BLOCK-CODES

Recently, a trellis-based recursive maximum likelihood decoding (RMLD) algorithm has been proposed for decoding binary linear block codes[1] . This RMLD algorithm is computationally more efficient than the Viter bi decoding algorithm. However, the computational complexity of the RM LD algorithm depends on the sectionalization of a code trellis. In gen eral, minimization of the computational complexity results in non-unif orm sectionalization of a code trellis. From implementation point of v iew, uniform sectionalization of a code trellis and regularity among t he trellis sections are desirable. In this paper, we apply the RMLD al gorithm to a class of codes which are transitive invariant. This class includes Reed-Muller (RM) codes, the extended and permuted BCH (EBCH) codes and their subcodes. For this class of codes, the binary uniform sectionalization of a code trellis results in the following regular s tructure. At each step of decoding recursion, the metric table constru ction procedure is applied uniformly to all the sections and the size and structure of each metric table are the same. This simplifies the i mplementation of the RMLD algorithm. Furthermore, for all RM codes of lengths 64 and 128 and EBCH codes of lengths 64 and 128 with relativel y low rate, the computational complexity of the RMLD algorithm based o n the binary uniform sectionalization of a code trellis is almost the same as that based on an optimum sectionalization of a code trellis.