Method for decoding inertia-effect bit-flip LDPC codes

Abstract

A method for decoding a Low Density Parity Check code. At each decoding iteration, as long as the syndrome of the estimated word indicates an error, a set ({tilde over (F)}) of the least reliable bits of the word is determined as those where the value of a local energy function ({tilde over (E)}.sub.n) is less than a threshold value. The local energy value of a bit includes a first component proportional to the correlation between this bit and a sample corresponding to the observed signal, a second component representing the number of non-satisfied constraints wherein the bit acts, and a third component decreasing with the number (.sub.n) of iterations made since the last flipping of this bit. The bits of the estimated word belonging to this set are flipped, where applicable with a predetermined probability, to provide a new estimated word at the following iteration.

Claims

1. A method for decoding, in a communication system, a received LDPC code represented by a Tanner graph comprising N variable nodes and M control nodes, each control node being associated with a parity constraint relating to a plurality of variable nodes, the method comprising: performing, by processing circuitry, successive iterations, each iteration including determining an estimated word from an observable representing a word to be decoded; when determining that the estimated word is not a code word, determining a set of least reliable bits of the estimated word to be flipped before a following iteration, the least reliable bits of the estimated word being determined as those where a value of a local energy function of a bit is less than a threshold value, the local energy function of the bit comprising a first term proportional to a correlation between the bit and a corresponding element of the observable, a second term representing a number of non-satisfied constraints in which the bit is involved, and an inertial term that decreases with a number of iterations performed since a last flipping of the bit, and flipping bits in the estimated word based on the determined least reliable bits: and when determining that the estimated word is a code word, outputting the estimated code word as a decoded LDPC code word.

2. The method for decoding an LDPC code according to claim 1, further comprising flipping each bit in the set of least reliable bits before the following iteration.

3. The method for decoding an LDPC code according to claim 1, further comprising flipping each bit in the set of least reliable bits with a predetermined probability p, 0<p<1, before the following iteration.

4. The method for decoding an LDPC code according to claim 1, wherein, the step of determining the set of least reliable bits comprises adding a random noise of predetermined variance to the value of the local energy function before comparison with said threshold value.

5. The method for decoding an LDPC code according to claim 1, further comprising determining the threshold value from the minimum value of the local energy function on the bits of the estimated word, increased by a predetermined margin δ≥0.

6. The method for decoding an LDPC code according to claim 1, wherein the threshold value is adaptive and is a function of a total number of iterations implemented since a start of decoding.

7. The method for decoding an LDPC code according to claim 1, wherein the inertial term of the local energy function of the bit is a decreasing linear function of the number of iterations implemented since the last flipping of the bit.

8. The method for decoding an LDPC code according to claim 1, wherein the inertial term of the local energy function of the bit is a linear function defined piecewise.

9. The method for decoding an LDPC code according to claim 1, wherein the local energy function of the bit is zero beyond a predetermined number L of iterations.

10. The method for decoding an LDPC code according to claim 9, further comprising initializing the number of iterations implemented since the last flipping of the bit to a value I.sub.max≥L, the number being set to zero as soon as said bit is flipped, and incremented at each iteration until said value L is reached.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Other features and advantages of the invention will emerge from reading a preferential embodiment of the invention described with reference to the accompanying figures, among which:

(2) FIG. 1 shows schematically a flow diagram of a GDBF decoding method for decoding an LDPC code, known from the prior art;

(3) FIG. 2 shows schematically a flow diagram of a method for decoding an LDPC code according to one embodiment of the present invention;

(4) FIGS. 3A and 3B illustrate the performances of decoding methods of the GDBF type known from the prior art and of a decoding method according to an embodiment of the present invention, in the case of a binary symmetric channel, respectively for a first and for a second example of an LDPC code;

(5) FIGS. 4A and 4B illustrate the performances of decoding methods of the GDBF type known from the prior art and of a decoding method according to an embodiment of the present invention in the case of an AWGN channel, respectively for a first and for a second example of an LDPC code.

DETAILED DESCRIPTION OF PARTICULAR EMBODIMENTS

