JP4283829B2 - Low density parity check code decoder - Google Patents

Description

  The present invention relates to a low-density parity check (LDPC) code decoding apparatus, and in particular, can cope with LDPC codes of various coding rates with the same configuration.

A Belief Propagation (BP) algorithm is known as a decoding algorithm in an LDPC code (see Non-Patent Document 1). The BP algorithm is a probability propagation algorithm that updates the reliability by repeating the row processing shown in equations (1) to (3) and the column processing shown in equations (4) and (5) ( Non-Patent Document 3).

Here, i is the number of decoding iterations, Z ⁱ n is the posterior log likelihood ratio (LLR) after i-th decoding processing is performed on the nth bit, Fn is the channel value, and R ⁱ mn is n of m rows. This is a row processing result after i-th decoding processing is performed on the th bit (initial values Z ⁰ n = Fn, R ⁰ mn = 0).

  The architecture of a decoding device to which the BP algorithm is already applied is shown. In Non-Patent Document 2, all row processing and column processing in decoding are performed in parallel for an LDPC code having a code length of 1024 bits and R = 1/2. It has been reported that a throughput of a maximum of 1 Gb / s can be realized by adopting a configuration (full parallel design). However, such a configuration method cannot perform decoding for LDPC codes having different parity check matrices.

On the other hand, the Structured LDPC code is an LDPC code composed of a basic matrix (basic check matrix) of Mb rows and Nb columns and a permutation matrix of R rows and R columns (see FIG. 4 described later), and changes the permutation matrix size R. Thus, a check matrix for codes having different code lengths can be configured. By using a zero matrix or a cyclic shift matrix as a permutation matrix and retaining only information of Mb × Nb shift values, the position of 1 in the parity check matrix can be easily specified. Non-Patent Document 3 reports on a decoding device using a structured LDPC code (hereinafter referred to as a structured LDPC code), and decoding with different code lengths is possible depending on the configuration method of the reported decoding device. .
R. G. Gallager, “Low-Density Parity-Check Codes”, IRE Trans. Info. Theory, vol. IT-8, pp. 21-28, 1962 A. J. et al. Blanksby and C.I. J. et al. Howlan, “A 690-mW 1-Gb / s 1024-b, Rate-1 / 2 Low-Density Parity-Check Code Decoder,” IEEE J. Solid-State Circuits, vol. 37, pp. 404-412, Mar. 2002 Y. Chen and D.C. Hosevar, “A FPGA and ASIC Implementation of Rate 1/2, 8088-b Irregular Low Density Parity Check Decoder,” IEEE GLOBECOM 2003, pp. 113-117, 2003

  LDPC codes with different coding rates differ in the number of rows, the number of columns, and the number of row weights (the number of 1 included in a row in the check matrix) of the basic matrix.

  In the configuration method of the decoding device proposed in Non-Patent Document 3, LDPC codes having different coding rates cannot be decoded without changing the circuit configuration.

  Therefore, a low density parity check (LDPC) code decoding apparatus that can decode an LDPC code having an arbitrary coding rate without changing the circuit configuration is desired.

  In order to solve this problem, in the present invention, a basic matrix of Mb (where Mb <= Mbmax) rows and Nb (where Nb <= Nbmax) columns and a permutation matrix of R rows and R columns that are elements of the basic matrix are provided. In the low-density parity check code decoding apparatus that decodes the low-density parity check code configured by: (1) The channel data is fetched and stored in parallel, and is stored in the same row of the basic matrix according to the BP algorithm. Nbmax data storage / column processing operation units that execute column processing of the permutation matrix in parallel, and (2) input the column processing results of all the data storage / column processing operation units, and follow the BP algorithm (3) dividing the input communication path data into per-replacement matrix size R and supplying the data to the data storage / column processing arithmetic unit; Column A column address corresponding to the logical operation unit and a row address common to all the data storage / column processing calculation units are generated and given to the data storage / column processing calculation units, and row processing according to the BP algorithm is performed. A decoding control unit that repeatedly executes the column processing, and generates decoding data based on the posterior log likelihood in all the data storage and column processing arithmetic units when the number of decoding iterations reaches a predetermined number of times, (3) The decoding control unit (3-1) cyclically relates to a valid / invalid flag of Mbmax × Nbmax and a valid valid / invalid flag determined according to a parity check matrix related to a low-density parity check code to be processed. A parity check matrix information holding unit that holds a shift amount of a permutation matrix formed of a shift matrix, and (3-2) a replacement row that holds a permutation matrix size R in the low-density parity check code to be processed A column size holding unit; and (3-3) a basic matrix row number holding unit that holds the number of rows Mb of the basic matrix in the low-density parity check code to be processed. (3-4) the valid / invalid flag The column address and the row address are generated using the shift amount, the permutation matrix size, and the basic matrix row number, and (4) each of the data storage / column processing calculation unit and the row processing calculation unit At least one has an invalidating means for invalidating the process according to the invalid valid / invalid flag.

  According to the present invention, a low-density parity check code decoding apparatus that can decode an LDPC code having an arbitrary coding rate can be realized with the same configuration.

