DEVICE COMPRISING A DECODER OF A RECEIVED MULTIDIMENSIONALSIGNAL AND CORRESPONDING SYSTEM

1. Field of the invention.

The present invention relates to the field of digital communication. More specifically, it deals with an efficient way to implement a receiver of a digital signal transmitted through a MIMO (Multiple In Multiple Out) system (i.e. that uses several antennas for transmission and for reception).

2. Technological background.

Optimal decoding of digital signals that have been distorted by linear filtering (e.g. a wireless channel) and corrupted by noise is a key and recurrent issue in digital communications. An optimal decoder is the one that finds the candidate digital signal that is the most likely, given the received observed signal. Such optimal decoder is said to be optimal in the sense of Maximum Likelihood (or ML).

A basic approach to perform ML decoding consists in exhaustively enumerating all possible transmitted digital signals and selecting the most likely candidate. The selection criterion often consists in computing a Euclidean distance between the filtered candidate and the received observation. However, such exhaustive enumeration is very time consuming and most of the time impractical for real time applications. Indeed the number of candidates, and hence the decoder complexity, is exponential with respect to the length of the digital signal. For instance a signal carrying 10 bits may take 1024 (or 2 ¹⁰ ) different values and all these values need being enumerated in basic ML decoding.

More appropriate ML decoding algorithms have emerged based on a multidimensional lattice description of the problem, which will be referred to as lattice decoders in the sequel. For instance a signal made of 8 consecutive 16QAM symbols can be described by a 8 dimension lattice with 16 discrete possible values per dimension. After linear filtering, the lattice will remain a lattice but it will be distorted. Instead of enumerating all possible lattice points (16 ⁸ in the present case), lattice decoders will restrict to evaluating lattice points that are in the vicinity of the received signal.

The main drawback of the state of the art is that lattice decoders are still complex (especially for real time applications) even if they have polynomial decoding complexity (instead of exponential for basic ML).

Simplifications of lattice decoders for applications of MIMO (or Multiple Input Multiple Output) transmissions, have been suggested in the following documents:

- "VLSI implementation of MIMO detection using the sphere decoding algorithm" written by Burg & Al (and published in Solid-State Circuits, IEEE Journal of Volume 40, Issue 7, July 2005 Pages 1566-1577); and

- "On maximum-likelihood detection and the search for the closest lattice point" written by Damen & Al (and published in Information Theory, IEEE Transactions on Volume 49, Issue 10, Oct. 2003 Pages:238 -2402). MIMO related techniques enable to significantly increase the throughput and/or reliability of wireless transmissions while keeping constant the transmitted power and used spectrum bandwidth. This feature makes these techniques particularly attractive for future broadcasting systems, and more particularly future DVBT standard (denoted DVBT-2) as they enable broadcasting more programs without increasing the system allocated spectrum.

However, existing MIMO techniques remains complex and costly.

3. Invention summary. The invention is aimed at alleviating these drawbacks of the prior art.

More particularly, the objective of the invention is to simplify the implementation of a decoding method based on a lattice, while keeping good performances. For this purpose, the invention proposes a device comprising a decoder of a multidimensional received signal transmitted through a channel, so-called transmitted signal, and at least a local antenna, the transmitted signal being transmitted by a plurality of transmitting antennas after coding by a space/time or space/frequency code with a rate larger than 1 . For complexity reduction the decoder comprises:

- means of reception of a first signal received by the at least a local antenna and means of reception of a second signal received by at least a distant antenna;

- means of decoding taking into account the first signal and the second signal to provide a decoded signal.

According to a specific feature, the space/time or space/frequency code rate is strictly larger than 1 .

According to a specific feature, the space/time or space/frequency code rate has a full rate. In a full rate code, the number of symbols transmitted at each time is equal to the number of antennas.

According to a specific feature, the space/time or space/frequency code is a perfect code.

This enables to better managing the conditioning of matrices used for decoding.

According to a specific feature, means of reception of a second signal receive a signal provided by a single distant antenna.

According to a specific feature, the decoder comprises a plurality of demodulators of multi-carrier modulated signal, each antenna being associated to a demodulator.

According to a specific feature, means of decoding comprise:

- means of computation of a first matrix with respect to an estimation of the channel and a code associated to the transmitted signal; - means of sorting of vectors of the first matrix according to a decreasing colinearity criterion, a permutation being applied to vectors of the first matrix to obtain a reordered matrix;

- means of decoding of an observation with a lattice decoding by using matrix derived from the reordered matrix to get estimation of a permutated transmitted signal; and

- means of inverse permutation of the estimation of the permutated transmitted signal to get an estimation of the transmitted signal.

According to a specific feature, means of decoding comprise: - means of preprocessing applied to a subset of bins within a set of time/frequency bins to build channel equivalent matrices restricted to the subset;

- means of interpolation for remaining time/frequency bins with respect to the channel equivalent matrices restricted to the subset to build channel equivalent matrices associated with the remaining time/frequency bins ; and - means of decoding of an observation with a lattice decoding by using the channel equivalent matrices associated to the set of time/frequency bins, that comprise channel equivalent matrices restricted to the subset and channel equivalent matrices associated with the remaining time/frequency bins. According to a specific feature, means of decoding comprise:

- determination of a minimum distance according to a noise level associated to the multidimensional received signal;

- for at least a part of candidate discrete multidimensional signals, selection of a subset according to the minimum distance with respect to the received multidimensional received signal ; and

- determination of a decoded point in the subset. Advantageously, the device comprises the local antenna(s), the local antenna(s) being inside the device itself or connected directly to the device through a connector or a short cable). According to an advantageous feature, the device does not comprise a distant antenna, the distant antenna(s) being outside the device and not directly attached to the device

(through a connector for example).

The invention concerns also a system comprising a device and at least a distant antenna connected to the device.

4. Brief description of the drawings.

The invention will be better understood, and other features and advantages will become apparent from reading the description that follows, the description referring to the appended drawings in which: Figure 1 represents a wireless network;

Figure 2 represents an exemplary architecture of a data transmitter capable of sending data in a way compliant with the invention; - Figure 3 represents an exemplary architecture of a data receiver according to a specific embodiment of the invention;

Figure 4 represents an exemplary architecture of a decoder inside the receiver of figure 3;

Figures 5 and 14 represent a decoding method implemented in the receiver of figure 3 according to the invention; - Figure 7 is a schematic view in a case the dimension of the decoding method of Figure 5 is two;

Figure 8 represents the distribution of the norm of the noise vector affecting the signal received by the receiver of figure 3;

Figures 6; 9 and 10 represent detailed step of the decoding method of Figure 5;

Figure 1 1 represents a multi-user detection according to a specific embodiment of the invention;

Figures 12 and 13 present matrix reordering step in the decoding method of figure 5; and - Figure 15 represent a constellation mapping used in the signal transmitted by the transmitter of figure 2 and received by the receiver of figure 3

5. Detailed description of the invention. According to the invention, a decoder receives a signal transmitted in a MIMO (Multiple In Multiple Out) channel. It decodes signals provided by at least a local antenna and at least a distant antenna. This enables to take advantage of the signal that is transmitted with a space/time coding rate at least larger than 1 (and advantageously strictly larger than 1 ). The use of local and distant antennas enables to improve the decoding quality while keeping a limited number of distant antennas (advantageously the number of distant antenna is equal to one). The present invention proposes a receiver architecture that would not require installing more roof top antennas at the user place while despite exploiting MIMO capability. For an application such as DVB (Digital Video Broadcast) reception, it may be a cheap solution as a user may already have a distant antenna (e.g. on a roof). Then, the invention enables to get more energy (corresponding to the transmitted signal) and to improve the conditioning of matrices used for decoding. The conditioning is linked to the determinant of the considered matrices ; it corresponds to an invertible matrix that is not too sensitive to the reception or computation noise affecting the received signal.