(6) We shall consider hereinafter a method for GDBF decoding of an LDPC code, in the form of a randomised variant such as PGDBF or NGDBF, as described in the introductory part.

(7) The idea at the basis of the invention is to add an inertial component to the local energy function. The purpose of this component is to reduce the probability of a bit being flipped if it has already recently been flipped during a previous iteration. In other words, an inertia effect is introduced obliging the iterative decoding algorithm to seek the maximum of the energy function while keeping a certain directional coherence. This component makes it possible to avoid oscillations between positions corresponding to local extrema.

(8) More precisely, the new energy function can be expressed in the form, keeping the previous notations:

(9) $\begin{array}{cc}{\tilde{E}}_n\left(x\right)\mathrm{\square \alpha }{x}_n{y}_n+\underset{m\in H\left(n\right)}{.Math.}\underset{n^{\prime }\in H\left(m\right)}{.Math.}{x}_{n^{\prime }}+\rho \left({\ell }_n\right)& \left(6\right)\end{array}$
where .sub.n≥1 is defined as the number of iterations since the last flipping of the bit x.sub.n and ρ(.sub.n) is the inertial component that is associated with l.sub.n. Thus, l.sub.n=1 if the bit x.sub.n was flipped at the last iteration, .sub.n=2 if it was flipped at the last iteration but one, etc. Hereinafter, the local energy function in the direction of x.sub.n will more simply be noted {tilde over (E)}.sub.n.

(10) It is supposed that the aforementioned inertial component has a memory effect limited to a predetermined number L of iterations. It can consequently be represented in the form of a vector p of size L, i.e. ρ=(ρ(1), ρ(2), . . . , ρ(L)), with ρ(1)≥ρ(2)≥ . . . ≥ρ(L)>0, on the understanding that ρ(.sub.n)=0 for l.sub.n>L.

(11) At the start of the decoding, the number .sub.n of iterations since the last iteration of the bit, x.sub.n, is initialised to L+1, this for n=1, . . . , N. If the bit x.sub.n is flipped during an iteration, the corresponding number .sub.n is set to zero. It is systematically incremented by 1 at the start of each iteration without however being able to exceed the maximum value, L+1. In other words, if the bit x.sub.n was flipped at the previous iteration, the value .sub.n=1 is taken into account at the current iteration for calculating the local energy function.

(12) According to a first embodiment of the invention, at the end of each iterative decoding iteration, a set {tilde over (F)}□{x.sub.v|{tilde over (E)}.sub.v≤{tilde over (E)}.sub.th} of unreliable bits is determined where {tilde over (E)}.sub.th is a fixed or adaptive threshold value, determined as specified below. The bits of F are next flipped in preparation for the following iteration.

(13) According to a second embodiment of the invention, corresponding to the PGDBF variant, each bit of {tilde over (F)} is flipped randomly, with a probability 0<p<1 where p is a parameter of the algorithm. In other words, for each bit belonging to {tilde over (F)}, a random variable u is drawn, for example equally distributed over the interval [0,1], the bit in question being flipped if u<p and being kept unchanged otherwise.

(14) According to a third embodiment of the invention, corresponding to the NGDBF variant, the set {tilde over (F)} of the unreliable bits are randomised, i.e. {tilde over (F)}□{x.sub.v|{tilde over (E)}.sub.v+Z.sub.v≤{tilde over (E)}.sub.th} where Z.sub.v□N(0,σ.sup.2) is a centred Gaussian random variable of variance σ.sup.2, σ.sup.2 being a parameter of the algorithm. In other words, to each energy value of a bit a random noise sample is added, for example a centred Gaussian noise of variance σ.sup.2, the energy value to which noise is thus added being compared with said threshold value. In an equivalent fashion, the energy value of each bit is compared with the sample of a Gaussian random variable centred on {tilde over (E)}.sub.th and of variance σ.sup.2, a sample being drawn at each bit. Typically σ□{tilde over (E)}.sub.th will be selected.

(15) FIG. 2 shows schematically a flow diagram of a method for decoding an LDPC code according a first embodiment of the present invention.

(16) At the step 210, an initial estimation is made of the code mode x from an observable y representing the word to be decoded as at step 110. As before, the vector y can consist of values of LLRs and the binary word x consists of corresponding sign values.

