JP2009182421A - Decoding method and decoding apparatus - Google Patents

Abstract

The present invention provides a decoding method and a decoding apparatus capable of performing decoding with high performance while suppressing erroneous correction for an irregular LDPC code.
A method for decoding an irregular LDPC code, based on an irregular parity check matrix, performing likelihood calculation in a row direction using likelihood information of a transmission path, and calculating an external value Step S101 for generating, changing the external value based on a row weight of the parity check matrix to generate a corrected external value, and column direction using the corrected external value based on the parity check matrix Step S103 for performing a likelihood calculation and generating a prior value, step S104 for generating a binary temporary estimated word using the likelihood information and the modified external value, and the parity check for the temporary estimated word It has step S105 which performs a parity check based on a matrix, and step S106 which determines whether decoding is performed repeatedly.
[Selection] Figure 3

Description

  The present invention relates to a decoding method for a non-regular LDPC code and a decoding apparatus that performs decoding of a non-regular LDPC code.

  In recent years, LDPC (Low Density Parity Check) codes have attracted attention and are actively studied as error correction codes that can achieve error rate characteristics approaching the Shannon limit. The LDPC code is a linear code defined by a very sparse parity check matrix. A sparse matrix means a matrix with very few non-zero elements in the matrix. FIG. 19 shows an example of a parity check matrix of an LDPC code having 15 rows and 20 columns.

  As shown in FIG. 19, the number of 1s constituting the matrix is 60, which is very small compared to the number 240 of 0s. Therefore, this is called a low density parity check code. One important parameter that determines the decoding performance of an LDPC code is a row weight that determines the number of 1s in the row direction and a column weight that determines the number of 1s in the column direction. The row weight is the number of bits constituting one parity check code (hereinafter referred to as element parity check code), and the column weight is what the one bit is as a constituent bit of the parity check code (hereinafter referred to as element bit). Indicates whether it is used once.

  The parity check matrix in FIG. 19 is an LDPC code with 4 row weights and 3 column weights because the number of 1s in each row is 4 and the number of 1s in each column is 3. As an LDPC code encoding method, generally, a sparse parity check matrix as shown in FIG. 19 is subjected to matrix conversion using a Gaussian elimination method or the like to generate a generator matrix as shown in FIG. In many cases, a method of encoding using a generator matrix is used. However, when this method is used, even if the original parity check matrix is a sparse matrix, the generator matrix generated by performing matrix transformation becomes a dense matrix, which complicates the structure of the encoding circuit. There is a problem that it ends up.

  As a method for solving this problem, a method of constructing a generator matrix and a parity check matrix using a structured matrix has been proposed (for example, see Patent Document 1). In the method described in Patent Document 1, a partial matrix Q as shown in Equation 2 is configured using a square matrix F as shown in Equation 1, and a generator matrix G is configured according to Equation 3.

  Further, the parity check matrix H is constructed according to the equation (4).

When this method is used, the generation matrix G and the parity check matrix H can be defined at the same time, so it is not necessary to perform a sequence conversion for obtaining the generation matrix G, and both matrices are structured together. Since it is in the state, there is an advantage that the structure of the encoding circuit and the decoding circuit is simplified.
JP 2006-1000094 A1

  However, in the conventional encoding method and decoding method, since the generated LDPC code is an irregular LDPC code having different row weights for each row, the probability of occurrence of erroneous correction differs for each row. However, since only the same decoding process is performed for any row, there is a problem that erroneous correction is likely to occur. In addition, there is a problem that the performance of iterative decoding deteriorates due to the influence of the erroneous correction.

  The present invention provides a decoding method and a decoding apparatus that suppress the occurrence of erroneous correction for an irregular LDPC code.

  In order to solve the above-described conventional problem, a decoding method of the present invention is a method for decoding an irregular LDPC code, wherein the likelihood information of a transmission path is obtained based on an irregular parity check matrix. Using the likelihood calculation in the row direction to generate an external value, changing the external value based on the row weight of the parity check matrix to generate a modified external value, and the parity check matrix A likelihood calculation in the column direction using the corrected external value to generate the prior value, and a binary temporary estimated word using the likelihood information and the corrected external value And a step of parity checking the temporary estimated word based on the parity check matrix and a step of determining whether or not to repeatedly perform decoding.

  In addition, the decoding apparatus of the present invention is an apparatus for decoding an irregular LDPC code, and based on an irregular parity check matrix, likelihood calculation is performed in a row direction using likelihood information of a transmission path. External value generation means for generating an external value, modified external value generation means for changing the external value based on a row weight of the parity check matrix to generate a corrected external value, and the parity check matrix A preliminary value generating means for performing likelihood calculation in the column direction using the modified external value and generating the prior value; and a binary temporary estimated word using the likelihood information and the modified external value A temporary estimated word generating means for generating a parity check means, a parity check means for parity checking the temporary estimated word based on the parity check matrix, and an iterative determination means for determining whether or not to repeat decoding. What to do That.

  According to the decoding method and the decoding apparatus of the present invention, since iterative decoding is performed in consideration of the reliability of the likelihood information of the transmission path, the performance of suppressing miscorrection with respect to the irregular LDPC code is improved. Good decoding can be realized.

  Embodiments of a decoding method and a decoding apparatus according to the present invention will be described below in detail with reference to the drawings.

