JP7542972B2 - Method for adaptively scaling correction values in decoding and decoder therefor - Google Patents

Description

The present invention relates to a method for improving the decoding performance in a decoding method and a decoder using the same.

The Low Density Parity Check (LDPC) code, discovered by Gallager in 1963, is one of the error-correcting codes that corrects errors that occur on the transmission line.

The biggest problem with LDPC codes is the implementation of the decoding method. The most common BP decoding method has high decoding performance, but because the formula contains complex functions, it was necessary to make the functions into a table in order to implement it. A simplified Min-sum (MS) decoding method was then considered, but degradation of decoding performance became an issue. To solve these problems, various simplified decoding methods have been proposed. Simplified decoding methods can be broadly divided into BP-based algorithms based on BP decoding method and MS-based algorithms based on Min-sum (MS) decoding method. BP-based has high decoding performance but high complexity, while MS-based has a certain degree of degradation in decoding performance but low complexity.

As an example of a decoding method, Patent Document 1 discloses a decoding method and decoding device that improves the decoding performance of error-correcting codes by approximating row calculations in Sum-Product decoding by offset BP-based decoding. This is achieved by subtracting an offset value corresponding to the magnitude of the minimum absolute value of a column LLR from the minimum absolute value of the column LLR in the row calculation, and setting the result as the row LLR corresponding to the column of the column LLR.

In addition, the decoder in Patent Document 2 discloses an invention for a decoding device that reduces power consumption when decoding a received signal that has been coded using low-density parity check coding. This is achieved by selecting either the correction value or zero depending on the state of the transmission line, and setting the correction term used in row processing to the value selected above.

In addition, in the decoding device and decoding method of Patent Document 3, the decoding device includes a bit node processing unit that determines a second probability message from a posterior probability with the prior probability set as an initial value and the first probability message, a check node processing unit that determines an update value of the first probability message based on the second probability message, and a posterior probability update processing unit that determines an update value of the posterior probability based on the second probability message and the update value of the first probability message. The check node processing unit determines an update value of the first probability message based on the second probability message based on an approximation equation obtained by expanding the equation of the BP algorithm for determining the first probability message by Jacobian logarithm and further expanding it by mathematical induction. This is a decoding device and decoding method that has better BER characteristics than the Layered Normalized Min-sum algorithm and uses an algorithm that is easy to realize in hardware.

In addition, in Patent Document 4, after extracting control information from TMCC, A is adaptively determined according to the modulation method, coding rate, and DU ratio, while in Patent Document 5, the scale of B is converted to match the scale of the theoretical formula of LLR, and in Patent Document 6, the scale of B is selected to be changed or set to 0 according to the noise variance value. Note that the parameter used in the MS (Min-sum) decoding method is A, the correction value used in the BP decoding method is B, and the parameter included in the approximation formula of B is C.

JP 2011-4229 A JP 2010-200126 A JP 2011-55168 A JP 2014-147029 A JP 2011-129981 A JP 2010-200126 A

As described in the above-mentioned patent documents, various methods have been used to improve and simplify the decoding performance.
Currently, in Japan, television broadcasting and material transmission are being made even higher resolution. For these error correction codes, LDPC codes similar to those in ISDB-S3, the standard for Japanese satellite digital broadcasting, are being adopted. ISDB-S3 requires an LDPC decoder that can reduce the required CNR, but from the viewpoint of practical application, it is difficult to apply a BP-based decoder with high decoding performance. Therefore, the present invention aims to provide a decoding method and decoder that achieve both high decoding performance and low complexity by simplifying the equations that appear in the BP-based decoding algorithm and adaptively adjusting the equations.

について、ｇ（Ｃ）≒０と見なせるＣを決定したのちに、任意のｋで、

とすると、

として場合分けを行い、Ｉｋ＞Ｃ＋であるとき演算を終了することによって演算量を削減しつつ、復号性能を維持するために、

により置き換えを行うこと
を特徴とする復号化における補正値の適応スケール変換方法である。 The present invention has been made to solve the above-mentioned problems, and the invention described in claim 1 is as follows:
In a decoding method for decoding a codeword encoded by an LDPC code, a formula of a BP-based algorithm based on a BP decoding method is simplified, and an error caused by the simplification is reduced ,

After determining C such that g(C) ≒ 0, for any k,

Then,

Then, when Ik>C+, the calculation is terminated to reduce the amount of calculation while maintaining the decoding performance.

To replace
The present invention relates to a method for adaptively scaling correction values in decoding, the method comprising the steps of:

について、ｇ（Ｃ）≒０と見なせるＣを決定したのちに、任意のｋで、

とすると、

として場合分けを行い、Ｉｋ＞Ｃ＋であるとき演算を終了することによって演算量を削減しつつ、復号性能を維持するために、

により置き換えを行うこと
を特徴とする復号化における補正値の適応スケール変換復号器である。 The invention described in claim 2 is as follows:
A decoder having a column processing calculation unit, a row processing input unit, an absolute value calculation unit, a sign extraction unit, a sign calculation unit, a minimum value search unit, a minimum value selection unit, a constant value calculation unit, a correction value calculation unit, a correction value selection unit, a row processing output unit, and a post-LLR calculation unit,
A decoder that simplifies the formula of a BP-based algorithm based on the BP decoding method and reduces the error caused by the simplification is as follows:

After determining C such that g(C) ≒ 0, for any k,

Then,

Then, when Ik>C+, the calculation is terminated to reduce the amount of calculation while maintaining the decoding performance.

To replace
The present invention relates to an adaptive scale conversion decoder for correction values in decoding.

The effect of the present invention is to reduce the amount of calculation required for the correction formula in the BP-based algorithm. In addition, the error can be reduced by adjusting the correction formula. Another advantage is that the degradation of decoding performance can be suppressed.

1 is a flowchart of a first embodiment of the present invention. This is a number line diagram represented by equation (39). FIG. 11 is a state transition diagram represented by equation (39). FIG. 13 is a diagram showing the effect of error reduction. 1 is an example of a flowchart of an LBP decoding method. 2 is a diagram showing an example of a decoder configuration according to a first embodiment of the present invention; BER characteristics of each decoding method. 1 is an example of a search tree. This is an example of a comparator. 1 is an example of a search tree for seven comparators. 13 is an example of a search tree for 13 comparators. 13 shows a configuration of a numerical search according to a second embodiment of the present invention. 11 is a graph showing the mode and frequency of the second embodiment according to the present invention. 11 is a diagram showing the structure of a search tree according to a second embodiment of the present invention. 13 shows the configuration of a sorting unit 2 according to a second embodiment of the present invention. 11 is a flowchart of a search tree according to a second embodiment of the present invention. 13 is a graph showing the min3 search accuracy of the second embodiment according to the present invention. 13 is a graph showing the search accuracy of min4 in the second embodiment according to the present invention. 11 is a first flowchart of a correction unit according to a second embodiment of the present invention. 13 is a second flowchart of the correction unit according to the second embodiment of the present invention. FIG. 11 is a schematic diagram of scale conversion according to a third embodiment of the present invention. FIG. 11 is a schematic diagram of scale conversion according to a third embodiment of the present invention. 13 shows the configuration of a decoder according to a third embodiment of the present invention. 11 is a flowchart of a decoder according to a third embodiment of the present invention. FIG. 13 is a diagram showing the relationship between the BP decoding method and each embodiment. A2+A4 BER characteristics (QPSK, R=3/4). A2+A4 BER characteristics (1024QAM, R=2/3).

