JP4803134B2 - Parity check decoder - Google Patents

Description

  The present invention relates to a parity check decoding apparatus.

  As one of error correction techniques, attention is paid to a low-density parity check (LDPC) code and a sum-product decoding method that is a decoding method thereof (see Patent Document 1). As for the characteristic of this code, it is known that a decoding characteristic of 0.004 dB can be obtained up to the Shannon limit of the white Gaussian channel.

The LDPC code can theoretically perform row processing for all rows at the same time, and can perform all parallel processing for simultaneously performing column processing for all columns, so that high-speed processing is possible.
However, in order to perform operations for all the rows or columns at the same time, the circuit is complicated and the scale becomes large, which is difficult to realize.
Therefore, when realizing LDPC decoding processing using circuit technology, a min-sum decoding method with a reduced amount of calculation is considered effective. However, the current situation is that the circuit scale has not yet been reduced to a sufficient size.

Therefore, Non-Patent Document 1 attempts to reduce the size of the circuit by performing an approximate serial calculation process for the parallel calculation process.
Non-Patent Document 2 proposes a partially parallel processing type LDPC decoder based on bit-serial processing.
In the non-patent document 1, the processing speed is reduced because the serial processing is complete, but in the non-patent document 2, the processing speed can be increased.
JP 2005-269535 A Darabiha, A, A bit-serial approximate min-sum LDPC decoder and FPGA implementation Proc.IEEE ISCA2006 Kazuhiro Shimizu "Partially-Parallel LDPC Decoder Based on High Efficiency Message-Passing Algorithm", Proc. IEEE ICCD2005, pp.503-510

   In the bit serial processing in Non-Patent Documents 1 and 2, the circuit can be reduced in size. However, in the bit serial processing, the received signal is processed in order from the front due to the characteristics of the algorithm, and the decoding result largely depends on the earlier data of the received signal sequence. As a result, when data with concentrated errors is received in front of the received signal sequence, there is a high possibility that it cannot be normally decoded.

  Therefore, an object of the present invention is to provide a parity check decoding apparatus suitable for preventing a reduction in processing speed while reducing the size of a circuit without using bit serial processing, and preventing deterioration in decoding performance. And

  The present invention provides a parity check decoding apparatus that repeatedly performs row processing and column processing based on a parity check matrix, a storage unit that stores row processing calculation results and column processing calculation results, and the column processing acquired from the storage unit A row processing unit that performs row processing based on the parity check matrix and outputs the row processing calculation result to the storage unit, and uses the calculation result of the row processing acquired from the storage unit. A column processing unit that performs column processing based on the parity check matrix and outputs a calculation result of the column processing to the storage unit, and a control unit that controls a decoding process, and the row processing unit includes a parity processing unit The column processing unit is configured as a partial column processing unit that performs column processing for a plurality of columns of a part of the parity check matrix. The control unit controls the order of rows and / or columns to be executed by the partial row processing unit and / or the partial column processing unit, and according to the controlled order, the partial row processing unit and The parity check decoding apparatus is characterized in that access to the storage unit by the partial sequence processing unit is controlled.

According to the present invention, since the row processing unit is configured as a partial row processing unit and the column processing unit is configured as a partial column processing unit and partial parallel processing is possible, compared to the case of full parallel processing. Thus, the circuit size of the row processing unit and the column processing unit can be reduced.
In addition, since the storage unit that stores the calculation results of the partial row processing unit and the partial column processing unit is included, the result of partial sequential execution of row processing or column processing can be accumulated in the storage unit.
In other words, even if row processing is not performed on all rows simultaneously or column processing is not performed on all columns simultaneously, partial row processing or column processing is performed and the results are sequentially stored in the storage unit. be able to. Therefore, the row processing calculation results or column processing calculation results for all the rows or columns are accumulated in the storage unit.

Furthermore, since the present invention includes a control unit that controls the order of rows and / or columns to be executed by the row processing unit and / or the column processing unit, the column processing after the row processing can be executed as soon as possible. The column order can be controlled so that the row processing after column processing can be executed as soon as possible.
Further, the control unit accesses the storage unit by the partial row processing unit and / or the partial column processing unit according to the order of the rows and / or columns to be executed by the partial row processing unit and / or the partial column processing unit. Therefore, even if the order of rows or columns is controlled, an appropriate storage unit is accessed.

  The storage unit includes a plurality of storage devices capable of storing a plurality of calculation results for one entry, and selects a storage device accessed by the partial row processing unit and / or the partial column processing unit. Preferably, the control unit controls the access to the storage unit by the partial row processing unit and / or the partial column processing unit by controlling the selection unit. In this case, since the storage unit includes a plurality of storage devices capable of storing a plurality of calculation results for one entry, the number of entries can be reduced, and the circuit configuration of the storage unit is simplified. In addition, even if the number of entries is reduced, a selection unit for selecting a storage device to be accessed by the partial row processing unit and / or the partial column processing unit is provided, so that an appropriate storage device can be accessed. is there.

  The control unit includes schedule data that defines when the partial row processing unit and / or the partial column processing unit accesses which storage device among the plurality of storage devices, and the control unit includes: It is preferable to control the selection unit based on the schedule data. In this case, since the partial row processing unit and / or the partial column processing unit can set which storage device to access when among the plurality of storage devices by the schedule data, the access schedule to the storage unit can be set by hardware. The design can be easily changed without any changes. Then, by appropriately setting the schedule data, the waiting time of the partial row processing unit or the partial column processing unit can be reduced for access to the storage unit.

The control unit controls the order of rows to be executed by the partial row processing unit so that the order is different from the row order in the parity check matrix. The order is preferably controlled so as to be in the same order as the columns in the parity check matrix.
In this case, the processing speed can be improved by controlling the order of rows to be executed by the partial row processing unit in an appropriate order so that column processing can be executed as soon as possible.
On the other hand, since the order of the columns of the parity check matrix corresponds to the order of the received signal sequence, if the order of the columns to be executed by the partial sequence processing unit is changed from the order of the columns of the parity check matrix, the operation result based on the parity check matrix However, by performing control in the same order without changing the order of the columns in the parity check matrix as in the present invention, such rearrangement becomes unnecessary and processing delay can be prevented.

  According to the present invention, it is possible to obtain a parity check decoding apparatus suitable for reducing a processing speed while preventing a reduction in processing speed and preventing deterioration in decoding performance.

