Error correction decoding apparatus

Abstract

An error correction decoding apparatus includes column operators 201 and row operators 211 to 213 provided respectively in accordance with the columns and rows of a check matrix of an LDPC code. A received LLR (log-likelihood ratio) of a received sequence is input into the column operators 201 together with row LLRs from the row operators 211 to 213, whereupon the column operators 201 calculate a total value z.sub.1 of the received LLR of the received sequence and the row LLRs from the row operators 211 to 213. The row operators 211 to 213 hold operation results relating to row LLRs or column LLRs obtained during a previous operation, calculate column LLRs using the total value input from the column operators 201 and the held operation results, calculate row LLRs from the calculated column LLRs, and output the calculated row LLRs to the column operators 201.

Claims

1. The error correction decoding apparatus for decoding a received sequence encoded using an LDPC (low-density parity check) code, comprising: column operators and row operators provided respectively in accordance with columns and rows of a check matrix of the LDPC code, an input introducing the LLR (log-likelihood ratio) of the received sequence into the column operators together with row LLRs from the row operators, wherein the column operators calculate a total value of the received LLR of the received sequence and the row LLRs from the row operators, and the row operators hold operation results relating to row LLRs or column LLRs obtained during a previous operation, calculate column LLRs using the total value input from the column operators and the held operation results, calculate row LLRs from the calculated column LLRs, and output the calculated row LLRs to the column operators, wherein each of the row operators include, storage units that hold, for the respective columns, row LLRs obtained in a previous operation and output to the column operators during the previous operation; subtraction units that calculate column LLRs for the respective columns by subtracting the row LLRs obtained during the previous operation and held in the storage units for the respective columns from the total value input from the column operators; calculation units that calculate a minimum value and a sub-minimum value among absolute values of the column LLRs of the respective columns output from the subtraction units; and operation units that calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values, output from the calculation units, and output the calculated row LLRs to the column operators.

2. The error correction decoding apparatus according to claim 1, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with a min-sum decoding method.

3. The error correction decoding apparatus according to claim 1, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with an offset BP-based decoding method.

4. The error correction decoding apparatus according to claim 1, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with a normalized min-sum decoding method.

5. The error correction decoding apparatus according to claim 1, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with a -min decoding method.

6. The error correction decoding apparatus for decoding a received sequence encoded using an LDPC (low-density parity check) code, comprising: column operators and row operators provided respectively in accordance with columns and rows of a check matrix of the LDPC code, an input introducing the LLR (log-likelihood ratio) of the received sequence into the column operators together with row LLRs from the row operators, wherein the column operators calculate a total value of the received LLR of the received sequence and the row LLRs from the row operators, and the row operators hold operation results relating to row LLRs or column LLRs obtained during a previous operation, calculate column LLRs using the total value input from the column operators and the held operation results, calculate row LLRs from the calculated column LLRs, and output the calculated row LLRs to the column operators, wherein each of the row operators include, storage units that hold, for the respective columns, a minimum value and a sub-minimum value of absolute values of column LLRs calculated during a previous operation; subtraction units that calculate column LLRs by subtracting row LLRs calculated from the minimum value and the sub-minimum value of the absolute values of the column LLRs, calculated during the previous operation and held in the storage units, from the total value input from the column operators; calculation units that calculate a minimum value and a sub-minimum value among absolute values of the column LLRs output from the subtraction units, and store the calculated minimum and sub-minimum values of the absolute values in the storage units; and operation units that calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values, output from the calculation units, and output the calculated row LLRs to the column operators.

7. The error correction decoding apparatus according to claim 6, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with a min-sum decoding method.

8. The error correction decoding apparatus according to claim 6, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with an offset BP-based decoding method.

9. The error correction decoding apparatus according to claim 6, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with a normalized min-sum decoding method.

10. The error correction decoding apparatus according to claim 6, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with a -min decoding method.

11. The error correction decoding apparatus for decoding a received sequence encoded using an LDPC (low-density parity check) code, comprising: column operators and row operators provided respectively in accordance with columns and rows of a check matrix of the LDPC code, an input introducing the LLR (log-likelihood ratio) of the received sequence into the column operators together with row LLRs from the row operators, wherein the column operators calculate a total value of the received LLR of the received sequence and the row LLRs from the row operators, and the row operators hold operation results relating to row LLRs or column LLRs obtained during a previous operation, calculate column LLRs using the total value input from the column operators and the held operation results, calculate row LLRs from the calculated column LLRs, and output the calculated row LLRs to the column operators; wherein each of the column operators are provided respectively for pluralities of columns of the check matrix of the LDPC code, and perform processing on the pluralities of columns one column at a time by means of time-division, and the row operators respectively comprise: storage units that hold, for the respective columns, a minimum value and a sub-minimum value of absolute values of column LLRs calculated during a previous operation; subtraction units that calculate column LLRs by subtracting row LLRs calculated from the minimum value and the sub-minimum value of the absolute values of the column LLRs, calculated during the previous operation and held in the storage units, from the total value input from the column operators; calculation units that calculate new minimum and sub-minimum values from absolute values of the column LLRs output from the subtraction units and the minimum value and the sub-minimum value of absolute values of the column LLRs stored in the storage units, and update the minimum and sub-minimum values of the absolute values held in the storage units using the new minimum and sub-minimum values; and operation units that calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values, output from the calculation units, and output the calculated row LLRs to the column operators.

12. The error correction decoding apparatus according to claim 11, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with a min-sum decoding method.

