METHOD AND DEVICE FOR COMPUTING SOFT ESTIMATE OF CODED BITS FORMING TRANSMITTED SYMBOL VECTORS

Abstract

The present invention concerns a method for computing a soft estimate of coded bits forming transmitted symbol vectors of a multi-dimentional constellation, the transmitted vectors being received by a receiver from a source through a channel, characterized in that the method comprises the steps of: obtaining from the receiver memory a predetermined list of vectors with integer or gaussian integer entries, obtaining a channel matrix estimation between the source and the receiver and received symbols, obtaining a reduced channel matrix and a change of basis matrix from the channel matrix estimation, computing a vector with integer coordinates at least from the reduced channel matrix and the received symbols, shifting the predetermined list of vectors around the vector with integer coordinates and obtaining a shifted list of vectors, computing a soft estimation of the coded bits according to vectors belonging to the shifted list of vectors and to a transformed multi-dimentional constellation obtained from the multi-dimentional constellation and the change of basis matrix.

Claims

1-15. (canceled)

16. Method for computing a soft estimate of coded bits forming transmitted symbol vectors of a multi-dimentional constellation, the transmitted vectors being received by a receiver from a source through a channel, characterized in that the method comprises the steps of: obtaining from the receiver memory a predetermined list of vectors with integer or gaussian integer entries, obtaining a channel matrix estimation H between the source and the receiver and received symbols y, obtaining a reduced channel matrix H.sub.r and a change of basis matrix T from the channel matrix estimation, where H=H.sub.r T, computing a vector with integer coordinates x at least from the reduced channel matrix and the received symbols, the vector with integer coordinates being the closest vector with integer coordinates to an observation y=H.sub.r.sup.1y, shifting the predetermined list of vectors around the vector with integer coordinates {circumflex over (x)} and obtaining a shifted list of vectors list .sub.s={x[{square root over (1)}].sup.N|x}, removing the vectors of .sub.s not belonging to a transformed multi-dimentional constellation .sub.R which is the set of all possible vectors of symbols x=Tz in order to obtain a list .sub.s.sub.R, computing a soft estimation of the coded bits according to the list of vectors .sub.s .sub.R vectors belonging to the shifted list of vectors and to a transformed multi-dimentional constellation obtained from the multi-dimentional constellation and the change of basis matrix.

17. Method according to claim 16, characterized in that the predetermined list of vectors is a spherical predetermined list of vectors around an origin of a lattice or a cubical list of vectors comprising all the vectors having a real and imaginary parts bounded by a lower and an upper bounds.

18. Method according to claim 16, characterized in that the vector with integer coordinates is obtained by successively applying a MMSE filter computed from the reduced channel matrix and performing a rounding to integer values.

19. Method according to claim 16, characterized in that the reduced channel matrix is obtained by using Minkovski, Korkine-Zolotarev, or Lenstra Lenstra Lovsz reduction.

20. Method according to claim 16, characterized in that the reduced channel matrix is obtained by selecting one reduced channel or one change of basis matrix according to a given figure of merit from a set of pre-computed reduced channel or of change of basis matrices.

21. Method according to claim 20, characterized in that the figure of merit is the value of the trace of a matrix obtained by a multiplication of the inverse of the reduced channel matrix by the conjugate transpose of the inverse of the reduced channel matrix.

22. Method according to claim 20, characterized in that the figure of merit is determined from an upper triangular matrix obtained by a decomposition of the reduced channel matrix into a unitary matrix and the upper triangular matrix.

23. Method according to claim 20, characterized in that the set of reduced channels or of change of basis matrices is obtained from an offline pre-processing of channel reduction algorithms on a random set of channel matrices.

24. Method according to claim 23, characterized in that the offline pre-processing of channel reduction algorithms on a random set of channel matrices is performed, a given number of times, by obtaining a set of candidate matrices of change of basis matrix, by initializing the set of candidate matrices to an empty set, and an associated vector of probabilities to an empty vector, by generating randomly a channel matrix according to an expected distribution of channels, with centered and unit variance entries, by applying a lattice reduction in order to obtain a change of basis matrix, by adding the obtained change of basis matrix to the set of candidate matrices if the obtained change of basis matrix is not already in the set of candidate matrices or by modifying a probability associated to the obtained change of basis matrix, and selecting a predetermined number of change of basis matrices of the set of candidate matrices having the highest probability.