Embodiments of the present invention will be described below with reference to the drawings.
FIG. 1 is a diagram illustrating an example of a configuration of a communication system having a decoding device (decoder) according to an embodiment of the present invention.
In FIG. 1, in the communication system, on the transmission side, an encoder 1 for generating a transmission code by adding redundant bits for error correction to transmission information, and a code of (K + M) bits from the encoder 1 are used. And a modulator 2 that modulates and outputs to the communication path 3 according to a predetermined method.

  The encoder 1 adds M bits of redundant bits for parity calculation to the K bits of information to generate (K + M) bits of LDPC (low density parity check) encoded data. In the low density parity check matrix, rows correspond to redundant bits and columns correspond to code bits. It should be noted that, in which bits of the (K + M) bits of LDPC encoded data, the K information bits and the M redundant bits are arranged as determined by the transmission side and the reception side. Also good.

  The modulator 2 performs modulation such as amplitude modulation, phase modulation, code modulation, frequency modulation or orthogonal frequency division multiplexing modulation according to the configuration of the communication path 3. For example, when the communication path 3 is an optical fiber, the modulator 2 performs light intensity modulation (a kind of amplitude modulation) by changing the luminance of the laser diode according to the transmission information bit value. For example, when the transmission data bit is “0”, it is converted to “+1”, and the laser diode is transmitted with an increased emission intensity. When the transmission data bit is “1”, it is changed to “−1”. After conversion, the emission intensity of the laser diode is weakened and transmitted.

  In the communication system, on the receiving side, a demodulator 4 that demodulates a modulated signal transmitted via the communication path 3 and demodulates a digital code of (K + M) bits, and (K + M) from the demodulator 4 ) A decoder (decoding device) 5 is provided that performs decoding processing based on a parity check matrix on a bit code to reproduce the original K-bit information.

  The demodulator 4 performs demodulation processing according to the transmission form in the communication path 3. For example, in the case of amplitude modulation, phase modulation, code modulation, frequency modulation, orthogonal frequency division multiplexing modulation, etc., the demodulator 4 performs processing such as amplitude demodulation, phase demodulation, code demodulation, and frequency demodulation.

  FIG. 2 is a diagram showing a list of correspondence relationships between the output data of the modulator 2 and the demodulator 4 when the communication path 3 is an optical fiber. In FIG. 2, as described above, when the communication path 3 is an optical fiber, the modulator 2 converts the transmission data to “1” when the transmission data is “0”, and the transmission laser diode (light emitting diode) When the emission intensity increases and the transmission data bit is “1”, it is converted to “−1”, and the emission intensity of the laser diode is reduced to transmit.

The light intensity transmitted to the demodulator 4 due to transmission loss in the communication path 3 has an analog intensity distribution from the strongest intensity to the weakest intensity. The demodulator 4 performs a quantization process (analog / digital conversion) on the input optical signal to detect the received light level.
FIG. 2 shows the received signal intensity when the light reception level is quantized in eight steps. That is, when the light reception level is data “7”, the light emission intensity is considerably high, and when the light reception level is “0”, the light intensity is considerably low. Each light reception level is associated with signed data and output from the demodulator 4. The output of the demodulator 4 is data “3” when the light reception level is “7”, and data “−4” when the light reception level is “0”. Therefore, the demodulator 4 outputs a signal subjected to multilevel quantization with respect to a 1-bit received signal.

  The decoder 5 receives (K + M) -bit received information (each bit includes multi-level information) given from the demodulator 4 and receives LDPC parity according to the sum-product decoding method or the min-sum decoding method. A check matrix is applied to restore the original K-bit information.

  In FIG. 2, the demodulator 4 generates bits quantized to 8 levels. However, in general, the demodulator 4 can perform decoding using bits quantized to L values (L ≧ 2).

  In FIG. 2, a binary signal may be generated by using a comparator to determine the level of the received signal using a certain threshold value.

FIG. 3 is a diagram schematically showing the configuration of the decoder 5. In FIG. 3, the demodulator 4 and the communication path 3 are also shown. The demodulator 4 includes a demodulation circuit 4a that demodulates a signal applied from the communication path 3, and an analog / digital conversion circuit 4b that converts an analog demodulated signal generated by the demodulation circuit 4a into a digital signal.
Output data (encoded data) Xn of the analog / digital conversion circuit 4b is applied to the decoder 5.

  The encoded data Xn given to the decoder 5 is L-value (L ≧ 2) data. Hereinafter, since the encoded data Xn is multilevel quantized data, it is referred to as a symbol. The decoder 5 performs a decoding process on the input symbol Xn sequence according to a decoding method such as a sum-product decoding method or a min-sum decoding method to generate decoded bits Cn as decoded data.

The decoder 5 includes a log likelihood ratio calculation unit 6 that generates a log likelihood ratio λn of the demodulated symbol Xn from the demodulator 4.
The log likelihood ratio calculation unit 6 generates a log likelihood ratio λn independently of the noise information of the received signal. Normally, when noise information is taken into consideration, this log likelihood ratio λn is given by Xn / (2 · σ · σ). Here, σ represents noise variance.
However, in the present embodiment, the log likelihood ratio calculation unit 6 is formed by a buffer circuit or a constant multiplier circuit, and the log likelihood ratio λn is given by Xn · f. Here, f is a non-zero positive number. Further, in the min-sum decoding method, since the calculation is performed using the minimum value in the decoding process (row process) based on the parity check matrix, linearity is maintained in the signal processing. For this reason, processing such as normalization of output data according to noise information is unnecessary. In this case, by calculating the log-likelihood ratio without using noise information, the circuit configuration is simplified and the calculation process is also simplified.

  In addition, the decoder 5 includes a row processing unit 9 that performs row processing of the parity check matrix and a column processing unit 10 that performs column processing of the parity check matrix.

When the decoding method is the sum-product decoding method, the row processing unit 9 and the column processing unit 10 perform arithmetic processing according to the following equations (1) and (2), and each element (non- The processing (row processing) for the zero element) and the processing (column processing) for each element (non-zero element) for the column are repeatedly executed.
Specifically, the row processing unit 9 performs an operation of calculating the external value logarithmic ratio (first variable) αmn according to the following equation (1), and the column processing unit 10 performs the prior value according to the following equation (2). An operation for calculating the log ratio βmn is performed.

