A RECEIVER, A PLURALITY OF TRANSMITTERS, A METHOD OF RECEIVING USER DATA FROM MULTIPLE TRANSMITTERS, AND A METHOD OF TRANSMITTING USER DATA

Abstract

A method is provided of receiving user data from multiple transmitters, the user data from each transmitter having been encoded as a Low Density Lattice codeword, and the multiple Low Density Lattice codewords having been transmitted so as to be received as a combined signal at a receiver, the method of receiving comprising the steps of: (i) receiving the signal, (ii) calculating coefficients of linear combinations of the codewords from the multiple transmitters, (iii) calculating a scaling factor to be applied to the signal based on the coefficients, (iv) applying the scaling factor to the signal to provide a linear combination of the codewords, (v) decoding the linear combination of the codewords based on channel state information to obtain an optimal independent linear combination of user data, (vi) repeating steps (ii), (iii) (iv) and (v) to obtain at least as many optimal independent linear combinations as the number of transmitters, and recovering the user data from the optimal independent linear combinations.

Claims

1. A method of receiving user data from multiple transmitters, the user data from each transmitter having been encoded as a Low Density Lattice codeword, and the multiple Low Density Lattice codewords having been transmitted so as to be received as a combined signal at a receiver, the method of receiving comprising: (i) receiving the signal, (ii) calculating coefficients of linear combinations of the codewords from the multiple transmitters, (iii) calculating a scaling factor to be applied to the signal based on the coefficients, (iv) applying the scaling factor to the signal to provide a linear combination of the codewords, (v) decoding the linear combination of the codewords based on channel state information to obtain an optimal independent linear combination of user data, (vi) repeating the calculating coefficients, calculating a scaling factor, applying and decoding to obtain at least as many optimal independent linear combinations as the number of transmitters, and recovering the user data from the optimal independent linear combinations.

2. A method of receiving according to claim 1, in which the calculation of the scaling factor comprises applying a minimum mean square error, MMSE, criterion to minimise variance of effective noise.

3. A method of receiving according to claim 1, in which the calculation of the coefficients comprises maximising a virtual rate of the linear combination of codewords.

4. A method according to claim 1, in which the decoding linear combinations comprises iterative cycles, each cycle comprising calculating a variable node message and calculating a check node message.

5. A method according to claim 4, in which obtaining each optimal independent linear combination comprises, after the final iteration, estimating probability density functions of codeword elements.

6. A method according to claim 1, in which the linear combination of codewords is itself a valid codeword of the Low Density Lattice.

7. A method according to claim 1, in which the recovering user data from the optimal independent linear combinations comprises taking a pseudo-inverse of a matrix of coefficients of the optimal independent linear combinations.

8. A method according to claim 1, in which the transmitters are user terminals for cellular wireless telecommunications.

9. A receiver configured to receive user data from multiple transmitters, the user data from each transmitter having being encoded as a Low Density Lattice codeword, and the multiple Low Density Lattice codewords having been transmitted so as to be received as a combined signal at the receiver, the receiver comprising: a receiving stage configured to receive the signal; an iterative processing stage configured to provide at least as many optimal independent linear combinations as the number of transmitters, the iterative processing stage comprising: a processor configured to calculate coefficients of linear combinations of the codewords from the multiple transmitters, a processor configured to calculate a scaling factor to be applied to the signal based on the coefficients, a processor configured to apply the scaling factor to the signal to provide a linear combination of the codewords, and a decoder configured to estimate an optimal linear combination of user data based on channel state information and the linear combination of the codewords; and the receiver also comprises a recovery stage configured to recover the user data from the optimal independent linear combinations.

10. A receiver according to claim 9, which is a base station for cellular wireless communications.

11. A receiver according to claim 9, in which the decoder is a Single-Input Single-Output, SISO, decoder.

12. A method of transmitting user data as codewords of a Low Density Lattice, wherein each transmitter encodes its user data into a respective codeword for transmission and transmits the codeword on a carrier signal over air; wherein a plurality of the transmitters use a shared Low Density Lattice codebook for the encoding.

13. A method of transmitting according to claim 12, in which the transmitters are user terminals for wireless cellular telecommunications.

