US2015039960A1PendingUtilityA1
Encoding and decoding techniques using low-density parity check codes
Est. expiryApr 8, 2031(~4.7 yrs left)· nominal 20-yr term from priority
H03M 13/118G06F 11/10H03M 13/11H03M 13/1182H03M 13/616H04L 1/0045H03M 13/1162H03M 13/1165H03M 13/1151H03M 13/1174H04L 1/0057H03M 13/611
41
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
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.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
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
]
.Join the waitlist — get patent alerts
Track US2015039960A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.