Here, in each of the above formulas (1) and (2), n′εA (m) \ n and m′εB (n) \ m mean elements other than themselves.
For the external value log ratio αmn, n ′ ≠ n, and for the prior value log ratio βmn, m ′ ≠ m. Further, the subscript “mn” indicating the position in the matrix of α and β is usually indicated by a subscript, but in this specification, it is indicated by “horizontal characters” for the sake of readability.
In Equation (1), f is a Gallager f function.

The function sign (x) is defined by the following equation (3).

In addition, the sets A (m) and B (n) have a set [1, N] = {1, 2, when the binary M · N matrix H = [Hmn] is a parity check matrix of the LDPC code to be decoded. .., N}.
A (m) = {n: Hmn = 1} (4)
B (n) = {m: Hmn = 1} (5)

  That is, the subset A (m) means a set of column indexes where 1 (non-zero element) stands in the m-th row of the parity check matrix H, and the subset B (n) A set of row indexes where 1 (non-zero element) stands in the n-th column is shown.

  Specifically, consider the parity check matrix H shown in FIG. In the parity check matrix H shown in FIG. 4, “1” stands in the first to third columns of the first row, “1” stands for the third and fourth columns of the second row, and “1” stands in the fourth column to the sixth column of the three rows. Therefore, in this case, the subset A (m) is as follows.

A (1) = {1, 2, 3}
A (2) = {3,4}
A (3) = {4, 5, 6}

Similarly, the subset B (n) is as follows.
B (1) = B (2) = {1}
B (3) = {1, 2}
B (4) = {2,3}
B (5) = B (6) = {3}

  In the parity check matrix H, when a Tanner graph is used, the connection relationship between a variable node corresponding to a column and a check node corresponding to a row is indicated by “1”. This is referred to as “1” stands ”in this specification. That is, as shown in FIG. 5, the variable nodes 1, 2, and 3 are connected to the check node X (first row), and the variable nodes 3 and 4 are connected to the check node Y (second row). The variable nodes 4, 5, and 6 are connected to the check node Z (third row). This variable node corresponds to a column of the check matrix H, and check nodes X, Y, and Z correspond to each row of the check matrix H. Therefore, the parity check matrix shown in FIG. 4 is applied to a code having a code length of 6 bits in total including 3 information bits and 3 redundant bits.

  In the LDPC parity check matrix H, the number of “1” s is small, and the parity check matrix is a low density, thereby reducing the amount of calculation.

  Each condition probability P (Xi | Yi) is propagated between the variable node and the check node, and a plausible code is determined for each variable node according to the MAP algorithm. Here, the conditional probability P (Xi | Yi) indicates the probability of being Xi under the condition of Yi.

Returning to FIG. 3, the decoder 5 includes a storage unit 11 that stores the external value logarithmic ratio αmn that is the calculation result of the row processing unit 9 and the prior value logarithm ratio βmn that is the calculation result of the column processing unit 10. .
The row processing unit 9 acquires the prior value logarithmic ratio βmn (initial value is 0) from the storage unit 11, and performs row processing calculation based on the above equation (1) from the acquired βmn and the log likelihood ratio λn. . The row processing unit 9 outputs the external value log ratio αmn, which is the calculation result of the row processing, to the storage unit 11 instead of directly supplying it to the column processing unit 10. The external value logarithmic ratio αmn stored in the storage unit 11 is updated by the external value logarithmic ratio αmn output from the row processing unit 9.

  The column processing unit 10 acquires the external value logarithmic ratio αmn from the storage unit 11, and performs column processing calculation based on the above equation (2) using the acquired αmn. The column processing unit 10 outputs the calculation result of the column processing to the storage unit 11 instead of directly giving it to the row processing unit 9. The prior value log ratio βmn stored in the storage unit 11 is updated by the prior value log ratio βmn output from the column processing unit 9.

  The decoder 5 includes a loop determination unit 12 that determines the end of repetition of decoding operations including row processing and column processing. The determination unit 12 determines whether or not the number of iterations of row processing and column processing has reached the end count, and when the number of iterations of row processing and column processing reaches the end count, ends the iteration of the decoding operation. .

Further, the determination unit 12 has a function of determining a code using the external value log ratio αmn and the log likelihood ratio λn after the repetition of the decoding operation.
Specifically, the determination unit 11 calculates Qn according to the following equation (6).

Further, the determination unit 11 calculates the estimated code Cn according to the following equation (7).

Now, as shown in FIG. 3, the row processing unit 9 performs row processing for any one row of the parity check matrix and calculates the external value log ratio αmn for the non-zero elements included in the row. A plurality of row calculation units 9a and 9b are provided. In this embodiment, the row calculation units 9a and 9b are not provided for the number of rows of the parity check matrix used for the decoding process, but are provided with a number smaller than the number of rows of the parity check matrix.
That is, the row processing that can be performed simultaneously by the row processing unit 9 is only for some of the plurality of rows of the parity check matrix, and is configured as a partial row processing unit. In the present embodiment, row processing is performed on all rows of the parity check matrix by executing partial row processing serially.
In the present embodiment, a plurality of rows that can be processed simultaneously by the row processing unit 9 are referred to as “row blocks”.

  Here, a parity check matrix H shown in FIG. 6A is assumed as a parity check matrix. The parity check matrix H is 6 rows × 12 columns. The row processing unit 9 of FIG. 3 is provided with a first row calculation unit 9a and a second row calculation unit 9b, and can perform partial row processing of two rows at the same time. Therefore, the row processing unit 9 can perform row processing for all rows (six rows) of the check matrix H by executing the partial row processing three times.

Further, as shown in FIG. 3, the column processing unit 10 also performs column processing on an arbitrary column of the parity check matrix to calculate a prior value log ratio βmn for the non-zero elements included in the column. A plurality of column calculation units 10a and 10b are provided. The column calculation units 10a and 10b are not provided as many as the number of columns of the parity check matrix used for the decoding process, but are provided with a number smaller than the number of columns of the parity check matrix.
That is, the column processing that can be performed simultaneously by the column processing unit 9 is only for some of the plurality of columns of the parity check matrix H, and is configured as a partial column processing unit. In the present embodiment, column processing is performed on all columns of the parity check matrix by executing partial column processing serially.

  The column processing unit 10 of FIG. 3 is provided with a first column calculation unit 10a and a second column calculation unit 10b, and can perform partial column processing of two columns at the same time. Therefore, the column processing unit 10 can perform column processing for all columns (12 columns) of the parity check matrix H shown in FIG. 6A by executing the partial row processing six times.

