Map decoding method using augmented lattices

Abstract

The invention relates to a MAP decoding method of a signal received through a noisy channel, the signal being composed of symbols in an alphabet having a non-uniform probability distribution, the symbols being represented by points in a lattice (). The probability distribution of symbols is modeled using a Gaussian distribution. An augmented lattice (.sub.exp) is formed from the lattice () and the ratio () between variance of the noise and variance of the Gaussian distribution of symbols. Therefore, the disclosed MAP decoding method consists essentially of decoding using an ML criterion searching the point in the augmented lattice closest to the point representative of the received signal (y.sub.exp).

Claims

1. A MAP decoding method implemented on a decoder for decoding a signal received through a noisy channel, wherein the method comprises: receiving, by a relay terminal of a network having a decoder, the signal transmitted by at least one source terminal through a noisy channel, said noisy channel comprising an elementary channel between each source terminal and the relay terminal, the signal being composed of symbols belonging to a predetermined alphabet, affected by an additional Gaussian white noise, a probability distribution of the symbols within the predetermined alphabet being non-uniform, the symbols being represented by points in a lattice ={x|x=Ma, aZ.sup.N} generated by a matrix M with dimension NN; determining, by the decoder, a vector y with dimension N representative of the received signal; determining, by the decoder, an augmented vector $y_{\exp }=\left[\begin{array}{c}y\\ 0_N\end{array}\right]$ in which 0.sub.N is a null vector with dimension N; determining, by the decoder, an augmented lattice .sub.exp={x|x=M.sub.expa,aZ.sup.N} (330) with generator matrix $M_{\exp }=\left[\begin{array}{c}M\\ M\end{array}\right]$ in which $=\frac{{}^2}{{}_v^2}$ is the ratio between variance of the noise and variance of a Gaussian probability distribution modelling the non-uniform probability distribution of the symbols in the alphabet; searching, by the decoder, among points in the augmented lattice to find a closest neighbour , which is the point closest to the vector representative of the received signal; and estimating, by the decoder, a received symbol {circumflex over (v)}.sub.MAP* from the generating matrix M and the closest neighbour , such that {circumflex over (v)}.sub.MAP*=M, to create a decoded signal.

2. The MAP decoding method according to claim 1, wherein said searching for the closest neighbour is limited to a finite sub-set .sub.a of the lattice representing a constraint on a signal energy.

3. The MAP decoding method according to claim 1, wherein said noisy channel comprises a plurality of K elementary channels between the source terminals and the relay terminal, each symbol comprising a combination of elementary symbols transmitted by the corresponding source terminals to said relay terminal, each elementary symbol belonging to an elementary alphabet of a source terminal.

4. The MAP decoding method according to claim 3, wherein the elementary alphabets of the source terminals are identical and the variance .sub.V.sup.2 of the Gaussian probability distribution modelling the non-uniform probability distribution of symbols in the alphabet is obtained by .sub.V.sup.2=K.sub.X.sup.2 where .sub.X.sup.2 is the variance of the probability distribution of elementary symbols within an elementary alphabet.

5. The MAP decoding method according to claim 4, wherein the variance .sub.X.sup.2 is obtained by .sub.X.sup.2=NP.sub.max where P.sub.max is the maximum transmission power of a source terminal.

6. The MAP decoding method according to claim 1, wherein the search for the closest neighbour is made using a sphere decoder.

7. The MAP decoding method according to claim 6, wherein the sphere decoding uses an enumeration of points according to Pohst's algorithm.

8. The MAP decoding method according to claim 1, wherein the searching for the closest neighbour comprises decoding, using a stack decoder with a spherical bound.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Other characteristics and advantages of the invention will become clear after reading preferred embodiments of the invention, with reference to the appended figures among which:

(2) FIG. 1 shows a simplified example of a cooperative network using physical layer network coding;

(3) FIG. 2 shows an error rate curve as a function of the signal to noise ratio for an exemplary application of the MAP augmented lattice decoding method according to one embodiment of this invention;

(4) FIG. 3 shows a flowchart of the MAP augmented lattice decoding method according to one embodiment of this invention.

DETAILED PRESENTATION OF PARTICULAR EMBODIMENTS

(5) In the following, we will consider an alphabet of information symbols with a non-uniform probability distribution. In other words, the symbols in this alphabet are not equally probable.

