ENCODING AND DECODING TECHNIQUES USING LOW-DENSITY PARITY CHECK CODES
Some embodiments include apparatus and methods for encoding message information. Such apparatus and methods can include using a parity check matrix of a low-density parity check (LDPC) code to generate a first matrix having an upper triangular sub-matrix. Parity information to encode the message information can be generated based on the first matrix if a total number of rows of the upper triangular sub-matrix is equal to the rank of the parity check matrix. If the total number of rows of the upper triangular sub-matrix is less than the rank of the parity check matrix, then a triangularization operation can be performed on a second sub-matrix of the first matrix to generate a second matrix. Parity information to encode the message information can be generated based on the second matrix. Other embodiments including additional apparatus and methods are described.
1 . An apparatus comprising:
an input to receive message information;
an encoder to generate codewords having the message information and parity information, and to generate the parity information based on an equation calculated from a combination of at least an inverse of a triangular sub-matrix generated from a first portion of a parity check matrix of a low-density parity check code and a sub-matrix generated from a second portion of the parity check matrix; and
an output to provide the codewords.
2 . The apparatus of claim 1 , wherein the equation includes p=T −1 (Bu), wherein p denotes the parity information, T −1 denotes the inverse of the triangular sub-matrix, B denotes the sub-matrix generated from the second portion of the parity check matrix, and u denotes the message information.
3 . The apparatus of claim 1 , wherein the encoder is configured to store entries of the inverse of the triangular sub-matrix.
4 . The apparatus of claim 1 , wherein the encoder is included in a memory device coupled to receive the codewords, the memory device including memory cells to store the codewords.
5 . The apparatus of claim 4 , wherein the memory device is configured to output the codewords in a read operation of the memory device.
6 . The apparatus of claim 5 , wherein the input and the output comprise a bi-directional interface of the memory device.
7 . The apparatus of claim 1 , wherein the apparatus is configured to store a record linking a position number of at least one column of the triangular sub-matrix with a position number of at least one column of the parity check matrix.
8 . An apparatus comprising:
an input to receive message information; and
a module to generate codewords having the message information and parity information, the module configured to generate a portion of the parity information based on a first equation calculated from at least an inverse of a first sub-matrix in a first portion of a matrix, the first sub-matrix including a diagonal entry having a value of one, the module also configured to generate an additional portion of the parity information based on a second equation calculated from at least a triangular sub-matrix in a second portion of the matrix; and
an output to provide the codewords.
9 . The apparatus of claim 8 , wherein the first equation includes p 2 =(C m2 −1 D m2 )u, the second equation includes p 1 =T −1 (A m2 p 2 +B m2 u), wherein p 1 and P 2 denote the portions of the parity information, C m2 denotes the first sub-matrix in the first portion of a matrix, T −1 denotes an inverse of the triangular sub-matrix, and A m2 , B m2 , and D m2 denote other sub-matrices of the matrix, the matrix having a block structure
[
T
A
m
2
B
m
2
0
C
m
2
D
m
2
]
.
10 . The apparatus of claim 8 , wherein the module is configured to store entries of the inverse of the triangular sub-matrix, and entries of the inverse of the first sub-matrix in the first portion of a matrix.
11 . The apparatus of claim 8 , wherein the module is configured to store entries of a parity check matrix of a low-density parity check code, and wherein the matrix is generated from the parity check matrix.
12 . The apparatus of claim 11 , wherein the module is configured to store a record linking at least a portion of column numbers of the matrix with at least a portion of column numbers the parity check matrix.
13 . The apparatus of claim 8 , wherein the module comprises a memory device having memory cells to store the codewords.
14 . A method comprising:
receiving message information;
generating parity information based on an equation calculated from at least an inverse of a triangular sub-matrix and a second sub-matrix, the triangular sub-matrix generated from a first portion of a parity check matrix of a low-density parity check code, the second sub-matrix generated from a second portion of the parity check matrix; and
generating a codeword based at least in part on the parity information.
15 . The method of claim 14 , wherein the equation includes p=T −1 (Bu), wherein p denotes the parity information, T −1 denotes the inverse of the triangular sub-matrix, B denotes the second sub-matrix, and u denotes the message information.
16 . The method of claim 14 , further comprising:
accessing a memory to retrieve entries of the inverse of the triangular sub-matrix.
17 . The method of claim 14 , wherein the codewords include a combination of the message information and the parity information.
18 . The method of claim 14 , further comprising:
decoding the codeword to retrieve the message information.
19 . The method of claim 14 , further comprising:
generating an additional portion of the parity information based on a second equation calculated from at least a triangular sub-matrix in a second portion of the matrix.
20 . The method claim 19 , wherein the first equation includes p 2 =(C m2 D m2 )u, the second equation includes p 1 =T −1 (A m2 p 2 +B m2 u), wherein p 1 and p 2 denote the portion and the additional portion of the parity information, C m2 denotes the first sub-matrix, T denotes the triangular sub-matrix, and A m2 , B m2 , and D m2 denote other sub-matrices of the matrix, the matrix having a block structure
[
T
A
m
2
B
m
2
0
C
m
2
D
m
2
]
.