(A) Main Embodiment Hereinafter, an embodiment of a low density parity check (LDPC) code decoding apparatus according to the present invention will be described in detail with reference to the drawings.

(A-1) Configuration of the Embodiment FIG. 1 is a block diagram showing the overall configuration of the LDPC code decoding device and the detailed configuration of the data storage / sequence processing operation unit according to the embodiment, and FIG. 2 shows the decoding in FIG. FIG. 3 is a block diagram illustrating a detailed configuration of the control unit, and FIG. 3 is a block diagram illustrating a detailed configuration of the matrix processing calculation unit in FIG.

  In FIG. 1, the LDPC code decoding apparatus 1 of this embodiment includes a decoding control unit 2 and Nbmax (Nbmax is the maximum number of applicable columns of the basic matrix) data storage / column processing calculation units 3- 1 to 3−Nbmax and a row processing calculation unit 4.

  The decoding control unit 2 executes control for decoding so as to be compatible with LDPC codes having different coding rates.

  As shown in FIG. 2, the decoding control unit 2 includes a decoding information storage control unit 10, Nbmax parity check matrix tables 11-1 to 11-Nbmax, Nbmax column address generation units 12-1 to 12-Nbmax, replacement A register 13 for storing the matrix size (R), a register 14 for storing the number of rows (Mb) of the basic matrix in the Structured LDPC code, a register 15 for storing the decoding repetition number (i), and three M-ary counters 16 to 18 A row address generation unit 19, a communication path data control unit 20, and a decoded data generation unit 21.

  The decoding information storage control unit 10 stores parity check matrix tables 11-1 to 11-Nbmax and permutation matrix size data determined according to addresses (CtrlAD) that arrive in parallel with the data (CtrlData) coming from the outside. Any one of the register 13, the basic matrix row number register 14, and the decoding repetition number storage register 15 is set.

  The check matrix is defined by all the information set in the check matrix tables 11-1 to 11-Nbmax. Each check matrix table 11-1 to 11-Nbmax stores Mb permutation matrix types (zero matrix or cyclic shift matrix) and shift value information. As permutation matrix types, for example, “0” is associated with a zero matrix and “1” is associated with a cyclic shift matrix. When the number of columns Nb of the basic matrix is smaller than the maximum number of columns Nbmax that can be applied, all the replacement matrix types of the Nbmax-Nb parity check matrix tables are set to “0”.

  FIG. 4 shows a parity check matrix in a structured LDPC code having different code lengths and coding rates, and FIG. 5 shows a storage example of the parity check matrix table in the example of FIG.

  Since the basic matrix of the parity check matrix shown in FIG. 4A is a 4 × 5 matrix and the basic matrix of the parity check matrix shown in FIG. 4B is a 3 × 8 matrix, for example, these two parity check matrices If the LDPC code decoding apparatus is compatible only with the above, the values of the maximum number of rows Mbmax and the maximum number of columns Nbmax may be 4 and 8, respectively.

  Since the number of columns of the parity check matrix shown in FIG. 4A is 5, as shown in FIG. 5A, five parity check matrix tables 11-1 to 11-5 out of 8 (= Nbmax) are included. Valid data is set, and no valid data is set in the remaining three parity check matrix tables 11-6 to 11-8. That is, the columns of the permutation matrix type in the check matrix tables 11-6 to 11-8 are all “0”.

  The permutation matrix in the first row and the first column is a cyclic shift matrix, and is obtained by shifting the column of the diagonal matrix in which the check bit “1” is arranged on the diagonal by two, so that the parity check matrix table The address “0” of 11-1 stores “1” representing the cyclic shift matrix and the shift value “2”. Since the permutation matrix in the second row and first column is a zero matrix, “0” representing the zero matrix is stored at address “1” of the parity check matrix table 11-1. The permutation matrix in the 3rd row and the 1st column is a cyclic shift matrix and is shifted by 3. Therefore, the address “2” in the parity check matrix table 11-1 is shifted to “1” representing the cyclic shift matrix. The value “3” is stored. The permutation matrix in the 4th row and the 1st column is a cyclic shift matrix and is shifted by 4. Therefore, the address “3” in the parity check matrix table 11-1 is shifted to “1” representing the cyclic shift matrix. The value “4” is stored.

  Also in the parity check matrix tables 11-2 to 11-5, values corresponding to the type and shift value of the permutation matrix of the parity check matrix shown in FIG.

  Since the number of columns of the parity check matrix shown in FIG. 4B is 8 (= Nbmax), valid data is set in all the parity check matrix tables 11-1 to 11-8 as shown in FIG. 5B. Is done.

  Since the permutation matrix in the first row and first column is a cyclic shift matrix and is not shifted, the address “0” in the parity check matrix table 11-1 has “1” representing the cyclic shift matrix and the shift value “0”. Is stored. Since the permutation matrix in the 2nd row and the 1st column is also a cyclic shift matrix and is not shifted, the address “1” in the parity check matrix table 11-1 has “1” representing the cyclic shift matrix and the shift value “0”. Is stored. The permutation matrix in the 3rd row and the 1st column is a cyclic shift matrix and is shifted by 3. Therefore, the address “2” in the parity check matrix table 11-1 is shifted to “1” representing the cyclic shift matrix. The value “3” is stored. Since the basic matrix of the parity check matrix shown in FIG. 4B is three rows and there is no fourth row, no data is set in the address “3” of the parity check matrix table 11-1.

  Also in the parity check matrix tables 11-2 to 11-8, values corresponding to the type and shift value of the permutation matrix of the parity check matrix shown in FIG.

  The permutation matrix size storage register 13 stores the size (R) of the permutation matrix, and the basic matrix row number storage register 14 stores the number of rows (Mb) of the basic matrix, and stores the decoding repetition number. The register 15 stores the decoding repetition number.

  The permutation matrix size R stored in the permutation matrix size storage register 13 is given to the M-ary counter 16 and the communication path data control unit 20. The basic matrix row number Mb stored in the basic matrix row number storage register 14 is given to the column address generators 12-1 to 12 -Nbmax, the M-ary counter 17, and the row address generator 19. The decoding repetition number stored in the decoding repetition number storage register 15 is given to the M-ary counter 17 and the row address generation unit 19.

  In the case of the parity check matrix shown in FIG. 4A, “6” is stored in the replacement matrix size storage register 13, and “4” is stored in the basic matrix row number storage register 14. In the case of the parity check matrix shown in FIG. 4B, “5” is stored in the replacement matrix size storage register 13, and “3” is stored in the basic matrix row number storage register 14.

  The M-ary counter 16 functions as a cyclic counter of the permutation matrix size (R) set in the permutation matrix size storage register 13, and a count-up trigger signal (CE) is given from the communication path data control unit 20. The count value Cout [1] is given to all the column address generators 12-1 to 12-Nbmax and the row address generator 18, and the carry signal is given to the M-ary counter 17 as a trigger signal.

  The M-ary counter 17 functions as a cyclic counter of the number of rows (Mb) of the basic matrix set in the basic matrix row number storage register 14, and the count value Cout [2] is set to all the check matrix tables 11-1. Is given to -11-Nbmax as a read address, is given to the row address generation unit 18 as an instruction for the processing target row of the basic matrix, and a carry signal is given to the M-ary counter 18 as a trigger signal.

  The M-ary counter 18 functions as a counter (cyclic counter) for the decoding repetition number (i) set in the decoding repetition number storage register 15, and gives a carry signal to the communication path data control unit 20.

  The communication path data control unit 20 controls the supply of the communication path data Din to the data storage / sequence processing calculation units 3-1 to 3-Nbmax. The communication path data control unit 20 performs control for newly distributing the communication path data Din to be used for decoding processing when a carry signal is output from the M-ary counter 18. Communication channel data Din buffered by a buffer unit (not shown) is input to the communication channel data control unit 20. When the column number Nb of the basic matrix is smaller than the maximum column number Nbmax, dummy data corresponding to the difference column number Nbma−Nb is inserted in the buffered communication path data Din. The communication path data control unit 20 divides the communication path data Din for each permutation matrix size (R) stored in the permutation matrix size storage register 13, and obtains Nbmax pieces of data Fn [1] to Fn [1] to Fn [Nbmax] is given in parallel with the addresses FAD [1] to FAD [Nbmax] to the data storage / column processing arithmetic units 3-1 to 3-Nbmax and stored in the respective Fn storage units 30, and so on. Repeated division and parallel transmission processing.

  The above-mentioned M-ary counter 16 counts up by a trigger signal (CE) output every time the communication path data control unit 20 sends out Nbmax pieces of data Fn [1] to Fn [Nbmax]. The count value Cout [1] of the M-ary counter 16 defines the processing target row in the permutation matrix.

  The count value Cout [2] of the M-ary counter 17 that receives the carry signal from the M-ary counter 16 as a trigger signal defines the processing target row (the position of the target substitution matrix) in the basic matrix. Yes.

  The row address generation unit 19 generates a row address based on the count values of the M-ary counters 16 and 17 and gives it to data storage / column processing calculation units 3-1 to 3-Nbmax described later. Since the M-ary counter 16 counts the permutation matrix size R and the M-ary counter 17 counts the basic matrix row number Mb using the carry signal of the M-ary counter 16 as a trigger, the permutation matrix size for one decoding iteration. The row address generation unit 19 generates a row address so that the number of rows corresponding to the number of rows which is the product of R and the basic matrix row number Mb is performed.

  The check matrix tables 11-1 to 11-Nbmax are given the count value Cout [2] of the M-ary counter 17 as a read address, and each of the check matrix tables 11-1 to 11-Nbmax relates to the read address. Output stored data.

  As illustrated in FIG. 5, the data stored in the parity check matrix tables 11-1 to 11 -Nbmax includes permutation matrix types (zero matrix or cyclic shift matrix) and shift value information. Of these, permutation matrix type data PTYPE [1] to PTYPE [Nbmax] are respectively provided to the corresponding data storage / column processing arithmetic units 3-1 to 3-Nbmax.

  Stored data of the corresponding check matrix tables 11-1 to 11-Nbmax and the count value Cout [1] of the M-ary counter 16 are given to the column address generation units 12-1 to 12-Nbmax, respectively. Each of the column address generation units 12-1 to 12-Nbmax corresponds to the input data, and column addresses CAD [1] to CAD [1] taking “1” in the row to be processed in the permutation matrix that is a cyclic shift matrix. Nbmax] is given to the corresponding data storage / column processing arithmetic units 3-1 to 3-Nbmax.

  For example, in the case of the parity check matrix shown in FIG. 4A (table contents shown in FIG. 5A), if the count value Cout [2] of the M-ary counter 17 is “0”, FIG. Is output from each of the check matrix tables 11-1 to 11-8. The permutation matrix type “1” (= PTYPE [1]) output from the check matrix table 11-1 is output to the corresponding data storage / column processing operation unit 3-1. At this time, if the count value Cout [1] of the M-ary counter 16 is “2” representing the third column, the column address generation unit 12-1 receives the shift value “2” and the count value Cout [1]. = 2, a column address CAD [1] indicating that the third column is valid is output.

  The decoded data generation unit 21 is calculated by all the data storage / column processing calculation units 3-1 to 3-Nbmax when the column processing and the row processing are repeated by the stored decoding repetition number (i). The a posteriori log likelihood ratios Zn [1] to Zn [Nbmax] are hard-decided and the decoded data Dout is generated.

  Each of the data storage / column processing operation units 3-1 to 3-Nbmax holds communication path data and performs the above-described column processing. Each of the data storage / column processing calculation units 3-1 to 3-Nbmax performs column processing related to the first to Nbmax-th substitution matrix in the basic matrix.

  Each of the data storage / column processing arithmetic units 3-1 to 3-Nbmax is represented by Fn storage units 30-1 to 30-Nbmax and Sn arithmetic as shown for the data storage / column processing arithmetic unit 3-1. Storage units 31-1 to 31-Nbmax, adders 32-1 to 32-Nbmax, Rmn storage units 33-1 to 33-Nbmax, subtractors 34-1 to 34-Nbmax, first selector 35-1 to 35-Nbmax and second selectors 36-1 to 36-Nbmax. The following description of the constituent elements will be given with respect to the data storage / column processing operation unit 3-1.

  The Fn storage unit 30-1 stores the communication path data Fn [1] given from the decoding control unit 2. The Fn storage unit 30-1 reads out the channel data stored in the area of the column address CAD [1] given from the decoding control unit 2 and gives it to the adder 32-1. The read communication path data corresponds to Fn in the above-described equation (5).

  The Sn calculation / storage unit 31-1 obtains an Sn value from Rmn [1] given via the second selector 36-1 according to the above-described equation (4), and stores the obtained Sn value. is there. The Sn operation / storage unit 31-1 reads out the Sn value stored in the area of the column address CAD [1] given from the decoding control unit 2 and gives it to the adder 32-1.

  The adder 32-1 adds two given values. In this addition, the above-described calculation of the equation (5) is performed. The value Zn [1] after addition is given to the decoding control unit 2 and also given to the subtractor 34-1 as a subtracted input.

  The Rmn storage unit 33-1 stores Rmn [1] given through the second selector 36-1. The Rmn storage unit 33-1 reads out the stored value of the area of the row address RAD given from the decoding control unit 2 and gives it to the subtracter 34-1 as a subtraction input.

  The subtractor 34-1 subtracts the read value of the Rmn storage unit 33-1 from the adder 32-1, and this subtraction corresponds to the calculation of the above-described equation (1).

  The output value of the subtractor 34-1 and the maximum value Max that can be taken by the input data to the row processing arithmetic unit 4 are given to the first selector 35-1 as selection inputs, and decoding control is performed as a selection control signal. Permutation matrix type data PTYPE [1] from unit 2 is provided. The first selector 35-1 selects the output value of the subtractor 34-1 when the permutation matrix type data PTYPE [1] is “1”, and when the permutation matrix type data PTYPE [1] is “0”. The maximum value Max is selected, and the selected value Lmn [1] is output to the row processing calculation unit 4.

  The value Rmn given from the row processing calculation unit 4 and “0” are given as selection inputs to the second selector 36-1, and the permutation matrix type data from the decoding control unit 2 as a selection control signal. PTYPE [1] is given. When the replacement matrix type data PTYPE [1] is “1”, the second selector 36-1 selects the value Rmn given from the row processing calculation unit 4, and the replacement matrix type data PTYPE [1] is “0”. "0" is selected, and the selected value is output to the Sn calculation / storage unit 31-1 and the Rmn storage unit 33-1.

  As shown in FIG. 3, the row processing operation unit 4 includes absolute value code separation units 40-1 to 40-Nbmax, first Gallager tables 41-1 to 41-Nbmax, an adder 42, and subtracters 43-1 to 43-1. 43-Nbmax, second Gallager tables 44-1 to 44-Nbmax, exclusive OR circuit tree 45, exclusive OR circuit (XOR) 46-1 to 46-Nbmax, and integer conversion units 47-1 to 47- Nbmax. The row processing calculation unit 4 shown in FIG. 3 is the same as that described in Non-Patent Document 3 described above, and executes the calculation of the above-described equation (2).

  Each of the absolute value code separation units 40-1 to 40-Nbmax uses the values Lmn [1] to Lmn [Nbmax] given from the corresponding data storage / sequence processing operation units 3-1 to 3-Nbmax as signs. The absolute values are separated, and the separated absolute values are given to the corresponding first Gallager tables 41-1 to 41-Nbmax, and the separated codes are given to the exclusive OR circuit tree 45 and the corresponding exclusive OR circuit 46-. 1 to 46-Nbmax. The separated signs are those in which positive is “0” and negative is “1”.

  The right side of the above-described expression (2) is composed of a calculation part related to the sign and a calculation part related to the absolute value in consideration of the expression (3). The first Gallager tables 41-1 to 41-Nbmax, the adder 42, the subtractors 43-1 to 43-Nbmax, and the second Gallager tables 44-1 to 44-Nbmax execute an arithmetic part related to absolute values. The exclusive OR circuit tree 45 and the exclusive OR circuit 46-1 to 46-Nbmax execute the calculation part related to the sign, and the integer conversion units 47-1 to 47-Nbmax are: The result of both operation parts is fused to form an output value.

  Each of the first Gallager tables 41-1 to 41-Nbmax is a look-up table that performs the calculation shown in the equation (3) on the input absolute value, and the calculation result is added to the adder 42 and the corresponding value. To the subtracters 43-1 to 43-Nbmax. The Gallager tables 41-1 to 41-Nbmax (and 44-1 to 44-Nbmax) are the maximum values that can be selected by the first selectors 35-1 to 35-Nbmax described above. The table is such that the output at that time is zero.

  The adder 42 obtains the sum of the outputs from all the first Gallager tables 41-1 to 41-Nbmax, and each of the subtracters 43-1 to 43-Nbmax corresponds to the corresponding first sum from the sum. The value of one Gallager table 41-1 to 41-Nbmax is subtracted. For example, the output of the subtracter 43-1 is the sum of the outputs of Nbmax-1 first Gallager tables 41-2 to 41-Nbmax excluding the output of the corresponding first Gallager table 41-1. The sum calculation in the equation (2) when n is 1 is executed.

  Each of the second Gallager tables 44-1 to 44-Nbmax is a look-up table for performing the operation shown in the expression (3) on the output of the corresponding subtractor 43-1 to 43-Nbmax. The result is given to the corresponding integer conversion units 47-1 to 47-Nbmax.

  The exclusive OR circuit tree 45 obtains products of codes from all the absolute value code separation units 40-1 to 40-Nbmax, and all the exclusive OR circuits 46-1 to 46-Nbmax are all And the codes from the corresponding absolute value code separation units 40-1 to 40-Nbmax (the codes from the corresponding absolute value code separation units 40-1 to 40-Nbmax for the products of all codes) Equal to the division of). For example, the output of the exclusive OR circuit 46-1 includes the codes of the Nbmax-1 absolute value code separation units 40-2 to 40-Nbmax excluding the corresponding codes of the absolute value code separation units 40-1. The calculation on the sign side in equation (2) when n is 1 is executed.

  Each integer conversion unit 47-1 to 47-Nbmax has a code given from the corresponding exclusive OR circuit 46-1 to the value given from the corresponding second Gallager table 44-1 to 44-Nbmax. Are converted into integers, and the obtained values Rmn [1] to Rmn [Nbmax] are output to the corresponding data storage / column processing arithmetic units 3-1 to 3-Nbmax. By the processing of each integer conversion unit 47-1 to 47-Nbmax, the calculation shown in the equation (2) is completed.