13. The error correction decoding apparatus according to claim 11, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with an offset BP-based decoding method.

14. The error correction decoding apparatus according to claim 11, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with a normalized min-sum decoding method.

15. The error correction decoding apparatus according to claim 11, characterized in that the operation units calculate the row LLRs from the minimum value and the sub-minimum value of the absolute values by performing operation processing in accordance with a -min decoding method.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a view showing an example of a low-density parity-check matrix.

(2) FIG. 2 is a view showing an example of a parity-check matrix constituted by an mn matrix.

(3) FIG. 3A is a view showing an example of conventional column operators, row operators, and wires.

(4) FIG. 3B is a view showing an example of conventional column operators, row operators, and wires.

(5) FIG. 4 is a view showing a configuration of an error correction decoding apparatus according to a first embodiment of this invention.

(6) FIG. 5 is a view showing an example of an operation performed by a conventional column operator.

(7) FIG. 6 is a view showing an example of an operation performed by a conventional row operator.

(8) FIG. 7 is a view showing an example of an operation performed by a column operator in the error correction decoding apparatus according to the first embodiment of this invention.

(9) FIG. 8 is a view showing an example of an operation performed by a row operator in the error correction decoding apparatus according to the first embodiment of this invention.

(10) FIG. 9 is a view showing an example of an operation performed by a row operator in an error correction decoding apparatus according to a second embodiment of this invention.

(11) FIG. 10A is a view showing an example of an operation performed by a row operator in an error correction decoding apparatus according to a third embodiment of this invention.

(12) FIG. 10B is a view showing an example of an operation performed by a row operator in an error correction decoding apparatus according to a third embodiment of this invention.

(13) FIG. 11 is a view showing an example of an operation performed by the row operator in the error correction decoding apparatus according to the third embodiment of this invention.

DESCRIPTION OF EMBODIMENTS

First Embodiment

(14) FIG. 4 shows an example configuration of an error correction decoding apparatus according to a first embodiment of this invention. In FIG. 4, an LDPC code decoding apparatus (referred to hereafter as an LDPC decoding circuit 100) for decoding a received sequence encoded using an LDPC code is shown as an example of the error correction decoding apparatus. As shown in FIG. 4, the LDPC decoding circuit 100 is constituted by column operators 101 and row operators 111. The column operators 101 and the row operators 111 are provided respectively in numbers corresponding to the number of columns and the number of rows on a parity-check matrix.

(15) The LDPC decoding circuit 100 uses received LLRs .sub.c corresponding to respective columns c of the parity-check matrix as input, and outputs estimated bit sequences b.sub.c corresponding to the respective columns c. Here, as described above, the respective columns c refer to columns included in a set N(r) of column numbers at which an element on an r.sup.th row of the parity-check matrix is 1. Further, as described above, the received LLRs .sub.c are received LLRs corresponding to the columns c.

(16) The column operators 101 are constituted by a plurality of column operators #1, #2, . . . , #n corresponding respectively to the columns of the parity-check matrix. Accordingly, n denotes the number of columns on the parity-check matrix.

(17) The row operators 111 are constituted by a plurality of row operators #1, #2, . . . , #m corresponding respectively to the rows of the parity-check matrix. Accordingly, m denotes the number of rows on the parity-check matrix.

(18) The column operators 101 and row operators 111 exchange data repeatedly either a predetermined number of times or a number of times determined midway through an operation. The column operators 101 then calculate the estimated bit sequences b.sub.c on the basis of Equation (7) and output the calculated estimated bit sequences b.sub.c.

(19) In this invention, the operations performed by the column operator and the row operator differ from those of a conventional configuration. Therefore, before describing the error correction decoding apparatus according to the first embodiment of this invention, conventional column and row operators will be described.

(20) First, FIGS. 5 and 6 respectively show example configurations of conventional column and row operators.

(21) It is assumed, for example, that the column operator 101 shown in FIG. 5 is connected to a row operator #1 111, a row operator #5 112, and a row operator #6 113 in accordance with the positions of the 1 elements on the parity-check matrix. The column operator 101 uses row LLRs .sub.1,1, .sub.5,1, .sub.6,1 output from the respective row operators 111, 112, 113 as input, and outputs z.sub.1,1, z.sub.1,5, z.sub.1,6, calculated on the basis of Equation (6), respectively to the row operator #1 111, the row operator #5 112, and the row operator #6 113. In FIG. 5, z.sub.1,1=.sub.1+.sub.5,1+.sub.6,1, z.sub.1,5=.sub.1+.sub.1,1+.sub.6,1, and z.sub.1,6=.sub.1+.sub.1,1+.sub.5,1 are specific calculation results obtained from Equation (6).

(22) In the row operator 111, the row operator 112, and the row operator 113, the row LLRs .sub.1,1, .sub.5,1, .sub.6,1 are calculated respectively on the basis of Equations (1) to (5) in accordance with the sum-product decoding method, and output to the column operator 101.

(23) FIG. 6 shows an example configuration of the conventional row operators 111, 112, 113 as a row operator #x 114.

(24) In FIG. 6, it is assumed, for example, that the row operator #x 114 is connected to a column operator #1 101, a column operator #i 102, a column operator #j 103, and a column operator #k 104 in accordance with the positions of the 1 elements on the parity-check matrix. The column operators 101 to 104 are configured basically identically to the column operator #1 101 shown in FIG. 5. As shown in FIG. 6, the row operator #x 114 is constituted by an absolute value minimum value and sub-minimum value calculation unit 115, an approximation-related operation processing unit 116, and a selector 117.

