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

The maximum-likelihood decoding of linear block codes by Wagner rule decoding is discussed. In this approach, the Wagner rule decoding, which has been primarily applied to single parity check codes, is employed on acyclic Tanner graphs. Accordingly, a coset decoding equipped with Wagner rule decoding is applied to the decoding of a code C having a Tanner graph with cycles. A subcode C₁ of C with acyclic Tanner graph is chosen as the base subcode. All cosets of C₁ have the same Tanner graph and are distinguished by their values of parity nodes in the graph. The acyclic Tanner graph of C₁ , together 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-likelihood 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₆, extended Golay codes, Reed-Muller codes, Hamming codes and (32,16,8) quadratic residue code. The generalisation to the decoding of lattices is briefly explained