On structure and decoding of product codes

Product codes have been an effective coding method for communication channels where both random and burst error occur. We present a new approach to the structure and maximum likelihood (ML) decoding of product codes using Tanner (1981) graphs. For product codes having a sub-code which is a product of simple parity codes and repetition codes, we show how to obtain a sub-code with an acyclic Tanner graph and the largest possible distance. We show that in all cases of interest, a n-dimensional product code has such a structure. Wagner rule decoding is used on this sub-code and its cosets to obtain an effective and efficient maximum likelihood decoding of the given product code