An example of an embodiment of the present invention will be described below with reference to the drawings. Fig. 1 is a flowchart of one embodiment of the present invention, Fig. 2 is a number line diagram represented by equation (39), Fig. 3 is a state transition diagram represented by equation (39), Fig. 4 is a diagram showing the effect of error reduction, Fig. 5 is an example of a flowchart of the LBP decoding method, Fig. 6 is an example of a decoder configuration of Example 1 of the present invention, and Fig. 7 is the BER characteristics of each decoding method.

The LDPC code is defined as a check matrix with very few non-zero matrix elements. When the check matrix of an LDPC code is expressed as H = [Hm,n] (m ∈ [1,M], n ∈ [1,N]), the set of column indices that have a 1 in the mth row is expressed as N(m) = {n:Hm,n = 1}, and the set of row indices that have a 1 in the nth column is expressed as M(n) = {m:Hm,n = 1}.

と表される。
ここで、ｘとｙはそれぞれ送信シンボルと受信シンボルである。変調方式をＢＰＳＫ、通信路を分散σ^２のＡＷＧＮ（Ａｄｄｉｔｉｖｅ Ｗｈｉｔｅ Ｇａｕｓｓｉａｎ Ｎｏｉｚｅ）通信路と仮定すると、ＬＬＲは

となる。 When decoding an LDPC code using soft decision based on LLR (Log Likelihood Ratio), the LLR is

This is expressed as:
Here, x and y are the transmitted symbol and the received symbol, respectively. Assuming that the modulation method is BPSK and the communication channel is an additive white Gaussian noise (AWGN) channel with a variance of σ ² , the LLR is

It becomes.

The most common method of decoding LDPC codes is the Belief Propagation (BP) decoding method. Generally, to evaluate the BP decoding method, parallel scheduling is used, in which the entire row processing and the entire column processing are performed alternately, or serial scheduling is used, in which row processing and column processing are performed partially alternately. A BP decoding method that employs serial scheduling is called a Layered BP (LBP) decoding method.

を復号系列とする。 The decoding process of the LBP decoding method is as follows, and the flowchart of the LBP decoding method is shown in Figure 5. Here, λn is the n-th LLR (Log Likelihood Ratio), l is the current iteration number, lmax is the maximum iteration number, α ^(l) _m,n is the extrinsic LLR sent from check node m to variable node n, _βm,n ^{(l) is} the prior LLR sent from variable node n to check node m, _βn ^(l) is the posterior LLR,

Let be the decoded sequence.

In step 1, initialization is performed: l=1, β _m ⁽⁰⁾ and lmax are set.

を計算する。ｎは１，２，・・・，Ｎの順序に従う。 Step 2 is column processing. For each n in the current layer, for the node with [H _m,n ]=1,

Calculate n in the order 1, 2, ..., N.

を計算する。ここで、

と定義され、ｆ（ｘ）をＧａｌｌａｇｅｒ関数という。ｍは１，２，・・・，Ｍの順序に従う。 Step 3 is row processing. For each m in the current layer, for the node with [H _m,n ]=1,

Calculate where:

where f(x) is called a Gallager function, and m follows the order 1, 2, ..., M.

を計算する。 Step 4 is to update the a posteriori LLR. For each n in the current layer, we use the already calculated α _m,n ^(l) and β _m,n ^(l)

Calculate.

Step 5 is to determine the layer. If a next layer exists, perform step 2; if not, perform step 6.

を用いて行う。 In step 6, the decoded sequence is estimated.

This is done using.

In step 7, a parity check is performed. If Hc ^{∧ T} = 0 or 1 = l _max , c ^∧ is output as the decoded result and the process ends. Or, if l = l + 1, step 2 is performed.

と表すことができる。ここで、演算田は、

と定義される。ここで、Ｉ_ｉ＞０であり、演算田は可換性、結合性を有する。式（１１）はＪａｃｏｂｉａｎ Ｌｏｇａｒｉｔｈｍにより、

と展開できる。ここで、ｍｉｎ（Ａ，Ｂ）は小さい方を選択する関数である。また、

とおくと、

と表せる。ＢＰ復号法は実装において関数ｇ（ｘ）の演算量が問題となるため、線形近似方式や区分線形近似方式、量子化テーブル方式などの手法が提案されている。 The row processing of the BP decoding method and the LBP decoding method uses the same formula.

Here, the calculation field is

Here, I _i >0, and the operators are commutative and associative. Equation (11) can be expressed by Jacobian Logarithm as follows:

Here, min(A, B) is a function that selects the smaller one.

Further afield,

In the BP decoding method, the amount of calculation of the function g(x) becomes an issue in implementation, so methods such as a linear approximation method, a piecewise linear approximation method, and a quantization table method have been proposed.

Modified MS (MMS) decoding and δ-min (DM) decoding are decoding methods that approximate the term g(x). The MMS decoding and DM decoding methods use a parameter D to perform approximation as follows:

の演算毎にＤを求めるため演算量が多くなる。行処理で演算されるＩ_ｉの個数は自ノードを除いた｜Ｎ（ｍ）｜－１個であるため、式（１８）の演算は｜Ｎ（ｍ）｜－２回必要となる。 The parameter D is determined by _Ia and _Ib obtained during decoding, so it does not need to be determined in advance and is not affected by the degree distribution of the code. However,

Since D is calculated for each calculation, the amount of calculation is large. Since the number of _Ii calculated in row processing is |N(m)|-1 excluding the node itself, the calculation of formula (18) is required |N(m)|-2 times.

ここで、Ｎ_Ｌ（ｍ）はＮ（ｍ）の最小値から昇順にＬ個まで選んだ集合である。関数ｇ（ｘ）の性質から最小値に近い値を用いるほど近似精度に対する貢献度が高くなる。 The λ-min decoding method has been proposed as a decoding method that reduces the number of calculations of equation (18). In the λ-min decoding method, only L LLRs are used for row processing calculations, and the number of calculations of equation (18) is reduced to L-1 times, thereby providing an approximation.

Here, N _L (m) is a set of L values selected in ascending order from the minimum value of N(m). Due to the nature of the function g(x), the closer a value to the minimum value is used, the greater the contribution to the approximation accuracy.

従って、

と表すことができる。ＭＳ復号法は演算量が最も少なくなるがＢＰ復号法に対する劣化が大きいことが問題となる。 Regarding the MS-based algorithm, the Min-sum (MS) decoding method, which is the simplest decoding method, is approximated as follows by ignoring g(x).

Therefore,

