Patent ID: 7278082

Claim:
A method of generating parity data based on a parity check matrix H having p codewords of length c, each codeword being divided into a message word of length m and parity data of length p, the method comprising: reordering a plurality of columns of the parity check matrix H based on elements in each of the columns having values of one to generate a reordered parity check matrix H′; determining a cross-point I between a diagonal line L 2 of a parity matrix part Mp in the parity check matrix H′ and a reordered diagonal line L 1 defined by a first entry of an element having a value of one in each column of the reordered parity check matrix H′; performing column permutations on the reordered parity check matrix H′ on the basis of positions of elements having a value of one in rows above a horizontal line L 3 that passes through the cross-point I to generate a triangular matrix T; calculating values using the triangular matrix T and the message words to obtain a first part of the parity data; and satisfying the equation Hx=0, where x is a codeword matrix, to obtain a remaining second part of the parity data.