JP2008199308A - Decoding device and decoding method - Google Patents

Abstract

The present invention provides a decoding device and a decoding method capable of reducing the number of quantized bits after the second iteration and thus reducing the circuit scale.
Using a parity check matrix that is sorted according to the reliability of received words and diagonalized in that order, reliability propagation (BP) is performed and the reliability is updated. The decoding device 30 repeats the above operation again for the updated value, and reduces the number of reliability quantization bits thereafter, compared with the number of reliability quantization bits of the received word.
[Selection] Figure 6

Description

  The present invention relates to a decoding apparatus and a decoding method applied to a circuit and a program storage medium for realizing an error correction code technique using an algebraic technique, for example.

  An algebraic geometric code, for example, a Reed-Solomon code or a BCH code as a sub-partial code thereof, is known a decoding method using the algebraic property and having good performance and calculation cost.

For example, if a Reed-Solomon code having a code length n, an information length k, a definition field GF (q) (q = p ^m , p: prime number) and a minimum distance d = n−k is RS (n, k), It is well known that minimum distance decoding (normal decoding) for decoding a decision received word into a code word with a minimum Hamming distance guarantees correction of t error symbols satisfying t <d / 2.

  Also, list decoding (hereinafter referred to as GS list decoding) by Guruswami-Sudan guarantees correction of t error symbols that satisfy t <√nk (see Non-Patent Document 1).

  List decoding (hereinafter referred to as K-V list decoding) by coater-Vardy using soft-decision received words as an extended version of Guruswami-Sudan list decoding is similar to Guruswami-Sudan. Calculation of symbol reliability, (2) extraction of bivariate polynomial interpolation conditions from reliability, (3) interpolation of bivariate polynomial, (4) factorization of interpolation polynomial and creation of decoded word list It is known that it has a higher performance than that of hard decision decoding (see Non-Patent Document 2).

  It is also known that the calculation cost can be reduced to a practical range by re-encoding (see Non-Patent Document 3).

  On the other hand, as a linear code, a low density parity-check code (LDPC code) that can obtain high performance close to the limit performance by iterative decoding using belief propagation (BP) has recently attracted attention. (See Non-Patent Document 4).

  It is theoretically known that belief propagation (BP) used for LDPC codes is generally effective only for linear codes having a low-density parity check matrix, and parity check for Reed-Solomon codes and BCH codes. It is known that reducing the density of a matrix is NP-hard (see Non-Patent Document 5).

  Therefore, it has been considered difficult to apply reliability propagation (BP) to Reed-Solomon codes and BCH codes.

  However, in 2004, reliability propagation to Reed-Solomon codes, BCH codes, and other linear codes having a parity check matrix that is not low density using a parity check matrix that is diagonalized according to the reliability of the received word ( It was introduced by Narayanan et al. (See Non-Patent Document 6) that the application of BP) is effective.

  This technique is called Adaptive Belief Propagation (ABP) decoding. Hereinafter, this ABP decoding method will be described.

  For example, consider a linear code C having a code length n = 6, an information length k = 3, and a coding rate r = 1/2 and having the following 3 × 6 matrix H as a parity check matrix.

  The code space C is expressed as follows.

  Suppose that a code word passes through a certain channel, for example, a BPSK modulation + AWGN channel (Additive White Gaussian Noise channel), and then is received by the receiver as a received word r as follows.

  At this time, the magnitude of each absolute value of the received value represents the reliability of the received word. In other words, numbers are assigned in ascending order of reliability as follows.

  Next, the parity check matrix H is diagonalized in order from the column corresponding to the symbol with low reliability. In this example, the columns corresponding to the symbols with low reliability are the third column, the fifth column, the first column, the fourth or sixth column, and the second column in this order. To do.

If the diagonalization attempt is linearly dependent on the previous diagonalization, it is left as is and diagonalization is attempted on the next rank.
Reliability is updated by reliability propagation (BP) using a new parity check matrix Hnew obtained as a result of diagonalization of the matrix H by rank.

FIG. 1 is a Tanner graph corresponding to the parity check matrix Hnew.
Trust propagation (BP) is achieved by moving messages back and forth along the edges of the Tanner graph.
A node corresponding to each column of the matrix is referred to as a variable node 1, and a node corresponding to each row is referred to as a check node 2.

  The message from the i-th variable node to the j-th check node is Q i, j, the message from the j-th check node to the i-th variable node is Ri, j, and the check node connected to the i-th variable node When the index set is J (i) and the index set of variable nodes connected to the jth check node is I (j), the respective update formulas are as follows.