When the row processing unit 9 and the column processing unit 10 as described above perform the row processing and column processing based on the parity check matrix H shown in FIG. 6A according to the order of the rows and columns, FIG. As shown in b), it takes 9 clocks.
That is, when executing row processing and column processing according to the order of row and column arrangement of the check matrix H, first, partial row processing of the first two rows (row block A in FIG. 6A) is performed. The partial row processing is sequentially performed for the next two rows (row block B in FIG. 6A) and the last two rows (row block C in FIG. 6A). , Column processing can be performed. In the column processing, first, the partial column processing of the first two columns (column block (1) in FIG. 7A) is performed, and the partial column processing for each two columns is sequentially performed in the last two columns (FIG. 6A ) To column block (6)). The above is one cycle of row processing and column processing, and it takes 9 clocks per cycle. The repetition loop of this cycle is repeated until it is determined by the loop determination unit 12 to end.

  On the other hand, the decoder 5 of this embodiment includes a control unit 14 for controlling the order of rows (row blocks) and / or columns (column blocks) to be processed in row processing and / or column processing. The row processing and / or the column processing can be performed in an order different from the order of the rows and columns of the parity check matrix H.

FIG. 7A shows a first replacement parity check matrix H _{1 in} which the arrangement of the rows of the parity check matrix H shown in FIG. Note that the parity check matrix H ₁ is obtained by replacing only the rows of the parity check matrix H, and the columns are not replaced. The first permutation check matrix H ₁ is obtained by replacing the arrangement of the rows of the check matrix H according to the row conversion correspondence table between the check matrix H and the first permutation check matrix H ₁ shown in FIG. Note that if only the order of rows to be processed is changed in row processing, the decoding characteristics are not affected. That is, the parity check matrix H and the first replacement parity check matrix H ₁ are equivalent in terms of decoding characteristics. Even when the column order is changed, the decoding characteristic does not change if the column processing result is returned to the order of the received signal sequence to be decoded (that is, the order of the columns of the check matrix H).

Focusing on the column block (1) portion of the row block C at the lower left corner of the _first permutation check matrix H ₁ shown in FIG. 7A, the column block (1) portion of the row block C contains zero elements. However, there is no non-zero element (“1”). On the other hand, the row blocks A and B of the column block (1) include non-zero elements. Therefore, in order to perform the column processing for the column block (1), the row processing for the row blocks A and B needs to be completed, but the row processing for the row block C does not need to be completed. . That is, when the row processing for the row blocks A and B is completed, the column processing for the column block (1) can be started.

  FIG. 7B shows the processing order when the row processing and the column processing are partially parallelized using this, and the row processing execution of the row block C and the column of the column block (1) are shown. By executing processing in parallel, the time required for one cycle of row processing and column processing can be reduced to 8 clocks.

The control unit 14 outputs a command for causing the row processing unit 9 and the column processing unit 10 to execute row processing and column processing in the order according to FIG. Specifically, the control unit 14 causes the row processing unit 9 to perform row processing according to the row arrangement of the check matrix H ₁ and to perform column processing according to the row arrangement of the check matrix H ₁ .

More specifically, the control unit 14 causes the row processing unit 9 to first execute row processing for the row block A of the parity check matrix H ₁ . In view of the check matrix H, the row processing for the first row and the fourth row is performed first.

That is, the control unit 14 designates, in the row processing unit 9, addresses at which the values of βmn for the first and fourth non-zero elements of the check matrix H are stored. The row processing unit 9 acquires the value of βmn from the storage unit 11 using the address. Then, the row processing unit 9 also calculates αmn for the non-zero elements in the first and fourth rows of the parity check matrix H using the value of λn, according to Equation (1).
Furthermore, the control unit 14 designates, in the row processing unit 9, addresses at which αmn for the non-zero elements in the first and fourth rows of the check matrix H are stored. The row processing unit 9 writes the calculated αmn in the storage unit 11 according to the address. Thereby, the value of the storage unit 11 for the αmn is updated.

Similarly, the control unit 14 causes the row processing unit 9 to execute row processing for the row block B of the parity check matrix H ₁ . In view of the check matrix H, this means that row processing is performed for the sixth and third rows. Further, the control unit 14 causes the row processing unit 9 to execute row processing for the row block C of the check matrix H ₁ . In view of the check matrix H, this means that row processing is performed for the fifth and second rows.

In addition, the control unit 14 causes the column processing unit 10 to start column processing at the same time as causing the row processing unit 9 to execute row processing for the row block C of the check matrix H ₁ .
That is, the control unit 14, the column processing unit 10, in parallel with the row processing of the row block C of the check matrix H _1, to execute sequence processing of column blocks of the check matrix H _{1 (1).} Since column replacement is not performed in the parity check matrix H ₁ , the column processing for each column block of the parity check matrix H ₁ and the column processing for each column block of the parity check matrix H are substantially the same. Is equivalent.

At the time of column processing, the control unit 14 causes the column processing unit 10 to determine the value of αmn for the non-zero elements of the column block (1) including the first column and the second column of the check matrix H (check matrix H ₁ ). The stored address of the storage unit 11 is designated. The column processing unit 10 acquires the value of αmn from the storage unit 11 using the address, and the non-zero elements of the first column and the second column of the check matrix H (check matrix H ₁ ) according to the equation (2). Βmn of each is calculated.
The control unit 14 further designates, in the column processing unit 10, addresses at which βmn is stored for the non-zero elements in the first and second columns of the check matrix H (check matrix H ₁ ) in the storage unit 11. The column processing unit 10 writes each calculated βmn in the storage unit 11 according to the address. By this. The value of the storage unit 11 for the βmn is updated.

