In recent years, research in, for example, communication fields such as mobile communication and deep space communication, and broadcasting fields such as terrestrial-wave or satellite digital broadcasts has progressed remarkably. Along with this situation, research on coding theories for making error correction coding and decoding efficient has been actively carried out.
As a theoretical limit of code performance, the Shannon limit implied by the so-called Shannon's (C. E. Shannon) channel coding theorem is known. Research on coding theories has been carried out for the purpose of developing codes exhibiting performance near this Shannon limit. In recent years, as a coding method exhibiting performance near the Shannon limit, for example, techniques for what is commonly called “turbo coding”, such as parallel concatenated convolutional codes (PCCC) and serially concatenated convolutional codes (SCCC), have been developed. Furthermore, whereas this turbo coding has been developed, low density parity check codes (hereinafter referred to as “LDPC codes”), which is a coding method that has been known for a long time, have attracted attention.
LDPC codes were proposed first in R. G. Gallager, “Low Density Parity Check Codes”, Cambridge, Mass.: M. I. T. Press, 1963. Thereafter, LDPC codes reattracted attention in D. J. C. MacKay, “Good error correcting codes based on very sparse matrices”, submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999, and M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, “Analysis of low density codes and improved designs using irregular graphs”, in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998.
It is beginning to be known from this recent research that, for the LDPC codes, as the code length increases, performance close to the Shannon limit can be obtained, similarly to turbo coding. Furthermore, since the LDPC codes have the property that the minimum length is proportional to the code length, they have the advantages that the block error probability characteristics are good, and a so-called error floor phenomenon, which is observed in decoding characteristics of turbo coding, hardly occurs.
Such LDPC codes will now be described in detail below. The LDPC codes are linear codes and do not always need to be two-dimensional, but here, a description is given assuming that the LDPC codes are two-dimensional.
The greatest features of the LDPC codes are that the parity check matrix that defines the LDPC codes are sparse. Here, a sparse matrix is formed in such a manner that the number of 1s in the elements of the matrix is very small. If the sparse check matrix is denoted as H, examples thereof include a check matrix in which, as shown in FIG. 1, the Hamming weight of each column (number of is; weight) is “3”, and the Hamming weight of each row is “6”.
As described above, the LDPC codes defined by the check matrix H in which the Hamming weight of each row and each column is fixed are called “regular LDPC codes”. On the other hand, the LDPC codes defined by a check matrix H in which the Hamming weight of each row and each column is not fixed are called “irregular LDPC codes”.
Coding by such LDPC codes is realized by generating a generation matrix G on the basis of the check matrix H and by generating a code word by multiplying this generation matrix G by a two-dimensional information message. More specifically, a coding apparatus for performing coding by LDPC codes computes a generation matrix G in which the equation GHT=0 holds with a transpose matrix HT of the check matrix H. Here, when the generation matrix G is a k×n matrix, the coding apparatus multiplies the generation matrix G by a k-bit information matrix (vector u), and generates an n-bit codeword c (=uG). The codeword generated by this coding apparatus is transmitted with the code bit whose value is “0” being mapped to “+1” and the code bit whose value is “1” being mapped to “1”, and is received at the reception side via a predetermined communication channel.
On the other hand, decoding of the LDPC codes can be performed by a message passing algorithm by belief propagation on a so-called Tanner graph, which is formed of a variable node (also called a message node) and a check node; this message passing algorithm was proposed by Gallager and is known as “probabilistic decoding”. Hereafter, the variable nodes and the check nodes are also referred to simply as nodes where appropriate.
However, in probabilistic decoding, since messages exchanged between nodes are real-number values, in order to find an analytical solution, it is necessary to trace the probability distribution of the message that takes a continuous value. This necessitates analysis involving a large degree of difficulty. Accordingly, Gallager has proposed an algorithm A or an algorithm B as an algorithm for decoding LDPC codes.
In general, decoding of the LDPC codes is performed in accordance with the procedure shown in FIG. 2. Here, the receiving value (the receiving code sequence) is denoted as U0(u0i), the message output from the check node is denoted as uj, and the message output from the variable node is denoted as vi. Here, the message is a real-number value such that the “0”-likeness of the value is represented by a so-called log likelihood ratio.
In the decoding of the LDPC codes, initially, as shown in FIG. 2, in step S11, the receiving value U0(u0i) is received, the message uj is initialized to 0, and a variable k that takes an integer as a counter for an iterative process is initialized to 0. The process then proceeds to step S12. In step S12, based on the received value U0(u0i), a message vi is determined by performing a computation shown in equation (1) (computation of a variable node). Furthermore, based on this message vi, a message uj is determined by performing a computation shown in equation (2) (computation of a check node).
                              v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                          u              j                                                          (        1        )                                          tanh          ⁢                                          ⁢                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                      tanh            ⁢                                                  ⁢                          (                                                v                  i                                2                            )                                                          (        2        )            