14. A plurality of transmitters configured to transmit towards a receiver respective data as codewords of a Low Density Lattice, wherein each transmitter encodes its respective data into a respective codeword for transmission and transmits the codeword via a carrier signal over air; wherein the plurality of the transmitters use a shared Low Density Lattice codebook for the encoding.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0045] An embodiment of the present invention will now be described by way of example and with reference to the drawings, in which:

[0046] FIG. 1 is a diagram illustrating the capacity of 4G systems as a function of SINR for various modulation schemes, and the Shannon bound,

[0047] FIG. 2 is a diagram illustrating a known Sparse Code Multiple Access (SCMA) encoder (PRIOR ART), and

[0048] FIG. 3 is a diagram illustrating a Low Density Lattice Multiple Access (LDLMA) encoder according to a first embodiment for comparison with FIG. 2,

[0049] FIG. 4 is a diagram illustrating encoding and decoding procedure according to the first embodiment,

[0050] FIG. 5 is a diagram illustrating in more detail the encoding shown in FIG. 4 including generation of an LDLMA codeword from user data, and

[0051] FIG. 6 is a flowchart illustrating in more detail the decoding shown in FIG. 4.

DETAILED DESCRIPTION

[0052] When considering the known media access method of the SCMA system mentioned above with reference to the Nikopour paper and FIG. 2, the inventors realised that the complexity of the joint multiuser detection used in SCMA quickly grows with the number of users. This essentially inhibits a practical deployment of the proposed technology as operators require scalable solutions.

Low Density Lattice Multiple Access (LDLMA)

[0053] The inventors realised that it is possible to provide multi-user medium access, based on multi-dimensional low density lattice codes (LDLC). We refer to this as the low density lattice multiple access (LDLMA)

[0054] Low density lattice codes as such are known from the paper by N. Sommer, M. Feder, and O. Shalvi, Low-density lattice codes, Information Theory, IEEE Transactions on, vol. 54, no. 4, pp. 1561-1585, April 2008.

[0055] As shown in FIGS. 3 and 4, each user terminal (user equipment, UE) 2 includes a respective LDLC encoder 4, and a single LDLC lattice codebook is used for encoding binary data 1 as codewords 9 of all network users.

[0056] As shown in FIG. 4, accordingly, a receiver 6 receives a combination 8 of all transmitted codewords 9. Since all users use the same lattice, the received linear combination of multiple codewords 9 is also an element of the lattice codebook used. Thus, the receiver 6 only needs to decode linear combinations 10 of users' LDLC codewords rather than separating them as required by standard joint detection schemes. A single-input-single-output (SISO) LDLC decoder 12 performs this decoding by exploiting the posterior probability of linearly combined codewords in an iterative manner. This results a decoding complexity which is linear even when the number of users is large.

[0057] In this approach, the individual codewords of distinct network users are detected by estimating the best combination coefficients 14 subject to the knowledge of channel state information and the received combined codeword.

[0058] This approach does not require the receiver 6, for example a base station (BS) 7, to distinguish each user's codeword by using joint-multiuser detection. Instead the receiver 6 estimates the best linear combination of users' codewords then retrieves the individual user's data 16 by solving a set of linear equations for the estimated best coefficients. The base station does not need to separate each user's codeword so a Single-Input Single-Output (SISO) decoder 12 is sufficient.

[0059] The encoding and decoding scheme may, of course, be implemented in either or both of uplink and downlink. Especially in the downlink (i.e. towards the user terminal), a SISO decoder may be used (having linear complexity), which reduces the hardware complexity of the mobile handset and saves user terminal battery energy.

[0060] The above is an outline. More detail is provided below.

Low Density Lattice Code

[0061] An n-dimensional lattice, denoted by , is a set of points in R.sup.n such that if x, y, then x+y, and if x, then x. A lattice can always be written in terms of a lattice generator matrix GR.sup.nn

={x=Gv:vZ.sup.n}.

