Iterative decoding method of LFSR sequences with a low false-alarm probability

Abstract

A message-passing iterative decoding method of an associated LFSR sequence (or M-sequence) as a simplex code, to a parity matrix H. The method includes determining a set of parity polynomials with a low weight obtained by combining the parity equations of the matrix H. For each combination of K such polynomials of this set, an extended parity matrix H.sub.ext is built by concatenating elementary parity matrices associated with the parity polynomials of said combination. The combination of parity polynomials leading to a bipartite graph not having cycles with a length 4 and having a minimum number of cycles with lengths 6 and 8 is selected. Then, the LFSR sequence is decoded using the bipartite graph corresponding to the selected combination. This decoding method enables the false-alarm rate to be substantially reduced.

Claims

1. A message-passing iterative decoding method comprising the following steps of: at the receiver, receiving samples of a signal over a wireless telecommunication system and which are to be checked for correspondence to a portion of an LFSR sequence with a length N generated with a generator polynomial, said LFSR sequence being associated, as a simplex code, with a parity matrix, H, and determining whether the samples of the signal correspond to the portion of the LFSR sequence by: (a) determining a set of parity polynomials, with a weight equal to 3 and a constant equal to 1, corresponding to a combination of parity equations of the parity matrix H; (b) generating an extended parity matrix H, by concatenating a predetermined number K or elementary parity matrices, respectively associated with K parity polynomials selected from said set of parity polynomials; (c) checking a length of cycles in a Tanner graph generated from the parity matrix H and checking that the Tanner graph associated with the extended parity matrix H.sub.ext does not include a cycle with a length 4 and, in an absence of such a cycle, (d) calculating a number of cycles with a length 6 within the Tanner graph and, in when the number of cycles with a length 6 is equal to NK, storing in a table a combination of the K parity polynomials selected in step (b); steps (b), (c), (d) being repeated for all combinations of the K parity polynomials of said set; and (e) calculating for each combination of the K parity polynomials stored in said table a number of cycles with the length 8 in the Tanner graph associated with the extended parity matrix H.sub.ext; (f) selecting a combination of K parity polynomials corresponding to a lowest number of cycles with a length 8 calculated in step (e) to carry out a message-passing iterative decoding of said sequence in the Tanner graph associated with the extended parity matrix H.sub.ext generated from the combination of K parity polynomials thus selected, wherein a criterion of convergence to values of nodes of variables of the Tanner graph is applied after a predetermined number of iterations and when the criterion of convergence is not met, it is concluded that there is an absence of the LFSR sequence in the received samples of the signal and the samples of the signal are determined to be only samples of noise, and when the criterion of convergence is met by predetermined number of iterations, the receiver synchronizes the received samples of the signal with the LFSR sequence.

2. The iterative decoding method according to claim 1, wherein checking in step (c) consists in determining whether one of following conditions r.sub.bi.sub.b=i.sub.a, r.sub.bi.sub.b=r.sub.a, r.sub.bi.sub.b=r.sub.ai.sub.a; r.sub.ai.sub.a=i.sub.b is met for at least any one couple of parity polynomials g.sub.a(x)=1+x.sup.i.sup.a+x.sup.r.sup.a and g.sub.b(x)=1+x.sup.r.sup.b+x.sup.r.sup.b, from the K parity polynomials selected in step (b), where r.sub.a and r.sub.b are the degrees of the parity polynomials g.sub.a (x) and g.sub.b(x), i.sub.a and i.sub.b are the degrees of the monomials within the parity polynomials g.sub.a(x) and g.sub.b(x), and the absence of a cycle with a length 4 in the Tanner graph being set if none of the previous conditions r.sub.bi.sub.b=i.sub.a, r.sub.bi.sub.b=r.sub.a, r.sub.bi.sub.b=r.sub.ai.sub.a; r.sub.ai.sub.a=i.sub.b is met.

3. The iterative decoding method according to claim 1, wherein the number of cycles with a length 6 in the Tanner graph associated with the extended parity matrix H.sub.ext is obtained from $N_6=\frac{1}{6}\left(\mathrm{tr}\left(A^3\right)-3\mathrm{KN}\left(\left(K^2+3K+1\right)-9\left(K+1\right)+2\right)\right)$ where A=H.sub.ext H.sub.ext.sup.T and tr(.) is the trace function.