(6) This alphabet may for example be the alphabet used by a non-uniform information source or it may be the result of a combination at a relay in a cooperative network making use of physical layer network coding.

(7) For illustration purposes and without reducing generalisation, we will disclose the decoding method according to the invention as part of a cooperative network. To achieve this, we will assume that K source terminals S.sub.1, . . . , S.sub.K transmit K symbols x.sub.1, . . . , x.sub.K respectively, and that a relay terminal receives a signal corresponding to a combination of these symbols, namely:

(8) $\begin{array}{cc}\frac{1}{N}E\left\{{.Math.x.Math.}^2\right\}{P}_{\mathrm{ma}x}& \left(8\right)\end{array}$
where g.sub.k, k=1, . . . , K are the gains of each of the channels between the source terminals and the relay terminal. Without reducing generality, we will assume that these gains are equal to 1.

(9) Symbols x.sub.k are elements of a finite alphabet A.sub.X=, called the elementary alphabet, in which is a lattice of dimension N, and is a convex of .sup.N, containing the origin and defining the transmission power constraint of a source terminal (assumed to be identical for all terminals).

(10) For example, if the symbols x.sub.k are elements in a QAM alphabet, the lattice dimension will be 2. Remember that a lattice with dimension N is generally defined by a matrix M with dimension NN, in which the column vectors of the matrix are called the lattice generator vectors, a point x in the lattice being defined in a vector form by x=Ma where aZ.sup.N is a vector with dimension N in which the elements are integers. However, it is understood that the origin of the lattice is not considered for a QAM alphabet (a0.sub.N). Nevertheless it will be understood that we can always consider gains g.sub.k equal to 1, provided that the matrix M can be modified.

(11) The convex is typically a sphere of .sup.N centred at the origin, the radius of the sphere being given by the maximum transmission power of the source terminal. Thus, if P.sub.max is the maximum transmission power of a source terminal, the convex can be defined by points x, such that:

(12) $\begin{array}{cc}y=\underset{k=1}{\overset{K}{.Math.}}{g}_k{x}_k+z& \left(7\right)\end{array}$
where E{.} is the mean value.

(13) The vector z in the expression (7) is a noise vector with dimension N the components of which are random Gaussian variables with zero mean and variance .sup.2.

(14) The relay terminal is provided with a decoder to decode the sum

(15) $v=\underset{k=1}{\overset{K}{.Math.}}{x}_k.$
After decoding if applicable, the relay terminal transmits it to the destination terminal.

(16) The sum symbol

(17) $v=\underset{k=1}{\overset{K}{.Math.}}{x}_k$
belongs to an alphabet A.sub.V resulting from superposition of elementary alphabets A.sub.X. Given that the lattice is stable by addition ( with the addition has a group structure), the sum symbol v still belongs to the lattice . The result is that the lattice .sub.V defining the alphabet A.sub.V is a sub-set of (.sub.V). The alphabet A.sub.V of sum symbols is such that A.sub.V=.sub.V.sub.V where .sub.V is a convex of .sup.N: reflecting the transmission power constraint of K source terminals.

(18) MAP decoding at the relay would result in a search for the sum vector {circumflex over (v)}.sub.MAP such that:

(19) 0$\begin{array}{cc}{\hat{v}}_{\mathrm{MAP}}=\underset{v{}_V}{\mathrm{argmax}}\left(P\left(v|y\right)\right)=\underset{v{}_V}{\mathrm{argmax}}\left(P\left(v\right)P\left(y|v\right)\right)& \left(9\right)\end{array}$
also such that:

(20) $\begin{array}{cc}{\hat{v}}_{\mathrm{MAP}}=\underset{v{}_V}{\mathrm{argmin}}\left(-\ln \left(P\left(v\right)\right)+\frac{{.Math.y-v.Math.}^2}{2{}^2}\right)& \left(10\right)\end{array}$
taking account of the fact that

(21) $P\left(y|v\right)=\exp \left(-\frac{{.Math.y-v.Math.}^2}{2{}^2}\right).$

(22) The basic idea of the invention is to model the sum symbol v using a random Gaussian variable with zero mean and variance .sub.V.sup.2=K.sub.X.sup.2=KNP.sub.max. This approximation is justified by application of the central limit theorem to the random variables x.sub.k.

(23) Based on this approximation, the probability distribution law of the sum symbol is given as follows:

(24) $\begin{array}{cc}P\left(v\right)=\frac{1}{{\left({}_V\sqrt{2}\right)}^N}\exp \left(-\frac{{.Math.v.Math.}^2}{2{}_V^2}\right)& \left(11\right)\end{array}$

(25) In substituting this estimation of P(v) in the expression (10), we obtain a new decoding criterion:

(26) $\begin{array}{cc}{\hat{v}}_{{\mathrm{MAP}}^{*}}=\underset{v{}_V}{\mathrm{argmin}}\left(N\ln \left({}_V\sqrt{2}\right)+\frac{1}{2{}_V^2}{.Math.v.Math.}^2+\frac{1}{2{}^2}{.Math.y-v.Math.}^2\right)& \left(12\right)\end{array}$

(27) Considering that the first term does not depend on v, decoding consists of determining:

(28) $\begin{array}{cc}{\hat{v}}_{{\mathrm{MAP}}^{*}}=\underset{v{}_V}{\mathrm{argmin}}\left({.Math.y-v.Math.}^2+\frac{{}^2}{{}_V^2}{.Math.v.Math.}^2\right)& \left(13\right)\end{array}$

(29) A vector, y.sub.exp called an augmented vector, with dimension 2N, resulting from the vertical concatenation of vector y and a null vector with dimension N, is added, namely

(30) $y_{\mathrm{ex}p}=\left[\begin{array}{c}y\\ 0_N\end{array}\right]$
and a full rank matrix

(31) $B=\left[\begin{array}{c}{I}_N\\ I_N\end{array}\right]$
where I.sub.N is the unit matrix with dimension NN and is a coefficient reflecting the ratio between the noise variance and the variance of the sum symbol to be decoded, namely

(32) $=\frac{{}^2}{{}_V^2}.$

(33) The decoding criterion (13) can then be expressed as follows:

(34) $\begin{array}{cc}{\hat{v}}_{{\mathrm{MAP}}^{*}}=\underset{\underset{a{}_a}{v=\mathrm{Ma}}}{\mathrm{argmin}}\left({.Math.y_{e\mathrm{xp}}-\mathrm{BMa}.Math.}^2\right)& \left(14\right)\end{array}$
in which the condition on the transmission power limit is shown by constraining the vector a to belong to a subset of Z.sup.N such that the transmission power constraint is satisfied, in other words

(35) 0${}_a=\left\{a{Z}^N|\frac{1}{N}E\left\{{.Math.\mathrm{Ma}.Math.}^2{P}_{\mathrm{ma}x}\right\}\right\}.$

(36) If we define the augmented matrix M.sub.exp with dimension 2NN by

(37) $M_{\exp }=\mathrm{BM}=\left[\begin{array}{c}M\\ M\end{array}\right],$
the decoding criterion is finally expressed in the following form:

(38) $\begin{array}{cc}{\hat{v}}_{{\mathrm{MAP}}^{*}}=\underset{\underset{a{}_a}{v=\mathrm{Ma}}}{\mathrm{argmin}}\left({.Math.y_{\exp }-M_{\exp }a.Math.}^2\right)& \left(15\right)\end{array}$
in other words, this is equivalent to searching for the point in an augmented lattice .sub.exp, generated by the matrix M.sub.exp, that is closest to the point y.sub.exp, representing the received signal. Consequently, it will be understood that it is equivalent to a conventional ML decoding in an augmented space, with dimension 2N, the lattice .sub.exp and the point representative of the received signal y.sub.exp both being dimension 2N.

(39) The search for the closest neighbour of y.sub.exp in the augmented lattice .sub.exp may be made classically using sphere decoding. It should be remembered that sphere decoding can limit the search for the closest neighbour to lattices belonging to a noise ball centred at the point representing the received signal. A description of sphere decoding is given in the article by E. Viterbo et al. entitled A universal lattice code decoder for fading channels published in IEEE Transactions on Information Theory, vol. 45, pages 1639-1642, July 1999. A spherical bound stack decoder (SB) can also be used as described in article by G. Rekaya Ben-Othman entitled The spherical bound stack decoder published in Proc. of IEEE International Conference on Wireless & Mobile Computing, Networking & Communication, pp. 322-327.

(40) The search for the closest neighbour using the sphere decoder could in particular use a Pohst enumeration, known in itself.