25. Method according to claim 23, characterized in that the offline pre-processing of channel reduction algorithms on a random set of channel matrices is performed, a given number of times, by obtaining a set of candidate matrices of reduced channel matrices, by initializing the set of candidate matrices to an empty set and an associated vector of probabilities to an empty vector, by generating randomly a channel matrix according to an expected distribution of channels, with centered and unit variance entries, by applying a lattice reduction in order to obtain a reduced channel matrix, by adding the obtained reduced channel matrix to the set of candidate matrices if the obtained reduced channel matrix is not already in the set of candidate matrices or by modifying a probability associated to the obtained reduced channel matrix, and selecting a predetermined number of reduced channel matrices of the set of candidate matrices having the highest probability.

26. Method according to claim 20, characterized in that the channel matrices are cyclotomic precoded diagonal channels and the set of reduced channel matrix is obtained from an offline pre-processing on a cyclotomic field of a cyclotomic rotation.

27. Method according to claim 16, characterized in that the computing of the soft estimation of the coded bits according to the constellation vectors belonging to the shifted list of vectors is performed by a multiplying of the inverse of the change of basis matrix by the vector with integer coordinates.

28. Method according to claim 16, characterized in that the computing of the soft estimation of the coded bits according to the constellation vectors belonging to the shifted list of vectors is performed using received transmitted symbol vectors through the channel.

29. Device for computing a soft estimate of coded bits forming transmitted symbol vectors of a multi-dimentional constellation, the transmitted vectors being received by a receiver from a source through a channel, characterized in that the device comprises: means for obtaining from the receiver memory a predetermined list of vectors with integer or gaussian integer entries, means for obtaining a channel matrix estimation H between the source and the receiver and received symbols y, means for obtaining a reduced channel matrix H.sub.r and a change of basis matrix T from the channel matrix estimation, where H=H.sub.rT, means for computing a vector with integer coordinates x at least from the reduced channel matrix and the received symbols, the vector with integer coordinates being the closest vector with integer coordinates to an observation y=H.sub.r.sup.1y, means for shifting the predetermined list of vectors around the vector with integer coordinates {circumflex over (x)} and obtaining a shifted list of vectors list .sub.s={x[{square root over (1)}].sup.N|x{circumflex over (x)}}, means for removing the vectors of .sub.s not belonging to a transformed multi-dimentional constellation .sub.R which is the set of all possible vectors of symbols x=Tz in order to obtain a list .sub.s.sub.R, means for computing a soft estimation of the coded bits according to the list of vectors .sub.s.sub.R vectors belonging to the shifted list of vectors and to a transformed multi-dimentional constellation obtained from the multi-dimentional constellation and the change of basis matrix.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0061] FIG. 1 represents a wireless system in which the present invention is implemented.

[0062] FIG. 2 is a diagram representing the architecture of a receiver in which the present invention is implemented.

[0063] FIG. 3 represents an algorithm for performing soft estimation of received coded bits based on a quantized list alphabet for a shifted list sphere decoder.

[0064] FIG. 4 represent a geometrical explanation of the constellation transformations by the channel and a lattice reduction.

DESCRIPTION OF EMBODIMENTS

[0065] FIG. 1 represents a wireless system in which the present invention is implemented.

[0066] The present invention will be disclosed in an example in which the signals transferred by a source Src are transferred to receivers Rec.

[0067] For example, the source Src may be included in a satellite or in a terrestrial transmitter and broadcasts signals to at least one receiver, the source Src may also transfer signals to a single receiver Rec.

[0068] The receiver Rec may be a mobile terminal to which data like video signals are transferred.

[0069] In order to improve the performance of hard output receivers, lattice reductions may be used. A lattice reduction is performed each time the channel H changes, which provides the following decomposition:

H=H.sub.rT

where H.sub.r is reduced for example according to Minkovski, Korkine-Zolotarev, or Lenstra Lenstra Lovsz reductions, which involves that H.sub.r generates the same lattice as H but has more orthogonal basis vectors.