Here, dv and dc in equations (1) and (2) are parameters respectively that indicate the number of 1s in the vertical direction (column) and in the horizontal direction (row) of the check matrix H and that can be selected as desired. For example, in the case of a (3, 6) code, dv=3 and dc=6.
In the computation of each of equations (1) and (2), since the message input from an edge (line connecting the variable node and the check node) from which a message is to be output is not used as a parameter for a sum or product computation, the range of the sum or product computation is from 1 to dv−1 or 1 to dc−1. In practice, the computation shown in equation (2) is performed by creating in advance a table of a function R(v1, v2), shown in equation (3), that is defined by one output with respect to two inputs v1 and v2 and by using this table continuously (recursively), as shown in equation (4).x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1,v2)  (3)uj=R(v1,R(v2,R(v3, . . . R(vdc−2,vdc−1))))  (4)
In step S12, furthermore, the variable k is incremented by 1, and the process then proceeds to step S13. In step S13, it is determined whether or not the variable k is greater than a predetermined number N of iterative decodings. When it is determined in step S13 that the variable k is not greater than N, the process returns to step S12, where the identical processing is performed again.
When it is determined in step S13 that the variable k is greater than N, the process proceeds to step S14, where the message vi serving as the decoded result, which is finally output as a result of performing the computation shown in equation (5), is determined and output. This completes the decoding process of the LDPC codes.
                              v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                            d                v                                      ⁢                          u              j                                                          (        5        )            
Here, unlike the computation of equation (1), the computation of equation (5) is performed using the input messages from all the edges connected to the variable nodes.
In such LDPC code decoding, for example, in the case of (3, 6) code, as shown in FIG. 3, messages are exchanged between nodes. In the node (variable node) indicated by “=” in FIG. 3, the computation shown in equation (1) is performed. In the node indicated by “+” (check node), the computation shown in equation (2) is performed. In particular, in the algorithm A, the message is formed to be two-dimensional; in the node indicated by “1+”, an exclusive OR computation of dc−1 input messages is performed; and in the node indicated by “=”, with respect to the received value R, when all the dv−1 input messages are different bit values, the sign is inverted and output.
Furthermore, in recent years, research on an implementation method of the decoding of LDPC codes has been carried out. Before describing the implementation method, the decoding of LDPC codes is described in a schematic form.
FIG. 4 shows an example of a parity check matrix of (3,6) LDPC codes (a coding rate of ½, a code length of 12). The parity check matrix of LDPC codes can be written by using a Tanner graph, as shown in FIG. 5. In FIG. 5, nodes indicated by “+” are check nodes, and nodes indicated by “=” are variable nodes. The check nodes and the variable nodes correspond to the rows and the columns of the parity check matrix, respectively. The connecting line between the check node and the variable node is an edge and corresponds to “1” of the check matrix. That is, when the element of the j-th row and the i-th column of the check matrix is 1, in FIG. 5, the i-th variable node (node of “=”) from the top and the j-th check node (node of “+”) from the top are connected to each other by an edge. The edge indicates that the sign bit corresponding to the variable node has a constraint condition corresponding to the check node. FIG. 5 shows a Tanner graph of the check matrix of FIG. 4.
In the sum product algorithm, which is a method of decoding LDPC codes, the computation of the variable node and the computation of the check node are repeatedly performed.
In the variable node, as shown in FIG. 6, the computation of equation (1) (variable node computation) is performed. That is, in FIG. 6, the message vi corresponding to the edge to be calculated is calculated by using the messages u1 and u2 from the remaining edges connected to the variable node, and the received information u0i. The messages corresponding to the other edges are also calculated similarly.
Next, before describing the check node computation, equation (2) is rewritten as shown in equation (6) by using the equation a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b), where sign(x) is 1 when x≧0 and is −1 when x<0.
                                                                        u                j                            =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                              tanh                        ⁢                                                                                                  ⁢                                                  (                                                                                    v                              i                                                        2                                                    )                                                                                      )                                                                                                                          =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                                              ∑                                                          i                              =                              1                                                                                                                      d                                c                                                            -                              1                                                                                ⁢                                                      ln                            ⁡                                                          (                                                                                                                                tanh                                  ⁡                                                                      (                                                                                                                  v                                        i                                                                            2                                                                        )                                                                                                                                                              )                                                                                                      }                                            ×                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                  sign                          ⁡                                                      (                                                          tanh                              ⁡                                                              (                                                                                                      v                                    i                                                                    2                                                                )                                                                                      )                                                                                                                ]                                                                                                                          =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                  -                                                      (                                                                                          ∑                                                                  i                                  =                                  1                                                                                                                                      d                                    c                                                                    -                                  1                                                                                            ⁢                                                              -                                                                  ln                                  ⁡                                                                      (                                                                          tanh                                      ⁡                                                                              (                                                                                                                                                                                                                        v                                              i                                                                                                                                                                            2                                                                                )                                                                                                              )                                                                                                                                                        )                                                                          }                                                              ]                                                  ×                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                      sign                    ⁡                                          (                                              v                        i                                            )                                                                                                                              (        6        )            