(25) The row operator #x 114 shown in FIG. 6 is configured on the basis of a decoding method in which an approximation operation is performed in relation to the sum-product decoding method, such as the min-sum decoding method (Equation (8)), the offset BP-based decoding method (Equation (9)), the normalized min-sum decoding method (Equation (10)), or the -min decoding method.

(26) The absolute value minimum value and sub-minimum value calculation unit 115 receives input column LLRs z.sub.x,1, z.sub.x,i, z.sub.x,j, z.sub.x,k calculated respectively by the column operator #1 101, the column operator #i 102, the column operator #j 103, and the column operator #k 104, and calculates a minimum value and a value derived from the minimum value from respective absolute values of the column LLRs. More specifically, when the min-sum decoding method (Equation (8)) or an approximation of a decoding method based on the min-sum decoding method, such as the offset BP-based decoding method (Equation (9)) or the normalized min-sum decoding method (Equation (10)), is used by the approximation-related operation processing unit 116 and the selector 117 in a subsequent stage, the absolute value minimum value and sub-minimum value calculation unit 115 calculates the minimum value and the second smallest value among the absolute values of the respective inputs z.sub.x,c, or in other words the inputs z.sub.x,1, z.sub.x,i, z.sub.x,j, z.sub.x,k. When, on the other hand, the -min decoding method or a similar approximation thereto is used by the approximation-related operation processing unit 116 and the selector 117 in a subsequent stage, the absolute value minimum value and sub-minimum value calculation unit 115 calculates the minimum value, the second smallest value, and the third smallest value among the absolute values of the respective inputs z.sub.x,c, or in other words the inputs z.sub.x,1, z.sub.x,i, z.sub.x,j, z.sub.x,k. Note that the number of sub-minimum values determined in relation to the minimum value may be set freely in accordance with a desired approximation precision, and in this invention there are no limitations thereon. In other words, this invention may be applied to any decoding method as long as the minimum value, the second smallest value, the third smallest value, and larger values (referred to hereafter as sub-minimum values) can be calculated by the absolute value minimum value and sub-minimum value calculation unit 115, and row LLRs can be calculated by the approximation-related operation processing unit 116 and the selector 117 in a subsequent stage from these calculated values.

(27) When the offset BP-based decoding method (Equation (9)), the normalized min-sum decoding method (Equation (10)), or the -min decoding method is used by the selector 117 in a subsequent stage, the approximation-related operation processing unit 116 performs various operations on the minimum value, the second smallest value, and so on as pre-processing. For example, when the offset BP-based decoding method is used, operations such as subtracting from a minimum value |z.sub.r,c| in Equation (9) are performed. When the approximation-related operation processing unit 116 performs pre-processing in this manner, the operation load of the selector 117 in a subsequent stage decreases, and therefore a circuit configuration of the selector 117 can be simplified. Needless to mention, when similar processing to that of the min-sum decoding method (Equation (8)) is performed, there is no particular need for the approximation-related operation processing unit 116, and therefore the approximation-related operation processing unit 116 may be omitted.

(28) The selector 117 calculates output values (row LLRs .sub.x,c) to be output to the respective column operators #c, or in other words the column operators #1, #i, #j, #k 101 to 104, by performing operation processing in accordance with one of the offset BP-based decoding method (Equation (9)), the normalized min-sum decoding method (Equation (10)), the -min decoding method, the min-sum decoding method (Equation (8)), or the like using the output of the approximation-related operation processing unit 116, and outputs the calculated output values. More specifically, the selector 117 calculates a positive/negative sign sg.sub.x,c in relation to the output of the approximation-related operation processing unit 116 using Equation (11), then calculates row LLRs .sub.x,1, .sub.x,i, .sub.x,j, .sub.x,k to be output to the respective column operators #1 101, #i, 102, #j 103, #k 104 using one of Equations (8) to (10) or the like, and then selects the appropriate column operators #1 101, #i 102, #j 103, #k 104 and outputs the calculated row LLRs .sub.x,1, .sub.x,i, .sub.x,j, .sub.x,k thereto. Note that the positive/negative sign calculation of Equation (11) may be performed in another location.

(29) $\begin{array}{cc}\left[\mathrm{Numeral}11\right]& \\ {\mathrm{sg}}_{x,c}=\left(\underset{c^{}N\left(x\right)\backslash \left\{c\right\}}{.Math.}\mathrm{sgn}\left(z_{x,c^{}}\right)\right)& \left(11\right)\end{array}$

(30) Note that in the above description, the approximation-related operation processing unit 116 and the selector 117 are provided separately, but the invention is not necessarily limited thereto, and these units may be integrated. The approximation-related operation processing unit 116 and the selector 117 together constitute an operation unit that calculates row LLRs from the minimum value and the sub-minimum value of the absolute values, output from the absolute value minimum value and sub-minimum value calculation unit 115, and will therefore be referred to collectively hereafter simply as an operation unit.

(31) The prior art was described above. Next, the column operator and row operator according to the first embodiment of this invention will be described.

(32) FIG. 7 shows the configuration of the column operator according to the first embodiment of this invention.