The complexity of the decoding is linked to the space/time code dimension, i.e. the number of symbol per space/time code. The resulting complexity, then, does not depend (or its very dependency is very limited) on the number of antennas (local antenna are very cheap). Especially, the costly steps of decoding may comprise lattice decoding (lattice decoding corresponds to a decoding of a distorted discrete multidimensional signal) and Cholesky or QR decomposition (as mentioned in the following disclosed embodiments of decoder); these steps do not depend on the number of antennas. In the disclosed embodiments of decoder, only a preprocessing step is working on matrix, the size of which depends on the number of antennas. Indeed, this step is not as complex as the lattice decoding itself (multiplication by G' ¹ in step 540 and step 542 in embodiment that will be detailed in the specification).

In addition, some variants of the invention disclosed hereafter enables to improve further the performances (and sometimes to render its implementation possible) although the MIMO channel matrices may be ill conditioned.

According to a variant of the invention, lattice decoders comprise generally two main phases: a preprocessing phase and a search phase. According to state of the art, the preprocessing phase is performed each time the lattice basis changes (this basis is, for example, related to the wireless channel realization). However thanks to the time and/or frequency coherence of the channel, the lattices corresponding to adjacent time and/or frequency bins are very similar. According to the an advantageous variant of the invention, the preprocessing phase is performed on a subset of time and/or frequency bins and the results of the preprocessing for the remaining bins are interpolated. Although the preprocessing operations are non linear, they can indeed be approximated as locally linear with no or very little impact on the performance. This property is exploited by the variant of invention. Interpolating instead of explicit preprocessing brings a significant complexity reduction in practical cases, which is important to implement high throughput schemes.

The invention is applicable to any lattice decoding algorithm and provides good results when lattice bases are sufficiently similar so that the interpolation can be used. It is applicable to any lattice decoding problem (e.g. decoding of Space-Time Block encoded signals and/or multi-user detection). The invention can be applied to all systems that are based on

lattice decoding, especially to decoding of Space-Time Block encoded signals, to decoding of data transmitted through a MIMO channel or to multiuser detection.

When applied to ML decoding of STBC encoded MIMO transmissions, this allows reducing the lattice decoding complexity. As a consequence, this enables implementing high throughput high reliability wireless MIMO transmissions with reasonable receiver complexity.

The interpolation is advantageously associated with other features. According to a first variant, vectors of a matrix (equivalent channel matrix or Gram matrix) are sorted according to a decreasing colinearity criterion, a permutation being applied to vectors of this matrix to obtain a reordered matrix. Then, the decoding of an observation with a lattice decoding is using matrix derived from the reordered matrix to get estimation of a permutated transmitted signal or the reordered matrix itself and inverse permutation is applied to the estimation of the permutated transmitted signal to get an estimation of the transmitted signal. This feature enable to reduce the complexity of lattice based decoders. In particular, it has been observed through simulations that some types of wireless channels strongly distort the lattice representing the transmitted signal, which induces a larger decoding complexity of lattice decoders (e.g. when the lattice basis is ill conditioned). This is the case for strongly spatially correlated channels and/or channels presenting a strong LOS (Line Of Sight) component. The invention brings a significant complexity reduction for this type of wireless channels, which has been observed as being a critical channel type that conditions the lattice decoder complexity and dimension the receiver design.

According to a second variant that can be combined with the first variant and that furthermore reduce the complexity of the receiver, the decoding of a multidimensional received signal comprises:

- determination of a minimum distance according to a noise level associated to the multidimensional received signal;

- for at least a part of candidate discrete multidimensional signals, selection of a subset according to the minimum distance with respect to the received multidimensional received signal; and - determination of a decoded point in the subset.

Figure 1 represents a wireless network 1 comprising several stations 10 to 12. Each station 10 to 12 comprises a transmitter and a

receiver using a MIMO (or Multiple Input Multiple Output) antenna system. Station 10 communicates with stations 1 1 and 12 through a wireless link. According to the invention, the stations 1 1 and 12 corresponding to indoor stations are using at least a local antenna and are also connected to at least a distant antenna (for instance outside antenna located on the roof of a building).

Figure 2 represents an exemplary architecture of a data transmitter 2 capable of sending data in a way compliant with the invention applied to decoding of a signal transmitted through a MIMO noisy channel. The data transmitter 2 can be implemented in stations 10 to 12. The transmitter 2 comprises: a Reed-Solomon encoder 19; an interleaver 210; a modulator 21 ; - an encoder 23; a time/frequency mapper 25;

Mx OFDM modulators 271 to 27/Wx each modulating with an OFDM modulator an input signal 261 to 26Mx; and Mx antennas 281 to 28Mx, each being associated to an OFDM modulator respectively 271 to 27Mx.

The transmitter 2 receives a binary signal 22 which is digitally encoded with a Reed-Solomon encoder, then interleaved with the interleaver 210, then modulated by the modulator 21 with a first modulation which is, for instance a QAM modulation (or "Quadrature Amplitude Modulation") (e.g. 16 QAM or 64QAM, or 32QAM as detailed hereafter). The modulator 21 generates groups of Q complex QAM symbols S1 to SQ. Q is for example equal to 8.

In a specific embodiment, the data bits are first encoded using a

Reed Solomon encoder 29 as non binary code encoder. The encoder uses an alphabet of symbols made of k bits in which the symbol size k divides the number of bits per space-time code words used in the multi carrier modulation as explained here after. The non binary encoder produces from sequences of symbols, code words on the same k bits symbols alphabet.

These symbols are then interleaved by a k bits symbols interleaving circuit 210. More specifically, the interleaving circuit is a row column interleaving circuit. The binary stream of interleaved symbols is split into groups of log ₂ (M) bits to be modulated by a QAM modulation. In this embodiment, the

modulation is a 32 QAM modulation. Thus each group of log ₂ (M) comprises 5 bits. Each group of 5 consecutive bits is then mapped and modulated according to a 32 QAM modulation in the modulator 21 . This type of modulation will be explained later on with reference to figure 15. The resulting complex symbols are then grouped by four and encoded in the encoder 23 with a space-time code, more particularly a perfect code such as the Golden code. The resulting output four complex symbols are then transmitted over two well separated frequency bins of a same OFDM symbol. The space-time code at the output of the Golden code encoder is turned into a space-frequency code using a time-frequency interleaving circuit 25. The two symbols streams resulting from the time-frequency interleaving circuit are sent to Ntx OFDM modulators 271 to 27Ntx associated with each transmitting antenna 281 to 28Ntx. The resulting base band signals on the two paths are transposed to RF signals and sent to the antennas. Each group of Q symbols 22 is encoded with the encoder 23 to form a STBC (or Space Time Block Code) codeword 24. The STBC is, for instance, a Golden code such as disclosed in document "The Golden Code: A 2 x 2 Full-Rate Space-Time Code with Non-Vanishing Determinants," which has been written by J. -C. Belfiore, G. Rekaya, E. Viterbo (and published in IEEE Transactions on Information Theory, vol. 51 , n. 4, pp. 1432-1436, Apr. 2005.). According to a variant, the STBC is as disclosed in "Space-Time block codes from orthogonal designs" document written by V.Tarokh, H. Jafarkhani, and R. A. Calderbank (and published in IEEE Transactions on Information Theory, vol. 45, pp. 1456-1467, July 1999). The STBC is based on a complex matrix of dimension N _tx ^* N where N is the time dimension of the STBC.

The generated STBC 24 is mapped in the time/frequency mapper that transmits a dedicated signal 261 to 26Ntx to each of OFDM modulator 271 to 27Ntx. Then, each modulator 271 to 27Ntx modulates its input signal into an OFDM modulated signal that is sent on an antenna respectively 281 to 28Ntx (after possibly filtering, frequency transposition and amplification as usually done in a radio transmitted signal). As summary, the STBC codeword 24 is then sent on a MIMO channel.

Such a transmitter system is disclosed in "Space-frequency coded broadband OFDM systems", written by H. Bδlcskei and A. J. Paulraj (and published in Proc. Wireless Commun. Networking Conf., Chicago, IL, Sept. 23-28, 2000, pp. 1 -6).

There are many possible variants of the transmitter that are compliant with the invention. Among them, a single carrier modulation can replace the OFDM modulation (or any multi carrier modulation such IOTA (for "Isotropic Orthogonal Transform Algorithm")). Then, a time/frequency mapper 25 and the OFDM modulators 271 to 27Ntx are replaced by at least two single carrier modulators associated each with a antenna. Such a transmitter system is disclosed in "Space-Time block coding: A simple transmitter diversity technique for wireless communications" written by S. Alamouti (and published in IEEE Journal On Select Areas In Communications, vol. 16, pp. 1451-1458, October 1998).

According to other variants (that are compliant with previous ones), the first modulation can be of any digital modulation, e.g. nPSK (for "Phase Shift Keying with n phase values) or nQAM (eg with n equals to 16, 32, 64, 256...). In the specific embodiment of transmitter that uses 32 QAM modulation, as a codeword of the Golden code encodes 20 bits in the case of a 32 QAM modulation having symbols of 5 bits (four 32QAM symbols) and codeword errors therefore span 20 bits, k is advantageously taken as dividing 20. Practical values for k are thus typically 5 and 10 here. Higher values of k induce a too high RS decoder complexity. In the case of 16QAM mapping, the Golden codewords would have spanned 16 bits and therefore an appropriate value for k would have been 8. As shown on figure 15, groups of 5 bits are mapped onto complex symbols of a constellation wherein the constellation is a cross 32 QAM constellation and the label of two adjacent points are modified on a minimum number of one bit except for one set of two adjacent points (10010,001 1 1 ; 10000,00101 ; 1 1000,01 101 ; 1 1010,01 1 1 1 ) in each quadrant. In the constellation 1/ V20 is a normalization factor that guarantees that the average symbol energy is 1 . The resulting complex symbols are grouped by 4 and encoded with a Golden code. The Golden code is a particular type of space-time code that provides full transmit diversity while simultaneously allowing to obtain the same code rate as for spatial multiplexing. Indeed, a codeword of the Golden code carries 4 modulated symbols, it is transmitted over 2 antennas and spans 2 symbol durations. Combined with 32QAM, the overall spectral efficiency is then 10 bits/s/Hz or slightly less if we account for the RS code rate, which is usually close to 1 .

The Golden code is defined by a complex 4x4 matrix and the encoding process by the multiplication of the input complex 4x1 symbol vector with the Golden code matrix.

More precisely, the encoding process consists in a multiplication of the complex input vector of Nsymb_per_STC (=4 here) symbols with the following complex matrix C that is isomorphic to a Golden code and presents the advantage of having many 1 s and Os :

r is the opposite of the conjugate of the Golden number. α=0.8507 is a normalization factor that guarantees that the energy is kept constant through the encoding process.

Figure 3 represents an exemplary architecture of a data receiving system 30 comprising a receiver 3 according to a specific embodiment of the invention. The receiver 3 receives a signal send by the transmitter 2 through a wireless channel. This channel is noisy and comprise Additive White

Gaussian Noise (or AWGN) and possibly other noise such as interferences.

The sent signal can also be affected by multipath echos and/or Doppler effect. The data receiver 3 can be implemented in stations 10 to 12.

The receiving system 30 comprises a distant antenna 37 connected to the receiver 3 through a cable 38. The distant antenna 37 is for example an antenna positioned on the roof of a building and adapted to receive a TV signal (e.g. DVB signal). The receiver 3 comprises:

Nrx local antennas 301 to 30Nrx (Nrx is for example equal to 1 , 2, 3, 4...);

Nrx+1 OFDM demodulators 31 1 to 31 λ/rx each demodulating a noisy OFDM modulated signal transmitted by an antenna respectively 301 to 30λ/rx; an OFDM demodulators 31 λ/rx+7 similar to OFDM demodulators 31 1 to 31 λ/rx demodulating a noisy OFDM modulated signal transmitted by the distant antenna 37; a time/frequency demapper 33; and

a decoder 35.

According to a variant, the receiving system 30 comprises several distant antennas, each being connected to an OFDM demodulator in the receiver 3 (one demodulator for one antenna). The receiver 3 matches the transmitter 2 (especially for modulation and code used by the transmitter). Then, according to variants using single carrier modulation inside the transmitter, the OFDM demodulators are replaced by the corresponding single carrier demodulators. The receiver 3 comprises Nrx receive antennas 301 to 30λ/rx so that the received signal 301 to 30Nrx can be represented by a Nrx ^* N matrix, or equivalently a (Nrx ^* N) ^* 1 vector R. N is, for instance, equal to 2 and represents the time and/or frequency range occupied by the STBC.

The transmission between the encoder 23 and decoder 35 can be modeled by the following equation:

R v = GS + v (relation 1 )

Where the different parameters are as follows:

- R is the complex (Nrx ^* N) ^* ^ received vector; - H ₁ is the complex Nrx ^* Ntx channel matrix at time/frequency interval / (frequency corresponds to a carrier of the multicarrier modulation; according to a variant using a single carrier modulation the interval / corresponds to a time interval);

- H=diag(H ₁ ,..., H _w ) is the complex block diagonal (N ^* Nrx) ^* (N ^* Ntx) channel matrix at time/frequency intervals 1 to N;

- C is the complex (Ntx ^* N) ^* Q STBC coding matrix, where Q is the number of input complex symbols per STBC codeword;

- S is the complex Q ^* 1 input vector of discrete modulated symbols;

- v is the complex (N ^* Nrx) ^*y \ Additive White Gaussian Noise (or AWGN) vector with autocorrelation matrix R _v =σ ² \NNrx, where \NNrx is the identity matrix of size (N ^* Nrx) ^* (N ^* Nrx) and σ ² represents the variance of the AWGN.

According to a variant, the space/time coding process takes place with real inputs (instead of complex inputs). Then, the C matrix is a real matrix with a dimension (2Ntx ^* N) ^* (2Q).

When the additive noise and interferences corrupting the received signal is not white, a whitening filter is advantageously implemented before the decoder 35. σ ² represents the variance of the resulting whitened noise.

The time/frequency demapper 33 received demodulated signal from OFDM demodulators 31 1 to 31 λ/rx and is doing the reverse mapping (corresponding to dual operation of mapper 25). It provides a demapped signal to decoder 35.

The decoder 35 is a lattice decoder and is particularly well suited to perform ML decoding of the Space-Time Block encoded signal.

According to a variant of the invention, the decoder 35 is exploiting the properties of the noise distribution by selecting points in a lattice that are between two spheres around a received point, the decoded point being chosen among selected points. This enables a reduction of the decoder complexity as the number of selected points can be lowered in comparison with a state of art decoder where the selected points are within one sphere around the received point. Actually, it is unlikely that ML decoding would choose points of the lattice that are too close to the received point as decoded points. Then, the decoder does not select these points as potential candidates for decoded points. Reduction of number of selected points enables a dramatic reduction of decoding complexity (the decoding complexity depend of the level of noise and is increasing with the number of selected points).

This aspect is illustrated on figure 7, which represents the distribution of received data received by the receiver 3. Figure 7 gives a simplified lattice representation 7 of the decoding problem. The problem is illustrated in the case where the dimension K is 2 (Q equals 1 ) for the sake of illustration clarity. Those two dimensions are represented respectively by lines 77 and lines 78. Intersections of lines 77 and 78 corresponds to points of the lattice 7.

The transmitted signal (which is the ML point here), is a lattice point 750 represented by USV The received signal 70 is represented by R _p =US'o+η (η being the noise vector) and is not a lattice point. The lattice points that can be considered as candidates for ML decoding are, according

to a variant of the invention, in a search space between two spheres 71 and 72:

- the sphere 71 S(R _p ,dmin) of radius dmin (which has a non null value) and centered on R _p ; - the sphere 72 S(R _p ,c//r?ax) of radius dmax (which is greater than dmin) and centered on R _p .

Then, as illustrative example, a lattice point 74 is within the sphere 71 and is not among candidate points for the ML decoding according to a variant of the invention (whereas according to other variants, this point would have been selected by decoding method). Lattice points 760 to 764 are outside the sphere 72 and are not among candidate points for the ML decoding. Lattice points 750 to 754 are in sphere 72 and outside sphere 71 ; then, these points are considered as candidates by the decoder.

Figure 8 illustrates a distribution 80 of the norm of the noise vector η for σ ² equal to 0.01 (2OdB SNR) and K (or 2Q) equal to 16. This is a chi square distribution with K=16 degrees of freedom denoted χ _κ ² . The horizontal axis 83 represents the normalized distance to the received point. The vertical axis 82 corresponds to the distribution of samples for a given normalized distance. The distances dmin and dmax are defined such that

Pr(||η||>c/max) equals 10 ^"2 and Pr(||η|| < dmin) equals 10 ^"2 . These probabilities are example values. It can be noted that area 801 corresponding to normalized distance lower than dmin and area 802 corresponding to normalized distance higher than dmax are very small (each having a normalized surface of 10 ^"2 ) compared to the middle area 800, where the normalized distance is greater than dmin and lower than dmax. On the given example, dmin is around 0.025 that is significant. Then, it shows that it is very unlikely that the distance between a point corresponding to the coded point (without noise) and the actual received point is below dmin.

In the decoding process, dmax gives an initial value for the radius of the sphere S(R _p ,r) within which the search will take place. By definition of dmax, the probability that the transmitted signal is outside this sphere is 10 ^"2 . Setting the initial radius to dmax therefore allows reducing the initial search space, and hence the decoding complexity, for a given level of performance.

According to a variant of the invention, dmin is introduced and can advantageously be used in the decoding process according to two ways, as follows:

- A way to use it is to interrupt the decoding as soon as a lattice point is found within dmin from the received signal. It is then very likely that this point is the transmitted point (with a probability of 99%);

- Another way to use it is to define a second sphere S(R _p ,dmin) inside S(Rp, dmax), inside which it is useless searching for lattice points.

Any of these utilizations (or a combination of both) will reduce the decoding complexity while knowing the impact on the performance.

More generally, dmin is advantageously defined by the following equation

where the integrated function is the probability density function (or pdf) of ||η|| ² and p ₀ is the desired probability threshold of the event (i.e. the transmitted signal is in S(R _p ,c//77/n)). Then, dminlσ can be determined according to a predefined value of po. It can be computed on the fly (dmin = σ.f(po) where f(po) is fixed if po is predefined and can be computed off line during the design phase of the decoder) or determined according to a look- up table defining dmin according to σ. Advantageously, a single value of po is used. According to variants, several values of po are used in the decoder.

Then, several values of f(po) are defined accordingly.

As variant, if a large number of po value are required for the decoding, dmin can be determined by using approximations of above equation (e.g. by using a first or second orders of a Taylor series).

Figure 4 represents an exemplary architecture of the decoder 35 of the receiver 3.

Decoder 35 comprises following elements that are linked together by a data and address bus 44: - a microprocessor 41 (or CPU), which is, for example, a DSP (or Digital Signal Processor);

- a ROM (or Read Only Memory) 42;

- a RAM (or Random Access Memory) 43;

- an interface 45 for reception of input signal coming from the demapper 33;

- an interface 46 for transmission of decoded data to an application.

Each of these elements of figure 2 are well known by those skilled in the art and won't be disclosed further.

In each of mentioned memory, the word « register » used in the specification can correspond to area of small capacity (some bits) or to very large area (e.g. a whole program or large amount of received or decoded data).

ROM 42 comprises a program 420.

Algorithm of the method according to the invention are stored in the ROM 42. When switched on, the CPU 41 uploads the program 420 in the RAM and executes the corresponding instructions.

RAM 43 comprises:

- in a register 430, the program executed by the CPU 41 and uploaded after switch on of the decoder 35; - input data in a register 431 ;

- decoded data in a register 432;

- a value of σ (standard deviation of noise) in a register 433;

- values of dmin and dmax in registers respectively 434 and 435;

- parameter D in a register 436; - parameter DMAX in a register 437;

- parameter K in a register 438;

- f(po) enabling the computation of dmin according to σ in a register 439;

- matrices G' (equivalent channel matrix), H (channel matrix), C (code matrix) in a register 4310; - Gram matrix M and small value matrix ε in a register 431 1 ;

- variables / and k in a register 4312;

- i_in and i_out indices in a register 4313;

- new equivalent channel matrix new_G' in a register 4314;

- new Gram matrix new_Gram in a register 4315; - a subset of time intervals and/or subcarriers in a register 4316; and

- matrices U, U ^"1 that correspond to the results of preprocessing applied to the subset in a register 4317.

According to a variant of the invention, the decoder 35 is implemented in pure hardware configuration (e.g. in one or several FPGA, ASIC or VLSI with corresponding memory) or in a configuration using both VLSI and DSP.

Figure 5 represents a decoding method implemented in the decoder 35.

The decoding begins with a initialization step 50, wherein different parameters of the method are set to their initial value(s). Then, during a step 51 , the decoder 35 waits for and receives a signal from demapper 33.

Then, the CPU 41 makes a channel estimation 52 based upon the received signal (associated to one transmitted block) or part of it. According to a variant of the invention, the estimation 52 is based upon several received signals (or part of them), each being associated to a transmitted block. According to another variant of the invention, the estimation 52 is not done at each reception of signal corresponding to one transmitted block; in this case, it may be done when necessary according to the channel changes (e.g. every 1 ms). Then, in a step 53, CPU 41 computes σ using, for example, a pilot sequence and determines dmin as explained above and possibly dmax in a similar way. Advantageously, step 53 is executed after each channel estimation 52. According to a variant of the invention, step 53 is not done at each reception of signal corresponding to one transmitted block. During a step 57, a subset of time/frequency bins is determined.

The subset comprises bins that correspond to one out of two time dimensions and one out of two frequency dimension.

According to a variant, the subset comprises bins that correspond to one out of two time dimensions and to all frequency dimensions (as the transmission channel in varying less in time dimensions than in frequency dimensions).

Indeed, any other subset of points comprising 1 out of p (p being equal, for example, to 2, 3, 4... 10, 1 1 , ..or any rational value (e.g. 2.5, 3/4, 2/3,...)) in time dimensions and/or in frequency dimensions can be chosen according to the invention. The points of subset are advantageously regularly located in time dimensions and/or frequency dimensions. Indeed, according to variants, the points of the subset may be more numerous in some time and/or frequency intervals (for example, if the transmission channel varies more in the corresponding intervals). Then, CPU 41 is executing a preprocessing step 54 on subset of time/frequency bins determined in step 57.

Then, during step 58, for each bin that does not belong to the subset, an interpolation is performed using the result step 54 for bins of subset, surrounding the considered bins. For example, if the subset comprises bins that correspond to one out of two time dimensions (eg. tθ, t2, t4,.... tu) and one out of two frequency dimensions (eg. /D, /2, f4,.... fv), these bins on which preprocessing 54 has been performed, are regularly located. Any other bin on which interpolation is performed, corresponds to intermediate time or frequency (typically t ^' \ between fi-1 and fi+1 and /j between /j-1 and /j). Then, a new lattice basis U and associated matrices U ¹ G'' used in the lattice decoding 55 for bin (that is detailed hereafter) are obtained by the following interpolation:

Ufi,/j = %(Ufi-1 ,/j-1 + Ufi-1 ,/j+1 + Ufi+1 ,/j-1 + Ufi+1 ,/j+1 ).

U ^" 'G''fi,/j = V ₄ (U- ¹ G ¹ Vi-I ₁ Zj-I + U ^" 'G'Vi-1 ,/j+1 + U ^" 'G'Vi+1 ,fj-1 + UWi+1 ,/j+1 ). According to a variant using QR decomposition instead of

Cholesky, the preprocessing produces matrices U and Q. So that the interpolation is performed to obtain such matrices, and Q can be expressed as:

Qfi./j = Vi(QfM ,/j-1 + Qfi-1 ,/j+1 + Qfi+1 ,/j-1 + Qfi+1 ,/j+1 ). In the following description, only detailed formula on U are given for ease of reading. Of course, similar formulas are determined for U ^" 'G'' (or Q for the variant).

According to another example, if the subset comprises points that correspond to one out of two time dimensions (eg. to, tl, M,.... tu) and all frequency dimensions (eg. /0, / ⁷ I , /2, .... fv), these points being regularly located in time dimension, any point corresponding to intermediate time (typically f\ between fi-1 and t\+^ ). Then, the new lattice basis U (that is detailed hereafter) can be expressed as:

Ufi,/j = 1 /2( Ufi-1 ,/j + Ufi+1 ,/j). As a variant any linear interpolation can be used to determine a new lattice basis U for bin f\f\. Advantageously, a higher weight is applied to bins close to the considered bin. Advantageously, the interpolation is based only on adjacent bins.

As exemplary variant, if the subset comprises bins that correspond to one out of 10 time dimensions (eg. tθ, M O, t20,.... HOu) and all frequency dimensions (eg. /0, f\ , fZ,.... fv), these bins on which preprocessing 54 has been performed, are regularly located. Any other bin

on which interpolation is performed, corresponds to intermediate time (typically t10\+k between t10\ and t10(\+λ ) for any subcarriery). Then, a new lattice basis U for bin t10\+kf\ is obtained by the following interpolation:

Ut10\+k,f\ = 1/1O((1 O-k)UtfOi,/j + kUf?0(ϊ+1 ),/j). Then, CPU 41 is enumerating lattice points and selects decoded point in a step 55.

Then, during a step 56, the components of the decoded point are inversely permutated according to the permutation produced by step 540. After step 56, step 51 is reiterated. According to a variant of the invention, step 540 does not comprise any permutation. Then, step 51 is reiterated after step 55.

In a variant using DSP and VLSI, advantageously, step 54 is performed by the DSP and step 55 by a VLSI (e.g. ASIC or FPGA).

The preprocessing step 54 changes the observation R' so that the lattice basis of the system can be expressed with a triangular matrix. In equation (2), the lattice basis is G': when S is modulated using e.g. a QAM modulation, each of the components of S are PAM modulated, i.e. they take bounded discrete values. Therefore G' is in this case a basis of the K=2Q dimensions lattice representing the problem.

To transform the basis matrix into a triangular matrix, we apply Lγ'G'' to the received signal R' yielding a new observation R _p , where U is an upper triangular KxK matrix coming from the Cholesky decomposition of G''G' : R _p = ϋ 'G"R'= ϋS'+η

In a variant, to transform the basis matrix into a triangular matrix, we apply Q' to the received signal R' yielding a new observation R _p , where Q is an orthogonal KxK matrix coming from the QR decomposition of G'.

Rp is the new K*λ observation vector and η is the K*1 noise vector with autocorrelation R _η = — l _κ . U is the new lattice basis that is used by lattice decoding algorithms.

To summarize, the preprocessing phase mainly produces the matrices U and U ^" ' from the original matrix G' (or U and Q according to a variant):

Coming back to two STBC codewords transmitted on time- frequency bins (ti.fi) and (t ₂ ,f ₂ ), the preprocessing phase of the decoding of each codeword performs the following operations:

_{G%λ )} preprocessing ^^^^

G'(/ ₂ ,/ ₂ ) ^™∞^ > u(; ₂ ,/ ₂ ),lTG'(; ₂ ,/ ₂ ) Two STBC codewords are affected by different channel realizations. However in practice, when the time-frequency bins defined by the sets {U,f _λ ) and {t _2l f ₂ ) are sufficiently close from each other compared to the channel coherence time and/or bandwidth, the original matrices G'(fi,fi) and G'(t ₂ ,f ₂ ) are quite similar and as well the matrices li(U,f _λ ) and U(t ₂ ,f ₂ ) and the matrices ir'G'tø./i) and ϋ ^'ι G'(t ₂ ,f ₂ ) produced by the preprocessing.

According to the invention, this similarity is used. The matrices LK-n/n) and U ^" 'G'(fn,/n) are used to decode a STBC codeword allocated to intermediate time-frequency bins (t _n ,f _π ) with respect to {U,f _λ ) and {t ₂ ,f ₂ ), instead of explicitly performing the preprocessing for these matrices. Although the preprocessing involves non linear operations, it turns out that the interpolation for small variations of the channel produces sufficiently accurate results while being much less complex that the explicit preprocessing. The interpolation may be linear or more complex interpolation may be performed. A linear interpolation corresponds to the first order of a Taylor series applied to U and U ¹ G'. As variant of the invention, other orders (e.g. 2, 3, ...) of Taylor series applied to U and U ¹ G' can be used for more accurate non linear interpolation.

A variant of the decoding method implemented in the decoder 35 is disclosed in figure 14 wherein a test is performed to check whether interpolation or preprocessing is appropriate.

The interpolation 58 may take place on a systematic basis, e.g. every two OFDM symbols (interpolation in time) and/or every two subcarriers (interpolation in frequency). However, non systematic interpolation may be more accurate, e.g. in the two following contexts: - Depending on the environment, the channel may change very rapidly (high Doppler corresponding to high mobility) and/or be very frequency selective (high delay spread corresponding to large environment). In such case, interpolating on a regular time and/or frequency basis may be inaccurate because the approximation of small variations is no longer

valid and therefore the approximation of local linearity of the operations involved in the preprocessing in also no longer valid.

- On the contrary, the channel may be very static (small Doppler corresponding to low mobility) and/or be flat in frequency (low delay spread corresponding to small environment and/or strong Line Of Sight component). In such case, interpolating on a regular basis, e.g. every two OFDM symbols or every two subcarriers, may be suboptimal as the channel stationnarity may be better exploited leading to better complexity reduction. Therefore, in a particular embodiment of the invention as disclosed in figure 14, the interpolation may be conditioned on a variation criterion based on the similarity between the matrices G(t-ι,fi) and G(t ₂ ,f ₂ ) (or U(ti,fi) and U(t _2l f ₂ ) or U ^" 'G'(ti,fi) and U ¹ G ¹ (t _2l f ₂ ) (or Q(ti,fi) and Q(t _2l f ₂ ) according to a variant based on QR decomposition)) between which the interpolation will take place. More explicitly, this criterion may be based on

with λ _a = G{t _x J _x )-G{t ₂ ,f ₂ ) e _b )-U(r ₂ ,/ ₂ ) e _c = )U*G%f ₁ )) with δ _c = U-'G%f _λ )-U*G'{t ₂ J ₂ ) and the interpolation takes place when one of this value (or a combination of them) is smaller than a predetermined threshold (e.g. normalized error ea, eb and ec below 0.01 ). Otherwise, explicit preprocessing shall be performed. The operator Tr(X) (Trace of X) corresponds to the sum of values of the diagonal elements of X.

According to a variant, the variation criterion is based on other values, e.g. on non normalized errors, on other norms such as the difference between a diagonal element of two explicitly computed matrices (e.g. G(ti,fi) and G(t ₂ ,f ₂ )).

Advantageously, the threshold is fixed. According to a variant, the threshold or the variation criterion can be changed with respect to, for example, the target level of performances or the STBC dimension. Steps 50 to 54 and 57 are similar in figures 5 and 14 and won't be further detailed. According to the variant of figure 14, after step 54, a test 59 is checking if the variation according to the variation criterion is small enough along time dimension, frequency dimension or both according to the subset (if bins do not belong to a subset according to specific dimensions, then the test 59 considers this dimension or these dimensions).

If so, steps 58, 55 and 56 are performed as mentioned in description of figure 5. According to a variant, step 51 is reiterated after step 55.

If no, a preprocessing step 510 (similar to preprocessing 54) applied to remaining bins (bins that do not belong to subset defined in step

57) is performed. As a variant, preprocessing 510 is only applied to a new subset among the remaining bins (this preprocessing then can be iterative).

Then, step 55 is performed.

According to a variant, as the channel may be very static, if it observed that results of preprocessing 54 of neighbor bins of the subset defined in step 57 are similar (i.e. the difference is lower that a given threshold), then next time step 57 is executed, the subset definition is modified to reduce the number of bins to take into account.

Figure 6 details preprocessing step 54. A brief explanation of the decoding method is first disclosed hereafter. As mentioned above, this processing step applies only on bins of subset.

We assume that the decoder 35 perfectly knows the channel matrix diag(Hi,..., H _N ), which is implemented in practice by using appropriate pilot symbols and appropriate tracking. The denomination STBC comes from the fact that each STB codeword is represented by a matrix CS and the encoding process is a simple matrix multiplication.

CS in equation (1 ) denotes the STB (Space Time Block) encoded signal. The encoding process is represented by complex matrix multiplications in the present case but from a more general point of view, it shall be represented by real matrices where the real and imaginary parts of S are encoded separately. Indeed, the STBC scheme disclosed in Alamouti document ("Space-Time block coding: A simple transmitter diversity technique for wireless communications") can only be represented with such real notations. Such more general writing turns (1 ) into:

where C is the STBC encoding matrix in real notations, (.) ^R and (.)' denote respectively the real and imaginary parts of a complex number or matrix.

In real notations, the dimension of the input signal S', which is the problem dimension, is K=2Q. When S is modulated using a QAM

modulation, each of the components of S are PAM modulated, i.e. they take bounded discrete values. Therefore G' is in this case a basis of the K=2Q dimensions lattice representing the problem. However, lattice decoding algorithms more advantageously use a triangular matrix as a lattice basis, so that the starting point of the search algorithm is not (2) but it is given by equation (3):

R _p = U ^" 'G"R'= US' + η

U is a upper triangular KxK matrix. R _p is the new Kx1 observation vector and η is the Kx1 noise vector with auto correlation R _n = — 1^ . U is the new lattice basis that is used by lattice decoding algorithms.

According to a variant, the time/frequency dimension N is replaced by a time dimension if a single carrier modulation is used.

From the new observation R _p and knowledge of the channel, the

STBC decoder finds the best estimate of the transmitted signal S. The lattice decoders use a lattice representation of the problem, where each lattice point is a potential transmitted signal. From this lattice representation, they enumerate a reduced number of candidate signals with respect to what would do a basic ML decoder. For instance, with Q equals to 8 and using

16QAM constellation, a basic ML decoder will enumerate 16 ⁸ candidates to decode a STBC codeword and the lattice decoders will only enumerate very few of them. According to ML decoding, The ML signal (or SML) corresponds to the minimum metric on all possible signals, i.e.

S _m = argmin (|R -GS| ² ) all possible S

As all possible signals are too many, the search space is reduced to the space between two spheres 71 and 72 of radius dmin and dmax.

For any type of lattice decoder, the decoding algorithm can be split into two main phases:

- the preprocessing phase 54 that enables the determination of a base of point lattice on a subset of time intervals and/or subcarriers

(frequencies).

- the search phase corresponding to step 55.

The preprocessing phase 54 begins with a computation 540 of Gram Matrix. Gram matrix corresponds to a multiplication of an equivalent channel matrix new_G' by its transpose new_G''.

Then, during a step 541 , the CPU 41 executes a triangular decomposition. A Cholesky decomposition of the associated Gram matrix is done by the CPU 41 . This operation provides a triangular matrix U corresponding to the Gram matrix. More precisely, thanks to the structure of new_G', a triangular matrix U is defined as follows (where X' denotes the transpose of a matrix X): new_G ' new_G' = U ¹ U