(A-2) Operation | movement of embodiment Next, operation | movement of the LDPC code decoding apparatus 1 of embodiment which has the structure shown in FIGS. 1-3 mentioned above is demonstrated.

  (S1) First, with respect to the check matrix tables 11-1 to 11-Nbmax, the permutation matrix size storage register 13, the basic matrix row number storage register 14, and the decoding repetition number storage register 15 via the decoding information input control unit 10, Set data according to the check matrix to be used.

  When the maximum number of columns (Nbmax) to which the basic matrix can be applied is 8, if the check matrix to be used is, for example, that shown in FIG. 4A, the content shown in FIG. 5A is the check matrix table. 11-1 to 11-8, “6” is set in the substitution matrix size storage register 13, and “4” is set in the basic matrix row number storage register 14. For example, if the parity check matrix to be used is the one shown in FIG. 4B, the content shown in FIG. 5B is set in the parity check matrix tables 11-1 to 11-8, and “5” is the replacement matrix. The size storage register 13 is set, and “3” is set in the basic matrix row number storage register 14. The number of decoding iterations is arbitrarily set regardless of the check matrix.

  (S2) Next, the communication channel data control unit 20 divides the input communication channel data Din into R data, which is the permutation matrix size set in the permutation matrix size storage register 13, and stores each data storage / column. Write to the Fn storage units 30-1 to 30-Nbmax in the processing arithmetic units 3-1 to 3-Nbmax.

  (S3) Based on the values Cout [1] and Cout [2] of the M-ary counters 16 and 17, row processing is performed by the row address generation unit 19 and the column address generation units 12-1 to 12-Nbmax. A row address RAD, Nbmax column addresses CAD [1] to CAD [Nbmax] and permutation matrix types PTYPE [1] to PTYPE [Nbmax] are generated, and data storage / column processing arithmetic units 3-1 to 3-Nbmax are generated. Output to.

  (S4) In each of the data storage / column processing calculation units 3-1 to 3-Nbmax, the Fn storage units 30-1 to 30-30 are based on the input row address RAD and column addresses CAD [1] to CAD [Nbmax]. -Nbmax, Sn calculation / storage units 31-1 to 31-Nbmax and Rmn storage units 33-1 to 33-Nbmax are read while performing the above-described equations (5) and (1), Also, input data Lmn [1] to Lmn [Nbmax] to the row processing calculation unit 3 is generated based on the input permutation matrix type information PTYPE [1] to PTYPE [Nbmax]. Here, if the permutation matrix type information is “0”, instead of the calculated value, the maximum value Max that can be taken by the input data Lmn [1] to Lmn [Nbmax] to the row processing calculation unit 3 is output. .

  (S5) The row processing computation unit 4 computes the formula (2) described above based on the data Lmn [1] to Lmn [Nbmax] input from the data storage / column processing computation units 3-1 to 3-Nbmax. Execute. The first Gallager tables 41-1 to 41-Nbmax are tables such that the output is 0 when the input is the maximum value, and thus the row for the column whose substitution matrix type is “1”. Only the processing result matches the result derived by the equation (2).

  (S6) In each of the data storage / row processing calculation units 3-1 to 3-Nbmax, the row processing results Rmn [1] to Rmn [Nbmax] output from the row processing calculation unit 4 and the substitution matrix type PTYPE [1] to The Sn value shown in Equation (4) is calculated using PTYPE [Nbmax]. Since the row processing results Rmn [1] to Rmn [Nbmax] of the row processing calculation unit 4 when the permutation matrix type is “0” are indefinite, row processing is performed by the second selectors 36-1 to 36 -Nbmax. Results The values of Rmn [1] to Rmn [Nbmax] are replaced with 0. The Rmn storage units 33-1 to 33-Nbmax hold the values, and the Sn calculation / storage units 31-1 to 31-Nbmax add the output values of the second selectors 36-1 to 36-Nbmax. , (4) is calculated.