However, since the positions of the non-zero elements included in each column are different between the check matrix H and the check matrix H ₁ , the column processing unit 10 acquires the value of βmn from the storage unit 11 or the value of αmn is stored in the storage unit. When the data is written in the memory 11, the storage unit 11 is accessed while corresponding to the difference in the positions of the non-zero elements accompanying the replacement of the rows.
Note that the storage unit 11 of the present embodiment stores values of αmn and βmn according to the arrangement of non-zero elements in the check matrix H ₁ . This point will be described later.

  When the column processing for the column block (1) is completed, the control unit 14 causes the column processing unit 10 to perform column processing for the remaining column blocks (2) to (6) in the same manner as described above.

When row processing is performed according to the _first permutation check matrix H ₁ shown in FIG. 7, the time required for one cycle of row processing and column processing is shortened as described above, and βmn or αmn, which is the processing result, is converted into the received signal sequence. In addition, there is an advantage that processing for rearranging them is unnecessary. That is, since the arrangement of the columns of the check matrix corresponds to the arrangement of the received signal sequences, if the columns are exchanged, finally, it is necessary to exchange the processing results of the arrangement of the received signal sequences, and processing delay may occur. However, in the parity check matrix H ₁ , there is no permutation of columns, so that processing delays associated with permutation are avoided.

However, if processing delays associated with rearrangement are not a problem, not only rows but also columns may be replaced. FIG. 9 shows a second replacement parity check matrix H _{2 in} which the rows and columns of the parity check matrix H shown in FIG. 6 are replaced. This second permutation parity check matrix H ₂ is obtained by exchanging the arrangement of the rows of the parity check matrix H according to the row conversion correspondence table between the parity check matrix H and the second permutation parity check matrix H ₂ shown in FIG. According to the column conversion correspondence table between the parity check matrix H and the second permutation parity check matrix H ₂ shown in (b), the arrangement of the columns is also changed.

In the second parity check matrix H ₂ shown in FIG. 9A, in addition to the column block (1) of the row block C at the lower left corner, the column block (6) of the row block A at the upper right has There are only zero elements. Therefore, in order to perform the row processing for the row block A, it is not necessary to complete the column processing for at least the column block (6). That is, when the column processing for the column blocks (1) to (5) is completed, the row processing for the row block A can be started without completing the column processing for the column block (6).

FIG. 9B shows the processing order when the row processing and the column processing are partially parallelized using this, and the row processing execution of the row block C is performed in the same manner as the check matrix H _1. In addition to performing column processing of the column block (1) in parallel, the column processing execution of the column block (6) and the row processing execution of the row block A can be performed in parallel. Therefore, compared with the check matrix H, the speed can be increased by 2 clocks.

FIG. 11 shows details of the configuration related to the storage unit 11 and the storage unit 11. In the following, a case will be described in which the row and column order of the first permutation check matrix H ₁ is followed as control of the order of rows or columns controlled by the control unit 14.

As shown in FIG. 11, the storage unit 11 includes a storage unit 11a having an external value logarithmic ratio αmn and a storage unit 11b having a prior value logarithmic ratio βmn.
Each of the storage units 11a and 11b includes a semiconductor storage device, and includes a plurality of storage devices 21 to 22, 31 to 34 that can store a plurality of data for one entry. Hereinafter, each “storage device” is simply referred to as “memory”.
Since each memory has only one entry, it is not possible to access (read or write) a plurality of data stored in one memory at the same time, and only one data can be accessed at the same time. is there.
However, a plurality of entries can be accessed simultaneously.

  The βmn storage unit 11b employs a configuration suitable for row processing computation because βmn is used for row processing computation. Specifically, in response to the row processing unit 9 having two row calculation units 9a and 9b, the βmn storage unit 11b has two memory groups 11b-1 and 11b-2. Yes.

The first memory group 11b-1, of the row of the check matrix H _1, the row (specifically first row calculation unit 9a plays the execution, the first row of the check matrix H _1, 3 row, fifth row In the parity check matrix H, βmn corresponding to a non-zero element (“1”) included in the first, sixth, and fifth rows) is stored.
Second memory group 11b-2, among the rows of the check matrix H _1, the row (specifically second row calculator 9b is responsible for execution, the second row of the check matrix H _1, 4 row, six rows In the parity check matrix H, βmn corresponding to the non-zero element (“1”) included in the fourth, third, and second rows) is stored.

Each of the memory groups 11b-1 and 11b-2 in the βmn storage unit 11b has a number (= 4) of memories according to the row weight (the number of non-zero elements included in each row) of the check matrix H ₁ (check matrix H). (Storage device). In the check matrix H ₁ (check matrix H), the row weight of each row is constant (= 4).

The memories 21 to 28 constituting each of the memory groups 11b-1 and 11b-2 of the βmn storage unit 11b correspond to the row calculation units 9a and 9b in charge of row processing of three rows, respectively. One data can be stored.
That is, “address 1” of “memory 1” 21 to “memory 4” 24 configuring the first memory group 11b-1 includes βmn corresponding to the non-zero element included in the first row of the check matrix H ₁ . Similarly, the value of βmn in the third row is stored in “Address 2”, and the value of βmn in the fifth row is stored in “Address 3”.
Further, “address 1” of “memory 5” 25 to “memory 8” 28 configuring the second memory group 11b-2 includes βmn corresponding to the non-zero element included in the second row of the check matrix H ₁ . Similarly, the value of βmn in the fourth row is stored in “Address 2”, and the value of βmn in the sixth row is stored in “Address 3”.
In FIG. 11, βmn is represented by a coordinate format display “(row, column)” indicating the position of the non-zero element in the check matrix H ₁ . The same applies to αmn.

As shown in FIG. 11, the Betamn storage unit 11b, since with Betamn accordance with the arrangement of non-zero elements in the check matrix H ₁ is stored, Betamn row to be executed simultaneously are stored in the same address, When the row processing unit 9 reads (acquires data) from the βmn storage unit 11b, it is sufficient to specify one address of the βmn storage unit 11b.
That, Betamn necessary for performing the row process of row block A consisting of the first and second rows of the check matrix H _1, because they are stored in the address 1 of the memory 1 to the memory 8 of Betamn storage unit If “address 1” is designated for all eight entries in the βmn storage unit 11b, the row processing unit 9 can obtain βmn in the first and second rows of the check matrix H ₁ at a stroke, and calculate the first row. The unit 9a and the second row calculation unit 9b can perform row processing at the same time.