The MS decoding method has the smallest amount of calculation, but the degradation compared to the BP decoding method is large.

ただし、パラメータγ，εは符号の次数分布によって変わるため、符号毎に適した値を予め定めておく必要がある。 Well-known decoding methods for reducing this degradation include the Offset MS (OMS) decoding method and the Normalized MS decoding method. Both are decoding methods that correct the obtained minimum value with a constant so that it becomes a value similar to that of the BP decoding method. The OMS decoding method and the NMS decoding method use parameters γ and ε, respectively, to perform correction as follows:

However, since the parameters γ and ε change depending on the degree distribution of the code, it is necessary to determine in advance values suitable for each code.

ここで、βｍｉｎ１とβｍｉｎ２はβ_ｍ，ｎ’ ^（ｌ）の最小値と第２最小値であり、パラメータγは無視したｇ（ｘ）の項による誤差を補正するパラメータである。 The Self-Adjustable Offset MS (SAOMS) decoding method has been proposed as a decoding method that does not require parameters based on degree distribution. In the SAOMS decoding method, an approximation is performed by using only the terms of the function g(x) with a high degree of contribution as a correction value, as follows:

Here, βmin1 and βmin2 are the minimum and second minimum values of β _m,n′ ^(l) , and the parameter γ is a parameter that corrects the error due to the ignored term of g(x).

ここで、｜Ａ｜＝｜Ｎ（ｍ）｜－１である。またｍｉｎｉはβ_ｍ，ｎ ^（ｌ）の値を除く値の集合からｉ番目に小さい値を取り出す演算である。このとき、式（１８）から比較演算を取り除くことができるため、

と表すことができる。ただし、Ｊ_｜Ａ｜＜Ｊ_{｜Ａ－１｜}＜・・・＜Ｊ_２＜Ｊ_１である。式（２６）を１つの式にまとめると、

となるから更に、

と表せる。ただし、

である。ここで、ｇ（ｘ）の項をまとめて、

とおけば、

と表せる。 As an expansion of row processing of the BP decoding method, the row processing of the BP decoding method is performed recursively using equation (18). Since the operators are commutative, it is assumed that I ₁ < I ₂ < ... <I _|A|-1 <I _|A| holds in equation (10). Here, A is a set whose elements are I _i , (i ∈ [1, |N(m)|-1]). I ₁ , I ₂ , ..., I _|A| are values expressed as follows:

Here, |A|=|N(m)|-1. Also, mini is an operation to extract the i-th smallest value from a set of values excluding the value of β _m,n ^(l) . In this case, since the comparison operation can be removed from the formula (18),

Here, J _|A| < J _|A-1| < ... < J ₂ < J _1. Combining equation (26) into one equation,

Therefore,

However,

Here, the terms of g(x) are summed up as follows:

So,

This can be expressed as:

と近似できる。 The error reduction of the approximate correction value will be described. When the formula (30) is approximated as J _|A| ≈ J _|A-1| ≈ ... ≈ J ₂ ≈ J ₁ , the following is obtained:

can be approximated as follows.

のように場合分けできる。Ｉ_ｋ－Ｉ_ｌ＞Ｃのとき、Ｉ_ｋ＋Ｉ_ｌ＞Ｃであることが明らかなので、

と表せる。Ｉ_ｋ＋Ｉ_ｌ＜Ｃのとき、Ｉ_ｋ－Ｉ_ｌ＜Ｃであることが明らかなので、

と表せる。また、Ｉ_ｋ－Ｉ_ｌ≦Ｃ、Ｉ_ｋ＋Ｉ_ｌ≧Ｃのとき、

と表せる。条件式は、

と置きなおすことができる。ここで、

である。ただし、（Ｃ_＋＋Ｃ_－）／２である。このとき、式（３３）を

と表せる。式（３９）によって表せる数直線図と状態遷移図をそれぞれ図２、図３に示す。ここで、ｋにおいてＩ_ｋ＞Ｃ_＋であるとき演算を終了する場合を考える。もし、ｋ＝２においてＩ_２が０に近い場合、ｋ≧３におけるＩ_ｋの値も小さくなる可能性がある。この場合、Ｉ_ｋ＞Ｃ_＋となるまでの遷移回数が多くなるため、演算量が増大する。 Now, if we determine C such that g(C) ≈ 0, then for any k,

The cases can be divided as follows. When _{I k} -I _l > C, it is clear that I _k +I _l > C.

When _{I k} +I _l < C, it is clear that I _k -I _l < C, so

In addition, when I _k -I _l ≦C and I _k +I _l ≧C,

The conditional expression is:

Here,

Here, (C ₊ +C ₋ )/2. In this case, formula (33) is

The number line diagram and state transition diagram expressed by equation (39) are shown in Fig. 2 and Fig. 3, respectively. Consider the case where the calculation is terminated when _Ik >C ₊ at k. If _I2 is close to 0 when k=2, the value of _Ik may also become small when k>3. In this case, the number of transitions until _Ik >C ₊ increases, and the amount of calculation increases.

と表せる。このとき、ｇ（Ｉ_ｋ－Ｉ_１）＞ｇ（Ｉ_Ｋ＋１－Ｉ_１）、ｇ（Ｉ_ｋ＋Ｉ_１）＞ｇ（Ｉ_Ｋ＋１＋Ｉ_１）よりｇ（Ｉ_２－Ｉ_１）－ｇ（Ｉ_２＋Ｉ_１）が支配的になる。例えば、ｋ≧３の項をＥとおくと、

と表せる。Ｅを削減するためには、

と近似すれば良い。ただし、γ_Ｅ≧１である。この例では、ｋ≧３の項をＥと置いたが、任意に変更しても良い。 Therefore, a method for maintaining the decoding performance while reducing the amount of calculation was studied. If it is assumed that when I ₂ <C _- , I _k <C _- for k≦L ₁ , and I _k >C ₊ for k>L ₂ , then

In this case, g(I ₂ -I ₁ )-g(I _{2 +} I ₁ ) is more dominant than g(I _k -I ₁ )>g(I _K+1 -I ₁ ) and g(I _k +I ₁ )>g(I K+ ₁ +I ₁ ). For example, if the term k≧3 is E, then

In order to reduce E,

Here, γ _E ≧1. In this example, the term k≧3 is set as E, but this may be changed arbitrarily.

と表せる。このとき、ｇ（Ｉ_ｋ－Ｉ_１）＞ｇ（Ｉ_Ｋ＋１－Ｉ_１）よりｇ（Ｉ_ｋ－Ｉ_１）が支配的になる。例えば、ｋ≧３の項をＥ’とおくと、

と表せる。Ｅ’を削減するためには、

と近似すれば良い。ただし、γ_Ｅ’≧１である。この例では、ｋ≧３の項をＥ’と置いたが、任意に変更しても良い。誤差の削減による効果を模式的に表すと図４のように表せる。 In addition, when C _- ≦I ₂ ≦C ₊ , if it is assumed that I _k >C ₊ when k >L ₂ , then