(41) The sphere decoder starts from a noise sphere with radius C centred at the point y.sub.exp representative of the received signal. Points a in the lattice .sub.exp belonging to this sphere satisfy the following relation:
y.sub.expM.sub.expa.sup.2C.sup.2(16)

(42) The search for the closest neighbour must also take account of the fact that the point a must satisfy the power constraint, in other words a.sub.a.

(43) In a preliminary step, the augmented matrix M.sub.exp is subject to a QR decomposition, in other words M.sub.exp=QR where Q is a matrix with dimension 2NN in which the column vectors are orthogonal and R is an upper triangular matrix with dimension NN. If we denote =M.sub.exp.sup.1y.sub.exp (Zero Forcing solution) and =a, relation (16) can be written again as follows:

(44) $\begin{array}{cc}.Math.R.Math.C^2\mathrm{or}\text{:}& \left(17\right)\\ \underset{i=1}{\overset{N}{.Math.}}{p_{\mathrm{ii}}\left({}_i+\underset{j=i+1}{\overset{N}{.Math.}}{p}_{\mathrm{ij}}{}_j\right)}^2{C}^2& \left(18\right)\end{array}$
where p.sub.ii=r.sub.ii.sup.2, i=1, . . . , N and

(45) $p_{\mathrm{ij}}=\frac{r_{\mathrm{ij}}}{r_{\mathrm{ii}}},$
j=i+1, . . . , N.

(46) The search begins with the N.sup.th component of a:

(47) $\begin{array}{cc}-\frac{C}{\sqrt{p_{\mathrm{NN}}}}{}_n\frac{C}{\sqrt{p_{\mathrm{NN}}}}& \left(19\right)\end{array}$
namely, considering the fact that a.sub.nZ:

(48) $\begin{array}{cc}.Math.{}_N-\frac{C}{\sqrt{p_{\mathrm{NN}}}}.Math.a_n.Math.{}_N+\frac{C}{\sqrt{p_{\mathrm{NN}}}}.Math.& \left(20\right)\end{array}$

(49) Similarly, the search for other components is limited to intervals:

(50) $\begin{array}{cc}.Math.-\sqrt{\frac{T_i}{p_{\mathrm{ii}}}}+S_i.Math.a_i.Math.\sqrt{\frac{T_i}{p_{\mathrm{ii}}}}+S_i.Math.& \left(21\right)\end{array}$
where

(51) $S_i={}_i+\underset{j=1}{\overset{N}{.Math.}}{p}_{\mathrm{ij}}{}_j$
and T.sub.i=T.sub.i-1p.sub.ii(S.sub.iia.sub.i) in which T.sub.N=C.sup.2. The search is made from the last component to the first, the choice of a component with a given index of a reducing the search interval for the component with a lower index.

(52) Search intervals (20) and (21) can be expressed using the simplified relation:

(53) $\begin{array}{cc}{b}_i^{-}{a}_i{b}_i^{+},i=1,\mathrm{.Math.},N{b}_i^{-}=.Math.-\sqrt{\frac{T_i}{p_{\mathrm{ii}}}}+S_i.Math.\mathrm{and}{b}_i^{+}=.Math.\sqrt{\frac{T_i}{p_{\mathrm{ii}}}}+S_i.Math.& \left(22\right)\end{array}$

(54) Search intervals also have to be restricted to take account of the maximum transmission power constraint, a.sub.a. This constraint imposes that each component a.sub.i in a should remain between two bounds:
.sub.i.sup.a.sub.i.sub.i.sup.+, i=1, . . . ,N(23)

(55) Therefore, finally, the search interval I.sub.i for each component a.sub.i is reduced to:
sup(.sub.i.sup.,b.sub.i.sup.)a.sub.iinf(.sub.i.sup.+,b.sub.i.sup.+)(24)

(56) Decoding then continues as follows; the first step is to choose a component a.sub.N within the interval I.sub.N=[sup(.sub.N.sup.,b.sub.N.sup.),inf (.sub.N.sup.+,b.sub.N.sup.+)], and the next step is to search for a candidate for component a.sub.N-1 within the interval I.sub.N-1=[sup(.sub.N-1.sup.,b.sub.N-1.sup.),inf(.sub.N-1.sup.+,b.sub.N-1.sup.+)] for which the bounds were calculated from a.sub.N. If there is no value a.sub.N-1 within this interval, then we return to level N to select another candidate for component a.sub.N. The process continues from step to step until level 1 is reached. Once a vector has been found for which the components satisfy all conditions (24), the radius of the sphere is updated and the search process is iterated by scanning all intervals I.sub.i, until the vector closest to y.sub.exp is found. The symbol {circumflex over (v)}.sub.MAP* is given by {circumflex over (v)}.sub.MAP*=M.