[0062] A low-density lattice code (LDLC) is constructed by extending the well-known low-density parity check codes (LDPC); this is done by extending the parity check matrix and syndrome of LDPC from operating over finite field to a real or complex field. An n dimensional LDLC is an n-dimensional lattice code with a non-singular generator matrix G satisfying det|G|=1, for which the parity check matrix H=G.sup.1 is sparse.

[0063] The row or column degree of H is defined as the number of nonzero elements in row or column, respectively. An n-dimensional LDLC is regular if all the row degrees and column degrees of the parity check matrix are equal to a common degree d. An n-dimensional regular LDLC with degree d is called Latin square LDLC if every row and column of the parity check matrix has the same nonzero values, except for a possible change of order and random signs. The sorted sequence of these d values is referred to as the generating sequence of the Latin square LDLC.

[0064] For example, a parity check matrix of a real LDLC with dimension n=6, row degree 4, column degree 3 and generating sequence {1,0.8,0.5} is as follows:

[00001]$H=\left[\begin{array}{cccccc}-0.8& 0.8& 0& 0.5& 0& -1\\ 0& 0& 1& -0.5& 1& -0.8\\ -0.5& 1& 0& -0.8& 0& 0.5\\ 1& 0& 0.8& 0& 0.5& 0\\ 0& -0.5& 0& 1& 0.8& 0\end{array}\right],$

Encoding

[0065] The encoding scheme is shown in more detail in FIG. 5.

[0066] As shown in FIG. 5, encoding in the encoder 4 involves power control 18 by Hypercube shaping, user data encoding 20, and transmission of that data, as described below.

Power Control

[0067] In practice, we adopt a power control (i.e. shaping) algorithm so that LDLC codewords meet transmission power constraints. Accordingly, each user terminal 2 uses hypercube shaping, based on a lower triangular parity-check matrix H, to transfer the integer information vector v.sub.l to another integer vector v.sub.l such that x.sub.l=Gv.sub.l satisfies the power constraint.

[0068] The hypercube shaping operation is given by

v.sub.l,k=v.sub.l,kMr.sub.l,k,

[0069] where r.sub.l,k is calculated as

[00002]$r_{l,k}=.Math.\frac{1}{M}.Math.\left(v_{l,k}-\underset{i=1}{\overset{k-1}{.Math.}}.Math.H_{k,i}.Math.x_{l,i}^{}\right).Math.$

[0070] Due to the linearity of LDLC, x.sub.l=x.sub.l mod from v.sub.l=v.sub.l mod M, where M is constellation size.

User Data Encoding

[0071] During user data transmission, binary user data are grouped to represent integers, and then mapped onto n-dimensional codewords of the LDLC lattice.

Transmission

[0072] Each codeword can be mapped onto distinct OFDM subcarriers or single antenna element of MIMO system.

Reception and Decoding

[0073] The reception and decoding stages are shown in FIG. 6 and with reference to FIG. 4.

[0074] As shown in FIG. 6, reception (step a) is followed by signal processing involving calculating (step b) the scaling factor and coefficients to apply and applying them (step c). The next stage is to one of obtaining (step d) the linear combination of users' messages then recovering (step e) the message of each individual user. These stages are considered below then an illustrative example is provided.

Reception of Superimposed Codeword (Step a)

[0075] Suppose the base station (BS) 7 serves L users such that the received signal at the base station is given by

[00003]$y=\underset{l=1}{\overset{L}{.Math.}}.Math.h_l.Math.x_l+z,$

where x.sub.l is the transmitted lattice codeword with dimension n; h.sub.l is the channel coefficient; and zCN(0,.sup.2I.sup.n) is the noise.

Signal Processing (Step b, Step c)

[0076] In order to form the linear combination of LDLC codewords, the base station 7 scales the received signal by a factor and expands the scaled signal as

[00004]$.Math..Math.y=\underset{\underset{t}{}}{\underset{l=1}{\overset{L}{.Math.}}.Math.a_l.Math.x_l}+\underset{\underset{z_{\mathrm{eff}}}{}}{\underset{l=1}{\overset{L}{.Math.}}.Math.\left(.Math..Math.h_l-a_l\right).Math.x_l+.Math..Math.z},$

[0077] where t is the linear combination of users' codewords and z.sub.eff is the effective noise.