(17) At step 215, the number .sub.n of iterations since the last flipping is also initialised, for each of the bits x.sub.n, n=1, . . . , N. More precisely, .sub.n=L+1, n=1, . . . , N.

(18) An iterative loop is next entered, wherein:

(19) The syndrome of x is calculated at 220, i.e. c.sub.m, m=1, . . . , M.

(20) At 230, it is checked from the syndrome whether x is a code word, that is to say whether c.sub.m=+1, ∀m∈{1, . . . , M} or, in an equivalent fashion, whether

(21) $\underset{m=1}{\overset{M}{.Math.}}{c}_m=M.$

(22) If such is the case, the decoding algorithm supplies the code word x at 235.

(23) On the other hand, if the word is erroneous, it is determined at 240 whether the maximum number of iterations is reached.

(24) If so, an error indication is generated at 245.

(25) If not, the step 250 continues by incrementing the values .sub.n of 1 without however exceeding the value L. In other words, .sub.n=min(.sub.n+1,L).

(26) At the step 260, local energy values are calculated, {tilde over (E)}.sub.n, n=1, . . . , N, from expression (6).

(27) The set {tilde over (F)} of the least reliable bits are next determined at step 270. The set {tilde over (F)} consists of bits the local energy values of which are lower than a threshold value {tilde over (E)}.sub.th, calculated for example as

(28) ${\tilde{E}}_{th}=\underset{n=1,.Math.,N}{\min }\left(E_n\right)+\delta ,$
where δ≥0 is a predetermined margin.

(29) At the step 280, the bits of x belonging to the set {tilde over (F)} are flipped and step 220 is returned to for a new iteration.

(30) A person skilled in the art will understand that the second embodiment differs from the first in that, at the step 270, the bits of the set {tilde over (F)} are not systematically flipped but are flipped only with a predetermined probability p as indicated above.

(31) In a similar fashion, the third embodiment differs from the first in that, at the step 260, in order to determine whether a bit belongs to the set {tilde over (F)}, a random noise sample is added to the local energy of the bit, for example a Gaussian random noise of variance σ.sup.2, before comparing it with the threshold value, {tilde over (E)}.sub.th.

(32) The elements of the vector representing the inertial component, ρ=(ρ(1), ρ(2) . . . , ρ(L)), can be determined in various ways.

(33) First of all, the elements of the vector ρ can be determined by simulation of the Monte-Carlo type so as to optimise the error correcting performance of the decoding method.

(34) Alternatively, they can be obtained by a reinforcement learning method wherein each state corresponds to a vector ρ (the elements ρ(1), ρ(2), . . . , ρ(L) are assumed to be discretised), a reward being allocated when the decoding supplies a code word, the reward being able to be proportional to the difference P.sub.max−P where P.sub.max is the maximum number of iterations in the stop criterion and P is the number of iterations performed in order to obtain the code word.

(35) Alternatively again, it will be possible to proceed with an exhaustive search in a restricted space.

(36) More precisely, if it is noted that {tilde over (E)}.sub.n=E.sub.n+ρ(.sub.n) and if it is assumed that the elements of the vector y are discretised, that is to say take their values in the set {−Q.sub.p, . . . , −Q.sub.1, 0, Q.sub.1, . . . , Q.sub.p}, the value of the local energy function E.sub.n associated with the variable x.sub.n is bounded by:
−(αQ.sub.p+d.sub.v)≤E.sub.n≤αQ.sub.p+d.sub.v  (7)
where d.sub.v is the maximum degree of a variable node in the Tanner graph.
If it is supposed now that at least one parity equation associated with a control node is unsatisfied (failing that all the parity equations would be satisfied and the word would be a code word), there is at least one variable node x.sub.n for which:
E.sub.n≤αQ.sub.p+(d.sub.v−2)  (8)
insofar as an error on x.sub.n results in a difference of 2 in a value of c.sub.m, m∈H(n).

(37) The result is that the minimum energy value

(38) 0$E_{\min }=\underset{n=1,.Math.,N}{\min }\left(E_n\right)$
also satisfies:
E.sub.min≤αQ.sub.p+(d.sub.v−2)  (9)