(57) FIG. 2 shows the symbol decoding error rate at the relay, as a function of the signal to noise ratio.

(58) In the case shown, it has been assumed that N=4, K=2 and a maximum transmission power P.sub.max=1.

(59) 210 relates to the curve corresponding to the classical maximum likelihood (ML) decoding method and 220 relates to the curve corresponding to the MAP augmented lattice decoding method according to this invention. This figure confirms that the augmented lattice decoding method enables to achieve a lower symbol error rate for a given signal to noise ratio or to achieve a better signal to noise ratio for a given target symbol error rate. It should have been noted that the gain is higher when the dimension N of the lattice is high.

(60) Those skilled in the art will understand that other search algorithms for the closest neighbour within a lattice and particularly Schnorr-Euchner's decoding could be used instead of the sphere decoder method, without going outside the scope of this invention.

(61) We will disclose the MAP augmented lattice decoding method below, in a general framework.

(62) The decoding method aims at decoding a signal received through a noisy channel, said signal being composed of information symbols belonging to a predetermined alphabet. The probability distribution of information symbols within this alphabet is non-uniform, in other words some information symbols are more frequent than others. Noise affecting the channel is assumed to be white and Gaussian.

(63) It is assumed that symbols in the alphabet can be represented by points in a lattice with dimension N defined by the relation {x|x=Ma, aZ.sup.N} in which M is a lattice generator matrix. This condition is satisfied particularly when symbols belong to a QAM type modulation constellation. The alphabet is a finite sub-part of , defined as being the intersection between said lattice and a convex of .sup.N. However in the case of a QAM alphabet, it should be noted that the origin of the lattice is excluded. The different points in the lattice are weighted by different probability distributions due to the non-uniformity of the probability distribution of symbols in the alphabet.

(64) According to the invention, the probability distribution of symbols in the alphabet is modeled by a Gaussian distribution with variance .sub.V.sup.2.

(65) The signal to be decoded is expressed in the form y=x+z, where x is a point in and z is a noise vector with dimension N of which the components are random variables with variance .sup.2.

(66) FIG. 3 diagrammatically shows the flowchart for the augmented lattice decoding method according to a general embodiment of the invention.

(67) In step 310, a vector y is formed, representative of the received signal in a space with dimension N where N is the dimension of the lattice . This vector may for example be obtained by demodulation of the received signal.

(68) In step 320, the augmented vector

(69) 0$y_{\exp }=\left[\begin{array}{c}y\\ 0_N\end{array}\right]$
is constructed.

(70) In step 330, an augmented lattice .sub.exp with generator matrix

(71) $M_{\exp }=\left[\begin{array}{c}M\\ M\end{array}\right]$
is formed, in which M is the generator matrix of the lattice and

(72) $=\frac{{}^2}{{}_v^2}$
is the ratio between the variance of the noise and the variance of the Gaussian probability distribution modelling the non-uniform probability distribution of symbols in the alphabet.

(73) In step 340, a search is made for the closest neighbour to the augmented vector y.sub.exp in the augmented lattice .sub.exp, in other words the vector of .sub.a minimising the distance y.sub.expM.sub.expa.sup.2, where .sub.a is a part of Z.sup.N reflecting a maximum energy constraint of the received signal.

(74) In step 350, the received symbol in the sense of the MAP criterion is estimated by {circumflex over (v)}.sub.MAP*=M.

(75) It will be understood that the search for the closest neighbour in the lattice can be made using a sphere decoder or a stack decoder with spherical bound, as mentioned above. The different known sphere decoding variants are applicable in this case, particularly those implementing enumeration of points making use of Pohst's algorithm.

(76) Those skilled in the art will understand that decoding of sum symbols for a channel of a cooperative network is a special case of decoding in FIG. 3 since these sum symbols form part of an alphabet obtained by superposition of the elementary alphabets of the different source terminals and that the distribution of sum symbols within this alphabet is non-uniform.

(77) Finally as mentioned above, other closest neighbour search algorithms in a lattice, and particularly Schnorr-Euchner's decoding, could be used without going outside the scope of this invention.