Method and apparatus for generating a low-density parity check code
A low density parity check (LDPC) code generating method and apparatus are provided. A parity check matrix with (N−K) rows for check nodes and N columns for variable nodes are formed to encode an information sequence of length K to a codeword of length N. The parity check matrix is divided into an information part matrix with K columns and a parity part matrix with (N−k) columns. The parity part is divided into P×P subblocks. P is a divisor of (N−K). First and second diagonals are defined in the parity part matrix and the second diagonal is a shift of the first diagonal by f subblocks. Shifted identity matrices are placed on the first and second diagonals and zero matrices are filled elsewhere. An odd number of delta matrices each having only one element of 1 are placed in one subblock column of the parity part matrix. The parity check matrix is stored.
1. A method of generating a low density parity check (LDPC) code, comprising the steps of:
(1) forming a parity check matrix having (N−K) rows for check nodes and N columns for variable nodes to encode an information sequence of length K to a codeword of length N;
(2) dividing the parity check matrix into an information part matrix having K columns and a parity part matrix having (N−k) columns;
(3) dividing the parity part matrix into P×P subblocks, P being a divisor of (N−K);
(4) defining a first diagonal and a second diagonal in the parity part matrix, the second diagonal being a shift of the first diagonal by f subblocks;
(5) placing shifted identity matrices with shift indexes in subblocks that lie on the first and second diagonals;
(6) filling zero matrices in the remaining subblocks other than the subblocks of the first and second diagonals;
(7) placing an odd number of delta matrices in one subblock column of the parity part matrix, each delta matrix comprising one element of 1 and the other elements of 0; and
(8) storing the parity check matrix.
2. The method of claim 1 , wherein the step of (4) comprises the step of defining the first diagonal so that the first diagonal starts with a first subblock row and a first subblock column and ends with a last subblock row and a last subblock column.
3. The method of claim 1 , wherein the sum module P of the shift indexes of the shifted identity matrices on the first and second diagonals is prime with P.
4. The method of claim 1 , wherein the step of (7) comprises the step of substituting one zero matrix in the first subblock column of the parity part matrix into a delta matrix.
5. The method of claim 1 , wherein the delta matrices each have one element of 1 in a first column.
6. The method of claim 1 , wherein the step of (8) comprises the step of storing information on the degree of each check node, the degree of each variable node, the positions of non-zero matrices in each row, and the shift indexes of each non-zero matrix, the shift index of a non-zero matrix being a delta matrix being equal to or less than P.
7. The method of claim 1 , wherein the step of (8) comprises the step of storing information about the degree of each check node, the degree of each variable node, the positions of non-zero matrices in each row, and the shift indexes of each non-zero matrix, and the 1-bit subblock information indicating whether the each non-zero matrix is a delta matrix or not.
8. The method of claim 7 , wherein the shift index of a non-zero matrix being a delta matrix indicates the position of an element of 1 in the delta matrix.
9. An apparatus for generating a low density parity check (LDPC) code, comprising:
a memory system for storing program codes used to generate a parity check matrix defining the LDPC code, and storing the parity check matrix; and
a processor for generating the parity check matrix by implementing the program codes,
wherein the processor is adapted to perform the steps of:
(a) forming a parity check matrix having (N−K) rows for check nodes and N columns for variable nodes to encode an information sequence of length K to a codeword of length N;
(b) dividing the parity check matrix into an information part matrix having K columns and a parity part matrix having (N−k) columns;
(c) dividing the parity part matrix into subblocks each being of size P×P where P is a divisor of (N−K);
(d) defining a first diagonal and a second diagonal in the parity part matrix, the second diagonal being a shift of the first diagonal by f subblocks;
(e) placing shifted identity matrices with shift indexes in subblocks that lie on the first and second diagonals;
(f) filling zero matrices in the remaining subblocks other than the subblocks of the first and second diagonals;
(g) placing an odd number of delta matrices in one subblock column of the parity part matrix, each delta matrix comprising one element of 1 and the other elements of 0; and
(h) storing the parity check matrix.
10. The apparatus of claim 9 , wherein the first diagonal starts with a first subblock row and a first subblock column and ends with a last subblock row and a last subblock column.
11. The apparatus of claim 9 , wherein the sum module P of the shift indexes of the shifted identity matrices on the first and second diagonals is prime with P.
12. The apparatus of claim 9 , wherein in the step of (g), the processor substitutes one zero matrix in the first subblock column of the parity part matrix into a delta matrix.
13. The apparatus of claim 9 , wherein the delta matrices each have one element of 1 in a first column.
14. The apparatus of claim 9 , wherein the memory system comprises the parity check matrix using information on the degree of each check node, the degree of each variable node, the positions of non-zero matrices in each row, and the shift indexes of each non-zero matrix, the shift index of a non-zero matrix being a delta matrix being equal to or less than P.
15. The apparatus of claim 9 , wherein the memory system comprises the parity check matrix using information on the degree of each check node, the degree of each variable node, the positions of non-zero matrices in each row, and the shift indexes of each non-zero matrix, and the 1-bit subblock information indicating whether the each non-zero matrix is a delta matrix or not.
16. The apparatus of claim 15 , wherein the shift index of a non-zero matrix being a delta matrix indicates the position of an element of 1 in the delta matrix.
17. A low density parity check (LDPC) coding method comprising the steps of:
receiving an information sequence;
encoding an information sequence of length K to a codeword of length N using an (N, K) parity check matrix having an information part matrix with (N−K) rows and K columns and a parity part matrix with K rows and K columns; and
transmitting the codeword to a receiver,
wherein the parity check matrix is a set of subblocks and comprises a matrix having one element of 1 in at least one of the subblocks and no columns of degree 1 exist in the parity check matrix.