(33) In FIG. 7, it is assumed, for example, that a column operator #1 201 is connected to three row operators, namely a row operator #1 211, a row operator #5 212, and a row operator #6 213 in accordance with the positions of the 1 elements on the parity-check matrix. A received LLR .sub.1 of a received sequence to be decoded and row LLRs .sub.1,1, .sub.5,1, .sub.6,1 output from the row operators 211 to 213 are input into the column operator #1 201. The column operator #1 201 determines a total value z.sub.1 of the received LLR and the row LLRs by performing a similar operation to that of Equation (7), i.e. z.sub.1=.sub.1+.sub.1,1+.sub.5,1+.sub.6,1, using the input values, and outputs the total value z.sub.1 to the row operator #1 211, the row operator #5 212, and the row operator #6 213. In this embodiment, in contrast to the prior art, an operation to determine a column LLR using Equation (6) is not performed by the column operator #1 201, and a column LLR is not output. A feature that differs greatly from the conventional configuration shown in FIG. 5 is that in the conventional column operator 101, as shown in FIG. 5, a different value (z.sub.1,1, z.sub.1,5, z.sub.1,6) is output to each connected row operator, whereas in this embodiment, as shown in FIG. 7, the column operator 201 outputs an identical value (the total value z.sub.1 alone) to all of the connected row operators 211 to 213. As a result, the complexity of the wiring is greatly reduced, leading to an improvement in mountability.

(34) The row operator #1 211, the row operator #5 212, and the row operator #6 213 each include a storage unit (not shown), and the row LLRs .sub.1,1, .sub.5,1, .sub.6,1 output to the column operator #1 201 are stored in the corresponding storage units. Here, .sub.1,1, .sub.5,1, and .sub.6,1 are expressed respectively as .sub.1,1, .sub.5,1, and .sub.6,1 when stored in the storage units. In the row operator #1 211, the row operator #5 212, and the row operator #6 213 according to this embodiment, column LLRs z.sub.1,1, z.sub.5,1, z.sub.6,1 are obtained by subtracting .sub.1,1, .sub.5,1, and .sub.6,1 stored in the respective storage units from the total value z.sub.1 input from the column operator #1 201. This will be described in detail below.

(35) Next, using FIG. 8, the configuration of the row operator according to this embodiment will be described.

(36) As shown in FIG. 8, it is assumed, for example, that a row operator #x 214 is connected to a column operator #1 201, a column operator #i 202, a column operator #j 203, and a column operator #k 204 in accordance with the positions of the 1 elements on the parity-check matrix. Note that the respective column operators 201 to 204 are connected to row operators other than the row operator #x 214, and as described above, connection relationships are determined in accordance with the parity-check matrix. The row operator #x 214 is constituted by the absolute value minimum value and sub-minimum value calculation unit 115, the approximation-related operation processing unit 116, the selector 117, a storage unit 218, and subtraction units 220, 221, 223, 224. The approximation-related operation processing unit 116 is similar to the conventional unit shown in FIG. 6, and therefore detailed description thereof has been omitted here. A feature that differs greatly from FIG. 6 is that in this embodiment, as shown in FIG. 8, the storage unit 218 and the subtraction units 220, 221, 223, 224 are added.

(37) The absolute value minimum value and sub-minimum value calculation unit 115 receives column LLRs z.sub.x,1, z.sub.x,i, z.sub.x,j, z.sub.x,k input from the subtraction units 220, 221, 223, 224, to be described below, and calculates a minimum value and a value derived from the minimum value from the respective absolute values of the column LLRs. The absolute value minimum value and sub-minimum value calculation unit 115 uses an identical calculation method to the conventional absolute value minimum value and sub-minimum value calculation unit 115 shown in FIG. 6, and therefore description thereof has been omitted here.

(38) The content of the operation processing performed by the selector 117 is identical to that of the selector 117 shown in FIG. 6, and therefore description thereof has been omitted here. However, a feature that differs from FIG. 6 is that in FIG. 8, an output line of the selector 117 is connected to the storage unit 218 as well as the respective column operators 201 to 204. Identical values to the values output to the column operators 101 to 104 in the conventional configuration (FIG. 6), or in other words the row LLRs .sub.x,c, are output to these output lines. More specifically, the row LLR .sub.x,1 is output to the column operator #1 201, the row LLR is output to the column operator #i 202, the row LLR .sub.x,j is output to the column operator #j 203, and the row LLR .sub.x,k is output to the column operator #k 204, while the row LLRs .sub.x,1, .sub.x,i, .sub.x,j, .sub.x,k (referred to collectively hereafter as the row LLRs .sub.x,c) are output to the storage unit 218.

(39) The storage unit 218 stores the output from the selector 117, or in other words the row LLRs .sub.x,c. Here, the respective values of the stored row LLRs .sub.x,c are expressed as .sub.x,c. The storage unit 218 outputs the stored row LLR .sub.x,1 to the subtraction unit 220 as appropriate at a timing when .sub.x,1 is input into the row operator #x 214 as z.sub.1 after having been output to the column operator #1 201 from the selector 117 and processed by the column operator #1 201. Similarly, the storage unit 218 outputs .sub.x,i to the subtraction unit 221 as appropriate at a timing where .sub.x,i is input into the row operator #x 214 as z.sub.1 after having been output to the column operator #i 202 from the selector 117 and processed by the column operator #i 202. Similar operations are performed with respect to the other subtraction units 223, 224.

(40) In the subtraction unit 220, the column LLR z.sub.x,1 is calculated by performing subtraction processing z.sub.x,1=z.sub.1.sub.x,1 to subtract .sub.x,1 from the total value z.sub.1 input from the column operator #1 201. Similar processing to that of the subtraction unit 220 is performed in the subtraction unit 221, the subtraction unit 223, and the subtraction unit 224, whereby a column LLR z.sub.x,i (=z.sub.1.sub.x,i), a column LLR z.sub.x,j (=z.sub.1.sub.x,j), and a column LLR z.sub.x,k (=z.sub.1.sub.x,k) are respectively calculated.