(S7) After the processes of (S3) to (S6) described above are repeated for the number of decoding iterations stored in the decoding iteration number storage register 15, all the data is decoded by the decoded data generation unit 21 in the decoding control unit 2. The data posterior log likelihood ratios Zn [1] to Zn [Nbmax] calculated by the data storage / sequence processing operation units 3-1 to 3-Nbmax are hard-decided and the decoded data Dout is generated (A-3). Effects of the Embodiment According to the LDPC code decoding apparatus of the above embodiment, decoding can be performed for any structured LDPC code whose basic matrix is Mb × Nb (where Mb <= Mbmax, Nb = Nbmax). In other words, an LDPC code having an arbitrary coding rate can be decoded without changing the configuration.

  Here, since the data representing validity / invalidity to correspond to an arbitrary structured LDPC code is configured and stored as shown in FIG. 5, the amount of data is reduced, and the configuration of the memory and the like is reduced. can do.

(B) Other Embodiments In the above embodiment, external data is set in Nbmax parity check matrix tables 11-1 to 11-Nbmax, permutation matrix size storage register 13, and basic matrix row number storage register 14. Although the basic matrix corresponds to an arbitrary structured LDPC code, the parity check matrix tables 11-1 to 11-Nbmax storing data in advance, the permutation matrix size storage register 13, and the basic matrix row number storage register are shown. A plurality of 14 sets may be provided, and one of the sets may be designated from the outside so that the basic matrix corresponds to an arbitrary structured LDPC code.

  In the above embodiment, the configuration in which the dummy data is inserted into the channel data according to the number of columns Nb of the basic matrix is provided outside the LDPC code decoding device. The number of columns Nb of the matrix may also be taken in from the outside, and dummy data may be inserted accordingly by the LDPC code decoding apparatus.

  The configuration of the row processing calculation unit is not limited to the configuration shown in FIG. 3 as long as the configuration can execute the calculation of equation (2). Moreover, the structure which can perform the calculation of the approximate expression of (2) Formula may be sufficient. As an arithmetic configuration of such an approximate expression, for example, a document ““ Near optimal universal belief propagating based decoding of low-density parity check codes, ”IEEE Trans. Commun. , Vol. 50, pp. 406-414, Mar. 2002 ".

  Further, the decoding repetition number (i) cannot be arbitrarily set, and may be a fixed number. Furthermore, the apparatus of the present invention may be configured such that either the number of rows Mb or the number of columns Nb of the basic matrix cannot be arbitrarily set.

  Further, the first selectors 35-1 to 35 -Nbmax and the second selectors 36-1 to 36 -Nbmax in the above embodiment may be provided as components of the row processing calculation unit 4.