[0078] Since the noise depends on the codeword, the optimal scaling factor is obtained for this purpose by applying a minimum mean square error (MMSE) criterion such that the variance of the effective noise is minimized, as given by

[00005]${}_{\mathrm{opt}}=\frac{h^H.Math.a.Math..Math.P}{{.Math.h.Math.}^2.Math.P+{}^2},$

[0079] where P is the power of transmitted codeword; and the coefficient vector a=[a.sub.1, . . . , a.sub.L] is determined by maximizing the virtual rate of t, given by

[00006]$R\left(h,a\right)=\underset{a{Z}^2}{\max }.Math.{\log }_2\left(\frac{P}{{.Math.{}_{\mathrm{opt}}.Math.h-a.Math.}^2.Math.P+.Math.{}_{\mathrm{opt}}.Math..Math.{}^2}\right).$

[0080] Substituting .sub.opt into the above equation results in:

[00007]$R\left(h,a\right)=\underset{a{Z}^2}{\max }.Math.{\log }_2\left(\frac{P}{{\mathrm{aMa}}^H}\right),$

[0081] where

[00008]$M={\mathrm{SNRI}}_L-\frac{{\mathrm{SNR}}^2.Math.{\mathrm{hh}}^H}{\left(1+\mathrm{SNR}.Math.{.Math.h.Math.}^2\right)}.$

Formally, let M=LL.sup.H be the Cholesky decomposition of M, where L is some lower triangular matrix. (The existence of L follows from the fact that M is Hermitian and positive-definite.). This gives aMa.sup.H=aL.sup.2. Hence, the above rate optimization is equivalent to solving the following shortest vector problem:

[00009]$M={\mathrm{SNRI}}_L-\frac{\mathrm{SNR}.Math.{}^2\mathrm{hh}^H}{\left(1+\mathrm{SNR}.Math.{.Math.h.Math.}^2\right)}.$

Obtaining Linear Combinations of Users' Messages (Step d)

[0082] After obtaining a.sub.opt, the base station 7 decodes the desired linear combination t. In order to successfully recover L user's messages, the base station has to decode the K optimal and independent linear combinations, where KL.

[0083] To decode the desired t, the proposed LDLMA scheme has to form the following distribution:

[00010]$a_{\mathrm{opt}}=\underset{a{Z}^2,a0}{\arg .Math..Math.\min }.Math.{.Math.a.Math..Math.L.Math.}^2.$

[0084] where t.sub.j is the j-th component of t; l is the lattice codeword and l.sub.j is the j-th component of it; d(l,y) denotes the Euclidean distance between y and l; and .sup.2 (,a) is the variance of effective noise, given by

.sup.2(,a)=ha.sup.2P+.sup.2.

[0085] One expands t as follows

[00011]$t=\underset{=1}{\overset{L}{.Math.}}.Math..Math.a_{}.Math.x_{}=\underset{=1}{\overset{L}{.Math.}}.Math..Math.a_{}.Math.{\mathrm{Gv}}_{}=G.Math.\underset{\underset{r}{}}{\underset{=1}{\overset{L}{.Math.}}.Math..Math.a_{}.Math.v_{}},$

[0086] where t itself is a valid codeword of LDLC such that r, which is the linear combination of users' messages, is extracted by passing t through the SISO LDLC decoder 12, given by {circumflex over (r)}=LDLCDecoder(y), where {circumflex over (r)} is the estimated signal. This is described in more detail as follows.

[0087] The decoder 12 iteratively estimates f.sub.T.sub.j.sub.|Y (t.sub.j|y) by using Gallager's message passing algorithm over real or complex field. Messages sent by the variable nodes are probability density functions (PDFs) of the dimensional-wise component of t while the messages sent by the check nodes are the periodic extensions of PDFs of dimensional-wise component of t. Each variable node corresponds to a single element of the lattice codeword. Each check node corresponds to a check equation, in other words a row of matrix H.

[0088] Let t.sub.1, . . . , t.sub.j, . . . , t.sub.n and c.sub.1, . . . , c.sub.j, . . . , c.sub.n denote the variable nodes and check nodes respectively. The SISO decoder 12 for the LDLC lattice combination t essentially operates by applying the following method:

[0089] Initialization: the variable node t.sub.1 sends the message

[00012]$f_j^{\left(0\right)}\left(t\right)=\frac{1}{\sqrt{2.Math.{}^2\left(,a\right)}}.Math.\exp \left(-\frac{{.Math..Math..Math.y_j-t.Math.}^2}{2.Math.{}^2\left(,a\right)}\right)$

to all neighbouring check nodes.

[0090] Basic iteration of check node message: each check node shares a different message with the neighbouring variable nodes. Suppose there are m (equals the row degree of H) variable nodes connected to the check node c.sub.j. Those variable nodes are denoted by t.sub.j,,{1, . . . ,m} and we have an appropriate check equation

[00013]$\underset{=1}{\overset{m}{.Math.}}.Math..Math.{}_{}.Math.t_{j,}Z,$

where Z is the integer set and .sub. is the entry of H. The message that was sent from t.sub.j, to the check node in the previous half-iteration is denoted as f.sub.(t),{1, . . . ,m}. The calculation of the message that the check node c.sub.j sends back to the variable node t.sub.j, follows the three basic steps:

[0091] 1) Convolution step: all messages excluding j, (t) are convolved, where

[00014]$\frac{t}{{}_{}}$

will be substituted into f.sub.(t), {1, . . . ,m}/{}:

[00015]${\tilde{p}}_{}\left(t\right)=f_1\left(\frac{t}{{}_1}\right)*\mathrm{.Math.}*f_{-1}\left(\frac{t}{{}_{-1}}\right)*f_{+1}\left(\frac{t}{{}_{+1}}\right)*\mathrm{.Math.}*f_m\left(\frac{t}{{}_m}\right)$

[0092] 2) Stretching step: {tilde over (p)}.sub. (t) is stretched by .sub. to p.sub.(t)={tilde over (p)}.sub.(.sub.t).

[0093] 3) Periodic extension step: p.sub.(t) is extended to a periodic function with period

[00016]$\frac{t}{.Math.{}_{}.Math.}$

given by

[00017]$P_{}\left(t\right)=\underset{i=-}{\overset{}{.Math.}}.Math..Math.p_{}\left(t-\frac{i}{{}_{}}\right),$

[0094] where P.sub.(t) is the final message that is sent to the variable node t.sub.j,.

[0095] Basic iteration of variable node message: each variable node sends a message to the neighbouring check node.

[0096] Suppose there are e (equals to the column degree of H) check nodes connected to the variable node t.sub.j, which are denoted by c.sub.j,, {1, . . . ,e}. The message that the check node c.sub.j, sends back to the variable node t.sub.j in the previous half-iteration is denoted by P.sub.(t). The calculation of the message that is sent from the variable node t.sub.j to the check node c.sub.j, follows the two basic steps:

[0097] 1) The product step:

[00018]${\tilde{f}}_{}\left(t\right)=e^{-\frac{{\left(.Math..Math.y_j-t\right)}^2}{2.Math.{}^2\left(,a\right)}}.Math.\underset{\underset{}{=1}}{\overset{e}{.Math.}}.Math..Math.P_{}\left(t\right).$

[0098] 2) the normalization step:

[00019]$f_{}\left(t\right)=\frac{{\tilde{f}}_{}\left(t\right)}{{}_{-}^{}.Math.{\tilde{f}}_{}\left(t\right).Math.\mathrm{dt}}.$

[0099] Repetition: The basic iteration is repeated until the iteration threshold is achieved.

[0100] Final Decision: To extract the desired linear combination of users' message, r, the final PDF of the codeword elements t.sub.1, . . . , t.sub.j, . . . , t.sub.n should be estimated in the final iteration without excluding any check node message in the product step, given by

[00020]${\tilde{f}}_{j,\mathrm{final}}\left(t\right)=e^{-\frac{{\left(.Math..Math.y_j-t\right)}^2}{2.Math.{}^2\left(,a\right)}}.Math.\underset{=1}{\overset{e}{.Math.}}.Math..Math.P_{}\left(t\right).$

