Patent ID: 8739005

Claim:
An error correction encoding apparatus, comprising: a linear encoder configured to support a linear coding scheme enabling a parity check to be carried out by a division using a generating polynomial and to apply the generating polynomial to input data to obtain linear coded data; and a low-density parity check (LDPC) encoder configured to apply a generator matrix corresponding to a parity check matrix for an LDPC code to the linear coded data to obtain output data, and wherein the parity check matrix satisfies an expression: R ⁡ ( d ⁡ ( x ) g ⁡ ( x ) ) ≠ 0 , and in this case, d ⁡ ( x ) = ∑ i ∈ S ⁢ \ ⁢ P  S  = J + 1 ⁢ ⁢ c ~ i ⁡ ( x ) ⁢ x qi = ∑ i ∈ S ⁢ \ ⁢ P  S  = J + 1 ⁢ ⁢ perm ⁡ ( H S ⁢ \ ⁢ i ) ⁢ x qi , where g(x): the generating polynomial, d(x): a sequence polynomial expressing a data portion of a low weight LDPC code word, R ⁡ ( d ⁡ ( x ) g ⁡ ( x ) ) ⁢ : a remainder of d ⁡ ( x ) g ⁡ ( x ) , H: the parity check matrix of J rows by K columns, comprising elements corresponding to q−1 th order polynomials, q: a block size used when H is expanded into a binary form, S: a set of column indices optionally extracted from H, |S|: a size of S, P: a set of column indices corresponding to a parity portion of H, H S : a sub-matrix comprising column vectors of H which are contained in S, S\i: a set of column indices in S other than a column index=i, {tilde over (c)} i (x): a polynomial expressing an element of the low weight code word which corresponds to the column index=i, and perm( ): a function meaning a calculation of a determinant on a binary polynomial ring.