In this case, g(I _k -I ₁ ) is more dominant than g(I k -I ₁ )>g(I _{K +1} -I ₁ ). For example, if the term k≧3 is E', then

In order to reduce E',

Here, γ _E′ ≧1. In this example, the term k≧3 is set as E′, but this may be changed arbitrarily. The effect of reducing the error can be represented diagrammatically as shown in FIG. 4.

図１は式（４６） に従った演算を示すフローチャートである。 In this case, equation (32) can be approximated as follows:

FIG. 1 is a flow chart showing the calculation according to equation (46).

を用いる。ここで、Ｃ’、Ｄは定数であり、０＜Ｃ’≦１、０＜Ｄ≦１である。例えば、Ｃ’＝０．９、Ｄ＝１／２やＣ’＝０．６２５、Ｄ＝１／４のように組み合わせることができる。式（４７）は次のように別の形で表すことができる。

ここで、Ｃ＝Ｃ’／Ｄである。Ｉ_２＜Ｃ_－のとき、

と表すことができる。また、Ｃ_－≦Ｉ_２≦Ｃ_＋のとき、

と表すことができる。このとき、式（４６）は次のように近似できる。

Consider the case where g(x) is replaced with an approximation suitable for implementation. In this application, the approximation of g(x) is as follows:

Here, C' and D are constants, 0<C'≦1, 0<D≦1. For example, combinations such as C'=0.9, D=1/2 or C'=0.625, D=1/4 are possible. Equation (47) can be expressed in another form as follows:

Here, C=C'/D. When I ₂ <C _- ,

In addition, when C ₋ ≦I ₂ ≦C ₊ ,

In this case, the formula (46) can be approximated as follows:

このとき、式（５１）を次のように近似できる。

ここで、

であり、

である。 In formula (25), the values I ₁ , I ₂ , ..., I _|A| are arranged in ascending order from the set of values excluding the value of β _{m,n (} ^l) , so I ₁ , I ₂ , ..., I _|A| must be reselected every time n changes. Therefore, the values I ₁ ', I ₂ ', ..., I _|B| ' are arranged in ascending order from the set of values including the value of β m, ^{n (l)} . Here, B is a set whose elements are I' _i (i∈[1, |N(m)|]). In this case, I' ₁ , I' ₂ , ..., I' _|B| are expressed as follows:

In this case, equation (51) can be approximated as follows:

Where:

and

It is.

とすると、

と表すことができる。 Next, the implementation in a decoder will be described.
The minimum value found in row processing has only two values, excluding the sign. Let min1 be the minimum value of |β ^(l) _m,n' | of all variable nodes n' ∈ N(m) connected to check node m, and min2 be the second minimum value. Let the index of min1 be

Then,

It can be expressed as:

と表すことができる。 Using the fact that the sign of α _m,n ^(l) is sign(β _m,n′ ^(l) )·sign(β _m,n ^(l) )=1,

It can be expressed as:

と表すことができる。 Furthermore, when the sign bit of equation (58) is expressed as b _m,n ^(l) =sign(β _m,n ^(l) ),

It can be expressed as:

は次の再帰的な性質

を持ち、

はＸＯＲ演算を表す。従って、α_ｍ，ｎ ^（ｌ）の符号はＸＯＲ演算をシリアルに実行することで得ることができる。 Where:

has the following recursive property:

With

represents an XOR operation. Therefore, the sign of α _m,n ^(l) can be obtained by serially performing XOR operations.

An example of the decoder configuration of this method is shown in Figure 6. The column processing calculation unit performs calculations according to equation (4). That is, the column processing value β m _,n ^(l ) is calculated by subtracting the row processing value α _m,n ^(l-1) output from the row processing output unit from the a posteriori LLR _{β n} ^(l-1) .

The row processing input unit inputs β _m,n' ^(l) of all variable nodes n' ∈ N(m) connected to check node m to the absolute value calculation unit and the sign extraction unit. The row processing input unit also has a FIFO, which inputs β _m,n ^(l) of variable node n to the sign extraction unit and the a posteriori LLR calculation unit in order.

The absolute value calculation section calculates |β _m,n' ^(l) |, and the minimum value search section finds up to L values min1, min2, . . . minL and index n _minl of minl arranged in ascending order from the minimum value from |β _m,n' ^(l) |.

The minimum value selection unit performs a calculation according to equation (57). That is, when n=n _min1 , min2 is selected, and when n≠n _min1 , min1 is selected.

The constant value calculation section, the correction value calculation section, and the correction value selection section perform calculations according to the flow chart in Fig. 1. The constant value calculation section calculates _min1C- and C+.

The correction value calculation unit calculates correction values γ _E 2Dmin1 and γ _E' D(C ₊ -min2) from min2, C _- , and C+. For example, when γ _E =3/2 and D=1/4, it is obtained by adding min1/min2 and the result of shifting that result one bit to the right. Also, when γ _E' =3/2 and D=1/4, it is obtained by adding the result of shifting (C ₊ -min2) two bits to the right and the result of shifting that result another bit to the right.

The correction value selection section selects the result obtained in the correction value calculation section from min2, C _- , and C+.

The sign extraction section extracts the sign bit b m,n' ^(l) from β _{m ,n'} ^(l) and the sign bit b m,n ^(l) from β _{m, n} ^(l) output from the FIFO.

The sign calculation unit performs a calculation according to equation (59). That is, a sign bit is obtained by performing an XOR operation on b _m,n′ ^(l) recursively and the result obtained by the XOR operation on b _m,n ^(l) .

The row processing output unit calculates α _m,n ^(l) from the outputs of the minimum value selection unit, the correction value selection unit, and the code calculation unit. The row processing calculation unit has a RAM, which inputs α _m,n ^(l) to the column processing calculation unit at the next iteration number l+1. The post-LLR calculation unit performs calculation according to equation (6). That is, β _m,n ^(l) output from the FIFO is added to α _m,n ^(l) to calculate β _n ^(l) .

Next, a BER evaluation was performed by computer simulation using the ISDB-S3 LDPC code. As a simulation model, QPSK modulation and an AWGN communication channel were set, and the coding rate used for the evaluation was R = 2/3. 10,771,200 bits were used to evaluate the pseudo error-free characteristics at BER = 10 ^-7 , and the maximum number of iterations in decoding was set to 50.

FIG. 7 shows the BER characteristics of each decoding method. The BP decoding method and the LBP decoding method were evaluated using floating-point arithmetic. For the other decoding methods, variables must be quantized due to memory length limitations in implementation, so the LLR and the extrinsic LLR were quantized as 6-bit signed absolute values, and the a posteriori LLR was quantized as 8-bit signed absolute values for evaluation. The parameters of each decoding method were ε=0.125 for the OMS decoding method, γ=0.875 for the NMS decoding method, and γ=0.125 for the Seif-Adjustable OMS decoding method. For the proposed method, γ _E =3/2, γ _E' =3/2, C=2.5, and D=1/4 were used. The case where L=2 was also evaluated using Δ(x). All the simple decoding methods were evaluated using serial scheduling. It can be seen that the proposed method can obtain higher decoding performance than the conventional method.

