Patent ID: 7178080

Claim:
A method of decoding a data stream encoded according to a low density parity check (LDPC) code; wherein the LDPC code is represented by a macro matrix having zero-valued and non-zero-valued entries arranged in block rows and block columns and in which each zero-valued entry corresponds to a p×p zero-valued matrix and each non-zero-valued entry corresponds to a p×p permutation matrix that has at most a single “1” entry in each row and each column and “0” entries elsewhere to define a parity check matrix, wherein the block columns of the macro matrix are grouped so that at most one column has a “1” entry in any row, and wherein the columns of the parity check matrix correspond to input nodes and the rows of the parity check matrix correspond to parity check sums; the method comprising the steps of: receiving a set of input values corresponding to input nodes of the macro parity check matrix; for each of the input nodes, over each of a plurality of parity check sums of the LDPC code, estimating a check node value using values of other input nodes contributing to the parity check sum; for each of the input nodes, estimating a probability value using the estimates of the check node values for that input node; and repeating the estimating steps until reaching a termination criterion.