It is a block diagram which shows the detailed structure of the whole structure of the LDPC code decoding apparatus which concerns on embodiment, and a data storage and sequence | processing part. It is a block diagram which shows the detailed structure of the decoding control part in FIG. It is a block diagram which shows the detailed structure of the matrix process calculating part in FIG. It is explanatory drawing which shows the test matrix in Structured LDPC code which is a different code length and coding rate. It is explanatory drawing which shows the example of storage of the check matrix table in the example of FIG.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 ... LDPC code decoding apparatus, 2 ... Decoding control part, 3-1 to 3-Nbmax ... Data storage and column processing calculating part, 4 ... Row processing calculating part, 10 ... Decoding information storing control part, 11-1 to 11- Nbmax: check matrix table, 12-1 to 12-Nbmax: column address generation unit, 13: substitution matrix size storage register, 14: basic matrix row number storage register, 15: decoding repetition number storage register, 16-18: M-ary Counter 19, row address generation unit 20, communication channel data control unit 21, decoded data generation unit 35-1 to 35 -Nbmax 1st selector 36-1 to 36 -Nbmax 2nd selector, 41-1 to 41-Nbmax: first Gallager table.

Claims (4)

A low-density parity check code composed of a basic matrix of Mb (where Mb <= Mbmax) rows and Nb (where Nb <= Nbmax) columns and a permutation matrix of R rows and R columns that are elements of the basic matrix In the low-density parity check code decoding device for decoding,
Nbmax data storage / column processing operation units that capture and store communication path data in parallel, and execute column processing of the substitution matrix according to the same row of the basic matrix in parallel according to the BP algorithm;
A row processing operation unit that inputs column processing results of all the data storage / column processing operation units and performs row processing according to the BP algorithm;
After the input communication channel data is divided for each permutation matrix size R and given to each data storage / column processing operation unit, the column address corresponding to each data storage / column processing operation unit and all the above A row address common to the data storage / column processing arithmetic unit is generated and given to each of the data storage / column processing arithmetic units, and the row processing and column processing according to the BP algorithm are repeatedly executed. A decoding control unit that generates decoded data based on the posterior log likelihood in all the data storage and column processing operation units when the predetermined number of times,
The decoding control unit
A check that retains the Mbmax × Nbmax valid / invalid flag and the shift amount of the permutation matrix composed of the cyclic shift matrix related to the valid valid / invalid flag, which are determined according to the check matrix related to the low-density parity check code to be processed A matrix information holding unit;
A permutation matrix size holding unit that holds a permutation matrix size R in the low-density parity check code to be processed;
A basic matrix row number holding unit for holding the number of rows Mb of the basic matrix in the low-density parity check code to be processed;
The column address and the row address are generated using the valid / invalid flag, the shift amount, the substitution matrix size, and the basic matrix row number,
At least one of the data storage / column processing operation unit and the row processing operation unit includes invalidation means for invalidating processing in accordance with the invalid validity / invalidity flag. Code decoding apparatus.   The invalidation means replaces the value of the column processing result given from each of the data storage / column processing arithmetic units to the row processing arithmetic unit with a maximum value that the column processing result can take. 2. The low density parity check code decoding device according to 1.   3. The low density according to claim 1, wherein the invalidation means replaces a value of a row processing result given from the row processing operation unit to each data storage / column processing operation unit with 0. Parity check code decoding device. The decoding control unit is a product of the permutation matrix size R held in the permutation matrix size holding unit and the basic matrix row number Mb held in the basic matrix row number holding unit for one decoding iteration. 4. The low-density parity check code decoding apparatus according to claim 1, wherein the row address is generated so that the number of rows corresponding to the number of rows is processed. 5.

Images