4. The iterative decoding method according to claim 1, wherein calculating the number of cycles with a length 8 in the Tanner graph associated with the extended parity matrix H.sub.ext comprises calculating tr(A.sup.4)4 (3K+1)tr(A.sup.3) where A=H.sub.extH.sub.ext.sup.T and tr(.) is the trace function.

5. The iterative decoding method according to claim 3, wherein a trace tr(A.sup.3) is obtained by calculating $\mathrm{tr}\left(A^3\right)=\underset{i=0}{\overset{K-1}{.Math.}}\underset{j=0}{\overset{K-1}{.Math.}}\underset{k=0}{\overset{K-1}{.Math.}}{T}_{\mathrm{ijk}}$ where: $T_{\mathrm{ijk}}=\underset{{}_{\mathrm{ji}}}{.Math.}\underset{{}_{\mathrm{kj}}}{.Math.}{A}_{k,i}\left(0,\right)A_{k,j}\left(0,\right)A_{j,i}\left(0,\right)$ A.sub.i,j(,v) being the element at a row and a column v of the matrix A.sub.i,j=H.sub.iH.sub.j.sup.T, where H.sub.i and H.sub.j are elementary parity matrices associated with two parity polynomials from the K parity polynomials selected in step (b), and where .sub.ji, .sub.kj are sets of non-zero elements of a first row of a matrix A.sub.i,j and a first row of a matrix A.sub.j,k, respectively.

6. The iterative decoding method according to claim 4, wherein trace tr(A.sup.4) is obtained by calculating $\mathrm{tr}\left(A^4\right)=\underset{i=0}{\overset{K-1}{.Math.}}\underset{j=0}{\overset{K-1}{.Math.}}\underset{k=0}{\overset{K-1}{.Math.}}\underset{l=0}{\overset{K-1}{.Math.}}{T}_{\mathrm{ijkl}}$ where: $T_{\mathrm{ijkl}}=\underset{.Math.{}_{\mathrm{ji}}}{.Math.}\underset{.Math.{}_{\mathrm{kj}}}{.Math.}\underset{.Math.{}_{\mathrm{lk}}}{.Math.}{A}_{l,i}\left(0,\left(++\mathrm{mod}N\right)\right)A_{k,j}\left(0,\right)A_{j,i}\left(0,\right)A_{l,k}\left(0,\right)$ A.sub.j,k(,v) being an element at a row and a column v of a matrix A.sub.j,k=H.sub.iH.sub.j.sup.T, where H.sub.i and H.sub.j are elementary parity matrices associated with two parity polynomials from the K parity polynomials selected in step (b) and where .sub.ji, .sub.kj, .sub.lk are sets of non-zero elements of first respective rows of matrices A.sub.i,j, A.sub.j,k, A.sub.k,l.

7. The iterative decoding method according to claim 1, wherein a Min-Sum-type algorithm is used on the Tanner graph associated with the extended parity matrix H.sub.ext generated from the combination of K parity polynomials selected in step (f).

8. The iterative decoding method according to claim 1, said method further comprising using a Sum-Product-type algorithm on the Tanner graph associated with the extended parity matrix H.sub.ext generated from the combination of K parity polynomials selected in step (f).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Further characteristics and advantages of the invention will appear upon reading preferential embodiments in reference to the appended figures in which:

(2) FIG. 1 represents an M-sequence generator according to a Fibonacci representation;

(3) FIG. 2 represents the false-alarm rate of a receiver, for a given LFSR sequence and different parity matrices;

(4) FIG. 3 represents a cycle with a length 6 in the bipartite graph used by the decoder;

(5) FIG. 4 schematically represents a flowchart of the decoding method according to one embodiment of the invention.

DETAILED DISCLOSURE OF PARTICULAR EMBODIMENTS

(6) Hereinafter, a receiver that has to be synchronized using an LFSR sequence and more precisely a decoder that has to decide between a presence hypothesis (A.sub.1) and an absence hypothesis (A.sub.0) of such a sequence will be considered, as described in the introductory part.