For the row block B consisting of the third and fourth rows of the parity check matrix H ₁ , “address 2” may be designated, and for the row block C consisting of the fifth and sixth rows of the parity check matrix H _1. May specify “address 3”.

  The αmn storage unit 11a employs a configuration suitable for column processing calculation because αmn is used for column processing calculation. Specifically, corresponding to the fact that the column processing unit 10 has two row calculation units 10a and 10b, the αmn storage unit 11a has two memory groups 11a-1 and 11a-2. Yes.

The first memory group 11a-1 of the αmn storage unit 11a includes columns that are executed by the first column calculation unit 10a among the columns of the parity check matrix H ₁ (specifically, the first column 3 and the third column 3 of the parity check matrix H ₁ ). Column, 5th column, 7th column, 9th column, 11th column) for storing αmn corresponding to a non-zero element (“1”).
second memory group 11a-2 of αmn storage unit 11a, among the rows of the check matrix H _1, the row (specifically second row calculation unit 10b is responsible for the execution, the second column of the check matrix H _1, 4 Column, 6th column, 8th column, 10th column, 12th column) for storing αmn corresponding to a non-zero element (“1”).

Each of the memory groups 11a-1 and 11a-2 in the αmn storage unit 11a has a number (= 2) corresponding to the column weight (the number of non-zero elements included in each column) of the check matrix H ₁ (check matrix H). It has a memory (storage device). In the check matrix H ₁ (check matrix H), the column weight of each column is constant (= 2).

The memories 31 to 34 constituting the memory groups 11a-1 and 11a-2 of the αmn storage unit 11a correspond to the column calculation units 10a and 10b in charge of column processing of six columns, respectively. , Six data can be stored.
That is, “address 1” of “memory 1” 31 and “memory 2” 32 configuring the first memory group 11a-1 includes αmn corresponding to the non-zero element included in the first column of the check matrix H ₁ . Similarly, the value of αmn in the third column is stored in “Address 2”, the value of αmn in the fifth column is stored in “Address 3”, and the seventh column is stored in “Address 4”. The αmn value of the ninth column is stored, the αmn value of the ninth column is stored in “Address 5”, and the αmn value of the eleventh column is stored in “Address 6”.

Further, “address 1” of “memory 3” 33 and “memory 4” 34 configuring the second memory group 11a-2 includes αmn corresponding to the non-zero element included in the second column of the check matrix H ₁ . Similarly, the value of αmn in the fourth column is stored in “Address 2”, the value of αmn in the sixth column is stored in “Address 3”, and the eight columns are stored in “Address 4”. The αmn value of the 10th column is stored in “Address 5”, and the αmn value of the 12th column is stored in “Address 6”.

As described above, the αmn storage unit 11a stores αmn in accordance with the arrangement of the non-zero elements in the check matrix H ₁ and also stores αmn of columns to be executed at the same address at the same address. When the unit 10 reads (acquires data) from the αmn storage unit 11a, it is sufficient to designate one address of the αmn storage unit 11a.
That, Arufamn necessary for performing the column process of column block (1) consisting of first and second columns of the check matrix H ₁ is stored in the address 1 of the memory 1 to the memory 4 of Arufamn storage unit 11a Therefore, if “address 1” is designated for all four entries in the αmn storage unit 11a, the column processing unit 9 can acquire αmn in the first column and the second column of the check matrix H ₁ at a stroke, and The first column calculation unit 10a and the second column calculation unit 10b can perform column processing at the same time.

For the column block (2) consisting of the third and fourth columns of the parity check matrix H ₁ , “address 2” may be designated, and the column block consisting of the fifth and sixth columns of the parity check matrix H _1. For (3), “address 3” may be designated, and for the column block (4) consisting of the seventh and eighth columns of the parity check matrix H ₁ , “address 4” may be designated. For the column block (5) consisting of the 9th and 10th columns of H ₁ , “address 5” may be specified, and for the column block (6) consisting of the 11th and 12th columns of the check matrix H _1. May specify “address 6”.

Now, as described above, the αmn storage unit 11a and the βmn storage unit 11b of the storage unit 11 of the present embodiment can read data in accordance with the procedure of row processing and column processing, so that αmn and βmn Holding.
On the other hand, for data writing, the output of the row calculation blocks 9a and 9b does not directly correspond to the entry of the αmn storage unit 11a, and directly corresponds to the entry of the column calculation blocks 10a and 10b and the βmn storage unit 11b. Therefore, it is necessary to select which entry the calculation result is given to.
In addition, since only one data can be simultaneously written in one memory, it may be necessary to write a plurality of calculation results in one memory at the same time, so timing adjustment is also necessary.

  Therefore, in the present embodiment, as shown in FIG. 11, the first selection unit 17 is provided between the output of the row processing unit 9 and the entry of the αmn storage unit 11a, and the output of the column processing unit 10 and the βmn storage unit. The second selection unit 18 is provided between the entries of 11b, and these selection units 17 and 18 are controlled by the control unit 14. Then, when the selection units 17 and 18 are appropriately controlled by the control unit 14, the outputs of the row calculation blocks 9 a and 9 b and the column calculation blocks 10 a and 10 b can be appropriately written in the storage unit 11.

  FIG. 12 shows details of the first selection unit 17. The first selection unit 17 has a number (= 4) of multiplexers M1 to M4 corresponding to the number of memory entries in the memories 31 to 34 of the αmn storage unit 11a. Specifically, the first selection unit 17 includes a first multiplexer M1 connected to output data to the “memory 1” 31 and a second multiplexer connected to output data to the “memory 2” 32. M2, a third multiplexer M3 connected to output data to the “memory 3” 33, and a fourth multiplexer M4 connected to output data to the “memory 4” 34.

The input sides of the multiplexers M1 to M4 are connected to the outputs of the first and second row calculation units 9a and 9b as necessary.
Here, as shown in FIG. 12, the first and second row calculation units 9a and 9b have four outputs 9a-1 to 9a-4 and 9b-5 to 9b-8, respectively. The first output 9a-1 of the first row calculation unit 9a outputs αmn corresponding to the non-zero element having the same coordinates as βmn stored in the “memory 1” 21 of the βmn storage unit 11b as the row calculation result. . That is, when the first row calculation unit 9a performs the row processing of the first row, the “memory 1” 21 stores the value of βmn for (1, 12) = 1 row and 12th column. The 1-row calculation unit 9a calculates the value of αmn for (1, 12) = 1 row and 12th column using the values of the other memories 22 to 24, and outputs the αmn.