[0070] The change of basis matrix T is unimodular with integer, or Gaussian integer in the complex input case, entries, which involves that the absolute value of the basis matrix determinant is one, and that the inverse of the basis matrix has integer, or Gaussian integer in the complex case, entries.

[0071] By definition, we note the transformed multi-dimensional constellation .sub.R={Tz}, i.e., is the set of all possible vectors of symbols x=Tz.

[0072] Thus, the hard output decoder usually performs a hard output decision based on the channel model y=H.sub.rx+T.sub.i and then uses the relationship x=Tz for obtaining an estimate on z by using a linear decoder. The performance of such detectors is good, which involves that the orthogonality assumption is quite good. The lattice reduction step has a high complexity, but can be mutualized between several decoding steps as soon as the channel does not change. This can be combined with the shifted list decoder as a pre-processing step.

[0073] The present invention, first takes benefit of the almost-orthogonality provided by lattice reductions. Indeed, after applying the lattice decomposition H=H.sub.rT, one can obtain the following channel model

H.sub.r.sup.1y=Tz+

where can be approximated as a white Gaussian noise and the new SNR as .

[0074] This channel model is by definition called RCM for Reduced Channel Model or channel model after latice reduction by opposition to the OCM for Observation Channel Model corresponding to the case where no latice reduction is performed.

[0075] According to the invention, the receiver Rec computes a soft estimate of coded bits forming transmitted symbol vectors of a multi-dimentional constellation, the transmitted vectors being received by a receiver from a source through a channel by: [0076] obtaining from the receiver memory a predetermined list of vectors with integer or gaussian integer entries, [0077] obtaining a channel matrix estimation between the source and the receiver and received symbols, [0078] obtaining a reduced channel matrix and a change of basis matrix from the channel matrix estimation, [0079] computing a vector with integer coordinates at least from the reduced channel matrix and the received symbols, [0080] shifting the predetermined list of vectors around the vector with integer coordinates and obtaining a shifted list of vectors, [0081] computing a soft estimation of the coded bits according to vectors belonging to the shifted list of vectors and to a transformed multi-dimentional constellation obtained from the multi-dimentional constellation and the change of basis matrix.

[0082] FIG. 2 is a diagram representing the architecture of a receiver in which the present invention is implemented.

[0083] The receiver Rec has, for example, an architecture based on components connected together by a bus 201 and a processor 200 controlled by the program as disclosed in FIG. 3.

[0084] It has to be noted here that the receiver Rec may have an architecture based on dedicated integrated circuits.

[0085] The bus 201 links the processor 200 to a read only memory ROM 202, a random access memory RAM 203 and a wireless interface 205.

[0086] The memory 203 contains registers intended to receive variables and the instructions of the programs related to the algorithm as disclosed in FIG. 3.

[0087] The processor 200 controls the operation of the wireless interface 205.

[0088] The read only memory 202 contains instructions of the program related to the algorithm as disclosed in FIG. 3, which are transferred, when the receiver Rec is powered on, to the random access memory 203.

[0089] Any and all steps of the algorithm described hereafter with regard to FIG. 3 may be implemented in software by execution of a set of instructions or program by a programmable computing machine, such as a PC (Personal Computer), a DSP (Digital Signal Processor) or a microcontroller; or else implemented in hardware by a machine or a dedicated component, such as an FPGA (Field-Programmable Gate Array) or an ASIC (Application-Specific Integrated Circuit).

[0090] In other words, the receiver Rec includes circuitry, or a device including circuitry, causing the receiver Rec to perform the steps of the algorithm described hereafter with regard to FIG. 3.

[0091] FIG. 3 represents an algorithm for performing soft estimation of received coded bits based on a quantized list alphabet for a shifted list sphere decoder.

[0092] More precisely, the present algorithm is executed by the processor 200 of the receiver Rec.

[0093] At step S30, the processor 200 performs an offline computation of a predetermined list of vectors [{square root over (1)}].sup.N.