(7) The decoder resorts to a message-passing decoding method in a bipartite graph. The bipartite graph consists of a plurality of variable nodes representing the elements of the sequence and a plurality of constraint nodes representing the parity equations to be checked by the elements of the sequence. The graph consists of a plurality K of elementary sub-graphs, said elementary sub-graphs sharing the variable nodes, each elementary sub-graph comprising its own constraint nodes. The edges of each elementary sub-graph are given by the rows of an elementary parity matrix, H.sub.a obtained by combining rows of the parity matrix H, each elementary parity matrix corresponding to a parity polynomial (or check polynomial) h.sub.a(x).

(8) The extended parity matrix H.sub.ext associated with the graph is then the concatenation of the elementary parity matrices H.sub.a. The message-passing iterative decoding is made using a Sum-product or Min-sum-type algorithm as set out above.

(9) Given that the combination of two rows of the parity matrix H provides again a parity equation, there is, for a given integer K, a great number of possible combinations of parity polynomials. For a given generator polynomial g(x) (and thus a given parity matrix H), the possible combinations of parity polynomials can be obtained, in a known manner per se, according to the method described in the papers by W. T. Penzhorn et al. entitled Computation of low-weight parity checks for correlation attacks on stream ciphers, Cryptography and Coding, Springer, 1995 and by P. Chose et al. entitled Fast correlation attacks: an algorithmic point of view, Advances in Cryptology, Eurocrypt 2002, Springer 2002, incorporated herein in reference.

(10) The idea underlining the invention is to resort only to parity polynomials h.sub.a(x) with a weight t=3 and a constant equal to 1, then to make among them a selection to remove the cycles with a length 4 and finally to choose from the remaining ones those which enable the number of cycles with lengths 6 and 8 to be minimized in the bipartite graph (or Tanner graph).

(11) It was in particular possible to show by simulation, in opposition to a commonly accepted idea, that the reduction in the number of cycles with a length 6 in the Tanner graph did not enable the erroneous decoding probability to be reduced but substantially reduced the false-alarm rate. In addition, it could be shown that the reduction in the number of cycles with a length 8 further reduced the false-alarm rate.

(12) The cycles of a bipartite graph are necessarily of an even length (the number of ridges of a cycle is necessarily even). The shorter cycles in such a graph are thus cycles with lengths 4, 6, 8.

(13) A cycle with a length 4 is reflected in the Tanner graph by two variable nodes both connected to two same constraint nodes (butterfly-shaped circuit between two variable nodes and two constraint nodes) and in the extended parity matrix H.sub.ext by elements equal to 1 at the vertices of a rectangle.

(14) The polynomials with a weight 3, respectively associated with the matrices H.sub.a and H.sub.b, are noted g.sub.a(x)=1+x.sup.i.sup.a+x.sup.r.sup.a and g.sub.b(x)=1+x.sup.i.sup.a+x.sup.r.sup.b where r.sub.a and r.sub.b are the degrees of the polynomials g.sub.a(x) and g.sub.b(x).

(15) If it is assumed that r.sub.ar.sub.b, it can be seen that because of the Toeplitz structure of the matrices H.sub.a and H.sub.b, a cycle with a length 4 in the bipartite graph (associated with the extended parity matrix H.sub.ext) can only exist if and only if one of the following conditions is met:
r.sub.bi.sub.b=i.sub.a(7-1)
r.sub.bi.sub.b=r.sub.a(7-2)
r.sub.bi.sub.b=r.sub.ai.sub.a(7-3)
r.sub.ai.sub.a=i.sub.b(7-4)

(16) In other words, to exclude the cycles with a length 4, it is sufficient to choose a combination of generator polynomials such that, for any two polynomials g.sub.a(x), g.sub.b(x) belonging to this combination, none of the conditions (7-1) to (7-4) is met.

(17) The number of cycles with a length 6 in the Tanner graph can be obtained by using the general method described in the paper of T. R. Halford et al. entitled An algorithm for counting short cycles in bipartite graphs, published in IEEE Trans. on Information Theory, vol. 52, no. 1, January 2006, pp. 287-292.

(18) More precisely, the following operators are defined:
Y=X=[y(i,j)] where y(i,j)=x(i,j)(8-1)
U=max(X,0)=[u(i,j)] where u(i,j)=max(0,x(i,j))(8-2)
V=X.Math.Y=[v(i,j)] where v(i,j)=x(i,j)y(i,j)(8-3)
Z(X)=XX.Math.I(8-4)