(41) Note that any number of column operators may be connected to the row operator #x 214, and this embodiment may be configured such that the number of connected column operators is different to the four shown in FIG. 8. The number of provided subtraction units and the processing performed by the other units differ according to the number of connected column operators, but a person having technical knowledge in this field could easily conceive of this from the content described heretofore.

(42) With a conventional column operator, output values to be output to the respective row operators are calculated in a number corresponding to the number of connected row operators so that a different value can be output to each connected row operator. In the row operator #x 214 according to this embodiment, however, the row LLR .sub.x,c obtained in the previous operation is held as .sub.x,c and subtracted from the total value z.sub.c. Therefore, the respective column operators 201 to 204 can output an identical value (the total value z.sub.c alone) to the row operators connected thereto. According to this embodiment, identical values are output to the row operators from the column operators, and therefore the complexity of the wiring can be reduced, leading to an improvement in mountability.

(43) Further, with a conventional column operator, in a case where the output values of the column operators are output after being stored temporarily in a flip-flop, one flip-flop must be provided for each connected row operator so that a different value can be output to each connected row operator. In this embodiment, however, an identical value is output to the connected row operators, and therefore only one type of flip-flop is required. According to this embodiment, the number of flip-flops can be reduced, leading to a reduction in circuit scale.

(44) In this embodiment, as described above, an LDPC code decoding apparatus for decoding a received sequence encoded using an LDPC code includes the plurality of column operators 201 to 204 and the plurality of row operators 214 provided in accordance with the respective columns and rows of the check matrix of the LDPC code. The received LLR of the received sequence is input into the column operators 201 to 204 together with the row LLRs from the row operators 214, whereupon the column operators 201 to 204 calculate the total value z.sub.c of the received LLR of the received sequence and the row LLRs from the row operators 214. Further, the row operators 214 hold calculation results relating to row LLRs or column LLRs obtained during a previous operation, calculate column LLRs using the total value z.sub.c input from the column operators 201 to 204 and the held calculation results, calculate row LLRs from the calculated column LLRs, and output the calculated row LLRs to the column operators. Hence, the column operators 201 to 204 are configured to calculate only the total value z.sub.c of the received LLR and the row LLRs from the row operators 214 without determining column LLRs, and to output an identical value (the total value z.sub.c) to all of the row operators. As a result, reductions can be achieved in the number of wires laid between the column operators and the row operators and the complexity of the wiring, leading to an improvement in the mountability of the LDPC code decoding circuit.

(45) Further, in this embodiment, each row operator 214 includes the storage unit 218 for holding, in relation to the respective columns, the row LLRs obtained during the previous operation and output to the column operators 201 to 204 during the previous operation, the subtraction units 220, 221, 223, 224 for calculating the column LLR of each column by subtracting the row LLR obtained in the previous operation and held in the storage unit for each column from the total value z.sub.c input from the column operators 201 to 204, the absolute value minimum value and sub-minimum value calculation unit 115 for calculating the minimum value and the sub-minimum value from the absolute values of the column LLRs of the respective columns, output from the subtraction units 220, 221, 223, 224, and the operation unit 116, 117 for calculating the row LLRs from the minimum value and sub-minimum value of the absolute values, output from the absolute value minimum value and sub-minimum value calculation unit 115, and outputting the calculated row LLRs. With a conventional column operator, output values to be output to the respective row operators are calculated in a number corresponding to the number of connected row operators so that a different value can be output to each connected row operator. With the row operators 214 according to this embodiment, configured as described above, however, the row LLRs .sub.x,c are held and subtracted from the total value z.sub.c, and therefore the respective column operators 201 to 204 can output an identical value to the row operators 214 connected thereto. Hence, according to this embodiment, identical values are output to the row operators from the column operators, and therefore the complexity of the wiring can be reduced, leading to an improvement in mountability.

(46) Furthermore, in this embodiment, the decoding processing of the selector 117 is performed using a decoding method in which an approximation operation is applied to the sum-product decoding method, such as the min-sum decoding method (Equation (8)), the offset BP-based decoding method (Equation (9)), the normalized min-sum decoding method (Equation (10)), or the -min decoding method, instead of the sum-product decoding method, and therefore an effect of reducing the calculation amount is obtained.

Second Embodiment

(47) In the first embodiment described above, the row operators 214 hold the row LLRs .sub.x,c obtained during the previous operation in the storage unit and subtract the held row LLRs .sub.x,c from the inputs obtained from the respective column operators 201 to 204, and as a result, the column operators 201 to 204 can output identical values to the row operators connected thereto. However, the storage unit 218 must be disposed in the row operator. In this embodiment, a method of disposing the storage unit is modified.

(48) FIG. 9 shows a configuration of a row operator #x 314 of an error correction decoding apparatus according to this embodiment.

(49) On the basis of the parity-check matrix, it is assumed, for example, that the row operator #x 314 is connected to the column operator #1 201, the column operator #i 202, the column operator #j 203, and the column operator #k 204. Note that the respective column operators are connected to row operators other than the row operator #x 314, and as described above, the connection relationships are determined in accordance with the parity-check matrix. The row operator #x 314 is constituted by the absolute value minimum value and sub-minimum value calculation unit 115, the approximation-related operation processing unit 116, the selector 117, a storage unit 318, an approximation-related operation processing unit 2 319, and the subtraction units 220, 221, 223, 224.