Here, θ represents a coefficient called a vertical step damping factor, and satisfies the condition of 0 <θ ≦ 1. Rj is set as an initial value of Qi, j, and extrinsic information Λ _j ^{x is} updated by the following equation.

Furthermore, LLRΛ _i ^q of each code bit is updated by the following equation.

Here, α1 represents a coefficient called an adaptive belief propagation damping factor and satisfies the condition of 0 <α1 ≦ 1.
The update of the LLR by the reliability propagation (BP) is repeated until the repetition stop condition prepared in advance is satisfied, for example, until the maximum repetition number It _H is reached.
In addition, the columns for updating the LLR may be performed only for some columns, for example, the columns subjected to diagonalization, without targeting all the columns.

By using the reliability of the LLR updated by belief propagation (BP), that is, by using the magnitude of the absolute value of the LLR as reliability, diagonalization is performed in the order of columns corresponding to symbols with low reliability, Iterative decoding by new reliability propagation (BP) can be performed.
This is called inner iterative decoding. This LLR update is repeated until an inner iterative decoding stop condition SC1 prepared in advance is satisfied.

Further, a plurality of ranks other than the reliability order of the received values are prepared as initial values of the diagonalization priorities of the columns of the parity check matrix. Using a plurality of ranks, iterative inner decoding is performed serially or in parallel.
This is called outer iterative decoding. This LLR update is repeated until the outer repeated decoding stop condition SC2 prepared in advance is satisfied.

The decoder performs decoding using the LLR repeatedly updated by the above ABP (adaptive belief propagation) procedure as an input.
If the target linear code is a Reed-Solomon code, for example, the following can be considered as the iterative decoding stop conditions SC1 and SC2.

(A) H · d == 0 or the number of repetitions t ≧ N,
(B) Successful limit distance decoding or number of repetitions t ≧ N,
(C) Koeter-Vardy soft decision list decoding success or number of iterations t ≧ N.

Here, d = (d ₁ , d ₂ ,..., D ₆ ) is a hard decision result of Λ _i , 1 if d _i = {Λ _i ^q > 0, 0 if Λ _i ^q ≦ 0}, N is a predetermined maximum number of repetitions.
As a decoding method, for example, the following can be considered.

(A) Hard decision decoding (b) Limit distance decoding (c) Koeter-Vardy soft decision list decoding

  FIG. 2 is a flowchart of iterative decoding using the ABP decoding method.

A search is performed in the order of reliability of received words (ST1), and order conversion is performed (ST2).
The parity check matrix is diagonalized according to the converted order (ST3), and reliability propagation (BP) is performed using this parity check matrix (ST4).
Next, the LLR is calculated (ST5), the reliability order of the calculated LLR is searched (ST6), decoding is performed, and the decoded word is added to the list (ST7).
The above processing is repeated until the repeated decoding stop conditions N1 and N2 are satisfied (ST8 and ST9).
Then, one decoded word is selected (ST10).

V. Guruswami, M .; Sudan, Improving decoding of Reed-Solomon and Algebraic-Geometry codes, IEEE Transactions on Information Theory, vol. 45, pp. 1757-1767, 1999 R. Koetter, A .; Vardy, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Information Theory, 2001 R. Koetter, J. et al. Ma, A .; Vardy, A, Ahmed, Effective Interpolation and Factorization in Algebraic Soft-Decoding Decoding of Reed-Solomon codes, Proceedings of ISIT2003 D. MacKay, Good Error-Correcting Codes Based on Very Sparse Matrices, IEEE Transactions on Information Theory, 1999 Berlekamp, R.M. McEliece, H.M. van Tilburg, On the Inherent Intactability of certain coding problems, IEEE Transactions on Information Theory, vol. 24, pp. 384-386, May, 1978). Jing Jiang, K.J. R. Narayan, Soft Decision Decoding of RS Codes Using Adaptive Parity Check Matrices, Proceeding of IEEE International Symposium on Information 4

FIG. 3 is a diagram showing a flow of an ABP decoder assuming RS (204, 188).
After sorting the received words, the parity check matrix is diagonalized with respect to the diagonalization target column 128, and the reliability propagation (BP) is repeated using the diagonalized matrix.