[0094] For example, the processor 200 uses the method as disclosed in the paper of U. Finkce and M. Pohst entitled Improved Methods for calculating Vectors of short length in a Lattice including a complexity analysis published in Mathematics of computation vol 44 pp 463 in 1985 in order to obtain a spherical list of vectors around the origin of the lattice. The predetermined list can be of other form, like cubical by listing all the vectors of [{square root over (1)}].sup.N belonging to a cubic shape, i.e., the real and imaginary parts of the entries of which being bounded by a lower and upper bound. The size of the list is selected to match a target complexity, or size of chipset in FPGA implementations.

[0095] At next step S31, the processor 200 obtains observation y and matrix channel estimation H from the wireless interface I/F 205.

[0096] The vector y may be received across several antennas, time slots, or sub-carriers according to the definition of the transmission model.

[0097] The channel estimation H is for example obtained by a preceding channel estimation step that allows to estimate each coefficient of H, for example by the use of pilot symbols sent by the source Src.

[0098] In a MIMO channel, the source Src has N transmit antennas and the receiver Rec has M receive antennas. The coefficients of the MN matrix H are considered as gaussian independent identically distributed with zero mean unity variance.

[0099] In case of a Precoded diagonal fading channel, the Source Src linearly combines M=N QAM symbols with a MM precoding matrix and sends each of the M linear combinations in parallel on one of M fading channels. The parallel transmission is represented by a diagonal MM matrix , where .sub.i,i is the i-th diagonal coefficient of and represents the fading of the i-th parallel fading channel.

[0100] Thus, the MM matrix H represents the concatenation of the precoding step and the transmission on the parallel fading channels as H=.

[0101] At next step S32, the processor 200 computes a channel reduction=H.sub.rT. H.sub.r is the reduced channel matrix and T is the change of basis matrix. The computation of the channel reduction that provides matrices H.sub.r and T from the matrix H such that H=H.sub.rT is obtained from an LLL reduction as disclosed, for example, in the paper of A Lenstra, H Lenstra and L. Lovasz entitled Factoring polynomials with rational coefficients in Mathematische Annalen, vol 261, pp 515-532 1982.

[0102] The channel reduction is for example computed as disclosed in the paper of C. Ling W. H Mow and N. Howgrave-Graham entitled Variants of the LLL algorithm in digital communications. Complexity analysis and fixed complexity implementation Computing Research Repository vol abs/1006. 1661, 2010.

[0103] The channel reduction is for example computed as disclosed in the paper of C. P Schnorr entitled A hierarchy of polynomial time lattice basis reduction algorithms Theoretical Computer Science, vol 53, pp 201-224, 1987.

[0104] In a variant of realization, the processor 200, in order to enable complexity reduction in the receiver Rec, defines offline a set of candidate matrices T that are stored in memory without using a lattice reduction algorithm online.

[0105] The processor 200 obtains the channel matrix H, performs a loop on a predefined number of candidate change of basis matrices T belonging to a set of candidate matrices T, computes, for each candidate change of basis matrice T, the reduced channel H.sub.r=HT.sup.1 and the processor 200 defines a figure of merit for example as: [0106] the value of trace(H.sub.r.sup.1H.sub.r.sup.) that is minimized and is the transpose conjuguate operator, [0107] the value defined by .sub.j.sub.i=1.sup.j-1|R.sub.i,j/R.sub.i,i|.sup.2 that is maximized, where the matrix R is obtained by the QR decomposition H.sub.r=QR where Q is unitary and R is upper-triangular.

[0108] The processor 200 selects the couple (T, H.sub.r) that optimizes the figure of merit.

[0109] The processor 200 obtains the set of candidate matrices T in an offline optimization by initializing the set of candidate matrices T to an empty set, and an associated vector of probabilities to an empty vector. The processor 200 generates randomly the channel matrix H according to the expected distribution of channels, for example, according to an independent identically distributed complex Gaussian multivariate distribution, with centered and unit variance entries. The processor 200 then applies a lattice reduction, as already disclosed in order to obtain T and H.sub.r. The processor obtains a candidate matrix T as a result of the reduction and adds the obtained matrix T to the set of candidate matrices T if the obtained candidate matrix is not already in the set of candidate matrices T or modifies a probability of occurrence associated to the obtained matrix. The processor 200 repeats the operation a given number of times. Finally, the processor 200 selects a given number of matrices T of the set of candidate matrices T having the highest probability.

