The Tanner graph associated with an extended parity-check (EPC) matrix of a cyclic code is shown to be useful in effectively implementing soft decision iterativedecoding pro-cedures based on belief propagation. Decoding with an EPC matrix has the advantage that is universal, in the sense that it does not depend on the specific family of cyclic codes being used. It is shown that there is no need to store the complete EPC matrix, i.e., the structure of the Tanner graph over which iterative decoding is implemented. The length, dimension and parity-check polynomial are all that is needed as input parameters to the decoder. Iterative soft decision decoding can be implemented with a pair of processing elements, to pass messages between nodes in the graph, with edges specified by the parity-check polynomial. By identifying received word positions with high reliability, using a designed threshold, decoding complexity can be reduced drastically while maintaining good error performance.

For more information, visit Sony Computer Science Laboratories’ Web site.