Method and apparatus for efficient computation of check equations in periodical low density parity check (LDPC) codes
View Patent ↗A periodic Low Density Parity Check (LPDC) coding apparatus and method allows reference to an LDPC code parity check matrix, where such reference is accomplished row by row. A specially configured memory and cyclical shift operation are used by the apparatus to efficiently compute check equations of the periodic LDPC code.
1. In an encoder for a rate K/N, periodic LDPC code, where N, the number of bits in a codeword, equals the sum of K, the number of information bits, and T, the number of parity bits, the code characterized by a Table, each row of which represents M columns of a Parity Check Matrix for the code, the Parity Check Matrix defining participating bit nodes for each check node in a node representation of the code, where a row in the Table, if successively modulo-T shifted by q, where q equals T/M, generates a corresponding M columns of the Parity Check Matrix, a method of encoding K information bits, comprising the following steps:
providing at least one Inverse Table of reduced form in relation to the Parity Check Matrix and identifying, for each of q check nodes, at least one participating bit node;
for a check node p, using the at least one Inverse Table to identify at least one participating bit node for a check node v, where v=p mod q; and
using the identified at least one participating bit node for the check node v to encode the K information bits, resulting in T parity bits that can be associated with the K information bits to form a codeword.
2. The method of claim 1 wherein the at least one Inverse Table identifies, for each of q check nodes, at least one participating bit node that is identified with an (r, s) pair, where r identifies a group of M bit nodes and s identifies a participating bit node within that group.
3. The method of claim 2 wherein the using step comprises the substeps of:
determining m i , an identifier of at least one participating bit node for the check node p, using the formula:
m i =M·r i +[( s i +u )mod M],
where (r i ,s i ) identifies a participating bit node for the check node u, and u=└p/q┘; and
using the identified at least one participating bit node for the check node p in encoding the K information bits.
4. In a decoder for a rate K/N, periodic LDPC code, where N, the number of bits in a codeword, equals the sum of K, the number of information bits, and T, the number of parity bits, the code characterized by a Table, each row of which represents M columns of a Parity Check Matrix for the code, the Parity Check Matrix defining participating bit nodes for each check node in a node representation of the code, where a row in the Table, if successively modulo-T shifted by q, where q equals T/M, generates a corresponding M columns of the Parity Check Matrix, a method of decoding a received codeword comprising the following steps:
providing at least one Inverse Table of reduced form in relation to the Parity Check Matrix and identifying, for each of q check nodes, at least one participating bit node;
for a check node p, using the at least one Inverse Table to identify at least one participating bit node for a check node v, where v=p mod q; and
using the identified at least one participating bit node for the check node v to decode the received codeword.
5. The method of claim 4 wherein the at least one Inverse Table identifies, for each of q check nodes, at least one participating bit node that is identified with an (r, s) pair, where r identifies a group of M bit nodes and s identifies a participating bit node within that group.
6. The method of claim 5 wherein the using step comprises the substeps of:
determining m i , an identifier of at least one participating bit node for the check node p, using the following formula:
m i =M·r i +[( s i +u )mod M],
where (r i , s i ) identifies a participating bit node for the check node u, and u=└p/q┘; and
using the identified at least one participating bit node for the check node p in decoding the received codeword.