For example, when the received word is quantized and the LLR quantized in the ABP decoder is handled, the received LLR that is repeatedly input for the first time is a column boundary that does not become a column to be diagonalized. Therefore, it is necessary to widen the dynamic range of quantization.
Further, in the reliability propagation (BP), it is necessary to make the quantization step width finer and perform the LLR update with high accuracy.

  As described above, ABP decoding with good performance cannot be realized unless the number of LLR quantization bits is set to be considerably large. However, if the number of quantization bits is large, the circuit scale also increases.

  An object of the present invention is to provide a decoding device and a decoding method capable of reducing the number of quantization bits after the second repetition and thus reducing the circuit scale.

  An aspect of the present invention is to perform reliability propagation (BP) using a parity check matrix that is sorted according to the degree of reliability of received words and diagonalized in that order to update the reliability. A decoding apparatus and method that repeats the above operation again with respect to the updated value, wherein the number of reliability quantization bits after that is smaller than the number of reliability quantization bits of the received word. To do.

According to the present invention, a function for requantizing the LLR is added after the first sorting, and the number of requantized bits is reduced.
As a feature of ABP decoding, for the received LLR that is repeatedly input for the first time, a column boundary that does not become a column to be diagonalized becomes important, so the dynamic range of quantization needs to be widened. In belief propagation (BP), the quantization step width needs to be fine. However, since the LLR near 0 is important, it is not necessary to increase the dynamic range.
Therefore, if the quantization bit number of the reception LLR is increased for the first sort of repetition, the performance is not affected even if the quantization bit number of the LLR is set small after the first repetition of the sort.

  According to the present invention, it is possible to reduce the number of quantization bits after the second repetition, and there is an advantage that the circuit scale can be reduced.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

The decoding apparatus according to the embodiment of the present invention can be applied to a circuit for realizing an error correction code technique using an algebraic technique, for example, an adaptive belief propagation (ABP) decoder.
ABP decoding is a decoding method for Reed-Solomon (RS) codes, BCH codes, and other linear codes having a parity check matrix that is not low density. When a codeword is received from a certain transmission path, the received word is further converted. Update to a reliable value.

  Hereinafter, after describing the positioning of the decoding device on the communication system in ABP decoding, a specific configuration and function of the decoding device according to the present embodiment will be described.

  FIG. 4 is a diagram showing a configuration example of a communication system using an ABP decoder in an error correction system such as a digital signal receiver, for example, a digital television.

  As shown in FIG. 4, the communication system 10 includes an RS encoder 11, an interleaver 12, a convolutional encoder 13, a convolutional code soft-output decoder 14, a deinterleaver 15, and an ABP iterative decoder with known information of an RS code. 16 and channel 17.

In the communication system 10, ABP decoding is performed after soft-output decoding of a convolutional code is performed on a transmission word subjected to RS encoding and convolutional encoding.
The soft output decoding of the convolutional code referred to here is, for example, decoding by the BCJR algorithm or SOVA.
In the ABP decoder 16, after updating the reliability by ABP, post-hard decision limit distance decoding, list decoding, or soft decision list decoding with the soft value as it is input.

FIG. 5 is a diagram illustrating a configuration example of an ABP decoder in which MAP decoding is performed at the subsequent stage.
As shown in FIG. 5, the decoder 20 includes an ABP decoding unit 21, a limit distance (BD) decoding unit 22, a reception reliability (LLR) holding unit 23, and a MAP decoding unit 24.

  In the decoder 20, after the reliability (LLR) is updated by the ABP decoding unit 21, hard decision is performed, and the BD decoding unit 22 performs limit distance decoding, collects the results in a list, and finally, the MAP decoding unit 24. The maximum a posteriori probability (MAP) decoding is performed in FIG.

  FIG. 6 is a diagram illustrating a configuration example of a decoding device of an ABP decoder.

The ABP decoder 30 in FIG. 6 is applicable to the ABP decoder 16 in FIG. 4 and the ABP decoder 21 in FIG. 5, and includes a sort input selection unit 31, a sort unit 32, a parity check matrix diagonalization unit 33, A reliability (LLR) holding unit 34, a reliability propagation (BP) unit 35, a quantization unit 36, and a requantization unit 37 are included.
Note that the re-quantization unit 37, the sort input selection unit 31, and the like constitute a processing unit.