Furthermore, in the case of x≧0, when the definition φ(x)=ln(tanh(x/2)) is made, since φ−1(x)=2 tanh−1(e−x), equation (6) can be written as equation (7).
                              u          j                =                              ϕ                          -              1                                ⁢                                          ⁢                      (                                          ∑                                  i                  =                  1                                                                      d                    c                                    -                  1                                            ⁢                              ϕ                ⁡                                  (                                                                                v                      i                                                                            )                                                      )                    ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                          sign              ⁡                              (                                  v                  i                                )                                                                        (        7        )            
In the check node, as shown in FIG. 7, the computation of equation (7) (check node computation) is performed. That is, in FIG. 7, the message uj corresponding to the edge for which a calculation is to be performed is calculated by using the messages v1, v2, v3, v4, and v5 from the remaining edges connected to the check node. The messages corresponding to the other edges are also calculated similarly.
The function φ(x) can also be expressed as φ(x)=ln((ex+1)/(ex−1)), and when x>0, φ(x)=φ−1(x). When the functions φ(x) and φ−1(x) are implemented as hardware, there are cases in which they are implemented using an LUT (Look-Up Table), and both of them are the same LUT.
When the sum product algorithm is implemented as hardware, it is necessary to repeatedly perform the variable node computation expressed by equation (1) and the check node computation expressed by equation (7) with an appropriate circuit scale and at an appropriate operating frequency.
As an example of the implementation of the decoding apparatus, a description is given first of an implementation method in a case where decoding is performed by simply performing the computation of each node one-by-one in sequence (full serial decoding).
It is assumed here that, for example, codes (a coding rate of ⅔, and a code length of 90) represented by a 30 (rows)×90 (columns) check matrix of FIG. 8 are decoded. The number of 1s of the check matrix of FIG. 8 is 269; therefore, in the Tanner graph, the number of edges becomes 269. Here, in the check matrix of FIG. 8 (the same applies to FIGS. 15 to 17 (to be described later)), 0 is represented by “.”.
FIG. 9 shows an example of the configuration of a decoding apparatus for decoding LDPC codes once.
In the decoding apparatus of FIG. 9, a message corresponding to one edge is calculated for each clock at which it operates.
More specifically, the decoding apparatus of FIG. 9 includes one memory 104 for reception, two memories 100 and 102 for edges, one check node calculator 101, and one variable node calculator 103.
In the decoding apparatus of FIG. 9, message data is read one-by-one from the memory 100 or 102 for edges, and by using the message data, the message data corresponding to the desired edge is calculated. Then, the message data determined by that calculation is stored one-by-one in the memory 100 or 102 for edges at a subsequent stage. When iterative decoding is to be performed, the iterative decoding is realized by serially concatenating a plurality of the decoding apparatuses of FIG. 9 for decoding LDPC codes once or by repeatedly using the decoding apparatus of FIG. 9. Here, it is assumed that, for example, a plurality of the decoding apparatuses of FIG. 9 are connected.
The memory 100 for edges stores output messages D100 supplied from the variable node calculator 103 of the decoding apparatus (not shown) at a previous stage in the order in which the check node calculator 101 at a subsequent stage reads them. Then, at the phase of the check node calculation, the memory 100 for edges supplies, to the check node calculator 101, the messages D100 as a message output D101 in the order in which they are stored. By using the message D101 supplied from the memory 100 for edges, the check node calculator 101 performs a computation in accordance with equation (7) and supplies a message D102 determined by that computation to the memory 102 for edges at a subsequent stage.
FIG. 10 shows an example of the configuration of the check node calculator 101 of FIG. 9 for performing check node calculations one-by-one.
In the check node calculator 101 of FIG. 10, messages vi from the variable node corresponding to each column of the check matrix, which are supplied from the memory 100 for edges, are read one-by-one, and the computation of φ(|vi|) in equation (7) is performed using an LUT. Furthermore, φ(|vi|) determined from the message vi from the variable node corresponding to each column over one row of the check matrix is integrated. As a result, the integrated value of φ(|vi|) determined from the messages vi from all the edges is determined. Thereafter, φ(|vi|) which was determined from the edge for which the message uj was desired to be determined and which was delayed at the FIFO (FIFO memory) is subtracted from the integrated value. As a result, for the edge for which the message uj is desired to be determined, Σφ(|vi|) in equation (7) is determined. That is, by subtracting the message from the edge for which the message uj is desired to be determined from the sum of the messages from all the edges to the check node, the message to the edge for which the message uj is desired to be determined is determined. Furthermore, based on the LUT, the computation of φ−1(Σφ(|vi|)) in equation (7) is performed. At the same time, the sign bit of the message uj, that is, Πsign(vi) in equation (7), is also calculated similarly by using an EXOR circuit. In the manner described above, the computation of equation (7) is performed, and the message uj is determined.
In FIG. 10, the check node calculator 101 is shown by assuming that each message, together with the sign bit, is quantized into a total of 6 bits. Since the maximum row weight of the check matrix to be processed here in FIG. 8 is 9, that is, since the maximum number of messages supplied to the check node is 9, the check node calculator 101 has FIFOs (First In First Out) for delaying nine messages (φ(|vi|)).
Referring back to FIG. 9, the memory 10 for edges stores the messages D102 supplied from the check node calculator 101 at a previous stage in the order in which the variable node calculator 103 at a subsequent stage reads them. Then, at the phase of the variable node calculation, the memory 10 for edges supplies the message output D102 as a message output D103 to the variable node calculator 103 in the order in which they are stored.
The variable node calculator 103 performs a computation in accordance with equation (1) by using the message output D103 supplied from the memory 10 for edges and received data (received value of the LDPC code) D104 supplied from the memory 104 for reception, and supplies a message D105 obtained as a result of the computation to the memory 100 for edges of the decoding apparatus (not shown) at a subsequent stage.
FIG. 11 shows an example of the configuration of the variable node calculator 103 of FIG. 9 for performing variable node calculations one-by-one.
In the variable node calculator 103 of FIG. 11, messages uj from the check node corresponding to each row of the check matrix, which are supplied from the memory 102 for edges, are read one-by-one, and the messages from the check node corresponding to each row over one column of the check matrix are integrated to determine the integrated value. Thereafter, the message which was supplied from the edge for which the message vi is desired to be determined and which was delayed at the FIFO is subtracted from the integrated value. Furthermore, by adding the received value u0i, the computation of equation (1) is performed on the basis of the subtracted value obtained thereby. As a result, the message vi is determined. That is, by subtracting the message from the edge for which the message vi is desired to be determined from the sum of the messages from all the edges to the variable node, the message to the edge for which the message vi is desired to be determined is determined.
Also, in FIG. 11, similarly to the case in FIG. 10, the variable node calculator 103 is shown by assuming that each message, together with the sign bit, is quantized into a total of six bits. Furthermore, in the check matrix to be processed here in FIG. 8, since the maximum value of the column weight is 5, the variable node calculator 103 has five FIFOs for delaying a message. When a message of the column whose weight is less than 5 is calculated, the amount of delay at the FIFO is reduced to the value of the weight of the column.
Referring back to FIG. 9 again, a control signal (not shown) is supplied to the decoding apparatus in accordance with the weight of the check matrix. According to the decoding apparatus of FIG. 9, if only the capacities of the memories for edges 100 and 102 and the FIFOs of the check node calculator 101 and the variable node calculator 103 are sufficient, various codes can be decoded by changing only the control signal.
Although not shown, in the decoding apparatus of FIG. 9, at the final stage of the decoding, instead of the variable node calculation of equation (1), the computation of equation (5) is performed, and the computation result is output as the final decoded result.
When LDPC codes are decoded by repeatedly using the decoding apparatus of FIG. 9, the check node computation and the variable node computation are alternately performed. Therefore, for one decoding using the check matrix having 269 edges, of FIG. 8, 269×2=538 clocks are required. Therefore, for example, in order to perform 50 iterative decodings, 538×50=26900 clock operations are necessary while 90 pieces of code information (received values), which is the code length, are received, and thus, a high-speed operation approximately 300 (≅26900/90) times as high as the receiving frequency becomes necessary. In this case, if the receiving frequency is assumed to be several tens of MHz, operation at a speed of GHz or higher is required, and the implementation is not easy.
Furthermore, in a case where, for example, 50 decoding apparatuses of FIG. 9 are concatenated to decode LDPC codes, a plurality of variable node calculations and check node calculations can be performed simultaneously. For example, while the first frame is performing a variable node computation, the second frame performs a check node computation and the third frame performs a variable node computation at a previous stage. In this case, while 90 pieces of code information are received, 269 edges need to be calculated, the decoding apparatus needs to operate at a frequency approximately 3 (≅269/90) times as high as the receiving frequency, and thus realization is sufficiently possible. However, in this case, the circuit scale becomes, in simple terms, 50 times as large as the decoding apparatus of FIG. 9.
Next, a description is given of the implementation method of the decoding apparatus in a case where decoding is performed by simultaneously performing computations of all the nodes (full parallel decoding).
This implementation method is described in, for example, C. Howland and A. Blanksby, “Parallel Decoding Architectures for Low Density Parity Check Codes”, Symposium on Circuits and Systems, 2001.
FIGS. 12A to 12C show the configuration of examples of the decoding apparatus for decoding the code (a coding rate of ⅔, and a code length of 90) represented by the check matrix of FIG. 8. FIG. 12A shows the overall configuration of the decoding apparatus. FIG. 12B shows the detailed configuration of the upper portion in the figure surrounded by the dotted line B, of the decoding apparatus of FIG. 12A. FIG. 12C shows the detailed configuration of the lower portion in the figure surrounded by the dotted line C, of the decoding apparatus of FIG. 12A.
The decoding apparatus of FIGS. 12A to 12C includes one memory 205 for reception, two edge interchange devices 200 and 203, two memories 202 and 206 for edges, a check node calculator 201 made up of 30 check node calculators 2011 to 20130, and a variable node calculator 204 made up of 90 variable node calculator 2041 to 20490.
In the decoding apparatus of FIGS. 12A to 12C, all the message data corresponding to 269 edges is read simultaneously from the memory 202 or 206 for edges, and by using the message data, new message data corresponding to the 269 edges is computed. Then, all the new message data determined as a result of the computation is simultaneously stored in the memory 206 or 202 for edges at a subsequent stage. By repeatedly using the decoding apparatus of FIGS. 12A to 12C, iterative decoding is realized. Each section will now be described below in detail.
The memory 206 for edges simultaneously stores all the output messages D2061 to D20690 from the variable node calculators 2041 to 20490 at a previous stage, reads the messages D2061 to D20690 as messages D2071 to D20790 at the next clock (the timing of the next clock), and supplies them as messages D200 (D2001 to D20090) to the edge interchange device 200 at the subsequent stage. The edge interchange device 200 rearranges (interchanges) the order of the messages D2001 to D20090 supplied from the memory 206 for edges in accordance with the check matrix of FIG. 8, and supplies necessary messages D2011 to D20130 to the check node calculators 2011 to 20130, respectively.
The check node calculators 2011 to 20130 perform a computation in accordance with equation (7) by using the messages D2011 to D20130 supplied from the edge interchange device 200, and supplies the messages D2021 to D20230 obtained as a result of the computation to the memory 202 for edges.
FIG. 13 shows an example of the configuration of a check node calculator 201m (m=1, 2, . . . , 30) of FIGS. 12A to 12C for simultaneously performing check node calculations.
In the check node calculator 201m of FIG. 13, similarly to the check node calculator 101 of FIG. 10, the check node computation of equation (7) is performed, and the check node calculations are simultaneously performed for all the edges.
More specifically, in the check node calculator 201m of FIG. 13, all the messages from the variable node corresponding to each column of the check matrix of FIG. 8, which are supplied from the edge interchange device 200, are read simultaneously, and the computation of φ(|vi|) in equation (7) is performed using the LUT. Furthermore, φ(|vi|) determined from the message vi from the variable node corresponding to each column over one row of the check matrix is integrated. This enables the integrated value of φ(|vi|) determined from the message vi from all the edges to be determined. Thereafter, φ(|vi|) determined from the edge for which the message uj is desired to be determined is subtracted from the integrated value. As a result, for the edge for which the message uj is desired to be determined, Σφ(|vi|) in equation (7) is determined. That is, by subtracting the message from the edge for which the message uj is desired to be determined from the sum of the messages from all the edges to the check node, the message to the edge for which the message uj is desired to be determined is determined. Furthermore, using the LUT, the computation of φ−1(Σφ(|vi|)) in equation (7) is performed. At the same time, the sign bit of the message uj, that is, Πsign(vi) in equation (7), is also calculated similarly by using an EXOR circuit. In the manner described above, the computation of equation (7) is performed, and the message uj is determined.
In FIG. 13, by assuming that each message, together with the sign bit, is quantized to a total of 6 bits, the check node calculator 201m is shown. The circuit of FIG. 13 corresponds to one check node. For the check matrix to be processed here in FIG. 8, since check nodes of 30 rows, which is the number of the rows thereof, exist, the decoding apparatus of FIGS. 12A to 12C has 30 check node calculators 201m shown in FIG. 13.
In the check node calculator 201m of FIG. 13, nine messages can be calculated simultaneously. For the row weight of the check matrix to be processed here in FIG. 8, the weight of the first row is 8 and the weight of the second row is 9, that is, there is one case in which the number of messages supplied to the check node is 8 and there are nine cases in which the number of messages is 9. Therefore, the check node calculator 2011 has a circuit configuration capable of simultaneously calculating eight messages similarly to the circuit of FIG. 13, and the check node calculators 2012 to 20130 are configured the same as the circuit of FIG. 13.
Referring back to FIGS. 12A to 12C, the memory 202 for edges simultaneously stores all the output messages D2021 to D20230 supplied from the check node calculators 2011 to 20130 at the previous stage, and at the next time, supplies all the messages D2021 to D20230, as the output messages D2031 to D20330, to the edge interchange device 203 at the subsequent stage.
The edge interchange device 203 rearranges the order of the messages D2031 to D20330 supplied from the memory 202 for edges in accordance with the check matrix of FIG. 8, and supplies necessary messages D2041 to D20490 to the variable node calculators 2041 to 20490, respectively.
The variable node calculators 2041 to 20490 perform a computation in accordance with equation (1) by using the messages D2041 to D20490 supplied from the edge interchange device 203 and the received data (received values) D2051 to D20590 supplied from the memory 205 for reception, and supplies messages D2061 to D20690 obtained as a result of the computation to the memory 206 for edges at the subsequent stage.
FIG. 14 shows an example of the configuration of a variable node calculator 204p (p=1, 2, . . . , 90) of FIGS. 12A to 12C for simultaneously performing variable node calculations.
In the variable node calculators 204p of FIG. 14, similarly to the variable node calculator 103 of FIG. 11, the check node calculation of equation (7) is performed, and the check node calculations are simultaneously performed for all the edges.
More specifically, in the variable node calculators 204p of FIG. 14, all the messages uj from the check node corresponding to each row of the check matrix, which are supplied from the edge interchange device 203, are read simultaneously, the message from the check node corresponding to each row over one row of the check matrix is integrated, and the integrated value is determined. Thereafter, the computation of equation (1) is performed by subtracting the message supplied from the edge for which the message vi is desired to be determined from the integrated value and by adding the received value u0i to the subtracted value obtained thereby. As a result, the message vi is determined. That is, by subtracting the message for which the message vi is desired to be determined from the sum of the messages from all the edges to the variable node, the message to the edge for which the message vi is desired to be determined is determined.
In FIG. 14, by assuming that each message, together with the sign bit, is quantized to six bits, the variable node calculators 204p is shown. The circuit of FIG. 14 corresponds to one variable node. For the check matrix to be processed here in FIG. 8, since variable nodes of 90 columns, which is the number of the columns thereof, exist, the decoding apparatus of FIGS. 12A to 12C has 90 variable node calculators 204p shown in FIG. 14.
In the variable node calculators 204p of FIG. 14, it is possible to simultaneously calculate five messages. The check matrix to be processed here in FIG. 8 have 15, 45, 29, and 1 columns having weights of 5, 3, 2, and 1, respectively. Therefore, 15 variable node calculators out of the variable node calculators 2041 to 20490 have the same circuit configuration as that of the circuit of FIG. 14. The remaining 45, 29, and 1 variable node calculators have the circuit configuration capable of simultaneously calculating 3, 2, and 1 messages similarly to the circuit of FIG. 14.
Although not shown, also, in the decoding apparatus of FIGS. 12A to 12C, similarly to the case of FIG. 9, at the final stage of the decoding, instead of the variable node calculation of equation (1), the computation of equation (5) is performed, and the computation result is output as the decoded result.
According to the decoding apparatus of FIGS. 12A to 12C, it is possible to simultaneously calculate all the messages corresponding to 269 edges at one clock.
When decoding is performed by repeatedly using the decoding apparatus of FIGS. 12A to 12C, the check node computation and the variable node computation are alternately performed, and one decoding can be performed at two clocks. Therefore, for example, in order to perform 50 decodings, while 90 pieces of code information are received, the decoding apparatus needs to operate at 2×50=100 clocks, and thus, approximately the same operating frequency as the receiving frequency may be used. In general, since the code length of the LDPC codes is as great as several thousands to several tens of thousands, if the decoding apparatus of FIGS. 12A to 12C is used, the number of decodings can be greatly increased, and the improvement in the error correction performance can be expected.
However, in the decoding apparatus of FIGS. 12A to 12C, since computations of messages corresponding to all the edges of a Tanner graph are performed in parallel, the circuit scale increases in proportion to the code length. When the decoding apparatus of FIGS. 12A to 12C is configured as an apparatus for performing the decoding of LDPC codes having a particular check matrix of a particular code length and a particular coding rate, it is difficult for the decoding apparatus to perform the decoding of LDPC codes having another check matrix of another code length and another coding rate. That is, unlike the decoding apparatus of FIG. 9, it is not possible for the decoding apparatus of FIGS. 12A to 12C to decode various codes even if the control signal is changed only, and the dependence on codes is high.
In addition to the decoding apparatus of FIG. 9 and FIGS. 12A to 12C, the implementation method for simultaneously calculating messages in units of four messages rather than one message or all messages is described in, for example, E. Yeo, P. Pakzad, B. Nikolic and V. Anantharam, “VLSI Architectures for Iterative Decoders in Magnetic Recording Channels”, IEEE Transactions on Magnetics, Vol. 37, No. 2, March 2001. In this case, there are problems in that, generally, it is not easy to avoid simultaneous read-out from or simultaneous writing to different addresses of the memory, and memory access control is difficult.
Furthermore, a method of implementation by approximating the sum product algorithm has also been proposed. However, in this method, the deterioration of performance is caused to occur.
FIG. 15 shows an example of a check matrix of LDPC codes of a code length of 90 and a coding rate of ⅔. When the implementation of the decoding apparatus for decoding LDPC codes, represented by this check matrix, is considered, the design itself of the decoding apparatus for calculating messages corresponding to the edge one-by-one or the decoding apparatus for simultaneously calculating all the messages corresponding to the edge is not difficult.
However, the realization of the decoding apparatus is not easy from the aspect of the circuit scale and the operation speed.
When the codes represented by the check matrix of FIG. 15 are decoded by using the decoding apparatus for simultaneously calculating particular p edges, in the memory in which edge data (messages corresponding to the edge) is stored, access of read-out from or access of writing to a position (address) different for each row or column is necessary. Therefore, different FIFOs need to be used for each row or column. Furthermore, for the message, there are cases in which the order in which it is calculated in the check node computation and the order in which it is used in the next variable node computation are interchanged, and thus it is not easy to realize the memory for storing messages simply by an FIFO.