Then, in a step 542, the received signal is projected on the matrix computed on step 541 . This projection first multiplies the received signal R' by new_G'' and then by the inverse of U'.

As the variant, the step 541 is replaced by a QR decomposition of a new equivalent channel matrix (new_G'), new_G' being equal to QU where Q is an orthogonal matrix and U an upper triangular matrix. In this case, step 542 comprises a multiplication by Q*. Figure 12 represents details Gram Matrix computation 540. The step 540 begins with a step 5400 of computation of an equivalent channel matrix G' equal to the product HC.

Step 540 consists in permuting the columns of the real matrix G' of equation (2) according to a particular criterion based on the components of the Gram matrix G''G'.

According to step 540, the lattice basis is permuted so that successive dimensions that are addressed in the search phase are as collinear as possible. The component (C ¹ C) _1J contains the scalar product between f ^h and f basis vectors that are respectively f ^h and f ^h column vectors of C, so that the larger abs((G''G')ι,), the more collinear the f ^h and / ⁷ vectors.

According to a variant, complex notations are used (instead of real notation), the vectorial space on the field of real numbers is replaced by the vectorial space on the field of complex numbers and the scalar product (and associated norm) is changed accordingly.

Then, during a step 5401 , a matrix M is computed, M being equal to the product G''G' plus ε, where ε is smaller than the smallest absolute value of M. The use of ε allows that the step 540 also produces a permutation of (1 ,..,K) even when M is diagonal. The product G''G'

corresponds to computation of non normalized scalar products of vectors of G'.

Then, during a step 5402, the diagonal of M is set to 0 (M(/,/) equals 0 for every value of / from 1 to K). This avoids producing the identity permutation or a permutation only based on the lattice basis vector norms, which performs worse than the present criterion.

During step 5402, the first element of a permutation vector P is set to 1 (P(1 ,1 )= 1 ) and a variable i_in is set to 1 . This corresponds to a choice of first column of G'. As a variant, the first dimension dealt with is the one corresponding to the smallest or largest diagonal value of G' ^l G' (this enables processing of the dimension with largest energy first, in the lattice decoding step).

After choice of a first dimension, the vectors of M are sorted according to a decreasing colinearity criterion, vectors being compared 2 by 2 (that enables a dimension permutation).

Then, during a step 5403, a counter / is set to 1 .

Then, during a step 5404, the element M(Mn, P(1 ,1 :/)) is set to 0. (1 :/) denotes the vector [1 ,2,...,i] so that P(1 ,1 :/) denotes the first / components of the row 1 of P. M(Mn,P(1 ,1 :/)) denotes the elements of row Mn of M having column indexes P(1 ,1 :/). This initialization 5404 of the Mn row of M is made to avoid producing twice the same index in the permutation vector (and hence not producing a permutation).

Then, during a step 5405, a counter k is set to 1 and a variable max is set to 0. Then, during a test 5406, the CPU 41 checks if the absolute value of M{i_in,k) is superior or equal to max.

If so, during a step 5407, max is set to the absolute value of M(Mn,/c) and an index i_out is set to k.

If the result of test 5406 or after 5407, the counter k is incremented (/c=/c+1 ).

In test 5406 and step 5407, the index i_out corresponding to the basis vector is searched. The index i_out is the most collinear (i.e. largest absolute value of scalar product) with respect to the current basis vector Mn.

Then, during a test 5409, the CPU 41 checks if the counter k is equal to K+1 .

If no, the test 5406 is reiterated.

If yes, during a step 5410, the value of P(1 ,/+1 ) is set to i_out. Adjacent dimensions in the permutation now have highest absolute value of scalar product. During, this step IJn is also set to i_out.

Then, during step 541 1 , the counter / is incremented (/=/+1 ). Then, during a test 5412, the CPU 41 checks if / equals K.

If no, step 5404 is reiterated.

If yes, during a step 5413, a new matrix new_G' is obtained from G' by permuting the columns of G' according to P (new_G = G'(:,P(1 ,1 :K))). The new Gram matrix new_Gram is equal to the product new_G'' ^* new_G' new_Gram=G' ^t G'(P(1 _J 1 :K),P(1 _J 1 :K)) and is obtained from C ¹ G' by permuting the columns and lines of G'*G'. This new matrices new_Gram and new_G' are the ones that will serve for the lattice decoding preprocessing phase (QR or Cholesky decomposition...).

In a variant where step 541 is replaced by a QR decomposition of new_G', producing a new_Gram matrix is not necessary (during step 5413).

According to a variant, during step 5401 M is equal to the product

G' ^l G and, it is checked whether M is diagonal or not. If so, steps 5402 to

5412 are replaced by a permutation that is only based on the diagonal values of M and more especially that comprises an ordering of its elements according to decreasing (or increasing) values of diagonal values.

According to a variant, step 5401 can be replaced by step 13 disclosed in figure 13. According to this variant the scalar product between vectors of G' is normalized.

Step 14 begins by a step 130 of set of a counter / to 0. Then, during a step 131 , the counter / is incremented (/=/+1 ).

Then, during a step 132, a countery is set to 0.

Then, during a step 133, the countery is incremented (/=/+1 ).

Then, during a step 134, the element M(i,j) is set to G' ^t G'(i,j)/sqrt(G' ^t G'(i,i) ^* G' ^t G'(j,j)), this scalar product being normalized. Then, during a test 135, the CPU 41 checks if j equals K. If no, step 133 is reiterated.

If yes, during a test 136, the CPU 41 checks if / equals K. If no, step 131 is reiterated. If yes, during a step 137, M is set to the sum M +ε.

Figure 9 and 10 detail decoding step 55, which comprises an enumeration of candidate lattice points that takes into account a minimum distance dm in.

ML points are searched among lattice points (using the basis U) that are in a space between spheres 71 and 72 of radius respectively dmin and dmax.

Depending on the type of lattice decoder, this search phase is implemented in different ways. Figures 9 and 10 detail two different embodiments. Other alternative search algorithms can be implemented according to the invention, these algorithms being based on algorithms such as so called tree search, branch and bound and wherein the ML points are searched in a space outside a sphere of a minimum radius dmin. Embodiment of figure 9 is based upon a sphere decoding (as the algorithm of Viterbo/Boutros) with a restriction of the selection lattice points that must not be too close to the received signal point (the distance between the selected points and the received signal point is greater than dmin). Provided that the sphere radius is large enough, the ML point is in the largest sphere. This approach allows to define bounds for each component (or dimension) of the candidate signals S, within which discrete components of the signal are enumerated. That can be summarized by the equation:

9 t drrύn < U ¹ R

P u'u U ¹ R < J max'

P

The inverse of U is straightforward. Using that U is upper triangular, we obtain recursive bounds for each component of a candidate S.

The components of S further satisfy the modulation constellation boundaries constraints as S components are a constellation point. For instance, if a 16QAM modulation is used, the components of S satisfy

-3<Si<3. The step 55 begins with an initialization step 550 where a cumulated metric DDim associated to each dimension is set to 0, a maximum distance DMAX is set to infinity and a current dimension index Dim is set to K (lattice dimension).

Then, during a step 551 , three intervals are defined: - Hdim=[V1,V2] defines boundaries for the components of dimension Dim of a candidate signal as follows:

+ lu _M o _u U , ,1+1 K o - s ':+I A: ,I

for / = K -1 and with r = DMAX, O = U ¹ R and / = Dim

P

I2dim =]-∞, V'1] U [\/'2, +∞[ defines boundaries for the components of dimension Dim of a candidate signal as follows:

(u _v o _{Iil +} fu _I>I+1 ,(o - S) ₁₊₁ , !)

for / = K -1 and with r = of/n/n, O = U R and / = Dim

P

- IDim is equal to the intersection of Hdim and I2dim and is also restricted to the boundaries of the modulation constellation.

Then, during a step 552, the CPU 41 begins to enumerate or continues to enumerate the discrete values of a component of dimension Dim of a candidate.

Then, during a test 553, the CPU 41 checks if the enumeration is finished (i.e. if all possible discrete values of /dim have been tested).

If the negative, during a step 554, the CPU 41 computes a new cumulated metric DDim associated to Dim and current related discrete value. Then, during a test 555, the CPU 41 checks if the cumulated metric DDim is smaller than DMAX and larger than dmin. If so, during a test 556, the CPU 41 checks if the current dimension Dim is equal to 1 .

If no, the dimension Dmin is decreased by 1 in a step 557 and the step 551 is reiterated.

If during the test 553, the end of enumeration is reached, or if the result of test 555 is negative, then, during a test 558, the CPU 41 checks if Dim equals K.

If Dim is different of K, then during a step 559, Dim is increased by 1 and step 552 is reiterated.

If Dim equals K, then, during a step 551 1 , the current ML candidate is chosen and sent as decoded signal and demapped according to digital modulation (symbol to bits conversion) to an application.

If the result of test 556 is positive (DZm=I ), then during a step 5510, a new candidate ML solution replaces the current one and DMAX is set to DDim. After step 5510, step 559 is performed.

Embodiment of figure 10 is based upon a decoding based on projections (as the Schnorr-Euchner algorithm) with a restriction of the selection lattice points that must not be too close to the received signal point

(the distance between the selected points and the received signal point is greater than dmin). The search comprises successive orthogonal projections of the received signal on lattice subspaces and enumerating the lattice points between two spheres 71 and 72 around the projected point.

The components of S further satisfy the modulation constellation boundaries constraints as S components are a constellation point. For instance, if a 16QAM modulation is used, the components of S satisfy -3<S/<3. According to variant of figure 10, the step 55 begins with an initialization step 5520 where a cumulated metric DDim associated to each dimension is set to 0, a maximum distance DMAX is set to infinity and a current dimension index Dim is set to K (lattice dimension).

Then, during a step 5521 , the CPU 41 computes a new discrete value of component of dimension Dim of a candidate signal and intermediate values related to Dim and to this discrete value (incrementing step, partial metric).

Then, during a step 5522, the CPU 41 computes a new cumulated metric DDim associated to Dim and current related discrete value. Then, during a test 5523, the CPU 41 checks if the cumulated metric DDim is smaller than the minimum value among dmax and DMAX (DDim<rr\\n(dmax,DMAX)) and larger than dmin (DD/m>dmin).

If so, during a test 5524, the CPU 41 checks if the current dimension Dim is equal to 1 .

If no, the dimension Dim is decreased by 1 in a step 5525 and the step 5521 is reiterated. If yes, during a step 5529, a new candidate ML solution replaces the current one and DMAX is set to DDim.

If the result of test 5523 is negative, or then, during a test 5526, the CPU 41 checks if Dim equals K.

If Dim is different of K or after step 5529, during a step 5527, Dim is increased by 1 .

Then, during a step 5528, the CPU 41 updates a new discrete value of component of dimension Dim of a candidate signal (i.e. add the incrementing step to the previous discrete value of Dim) and intermediate values related to Dim and to this discrete value. Then, step 5522 is reiterated.

If Dim equals K during the test 5526, then, during a step 5530, the current ML candidate is chosen and sent as decoded signal and demapped according to digital modulation (symbol to bits conversion) to an application.

As a variant step 55 does not take into account a minimum distance dmin. Such a variant can derive from decoding step presented in figures 9 and 10 and is, for example, based on the enumeration of candidates as in document "A universal lattice code decoder for fading channel," written by E. Viterbo and J. Boutros (and published in IEEE Trans.

Inform. Theory, vol. 45, pp. 1639-1642, July 1999) or in document "Lattice basis reduction: Improved practical algorithms and solving subset sum problems," written by CP. Schnorr and M. Euchner (and published in Math.

ProGraming, vol. 66, pp. 181-191 , 1994). Those documents disclose ML recursive decoding algorithms that are based on a lattice and enable enumeration of points and selection of points after reception of a signal representative of data. The selection of points is done in a sphere the diameter of which depends on the signal/noise ratio. After computation of some metrics, a ML point is selected either by enumerating candidates points in a sphere (Boutros) or by successive projections on sublattices

(Schnorr/Euchner). Figure 11 represents a multiuser detection according to a specific embodiment of the invention. This detection or decoding is applied to a wireless network comprising a receiver and a set of several transmitters that

can be identified through a multiple access scheme (e.g. CDMA (or Code Division Multiple Access), flash OFDM, ...). In this context, several users are sharing the same propagation resource to transmit data to the receiver.

In the case of multiuser detection, similarly to the MIMO decoding as disclosed previously, the decoding problem comprises a detection of a transmitted multidimensional discrete input vector based on a multidimensional continuous observation that is made of a linearly distorted version of the transmitted vector further corrupted by additive noise.

For multiuser detection according to the invention, the multidimensional input vector is made of the real and imaginary components of the collection of symbols transmitted by Q users on a given time and/or frequency region depending on the multiple access scheme. For instance, in the case of Code Division Multiple Access (CDMA), the region corresponds to the time duration of the spreading sequences. The multidimensional continuous observation is made of the collection of matched responses to the set of used multiple access signatures. The linear distortion of the transmitted signals is the matrix made of the collection of equivalent channel matrices between the Q transmitters and the receiver taking into account the multiple access scheme. For instance, in the case of CDMA, this linear distortion is made of the combination of the channel matrices with the correlation matrix of the spreading codes subset. The additive noise is the thermal additive white Gaussian noise at the receiver side and its amplitude follows a chi square law.

Figure 1 1 represents a multi-user detection according to a specific embodiment of the invention. This detection is implemented in a receiver that receives data from Q transmitters using e.g. a CDMA.

The decoding begins with a initialization step 1 10, wherein different parameters of the method are set to their initial value(s).

Then, during a step 1 1 1 , the receiver waits for and receives a signal from filters matched to the used CDMA sequences.

Then, the receiver makes an estimation 1 12 of the channels between the Q transmitters and the receiver. This estimation is based upon the pilot sequences used specifically by each transmitter.

Then, in a step 1 13, the receiver computes σ using, for example, pilot sequences, and determines dmin as explained above (Q meaning here the number of transmitters being used to define dmin in the same way as Q meaning the number of symbol per space/time codeword in the embodiment

of figure 5) and possibly dmax in a similar way. Advantageously, step 1 13 is executed after each channel estimation 1 12. According to a variant of the invention, step 1 13 is not done at each reception of signal corresponding to one transmitted block. According to a variant, the decoding method does not take into account any minimum distance dmin and step 1 13 does not determine dmin.

During a step 1 17, a subset of time/frequency bins is determined.

The subset comprises bins that correspond to one out of two time dimensions and one out of two frequency dimension. Step 1 17 is similar to step 57 and won't be furthered disclosed.

Then, the receiver is executing a preprocessing step 1 14 similar to step 54 of figure 5, the equivalent channel matrix G' being replaced by the matrix made of the collection of equivalent channel matrices between the Q transmitters and the receiver taking into account the multiple access scheme.

Then, during step 1 18, for each bin that does not belong to the subset, an interpolation is performed using the result step 1 14 for bins of subset, surrounding the considered bins. Step 1 18 is similar to step 58 and won't be furthered disclosed. Then, receiver is enumerating lattice points and selects decoded point in a step 1 15 similarly to step 55 of figure 5, the candidate transmitted space/time encoded signal being replaced by the collection of the transmitted signals by the Q transmitters.

Then, during a step 1 16, the components of the decoded point are inversely permutated according to the permutation produced by step 540. After step 1 16, step 1 1 1 is reiterated.

According to variant of multi-user detection, part of the transmitters or all of them and the receiver use single antennas, or MIMO. According to other variants, the transmitters and the receiver are using single carrier or multiple carrier modulation.

According to a variant (not illustrated), a test is performed to check whether interpolation or preprocessing is appropriate. According to this variant, a test similar to test 59 is performed after step 1 14. If the result of this test is positive, then the step 1 18 is performed. Else, a preprocessing step similar to step 1 14 and applied to bin that are outside the subset is performed, this step being followed by step 1 15.

Of course, the invention is not limited to the embodiments described above.

The invention is compatible with any type of wireless link (point to point links, wireless LANs, mobile networks, digital broadcasting, satellite communication, ...). The disclosed receiver in figure 3 comprises then elements adapted to a specific application (such as front end, demodulator, MAC layer interface, and all other usual communication layer elements). The invention is especially well adapted to the reception of Digital Video Broadcasting (or DVB (e.g. DVB-T (terrestrial), DVB-S (satellite), DVB-H (handheld)..). In this case, the discrete multidimensional coded signal comprises data representative of a digital video broadcast signal.

The invention is advantageously used in high spectral efficiency wireless transmission (MIMO system and/or nQAM modulation), and, in particular, high rate transmission. Indeed, the invention can be used for other transmission (eg. single antenna for multi-user detection, nQPSK modulation, ...).

The invention is not limited to MIMO decoding or multi-user detection and can be applied to combination of MIMO decoding and multiuser detection and more generally to any system wherein noise amplitude distribution is following a chi square law and more generally laws that are not centred on 0 (these laws are generally associated to a multidimensional distribution of noise in a multidimensional signal decoding).

The invention comprises the determination of a minimum distance according to a noise level associated to the multidimensional received signal. When applied to a MIMO decoding, the dimensions of the received signals corresponds to K (in real notation for nQAM or nPSK modulation) or Q(in complex notation for nQAM or nPSK modulation or polar notation for nPSK modulation). When applied to a multi-user detection, the dimensions of the received signal corresponds to the number of users (Q in complex notation or polar notation (if the users using nPSK modulation)) or K-2Q in real notation.

According to MIMO decoding according to the invention, the receiver decodes a signal that has been space time encoded and transmitted with at least two antennas. The space time encoding can be based on a space time block code. According to a variant, the space time encoding is a simple spatial multiplexing; then, the code matrix C is the identity matrix.