(50) The column operator #1 201, the column operator #i 202, the column operator #j 203, the column operator #k 204, the absolute value minimum value and sub-minimum value calculation unit 115, the approximation-related operation processing unit 116, the selector 117, and the subtraction units 220 to 224 are similar to the first embodiment. This embodiment differs from the first embodiment in that the storage unit 318 is provided in place of the storage unit 218, and that the approximation-related operation processing unit 2 319 is added. Hence, the storage unit 318 and the approximation-related operation processing unit 2 319, which differ from the first embodiment, will be described here.

(51) The storage unit 318 holds the output from the absolute value minimum value and sub-minimum value calculation unit 115. More specifically, the storage unit 318 stores the minimum value and sub-minimum value of the absolute values of the column LLRs z.sub.x,1, z.sub.x,i, z.sub.x,j, z.sub.x,k, which are output from the subtraction units 220, 221, 223, 224, calculated by the absolute value minimum value and sub-minimum value calculation unit 115. The stored minimum value and sub-minimum value are input into the operation processing unit 2 319 and used therein to calculate the row LLRs .sub.x,1, .sub.x,i, etc.

(52) The approximation-related operation processing unit 2 319 calculates the row LLRs .sub.x,1, .sub.x,i, etc. on the basis of the minimum value and sub-minimum value output from the storage unit 318. As a calculation method, identical processing to that of the approximation-related operation processing unit 116 is performed. Note, however, that the approximation-related operation processing unit 2 319 also includes a part of the functions of the selector 117, namely a function for selecting the appropriate subtraction unit 220 and outputting the calculated values .sub.x,1, .sub.x,i, etc. thereto, and a function for calculating the positive/negative sign on the basis of Equation (11).

(53) Note that any number of column operators may be connected to the row operator #x 314, and this embodiment may be configured such that the number of connected column operators is different to the four shown in the drawing. The number of provided subtraction units and the processing performed by the other units differ according to the number of connected column operators, but a person having technical knowledge in this field could easily conceive of this from the content described heretofore.

(54) According to this embodiment, the storage unit can be reduced in size in comparison with the first embodiment, even in a row operator having a large number of connections to column operators, and as a result, the circuit scale can be reduced.

(55) Although the approximation-related operation processing unit 2 319 is required, the processing unit 319 is a merely a circuit that performs a subtraction operation or the like on several values including the minimum value and the second smallest value, as described above, and therefore the processing unit 2 319 has a smaller circuit scale than the other operation units.

(56) Furthermore, likewise in this embodiment, the storage unit not provided in the conventional configuration (FIG. 6) is required, but even in the conventional configuration, a storage unit must be provided somewhere in order to realize a circuit. In the conventional configuration, the storage unit is located in the column operator, the row operator, or on the exterior thereof, and can be configured with a high degree of freedom. Therefore, the storage unit is not shown in FIG. 6. The storage unit provided in this embodiment and the other embodiments includes a part or all of the functions of the storage unit provided in the conventional configuration, and does not therefore contribute greatly to an increase in circuit scale.

(57) According to this embodiment, as described above, similar effects to the first embodiment are obtained. Additionally, in this embodiment, only the minimum value and sub-minimum value calculated by the absolute value minimum value and sub-minimum value calculation unit 115 are stored in the storage unit 318, and therefore, in comparison with the first embodiment, a storage capacity of the storage unit 318 can be reduced, enabling a reduction in circuit scale.

Third Embodiment

(58) In the first and second embodiments described above, configurations in which the column operators are disposed in a number corresponding to the number of columns on the parity-check matrix were described. In this embodiment, the column operators are disposed in a smaller number than the number of columns on the parity-check matrix, and processing is performed on all of the columns by having the column operators implement time-division processing.

(59) FIG. 10 shows a configuration of an error correction decoding apparatus according to this embodiment. FIG. 10A illustrates an example of a parity-check matrix and the column operators and row operators used to process the columns and rows of the parity-check matrix. In FIG. 10B, a column operator #1 11, a column operator #2 12, a row operator #1 21, a row operator #2 22, a row operator #3 23, a row operator #4 24, a row operator #5 25, and a row operator #6 26 are shown as examples. FIG. 10B shows wiring laid between the respective column operators and row operators, and data input/output relationships are indicated by arrows.

(60) In the example of FIG. 10A, the column operation on the first to third columns and the column operation on the fourth to sixth columns from the left are performed by the column operator #1 11 and the column operator #2 12 which are shown in FIG. 10B, respectively, one column at a time by means of time-division processing. In this case, as shown in FIG. 10B, the column operator #1 11 is connected to the row operator #1 21, the row operator #2 22, the row operator #4 24, the row operator #5 25, and the row operator #6 26 in accordance with the elements of the parity-check matrix. In other words, the column operator #1 in FIG. 10 is wired to all of the row operators to which the column operators #1 to #3 are connected in FIG. 3. As shown in the drawing, however, the column operation is performed by time-division processing, and therefore a wire extending from a row operator to a column operator can be shared by columns having different column numbers. The reason for this is that the column operator #1 performs column processing relating to one column at a certain unit time, and therefore an input signal from the row operator need only relate to one column. For example, the column operator #1 11 and the row operator #6 26 exchange data on all of columns 1, 2, and 3, but the data processed simultaneously by the column operator #1 11 relate to one column, and therefore the wire can be shared. As a result, three wires shown in FIG. 10 can be reduced to a single wire.