[0110] In a variant of realization, in order to enable complexity reduction in the receiver Rec, the processor 200 defines offline a set of candidate matrices H.sub.r that are stored in memory without using a lattice reduction algorithm online. The processor 200 obtains the channel matrix H, performs a loop on a predefined number of candidate matrices H.sub.r belonging to a set of candidate matrices H.sub.r, computes, for each candidate matrix H.sub.r, the candidate change of basis matrice

[0111] T=[[H.sub.r.sup.1H]] where [[.]] denotes a rounding of each coefficient of the candidate change of basis matrix to the closest integer value or gaussian integer and the processor 200 defines a figure of merit for example as the value of trace (TH.sup.1H.sup.T.sup.) that is minimized.

[0112] The processor 200 selects the couple (T, H.sub.r) that optimizes the figure of merit.

[0113] The processor 200 obtains a set of candidate matrices H.sub.r in an offline optimization by initializing the set of candidate matrices H.sub.r matrices to an empty set, and an associated vector of probabilities to an empty vector. The processor 200 generates randomly the channel matrix H according to the expected distribution of channels, for example, according to an independent identically distributed complex Gaussian multivariate distribution, with centered and unit variance entries. The processor 200 then applies a lattice reduction, as already disclosed in order to obtain T and H.sub.r. The processor 200 obtains a candidate matrix H.sub.r as a result of the reduction and adds the obtained matrix H.sub.r to the set of candidate matrices H.sub.r if the obtained candidate matrix is not already in the set of candidate matrices H.sub.r or modifies a probability associated to the obtained matrix. The processor 200 repeats the operation a given number of times. Finally, the processor 200 selects a given number of matrices H.sub.r of the set of candidate matrices H.sub.r having the highest probability.

[0114] If the channel matrices are cyclotomic precoded diagonal channels, the set of reduced channel matrix is obtained from an offline pre-processing on the cyclotomic field of the cyclotomic rotation.

[0115] Indeed, if is a cyclotomic rotation, we consider a set of candidate matrices .sub.q associated to the units of the cyclotomic field. The units can be built from the set of n fundamental units {u.sub.i} represented as vectors of size n.

[0116] For each fundamental unit, the processor 200 defines a diagonal matrix B.sub.i which diagonal elements are defined by diagB.sub.i={square root over (n)}u.sub.i, where the notation diag is extracting the diagonal elements of a matrix A into a vector diagA=[A.sub.1,1, . . . , A.sub.n,n].sup.T, where A.sub.i,i is the ith element of the ith row and column.

[0117] Finally, one can show that

[00003]${}_q,k{\left[\sqrt{-1}\right]}^{n^{}},{}_q=\underset{i}{.Math.}.Math.B_i^{k_i}$

Where n is a parameter lower or equal than n.

[0118] Thus, the processor 200 builds a set of candidates matrices .sub.q from a set of lattice vectors selected for example at random, or in other words from a random set of k vectors. Then, for each channel estimation H, the processor 200 computes =.sup.H, and selects a candidate .sub.q from such that

=.sub.q

where is the quantization error of into .sub.q, and for example such that the value max.sub.i(|log(|.sub.i|)|) is minimized.

[0119] Then, the algebraic property of the cyclotomic rotation gives T=.sup..sub.q and H.sup.r=, which allows to get the set of matrices T from the set of .sub.q.

[0120] At next step S33, the processor 200 computes the new observation of the RCM y=H.sub.r.sup.1y.

[0121] The new observation of the RCM y=H.sub.r.sup.1y is computed from the received observation y obtained at step S31 and the inverse of the reduced channel H.sub.r obtained at step S32.

[0122] At next step S34, the processor 200 determines an estimation {circumflex over (x)} of the closest vector of y in the RCM. The estimation x is a vector with integer coordinates.

[0123] The estimation {circumflex over (x)} of the closest vector of y in the RCM is for example obtained by first applying an MMSE filter on y based on the OCM, followed by a decision which is then multiplied by T in order to get {circumflex over (x)}.

[0124] The estimation {circumflex over (x)} of the closest vector of y in the RCM is for example obtained by taking the closest integer value (independently on the real and imaginary part if in complex dimension), i.e., by first computing x