Similarly, the second output 9a-2 of the first row calculation unit 9a outputs αmn corresponding to βmn stored in the “memory 2” 22 of the βmn storage unit 11b as the row calculation result. The third output 9a-3 of the calculation unit 9a outputs αmn corresponding to βmn stored in the “memory 3” 23 of the βmn storage unit 11b as the row calculation result, and the fourth output of the first row calculation unit 9a. Output 9a-4 outputs αmn corresponding to βmn stored in the “memory 4” 24 of the βmn storage unit 11b as a row calculation result.
The same applies to the fifth output 9b-5 to the eighth output 9b-8 of the second row calculation unit 9.

  Of the outputs 9a-1 to 9a-4 and 9b-5 to 9b-8, the third output 9a-3, the fourth output 9a-4, and the sixth output 9b are connected to the input side of the first multiplexer M1. -6 and the seventh output 9b-7 are connected. This is because the “memory 1” 31 of the αmn storage unit 11a to which the output of the first multiplexer M1 is connected is (1,1), (2,3), (4,5), (4,7), It is an area for storing the value of αmn for the non-zero elements of (3, 9), (1, 11), and the output of these αmn is the four outputs 9a-3, 9a- This is because 4, 9b-6 and 9b-7.

From the same viewpoint, necessary outputs among the outputs 9a-1 to 9a-4 and 9b-5 to 9b-8 are also connected to the input sides of the second to fourth multiplexers M2 to M4. As described above, in the present embodiment, since only necessary outputs are connected to the multiplexer, the number of wirings can be reduced.
Note that all the outputs 9a-1 to 9a-4, 9b-5 to 9b-8 may be connected to each multiplexer. In this case, a general-purpose circuit configuration that is not affected by the arrangement of αmn and βmn in the storage unit 11 is obtained.

When the row processing unit 9 writes the row processing calculation result in the αmn storage unit, the control unit 14 selects which input is to be output to each of the multiplexers M1 to M4 of the first selection unit. Signals C1 to C4 are output.
The selection signals C1 to C4 are generated based on the schedule data 14a that the control unit 14 has. FIG. 13 shows an example of schedule data when the row processing unit 9 writes the row processing calculation result in the αmn storage unit.

In the schedule data of FIG. 13, “coordinates” indicate the coordinates of non-zero elements in the check matrix H ₁ . “Time” indicates the time at which the row processing is performed for the non-zero element of the coordinate, and corresponds to “Time” in FIG. The “memory number” indicates the number of the memories 1 to 4 in the αmn storage unit 11 in which the value of αmn, which is the row processing calculation result for the non-zero element indicated by “coordinates”, is written. “Memory address” indicates the address of the memory in which the value of αmn, which is the result of the row processing calculation for the non-zero element indicated by “coordinates”, is written. “Switching number” indicates a multiplexer input number (1 to 4 or 1 to 5) selected by the multiplexer. Since the memories 31 to 34 and the multiplexers M1 to M4 correspond one-to-one, the multiplexer to which the “switching number” is to be given is specified by the “memory number”.

As shown in FIG. 13, at the time “1” when the row processing for the row block A composed of the first row and the second row of the parity check matrix H ₁ is performed, for example, αmn of the coordinates (1, 1) is It should be written to “memory address 1” of “memory 1” (= memory number: 1) of the αmn storage unit 11a. As is apparent from FIGS. 11 and 12, αmn of the coordinates (1, 1) is output from the third output 9a-4 of the first row calculation unit 9a and given to the first input of the first multiplexer M1. It has been.
Therefore, the selection signal C1 provided to the first multiplexer M1 may be “1” for selecting the first input, and this “1” is the “switching number” for the coordinates (1, 1). Is registered in the schedule data 14a of FIG.

In the schedule data 14a of FIG. 13, “switching numbers” for writing to the αmn storage unit 11a are registered in the same way for αmn of other coordinates.
The control unit 14 generates selection signals C1 to C4 to the first to fourth multiplexers M1 to M4 for each “time” according to the schedule data 14a, and supplies the selection signals C1 to M4 to the multiplexers M1 to M4.

However, since the schedule data example in FIG. 13 is simple, for example, at the time “1” when the row block A including the first row and the second row of the check matrix H ₁ is processed, the “memory number” Writing to the “memory 1” 31 specified by = 1 is required three times.
In addition, at time “2” when the row block B including the third row and the fourth row of the check matrix H ₁ is processed, writing to the “memory 2” 32 specified by “memory number” = 1 is 3 Is required.

As described above, when writing to the same memory is necessary at the same “time”, the selection signals C1 of the multiplexers M1 to M4 are sequentially performed according to a clock obtained by subdividing the “time”. The output timing of .about.C4 may be shifted. In this case, processing delay for memory writing occurs. In order to avoid the occurrence of this processing delay, it suffices to devise which address of which memory each αmn value is placed, and if appropriate schedule data is determined according to the memory arrangement, Processing delay can be avoided.
If the memory layout of αmn is different from that shown in FIG. 11, a selection unit is provided between the βmn storage unit 11b and the row processing unit 9, and schedule data for controlling the selection unit is provided. Just prepare.

The second selection unit 18 is also configured in the same manner as the first selection unit 17, and specifically corresponds to the βmn storage unit 11b including eight memories 21 to 28. And eight multiplexers M11 to M18. The outputs of the multiplexers M11 to M18 are connected to the entries of the memories 21 to 28 of the βmn storage unit 11b. Although detailed wiring between the column processing unit 10 and each of the multiplexers M11 to M18 of the second selection unit is omitted, the outputs of the column calculation units 10a and 10b and the βmn storage are the same as in the first selection unit 17. Wiring is performed according to the relationship with βmn stored in the unit.
In the second selection unit 18 as well, all the outputs of the column calculation units 10a and 10b may be connected to the input sides of the multiplexers M11 to M18. In this case, the versatility of the circuit is expanded.

  The control unit 14 also gives control signals C11 to C18 generated according to schedule data (not shown) to the multiplexers M11 to M18 of the second selection unit 18. As a result, the value of βmn, which is the calculation result of the column processing unit 10, is written to a predetermined address in a predetermined memory of βmn.

  Note that a selection unit may be provided between the αmn storage unit 11a and the column processing unit 10, and schedule data for controlling the selection unit may be prepared.