(19) It is thus understood that the operator .Math. represents the Hadamard multiplication and the operator Z(.) cancels the diagonal of the matrix to which it is applied.

(20) The following matrices are further defined:
A=H.sub.extH.sub.ext.sup.T(9-1)
B=H.sub.ext.sup.TH.sub.ext(9-2)
=A.Math.I(9-3)
{tilde over (B)}=B.Math.I(9-4)
.sub.m=max(1,0)(9-5)
{tilde over (B)}.sub.m=max({tilde over (B)}1,0)(9-6)

(21) It can be shown that the number of cycles with a length 6 is equal to:

(22) $\begin{array}{cc}{N}_6=\frac{1}{6}\mathrm{tr}\left(L\right)\mathrm{with}& \left(10\text{-}1\right)\\ L=Z\left(A\right)A^2-A{\tilde{B}}_m{\mathrm{BE}}^T-Z\left(A{\tilde{A}}_m\right)A-\mathrm{EZ}\left(B{\tilde{B}}_m\right)E^T+{\tilde{A}}_{m}E{\tilde{B}}_m{E}^T& \left(10\text{-}2\right)\end{array}$

(23) The matrices A and B depend on the extended parity matrix H.sub.ext and consequently on the selected combination of parity polynomials. It is reminded that the extended parity matrix is formed by concatenating K elementary parity matrices H.sub.ext=[H.sub.a(1).sup.TH.sub.a(2).sup.T . . . H.sub.a(K).sup.T].sup.T where g.sub.a(k)(x)=1+x.sup.i.sup.a(k)+x.sup.r.sup.a(k) is the parity polynomial associated with the parity matrix H.sub.a(k), the combination of parity polynomials being formed by the polynomials g.sub.a(k)(x), k=1, . . . , K.

(24) Because the elementary parity matrices H.sub.a(k) are circulant, it can be shown that the expression (10-2) can be simplified as:

(25) $\begin{array}{cc}{N}_6=\frac{1}{6}\left(\mathrm{tr}\left(A^3\right)-3\mathrm{KN}\left(\left(K^2+3K+1\right)-9\left(K+1\right)+2\right)\right)& \left(11\right)\end{array}$

(26) In other words, given that K and N are constants, minimizing the number of cycles with a length 6 in the Tanner graph amounts to minimizing the trace of the matrix A.sup.3.

(27) On the other hand, it is possible to determine the minimal number of cycles with a length 6. Indeed, it can be shown that 3 cycles with a length 6 pass through each variable node.

(28) FIG. 3 shows a cycle with a length 6 passing through the variable nodes z(k), z(k+i.sub.a), z(k+i.sub.ar.sub.a) and the constraint nodes F.sub.a(k), F.sub.a(kr.sub.a), F.sub.a(kr.sub.a+i.sub.a) (each representing a parity equation of the matrix H.sub.a). The 2 other cycles are deduced from the one represented by replacing k by ki.sub.a and kr.sub.ai.sub.a. Given that each cycle involves 3 variable nodes, the minimum number of cycles with a length 6 is:
N.sub.6.sup.min=NK(12)

(29) In the same way as previously, the number of cycles with a length 8 in the Tanner graph can be calculated for each extended parity matrix H.sub.ext=[H.sub.a(1).sup.TH.sub.a(2).sup.T . . . H.sub.a(K).sup.T].sup.T, corresponding to a given combination of the parity polynomials g.sub.a(k)(x), k=1, . . . , K:

(30) $\begin{array}{cc}{N}_8=\frac{1}{8}\left(\mathrm{tr}\left(A^4\right)-4\left(3K+1\right)\mathrm{tr}\left(A^3\right)+Q\left(N,K\right)\right)& \left(13\right)\end{array}$
where Q(N,K) is a value which only depends on the constants K,N. Thereby, it is understood that minimizing the number of cycles with a length 8 amounts to minimizing tr(A.sup.4)4(3K+1)tr(A.sup.3) on the set of possible combinations g.sub.a(k)(x), k=1, . . . , K.

(31) FIG. 4 represents a flowchart of the decoding method according to one embodiment of the invention.