(Embodiment 1)
In the present embodiment, the decoding method of the present invention will be described. However, in order to obtain information to be decoded, an example of encoding will be described first. Encoding can be performed by using a parity check matrix or a generator matrix as described above. For example, consider a case where a parity check matrix as shown in FIG. 1 is used. First, as shown in FIG. 1, the left half of the matrix is made to correspond to the information part of the LDPC code, and the remaining right half is made to correspond to the parity part of the LDPC code. Then, from the first row to the fifth row, it can be considered that each row includes one different parity bit, so the information bits that are element bits for each row are added by mod 2 By going, the parity bit can be easily obtained.

  For example, if the information bits are a 15-bit data series represented in FIG. 2A, the first, sixth, eleventh, 16th columns of the first row of the parity check matrix of FIG. Since 1 exists in the column, the first bit “0”, the sixth bit “0”, and the eleventh bit “0” of the information bits are added by mod 2, and the result is the parity bit (16 The parity bit “0” in the first row can be obtained. Similarly, the parity bit for each row can be obtained by adding the element bits with mod 2 in each row up to the fifth row.

  For the sixth and subsequent rows, the parity bit for each row can be obtained by adding the information bits that are element bits and the generated parity bit in order from mod 2 in the upper row. For example, with respect to the 6th row, since 1 exists in the 1st, 7th, 13th, 19th, and 21st columns, the first bit “0” of the information bit, the 7th By adding bit “0”, the 13th bit “1” and the fourth bit (19th bit) “0” of the parity bit with mod 2, the result is used as the parity bit (21st bit). , The parity bit “1” in the sixth row can be obtained. For the seventh and subsequent rows as well, parity bits can be obtained by adding the element bits with mod 2 in the same manner.

  By this operation, parity bits as shown in FIG. 2B are generated from the information bits shown in FIG. 2A, and the LDPC codeword as shown in FIG. Is obtained. Since the parity check matrix shown in FIG. 1 has different row weights and column weights for each row and column, the LDPC code generated by the parity check matrix of FIG. 1 is an irregular LDPC code.

  Next, the transmission path will be described. Noise is added to the LDPC-encoded information through the transmission path. Here, white Gaussian noise is assumed as added noise. The information received through the transmission path is usually represented by an amplitude value, a power value, or the like. However, when decoding an LDPC code, it is necessary to convert these values into likelihood information. Likelihood information is a value indicating whether the value of the bit is “0” or “1”. it can. Note that p (y | x) is a conditional probability distribution of the transmission path.

  Next, a decoding method will be described. Decoding is performed using likelihood information based on a parity check matrix. FIG. 3 is a flowchart showing the procedure of the decoding method according to Embodiment 1 of the present invention.

  In FIG. 3, first, in the external value generation step S101, based on the irregular parity check matrix, likelihood calculation is performed in the row direction using the input likelihood information and a priori value, and an external value is generated. . Next, in a modified external value generation step S102, the external value is changed based on the row weight of the parity check matrix to generate a modified external value. In advance value generation step S103, likelihood calculation is performed in the column direction using the corrected external value based on the parity check matrix, and an advance value is generated. Next, in the temporary estimated word generation step S104, a binary temporary estimated word is generated using the likelihood information and the corrected external value. In the parity check step S105, the temporary estimated word is based on the parity check matrix. Parity check is performed. Then, in repetition determination step S106, it is determined whether or not decoding is to be repeated.

Hereinafter, each step will be described in detail. However, here, as an example, decoding is performed using an irregular parity check matrix H = {H _mn } having m rows and n columns, and a set of column indexes belonging to the m-th row and having a value “1” A (m), a set of row indexes belonging to the nth column and having a value “1” will be described as B (n). The irregular parity check matrix refers to a parity check matrix having different row weights and column weights as shown in FIG.

First, the external value generation step S101 will be described. In step S101, an external value α _mn is generated according to _Equation 6 using the input likelihood information λ _i and the prior value β _mn based on the irregular parity check matrix H. However, the value of the prior value β _mn is all set to 0 only for the first decoding, and the value of the prior value β _mn calculated in step S103 is used for the second and subsequent decodings. In addition, sign (x) and f (x) in Equation 6 are functions represented by Equation 7 and Equation 8, respectively.

Next, the corrected external value generation step S102 will be described. In step S102, the external value α _mn is changed based on the row weight of the parity check matrix H, and the corrected external value α ′ _mn is generated. When decoding an LDPC code encoded using a parity check matrix having different row weights for each row as shown in FIG. 1, the higher the row weight, the easier the error correction. This is because the higher the row weight, the higher the number of bits constituting the element parity check code, and thus the higher the possibility that a plurality of errors are included in the element parity check codeword.

Accordingly, by reducing the absolute value of the external value α _mn and reducing the influence on decoding as the row weight is higher, the occurrence probability of erroneous correction can be reduced when viewed as an entire LDPC code. However, as the decoding is repeated, the reliability of the likelihood information is improved. In a state where the reliability of the likelihood is improved, more efficient decoding can be performed by actively using a row having a high row weight that can update the likelihood of many bits at a time.

Therefore, in the beginning of the low reliability of the likelihood information, the decoding is performed with emphasis on the row having a low row weight. As the number of decoding increases and the reliability of the likelihood information improves, the row weight increases. It can be said that it is important to improve the degree of use of rows. Hereinafter, a method of generating the modified external value α ′ _mn that enables efficient decoding will be described.

As an example, a method of generating the corrected external value α ′ _mn by multiplying the external value α _mn by a positive coefficient will be described. In this case, the positive coefficient can be obtained based on the external value α _mn . Since the external value α _mn is a value obtained by performing a likelihood calculation based on the parity check condition in each row, it can be considered to be a value representing the degree of improvement in the likelihood of each row.

Further, the external value α _mn is considered to show almost the same improvement degree in the row having the same row weight. _Therefore , if the average value of the absolute values of the external value α _mn is taken for each row having the same row weight, These values can be considered to represent the reliability for each row weight. Here, a method for obtaining a coefficient using the reliability for each row weight will be described.

Since the external value α _mn is a value calculated according to _Equation 6, there is a high possibility that the absolute value of the external value α _mn becomes smaller as the row weight is higher. This is because, as the row weight is higher, the number of bits constituting the element parity check code is larger, and thus it is more likely that the external value calculation includes likelihood information having a smaller absolute value. Therefore, the average value of the absolute value of the external value α _mn for each row weight, that is, the reliability for each row weight becomes smaller as the row weight is higher.

Therefore, for example, if each coefficient is a value obtained by dividing all average values by the largest value among the average values of absolute values, the higher the row weight, the smaller the coefficient. By multiplying the external value α _mn for each row, it is possible to obtain a corrected external value α ′ _{mn in} which a portion with low reliability is weakened. By using this modified outside values [alpha] _'mn instead of the external value alpha _mn, it is possible to reduce the possibility of causing erroneous correction than when decoded using external value alpha _mn.

Furthermore, when decoding is repeated and the reliability of the likelihood is improved, even if the number of bits constituting the element parity check code is large, the calculation of the external value α _mn includes likelihood information having an extremely small absolute value Is less likely. Therefore, each time repeating the decoding, since the row weight is smaller difference between low line and high coefficient row, by performing decoding using the modified external value [alpha] _'mn produced by the above-described method, the influence of the erroneous correction It is possible to efficiently improve the likelihood while suppressing the above.

When the coefficient is obtained, the coefficient may be obtained by the above method every time the external value α _mn is calculated in the external value generation step S101. Is prepared, and an appropriate coefficient is selected therefrom. The coefficient table can be generated, for example, by the steps shown in FIG. First, in the first reliability calculation step S201, the likelihood reliability is obtained from the input likelihood information. Next, in an external value generation step S202, likelihood calculation is performed in the row direction using likelihood information based on the parity check matrix to generate an external value. Then, in a coefficient generation step S203, a predetermined positive coefficient is obtained from the external value. In a coefficient table generation step S204, a coefficient table is generated by associating the reliability of likelihood with a predetermined positive coefficient. Hereinafter, each step will be described in detail.

First, the first reliability calculation step S201 will be described. In the first reliability calculation step S201, the reliability of likelihood is obtained from the input likelihood information λ _i . The input likelihood information λ _i is a value indicating whether each bit seems to be 0 or 1, and it can be said that the smaller the absolute value, the lower the reliability. Therefore, it is possible to know the reliability of likelihood by examining how much likelihood information having a small absolute value is included. For example, the reliability of the likelihood can be obtained by the steps shown in FIG. Hereinafter, each step will be described in detail.

First, in likelihood selection step S301, a predetermined number of values are selected from the likelihood information λ _i having the smallest absolute value. Theoretically, since the likelihood information with the smallest absolute value can be said to be the least reliable, it can be said that the value indicated by the likelihood information with the smallest absolute value represents the reliability of the likelihood. First, a predetermined number of values are selected from those having a small absolute value. Here, as an example, the number of 5% of the LDPC codeword length is selected. That is, assuming that the LDPC codeword length is 1000 bits, 50 pieces of information having a small absolute value are selected from the 1000 pieces of likelihood information.

  Next, in the first reliability calculation step S302, an average value of the absolute values of the selected values is obtained, and the average value is set as the reliability of likelihood. In this way, by taking an average value of a predetermined number of values selected from those having a small absolute value, smoothing is performed and variation is reduced, so that more reliable reliability can be obtained. As described above, the reliability of likelihood is obtained by the operations of S301 and S302.

Next, the external value generation step S202 will be described. In the external value generation step S202, based on the parity check matrix, the external value γ _mn is generated according to _Equation 9 using the likelihood information λ _i .

Next, the coefficient generation step S203 will be described. In the coefficient generation step S203, a positive coefficient is obtained from the external value γ _mn . The positive coefficient can be obtained by the steps shown in FIG. 6, for example. Hereinafter, each step will be described in detail.

First, in the external value reliability calculation step S401, as shown in FIG. 7, the rows having the same row weight are grouped together, and the average value of the absolute values of the external values γ _mn for each group according to Equation 10. seek δ _a.

In Equation 10, a is the group number, d _a is the row number in the a-th group, D _a is the number of rows in the a-th group, and E (d _a ) is the d _a row in the a-th group. belongs to the set of column index whose value is "1", k is the column number of, γ _dak is d _a row k-th column of the external value of a second of the group, l _a is present in a second of the group " 1 ”represents the total number. As described above, since the average value δ _a of the absolute values of the external values γmn of the rows having the same row weight can be regarded as the reliability for each row weight, first, the absolute value of the external value γ _mn for each row weight. determination of the mean value [delta] _a.

Then, in the coefficient calculation step S402, the ratio of the average value [delta] _a of the absolute values obtained for each group were calculated, and the ratio of their mean value and the positive coefficient. This operation is also as described above, and if each coefficient is a value obtained by dividing all the average values by the largest value among the obtained average values, a row having a higher row weight can have a smaller coefficient. . As described above, the coefficient for each row weight is obtained by the operations of S401 and S402.

  Next, the coefficient table generation step S204 will be described. In the coefficient table generation step S204, the likelihood reliability obtained in the first reliability calculation step S201 is associated with the positive coefficient generated in the coefficient generation step S203. For example, consider a case where an LDPC code generated by a parity check matrix having three row weights of 4, 5, and 6 as shown in FIG. 7 is transmitted to a transmission line having an S / N ratio of 5.0 dB. . However, the S / N ratio is assumed to be expressed by Equation 11.

In Equation 11, R represents the coding rate, and σ ² represents the variance of white Gaussian noise. Then, a coefficient applied to a row having a likelihood of 0.5 and a row weight of 4 (hereinafter referred to as a row weight 4 coefficient) of the signal received via the transmission line is 0.5. A coefficient applied to a row with a row weight of 5 (hereinafter referred to as a coefficient with a row weight of 5) is 0.7, and a coefficient applied to a row with a row weight of 6 (hereinafter referred to as a coefficient with a row weight of 6). Is 0.9. In that case, a coefficient table as shown in Table 1 can be generated.

  Similarly, by repeating steps S201 to S204 while changing the SN ratio of the transmission path to 6.0 dB, 7.0 dB, and 8.0 dB based on Equation 11, the reliability of likelihood as shown in Table 2 is obtained. A coefficient table in which degrees and positive coefficients are associated can be generated.

  By selecting a coefficient from the coefficient table generated in this way, it is possible to save the trouble of recalculating the coefficient each time decoding is repeated. The operations in steps S201 to S204 can be performed by computer simulation or the like.

  Next, a procedure for generating a corrected external value using a coefficient table will be described. The corrected external value can be generated by the steps shown in FIG. First, in the second reliability calculation step S501, the reliability of the current likelihood is obtained from the likelihood information and the past corrected external value. Next, in coefficient selection step S502, referring to the coefficient table, a positive coefficient is selected for each row based on the reliability of the current likelihood. In a coefficient multiplication step S503, a corrected external value is generated by multiplying the external value by a positive coefficient. Hereinafter, each step will be described in detail.

First, the second reliability calculation step S501 will be described. In the second reliability calculation step S501, the reliability of the current likelihood is obtained from the likelihood information λ _i and the past corrected external value α ′ _mn . The reliability of the current likelihood can be obtained by the steps shown in FIG. Hereinafter, each step will be described in detail.

First, the modified likelihood information generation step S601 will be described. In the modified likelihood information generation step S601, the likelihood information λ _i and the past modified external value α ′ _mn corresponding to the likelihood information are added according to Equation 12, and the modified likelihood information λ ′ _i is generated. However, the value of the modified external value α ′ _mn is all 0 only for the first decoding, and the value of the modified external value α ′ _mn calculated in step S102 is used for the second and subsequent decodings.

Next, the modified likelihood selection step S602 will be described. In the modified likelihood selection step S602, a predetermined number of values are selected from the modified likelihood information λ ′ _i having the smallest absolute value.

  Next, the second reliability calculation step S603 will be described. In the second reliability calculation step S603, an average value of the absolute values of the selected values is obtained, and the average value is set as the reliability of the current likelihood. As described above, the reliability of the current likelihood can be obtained by the operations in steps S601 to S603.

  Next, the coefficient selection step S502 will be described. In the coefficient selection step S502, referring to the coefficient table, a positive coefficient is selected for each row based on the reliability of the current likelihood. For example, if the reliability of the current likelihood is 0.68, the coefficient of the row weight 4 is 0.7, the coefficient of the row weight 5 is 0.8, and the coefficient of the row weight 6 is based on the coefficient table of Table 2. Is 0.93.

Next, the coefficient multiplication step S503 will be described. In a coefficient multiplication step S503, a modified external value α ′ _mn is generated by multiplying the external value α _mn by the coefficient selected in the coefficient selection step S502. Specifically, the coefficient selected for each row is multiplied by the external value _αmn of the corresponding row. Thereby, since the value of the external value α _mn becomes smaller as the row weight becomes higher, the influence of erroneous correction can be reduced. As described above, the corrected external value α ′ _mn can be generated by the operations of steps S501 to S503.

Next, the prior value generation step S103 will be described. In the prior value generation step S103, the prior value β _mn is generated based on the parity check matrix H using the corrected external value α ′ _{mn according} to Equation 13.

Next, temporary estimated word generation step S104 will be described. In the temporary estimated word generation step S104, a binary temporary estimated word C _n is generated according to Equation 14 using the likelihood information λ _i and the modified external value α ′ _mn .

Next, the parity check step S105 will be described. In the parity check step S105, the temporary estimated word C _n, the parity check based on a parity check matrix H is performed. Specifically, it is determined whether or not the temporary estimated word C _n satisfies Expression 15.

  Next, the repetition determination step S106 will be described. In iterative determination step S106, it is determined whether or not decoding is to be repeated. Specifically, in the parity check step S105, the operations of steps S101 to S105 are performed again only when the temporary estimated word Cn does not satisfy Equation 15 and the current number of decoding iterations is smaller than the predetermined number of decoding iterations. . Then, in the parity check step S105, the decoding is terminated when the temporary estimated word Cn satisfies Expression 15 or the current number of decoding iterations reaches a predetermined number of decoding iterations.

  As described above, the external value is corrected based on the likelihood reliability and the row weight based on the probability distribution of the transmission line, and iterative decoding is performed using the corrected external value. As compared with the case where iterative decoding is performed, it is possible to perform decoding with better performance while suppressing the influence of erroneous correction.

In the above, the case where the corrected external value α ′ _mn is generated by multiplying the external value α _mn by a positive coefficient has been described. However, by adding or subtracting a positive constant to the external value α _mn , the corrected external value α _mn is generated. The value α ′ _mn may be generated. In this case, instead of the coefficient table described above, a constant table in which the reliability of likelihood is associated with a positive constant for addition / subtraction may be created in advance. Then, as shown in FIG. 10, in the second reliability calculation step S501, the reliability of the current likelihood is calculated, and in the constant selection step S504, for each row based on the reliability of the likelihood and the constant table. A constant is selected, and in the constant addition / subtraction step S505, a corrected external value α ′ _mn may be generated by adding / subtracting the selected constant to / from the external value α _mn .

However, in the case of addition and subtraction in a direction to increase the absolute value of the external value alpha _mn, in the case of addition and subtraction in a direction to decrease the absolute value of the external value alpha _mn it is necessary to change some methods constants table and addition and subtraction to create is there.

First, when adding or subtracting in the direction of increasing the absolute value of the external value α _mn , a constant table is created so that a constant having a larger value is set for a row having a smaller row weight. If the external value is a positive value, the constant selected for each row is added. If the external value is a negative value, the constant selected for each row is subtracted.

Next, when adding or subtracting in the direction of decreasing the absolute value of the external value α _mn , a constant table is created so that a constant having a larger value is set for a row having a larger row weight. If the external value is a positive value, the constant selected for each row is subtracted. If the external value is a negative value, the constant selected for each row is added. However, when the sign of the external value changes due to addition / subtraction, the value of the corrected external value is set to 0. By the above method, it is possible to perform decoding with good performance while suppressing erroneous correction, as in the case of generating the corrected external value α ′ _mn by multiplying the external value α _mn by a positive coefficient.

In the above, the method of selecting positive coefficients for each row according to the reliability of likelihood has been described. However, positive coefficients are selected based on the number of times of decoding, and those coefficients are set as external values. The corrected external value α ′ _mn may be generated by multiplying α _mn . When using this method, in the communication channel to which this method is applied, check in advance how many times the decoding is performed and how much the reliability of the likelihood at that time will be. Based on the reliability, only the coefficients corresponding to the number of decoding times are extracted from the coefficient table described above, and a new coefficient table may be created from the relationship between the number of decoding times and the coefficient at that time.

  For example, if the likelihood reliability is 0.68 when decoding is performed twice, from Table 2, the coefficients of the row weight 4, the row weight 5, and the row weight 6 when the number of decoding is the second time are as follows. When the decoding reliability is 0.86 when the decoding is performed three times, the row weight 4 and the row weight when the decoding count is the third time are 0.7, 0.8, and 0.93, respectively. The coefficients of 5 and row weight 6 are 0.8, 0.9, and 0.95, respectively. By creating a coefficient table corresponding to the number of times of decoding in this way, it is possible to save the trouble of calculating the reliability of likelihood every time decoding is repeated. In addition, the capacity of the coefficient table can be reduced.

Then, as shown in FIG. 11, in coefficient selection step S506, a predetermined positive coefficient is selected for each row based on the number of times of decoding with reference to the coefficient table, and in coefficient multiplication step S507, a positive value is selected. A modified external value α ′ _mn is generated by multiplying the external value α _mn by the coefficient. According to the above method, it is possible to perform decoding with good performance while suppressing erroneous correction, as in the case of obtaining a positive coefficient from the reliability of likelihood.

Alternatively, a corrected constant value α ′ _mn may be generated by selecting a positive constant based on the number of times of decoding and adding or subtracting the constant to or from the external value α _mn . When using this method, in the communication channel to which this method is applied, check in advance how many times the decoding is performed and how much the reliability of the likelihood at that time will be. Based on the reliability, only the constants corresponding to each number of times of decoding are extracted from the above-described constant table, and a new constant table may be created from the relationship between the number of times of decoding and the constants at that time.

Then, as shown in FIG. 12, in the constant selection step S508, a predetermined positive constant is selected for each row based on the number of times of decoding with reference to the constant table. In the constant addition / subtraction step S509, a positive value is selected. A constant is _added to or subtracted from the external value α _mn to generate a corrected external value α ′ _mn . By the above method, it is possible to perform decoding with good performance while suppressing erroneous correction, as in the case of generating the corrected external value α ′ _mn by multiplying the external value α _mn by a positive coefficient.

(Embodiment 2)
In the present embodiment, the decoding device of the present invention will be described. However, before that, an example of an encoding device that generates information to be decoded will be described. The encoding apparatus can be configured by replacing the encoding method described in the first embodiment with an apparatus. That is, based on an irregular parity check matrix, a configuration is performed in which parity bits are generated by adding bits that are element bits for each row by mod 2 and information bits and parity bits are connected. Just do it. With such an encoding device, an irregular LDPC code can be generated.

  Next, the transmission path will be described. Noise is added to the LDPC-encoded information through the transmission path. Here, white Gaussian noise is assumed as added noise. And the information received through the transmission line shall be converted into likelihood information. However, the likelihood information is obtained by Equation 5 for the i-th component of the transmitted LDPC code. Note that p (y | x) is a conditional probability distribution of the transmission path.

  Next, the decoding apparatus will be described. FIG. 13 shows a block diagram of a decoding apparatus according to Embodiment 2 of the present invention. First, the external value generation unit 701 performs likelihood calculation in the row direction using the input likelihood information and a priori value based on the irregular parity check matrix, and generates an external value. Next, the modified external value generation unit 702 changes the external value based on the row weight of the parity check matrix, and generates a modified external value. Then, the prior value generation unit 703 performs likelihood calculation in the column direction using the corrected external value based on the parity check matrix, and generates a prior value. Then, the temporary estimated word generation unit 704 generates a binary temporary estimated word using the likelihood information and the modified external value, and the parity check unit 705 generates a temporary estimated word based on the parity check matrix. A parity check is performed. Then, iterative determination means 706 determines whether or not to repeat decoding. Hereinafter, each means will be described in detail.

First, the external value generation unit 701 will be described. The external value generation unit 701 generates an external value α _mn according to _Equation 6 using the input likelihood information λ _i and the prior value β _mn based on the irregular parity check matrix H. However, as the value of the prior value β _mn , 0 is used only for the first decoding, and the value of the prior value β _mn calculated by the prior value generation unit 703 is used for the second and subsequent decodings. In addition, sign (x) and f (x) in Equation 6 are functions represented by Equation 7 and Equation 8, respectively.

Next, the corrected external value generation unit 702 will be described. In the corrected external value generation means 702, the external value α _mn is changed based on the row weight of the parity check matrix H, and the corrected external value α ′ _mn is generated. As an example, a case will be described in which a corrected external value α ′ _mn is generated by multiplying the external value α _mn by a positive coefficient. In this case, the modified external value generation means 702 can be configured by a memory for storing the coefficient table shown in FIG. 14 and three means. In FIG. 14, a memory 801 is a memory that stores a coefficient table generated in advance by the method described in the first embodiment.

Next, the reliability calculation unit 802 calculates the reliability of the current likelihood from the likelihood information and the past corrected external value. Then, the coefficient selection unit 803 refers to the coefficient table stored in the memory 801 and selects a predetermined positive coefficient for each row based on the reliability of the current likelihood. Then, the multiplication unit 804 multiplies the external value by the coefficient selected by the coefficient selection unit 803 to generate a modified external value α ′ _mn . Hereinafter, each means will be described in detail.

First, the reliability calculation means 802 will be described. In the reliability calculation means 802, the reliability of the current likelihood is obtained from the likelihood information λ _i and the past corrected external value α ′ _mn . The reliability calculation means 802 is composed of three means shown in FIG. Hereinafter, each means will be described in detail.

First, the modified likelihood information generating unit 901 will be described. Fixes likelihood information generation unit 901, in accordance with the number 12, are subject to past modified external value [alpha] _'mn corresponding to the likelihood information lambda _i and likelihood information, corrected likelihood information Ramuda' _i is generated . However, as the value of the modified external value α ′ _mn , all 0s are used only for the first decoding, and the modified external value α ′ _mn calculated by the modified external value generation unit 702 for the second and subsequent decodings. Is used.

Next, the modified likelihood selecting means 902 will be described. The corrected likelihood selection means 902 selects a predetermined number of values from the corrected likelihood information λ ′ _i having the smallest absolute value.

  Next, the reliability calculation means 903 will be described. In the reliability calculation means 903, the average value of the absolute values of the selected values is obtained, and the average value is set as the reliability of the current likelihood. As described above, the reliability of the current likelihood is obtained by the means 901 to 903.

  Next, the coefficient selection unit 803 will be described. The coefficient selection unit 803 refers to the coefficient table stored in the memory 801 and selects a predetermined positive coefficient for each row based on the reliability of the current likelihood. For example, if the reliability of the current likelihood is 0.68, the coefficient of the row weight 4 is 0.7, the coefficient of the row weight 5 is 0.8, and the coefficient of the row weight 6 is based on the coefficient table of Table 2. Is 0.93.

Next, the multiplication unit 804 will be described. The multiplier unit 804, coefficient selected in the coefficient selection unit 803 fixes the external value [alpha] _'mn by being multiplied in the external value alpha _mn is generated. Specifically, the coefficient selected for each row is multiplied by the external value α _mn of the corresponding row. Thereby, since the value of the external value α _mn becomes smaller as the row weight becomes higher, the influence of erroneous correction is reduced. As described above, the corrected external value α ′ _mn is generated by the means 802 to 804 and the memory 801.

Next, the prior value generation unit 703 will be described. Based on the parity check matrix H, the prior value generation means 703 generates the prior value β _mn according to Equation 13 using the corrected external value α ′ _mn .

Next, the temporary estimated word generation means 704 will be described. The temporary estimated word generation means 704 generates a binary temporary estimated word C _n according to Equation 14 using the likelihood information λ _i and the modified external value α ′ _mn .

Next, the parity check unit 705 will be described. The parity check unit 705, the temporary estimated word C _n, the parity check based on a parity check matrix H is performed. Specifically, it is determined whether or not the temporary estimated word C _n satisfies Expression 15.

Next, the repetition determination unit 706 will be described. Iterative determination means 706 determines whether or not to repeat decoding. Specifically, when the parity check means 705 determines that the temporary estimated word C _n does not satisfy Equation 15, and further repeats decoding only when the current number of decoding iterations is smaller than a predetermined number of decoding iterations. Determined. Then, in the parity check means 705, when it is determined that the temporary estimated word C _n satisfies Equation 15, or when the current number of decoding iterations reaches a predetermined number of decoding iterations, it is determined that decoding has ended.

  Using the above device, the external value is corrected based on the likelihood reliability and the row weight based on the probability distribution of the transmission path, and the normal external value is obtained by performing iterative decoding using the corrected external value. It is possible to perform decoding with better performance with less influence of erroneous correction than when iterative decoding is used.

In the above, in the modified external value generating means 702, has been described to generate a modified external value [alpha] _'mn by multiplying a positive coefficient in external value alpha _mn, a positive constant to the external value alpha _mn The corrected external value α ′ _mn can also be generated by addition / subtraction. In this case, instead of the coefficient table described above, a constant table in which the reliability of likelihood is associated with a positive constant for addition / subtraction may be created and stored in the memory 801.

Then, the reliability calculation means 802 shown in FIG. 16 calculates the reliability of the current likelihood, and the constant selection means 805 calculates the reliability for each row based on the likelihood reliability and the constant table stored in the memory 801. select constant, the addition and subtraction means 806, it may be generated a modified external value [alpha] _'mn by subtracting the selected constant external value alpha _mn. However, in the case of addition and subtraction in a direction to increase the absolute value of the external value alpha _mn, in the case of addition and subtraction in a direction to decrease the absolute value of the external value alpha _mn it is necessary to change some methods constants table and addition and subtraction to create is there.

First, when adding or subtracting in the direction of increasing the absolute value of the external value α _mn , a constant table is created so that a constant having a larger value is set for a row having a smaller row weight. Then, in the addition / subtraction means 806, when the external value is a positive value, the constant selected for each row is added, and when the external value is a negative value, the constant selected for each row is subtracted.

Next, when adding or subtracting in the direction of decreasing the absolute value of the external value α _mn , a constant table is created so that a constant having a larger value is set for a row having a larger row weight. Then, in the addition / subtraction means 806, when the external value is a positive value, the constant selected for each row is subtracted, and when the external value is a negative value, the constant selected for each row is added. However, when the sign of the external value changes due to addition / subtraction, the value of the corrected external value is set to 0. With the above configuration, it is possible to perform decoding with good performance while suppressing erroneous correction as in the case of generating the corrected external value α ′ _mn by multiplying the external value α _mn by a positive coefficient.

In the above description, the case where the corrected external value generation unit 702 selects a positive coefficient for each row according to the reliability of the likelihood has been described. However, the positive coefficient is determined based on the number of times of decoding. The modified external value α ′ _mn may be generated by selecting and multiplying the coefficient by the external value α _mn . In this case, in the communication channel to which this method is applied, the number of times of decoding is checked in advance to determine how much the reliability of the likelihood is, and the reliability of the likelihood at that time is determined. Based on the above-described coefficient table, only the coefficient corresponding to each number of decoding times is extracted, a new coefficient table is created from the relationship between the number of decoding times and the coefficient, and stored in the memory 801.

  For example, if the likelihood reliability is 0.68 when decoding is performed twice, from Table 2, the coefficients of the row weight 4, the row weight 5, and the row weight 6 when the number of decoding is the second time are as follows. When the decoding reliability is 0.86 when the decoding is performed three times, the row weight 4 and the row weight when the decoding count is the third time are 0.7, 0.8, and 0.93, respectively. The coefficients of 5 and row weight 6 are 0.8, 0.9, and 0.95, respectively. By creating a coefficient table corresponding to the number of times of decoding in this way, it is possible to save the trouble of calculating the reliability of likelihood every time decoding is repeated. In addition, the capacity of the memory 801 that stores the coefficient table can be reduced.

Then, in the coefficient selection means 1001 shown in FIG. 17, a predetermined positive coefficient is selected for each row based on the number of times of decoding with reference to the coefficient table stored in the memory 801. In the multiplication means 1002, A corrected external value α ′ _mn is generated by multiplying the external value α _mn by a positive coefficient. With the above configuration, it is possible to perform decoding with good performance while suppressing erroneous correction, as in the case of obtaining a positive coefficient from the reliability of likelihood.

Alternatively, a positive constant may be selected based on the number of times of decoding, and the corrected external value α ′ _mn may be generated by adding or subtracting the constant to or from the external value α _mn . In this case, in the communication channel to which this method is applied, the number of times of decoding is checked in advance to determine how much the reliability of the likelihood is, and the reliability of the likelihood at that time is determined. Based on the above-described constant table, only the constants corresponding to each number of decoding times are extracted, a new constant table is created from the relationship between the number of decoding times and the constants at that time, and stored in the memory 801.

Then, the constant selection unit 1003 shown in FIG. 18 refers to the constant table stored in the memory 801 and selects a predetermined positive constant for each row based on the number of times of decoding. A positive constant is _added to or subtracted from the external value α _mn to generate a corrected external value α ′ _mn . With the above configuration, it is possible to perform decoding with good performance while suppressing erroneous correction as in the case of generating the corrected external value α ′ _mn by multiplying the external value α _mn by a positive coefficient.

  According to the decoding method and the decoding apparatus of the present invention, it is possible to realize high-performance decoding for non-regular LDPC codes, which is useful in any communication channel using non-regular LDPC codes. In particular, it is useful for a hologram recording / reproducing system or the like in which the SN ratio is poor and many errors frequently occur.

The figure which shows the example of the parity check matrix in embodiment of this invention The figure which shows the example of the LDPC codeword in embodiment of this invention The flowchart which showed the procedure of the decoding method in the 1st Embodiment of this invention The flowchart which showed the procedure which produces the coefficient table in the 1st Embodiment of this invention The flowchart which showed the procedure of the 1st reliability calculation step in the 1st Embodiment of this invention. The flowchart which showed the procedure of the coefficient production | generation step in the 1st Embodiment of this invention The figure which showed the example of grouping in the 1st Embodiment of this invention The flowchart which showed the procedure of the correction | amendment external value generation step in the 1st Embodiment of this invention. The flowchart which showed the procedure of the 2nd reliability calculation step in the 1st Embodiment of this invention. The flowchart which showed the procedure of the correction | amendment external value generation step in the 1st Embodiment of this invention. The flowchart which showed the procedure of the correction | amendment external value generation step in the 1st Embodiment of this invention. The flowchart which showed the procedure of the correction | amendment external value generation step in the 1st Embodiment of this invention. The block diagram which showed the structure of the decoding apparatus in the 2nd Embodiment of this invention The block diagram which showed the structure of the correction | amendment external value production | generation means in the 2nd Embodiment of this invention. The block diagram which showed the structure of the reliability calculation means in the 2nd Embodiment of this invention The block diagram which showed the structure of the correction | amendment external value production | generation means in the 2nd Embodiment of this invention. The block diagram which showed the structure of the correction | amendment external value production | generation means in the 2nd Embodiment of this invention. The block diagram which showed the structure of the correction | amendment external value production | generation means in the 2nd Embodiment of this invention. The figure which shows the example of the general parity check matrix H The figure which shows the example of the general generator matrix G

Explanation of symbols

S101 External value generation step S102 Modified external value generation step S103 Prior value generation step S104 Temporary estimation word generation step S105 Parity check step S106 Repetition determination step S201 First reliability calculation step S202 External value generation step S203 Coefficient generation step S204 Coefficient table Generation step S301 Likelihood selection step S302 First reliability calculation step S401 External value reliability calculation step S402 Coefficient calculation step S501 Second reliability calculation step S502 Coefficient selection step S503 Coefficient multiplication step S504 Constant selection step S505 Constant addition / subtraction step S506 coefficient selection step S507 coefficient multiplication step S508 constant selection step S509 constant addition / subtraction step S601 correction Degree information generation step S602 Correction likelihood selection step S603 Second reliability calculation step 701 External value generation means 702 Correction external value generation means 703 Prior value generation means 704 Temporary estimation word generation means 705 Parity check means 706 Repetition determination means 801 Memory 802 Reliability calculation means 803 Coefficient selection means 804 Multiplication means 805 Constant selection means 806 Addition / subtraction means 901 Correction likelihood information generation means 902 Correction likelihood selection means 903 Reliability calculation means 1001 Coefficient selection means 1002 Multiplication means 1003 Constant selection means 1004 Addition / subtraction means

Claims (21)

A method for decoding an irregular LDPC code, comprising:
Based on the irregular parity check matrix, performing likelihood calculation in the row direction using the likelihood information of the transmission path, generating an external value;
Changing the external value based on a row weight of the parity check matrix to generate a modified external value;
Based on the parity check matrix, performing a likelihood calculation in the column direction using the modified external value, and generating a prior value;
Generating a binary temporary estimated word using the likelihood information and the modified external value;
Parity checking the temporary estimate word based on the parity check matrix;
And a step of determining whether or not to repeatedly perform decoding. The change based on the row weight of the parity check matrix is:
By multiplying the external value of each row by a predetermined positive coefficient;
The coefficient applied to the external value of a row with a small row weight is
The decoding method according to claim 1, wherein the row weight is larger than a coefficient applied to the external value of a row having a large row weight. The change based on the row weight of the parity check matrix is:
By adding or subtracting a predetermined positive constant to the external value of each row,
When the external value of a row with a small row weight is a positive value,
Adding a constant larger than a constant applied to the external value of the row having a large row weight to the external value of the row having a small row weight;
When the external value of a row with a small row weight is a negative value,
The decoding method according to claim 1, wherein a constant larger than a constant applied to the external value of a row having a large row weight is subtracted from the external value of a row having a small row weight. The change based on the row weight of the parity check matrix is:
By adding or subtracting a predetermined positive constant to the external value of each row,
When the external value of a row with a small row weight is a positive value,
Subtracting a constant smaller than the constant applied to the external value of the row with the large row weight from the external value of the row with the small row weight;
When the external value of a row with a small row weight is a negative value,
Adding a constant smaller than a constant to be applied to the external value of a row having a large row weight to the external value of a row having a small row weight;
When the sign of the external value changes due to the addition / subtraction,
The decoding method according to claim 1, wherein the value of the modified external value is set to 0. Before decoding, further comprising generating a coefficient table associating the reliability of likelihood with the predetermined positive coefficient;
Generating the modified external value comprises:
Obtaining a reliability of a current likelihood from the likelihood information and a past corrected external value;
Selecting the predetermined positive coefficient for each row based on the reliability of the current likelihood with reference to the coefficient table;
Generating the modified external value by multiplying the external value by the predetermined positive coefficient;
The decoding method according to claim 2, comprising: Generating a constant table associating the reliability of likelihood with the predetermined positive constant before decoding;
Generating the modified external value comprises:
Obtaining a reliability of a current likelihood from the likelihood information and a past corrected external value;
Selecting the predetermined positive constant for each row based on the reliability of the current likelihood with reference to the constant table;
Generating the modified external value by adding / subtracting the predetermined positive constant to / from the external value;
The decoding method according to claim 3 or 4, wherein the decoding method comprises: Determining the reliability of the current likelihood;
Adding the past correction external value corresponding to the likelihood information and the likelihood information, and generating corrected likelihood information;
Selecting a predetermined number of values from the correction likelihood information having a small absolute value;
Obtaining an average value of absolute values of selected values, and setting the average value of the absolute values as a reliability of the current likelihood;
The decoding method according to claim 5 or 6, characterized by comprising: Generating the coefficient table comprises:
Obtaining a likelihood reliability from the likelihood information;
Based on the parity check matrix, performing likelihood calculation in the row direction using the likelihood information, and generating the external value;
Obtaining the predetermined positive coefficient from the external value;
Associating the likelihood reliability with the predetermined positive coefficient and generating the coefficient table;
The decoding method according to claim 5, comprising: Determining the likelihood reliability;
Selecting a predetermined number of values from the likelihood information having a small absolute value;
Obtaining an average value of absolute values of selected values, and setting the average value of the absolute values as a reliability of the likelihood;
The decoding method according to claim 8, comprising: Obtaining the predetermined positive coefficient comprises:
Collecting the rows having the same row weight as a group, and obtaining an average value of absolute values of the external values for each group;
Calculating a ratio of the average values of the absolute values obtained for each group, and setting the ratio of the average values as the predetermined positive coefficient;
The decoding method according to claim 8, comprising: Before decoding, further comprising generating a coefficient table associating the number of decoding times with the predetermined positive coefficient;
Generating the modified external value comprises:
Selecting the predetermined positive coefficient for each row based on the number of times of decoding with reference to the coefficient table;
Generating the modified external value by multiplying the external value by the predetermined positive coefficient;
The decoding method according to claim 2, comprising: Before decoding, further comprising the step of generating a constant table associating the number of decoding times with the predetermined positive constant;
Generating the modified external value comprises:
Selecting the predetermined positive constant for each row based on the number of times of decoding with reference to the constant table;
Generating the modified external value by adding / subtracting the predetermined positive constant to / from the external value;
The decoding method according to claim 3 or 4, wherein the decoding method comprises: An apparatus for decoding a non-regular LDPC code,
Based on the irregular parity check matrix, external value generation means for performing likelihood calculation in the row direction using the likelihood information of the transmission path and generating an external value;
Modified external value generating means for changing the external value based on a row weight of the parity check matrix and generating a corrected external value;
Based on the parity check matrix, prior value generation means for performing a likelihood calculation in the column direction using the modified external value and generating a prior value;
Temporary estimated word generation means for generating a binary temporary estimated word using the likelihood information and the modified external value;
Parity check means for parity checking the temporary estimated word based on the parity check matrix;
A decoding apparatus comprising: an iterative determination unit that determines whether or not to perform decoding repeatedly. The modified external value generation means includes
Generating the modified external value by multiplying the external value of each row by a predetermined positive coefficient;
The coefficient applied to the external value of a row with a small row weight is
The decoding device according to claim 13, wherein the row weight is larger than a coefficient applied to the external value of a row having a large row weight. The modified external value generation means includes
Generating the modified external value by adding or subtracting a predetermined positive constant to the external value of each row;
When the external value of a row with a small row weight is a positive value,
Adding a constant larger than a constant applied to the external value of the row having a large row weight to the external value of the row having a small row weight;
When the external value of a row with a small row weight is a negative value,
14. The decoding apparatus according to claim 13, wherein a constant larger than a constant applied to the external value of a row having a large row weight is subtracted from the external value of a row having a small row weight. The modified external value generation means includes
Generating the modified external value by adding or subtracting a predetermined positive constant to the external value of each row;
When the external value of a row with a small row weight is a positive value,
Subtracting a constant smaller than the constant applied to the external value of the row with the large row weight from the external value of the row with the small row weight;
When the external value of a row with a small row weight is a negative value,
Adding a constant smaller than a constant applied to the external value of the row having a large row weight to the external value of the row having a small row weight;
When the sign of the external value changes due to the addition / subtraction,
The decoding device according to claim 13, wherein the value of the modified external value is set to 0. A memory for storing a coefficient table associating the reliability of likelihood with the predetermined positive coefficient;
The modified external value generating means is
A reliability calculation means for determining the reliability of the current likelihood from the likelihood information and the past corrected external value;
Referring to the coefficient table, coefficient selecting means for selecting the predetermined positive coefficient for each row based on the reliability of the current likelihood;
Multiplying means for generating the modified external value by multiplying the external value by the predetermined positive coefficient;
The decoding device according to claim 14, comprising: A memory for storing a constant table associating the reliability of likelihood with the predetermined positive constant;
The modified external value generating means is
A reliability calculation means for determining the reliability of the current likelihood from the likelihood information and the past corrected external value;
Constant selection means for referring to the constant table and selecting the predetermined positive constant for each row based on the reliability of the current likelihood;
Addition / subtraction means for generating the corrected external value by adding / subtracting the predetermined positive constant to / from the external value;
The decoding device according to claim 15 or 16, characterized by comprising: The reliability calculation means is
Correction likelihood information generating means for adding the likelihood information and the past correction external value to generate correction likelihood information;
Likelihood information selection means for selecting a predetermined number of values from the corrected likelihood information having a small absolute value;
An average value of the absolute values of the selected values, and a reliability calculation means for setting the average value of the absolute values as the reliability of the current likelihood;
The decoding device according to claim 17 or 18, characterized by comprising: A memory for storing a coefficient table associating the number of decoding times with the predetermined positive coefficient;
The modified external value generating means is
Coefficient selection means for referring to the coefficient table and selecting the predetermined positive coefficient for each row based on the number of times of decoding;
Multiplying means for generating the modified external value by multiplying the external value by the predetermined positive coefficient;
The decoding device according to claim 14, comprising: A memory for storing a constant table associating the number of decoding times with the predetermined positive constant;
The modified external value generating means is
Constant selection means for selecting the predetermined positive constant for each row based on the number of times of decoding with reference to the constant table;
Addition / subtraction means for generating the corrected external value by adding / subtracting the predetermined positive constant to / from the external value;
The decoding device according to claim 15 or 16, characterized by comprising:

Images