(61) To perform the column operation by time-division processing, the input data of the column operator are controlled such that the row LLRs corresponding to the column to be processed at that time are output from the respective row operators. In other words, a column operator #1 402 performs column processing on a set column at a predetermined time. The configuration of the row operator will be described below.

(62) FIG. 11 shows a configuration of an error correction decoding apparatus according to this embodiment.

(63) In this embodiment, as shown in FIG. 11, it is assumed that a row operator #x 414 is connected to a column operator #1 402, a column operator #2 403, and other column operators. Note that the respective column operators are connected to row operators other than the row operator #x 414, and as described above, the connection relationships are determined in accordance with the parity-check matrix. Further, as shown in FIG. 11, the row operator #x 414 is constituted by an absolute value minimum value and sub-minimum value calculation unit 415, the approximation-related operation processing unit 116, a selector 417, a storage unit 418, an approximation-related operation processing unit 2 419, and subtraction units 420, 421.

(64) As described above, the column operator #1 402 performs column processing on a set column at a predetermined time. It is assumed here, for example, that the column processing is performed from column 1 to column i. Control for determining the column to be subjected to the column operation is performed externally so that the row LLRs .sub.r,c and the received LLR .sub.c are selected appropriately and input into the column operator 402 at an appropriate timing. Further, the output estimated bits b.sub.c are stored in an appropriate sequence in an externally disposed storage apparatus such as a buffer memory.

(65) The column operator #2 403 performs similar processing to the column operator #1 402.

(66) The absolute value minimum value and sub-minimum value calculation unit 415 calculates new minimum and sub-minimum values using column LLRs z.sub.x,p, z.sub.x,q input from the subtraction units 420, 421 and minimum and sub-minimum values stored in the storage unit 418 as input, and outputs the calculated minimum and sub-minimum values to the approximation-related operation processing unit 116 and the storage unit 418. Since the column operation processing is performed by time-division processing, this measure is taken so that the minimum value and sub-minimum value of the absolute values can be processed sequentially. Note that here, p and q denote column numbers of the column processing performed by the column operator #1 402 and the column operator #2 403. In other words, p denotes any column number from 1 to i and q denotes any column number from j to k.

(67) The calculation processing performed by the approximation-related operation processing unit 116 is identical to that of the first and second embodiments, and therefore description thereof has been omitted.

(68) The selector 417 calculates output values (the row LLRs .sub.x,c) to be output to respective column operators #c 402, 403 in accordance with the output of the approximation-related operation processing unit 116, and outputs the calculated output values. Since the column operation is performed by time-division processing, data are not necessarily output to all of the column operators #c 402, 403 connected to the selector 417 at each time. The selector 417 performs a selection such that 0 is output to a connection line connected to a column operator that does not require output. Note that similarly to the selector 117 according to the first and second embodiments, the selector 417 calculates a positive/negative sign in accordance with the output of the approximation-related operation processing unit 116 using Equation (11), calculates the row LLRs to be output to the column operators using one of Equations (8) to (10) or the like, selects the appropriate column operators, and outputs the calculated row LLRs thereto. The positive/negative sign calculation of Equation (11) may be performed in another location.

(69) Similarly to the second embodiment, the storage unit 418 stores the minimum value and sub-minimum value calculated by the absolute value minimum value and sub-minimum value calculation unit 415 during the previous operation, and outputs the stored minimum value and sub-minimum value to the absolute value minimum value and sub-minimum value calculation unit 415 and the approximation-related operation processing unit 2 419. At this time, the absolute value minimum value and sub-minimum value calculation unit 415 updates the minimum value and sub-minimum value stored in the storage unit 418 within a range enabling calculation of .sub.x,p, .sub.x,q, which are used by the subtraction units 420, 421. The reason for this is that .sub.x,p, .sub.x,q used by the subtraction units 420, 421 must be identical to values .sub.x,p, .sub.x,q output previously by the row operator #x 414, and therefore, when the minimum value and sub-minimum value stored in the storage unit 418 are updated constantly, it may become impossible to calculate .sub.x,p, and .sub.x,q appropriately due to a time difference.

(70) The approximation-related operation processing unit 2 419 calculates the row LLRs .sub.x,p, .sub.x,q, etc. on the basis of the minimum value and sub-minimum value output from the storage unit 418. Here, p and q indicate the column numbers of the column processing performed by the column operator #1 402 and the column operator #2 403. Accordingly, the values .sub.x,p, .sub.x,q, etc. corresponding to the column processing performed at that time are calculated and output to the subtraction units 420 and 421. .sub.x,p, .sub.x,q, etc. are calculated by identical processing to that of the approximation-related operation processing unit 1 116. Note, however, that the approximation-related operation processing unit 2 419 also includes a part of the functions of the selector 417, namely a function for selecting the appropriate subtraction unit 220 and outputting the calculated values .sub.x,1, .sub.x,i, etc. thereto, and a function for calculating the positive/negative sign on the basis of Equation (11).