As shown in the characteristics in Figure 7, we proposed a decoding algorithm that achieves both high decoding performance and low complexity. Computer simulations confirmed that the proposed method achieves higher decoding performance than conventional methods.

As a result, the invention of Example 1 has the advantage of being able to reduce the amount of calculation required for the correction formula, reduce errors by adjusting the correction formula, and suppress degradation of decoding performance.

In Example 2, we propose a decoding algorithm that combines high decoding performance and low complexity as a probabilistic numerical search and numerical correction method. The decoding algorithm simplifies the formulas that appear in a BP-based manner and adaptively adjusts the formulas. Computer simulations have confirmed that the proposed method achieves higher decoding performance than conventional methods.

ここで、ＮＬ（ｍ）はＮ（ｍ）の最小値から昇順にＬ個まで選んだ集合である。
｜Ｎ（ｍ）｜個から最小値などの極値を探索するには一般に｜Ｎ（ｍ）｜－１回の比較を要する。探索ツリーの例を図８に、ツリーに用いられる比較器を図９（ａ）に示す。 Since the number of _Ii calculated in row processing is |N(m)|-1 excluding the node itself, the calculation of equation (18) is required |N(m)|-2 times. The λ _-min decoding method has been proposed as a decoding method that reduces the number of calculations of equation (18). In the λ _-min decoding method, only L LLRs are used for the calculation of row processing, and the number of times equation (18) is calculated can be reduced to L-1 times.

Here, NL(m) is a set of up to L values selected in ascending order from the minimum value of N(m).
Searching for an extreme value such as a minimum value from |N(m)| items generally requires |N(m)|-1 comparisons. An example of a search tree is shown in Figure 8, and a comparator used in the tree is shown in Figure 9(a).

There are two types of search trees: sequential search trees, which perform comparisons serially as shown in Figure 8, and tournament search trees, which perform comparisons in parallel. When using these search trees, L(|N(m)|-1) comparisons are required to search for L values, so methods have been proposed that perform searches with a smaller number of comparisons. The proposed search trees are shown in Figures 10 and 11, and the comparators used in the trees are shown in Figure 9. This allows for a large number of values to be searched for while significantly reducing the number of comparisons, but the problem is that the accuracy rate is low.

In the λ _-min decoding method of the second embodiment, the number of comparators used in the search increases in proportion to the number of values used in the decoding. Although a method for searching with a small number of comparisons has been proposed, the decoding performance deteriorates when the accuracy rate is low. Therefore, we propose a method for searching with high accuracy while suppressing the number of comparisons, and a method for correcting values that are considered to be erroneous.

Next, we will explain the configuration of the numerical searcher. There are two methods of numerical search: sequential search and tournament search. In sequential search and tournament search, all input values are compared, so at least one desired numerical value is always obtained. Let us denote the L LLRs obtained by numerical search in ascending order from the minimum value as min1, min2, ..., Lth-min.

The case where L=4 will be explained. The configuration of the proposed numerical searcher is shown in Fig. 12. The processing flow in each part is shown below. Here, the input to the search tree is {x _l } (l ∈ [1|N(m)|]).

(1) min1 is found from {x _l } by the sequential search section.

