Decoding apparatus, decoding method, and program to decode low density parity check codes

Abstract

The present invention relates to a decoding apparatus and a decoding method for realizing the decoding of LDPC codes, in which, while the circuit scale is suppressed, the operating frequency can be suppressed within a sufficiently feasible range, and control of memory access can be performed easily, and to a program therefor. A check matrix of LDPC codes is formed by a combination of a (P×P) unit matrix, a matrix in which one to several 1s of the unit matrix are substituted with 0, a matrix in which they are cyclically shifted, a matrix, which is the sum of two or more of them, and a (P×P) 0-matrix. A check node calculator 313 simultaneously performs p check node calculations. A variable node calculator 319 simultaneously performs p variable node calculations.

The invention claimed is: 
     
       1. A decoding apparatus for decoding Low Density Parity Check (“LDPC”) codes, the LDPC codes being represented by a check matrix, which is composed of a plurality of sub-matrices, the sub-matrices including a (P×P) unit matrix, a quasi-unit matrix, a shift matrix, a sum matrix, and a (P×P) zero matrix, wherein the quasi-unit matrix is a unit matrix having one or more 1s being substituted with 0, the shift matrix is a unit matrix or a quasi-unit matrix which is cyclically shifted, the sum matrix is the sum of two or more of said unit matrix, said quasi-unit matrix, and said shift matrix, the decoding apparatus comprising:
 first computation means for simultaneously performing P check node computations for decoding said LDPC codes; 
 second computation means for simultaneously performing P variable node computations for decoding said LDPC codes; and 
 message storage means for simultaneously reading and writing message data corresponding to P edges, the message data being obtained as a result of said P check node computations or said P variable node computations; 
 wherein said message storage means stores message data corresponding to the edges, the message data being read during the check node computation in such a manner that the sub-matrices of the check matrix are packed closer in a predetermined direction excluding the zero matrix. 
 
     
     
       2. The decoding apparatus according to  claim 1 , wherein
 said first computation means has P check node calculators for performing check node computations; and 
 said second computation means has P variable node calculators for performing variable node computations. 
 
     
     
       3. The decoding apparatus according to  claim 1 , wherein
 the sub-matrices of the check matrix are packed closer in the row direction. 
 
     
     
       4. The decoding apparatus according to  claim 1 , wherein
 the sub-matrices of the check matrix are packed closer in the column direction. 
 
     
     
       5. The decoding apparatus according to  claim 1 , wherein
 said message storage means stores, at the same address, messages corresponding to P edges belonging to a unit matrix whose weight is 1, a quasi-unit matrix, or a shift matrix, when the sub-matrices, whose weight is 2 or more from among the sub-matrices representing said check matrix, are represented in the form of the sum of the unit matrix whose weight is 1, the quasi-unit matrix, or the shift matrix. 
 
     
     
       6. The decoding apparatus according to  claim 1 , wherein
 said message storage means comprises number-of-rows/p FIFOs and number-of-columns/p FIFOs; and 
 said number-of-rows/p FIFOs and said number-of-columns/p FIFOs each have a number of words corresponding to the weight of the row and the weight of the column of said check matrix, respectively. 
 
     
     
       7. The decoding apparatus according to  claim 1 , wherein
 said message storage means comprises a Random Access Memory (“RAM”); and 
 said RAM stores said message data in the read-out sequence in such a manner as to be packed closer and reads said message data in the storage position sequence. 
 
     
     
       8. The decoding apparatus according to  claim 1 , further comprising:
 received information storage means for storing received information of LDPC codes and for simultaneously reading P pieces of said received information. 
 
     
     
       9. The decoding apparatus according to  claim 8 , wherein
 said received information storage means stores said received information in such a manner that the received information can be read in the sequence necessary for said variable node computation. 
 
     
     
       10. The decoding apparatus according to  claim 1  further comprising:
 rearranging means for rearranging messages obtained as a result of said P check node computations or said P variable node computations. 
 
     
     
       11. The decoding apparatus according to  claim 10 , wherein
 said rearranging means comprises a barrel shifter. 
 
     
     
       12. The decoding apparatus according to  claim 1 , wherein
 said first computation means and said second computation means determine messages corresponding to P edges. 
 
     
     
       13. The decoding apparatus according to  claim 1 , wherein
 said first computation means performs some of said P check node computations and said P variable node computations; and 
 said second computation means performs some of the others of said P variable node computations. 
 
     
     
       14. The decoding apparatus according to  claim 13 , wherein
 said first computation means comprises P calculators for performing some of said P check node computations and said P variable node computations; and 
 said second computation means comprises P calculators for performing some of the others of said P variable node computations. 
 
     
     
       15. The decoding apparatus according to  claim 13 , further comprising:
 first decoding in-progress result storage means for simultaneously reading and writing first decoding in-progress results corresponding to P edges, which are obtained by said first computation means by performing some of said P check node computations and said P variable node computations. 
 
     
     
       16. The decoding apparatus according to  claim 15 , wherein
 said first decoding in-progress result storage means stores said first decoding in-progress results corresponding to the edge, which are read when some of the others of said P variable node computations are performed, in such a manner that 1s of the check matrix are packed closer in the row direction. 
 
     
     
       17. The decoding apparatus according to  claim 15 , wherein
 said first decoding in-progress result storage means are two single-port Random Access Memories (“RAMs”). 
 
     
     
       18. The decoding apparatus according to  claim 17 , wherein
 said two single-port RAMs alternately store said first decoding in-progress results in units of said first decoding in-progress results corresponding to edges of P rows of said check matrix. 
 
     
     
       19. The decoding apparatus according to  claim 17 , wherein
 said two single-port RAMs each read said first decoding in-progress results stored at the same address, where said decoding in-progress results were previously stored. 
 
     
     
       20. The decoding apparatus according to  claim 15 , wherein
 said first decoding in-progress result storage means stores, at the same address, said first decoding in-progress results corresponding to P edges belonging to a unit matrix whose weight is 1, a quasi-unit matrix, or a shift matrix when the sub-matrices, whose weight is 2 or more from among the sub-matrices representing said check matrix, are represented in the form of the sum of the unit matrix whose weight is 1, the quasi-unit matrix, or the shift matrix. 
 
     
     
       21. The decoding apparatus according to  claim 13 , further comprising:
 second decoding in-progress result storage means for simultaneously reading and writing said second decoding in-progress results corresponding to P edges, which are obtained by said second computation means by performing some of the others of said P variable node computations. 
 
     
     
       22. The decoding apparatus according to  claim 13 , further comprising:
 received information storage means for storing received information of LDPC codes and simultaneously reading said P pieces of received information. 
 
     
     
       23. The decoding apparatus according to  claim 22 , wherein
 said received information storage means stores said received information in such a manner that said received information can be read in the sequence necessary for some of the others of said P variable node computations. 
 
     
     
       24. The decoding apparatus according to  claim 13 , further comprising:
 rearranging means for rearranging first decoding in-progress results obtained by said first computation means by performing some of said P check node computations and said P variable node computations, or second decoding in-progress results obtained by said second computation means by performing some of the others of said P variable node computations. 
 
     
     
       25. The decoding apparatus according to  claim 24 , wherein
 said rearranging means comprises a barrel shifter. 
 
     
     
       26. The decoding apparatus according to  claim 1 , wherein
 said first computation means performs some of said P check node computations; and 
 said second computation means performs some of the others of said P check node computations, and said P variable node computations. 
 
     
     
       27. The decoding apparatus according to  claim 26 , wherein
 said first computation means comprises P calculators for performing some of said P check node computations; and 
 said second computation means comprises P calculators for performing some of the others of said P check node computations, and said P variable node computations. 
 
     
     
       28. The decoding apparatus according to  claim 26 , further comprising:
 first decoding in-progress result storage means for simultaneously reading and writing first decoding in-progress results corresponding to P edges, which are obtained by said first computation means by performing some of said P check node computations. 
 
     
     
       29. The decoding apparatus according to  claim 26 , further comprising:
 second decoding in-progress result storage means for simultaneously reading and writing second decoding in-progress results corresponding to P edges, which are obtained by said second computation means by performing some of the others of said P check node computations, and said P variable node computations. 
 
     
     
       30. The decoding apparatus according to  claim 29 , wherein
 said second decoding in-progress result storage means stores said second decoding in-progress results corresponding to edges, which are read when some of the others of said P check node computations; and 
 said P variable node computations are performed, in such a manner that 1s of the check matrix are packed closer in the column direction. 
 
     
     
       31. The decoding apparatus according to  claim 29 , wherein
 said second decoding in-progress result storage means are two single-port Random Access Memories (“RAMs”). 
 
     
     
       32. The decoding apparatus according to  claim 31 , wherein
 said single-port RAMs alternately store said second decoding in-progress results in units of said second decoding in-progress results corresponding to P edges of said check matrix. 
 
     
     
       33. The decoding apparatus according to  claim 31 , wherein
 said two single-port RAMs each read said second decoding in-progress results stored at the same address, where said decoding in-progress results were previously stored. 
 
     
     
       34. The decoding apparatus according to  claim 29 , wherein
 said second decoding in-progress result storage means stores, at the same address, said second decoding in-progress results corresponding to P edges belonging to a unit matrix whose weight is 1, a quasi-unit matrix, or a shift matrix when the sub-matrices whose weight is 2 or more from among the sub-matrices representing said check matrix are represented in the form of the sum of the unit matrix whose weight is 1, the quasi-unit matrix, or the shift matrix. 
 
     
     
       35. The decoding apparatus according to  claim 26 , further comprising:
 received information storage means for storing received information of LDPC codes and for simultaneously reading said P pieces of received information. 
 
     
     
       36. The decoding apparatus according to  claim 35 , wherein
 said received information storage means stores said received information in such a manner that said received information can be read in the sequence necessary for some of the others of said P check node computations, and said P variable node computations. 
 
     
     
       37. The decoding apparatus according to  claim 26 , further comprising:
 rearranging means for rearranging first decoding in-progress results obtained by said first computation means by performing some of said P check node computations, or second decoding in-progress results obtained by said second computation means by performing some of the others of said P check node computations, and said P variable node computations. 
 
     
     
       38. The decoding apparatus according to  claim 37 , wherein
 said rearranging means comprises a barrel shifter. 
 
     
     
       39. A decoding method for use with a decoding apparatus for decoding Low Density Parity Check (“LDPC”) codes, the LDPC codes being represented by a check matrix, which is composed of a plurality of sub-matrices, the sub-matrices including a (P×P) unit matrix, a quasi-unit matrix, a shift matrix, a sum matrix, and a (P×P) zero matrix, wherein the quasi-unit matrix is a unit matrix having one or more 1s being substituted with 0, the shift matrix is a unit matrix or a quasi-unit matrix which is cyclically shifted, the sum matrix is the sum of two or more of said unit matrix, said quasi-unit matrix, and said shift matrix, the decoding method comprising:
 a first computation step of simultaneously performing P check node computations for decoding said LDPC codes; 
 a second computation step of simultaneously performing P variable node computations for decoding said LDPC codes; and 
 a message storage step of simultaneously reading and writing message data corresponding to P edges, the message data being obtained as a result of said P check node computations or said P variable node computations; 
 wherein the message storage step stores message data corresponding to the edges, the message data being read during the check node computation in such a manner that the sub-matrices of the check matrix are packed closer in a predetermined direction excluding the zero matrix. 
 
     
     
       40. A non-transitory computer readable medium having a program for causing a computer to perform a decoding method for use with a decoding apparatus for decoding Low Density Parity Check (“LDPC”) codes, said method comprising:
 a first computation step, performed by the computer, of simultaneously performing P check node computations for decoding said LDPC codes; 
 a second computation step, performed by the computer, of simultaneously performing P variable node computations for decoding said LDPC codes; and 
 a message storage step, performed by the computer, for simultaneously reading and writing message data corresponding to P edges, the message data being obtained as a result of said P check node computations or said P variable node computations; 
 wherein the message storage step stores message data corresponding to the edges, the message data being read during the check node computation in such a manner that the sub-matrices of the check matrix are packed closer in a predetermined direction excluding the zero matrix. 
 
     
     
       41. An apparatus for decoding low density parity check (LDPC) codes, the LDPC codes being represented by a check matrix, which is composed of a plurality of sub-matrices, the sub-matrices including a (P×P) unit matrix, a quasi-unit matrix, a shift matrix, a sum matrix, and a (P×P) zero matrix, wherein the quasi-unit matrix is a unit matrix having one or more 1s being substituted with 0, the shift matrix is a unit matrix or a quasi-unit matrix which is cyclically shifted, the sum matrix is the sum of two or more of the unit matrix, the quasi-unit matrix, and the shift matrix, the apparatus comprising:
 a check node calculation section for simultaneously performing P check node computations for decoding the LDPC codes; 
 a variable node calculation section for simultaneously performing P variable node computations for decoding the LDPC codes; and 
 a message storage unit for storing message data corresponding to P edges of the sub-matrices, the message data being obtained from the P check node computations or from the P variable node computations; 
 wherein the message storage unit reads the message data during the P check node computations in a manner that the sub-matrices of the check matrix are packed closer in a predetermined direction excluding the zero matrix. 
 
     
     
       42. The apparatus of claim 41, wherein the check node calculation section includes a plurality of check node calculators for performing the P check node computations, and the variable node calculation section includes a plurality of variable node calculators for performing the P variable node computations. 
     
     
       43. The apparatus of claim 41, wherein the sub-matrices of the check matrix are packed closer in a row direction. 
     
     
       44. The apparatus of claim 41, wherein the sub-matrices of the check matrix are packed closer in a column direction. 
     
     
       45. The apparatus of claim 41, wherein, when a sub-matrix has a weight of 2 or more, which is formed by summing two or more of the unit matrix, the quasi-unit matrix, and the shift matrix, the storage unit stores the message data corresponding to the P edges of the unit matrix, the quasi-unit matrix, or the shift matrix at the same address. 
     
     
       46. The apparatus of claim 41, wherein the storage unit comprises a random access memory (RAM), wherein the RAM stores the message data in a read-out sequence in such a manner as to be packed closer, and reads the message data in a storage position sequence. 
     
     
       47. The apparatus of claim 41, further comprising a received information storage unit for storing received information of the LDPC codes and for simultaneously reading pieces of the received information. 
     
     
       48. The apparatus of claim 47, wherein the received information storage unit stores the received information in a such manner that the received information is readable in a sequence necessary for the P variable node computations. 
     
     
       49. The apparatus of claim 41, further comprising a rearranging unit for rearranging the message data obtained from the P check node computations or the P variable node computations. 
     
     
       50. The apparatus of claim 49, wherein the rearranging unit comprises a barrel shifter. 
     
     
       51. The apparatus of claim 41, wherein the check node calculation section and the variable node calculation section determine the message data corresponding to the edges. 
     
     
       52. The apparatus of claim 41, wherein the check node calculation section performs the P check node computations and some of the P variable node computations, and the variable node calculation section performs some of the other P variable node computations. 
     
     
       53. The apparatus of claim 52, wherein the check node calculation section comprises a plurality of first calculators for performing the P check node computations and some of the P variable node computations, and the variable node calculation section comprises a plurality of second calculators for performing some of the other P variable node computations. 
     
     
       54. The apparatus of claim 52, further comprising a first decoding in-progress result storage unit for simultaneously reading and writing first decoding in-progress results corresponding to the edges obtained from the check node calculation section by performing the P check node computations and some of the P variable node computations. 
     
     
       55. The apparatus of claim 52, further comprising a second decoding in-progress result storage unit for simultaneously reading and writing second decoding in-progress results corresponding to the edges obtained from the variable node calculation section by performing some of the other P variable node computations. 
     
     
       56. The apparatus of claim 52, further comprising a rearranging unit for rearranging first decoding in-progress results obtained from the check node calculation section by performing the P check node computations and some of the P variable node computations, or rearranging second decoding in-progress results obtained from the variable node calculation section by performing some of the other P variable node computations. 
     
     
       57. The apparatus of claim 41, wherein the check node calculation section performs some of the P check node computations, and the variable node calculation section performs the P variable node computations and some of the other P check node computations. 
     
     
       58. The apparatus of claim 57, wherein the check node calculation section comprises a plurality of first calculators for performing some of the P check node computations, and the variable node calculation section comprises a plurality of second calculators for performing the P variable node computations and some of the other P check node computations. 
     
     
       59. The apparatus of claim 57, further comprising a first decoding in-progress result storage unit for simultaneously reading and writing first decoding in-progress results corresponding to the edges obtained from the check node calculation section by performing some of the P check node computations. 
     
     
       60. The apparatus of claim 57, further comprising a second decoding in-progress result storage unit for simultaneously reading and writing second decoding in-progress results corresponding to the edges obtained from the variable node calculation section by performing the P variable node computations and some of the other P check node computations. 
     
     
       61. The apparatus of claim 57, further comprising a rearranging unit for rearranging first decoding in-progress results obtained from check node calculation section by performing some of the P check node computations, or rearranging second decoding in-progress results obtained from the variable node calculation section by performing the P variable node computations and some of the other P check node computations. 
     
     
       62. A method for decoding low density parity check (LDPC) codes, the LDPC codes being represented by a check matrix, which is composed of a plurality of sub-matrices, the sub-matrices including a (P×P) unit matrix, a quasi-unit matrix, a shift matrix, a sum matrix, and a (P×P) zero matrix, wherein the quasi-unit matrix is a unit matrix having one or more 1s being substituted with 0, the shift matrix is a unit matrix or a quasi-unit matrix which is cyclically shifted, the sum matrix is the sum of two or more of the unit matrix, the quasi-unit matrix, and the shift matrix, the method comprising using a decoding apparatus to perform:
 decoding the LDPC codes by simultaneously performing P check node computations; 
 decoding the LDPC codes by simultaneously performing P variable node computations; 
 storing message data corresponding to P edges of the sub-matrices, the message data being obtained from the P check node computations or from the P variable node computations; and 
 reading the message data during the P check node computations in a manner that the sub-matrices of the check matrix are packed closer in a predetermined direction excluding the zero matrix. 
 
     
     
       63. A non-transitory computer readable medium having a program for causing a computer apparatus to perform a method for decoding low density parity check (LDPC) codes, the LDPC codes being represented by a check matrix, which is composed of a plurality of sub-matrices, the sub-matrices including a (P×P) unit matrix, a quasi-unit matrix, a shift matrix, a sum matrix, and a (P×P) zero matrix, wherein the quasi-unit matrix is a unit matrix having one or more 1s being substituted with 0, the shift matrix is a unit matrix or a quasi-unit matrix which is cyclically shifted, the sum matrix is the sum of two or more of the unit matrix, the quasi-unit matrix, and the shift matrix, the method comprising:
 decoding the LDPC codes by simultaneously performing P check node computations using the computer; 
 decoding the LDPC codes by simultaneously performing P variable node computations using the computer; 
 storing message data corresponding to P edges of the sub-matrices, the message data being obtained from the P check node computations or from the P variable node computations; and 
 reading the message data during the P check node computations in a manner that the sub-matrices of the check matrix are packed closer in a predetermined direction excluding the zero matrix.