In the ABP decoder 30, for example, a 7-bit reception LLRS 32 is input to the sort input selection unit 31 as an input quantized by the quantization unit 36.
The column index S31 generates and uses values counted up as 0, 1, 2, 3, and so on from the beginning of the code word of the input reception LLR.
The sort input selection unit 31 selects the column index S31 and the quantized reception LLRS 32 for the first time, and after the second and subsequent iterations, selects the updated LLRS 40 and its column index S39 after reliability propagation (BP).

As shown in FIG. 6, when a received word is input, first, the sorting unit 32 sorts column indexes according to the reliability (LLR).
Next, the diagonalization unit 33 diagonalizes the parity check matrix in order from the column corresponding to the symbol with low reliability.
Finally, the value is updated by performing belief propagation (BP) using the diagonalized parity check matrix.
Sorting, diagonalization, and reliability propagation (BP) are performed again on the updated value. The number of repetitions is predetermined, and this is repeated for the number of repetitions.
The LLR holding unit 34 re-quantizes the LLR by the re-quantization unit 37 after the first repetitive sorting, and reduces the number of re-quantization bits (for example, from 7 bits to 5 bits).

  As described above, in the ABP decoder 30 according to the present embodiment, a circuit scale is reduced by adding a function of requantizing the LLR after the first sort of repetition and reducing the number of requantization bits. The

Hereinafter, quantization will be considered.
FIG. 7 is a diagram showing a relationship between received word quantization and LLR in the flow of the ABP decoder.

  First, when the received words are sorted, if the LLR for the column 1632 rearranged based on the LLR is not quantized, as shown in FIG. As it becomes, the size of the LLR increases.

  Here, a case where a received word quantized using a narrow dynamic range A and a wide dynamic range B is input will be considered.

  FIG. 8 is a diagram illustrating the relationship between the diagonalization target column and the non-target column and the LLR when the received word is quantized with the dynamic range A. FIG. 9 is a diagram illustrating the received word quantized with the dynamic range B. FIG. 10 is a diagram illustrating the relationship between the diagonalization target sequence and non-target sequence and LLR in the case where FIG. 10 quantizes the received word in the dynamic range B and further re-quantizes It is a figure which shows the relationship between an object column and LLR.

When considering a system in which received words quantized using the dynamic range A are input, as shown in FIG. 8, after sorting, a column with a large LLR and a diagonalized non-target column after the sorting The size of the LLR is the same.
For this reason, there is a possibility that a reception value that is likely to be erroneous, which was originally scheduled to enter the diagonalization target column, may be included in the diagonalization non-target column, which degrades the performance.
In addition, among the diagonalized non-target columns, a column with a small LLR may be replaced with the diagonalized target column after the second iteration, so it is necessary to determine a column set with a small LLR among the diagonalized non-target columns. There is.
Therefore, as shown in FIG. 9, the received word is quantized using a larger dynamic range B, and the diagonalization target column is obtained even if the column that was scheduled to enter the diagonalization target column is quantized when not quantized. In the case of entering and not quantizing, it is necessary to come to the head of the diagonalization non-target sequence even if the LLR having a small LLR is quantized.

Next, consider reliability propagation (BP).
As shown in FIG. 10, for reliability propagation (BP), it is preferable to increase the number of quantization bits because reliability propagation with high accuracy is possible when the quantization step width is small. What we want to do is an LLR near 0 in particular, so the dynamic range should be narrower and fine quantization only near 0.
Therefore, the number of quantization bits can be reduced as compared with the quantization of the received word.
As described above, according to the present embodiment, since the number of quantization bits different depending on the circuit is allocated, the circuit scale of the ABP decoder can be further reduced.

In FIG. 6, the number of LLR quantization bits in the ABP decoder 30 is shown.
In addition to the received word quantization unit 36, a requantization unit 37 is also arranged before the input of the LLR holding unit 34.

  Until the LLRs of the received words are repeatedly sorted for the first time, the number of quantization bits is increased and the diagonalization target column determined first is accurately selected. After that, the LLR quantization bit number is small. However, 0 is added to the most significant bit of the LLR before the sort input selection unit 31 for the second and subsequent repetitions to match the number of bits after quantization of the reception LLR.