(32) It is assumed that the receiver knows the generator polynomial of the M-sequence or, equivalently, the parity matrix H of this sequence (parity matrix of a simplex code).

(33) The length N of the sequence is supposed to be known and a number K of parity polynomials, or equivalently, of elementary parity matrices H.sub.a is set.

(34) It will be supposed hereinafter, to simplify the presentation, that the receiver processes N successive samples. The decoding method however is also applicable to the case where the receiver only receives M<N samples.

(35) In step 410, the set S.sub.3 of parity polynomials with a weight 3 and a constant equal to 1, which are obtained by combining the parity equations of the matrix H is determined.

(36) Given that the simplex code [2.sup.r1, r] is the dual of the Hamming code [2.sup.r1, 2.sup.rr1], the number A.sub.3 of parity equations (or polynomials) with a weight 3 and a constant equal to 1 is equal to the number of words of the Hamming code with the weight 3 and a constant equal to 1, that is:
.sub.3=2.sup.r11(14)

(37) In step 420, it is checked whether all the combinations of the K parity polynomials from the set S.sub.3 have already being selected. If so, step 480 is proceeded.

(38) If all the combinations of K parity polynomials from the set S.sub.3 have not been selected, a new combination of K polynomials is selected in step 430, g.sub.a(k)(x), k=1, . . . , K.

(39) In step 440, the corresponding parity matrices H.sub.a(k), k=1, . . . , K are deduced from the K parity polynomials thus selected. The elements of these matrices are given by the expression (4). Then, the extended parity matrix H.sub.ext=[H.sub.a(1).sup.TH.sub.a(2).sup.T . . . H.sub.a(K).sup.T].sup.T is formed.

(40) In step 450, it is checked that the bipartite graph corresponding to the extended parity matrix H.sub.ext does not include a cycle with a length 4. For this, it is determined whether any couple of polynomials from the K selected parity polynomials meets one of the conditions (7-1)-(7-4). If so, the method goes back to step 420. Otherwise, step 460 is proceeded.

(41) It will be noted that steps 440 and 450 can be inverted.

(42) In step 460, the number, N.sub.6, of cycles with a length 6 is calculated in the bipartite graph corresponding to the extended parity matrix H.sub.ext. This calculation can be made from the expression (11).

(43) In step 470, it is checked whether N.sub.6=NK. If not, the method directly go back to step 420. On the other hand, if so, the bipartite graph contains a minimal number of cycles with a length 6 and the combination of the polynomials g.sub.a(k)(x), k=1, . . . , K is stored in a table in 475, and then the method goes back to step 420 to select a new combination of polynomials of S.sub.3 (if they have not all been already selected).

(44) In step 480, for each combination of polynomials stored in the table , the number N.sub.8 of cycles with a length 8 is calculated in the bipartite graph corresponding to the extended parity matrix H.sub.ext. To that end, it will be sufficient to calculate the part of N.sub.8 which depends on the choice of the combination, in other words tr(A.sup.4)4(3K+1)tr(A.sup.3).

(45) In 490, the combination C of parity polynomials g.sub.a(k)(x), k=1, . . . , K which minimizes N.sub.8 is retained, in other words the combination:

(46) $\begin{array}{cc}C=\underset{\left\{g_{\left(k\right)}\left(x\right),k-1,\mathrm{.Math.},L\right\}}{\arg \min }\left(N_8\right)& \left(15\right)\end{array}$

(47) The combination C of polynomials thus retained and the bipartite graph associated with the corresponding matrix H.sub.ext are then used to decode the sequence of the received samples.

(48) If, after a predetermined number of iterations, a convergence criterion is not fulfilled, the receiver concludes for the hypothesis A.sub.0, otherwise, it concludes for the hypothesis A.sub.1. The convergence criterion can be for example a mean of the absolute values of the variable nodes, expressed as Log Likelihood Ratios (LLR). In the latter case, the mean of the absolute values can be compared with a threshold to decide for the hypothesis A.sub.0 or A.sub.1.

(49) The calculation of the numbers of cycles N.sub.6 and N.sub.8 can however be complex because of the terms tr(A.sup.3) and tr(A.sup.4), since the size of the matrix A can reach 10001000.

(50) It is however possible to simplify the calculation of the traces in question by taking advantage of the circulant nature of the elementary parity matrices H.sub.a.