[0101] Then, the estimated codeword element can be obtained from {circumflex over (t)}=arg max.sub.t{tilde over (f)}.sub.j,final(t). At last, the desired r is calculated as {circumflex over (r)}=H.Math.t.

Message Recovery (Step e)

[0102] Given the channel state information, the base station 7 obtains the best K linear combination {circumflex over (r)}'s, indexed as [{circumflex over (r)}.sub.1, . . . , {circumflex over (r)}.sub.K], namely, at least as many optimal independent linear combinations are obtained as the number of transmitters. The coefficients of these linear combinations form a matrix

[00021]$A=\left[\begin{array}{c}{a}_1\\ \mathrm{.Math.}\\ a_K\end{array}\right].$

In order to successfully recover the users' messages [v.sub.1, . . . , v.sub.L], the rank of A should be no less than L. As such, the base station takes the pseudo inverse to recover [v.sub.1, . . . , v.sub.L], given by

[00022]$\left[\begin{array}{c}{\hat{v}}_1\\ \mathrm{.Math.}\\ {\hat{v}}_L\end{array}\right]={\left(A^T.Math.A\right)}^{-1}.Math.A^T.Math.\left[\begin{array}{c}{\hat{r}}_1\\ \mathrm{.Math.}\\ {\hat{r}}_K\end{array}\right].$

Example

[0103] Here is a simple example to illustrate the decoding procedure of LDLMA: there are 2 user terminals with access to the base stations. Both user terminals employ the same LDLC codebook , where the codewords are x.sub.1=Gv.sub.1 and x.sub.2=Gv.sub.2, respectively. Assume that the channel coefficient vector is h=[h.sub.1 h.sub.2].sup.T=[1 2.2].sup.T such that the received signal is y=1x.sub.1+2.2x.sub.2+z. Assuming after the rate optimization, the base station selects, say, .sub.1=5 and .sub.2=4 as the best two scale factors such that we have

[00023]$5.Math..Math.y=\underset{\underset{t_1}{}}{5.Math..Math.x_1+11.Math..Math.x_2}+5.Math..Math.z,.Math.\mathrm{and}$$\begin{array}{c}4.Math..Math.y=.Math.4.Math..Math.x_1+8.8.Math..Math.x_2+4.Math..Math.z\\ =.Math.\underset{\underset{t_2}{}}{4.Math..Math.x_1+9.Math..Math.x_2}+\underset{\underset{z_{\mathrm{eff},2}}{}}{\left(-0.2.Math..Math.x_2+4.Math..Math.z\right)}.\end{array}$

[0104] where

[00024]$A=\left[\begin{array}{cc}5& 11\\ 4& 9\end{array}\right]$

as t.sub.1,t.sub.2 , the SISO lattice decoder over A iteratively estimates the distributions f.sub.T.sub.1.sub.|Y, (t.sub.1|y) and f.sub.T.sub.2.sub.|Y, (t.sub.2|y) to extract r.sub.1=5v.sub.1+11v.sub.2 and r.sub.2=4v.sub.1+9v.sub.2 because of the following equalities: 5x.sub.1+11x.sub.2=G (5v.sub.1+11v.sub.2) and 4x.sub.1+9x.sub.2=G(4v.sub.1+9v.sub.2). Once we have r.sub.1, r.sub.2 and A, we obtain the users' data v.sub.1 and v.sub.2 by taking the inverse of A over r.sub.1 and r.sub.2.

[0105] The present invention may be embodied in other specific forms without departing from its essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes that come within the meaning and range of equivalency of the claims are to be embraced within their scope.

[0106] A person skilled in the art would readily recognize that steps of various above-described methods can be performed by programmed computers. Some embodiments relate to program storage devices, e.g., digital data storage media, which are machine or computer readable and encode machine-executable or computer-executable programs of instructions, wherein said instructions perform some or all of the steps of said above-described methods. The program storage devices may be, e.g., digital memories, magnetic storage media such as a magnetic disks and magnetic tapes, hard drives, or optically readable digital data storage media. Some embodiments involve computers programmed to perform said steps of the above-described methods.