The LLR handled by the belief propagation (BP) has a small number of quantization bits. However, if the selection between the diagonalization target column and the non-diagonal column is made accurate at the beginning, the quantization step width of the LLR near 0 is There are no particular problems with the details.
As a result, the circuit scale is reduced as the number of quantization bits is reduced.
For example, the memory size of the LLR holding unit 34 is reduced. Furthermore, the amount of calculation of the check node calculation in the reliability propagation (BP) is reduced, and the circuit scale of the reliability propagation (BP) unit 35 is also reduced.

FIG. 11 is a diagram showing a simulation model.
The simulation model 40 includes an RS encoder 41, a BPS modulator 42, an AWGN channel 43, a BPSK demodulator 44, and an ABP decoder 45, as shown in FIG.
FIG. 12 is a diagram showing a simulation result.
FIG. 12 is a diagram showing a frame error rate when RS (204, 188) is assumed. The curve indicated by A indicates the decoding performance of the existing method, and the curve indicated by B indicates the present implementation. The form shows the decoding performance of the method.

  Compared with the existing technology, the simulation model 40 as shown in FIG. 11 shows that the performance degradation hardly occurs as shown in FIG.

Note that the method described above in detail can be formed as a program according to the above-described procedure and executed by a computer such as a CPU.
Further, such a program can be configured to be accessed by a recording medium such as a semiconductor memory, a magnetic disk, an optical disk, a floppy (registered trademark) disk, or the like, and to execute the program by a computer in which the recording medium is set.

It is a Tanner graph corresponding to the parity check matrix Hnew. It is a flowchart of iterative decoding using an ABP decoding method. It is a figure which shows one line of the flow for every repetition of an ABP decoding apparatus. It is a figure which shows the structural example of the communication system which used the ABP decoder for error correction systems, such as a digital signal receiver, for example, digital television. It is a figure which shows the structural example of the ABP decoder to which the MAP decoding was attached to the back | latter stage. It is a figure which shows the structural example of the decoding apparatus of an ABP decoder. It is a figure which shows the relationship between quantization of a received word and LLR in the flow of an ABP decoder. It is a figure which shows the relationship between a diagonalization object column and a non-object column, and LLR when a received word is quantized by the dynamic range A. FIG. It is a figure which shows the relationship between a diagonalization object sequence | sequence when a received word is quantized by the dynamic range B, a non-object sequence | arrangement, and LLR. It is a figure which shows the relationship between the diagonalization object sequence | part and non-object sequence | arrangement, and LLR at the time of quantizing a received word with the dynamic range B, and also requantizing. It is a figure which shows a simulation model. It is a figure which shows a simulation result.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 10 ... Communication system, 11 ... RS encoder, 12 ... Interleaver, 13 ... Convolutional encoder, 14 ... Soft output decoder of convolutional code, 15 ... Deinterleaver, 16 ... ABP iterative decoder, 17 ... channel, 20 ... decoder, 21 ... ABP decoder, 22 ... limit distance (BD) decoder, 23 ... reception reliability (LLR) ) Holding unit, 24 ... MAP decoding unit, 30 ... ABP decoder, 31 ... Sort input selection unit, 32 ... Sort unit, 32A, 32B ... Data sort device, 33, 33A ..Diagonalization unit of parity check matrix, 34... Reliability (LLR) holding unit, 35 .. reliability propagation (BP) unit, 36... Quantization unit, 37. Department.

Claims (6)

Using the parity check matrix that is sorted according to the reliability of the received words and diagonalized in that order, the reliability is updated by performing the belief propagation (BP), and the updated value In contrast, a decoding device that repeats the above operation again,
A decoding apparatus comprising: a processing unit that reduces the number of reliability quantization bits after that compared to the number of quantization bits of reliability of a received word. The processor is
The decoding device according to claim 1, wherein the dynamic range of quantization of reliability thereafter is narrower than the dynamic range of quantization of reliability of received words. The processor is
The decoding apparatus according to claim 2, wherein the reliability quantization step width thereafter is made equal to the quantization step width of the reliability of the received word. Using the parity check matrix that is sorted according to the reliability of the received words and diagonalized in that order, the reliability is updated by performing the belief propagation (BP), and the updated value In contrast, a decoding method that repeats the above operation again,
Decoding method that reduces the number of reliability quantization bits after that compared to the number of quantization bits for reliability of received words. The decoding method according to claim 4, wherein the dynamic range of reliability quantization thereafter is narrowed compared to the dynamic range of quantization of reliability of received words. The decoding method according to claim 5, wherein the reliability quantization step width thereafter is made equal to the quantization step width of the reliability of the received word.

Images