(51) More precisely, if A.sub.i,j=H.sub.iH.sub.j.sup.T is set, the matrix A can be expressed as:

(52) $\begin{array}{cc}A=\left[\begin{array}{cccc}{A}_{0,0}& A_{0,1}& \mathrm{.Math.}& A_{0,N-1}\\ A_{1,0}& A_{1,1}& \mathrm{.Math.}& A_{1,N-1}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ A_{N-1,0}& A_{N-1,1}& \mathrm{.Math.}& A_{N-1,N-1}\end{array}\right]& \left(16\right)\end{array}$

(53) If T.sub.ijk=tr (A.sub.i,jA.sub.k,jA.sub.ik) is set, the trace of A.sup.3 can be obtained in the following way:

(54) $\begin{array}{cc}\mathrm{tr}\left(A^3\right)=\underset{i=0}{\overset{K-1}{.Math.}}\underset{j=0}{\overset{K-1}{.Math.}}\underset{k=0}{\overset{K-1}{.Math.}}{T}_{\mathrm{ijk}}& \left(17\right)\end{array}$
with, by assuming ijk:

(55) $\begin{array}{cc}{T}_{\mathrm{ijk}}=\underset{s=0}{\overset{N-1}{.Math.}}\underset{h=0}{\overset{N-1}{.Math.}}\underset{l=0}{\overset{N-1}{.Math.}}{A}_{\mathrm{ki}}\left(0,\left(s-l\right)\right)A_{\mathrm{kj}}\left(0,\left(h-l\right)\right)A_{\mathrm{ji}}\left(0,\left(s-h\right)\right)\mathrm{where}\text{:}& \left(18\right)\\ \left(u\right)=\{\begin{array}{c}u\mathrm{if}0uN-1\\ N+u\mathrm{if}-N<u<0\end{array}& \left(19\right)\end{array}$

(56) Thereby, it can be shown that:

(57) $\begin{array}{cc}{T}_{\mathrm{ijk}}=\underset{{}_{\mathrm{ji}}}{.Math.}\underset{{}_{\mathrm{kj}}}{.Math.}{A}_{k,i}\left(0,\right)A_{k,j}\left(0,\right)A_{j,i}\left(0,\right)& \left(20\right)\end{array}$
where =(sl); =(hl); =(sh)=(+)mod N and where .sub.ji is the set of the non-zero elements of the first row of the matrix A.sub.ij, that is .sub.ji={m|A.sub.j,i(0, m)0}. It can be shown that .sub.ji contains 9 indices if ij and 7 indices otherwise. The calculation of the trace of A.sup.3 in step 460 is thus dramatically simplified.

(58) In a similar way, if T.sub.ijkl=tr(A.sub.i,jA.sub.k,jA.sub.i,kA.sub.l,k) is set, the calculation of the trace of A.sup.4 in step 480 can be simplified from:

(59) 0$\begin{array}{cc}\mathrm{tr}\left(A^4\right)=\underset{i=0}{\overset{K-1}{.Math.}}\underset{j=0}{\overset{K-1}{.Math.}}\underset{k=0}{\overset{K-1}{.Math.}}\underset{l=0}{\overset{K-1}{.Math.}}{T}_{\mathrm{ijkl}}& \left(21\right)\\ T_{\mathrm{ijkl}}=\underset{.Math.{}_{\mathrm{ji}}}{.Math.}\underset{.Math.{}_{\mathrm{kj}}}{.Math.}\underset{.Math.{}_{\mathrm{lk}}}{.Math.}{A}_{l,i}\left(0,\left(++\mathrm{mod}N\right)\right)A_{k,j}\left(0,\right)A_{j,i}\left(0,\right)A_{l,k}\left(0,\right)& \left(22\right)\end{array}$
with the same notation conventions as previously.

(60) Hereinafter, it has been supposed that the selection of the parity polynomials, g.sub.a(k)(x), k=1, . . . , K and the building of the corresponding extended parity matrix H.sub.ext was made at the receiver. However, it will be understood that the selection of the parity polynomials and the building of the extended parity matrix can alternatively be made only once, optionally for different generator polynomials (in other words for different possible M-sequences) and the results of this selection/building be stored at the receiver.