Method and system for generating parallel decodable low density parity check (LDPC) codes
An approach is provided for efficiently decoding low density parity check (LDPC) codes. An LDPC decoder includes a memory for storing a mapped matrix that satisfies a plurality of parallel decodable conditions for permitting a lumped memory structure. Additionally, the decoder includes a parallel processors accessing edge values from the stored mapped matrix decode the LDPC codes. The above approach has particular applicability to satellite broadcast systems.
1. A method for supporting decoding of low density parity check (LDPC) codes, the method comprising:
constructing a mapped matrix based on a parity check matrix associated with the LDPC codes, wherein the mapped matrix satisfies a plurality of parallel decodable conditions for permitting a lumped memory structure that is accessible by a plurality of processors operating in parallel; and
storing the mapped matrix in memory for decoding the LDPC codes by the processors.
2. A method according to claim 1 , wherein the parallel decodable conditions include:
determining that none of any two different entries in an identical row of the mapped matrix connects to identical bit nodes or identical check nodes;
if bit node group, BG i , represents all bit nodes connected to edges in an ith row, for i≠j, BG i and BG j , verifying that BG i either has no common node or is identical; and
if check node group, CG i , represents all the check nodes connected to edges in an ith row, for i≠j, CG i and CG i , verifying that CG i either has no common node or is identical.
3. A method according to claim 1 , wherein the parity check matrix is permutation equivalent to a block matrix having entries of n×n density balanced matrices.
4. A method according to claim 3 , wherein one of the entries of the n×n density balanced matrices is a m×m density balanced matrix, and other entries of the n×n density balanced matrices are decomposable into block density balanced submatrices.
5. A method according to claim 4 , wherein m is an integer fraction of n.
6. A method according to claim 1 , wherein the LDPC codes are represented by a signal modulated according to a signal constellation that includes one of 8-PSK (Phase Shift Keying), 16-QAM (Quadrature Amplitude Modulation), 16-APSK (Amplitude Phase Shift Keying), 32-APSK and QPSK (Quadrature Phase Shift Keying).
7. A method according to claim 6 , wherein the signal is transmitted over a satellite link according to a digital video broadcast.
8. A decoding apparatus for decoding of low density parity check (LDPC) codes, the apparatus comprising:
a memory configured to store a mapped matrix that satisfies a plurality of parallel decodable conditions for permitting a lumped memory structure; and
a plurality of processors operating in parallel, the processors accessing the memory to decode the LDPC codes.
9. An apparatus according to claim 8 , wherein the parallel decodable conditions include:
determining that none of any two different entries in an identical row of the mapped matrix connects to identical bit nodes or identical check nodes;
if bit node group, BG i , represents all bit nodes connected to edges in an ith row, for i≠j, BG i and BG j , verifying that BG i either has no common node or is identical; and
if check node group, CG i , represents all the check nodes connected to edges in an ith row, for i≠j, CG i and CG i , verifying that CG i either has no common node or is identical.
10. An apparatus according to claim 8 , wherein the number of processors is n, the memory storing a derived mapped matrix that is constructed based on the mapped matrix by deleting edge values within the mapped matrix, wherein the new mapped matrix is used by m parallel processors, m being less than n.
11. An apparatus according to claim 10 , wherein m is an integer fraction of n.
12. An apparatus according to claim 10 , wherein the parity check matrix is permutation equivalent to a block matrix having entries of n×n density balanced matrices.
13. An apparatus according to claim 12 , wherein one of the entries of the n×n density balanced matrices is a m×m density balanced matrix, and other entries of the n×n density balanced matrices are decomposable into block density balanced submatrices.
14. An apparatus according to claim 8 , wherein the LDPC codes are represented by a signal modulated according to a signal constellation that includes one of 8-PSK (Phase Shift Keying), 16-QAM (Quadrature Amplitude Modulation), 16-APSK (Amplitude Phase Shift Keying), 32-APSK and QPSK (Quadrature Phase Shift Keying).
15. An apparatus according to claim 14 , wherein the signal is transmitted over a satellite link according to a digital video broadcast.
16. A method for supporting decoding of low density parity check (LDPC) codes, the method comprising:
storing a mapped matrix based on a parity check matrix corresponding to the LDPC codes;
determining that none of any two different entries in an identical row of the mapped matrix connects to identical bit nodes or identical check nodes;
if bit node group, BG i , represents all bit nodes connected to edges in an ith row, for i≠j, BG i and BG j , verifying that BG i either has no common node or is identical;
if check node group, CG i , represents all the check nodes connected to edges in an ith row, for i≠j, CG i and CG i , verifying that CG i either has no common node or is identical; and
outputting the mapped matrix for storage into memory that is accessible by a plurality of processors operating in parallel to decode the LDPC codes according to the stored mapped matrix.
17. A method according to claim 16 , wherein the number of processors is n, the method further comprising:
deleting edge values within the mapped matrix to output a derived mapped matrix, wherein the derived mapped matrix is used by m parallel processors, m being less than n.