(39) Since the purpose of the inertial component is to increase the energy of the bits that have recently been flipped, it can be supposed that the minimum E.sub.min is reached for a bit that has not been flipped during the last L iterations, that is to say the inertial component of which is zero ρ(.sub.n)=0.

(40) As a result, the threshold value {tilde over (E)}.sub.th satisfies:
{tilde over (E)}.sub.th≤αQ.sub.p+(d.sub.v−2)+δ  (10)

(41) If now ρ.sub.max=2αQ.sub.p+(2d.sub.v−2)+δ+ε, is defined, it will be understood that, as soon as a variable node x.sub.n has a local energy value E.sub.n with an inertial component ρ(.sub.n)≥ρ.sub.max:
{tilde over (E)}.sub.n=E.sub.n+ρ(.sub.n)≥αQ.sub.p+(d.sub.v−2)+δ+ε>{tilde over (E)}.sub.th  (11)
and therefore that x.sub.n will not be flipped during the current iteration.

(42) It can therefore be concluded from this that ρ()≤ρ.sub.max, =1, . . . , L insofar as a value higher than ρ.sub.max would prevent any flipping of a bit as soon as the number of iterations since the last flipping thereof would be equal to .

(43) This property makes it possible to restrict the search for possible values of ρ(1), ρ(2), . . . , ρ(L) to a restricted zone of (□.sup.+).sup.N, namely the one defined by:
ρ.sub.max≥ρ(1)≥ρ(2)≥ . . . ≥ρ(L)>0  (12)

(44) Thus, it will be possible initially to fix a value of L and then make a search by brute force among the L-tuplets ρ(1), ρ(2), . . . , ρ(L) of discretised values satisfying (12) and leading to the smallest error rate. Alternatively, it will be possible to use a genetic algorithm with operations of mutation, combination and selection of the vectors ρ in order to seek the one corresponding to the lowest error rate.

(45) In all cases this optimisation of the elements of ρ can be done once and for all offline.

(46) According to another approach, it will be possible to express the inertial component ρ() as a linear or polynomial function of the number f of iterations since the last flipping. For example, in the linear case the inertial component will have the following form:
ρ()=−a+b,=1, . . . ,L  (13)
with a,b>0. The maximum value, ρ.sub.max, of the inertial component will then be selected so that:
ρ.sub.max≥ρ(1)=−a+b  (14-1)
and the minimum value of this component must be positive, i.e.:
ρ(L)=−aL+b>0  (14-2)

(47) Finally, optimisation of the elements of ρ will be reduced to the search for the parameters a,b.

(48) A person skilled in the art will be able to envisage other parametric expressions of ρ() without departing from the scope of the present invention. Thus ρ() will be able to be sought as a decreasing polynomial expression on [1,L].

(49) For high values of L, it will also be possible to define the function ρ() piecewise, for example as a linear or even constant function by pieces, in which case:
ρ(1)= . . . =ρ(.sub.1)>ρ(.sub.1+1)= . . . =ρ(.sub.2)> . . . >ρ(.sub.s+1)= . . . =ρ(L)>0  (15)
with 1<.sub.1<.sub.2 . . . <.sub.s<L defining the bounds of the intervals in question.

(50) The differences in performance between the method for decoding LDPC code according to the present invention and the methods known from the prior art are illustrated by means of FIGS. 3A-3B and 4A-4B.

(51) The first LDPC code was a regular code (4,8), of rate R=0.5, of length N=1296 bits. It will be recalled that a code is regular when all the variable nodes have the same degree, d.sub.v, and all the control nodes also have the same degree, d.sub.c, in the Tanner graph. The degrees of the variable nodes and of the control nodes were respectively d.sub.v=4 and d.sub.c=8.

(52) The second LDPC code was a regular code (6,32), of rate R=0.84, of length N=2048 bits. The degrees of the variable nodes and of the control nodes were respectively d.sub.v=6 and d.sub.c=32. This code comes from IEEE 802.3an (Ethernet 10 Gbits/s on twisted pair).

(53) The decoding methods known from the prior art have been shown in the figures by their acronyms, namely:

(54) BP, floating point: decoding by belief propagation, floating-point calculation;

(55) MS, quant (4,6): decoding by means of the Min-Sum algorithm with 4-bit messages;

(56) MS, floating point: decoding by means of the Min-Sum algorithm, floating-point calculation;

(57) BF: original method by bit flipping (Gallagher);

(58) GDBF: gradient descent bit flipping decoding method;

(59) PGDBF: probabilistic gradient descent bit flipping method.

(60) The examples of decoding methods according to the present invention are represented by:

(61) GDBF-w/M: GDBF with inertial component (with momentum)

(62) PGDBF-w/M: PGDBF with inertial component (with momentum)

(63) In the case of FIGS. 3A and 3B, it has been supposed that the channel was binary symmetric and the word error rate or WER has been shown as a function of the probability of switching of a bit onto the channel (BSC crossover probability).

(64) The correlation coefficient (GDBF/PGDBF methods with or without inertia) was selected so that α=1.0 for the first LDPC code and α=2.0 for the second LDPC code.

(65) The margin δ in the threshold value {tilde over (E)}.sub.th (GDBF/PGDBF methods with or without inertia) was selected as zero whether for the first or the second LDPC code.

(66) The probability of flipping p in the PGDBF and PGDBF-w/M methods was selected so that p=0.9 for decoding the first LDPC code and p=0.8 for decoding the second LDPC code.

(67) For decoding the first LDPC code with the GDBF-w/M and PGDBF-w/M methods, the inertial component was the dimension L=3 with ρ=[4 2 1].

(68) For decoding the second LDPC code with the GDBF-w/M and PGDBF-w/M methods, the inertial component was the dimension L=4 with ρ=[4 3 2 1].

(69) It will be noted that introducing an inertial component substantially improves the GDBF and PGDBF decodings. Furthermore, the GDBF-w/M decoding has better performance than the PGDBF decoding, even though the first does not use randomisation for flipping. Furthermore, the PGDBF-w/M decoding of the first or second code does not show any error floor as far as WER levels of around 10.sup.−7. Finally, decoding the second LDPC code by the GDBF-w/M method or by the PGDBF-w/M method have equivalent performances, these performances being of the same order as, or even better than, those of the belief propagation BP method in the region of the error floor.

(70) In the case of FIGS. 4A and 4B, it has been supposed that the channel was of the AWGN type (in other words affected by Gaussian additive white noise) and the word error rate (WER) has been shown.

(71) The correlation coefficient (GDBF/PGDBF methods with or without inertia) was selected so that α=1.8 for the first LDPC code and α=4.5 for the second LDPC code.

(72) The margin δ in the threshold value {tilde over (E)}.sub.th (GDBF/PGDBF methods with or without inertia) was selected equal to 1.1 for the first LDPC code and 1.2 for the second LDPC code.

(73) The flipping probability p in the PGDBF and PGDBF-w/M methods was selected so that p=0.9 for decoding the first LDPC code and p=0.8 for decoding the second LDPC code.

(74) For decoding the first LDPC code with the GDBF-w/M and PGDBF-w/M methods, the inertial component was the dimension L=7 with ρ=[2 2 2 2 2 1 1].

(75) For decoding the second LDPC code with the GDBF-w/M and PGDBF-w/M methods, the inertial component was the dimension L=4 with ρ=[3 3 2 1].

(76) It will be noted that the GDBF-w/M and PGDBF-w/M decodings have substantially the same performances in the waterfall region and even exceed those of the floating-point MS decoding even if the GDBF-w/M decoding has lower performance than PGDBF-w/M in the floor region. The performance of the PGDBF-w/M decoding approaches (first LDPC code) or even attains (second LDPC code) those of the belief propagation decoding with floating-point calculation (floating-point BP).

(77) In general, the GDBF or PGDBF decoding methods with inertial component make it possible to obtain performances (in terms of WER as a function of the signal to noise ratio) comparable to those of a belief-propagation (BP) decoding method or even better in the error floor region. The decoding methods according to the invention are therefore particularly advantageous in the cases where the error floor is very low, that is to say when the Tanner graph has a high degree of connectivity d.sub.c.