With the configuration described above, the processing results of the row processing unit 9 and / or the column processing unit 10 are transferred to predetermined addresses in a predetermined memory in the storage unit 9 by the selection units 17 and 18 controlled according to the schedule data. Can write. Further, αmn or βmn required for processing by the row processing unit 9 and / or the column processing unit 10 can be read from a predetermined address in a predetermined memory of the storage unit 9 by a control unit controlled according to the schedule data.
Therefore, by appropriately setting the arrangement of αmn and / or βmn and the schedule data in the storage unit 9, the memory access delay in the storage unit 9 as in the present embodiment can be reduced.

FIG. 14 shows a case where the decoding process is performed according to the row and column arrangement of the first replacement parity check matrix H _{1 in which} only the row arrangement of the parity check matrix H is replaced (example), and the row and column arrangement of the parity check matrix H. The error rate (bit error rate) when the decoding process is performed according to (Comparative example) is shown. As shown in FIG. 14, the error rate is almost the same between the embodiment and the comparative example, and it can be seen that the decoding characteristics are not affected even if the row arrangement is changed as in the embodiment.

The present invention is not limited to the above embodiment, and various modifications can be made without departing from the scope of the invention.
For example, the decoding method is not limited to the sum-product decoding method, and may be a min-sum decoding method.

1 is a diagram schematically showing a configuration of a communication system. It is a figure which shows an example of a response | compatibility with transmission data and demodulation data. It is a figure which shows the structure of a decoder. It is an example of a check matrix. 5 is a Tanner graph of the parity check matrix shown in FIG. (A) shows a check matrix H, and (b) is a timing chart showing a processing process when the rows and columns of the check matrix H follow. (A) shows a check matrix H ₁ , and (b) is a timing chart showing a process revision when the rows and columns of the check matrix H ₁ are aligned. It is a row conversion correspondence table from the check matrix H to the check matrix H ₁ . (A) shows a check matrix H ₂ , and (b) is a timing chart showing a process revision when the rows and columns of the check matrix H ₂ are aligned. (A) is a row conversion correspondence table for converting from the check matrix H to the check matrix H ₂ , and (b) is a column conversion correspondence table. It is explanatory drawing of a memory | storage part and the structure relevant to it. It is explanatory drawing of a 1st selection part and the structure relevant to it. It is a figure which shows the example of schedule data. It is a graph regarding an error rate.

Explanation of symbols

1: encoder, 2: modulator, 3: communication channel, 4: demodulator, 4a: demodulation circuit, 4b: analog / digital conversion circuit, 5: decoder, 6: log likelihood ratio calculation unit, 9: Row processing unit, 9a: first calculation unit, 9b: second calculation unit, 10: column processing unit, 10a: first column calculation unit, 10b: second column calculation unit, 11: storage unit, 11a: αmn storage unit 11b: βmn storage unit, 12: determination unit, 14: control unit, 14a: schedule data, 17: first selection unit, 18: second selection unit, M1 to M8: multiplexer, M11 to M18: multiplexer

Claims (4)

In a parity check decoding apparatus that repeatedly performs row processing and column processing based on a parity check matrix,
A storage unit for storing a calculation result of row processing and a calculation result of column processing;
A row processing unit that performs row processing based on the parity check matrix using the column processing calculation result obtained from the storage unit, and outputs the row processing calculation result to the storage unit;
A column processing unit that performs column processing based on the parity check matrix using the operation result of the row processing acquired from the storage unit, and outputs the operation result of column processing to the storage unit;
A control unit for controlling the decoding process;
With
The row processing unit is configured as a partial row processing unit that performs row processing for a plurality of rows of a part of a parity check matrix,
The column processing unit is configured as a partial column processing unit that performs column processing on a plurality of columns of a part of a parity check matrix,
The control unit controls the order of rows and / or columns to be executed by the partial row processing unit and / or the partial column processing unit, and according to the controlled order, the partial row processing unit and / or Or control access to the storage unit by the subsequence processing unit,
The storage unit
A first storage unit for storing a row processing calculation result by the partial row processing unit;
A second storage unit for storing a column processing calculation result by the partial sequence processing unit;
Have
The first storage unit includes a plurality of storage devices that can store a plurality of row processing calculation results for one entry, and thus has a plurality of entries, and is stored at a designated address for each entry. The row processing calculation result is output to the partial sequence processing unit,
The second storage unit includes a plurality of storage devices that can store a plurality of column processing calculation results for one entry, and thus has a plurality of entries, and is stored at a designated address for each entry. The column processing calculation result is output to the partial row processing unit,
A plurality of row processing calculation results corresponding to non-zero elements included in a plurality of columns simultaneously subjected to column processing by the partial column processing unit are assigned to the same address of a plurality of storage devices constituting the first storage unit. Stored,
A plurality of column processing calculation results corresponding to non-zero elements included in a plurality of rows that are simultaneously subjected to row processing by the partial row processing unit are assigned to the same address of a plurality of storage devices constituting the second storage unit. Stored,
The controller is
When the partial row processing unit acquires a column processing calculation result from the second storage unit, a plurality of non-zero elements included in a plurality of rows in which the partial row processing unit simultaneously executes row processing Designating one address storing the column processing calculation result of the plurality of entries in the second storage unit;
When the partial sequence processing unit acquires a row processing calculation result from the first storage unit, a plurality of non-zero elements included in a plurality of columns in which the partial sequence processing unit simultaneously performs column processing A parity check decoding apparatus characterized by designating one address storing the row processing calculation result for the plurality of entries of the first storage unit . A selection unit for selecting a pre-Symbol partial row processing unit and / or the memory device the subsequence processing unit accesses,
The parity check decoding according to claim 1, wherein the control unit controls access to the storage unit by the partial row processing unit and / or the partial column processing unit by controlling the selection unit. apparatus. The control unit has schedule data that defines when the partial row processing unit and / or the partial column processing unit access which storage device among the plurality of storage devices,
The parity check decoding apparatus according to claim 2, wherein the control unit controls the selection unit based on the schedule data. The control unit controls the order of rows to be executed by the partial row processing unit so that the order is different from the row order in the parity check matrix. The parity check decoding apparatus according to any one of claims 1 to 3, wherein the order is controlled so as to be the same as the order of columns in the parity check matrix.

Images