(71) The subtraction unit 420 calculates z.sub.x,p=z.sub.p.sub.x,p by performing processing to subtract the row LLR .sub.x,p input from the approximation-related calculation processing unit 2 419 from z.sub.p (=z.sub.1 to z.sub.i) input from the column operator #1 402, and outputs the calculated value. Note that since the column operation is performed by time-division processing, meaningful data are not always output to the row operator #x 414 from the column operator #1 402. More specifically, on the row of the parity-check matrix to which the row operator #x 414 corresponds and the column in which the column operator #1 402 performs the column operation at a certain time, the matrix element of the parity-check matrix may be 0. In this case, the output value of the subtraction unit 420 is fixed at a predetermined large value regardless of the input value. On a circuit, a bit width of each piece of data is fixed, and therefore a maximum value (a positive value) corresponding to the bit width may be output. When the maximum value is output, the maximum value is automatically ignored by the absolute value minimum value and sub-minimum value calculation unit 415 in the subsequent stage.

(72) The subtraction unit 421 is configured similarly.

(73) Note that any number of column operators may be connected to the row operator #x 414, and this embodiment may be configured such that the number of connected column operators is different to the two shown in FIG. 11. The number of provided subtraction units and the processing performed by the other units differ according to the number of connected column operators, but a person having technical knowledge in this field could easily conceive of this from the content described heretofore.

(74) With the configuration described above, the column operation processing is performed by time-division, and therefore the wiring extending from the row operators to the column operators can be shared. As a result, the complexity of the wiring can be reduced.

(75) Further, by performing the column operation processing by time-division, the number of column operators can be reduced, enabling a reduction in the circuit scale.

(76) The internal configuration of the row operator #x 414 was described above using FIG. 11, but the scope of this invention is not limited to this configuration. For example, in the above description, the subtraction unit 420 performs processing to subtract the row LLR .sub.x,p input from the approximation-related calculation processing unit 2 419 from z.sub.p (=z.sub.1 to z.sub.i) input from the column operator #1 402, but the following configuration may be employed instead. By having the approximation-related calculation processing unit 2 419 invert the sign of the row LLR .sub.x,p so as to output .sub.x,p to the subtraction unit 420, the subtraction unit 420 can perform an equivalent operation by adding together z.sub.p and .sub.x,p. This applies likewise to the first and second embodiments.

(77) Further, as regards calculation of the positive/negative sign sg.sub.x,c based on Equation (11), Equation (11) does not have to be calculated every time, and instead, a calculation result sync of Equation (12) may be held, and the positive/negative sign sg.sub.x,c may be calculated by multiplying sgn(z.sub.x,c) by sync. Furthermore, by setting sgn(z.sub.x,c)=+1 at 0, setting sgn(z.sub.x,c)=1 at 1, and expressing these respective values as single bits, multiplication of sgn(z.sub.x,c) becomes equivalent to an exclusive OR operation. This applies likewise to the first and second embodiments.

(78) $\begin{array}{cc}\left[\mathrm{Numeral}12\right]& \\ {\mathrm{syn}}_c=\left(\underset{c^{}N\left(x\right)}{.Math.}\mathrm{sgn}\left(z_{x,c^{}}\right)\right)& \left(12\right)\end{array}$

(79) As indicated by these examples, the configurations set forth in the embodiments are merely examples, and this invention may be configured by performing equivalent operations. Likewise in these cases, the effects of reducing the complexity of the wiring and reducing the circuit scale can be obtained.

(80) Moreover, in a similar configuration to the configuration of this embodiment, the row operation processing may be performed by time-division processing. A row operator #x that performs the row operation processing by time-division processing is configured identically to that of FIG. 9 (a case where the column operation is not performed by time-division) or FIG. 11 (a case where both the column operation processing and the row operation processing are performed by time-division processing) apart from slight differences, but the connection relationships between the row operator #x and the column operators differ in accordance with the correspondence between the plurality of rows on which the row operator #x performs time-division processing and the positions of the is on the parity-check matrix. Further, the storage capacity of the storage portion must be increased in comparison with the configurations shown in FIGS. 9 and 11 by an amount corresponding to the number of rows processed by the row operator #x. Note, however, that the increase in storage capacity is an increase per row operator, and the total storage capacity, taking into account all of the row operators, is equivalent to that of the configurations shown in FIGS. 9 and 11.

(81) Likewise in this case, similarly to a case where the column operation processing is performed by time-division processing, the wiring can be shared, enabling a reduction in the complexity of the wiring. Furthermore, the number of row operators can be reduced, enabling a reduction in the circuit scale.

(82) In the time-division processing performed during the column operation according to this embodiment, the number of wires that can be shared increases steadily as the number of matrix elements exhibiting 1 on the same row in the plurality of columns subjected to time-division processing by the respective column operators increases, and as a result, the complexity of the wiring can be reduced even further. In one type of LDPC code, known as a spatially-coupled LDPC code, in particular, the parity-check matrix is regular, making it easy to locate a set of columns in which a large number of matrix elements exhibiting 1 are included on the same row in a plurality of columns. In other words, the columns to be subjected to time-division processing by the respective column operators can be allocated efficiently so that a large number of wires can be shared, and as a result, the complexity of the wiring can be reduced. Moreover, likewise in a case where the row operation processing is performed by time-division processing, the rows to be subjected to time-division processing by the respective row operators can be allocated efficiently using the regularity of the parity-check matrix of a spatially-coupled LDPC code, and therefore a large number of wires can be shared, with the result that the complexity of the wiring can be reduced.

(83) According to this embodiment, as described above, similar effects to the first and second embodiments are obtained. Furthermore, in this embodiment, the column operators are disposed in a smaller number than the number of columns on the parity-check matrix, and the columns are processed entirely by time-division processing. Therefore, the wiring extending from the row operators to the column operators can be shared, enabling a reduction in the complexity of the wiring, and the number of column operators can be reduced, enabling a reduction in the circuit scale.