[00004]$i.Math.\{\begin{array}{c}.Math.\left(x_i^{}\right)=.Math..Math.\left(y_i^{}\right).Math.\\ \left(x_i^{}\right)=.Math.\left(y_i^{}\right).Math.\end{array}$

[0125] Optionally, in order to make sure that x belongs to the multi-dimensional QAM modulation, an additional step is required that computes z=T.sup.1x and get z from

[00005]$i.Math.\{\begin{array}{c}.Math.\left(z_i^{}\right)=\min \left(\max \left(0,.Math.\left(z_i^{}\right)\right),2^{s_i/2}-1\right)\\ \left(z_i^{}\right)=\min \left(\max \left(0,\left(z_i^{}\right)\right),2^{s_i/2}-1\right)\end{array}$

in order to finally obtain {circumflex over (x)}=Tz.

[0126] At next step S35, the processor 200 shifts the predetermined list around {circumflex over (x)} to produce the list .sub.s={x[{square root over (1)}].sup.N|xx}. This is for example obtained by computing, for each , the set of vectors +{circumflex over (x)}.

[0127] At next step S36, the processor 200 removes the vectors of .sub.s not belonging to the transformed multi-dimentional constellation .sub.R and obtains the list .sub.s.sub.R.

[0128] In order to remove the vectors of not belonging to the transformed multi-dimentional constellation .sub.R, the processor 200 computes the list .sub.s={z[{square root over (1)}].sup.N|Tz.sub.s} which is the result of transforming the shifted list .sub.s by T.sup.1, and then applies the intersection with . Indeed, the implementation of this intersection .sub.s is more easy than computing .sub.s.sub.R directly, and can be performed as follows

for all z.sub.s [0129] check that i, 0(z.sub.i)2.sup.s.sup.i.sup./21 [0130] check that i, 0(z.sub.i) 2.sup.s.sup.i.sup./21 [0131] remove the vector z from .sub.s if one of the check is false

[0132] As a result, the list of remaining vectors is .sub.s, and the list .sub.s.sub.R is obtained by applying a transformation by T.

[0133] When the sets of matrices T are pre-computed and stored, the list of vectors .sub.s may be precomputed and stored for each possible T.

[0134] In another option, the processor 200 stores all lists .sub.s.sub.R for all possible values of T and R.

[0135] In another option, the processor 200 stores all lists .sub.s for all possible values of T and T.sup.1{circumflex over (x)}.

[0136] A next step S37, the processor 200 computes the soft estimation of the coded bits according to the list of vectors .sub.s.sub.R.

[0137] According to a preferred mode of realization, the processor 200 computes the LLR according to

[00006]$L.Math..Math.L.Math..Math.R_j=\log .Math.\frac{\underset{x^{}\left\{x{}_s.Math.R_{}{}_j^{-1}\left(T^{-1}.Math.x\right)=1\right\}}{.Math.}.Math.e^{-.Math.{.Math.y-H_r.Math.x^{}.Math.}^2/2}.Math.\underset{uj}{.Math.}.Math..Math.1-{}_u-{}_u^{-1}\left(T^{-1}.Math.x^{}\right).Math.}{\underset{x^{}\left\{x{}_s.Math.R_{}{}_j^{-1}\left(T^{-1}.Math.x\right)=0\right\}}{.Math.}.Math.e^{-.Math.{.Math.y-H_r.Math.x^{}.Math.}^2/2}.Math.\underset{vj}{.Math.}.Math..Math.1-{}_v-{}_v^{-1}\left(T^{-1}.Math.x^{}\right).Math.}$

which requires the list .sub.s.sub.R.

[0138] In another mode of realization, the processor 200 computes the LLR according to

[00007]$L.Math..Math.L.Math..Math.R_j=\log .Math.\frac{\underset{z^{}\left\{z{}_s^{}.Math.{}_j^{-1}\left(z\right)=1\right\}}{.Math.}.Math.e^{-.Math.{.Math.y-H.Math..Math.z^{}.Math.}^2/2}.Math.\underset{uj}{.Math.}.Math..Math.1-{}_u-{}_u^{-1}\left(z^{}\right).Math.}{\underset{z^{}\left\{z{}_s^{}.Math.{}_j^{-1}\left(z\right)=0\right\}}{.Math.}.Math.e^{-.Math.{.Math.y-H.Math..Math.z^{}.Math.}^2/2}.Math.\underset{vj}{.Math.}.Math..Math.1-{}_v-{}_v^{-1}\left(z^{}\right).Math.}$

which requires the list .sub.s

[0139] In another mode of realization, the processor 200 estimates the LLR according to

[00008]$L.Math..Math.L.Math..Math.R_j=\log .Math.\frac{\begin{array}{c}\underset{x^{}\left\{x{}_s.Math.R_{}{}_j^{-1}\left(T^{-1}.Math.x\right)=1\right\}}{.Math.}.Math.e^{-{}^{}.Math.{.Math.H_r^{-1}.Math.y-x^{}.Math.}^2/2}\\ \underset{uj}{.Math.}.Math..Math.1-{}_u-{}_u^{-1}\left(T^{-1}.Math.x^{}\right).Math.\end{array}}{\begin{array}{c}\underset{x^{}\left\{x{}_s.Math.R_{}{}_j^{-1}\left(T^{-1}.Math.x\right)=0\right\}}{.Math.}.Math.e^{-{}^{}.Math.{.Math.H_r^{-1}.Math.y-x^{}.Math.}^2/2}\\ \underset{vj}{.Math.}.Math..Math.1-{}_v-{}_v^{-1}\left(T^{-1}.Math.x^{}\right).Math.\end{array}}$

which requires the list .sub.s.sub.R, and where some complexity is saved by computing only once the matrix-vector multiplication H.sub.r.sup.1y instead of computing as many matrix-vector multiplications H.sub.rx as needed.

[0140] FIG. 4 represent a geometrical explanation of the constellation transformations by the channel and a lattice reduction.

[0141] The FIG. 4a discloses the real parts of a multi-dimensional constellation as a constellation of .sup.2 wherein N=2 for the sake of illustration. The vectors z are illustrated as the black dots while the white dots are other vectors of .sup.2.

[0142] After a MIMO channel transformation, the rectangular constellation containing vectors z is skewed into a parallelotopic constellation .sub.O containing vectors Hz.sub.O observed on FIG. 4c as black dots. The observed lattice marked as white dots are other vectors of the lattice defined by the channel matrix H. This corresponds to the OCM.

[0143] After the channel reduction, the closest representation of the observed lattice with a constellation in .sup.2 containing vectors Tz.sub.R is shown in FIG. 4b. There is a basis change between FIGS. 4a and 4c and the transformed multi-dimentional constellation .sub.R is parallelotopic in .sup.2. This corresponds to the RCM.

[0144] We observe that, whatever the channel H, the transformation H.sub.r from FIG. 4b to FIG. 4c is almost orthogonal thanks to the reduced channel property, which involves that a sphere drawn in FIG. 4b, is almost spherical in FIG. 4c after transformation by H.sub.r.

[0145] Thus, the present invention aims at drawing a spherical list of vectors in the RCM instead of OCM.

[0146] The transformed multi-dimentional constellation .sub.R always lies in [{square root over (1)}].sup.N, which means that a spherical list of the closest vector to the origin of the lattice may be, according to the present invention, computed once and for all and shifted to a hard estimation of Tz.

[0147] As the construction of the list of vectors can be done offline, the present invention saves a lot of complexity.

[0148] We can observe that the sphere considered in FIG. 4b is skewed into an ellipsoid in FIG. 4a, by the effect of T.sup.1.

[0149] Also, the transformed multi-dimentional constellation .sub.R={Tz} in FIG. 4b is a skewed version of the rectangular multi-dimentional constellation of the QAM vectors ={z} in FIG. 4a, by the effect of T.

[0150] Thus, T plays now the role of an equivalent channel, but has a property of having integer entries and belongs with a high probability to a finite alphabet. The present invention uses this property to further save complexity.

[0151] Finally, for computing the soft output detection, only the vectors belonging to the constellation are taken into account requiring then an operation of selection to reject vectors outside the constellation.

[0152] Naturally, many modifications can be made to the embodiments of the invention described above without departing from the scope of the present invention.