Acyclic Tanner graphs and maximum-likelihood decoding of linear block codes

The maximum-likelihood decoding of linear block codes by Wagner rule decodi ng is discussed. In this approach, the Wagner rule decoding, which has been primarily applied to single parity check codes, is employed on acyclic Tan ner graphs. Accordingly, a coset decoding equipped with Warmer rule decodin g is applied to the decoding of a code C having a Tanner graph with cycles. A subcode C-1 of C with acyclic Tanner graph is chosen as the base subcode . All cosets of C-1 have the same Tanner graph and are distinguished by the ir values of parity nodes in the graph. The acyclic Tanner graph of C-1, to gether with a trellis representation of the space of the parity sequences, represent the code C. This graphical representation provides a unified and systematic approach to search for an efficient method for the maximum-likel ihood decoding of a given linear block code. It is shown that the proposed method covers the most efficient techniques known for the decoding of some important block codes, including the hexacode H-6, extended Golay codes, Re ed-Muller codes, Hamming codes and (32, 16, 8) quadratic residue code. The generalisation to the decoding of lattices is briefly explained.