(2) The value {y _{l '} } (l ' ∈ [1 | N (m) | -1]) other than min1 by the sorting unit 1
Rearrange the items.

(3) The tournament search unit finds 2nd to min4 from {y _l' }. The tournament search unit has two tournament blocks. One tournament block finds min2, and the other finds min3 or min4.

(4) The auxiliary search unit finds min3 or min4 from the value {z ₁ , z ₂ } that was not last selected in each tournament block.

(5) The values obtained by the tournament search unit and the auxiliary search unit are sorted by sorting unit 2 to obtain min2 to min4.

(6) The correction unit corrects the values of min3 and min4.

This numerical searcher searches for one value in the sequential search section, two in the tournament search section, and one in the auxiliary search section. The sequential search section corresponds to a sequential search tree, while the tournament search section and the auxiliary search section correspond to tournament search trees. As two search trees are used, min1 and min2 can always be found. However, min3 and min4 may not be the true third and fourth values when a full sort is performed, so the search accuracy of min3 and min4 is improved by rearranging the values using the properties of the sequential search section.

In addition, the more values are input to the search tree, the more the search accuracy of min3 and min4 deteriorates, so at the end we have a correction section that corrects the values of min3 and min4. First we explain the method for improving search accuracy, and then we explain how to correct the values.

We will explain sorting that takes advantage of the properties of the sequential search unit. In the sequential search unit, the output of a binary comparison is repeatedly input to the next binary comparison, so the later the output, the more likely it is that smaller values will appear. When a serial number is given to the output of the sequential search unit, the mode and frequency for the serial number are as shown in Figure 13. We can see that the larger the serial number, the higher the rate of appearance of small values.

As can be seen from Figure 13, y4, y5, y6, and y7 are the ones that frequently produce small values in the output of the sequential search unit. To improve the search accuracy of min3 and min4, it is desirable to configure the tournament search unit so that small values are not compared with each other. Therefore, the tournament search unit rearranges the values before inputting them to the comparator so that small values are compared with large values. Let the input to the tournament search unit be {y _l' } (l' ∈ [1|N(m)|-1]).

(A) Divide {y _{l '} } into odd-numbered elements y _i (i=2k+1) and even-numbered elements y _j (j=2k+2).

(B) Divide {y _l } into elements y _i1 (i ₁ =4k+1) and y _i2 (i ₂ =4k+3), and divide {y _j } into elements y _j1 (j ₁ =4k+2) and y _j2 (j ₂ =4k+4).

(C) Let [{y _i1 },{y _i2 }] and [{y _j1 },{y _j2 }] be the inputs to each tournament block, where if the number of elements in [{y _i1 },{y _i2 }] or [{y _j1 },{y _j2 }] is odd, then a seed slot is generated for the tournament.

Here, k = 0, 1, 2, .... After sorting, each tournament block compares pairs of two elements. For simplicity, we will explain with |N(m)| = 8.

In (A), divide the |N(m)|-1 numbers {y1, y2, ... y7} into odd-numbered elements {y1, y3, y5, y7} and even-numbered elements {y2, y4, y6}.

In (B), {y1, y3, y5, y7} is further divided into {y1, y5} and {y3, y7}, and {y2, y4, y6} is divided into {y2, y6} and y4.

In (C), {y1, y5, y3, y7} and {y2, y6, y4} are input to each tournament block. However, in the tournament block where {y2, y6, y4} is input, y4 becomes the seed slot.

Figure 14 shows an example of a search tree when the input is sorted using this method. To sort the output of the search tree in ascending order from the smallest value, use sorting unit 2 in Figure 15. Figure 16 shows a flowchart from input to the search tree to output to the decoder.

Figures 15 and 16 show the results of comparing search accuracy when the input is not swapped, when the input is randomized, and when the input is swapped using the proposed method. The accuracy of min1 and min2 is 100% for both methods. The accuracy of the proposed method for min3 and min4 was improved by up to 5.4% and 7.2%, respectively, compared to the other methods.

Table 1 shows the results of comparing the proposed method with the existing method in terms of search accuracy and number of comparators. However, |N(m)| = 8, the number of trials was 10,000, and the values were rounded down to the second decimal place. The existing method is a search tree that originally seeks 1st to min3, but for comparison, the accuracy was sought up to min4. The proposed method, with the same number of comparators as approximation method 2, improved the accuracy of min3 and min4 by 4.3% and 11.6%, respectively.

とすると，

と表すことができる。一方、行処理で求めるｇ（ｘ） は，

と表すことができる。ただし，ｋ≧２である。提案手法は式（６５）は正しく得られるが、
ｋ≧３の場合に式（６６）は近似値となる可能性がある。ｍｉｎ３、ｍｉｎ４が誤まって得られる確率が高い値は、図１７、図１８より、それぞれフルソートした場合の本来の４，５ 番目の値である。また、４、５番目の値に間違える確率は｜Ｎ（ｍ）｜が大きいほど高くなる。このとき、ｇ（ｘ）の値が０に近づくため、計算コストに対する性能向上への貢献度は小さくなる。 Next, the correction of outliers will be described.
The minimum value found in row processing has only two values, excluding the sign. Let min1 be the minimum value of |β _m,n' ^(l) | of all variable nodes n' ∈ N(m) connected to check node m, and min2 be the second minimum value. Let the index of min1 be

Then,

On the other hand, g(x) obtained by row processing is

where k≧2. The proposed method correctly obtains equation (65), but
When k≧3, formula (66) may be an approximation. As shown in FIG. 17 and FIG. 18, the values that are most likely to be obtained by mistake in min3 and min4 are the true 4th and 5th values in full sorting. The probability of mistaking the 4th and 5th values increases as |N(m)| increases. In this case, the value of g(x) approaches 0, so the contribution to performance improvement relative to calculation cost decreases.

ｍｉｎ３’、ｍｉｎ４’は処理後の値である。ここで、Ｃ_３’、Ｃ_４’はｍｉｎ２＜ｍｉｎ３－Ｃ_３’＜ｍｉｎ３、ｍｉｎ３＜ｍｉｎ４－Ｃ_４’＜ｍｉｎ４となるような定数である。
例えば，

のように与えることができる。γ_３’、γ_４’はスケール因子である。ｍｉｎ３’、ｍｉｎ４’で補正する場合のフローチャートを図１９に示す。 Therefore, if min3 and min4 are considered to be outliers that exceed a specific value, they are judged to be errors and corrections are made. Assume that the outliers of min3 and min4 are min3> _X3 + _E3 and min4> _X4 + _E4 , respectively. Here, _X3 and _X4 are the average values of the original third and fourth values when fully sorted, respectively, and can be obtained in advance by simulation or the like. Also, _E3 and _E4 can be obtained in advance as _E3 =( _X4 - _X3 )/2 and _E4 =( _X5 - _X4 )/2, respectively. If min3 and min4 are outliers, the following processing is performed.

min3' and min4' are the values after processing, where C3 _' and C4 _' are constants such that min2<min3-C3 _' <min3 and min3<min4-C4 _' <min4.
for example,

where γ _3′ and γ _4′ are scale factors. A flowchart for performing correction using min3′ and min4′ is shown in FIG.

ここで、ｍｉｎ３’’、ｍｉｎ４’’は処理後の値である。ここで、Ｃ_３’’＞Ｃ_３’、Ｃ_４’’＞Ｃ_４’であり、ｍｉｎ２＜ｍｉｎ３－Ｃ_３’’＜ｍｉｎ３、ｍｉｎ３＜ｍｉｎ４－Ｃ_４’’＜ｍｉｎ４となるような定数である。例えば、

のように与えることができる。γ_３’、γ_４’はスケール因子である。ｍｉｎ３’’、ｍｉｎ４で補正する場合のフローチャートを図２０に示す。 Furthermore, if min2 is a value smaller than normal, there is a high probability that min3 and min4 will also be small values. In this case, when min3 and min4 are determined to be outliers, the error will be very large. Therefore, the following process is further performed.

Here, min3″ and min4″ are the values after processing. Here, C3 _″ > _C3′ , C4 _″ >C4 _′ , and min2<min3- _C3″ <min3, and min3<min4- _C4″ <min4 are constants. For example,

where γ _3′ and γ _4′ are scale factors. A flowchart for the case of correction using min3″ and min4 is shown in FIG.

In Example 2, we proposed a method for performing a numerical search with a small number of comparisons. We confirmed that when the proposed method was combined with other decoding methods, there was almost no degradation in decoding performance.

The effects of the invention of the second embodiment include reducing the number of comparisons required for a numerical search, suppressing the deterioration of search accuracy due to the reduction in the number of comparisons, and improving search accuracy by correcting outliers.

と表される。ここで。ｂ_ｉ＝０であるレプリカシンボルの集合をＳ_０、ｂ_ｉ＝１であるレプリカシンボルの集合をＳ_１とし、通信路を分散σ^２のＡＷＧＮ（Ａｄｄｉｔｉｖｅ Ｗｈｉｔｅ Ｇａｕｓｓｉａｎ Ｎｏｉｓｅ）通信路と仮定している。式（７１）は指数和を含むため演算が複雑となり、σ^２が非常に小さい場合にアンダーフローやオーバーフローが生じる。そこで、Ｍａｘ－ｌｏｇ近似による近似式

を利用する場合がある。変調方式をＢＰＳＫまたはＱＰＳＫとすると、ＬＬＲ は

となる。ＱＰＳＫの場合はＩＱ平面の各相に割り当てられたビットに対してＬＬＲが求められる。 In the third embodiment, a method of scaling the LLR and the correction value will be described.
From equation (1), the LLR of bit b _i assigned to the transmission symbol x is

Here, the set of replica symbols where _{b i} =0 is S ₀ , the set of replica symbols where b _i =1 is S ₁ , and the communication channel is assumed to be an AWGN (Additive White Gaussian Noise) channel with variance σ ^2. Since equation (71) includes an exponential sum, the calculation becomes complicated, and underflow or overflow occurs when σ ² is very small. Therefore, an approximation equation using Max-log approximation is used.

If the modulation method is BPSK or QPSK, the LLR is

In the case of QPSK, the LLR is calculated for the bits assigned to each phase of the IQ plane.

と近似できる。式（７４）は２／σ^２で正規化した場合と等価であるため、正規化係数を

とおき、式（７２）についても正規化すると、

と近似できる。また、

と更に近似してもよい。 When the decoder is implemented in fixed-point, the dynamic range of the LLR is finite, so that underflow or overflow occurs when σ ² is very small. Therefore, if σ ² is constant, we can write Equation (73) as

Since equation (74) is equivalent to the case where it is normalized by 2/σ ² , the normalization coefficient is

Then, equation (72) is also normalized as follows:

It can be approximated as follows.

It may be further approximated as:

と表すことができる。ｇ（ｘ）はλ_ａ、λ_ｂの和と差により計算されるが、近似ＬＬＲを使用する場合は和と差の大きさが変化する。近似ＬＬＲが近似前よりも小さくなる場合、ｍｉｎ（Ａ，Ｂ）の大きさは近似前より小さくなり、ｇ（ｘ）の大きさは近似前よりも大きくなる。対して、近似ＬＬＲが近似前よりも大きくなる場合、ｍｉｎ（Ａ，Ｂ）の大きさは近似前より大きくなり、ｇ（ｘ）の大きさは近似前よりも小さくなる。この場合、ｍｉｎ（Ａ，Ｂ）がｇ（ｘ）により正しく補正されないため、復号性能が劣化する場合がある。 When the approximate LLR is used, the ratio of min(A, B) and g(x) in formula (14) may change significantly. For simplicity, an example will be given of the initial stage of decoding. When l=0, β _n ⁽⁰⁾ =λ _n , so β _m,n ⁽⁰⁾ =λ _n . In this case, formula (14) becomes:

g(x) is calculated by the sum and difference of λ _a and λ _b , but the magnitude of the sum and difference changes when the approximated LLR is used. When the approximated LLR becomes smaller than before the approximation, the magnitude of min(A, B) becomes smaller than before the approximation, and the magnitude of g(x) becomes larger than before the approximation. On the other hand, when the approximated LLR becomes larger than before the approximation, the magnitude of min(A, B) becomes larger than before the approximation, and the magnitude of g(x) becomes smaller than before the approximation. In this case, min(A, B) is not correctly corrected by g(x), so the decoding performance may deteriorate.

を用いる。Ｃ、Ｄはそれぞれ傾きと切片であり、０＜Ｃ＜１、０＜Ｄ＜１である。例えば、Ｃ＝０．９、Ｄ＝１／２やＣ＝０．６２５、Ｄ＝１／４のように組み合わせることができる。このとき、式（１４）を、

と近似できる。 A method for maintaining the ratio of min(A, B) and g(x) as much as possible even if the scale of the LLR is changed due to the approximation of the LLR or bit precision will be described. Here, the approximate LLR calculated by the formula (74) or the formula (76) is used. Also, as an approximation formula of the function g(x),

where C and D are the slope and intercept, respectively, and 0<C<1 and 0<D<1. For example, combinations such as C=0.9, D=1/2 or C=0.625, D=1/4 can be used. In this case, formula (14) can be rewritten as follows:

can be approximated as follows.

により、γ_ｑλ_ｉ∈［－２^ｑ－１２^ｑ－１］としてスケール変換する。ここで、近似前のＬＬＲをγ_ｓλ_ｉとし，スケール変換後のＬＬＲをγ_ｑλ_ｉとすると、その比は、

と表すことができる。式（７４）や式（７７）を用いるとき、γ_ｓは計算されないため、

と近似できる。ここで、σ＾^２ はＢＥＲ（Ｂｉｔ Ｅｒｒｏｒ Ｒａｔｅ）＝０となるＣＮＲ（Ｃａｒｒｉｅｒ－ｔｏ－Ｎｏｉｓｅ Ｒａｔｅ）から求められる分散である。
このとき、式（８０）は、

のように表される。このスケール変換はγ_ｃ＞１の場合にのみ行うγ_ｃ＞１の場合のｍｉｎ（Ａ，Ｂ）とｇ（ｘ）のスケール変換の模式図を図２１に示す。この例では式（７４）のみを示す。γ_ｃ＞１となる場合は、変調多値数が小さいときに起こりえる。変調多値数が小さい場合、ほとんどのビットのＬＬＲがλ_{ｉ，ｍａｘ}＜２^ｑ－１となる。そこで、ＬＬＲを２^ｑ－１までスケールアップし、ｇ（ｘ）も適切にスケールアップすることで、比を保持したままダイナミックレンジを広げる。 When the modulation method is multi-level, the LLR of each bit assigned to the transmission symbol is calculated. The LLR of bit b _i of the transmission symbol is represented as λ _i , and the maximum possible LLR value of b _i is represented as λ _i,max . The maximum value of λ _i,max is represented as λ _max . When the LLR is quantized as a signed absolute value of q bits,

Here, if the LLR before approximation ^is γ _s λ _i and the LLR after ^the scale transformation is γ _{q λ i ,} the ratio is

When using equation (74) or equation (77), γ _s is not calculated, so

Here, σ^ ² is the variance calculated from the CNR (Carrier-to-Noise Rate) at which BER (Bit Error Rate)=0.
In this case, equation (80) becomes:

This scale conversion is performed only when γ _c > 1. A schematic diagram of the scale conversion of min(A, B) and g(x) when γ _c > 1 is shown in FIG. 21. In this example, only formula (74) is shown. The case where γ _c > 1 occurs when the modulation multi-level number is small. When the modulation multi-level number is small, the LLR of most bits becomes λ _i,max < 2 ^q-1 . Therefore, by scaling up the LLR to 2 ^q-1 and also appropriately scaling up g(x), the dynamic range is expanded while maintaining the ratio.

のように表される。γ_ｃ≦１の場合のスケール変換の模式図を図２２に示す。γ_ｃ≦１となる場合は、変調多値数が大きいときに起こりえる。変調多値数が大きい場合、λ_{ｉ，ｍａｘ}≧２^ｑ－１となるビットが増加する。ＬＬＲが大きいとき、ｍｉｎ（Ａ，Ｂ）に対するｇ（ｘ）の大きさが非常に小さくなる。そのため、λ_{ｉ，ｍａｘ}≧２^ｑ－１となるビットｂ_ｉのＬＬＲは重要になりにくい。また、λ_ｉ≧２^ｑ－１となる可能性も高いため、スケールアップしてもほとんどの場合クリップされる。そこで、λ_{ｉ，ｍａｘ}＜２^ｑ－１となるビットｂ_ｉのＬＬＲに対してスケールアップを適切に行うことで、特定のビットのＬＬＲのみダイナミックレンジを広げる。 On the other hand, when γ _c ≦1, a scale conversion different from the above is performed. The approximate LLR is scaled as γ _M λ _i by γ _M , and clipped at 2 ^q−1 . Different values can be used for γ _M depending on the modulation multi-level number. However, from the coefficients of equations (76) and (77), 1≦γ _M ≦1/4 is set. Scale conversion of g(x) is not performed. In this case, equation (78) becomes

It is expressed as follows. A schematic diagram of scale conversion in the case of γ _c ≦1 is shown in FIG. 22. When γ _c ≦1 occurs when the modulation multi-level number is large. When the modulation multi-level number is large, the number of bits for which λ _i,max ≧2 ^q-1 is increased. When the LLR is large, the magnitude of g(x) for min(A,B) becomes very small. Therefore, the LLR of bit b _i for which λ _i,max ≧2 ^q-1 is not likely to be important. In addition, since there is a high possibility that λ _i ≧2 ^q-1 is satisfied, even if scaled up, it is clipped in most cases. Therefore, by appropriately performing scale up on the LLR of bit b _i for which λ _i,max <2 ^q-1 is satisfied, the dynamic range of only the LLR of a specific bit is expanded.

The absolute magnitude of the LLR varies depending on transmission parameters such as the modulation method, mapping method, and coding rate, and furthermore, when the decoder is implemented in hardware, the dynamic range of the LLR is finite. Therefore, it is necessary to adjust the LLR and C in equation (80) according to the transmission parameters and bit precision. In Japan, the OFDM method used for television broadcasting and material transmission allows the setting of transmission parameters such as the modulation method, mapping method, and coding rate, and the transmission parameters are added to the TMCC (Transmission and Multiplexing Configuration and Control) signal. Figure 23 shows the configuration when adjusting the LLR and C using the TMCC transmission parameters, and Figure 24 shows the flowchart.

The operation control unit reads the parameters corresponding to the transmission parameters contained in the TMCC signal from the table, and then outputs the parameters to the probability information calculation unit and the row processing unit of the LDPC decoder. The table stores parameters associated with the modulation method, mapping method, and coding rate. It is also possible to realize this by putting the LLR after scale conversion into a table.

In Example 3, we proposed a method for scaling LLRs to suppress degradation of decoding performance with limited bit precision, and a method for scaling decoding parameters in accordance with the scaled LLRs. We confirmed that when the proposed method is combined with other decoding methods, there is almost no degradation in decoding performance.

Currently, in Japan, efforts are being made to further improve the resolution of television broadcasting and material transmission. In order to achieve the transmission of high-resolution video, the number of modulation levels is being increased to increase capacity, and high reliability is being achieved by using NUC (Non-Uniform Constellation) with non-uniform signal point arrangement and LDPC codes with high error correction capabilities. LDPC codes perform decoding using the LLRs of bits assigned to signal points, but when the signal point interval changes due to changes in the number of modulation levels or mapping method, the bit precision of the LLRs required to maintain decoding performance may also change. Therefore, in the third embodiment, we propose a method of scaling LLRs to suppress degradation of decoding performance with limited bit precision, and a method of scaling decoding parameters corresponding to the scaled LLRs. It has been confirmed that when the proposed method is combined with other decoding methods, there is almost no degradation in decoding performance.

The effect of the third embodiment is that it can suppress the degradation of decoding performance and can respond to changes in transmission parameters.

と表される。 Next, an evaluation will be performed when the methods of each embodiment are combined.
LDPC codes are codes defined by a check matrix with very few non-zero matrix elements. BP decoding, a common decoding method for LDPC codes, consists of two operations: row processing for each row of the check matrix and column processing for each column. Of these, the row processing in BP decoding is as follows:

This is expressed as:

The biggest problem with LDPC codes is the implementation of row processing. Because the equation for row processing contains complex functions, the functions must be tabulated in order to implement it. In addition, the amount of calculations required is also an issue because recursive calculations are required. To solve this problem, various simplified decoding methods have been proposed. Simple decoding methods can be broadly divided into BP-based algorithms based on BP decoding and MS-based algorithms based on Min-sum (MS) decoding. BP-based simplifies the method by approximating logarithmic functions. However, the amount of calculations remains high because recursive calculations remain.

On the other hand, MS-based simplifies the process by correcting the minimum value obtained by min(A, B) with parameters. However, it is necessary to predetermine suitable parameters for each code, and even if optimal parameters are set, the decoding performance deteriorates.

As such, BP-based has high decoding performance but requires a large amount of calculations, while MS-based requires parameter setting, which results in poorer decoding performance but requires less calculations. Therefore, the purpose of this research is to provide a new decoding algorithm that combines the advantages of both BP-based and MS-based.

The proposed methods can be classified into several categories. Figure 25 shows the relationship between each process of decoding LDPC codes and each embodiment. The effects obtained by the proposed method of each embodiment are as follows.
(Embodiment 1) A method for reducing errors in approximate correction values (reducing the amount of calculations and improving decoding performance).
(Example 2) Probabilistic numerical search and numerical correction method (reduction of the amount of calculation).
(Embodiment 3) Scale conversion method for LLR and correction value (improvement of decoding performance, support for multi-level modulation and mapping method).
Here, (Example 1) is an algorithm relating to a method for calculating x, (Example 2) is a search algorithm relating to the numerical values used in the calculation of x, and (Example 3) is a method for calculating LLR and g(x).
For the sake of convenience, in the evaluation, Example 1 is represented as A2, Example 2 is represented as A3, and Example 3 is represented as A4. The BER characteristics of A2+A4 are shown in Figures 26 and 27. Figure 26 shows the case of QPSK, R=3/4, and Figure 27 shows the case of 1024QAM, R=2/3.

The evaluation was carried out when the examples were combined.
The parameters of A2 were γ _E =3/2, γ _E' =3/2, C=2.5, and D=1/4.
The parameters of A3 were set as γ ₃ =1/8, γ ₄ =1/4, γ _3' =1, and γ _4' =5/8.
The parameters of A4 are q=6 and γ _M =1/2.

The evaluation results show that the parameters need to be optimally determined through prior simulations, but depending on the settings, decoding performance that exceeds that of DM decoding and SAOMS decoding can be obtained. The amount of calculation is about the same as that of SAOMS decoding.

As a result, A2 can be said to be a decoding algorithm that requires parameter settings that have decoding performance equal to or better than BP-based, while still requiring a computational load that can be considered MS-based.

The present invention can achieve both high composite performance and low complexity, so that the required CNR of the LDPC decoder, which is necessary for further increasing the resolution of television broadcasting and material transmission, can be reduced. Therefore, the present invention can be applied to various types of decoders that use error correction.

Claims (2)

In a decoding method for decoding a codeword encoded by an LDPC code, a formula of a BP-based algorithm based on a BP decoding method is simplified, and an error caused by the simplification is reduced ,

After determining C such that g(C) ≒ 0, for any k,

Then,

Then, when Ik>C+, the calculation is terminated to reduce the amount of calculation while maintaining the decoding performance.

To replace
13. A method for adaptively scaling correction values in decoding, comprising: A decoder having a column processing calculation unit, a row processing input unit, an absolute value calculation unit, a sign extraction unit, a sign calculation unit, a minimum value search unit, a minimum value selection unit, a constant value calculation unit, a correction value calculation unit, a correction value selection unit, a row processing output unit, and a post-LLR calculation unit,
A decoder that simplifies the formula of a BP-based algorithm based on the BP decoding method and reduces the error caused by the simplification is as follows:

After determining C such that g(C) ≒ 0, for any k,

Then,

Then, when Ik>C+, the calculation is terminated to reduce the amount of calculation while maintaining the decoding performance.

To replace
13. An adaptive scaling decoder for a correction value in decoding, comprising:

Images