Patent ID: 7139959

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 parity check matrix, in which the rows of the parity check matrix are grouped into subsets in which each column has a maximum column weight of one, 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 parity check matrix; and for each subset, repeating a sequence of steps comprising: for each row of the subset, subtracting a previous check node value from a probability value for each input node contributing to the parity check sum for that row; generating a new check node value for that row of the subset, using the result of the subtracting step; and for each input node contributing to the parity check sum for that row, updating a probability value using the new check node value and the result of the subtracting step.