JP2008167379A - Decoding method, decoding apparatus, and program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a decoding device and a decoding method, and a program that can perform accurate decoding at high speed with less computational complexity and a small circuit scale. <P>SOLUTION: Disclosed is a decoding device 30 which sorts received words according to their reliabilities, performs belief propagation (Belief propagation: BP) using a parity check matrix diagonalized in the order to update the reliabilities, and repeats the operation for the updated values, the decoding device having a belief propagation unit 35 which performs the belief propagation (BP) of the reliabilities (LLR) of the received words. The belief propagation unit 35 performs the belief propagation using only indexes of columns to be updated, necessary rows of the parity check matrix corresponding to the columns, and LLRs of all the columns. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

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

  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 the initial value of Qi, j, and extrinsic information Λ _i ^{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

Incidentally, in the above technique, the maximum number of repetitions It _H of belief propagation (BP) is not particularly count is defined. Moreover, the amount of calculation increases as the number of repetitions increases.
In addition, if the LLR update is performed for all the nodes of the codeword, a considerable amount of computation is required. Particularly, the computation matrix is very large because the submatrix is very dense in nodes other than the diagonalization target column. .
In particular, in a belief propagation (BP) device, both check node operations and variable node operations must be performed, and both require a parity check row and a parity check matrix column. It is difficult to read both from the circuit even in a general memory configuration.

In addition, the message memory requires the number of words of 1 in the parity check matrix. However, since the parity check matrix changes at any time, it is difficult to set a fixed number of memory words, and the number of words is sufficiently large. Attempting to do so further increases the memory.
In the first place, the circuit scale of the variable node arithmetic unit and the message memory itself is large.

  An object of the present invention is to provide a decoding method, a decoding apparatus, and a program capable of performing decoding with high reliability with a small amount of calculation at high speed and with a small circuit scale.

  The first 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. And a BP step for performing reliability propagation (BP) of the reliability (LLR) of the received word with respect to the updated value, and the BP step. In, reliability propagation is performed using only the index of the column to be updated, the essential row of the parity check matrix corresponding to the column, and the LLRs of all the columns.

  Preferably, the BP step performs a check node operation using an input LLR and a parity check row to generate an update message, an LLR of a column to be updated selected by an index of the column to be updated, and the first And a second step of updating the LLR of the update sequence with the update message generated in the step.

  Preferably, in the second step, the LLR is updated only for the diagonalization target column.

  According to a second aspect of the present invention, belief propagation (BP) is performed by using a parity check matrix that is sorted according to the reliability of received words and diagonalized in that order, and the reliability And a reliability propagation unit that performs reliability propagation (BP) of the reliability (LLR) of the received word, the decoding device repeating the above operation again for the updated value, The reliability propagation unit performs reliability propagation using only the index of the column to be updated, the main row of the parity check matrix corresponding to the column, and the LLRs of all the columns.

  Preferably, the reliability propagation unit performs a check node operation using an input LLR and a parity check row to generate an update message, an LLR of a column to be updated selected by an index of the column to be updated, and the first And an update unit that updates the LLR of the update sequence using the update message generated in one step.

  Preferably, the update unit updates the LLR only for the diagonalization target column.

  The third aspect of the present invention is to perform reliability propagation (BP) using a parity check matrix that is sorted according to the reliability of received words and is diagonalized in that order, and the reliability. In the decoding process in which the above operation is repeated again for the updated value, the index of the column to be updated in the BP step for performing reliability propagation (BP) of the reliability (LLR) of the received word, This is a program that causes a computer to execute a process of performing reliability propagation (BP) using only the main row of the parity check matrix corresponding to the column and the LLRs of all the columns.

According to the present invention, a node with high reliability is highly likely not to be wrong, and a node with low reliability is highly likely to be wrong. In addition, the diagonalization target column and the asymmetric column may be interchanged between the two having close reliability, and a node with a considerably high reliability is unlikely to become a diagonalization target column. From the above, LLR update is not performed for nodes other than the diagonalization target column.
In addition, in reliability propagation (BP), when 2n cycles exist on the Tanner graph, if reliability propagation is repeated n times or more, the independence of messages may be lost and performance degradation may occur. . In fact, the parity check matrix is also very dense and has many cycles of n = 2. For this reason, the present invention is configured such that the number of repetitions of reliability propagation (BP) is limited to one.

  According to the present invention, there is an advantage that a highly reliable decoding can be performed at a high speed with a small calculation amount and with a small circuit scale.

  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 as 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 a Reed-Solomon (RS) code, a BCH code, and other linear codes having a parity check matrix that is not low in 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, the specific configuration and function of the sorting device according to the present embodiment will be described.

  FIG. 3 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. 3, the communication system 10 includes an RS encoder 11, an interleaver 12, a convolutional encoder 13, a soft output decoder 14 for a convolutional code, a deinterleaver 15, an ABP iterative decoder 16, and a channel 17. Have.

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. 4 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. 4, 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. 5 is a diagram illustrating a configuration example of a decoding device of an ABP decoder.

  The ABP decoder 30 in FIG. 5 is applicable to the ABP decoder 16 in FIG. 3 and the ABP decoder 21 in FIG. 4, and includes a sort input selector 31, a sort unit 32, a parity check matrix diagonalization unit 33, A reliability (LLR) holding unit 34 and a reliability propagation (BP) unit 35 are included.

In the ABP decoder 30, the reception LLRS 32 is input as an input.
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 reception LLRS 32 for the first time, and selects the update LLRS 40 and its column index S39 after reliability propagation (BP) for the second and subsequent iterations.

As shown in FIG. 5, 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 row S37.
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 decoding method according to the embodiment of the present invention can be applied to the belief propagation (BP) unit 35 of the decoder 30.

  FIGS. 6, 7 and 8 are diagrams illustrating message flows on a Tanner graph of iterative decoding using adaptive belief propagation (ABP) according to an embodiment of the present invention.

In this embodiment, the number of repetitions of belief propagation (BP) is limited to one, and the reliability is updated only for the diagonalization target column.
In FIG. 6, first, an initial value of a message from the variable node node 41 to the check node 42 is determined. The received word ri is set as the initial value. That is, it is given by the following equation.

  Next, the message from the check node 42 to the variable node 41 in FIG. 7 is calculated as follows.

  Finally, in FIG. 8, since the number of repetitions is one, the variable node calculation in the variable node 41 is not performed, and the LLR of each bit is updated. The values for the first column, the third column, and the fifth column, which are diagonalization target columns, are updated and output as the updated values shown below.

  For the second column, the fourth column, and the sixth column that are not the diagonalization target column, the received word ri is output as an updated value as it is.

  As described above, the amount of calculation is reduced, and it is not particularly necessary to perform variable node calculation.

  FIG. 9 is a diagram showing a graph of decoding performance comparison using simulations in the existing method and the method according to the present embodiment.

FIG. 9 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.
In the simulation model concatenated with the convolutional code as shown in FIG. 3, the simulation shows that there is almost no performance degradation due to the present invention as shown in FIG.

  FIG. 10 is a diagram illustrating a configuration example of a reliability propagation (BP) unit of the ABP decoder according to the embodiment of the present invention. FIG. 11 is a diagram illustrating a configuration example of the reliability propagation (BP) unit of the ABP decoder when the decoding method according to the embodiment of the present invention is not applied.

The reliability propagation (BP) unit 35 of FIG. 10 includes an update sequence LLR selection unit 351, a check node calculation unit 352, and an LLR update unit 353.
For example, when RS (204, 188) is assumed, when LLRSs 42 of all 1632 columns are input, the LLRS 87 of the column to be updated is selected by the update column LLR selection unit 351 and the index S41 of the column to be updated.
Further, the check node calculation unit 352 performs check node calculation using the input LLRS 44 and the parity check row S43.
Here, since the variable node to be updated is always a diagonalization target column, there is always only one check node connected to the variable node. That is, all messages arriving at the variable node to be updated are calculated by one line input and LLR input.
Therefore, if the LLR update unit 353 adds the message S45 updated by the check node calculation and the LLRS 44 selected by the update column LLR selection unit 351, that is, the LLR of the update column S41 is updated by performing the following calculation. Be done

  Further, the reliability propagation (BP) unit 35A of FIG. 11 includes an update sequence LLR selection unit 351A, a check node (check node) calculation unit 352A, an LLR update unit 353A, a variable node calculation input selection unit 354, a variable node. A node computing unit 355, a v2c message memory 356, and a c2v message memory 357 are provided.

The update sequence LLR selection unit 351A selects the LLR of the sequence index S81 to be updated from the input S52 having the LLR for the code length.
The variable node computation input selection unit 354 selects the input LLRS 52 for the first iteration of reliability propagation (BP), and selects the message S85 after the check node computation for the second and subsequent iterations.
The v2c message memory 356 functions as a message memory from the variable node to the check node, and the c2v message memory 357 functions as a message memory from the check node to the variable node.

In the reliability propagation (BP) unit 35A of FIG. 11, first, the variable node calculation unit 355 performs variable node calculation using the message after the check node calculation, and outputs an updated message S55.
However, as described above, the update message S55 is set to the input LLRS 52 for the first repetition. After the variable node calculation is completed, a message from the variable node to the check node is output from the v2c message memory 356, and the check node calculation unit 352A performs the check node calculation.
Thereafter, the update message is held in the c2v message memory 357. A message S59 is sent from the c2v message memory 357 to the variable node calculation unit 355.
This is repeated thereafter. After repeating this as many times as the number of repetitions, the LLR update unit 353A updates the LLR using the LLRS 57 and the message S59 to be updated, and outputs them.

  As described above, in the belief propagation (BP) unit 35A of FIG. 11, both the check node operation and the variable node operation must be performed, and both the parity check row and the parity check matrix column are required for both. . In addition, the message memory requires one word number of the parity check matrix.

On the other hand, in the reliability propagation (BP) unit 35 of FIG. 10 according to the embodiment of the present invention, a variable node calculation unit and a message memory are not necessary. Therefore, an increase in circuit scale can be prevented.
Further, since only the parity check row is required and no column is required, the diagonalization unit 33 only needs to output only the parity check row S37 to the reliability propagation (BP) unit 35 as shown in FIG. This is not difficult because of the memory configuration. As a result, the calculation amount is reduced and the operating frequency can be reduced.

As described above, according to the present embodiment, the number of repetitions of reliability propagation (BP) can be suppressed to one time, and the calculation amount can be increased by updating the reliability only to the diagonalization target column. Can be reduced.
In particular, in the apparatus, since the number of repetitions of belief propagation (BP) is one, it is not necessary to perform a variable node operation. As a result, the variable node operation device can be omitted and the circuit scale can be reduced.
Further, it is not necessary to read out the parity check matrix column necessary for the variable node calculation from the diagonalization unit. Further, when the reliability is updated only to the diagonalization target column, the number of check nodes connected to the variable node that updates the LLR is one. Therefore, if the check node calculation update message and the LLR of the column to be updated are directly input to the LLR update unit, the LLR update is completed, and it is not necessary to provide a message memory subsequent to the check node calculation unit.

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 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 showing the 1st flow of the message on the Tanner graph of iterative decoding using adaptive reliability propagation (ABP: adaptive belief propagation) concerning the embodiment of the present invention. It is a figure showing the 2nd flow of the message on the Tanner graph of iterative decoding using adaptive belief propagation (ABP: adaptive belief propagation) concerning the embodiment of the present invention. It is a figure showing the 3rd flow of the message on the Tanner graph of iterative decoding using adaptive reliability propagation (ABP: adaptive belief propagation) concerning the embodiment of the present invention. It is a figure which shows the graph of the decoding performance comparison using the simulation in the existing method and the method which concerns on this embodiment. It is a figure which shows the structural example of the reliability propagation (BP) part of the ABP decoder which concerns on embodiment of this invention. FIG. 11 is a diagram illustrating a configuration example of the reliability propagation (BP) unit of the ABP decoder when the decoding method according to the embodiment of the present invention is not applied.

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, 32A... Sorting unit, 33. 34 ... Reliability (LLR) holding unit, 35 ... Reliability propagation (BP) unit, 351 ... Update sequence LLR selection unit, 352 ... Check node calculation unit, 353 ..LLR update unit, 41 ... Bali Burunodo, 42 ... check node.

Claims (15)

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,
A BP step for performing reliability propagation (BP) of received word reliability (LLR);
In the BP step,
A decoding method for performing reliability propagation using only an index of a column to be updated, a main row of a parity check matrix corresponding to the column, and an LLR of all columns. The BP step includes
A first step of performing a check node operation with an input LLR and a parity check row to generate an update message;
The decoding method according to claim 1, further comprising: an LLR of the column to be updated selected by an index of the column to be updated and a second step of updating the LLR of the update column by the update message generated in the first step. In the second step,
The decoding method according to claim 2, wherein the LLR is updated only for the diagonalization target column. In the second step,
The decoding method according to claim 3, wherein the LLR of the non-diagonalization target column is used as an update value as it is. In the second step,
The decoding method according to claim 2, wherein the LLR is updated by adding the LLR of the selected column to be updated and the update message. In the BP step,
The decoding method according to any one of claims 1 to 5, wherein the reliability propagation is repeated once. 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 reliability propagation unit that performs reliability propagation (BP) of received word reliability (LLR);
The reliability propagation unit is
A decoding apparatus that performs reliability propagation using only an index of a column to be updated, a main row of a parity check matrix corresponding to the column, and an LLR of all columns. The reliability propagation unit is
An arithmetic unit for performing a check node operation by an input LLR and a parity check line and generating an update message;
The decoding device according to claim 7, further comprising: an LLR of the column to be updated selected by an index of the column to be updated and an update unit that updates the LLR of the update column by the update message generated in the first step. The update unit
The decoding apparatus according to claim 8, wherein the LLR is updated only for the diagonalization target column. The update unit
The decoding device according to claim 9, wherein the LLR is output as an update value for the non-diagonalization target column. The update unit
The decoding device according to claim 8, wherein the LLR is updated by adding the LLR of the selected column to be updated and the update message. In the reliability propagation unit,
The decoding device according to any one of claims 7 to 11, wherein the reliability propagation is repeated once. 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 the decoding process that repeats the above operation again,
In the BP step that performs the reliability propagation (BP) of the reliability (LLR) of the received word,
A program that causes a computer to execute a process of performing reliability propagation (BP) using only the index of the column to be updated, the essential row of the parity check matrix corresponding to the column, and the LLRs of all the columns. In the BP step,
A first process for performing a check node operation with an input LLR and a parity check row to generate an update message;
A computer executes a process including an LLR of an updated column selected by an index of an updated column and a second process of updating the LLR of the updated column by an update message generated in the first process. 13 programs In the second process,
The program according to claim 14, wherein the LLR is updated only for the diagonalization target column.

Images