Tree search-based decoding

Abstract

A method, device, and a computer program are provided to decode a signal received through a transmission channel in a communication system, the received signal being represented by a signal vector. The method comprises: calculating an initial estimate of a transmitted symbol vector carried by the received signal vector; calculating a bound parameter (201) from a linear function of the initial estimate of the transmitted symbol vector, the linear function being defined by a slope coefficient and an intercept coefficient, the method further comprising: determining estimated symbols representative of the transmitted symbols carried by the received signal, the estimated symbols being determined from a set of candidate lattice points, each lattice point comprising a set of components, each component of a candidate lattice point being searched in a search interval (203), the search interval having at least one search interval bound computed from the bound parameter; determining (205) the estimated symbols from the closest lattice point to the received signal vector among the candidate lattice points.

Claims

1. A method for decoding a signal received through a transmission channel in a communication system, said received signal being represented by a signal vector, the method comprising: calculating an initial estimate of a transmitted symbol vector carried by the received signal vector; calculating a bound parameter from a value of a linear function of said initial estimate of the transmitted symbol vector and a first quantity depending on a noise variance and a channel matrix associated with said transmission channel, said linear function being defined by a slope coefficient and an intercept coefficient, the slope coefficient and the intercept coefficient depending on a first function parameter () which is higher than a predefined threshold, said first function parameter being a real value positive parameter, said threshold being determined from said initial estimate of the transmitted symbol vector; the method further comprising: determining estimated symbols representative of transmitted symbols carried by the received signal, said estimated symbols being determined from a set of candidate lattice points, each candidate lattice point comprising a set of components, each component of a candidate lattice point being searched in a search interval, said search interval having at least one search interval bound computed from said bound parameter; and determining said estimated symbols from the closest candidate lattice point to the received signal vector among said candidate lattice points.

2. The method of claim 1, wherein said channel matrix is of a given dimension (n), a QR decomposition being previously applied to said channel matrix where Q designates an orthogonal matrix and R an upper triangular matrix.

3. The method of claim 2, wherein said bound parameter (C.sub.prop) is defined as a minimum value between: the first quantity being determined from at least one of a first radius (C.sub.1) function of the noise variance (.sup.2) and a second radius (C.sub.2) function of a minimum of diagonal elements of a Gram matrix of said channel matrix, and a second quantity corresponding to the value of said linear function of said initial estimate (C.sub.d.sub.DFE).

4. The method of claim 3, wherein said first quantity is determined as the minimum between said first radius (C.sub.1) and said second radius (C.sub.2).

5. The method of claim 3, wherein a minimum value of said threshold depends on a square of the initial estimate of the transmitted symbol vector (d.sub.DFE.sup.2), a square of the first radius (C.sub.1.sup.2), and/or a square of the second radius (C.sub.2.sup.2).

6. The method of claim 5, wherein a minimum value of said threshold .sub.min of the first function parameter () is defined as: ${}_{\min }=\max \left(\frac{d_{\mathrm{DFE}}^2}{C_1^2},d_{\mathrm{DFE}}^2{C}_2^2\right),$ where d.sub.DFE.sup.2 designates the square of the initial estimate of the transmitted symbol vector, C.sub.1.sup.2 designates the squared first radius (C.sub.1.sup.2), and C.sub.2.sup.2 the squared second radius.

7. The method of claim 3, wherein the intercept coefficient is equal to , and a minimum value of said threshold depends on at least one of: a difference between the initial estimate of the transmitted symbol vector (d.sub.DFE) and the first radius (C.sub.1) and/or a difference between the initial estimate of the transmitted symbol vector (d.sub.DFE) and the second radius (C.sub.2).

8. The method of claim 7, wherein the minimum value of the threshold .sub.min of the first function parameter () is defined as a maximum value between: the difference between the initial estimate of the transmitted symbol vector (d.sub.DFE) and the first radius (C.sub.1) and the difference between the initial estimate of the transmitted symbol vector (d.sub.DFE) and the second radius (C.sub.2).

9. The method of claim 1, wherein said linear function is a multiplicative function, said slope coefficient being different from one.

10. The method of claim 1, wherein the slope coefficient is equal to an inverse of a square root of the first function parameter $\left(\frac{1}{\sqrt{}}\right).$

11. The method of claim 1, wherein said linear function is an additive function different from an identity function, the slope coefficient being equal to one and the intercept coefficient being different from zero.

12. The method of claim 1, wherein the intercept coefficient is equal to .

13. The method of claim 1, wherein said candidate lattice points are determined according to a sphere-constrained decoding algorithm utilizing a decoding tree comprising nodes representing possible symbols of the transmitted symbol vector, and searching said candidate lattice points in a sphere having an initial radius set to the bound parameter, said step of determining estimated symbols comprises searching each component of said candidate lattice point in a search interval comprising a lower bound and an upper bound depending on said initial radius.

14. The method of claim 13, wherein said candidate lattice points are determined according to a spherical decoding algorithm, said step of determining estimated symbols comprising in response to the determination of said candidate lattice point, further determining if an Euclidean distance between said candidate lattice point and a point representing the received signal vector is lower than the bound parameter and if so updating the initial radius of the sphere.

15. The method of claim 14, wherein said step of updating the initial radius comprises computing an updated radius from the Euclidean distance between said candidate lattice point and the point representing the received signal vector.

16. The method of claim 3, wherein said candidate lattice points are determined according to a (Spherical Bound) SB-stack spherical decoding algorithm, said step of searching candidate lattice points comprising storing each component of said candidate lattice point in a stack in association with a metric.

17. A computer program product for decoding a signal received through a transmission channel in a communication system, said received signal being represented by a signal vector, the computer program product comprising: a non-transitory computer readable storage medium; and instructions stored on the non-transitory computer readable storage medium that, when executed by a processor, cause the processor to: calculate an initial estimate of a transmitted symbol vector carried by the received signal vector; calculate a bound parameter from a value of a linear function of said initial estimate of the transmitted symbol vector and a first quantity depending on a noise variance and a channel matrix associated with said transmission channel, said linear function being defined by a slope coefficient and an intercept coefficient, the slope coefficient and the intercept coefficient depending on a first function parameter which is higher than a predefined threshold, said first function parameter being a real value positive parameter, said threshold being determined from said initial estimate of the transmitted symbol vector; wherein said processor is further caused to: determine estimated symbols representative of transmitted symbols carried by the received signal, said estimated symbols being determined from a set of candidate lattice points, each candidate lattice point comprising a set of components, each component of a candidate lattice point being searched in a search interval, said search interval having at least one search interval bound computed from said bound parameter; and determine said estimated symbols from the closest candidate lattice point to the received signal vector among said candidate lattice points.

18. A device for decoding a signal received through a transmission channel in a communication system, said received signal being represented by a signal vector, wherein the device comprises: at least one processor; and a memory coupled to the at least one processor and including instructions that, when executed by the at least one processor, cause the device to: calculate an initial estimate of a transmitted symbol vector carried by the received signal vector; calculate a bound parameter from a value of a linear function of said initial estimate of the transmitted symbol vector and a first quantity depending on a noise variance and a channel matrix associated with said transmission channel, said linear function being defined by a slope coefficient and an intercept coefficient, the slope coefficient and the intercept coefficient depending on a first function parameter which is higher than a predefined threshold, said first function parameter being a real value positive parameter, said threshold being determined from said initial estimate of the transmitted symbol vector; wherein said device is further caused to: determine estimated symbols representative of transmitted symbols carried by the received signal, said estimated symbols being determined from a set of candidate lattice points, each candidate lattice point comprising a set of components, each component of a candidate lattice point being searched in a search interval, said search interval having at least one search interval bound computed from said bound parameter; and determine said estimated symbols from the closest candidate lattice point to the received signal vector among said candidate lattice points.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The accompanying drawings, which are incorporated in this specification and constitute a part of thereof, illustrate various embodiments of the invention and, together with the general description of the invention given above, and the detailed description of the embodiments given below, serve to explain the embodiments of the invention.

(2) FIG. 1 schematically represents an exemplary communication system implementing the decoding method;

(3) FIG. 2 is a flowchart depicting the main steps of the sphere-constrained decoding method according to certain embodiments of the invention;

(4) FIG. 3 is a flowchart depicting an exemplary application of the invention to SB-stack decoding;

(5) FIG. 4 is a flowchart depicting the determination of the initial radius according to certain embodiments;

(6) FIG. 5 is a diagram illustrating the probability of having C.sub.d.sub.DFEC.sub.0 in a 22 MIMO communication system comprising a Sphere Decoder for different values of the radius function parameter;

(7) FIG. 6 is a diagram illustrating the total complexity obtained for different values of the radius function parameter where the radius function is of multiplicative type, in a 22 MIMO communication system using spatial multiplexing and 16-QAM modulation, and comprising a sphere decoder;

(8) FIG. 7 is a diagram illustrating the total complexity obtained for different values of the radius function parameter where the radius function is of additive type, in a 22 MIMO communication system using spatial multiplexing and 16-QAM modulation, and comprising a sphere decoder;

(9) FIG. 8 is a flowchart depicting another embodiment of the invention using the bound parameter as a node metric constraint; and

(10) FIG. 9 schematically shows an exemplary hardware architecture of the decoder according to certain embodiments.

DETAILED DESCRIPTION

(11) Embodiments of the invention provide a method and apparatus for decoding a signal received over a communication channel that reduces the number of search operations in any tree-search based decoder by providing a bound parameter to constraint the search of the closest lattice point. Such tree search comprises the determination of estimated symbols representative of the transmitted symbols carried by the received signal, the estimated symbols being determined from a set of candidate lattice points. Each candidate lattice point comprises a set of components. Each component of a candidate lattice point is searched in a search interval, the search interval I.sub.i having at least one search interval bound computed from a bound parameter.

(12) According to one aspect of the invention, the bound parameter is determined from a linear function of the Euclidean distance between an initial estimate d.sub.e of the transmitted symbol vector and the received signal. The linear function f( ) (also referred to hereinafter as the bound parameter function or the radius function) is defined by a slope coefficient and an intercept coefficient as follows:
(d.sub.E)=a.sub.1.Math.d.sub.E+a.sub.2(1)

(13) In equation (1), a.sub.1 represents the slope coefficient of the bound parameter function and a.sub.2 represents the intercept coefficient of the bound parameter function. Such bound parameter function ensures that at least one lattice point is found in the search space while optimizing the computational complexity.

(14) The slope and intercept coefficients are real value parameters. Preferably, if the slope coefficient of the radius function a.sub.1 is equal to 1 (a.sub.1=1), the intercept coefficient a.sub.2 is set to a value different from 0 (a.sub.20).

(15) The invention may apply to any tree-search based decoder implementing a tree search strategy to scan the lattice points. Particularly, the invention may apply to sphere-constrained decoders which implement a depth-first strategy for searching the candidate lattice points and search the candidate lattice points inside a sphere having a radius initially set to an initial radius value, the sphere being centered at a point representing the received symbol or on a particular symbol of the lattice points. In such application of the invention to sphere-constrained decoders, the bound parameter corresponds to the initial sphere radius of the sphere inside which the candidate lattice points are searched. Examples of sphere-constrained decoders comprise the sphere decoding algorithms or SB-stack decoding algorithm.

(16) Alternatively, the invention may apply to other types of tree-search based decoder algorithms which implement a tree search strategy to scan the lattice points without limiting as such the search region of the lattice points to a spherical region, such as Stack decoding algorithms, the Zigzag Stack decoding algorithm and the M-algorithm. In such applications, the bound parameter may be used to set a metric threshold (or cost threshold), the lattice points being explored only if their respective metric satisfies a constraint related to the bound parameter.

(17) Tree-search based decoding algorithms use a tree representation to search for candidate lattice points. The search tree is a decoding tree data structure representing constellation points of the received signal corresponding to a constellation such as a 2.sup.q QAM. The search tree comprises a number of nodes. Each node comprises an integer value representing a component of a symbol of the received data signal (the received data signal may be represented according to a real-value representation). In the following description, the term node or node value will be similarly used to designate a component of a symbol of the received data signal. The first node of the tree is referred to as the root node. A node that does not have any child node is referred to as a leaf node and corresponds to the lowest level in the tree. Each node has at most one parent node located above it in the tree. The root node being the highest node in the tree, it does not have any parent node. The depth (or dimension) of a given node designates the length of the path from this given node up to the root node of the decoding tree. All the nodes of the decoding tree can be reached from the root node. Each path from the root node to a leaf node thus represents a possible transmitted signal. Nodes in the decoding tree represent the different possible values of the symbols s.sub.i, where s.sub.i, with i representing an integer ranging from n to 1, represent the real and imaginary components of the transmitted information vector.

(18) In one embodiment, the initial estimate of the transmitted symbol vector may be a Zero Forcing decision feedback equalizer decoding (ZF-DFE) estimate, determined using a ZF-DFE detection, the bound parameter function being then defined from the linear function f( ) of the Euclidean distance d.sub.DFE between the ZF-DFE estimate and the received signal:
(d.sub.DFE)=a.sub.1.Math.d.sub.DFE+a.sub.2

(19) Although the use of a ZF-DFE estimate has particular advantages in certain applications, the invention is not limited to such type of initial estimate of the transmitted symbol vector. For example, the initial estimate of the transmitted symbol vector may be alternatively determined using any sub-optimal decoding method such as the minimum mean square error (MMSE) method providing an MMSE estimate or a zero forcing (ZF) method providing a ZF estimate. Such initial estimate of the transmitted symbol vector may be obtained using a preprocessing such as a Lattice Reduction or a MMSE-GDFE (Minimum Mean-squared Error Generalized Decision-Feedback Equalization) preprocessing followed by a suboptimal linear or non-linear decoder (such as ZF or ZF-DFE decoders respectively). The following description of certain embodiments of the invention will be made with reference to a ZF-DFE estimate for illustration purpose only. Exemplary linear decoders 300 that may be used to determine the initial estimate of the received signal are described for example in:

(20) K. R. Kumar, G. Caire, and A. L. Moustakas, The Diversity-Multiplexing Tradeoff of Linear MIMO Receivers, IEEE Information Theory Workshop ITW'07, pp. 487-492, 2007, or

(21) J. Jalden, P. Elia, DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models, IEEE Transactions on Information Theory, May 25, 2009.

(22) Embodiments of the invention thus improve the determination of the bound parameter defined to constraint the tree search (initial radius of a sphere-constrained decoder or cost threshold) and reduce the number of visited nodes while ensuring ML performance, and speeding up the decoder.

(23) Embodiments of the present invention will now be described in relation with sphere-constrained decoders where the bound parameter represents the initial sphere radius of the sphere within which the lattice points are searched, for illustration purpose only.

(24) In sphere-constrained decoders (also referred to as spherical lattice decoders) such as the SB-Stack decoder as described in EP2274852 and the sphere decoders as described for example A Universal Lattice Code Decoder for Fading and Channels (J. Boutros et E. Viterbo, IEEE Transactions on Information Theory, July 1999), the search space, inside which the lattice points are searched, is confined within a sphere having an initial radius, centered on a point representing the received symbol or on another selected point. While the sphere decoder uses a Depth First Search strategy to scan the lattice points, the SB-stack uses the Best First Search strategy.

(25) Such sphere-constrained decoders are based on generating a decoding tree from a received signal where each path from a root node to a leaf node represents a possible transmitted signal, according to the associated tree search strategy (Depth-first search for a sphere decoder, Best-First search for an SB-stack decoder). Such a decoding tree may be used in the decoder to determine the closest vector to the received signal according to the Maximum Likelihood (ML) criterion, by searching a set of candidate lattice points within the sphere having the initial radius.

(26) The Depth-First strategy, as implemented in the Sphere Decoders, starts from the root node and explores the first child node s.sub.n, then its nearest child node s.sub.n-1, and so on until reaching a leaf node s.sub.1. Given the first path found, the search proceeds by returning back to the level 2 in the tree and explores the neighbor of the already explored node s.sub.2. After finding all the possible paths and computing their relative cumulated weights, the shortest path may be output.

(27) The Best First strategy as implemented in the SB-stack decoders corresponds to an optimized version of the Breadth-First strategy. The search strategy is based on exploring only best paths in the tree of possible lattice points based on the respective metrics (also referred to as the costs or weights) assigned to the nodes. Starting from the root node, the algorithm explores all child nodes s.sub.n and stores all or a subset of the child nodes in a stack in association with their respective metrics. The stack is then reordered based on the node metrics. According to a recursive process, the child nodes of the top node in the stack are then generated and the metric of the child nodes are computed, before storing all or a subset of the child nodes in the stack in association with their respective metrics and ordering the stack by metric. The search is recursively repeated for each top node in the stack until finding a leaf node. The optimal path s.sup.(1)=(s.sub.n, s.sub.n-1, . . . , s.sub.1) is then returned. By maintaining only the nodes having lower weights, the search complexity is reduced.

(28) In sphere-constrained decoders (sphere decoders or SB-stack decoders for example), during the progressive construction of the decoding tree, the nodes corresponding to points inside the sphere are generated. In other words, for each node generated according to the applied tree search strategy, a node s.sub.i is expanded or selected only if the node value is comprised in a search interval I.sub.i=[B.sub.inf,i, B.sub.sup,i] having a lower boundary B.sub.inf,i and an upper boundary B.sub.sup,i which both depend on the initially set radius C. The data signal can be estimated by taking into account the node information, such as the node path(s).

(29) A sphere having an initial radius C, centered on a point representing the received symbol (or on another selected point), is thus considered in sphere-constrained decoders. This amounts to determining if each node value s.sub.i is comprised in the search interval I.sub.i, the boundaries B.sub.inf.sub.i and B.sub.sup.sub.i depending on the initial radius.

(30) In a method according to the invention, the initial radius C is determined from the linear function of Euclidean distance d.sub.DFE between an initial estimate of the transmitted symbol vector, such as a ZF-DFE estimate, and the received signal, according to equation 1:
(d.sub.DFE)=a.sub.1.Math.d.sub.DFE+a.sub.2(1)

(31) The initial radius is thus optimally set so that the number of lattice points included inside a sphere with the initial radius can be efficiently reduced. Hence, the computational complexity of the sphere-constrained decoder can be significantly reduced.

(32) The present invention may be implemented in a wireless communication system for decoding information symbols (also referred to hereinafter as lattice points). The communication system comprises at least a transmitter for transmitting simultaneously a plurality of information symbols through a communication channel, and at least a receiver for receiving one or more of the symbols transmitted by the transmitter(s) in the form of independent signals. The communication channel may be any linear AWGN (Additive White Gaussian Noise) channel or multipath channel combined with multicarrier modulation techniques such as an OFDM (Orthogonal Frequency-Division Multiplexing), or multiple access techniques such as CDMA (Code division multiple access).

(33) An embodiment of the invention can be integrated in a receiver, for example for the decoding of data transmitted in a MIMO (Multiple Input Multiple Output) channel, according to any MIMO configuration, or for the decoding of signals sent by multiple users.

(34) When applied to MIMO decoding, in the presence of a single user or multiple users, the dimension of the received signal or channel output depends on the dimension of the signal space at the transmitter, on the number (n.sub.t) of the Transmit (Tx) antennas and/or on the number (n.sub.r) of Receive (Rx) antennas.

(35) Referring to FIG. 1, an exemplary wireless network environment 100 is shown in which embodiments of the invention may be implemented. The wireless network environment 100 may comprise a plurality of base stations (also referred to as nodes or access points or cells depending on the application context of the invention), each base station including a transmitter and a receiver including one or more antennas. Each station may communicate with other stations through a wireless connection. Each transmitter of a station may exchange data with a receiver of another station according to the wireless communication system illustrated in FIG. 1. The wireless network 100 may rely on a centralized architecture (a controller is provided to control the operation of the base stations) or a decentralized architecture (the base stations may communicate directly with one another). User Terminals (such as wireless devices, cellular phones, personal digital assistants, etc.), may communicate with one or more base stations on the forward link or on the reverse links. The user terminals may be fixed or mobile.

(36) The MIMO configuration may be symmetric, in which case it includes a same number (n.sub.t) of Transmit antennas as the number (n.sub.r) of Receive antennas. Alternatively, the MIMO configuration may be asymmetric, in which case the number (n.sub.t) of Transmit antennas is different from the number (n.sub.r) of Receive antennas (in particular the number n.sub.r, at the receive side, is higher than n.sub.t, at the transmit side to avoid a rank deficiency).

(37) FIG. 1 shows an exemplary wireless communication system 100 between a transmitter and a receiver in which a MIMO transmission is used, implementing an STBC (Space Time Block Code) code in transmission to distribute the symbols modulated over various degrees of freedom of the channel.

(38) The transmitter 2 can transmit a signal to a receiver 3 by means of a noisy MIMO channel. The data transmitter 2 can in particular be integrated in the base stations. The transmitter 2 may comprise for example:

(39) a channel coder 20 for providing convolutional codes,

(40) a modulator 21 such as a QAM modulator for delivering symbols;

(41) a space/time coder 22 for delivering a code word;

(42) n.sub.t transmission antennas 23, each transmission antenna being associated with an OFDM modulator.

(43) The transmitter 2 codes a binary signal received as input using a convolutional code provided by the channel coder 20. The signal is then modulated by the modulator 21 according to a modulation scheme (for example, a quadrature amplitude modulation 2.sup.q QAM). The modulator 21 can also implement a modulation scheme by phase shift, for example of the nPSK type, or any modulation. The modulation results in the generation of complex symbols belonging to a group of symbols s.sub.i. The modulated symbols thus obtained are then coded by the space-time coder 22 to form a code word STBC, such as the Golden Code (The Golden Code: A 22 Full-Rate Space-Time Code with Non-Vanishing Determinants, J.-C. Belfiore, G. Rekaya, E. Viterbo, IEEE Transactions on Information Theory, vol. 51, no. 4, pages 1432-1436, April 2005). The STBC code may be based on a complex matrix of dimension n.sub.tT, in which n.sub.t designates the number of transmission antennas and T is the time length of the STBC code, or on a spatial multiplexing (the modulated symbols are directly sent to the transmission antennas).

(44) The code word thus generated is converted from the time domain to the frequency domain and distributed over the n.sub.t transmission antennas. Each dedicated signal is then modulated by a respective OFDM modulator, and transmitted over the corresponding transmission antenna 23, optionally after filtering, frequency transposition and amplification.

(45) The receiver 3 can be also integrated in the base stations. The receiver 3 may be configured to receive a signal y transmitted by the transmitter 2 in a wireless channel. The channel may be noisy (for example channel with Additive White Gaussian Noise (AWGN) subjected to fading). The signal transmitted by the transmitter 2 may be further affected by echoes due to the multiple paths and/or the Doppler effect.

(46) In one exemplary embodiment, the receiver 3 may comprise:

(47) n.sub.r receiving antennas 33 for receiving the signal y, each receiving antenna being associated with a respective OFDM demodulator; the OFDM demodulators (n.sub.r demodulators) are configured to demodulate the received signal observed at each receiving antenna and delivering demodulated signals. A frequency/time converter may be used to perform a reverse operation of the time/frequency conversion implemented in transmission, and to deliver a signal in the frequency domain;

(48) a space/time decoder 30 configured to deliver a decoded signal;

(49) a demodulator 31 configured to perform a demodulation associated with a decoding.

(50) The Space Time decoder 30 may comprise an initial estimation unit such as a sub-optimal decoder 300 (which may be a linear or non-linear decoder) for providing an initial estimation of the transmitted signal (also referred to as a sub-optimal signal estimation) from the received signal using a sub-optimal decoding technique such as a ZF-DFE technique. The Space Time decoder 30 further comprises a tree-search based decoder 310 according to the embodiments of the invention which is configured to use the initial estimate of the original signal (e.g. ZF-DFE estimate), provided by the signal initial estimation unit, to decode the received signal.

(51) It should be noted that the receiver 3 implements a reverse processing of the processing implemented in transmission. Accordingly, if a single-carrier modulation is implemented in transmission instead of a multi-carrier modulation, the n.sub.r OFDM demodulators are replaced by corresponding single-carrier demodulators.

(52) The skilled person will readily understand that the various embodiments of the invention are not limited to specific applications. Exemplary applications of this new decoder include, with no limitation, multi-user communication systems, MIMO decoding in any symmetric or asymmetric configurations and implementable in wireless standards such as the WiFi (IEEE 802.11n), the cellular WiMax (IEEE 802.16e), the cooperative WiMax (IEEE 802.16j), the Long Term Evolution (LTE), the LTE-advanced, the 5G ongoing standardization, and optical communications.

(53) In one application of the invention to a multi-antenna system, for decoding a signal received by the multi-antenna system (MIMO), with n.sub.t transmit and n.sub.r receive antennas using spatial multiplexing, the data signal y.sub.c received as a complex-valued vector is equal to:
y.sub.c=H.sub.cs.sub.c+w.sub.c(2)

(54) In Equation (2), H.sub.c, s.sub.c and w.sub.c correspond respectively to the complex value of the channel matrix H, the vector s representing the transmitted data signal and the noise vector w. The received signal y.sub.c may be then transformed into a real-value representation, for example according to equation (3):

(55) $\begin{array}{cc}y=\left[\begin{array}{cc}\left(H_c\right)& -\left(H_c\right)\\ \left(H_c\right)& \left(H_c\right)\end{array}\right]\left[\begin{array}{c}\left(s_c\right)\\ \left(s_c\right)\end{array}\right]+\left[\begin{array}{c}\left(w_c\right)\\ \left(w_c\right)\end{array}\right]& \left(3\right)\end{array}$

(56) In equation (3), () and () denote respectively the real and imaginary parts of a complex-value vector.

(57) The equivalent channel output can then be written as:
y=Hs+w(4)

(58) In embodiments where a length-T Space-Time code is used, the channel output can be written in the same form as equation (2) with the equivalent channel matrix H.sub.eq given by:
H.sub.eq=H.sub.c(5)

(59) In equation (5), .sup.n.sup.t.sup.Tn.sup.t.sup.T corresponds to the coding matrix of the underlying code. Both uncoded and coded schemes result in a same real-value lattice representation. The following description will be accordingly made with reference to the spatial multiplexing and symmetric case with n.sub.t=n.sub.r and n=2n.sub.t for illustration purpose only.

(60) According to the equivalent system obtained in (4), the received signal can be viewed as a point of the lattice generated by H and perturbed by the noise vector w.

(61) The receiver is configured to provide an estimate of the symbol vector s, from the given data in H and y. Under such conditions, optimal ML decoding is solved for the closest vector in the n-dimensional lattice generated by H according to the minimization problem:
=arg min.sub.s.sub.c.sub.QAMyHs.sup.2(6)

(62) It should be noted that the embodiments of the invention particularly apply to coherent systems where H is known at the receiver or estimated at the receiver before the decoding stage.

(63) The ML decoder accordingly chooses the symbol vector s which yields the smallest Euclidean distance between the received vector y and the hypothesized message Hs. The ML decoder represents a discrete optimization problem over candidate vectors s within the chosen constellation. In the case of higher constellations and higher dimension of the system (number of antennas), the search for the ML solution in an exhaustive way generally requires a very high complexity.

(64) Before transmission of the signal to the decoder, a predecoding may be performed using a QR decomposition of the channel matrix such that H=QR where Q designates an orthogonal matrix and R is an upper triangular matrix. Given the orthogonality of Q, equation (4) can be rewritten in the following form:
{tilde over (y)}=Q.sup.ty=Rs+Q.sup.t{tilde over (w)}(7),

(65) Where {tilde over (w)} is the equivalent noise having the same properties as w.

(66) The ML decoding problem then amounts to solving the equivalent system given by:
=arg min.sub.s.sub.c.sub.A{tilde over (y)}Rs.sup.2(8),

(67) where designates the constellation.

(68) As a sphere constrained decoder satisfies a spherical region constraint for the search of the closest point, the optimal solution s belongs to the sphere of radius C and satisfies:
=arg min.sub.sA{tilde over (y)}Rs.sup.2C.sup.2(9).

(69) The problem expressed by equation 9 may be solved by considering the parameter =R.sup.1=H.sup.1y and =s, where represents the coordinates of {tilde over (y)} in the lattice .sub.R. Accordingly:
R=R(s)={tilde over (y)}Rs

(70) A sphere constrained decoder searches the closest lattice point to the received point within a sphere centered at a point representing the received symbol or alternatively at another selected point. Each vector (codeword) Hs is represented by a lattice point in a lattice representation. The sphere-constrained decoder outputs any lattice point inside the sphere and as a result the nearest lattice point to the received signal (ML solution) is found by enumerating the lattice points inside the sphere that belong to the used constellation.

(71) The following description of certain applications of the invention to sphere-constrained decoders will be made with reference to a sphere centered on a point representing the received symbol y for illustrative purpose, although it is to be understood that the invention also applies to a sphere centered on another selected point.

(72) Sphere constrained decoders determine a set of lattice points inside the sphere (y, C) centered at the point y representing the received symbol y and having a radius C by converting H into a triangular matrix through the QR decomposition. The sphere constraint according to which a lattice point is to belong to the sphere S (Hs(y, C)) can be expressed according to the inequality (10):
{tilde over (y)}Rs.sup.2C.sup.2(10)

(73) From the previous formulas, the inequality {tilde over (y)}Rs.sup.2C.sup.2 can be rewritten as:
R.sup.2C.sup.2(11)

(74) In Equation (11), R is a nn matrix and is an n-dimensional vector.

(75) The minimization problem (ML solution) min.sub.s A{tilde over (y)}Rs.sup.2C.sup.2 can thus be rewritten:
min.sub.sAR.sup.2C.sup.2(12)

(76) To limit the search region to the sphere of initial radius C, the search interval I.sub.i=[b.sub.inf,i; b.sub.sup,i] is defined for each decoded component s.sub.i, the lower boundary b.sub.inf,i and the upper boundary b.sub.sup,i of the search interval I.sub.i being determined from the initial radius C.

(77) Indeed, the solution to the sphere constraint can be found recursively by scanning the points s in the sphere of radius C according to a branch and bound approach and by selecting the candidate lattice points that satisfy equation (12). To recursively solve equation 12, starting from the bottom layer of matrices involved in the inequality (12), for each real or imaginary component of a symbol of the signal to be decoded, the interval I.sub.i=[b.sub.inf,i; b.sub.sup,i] is used. Specifically, the search interval I.sub.i for each decoded symbol s.sub.i such that b.sub.inf,is.sub.ib.sub.sup,i may be defined by the following boundaries:

(78) $\begin{array}{cc}{b}_{\inf ,i}=.Math.-\sqrt{\frac{T_i}{p_{\mathrm{ii}}}}+S_i.Math.& \left(13.1\right)\\ b_{\sup ,i}=.Math.\sqrt{\frac{T_i}{p_{\mathrm{ii}}}}+S_i.Math.& \left(13.2\right)\end{array}$
Where:

(79) $\begin{array}{cc}{p}_{\mathrm{ii}}=R_{\mathrm{ii}}^2\mathrm{with}i=1,\mathrm{.Math.},n& \left(13.3\right)\\ p_{\mathrm{ij}}=\frac{R_{\mathrm{ij}}}{R_{\mathrm{ii}}}\mathrm{with}j=i+1,\mathrm{.Math.},n& \left(13.4\right)\\ S_i={}_i+\underset{j=1+1}{\overset{n}{.Math.}}{p}_{\mathrm{ij}}{}_j^2& \left(13.5\right)\\ T_i=C^2-\underset{l=i+1}{\overset{n}{.Math.}}{p_{\mathrm{ll}}\left({}_i+\underset{j=l+1}{\overset{n}{.Math.}}{p}_{\mathrm{ij}}{}_j\right)}^2=T_{i-1}-p_{\mathrm{ii}}\left(S_i-s_i\right)& \left(13.6\right)\end{array}$

(80) The number of visited nodes during the decoding process depends then on the interval I.sub.i for each symbol s.sub.i, the boundaries of the search interval depending on the initial sphere radius C.

(81) It should be noted that for a given channel matrix H, the computational decoding complexity of the sphere decoder is given by:

(82) $\begin{array}{cc}O\left(n^2{\left(1+\frac{n-1}{4{\mathrm{dC}}^2}\right)}^{4{\mathrm{dC}}^2}\right)& \left(14\right)\end{array}$

(83) In formula 14, d.sup.1 denotes a lower bound for the eigenvalues of the Gram matrix G=H.sup.tH and C corresponds to the initial sphere radius. This shows that the initial radius greatly impacts the decoding complexity of sphere-constrained decoders.

(84) By setting the initial sphere radius of the sphere C from the linear function (1), which takes as parameter the Euclidean distance between the initial ZF-DFE estimate (or more generally any estimate of the transmitted signal vector. The ZF-DFE solution constituting a suboptimal estimate of the original signal) and the received signal, the search of candidate lattice points is optimized.

(85) Referring now to FIG. 2, a flowchart is presented that depicts a process which may be executed by a sphere decoder, according to certain embodiments.

(86) Prior to the decoding method, in a predecoding step (200), a QR-decomposition of the channel matrix H, as described above, may be performed to provide the Q and R matrices.

(87) In step 201, an initial radius is determined from the linear radius function ( ) of the Euclidean distance d.sub.DFE from the received signal y to the ZF-DFE estimate Hs.sub.DFE.

(88) Let d.sub.DFE denote the Euclidean distance from the received signal to the ZF-DFE estimate s.sub.DFE such that:
d.sub.DFE=yHs.sub.DFE(15)

(89) The initial radius C.sub.prop may then be determined from the parameter C.sub.d.sub.DFE:
C.sub.d.sub.DFE=(d.sub.DFE)(16)

(90) In step 203, the sphere-constrained decoder performs a lattice search to search for candidate lattice points (code words) within a sphere having an initial radius corresponding to the bound parameter determined in step 202, based on a tree search depending on a tree search strategy in order to determine the closest lattice point to the received signal y.

(91) In step 204, each time a candidate lattice point is found, the initial radius may be updated. Step 203 is then iterated for the new radius value set at step 204.

(92) In step 205, the closest vector to the received signal according to the Maximum Likelihood (ML) criterion (ML estimate vector) is determined from the candidate lattice points obtained in step 203.

(93) In one embodiment, the tree search strategy may be based on a depth-first tree search (sphere decoding): the search is performed from the highest dimension of the decoding tree in a descending order to search for lattice points included inside the sphere centered at the received signal and having the initial radius while branches out of the sphere are deleted (i.e. satisfying inequality (10)). This involves that only the nodes having a value that is comprised in the interval I.sub.i=[b.sub.inf,i; b.sub.sup,i] are selected, with b.sub.inf,i and b.sub.sup,i depending on the initial radius, calculated in step 201. The interval I.sub.i is determined for each symbol component (represented by a node value).

(94) Each time a candidate lattice point is found inside the sphere, the radius of the sphere may be updated in step 204 by setting the initial radius to a new value equal to the Euclidean distance between the found lattice point and the received signal in order to reduce the search space of the sphere, if such Euclidean distance is inferior to the radius. When all the lattice points have been searched recursively, the candidate lattice point having the minimum Euclidean distance to the received signal from the candidate lattice points may be selected as the ML estimate vector in step 205.

(95) Alternatively, the tree search strategy may be based on a Best-first strategy as implemented by the SB-stack decoder. The SB-stack decoder uses a tree representation of the ML decoding problem, each path from the root node to a leaf node being a possible transmitted signal: Starting from the root node (from the highest dimension of the tree in a descending order), all or a subset of the child nodes s.sub.n are explored, and for each explored node a metric associated with the node is computed. Only the nodes having a value that satisfies the sphere constraint (according to inequality (10)) are generated and may be stored in a stack. This involves that only the nodes having a value that is comprised in the interval I.sub.i=[b.sub.inf,i; b.sub.sup,i] are visited, where b.sub.inf,i and b.sub.sup,i depend on the initial radius, as calculated in step 201, can be stored in the stack. An interval is determined for each node representing a component of a symbol of the signal to be decoded. The search is continued until finding a leaf node and the optimal path s.sup.(1)=(s.sub.n, s.sub.n-1, . . . , s.sub.1) is returned in step 205 (closest vector to the received signal vector according to ML criterion), without any update of the radius. Particularly, in step 205, a likelihood probability may be further assigned to the bits of at least one symbol of the data signal, taking into account the stored paths and a probabilistic estimation of the data signal (single-carrier and multi-carrier) may be determined taking into account the path(s) stored in the second stack and likelihood probabilities to determine the optimal path.

(96) Referring to FIG. 3, a flowchart depicting the SB stack decoding method according to certain embodiments is shown.

(97) In the SB stack embodiment, the pre-decoding step 200 of FIG. 2 may comprise:

(98) performing a QR decomposition of the channel matrix such that H=QR where Q designates the orthogonal matrix and R designates an upper triangular matrix,

(99) calculating the equivalent system according to equation 7, which provides a triangular lattice representation of the lattice generated by H or equivalently by R,

(100) Calculating the ZF-DFE point: =H.sup.1y

(101) This allows making a tree search to find the point in the tree solution of the minimization problem given by equation (12): min.sub.s AR.sup.2C.sub.prop.sup.2 (12), with =s.

(102) Once the signal has been received, the decoder may implement at least one iteration of the following steps 302 to 315, for a current node of the tree stored in the stack.

(103) The generation of the decoding tree implements at least one iteration of the following steps, for a current node of the tree stored in the stack. The first node of the tree is the root node.

(104) The method initially starts with the root node as the current node. The first current node is therefore the root node (step 301).

(105) The method initially starts by processing the root node as the current node (step 301). Steps 302 to 315 are iterated for each current node selected from the top of the stack to generate the child nodes for which the current node is the parent node. Each iteration is thus associated with a level i of the decoding tree (i=n to 1). The parameter i may be decremented for each new iteration, depending on the top node selected in the stack.

(106) The first iteration of the decoding tree method is implemented to determine the child nodes of the root node at a first level i=n, which provides the ZF-DFE solution. The ZF-DFE solution (or more generally the suboptimal estimation of the original signal) may be determined in a preliminary step before the iterations 302 to 315 of the stack decoding method to find the ML solution.

(107) The subsequent iterations of the decoding tree method are implemented to determine the child nodes of a current node corresponding to the top node in the stack (and to a given level or layer i of the decoding tree). Initially the current node is set as the root node.

(108) Each node of the tree may be associated with a metric f.sup.i(s.sub.i), a path and/or a dimension (or depth). The dimension of a node corresponds to the number of levels between that node and the root node. The metric of a node may correspond to a function of the Euclidean distance between the signals received and the path between the root node and the node considered. In the decoding tree, there exists a single path between the root node and a node being considered. From this path, it is thus possible to determine the corresponding decoded bits or an estimation of the transmitted information sequence transmitted between the root node and the node considered.

(109) Specifically, for the current node being processed, all or a preselected subset of child nodes are determined by projecting on the i-th layer of the matrix R resulting from the QR decomposition, and for each child node (step 302), a constraint defining a condition that is to be satisfied by the child node with respect to the search interval I.sub.i. The search interval I.sub.i=[b.sub.inf,i; b.sub.sup,i] for the level i of the current node (corresponding to a component of the decoded symbol) is determined in step 304 and comprises a lower bound b.sub.inf,i and an upper bound b.sub.sup,i determined from the initial radius according to equations (13.1) and (13.2). This interval thus limits the search region.

(110) Specifically, in steps 305 and 306, it is determined if the considered child node of the current node has a value comprised within the interval I.sub.i. If so, the metric of the node is computed in step 307 and the child node is added in the stack, in step 308, together with its associated metrics. Additional data may be stored in the stack in association with each child node such as the path and/or the dimension of the child node. A child node may be thus taken into consideration only when its value lies in the search interval I.sub.i. Accordingly, all child nodes or a subset of the child nodes having a value comprised in the interval I.sub.i will be stored in the stack. As a result, the paths scanned in the tree correspond to the points of the lattice located inside a sphere having a radius C.sub.prop.

(111) In certain embodiments, the metric f.sup.i(s.sub.i) associated with a child node (s.sub.i) may be computed in step 307 as the weight metrics ((s.sub.j)) of the nodes in the tree comprised in the path from the root node s.sub.n to the current node s.sub.i.

(112) In particular, the metric associated with a reference child node (s.sub.i) at level i (i.sup.th decoded symbol) may be determined as the cumulated weight c(s.sub.i). The cumulated weight c(s.sub.i) is determined from the sum of the weight metrics (s.sub.j) of the nodes in the tree comprised in the path s.sup.(i) from the root node s.sub.n to the node s.sub.i (due to the triangular structure of matrix R, the search starts from the component s.sub.n, where n designates the dimension of the channel matrix).

(113) As the cumulated weight c(s.sub.i) of a node s.sub.i is equal to the sum over all weights for different nodes forming the path s.sup.(i), it represents the metric of the path. A path of depth i in the tree designates the vector of length ni+1 defined by s.sup.(i)=(s.sub.n, s.sub.n-1, . . . , s.sub.i). A node being in depth n is a leaf node.

(114) The weight metric (s.sub.j) of a node at a level j of the tree can be determined as the Euclidean distance between the j.sup.th component of the vector {tilde over (y)} representing the received signal and the vector (s.sub.n . . . s.sub.j) comprising the node values of the tree from the root node s.sub.n to the node s.sub.j at level j according to equation (17):
(s.sub.j)={tilde over (y)}.sub.j.sub.k=j.sup.nR.sub.jks.sub.k|.sup.2(17)

(115) Accordingly, the cumulated weight cw(s.sub.i) for a node s.sub.i may be determined as:
cw(s.sub.i)=.sub.j=i.sup.nw.sub.j(s.sub.j)=.sub.j=i.sup.n|{tilde over (y)}.sub.j.sub.k=j.sup.nR.sub.jks.sub.k|.sup.2(18),

(116) For a leaf node, the cumulated weight cw(s.sub.1) corresponds to the Euclidean distance between the received signal {tilde over (y)} and s.sup.(1), which is equal to {tilde over (y)}R.sub.s.sup.(1).sup.2|{tilde over (y)}R.sub.s.sup.(1)|.sup.2.

(117) In such an embodiment, the ML metric minimization of (8) amounts to a search of the path in the tree having the least cumulated weight.

(118) In an alternative embodiment, the cumulated weight function cw(s.sub.i) may be determined by taking into account a bias parameter b, where b has a real and positive value (b.sup.+). Specifically, the bias parameter b may be deduced from the weight function, such that equation 17 is replaced by the following equation (parameterized weight (s.sub.j) for a node s.sub.i at level i in the tree):
(s.sub.j)={tilde over (y)}.sub.j.sub.k=i.sup.nR.sub.iks.sub.k|.sup.2b.Math.j(19)

(119) Accordingly, in this alternative parameterized approach, the cumulated weight cw(s.sub.i) for a node s.sub.i may be determined as:
cw(s.sub.i)=.sub.j=i.sup.nw.sub.j(s.sub.j)=.sub.j=i.sup.n(|{tilde over (y)}.sub.j.sub.k=j.sup.nR.sub.jks.sub.k|.sup.2)b*i(20)

(120) In particular, the application of a bias b equal to zero (b=0) provides the ML solution.

(121) The value of the bias parameter may be determined arbitrarily or depending on the channel variance .sup.2 as described in Lattice Sequential Decoder for Coded MIMO Channel: Performance and Complexity Analysis. W. Abediseid and Mohamed Oussama Damen. CoRR abs/1101.0339 (2011):

(122) $\begin{array}{cc}b={}^2\log \left(\frac{4}{{}^2}\right)& \left(21\right)\end{array}$

(123) Such parameterized embodiment of the decoding search tree makes it possible to obtain a wide range of decoding performance (thus complexity) by taking into account the bias parameter b in the weight function.

(124) It should be noted that the invention is not limited to the use of sub-optimal decoders 300 to provide an initial estimation of the transmitted signal from the received signal. For example, in certain embodiments of the invention applying the parameterized version of the SB-Stack algorithm (using a bias b), the ZF-DFE estimate can alternatively be determined by setting the bias parameter to a large value (for example higher than 10) in a first iteration of the SB-stack decoding algorithm (iteration of steps 302 to 315), which provides the ZF-DFE solution, and by iterating subsequently the SB-Stack decoding algorithm with a value of the bias set to zero (b=0) to find the ML solution.

(125) The decoding method may be applicable to decode finite or infinite lattices in .sup.n, the value of each node in the tree corresponding to the component of a symbol belonging to a constellation having a predefined range between a minimum threshold C.sub.min and a maximum threshold C.sub.max. In embodiments where finite lattices are decoded (finite constellations), such as with QAM modulation, information symbols s.sub.i are selected from a finite alphabet and their real and imaginary parts, which correspond to the decoded symbols over the tree, belong to the finite interval I=[C.sub.min, C.sub.max]. For example, in embodiments using a q-QAM modulation, the symbols s.sub.i belong to the interval I.sub.c=[1, 2, 3, . . . , {square root over (q)}1] and the nodes in the search tree corresponding to the used constellation symbols belong to the infinite set I=[0, 1, 2, 3, . . . , {square root over (q)}1] where C.sub.min=0 and C.sub.max={square root over (q)}1.

(126) In such embodiments, in order to guarantee that the estimated symbols belong to the considered constellation, in steps 305 and 306, the child nodes of the i.sup.th level may be alternatively selected within an interval I.sub.i corresponding to the intersection between the constellation interval [C.sub.min, C.sub.max] corresponding to the constellation and the intervals I.sub.i:
I.sub.i=[max(C.sub.min,b.sub.inf.sub.i),(C.sub.max,b.sub.sup.sub.i)].

(127) When all the child nodes of the current node have been processed, in step 309, the current node is deleted from the stack.

(128) In step 310, the stack may be reordered by an increasing order of the metrics f.sup.k(s.sub.k) so that the node s.sub.q in the stack having the lowest metric is stored in the top of the stack.

(129) In step 311, the top node of the stack s.sub.q is selected as the current node in order to generate its child nodes.

(130) In step 312, it is determined if the selected node is a leaf node. If the selected node is a leaf node (i.e. not having no child node), the method is terminated in step 315.

(131) Otherwise, in step 314, the selected node is set as the current node and steps 302 to 315 may be repeated for the newly selected node (which represents the node having the lowest metric in the stack) to generate the child nodes, at a next level j of the decoding tree with j being comprised between n1 to 1. The next processed level j depends on the top node selected in the stack.

(132) Each iteration of steps 302 to 315 (corresponding to the processing of a current node) thus provides a path between the root node and a new leaf node stored in the stack.

(133) When a leaf is reached in the first iteration, the algorithm generates the ZF-DFE solution and may use it to update the initial radius C.sub.prop of the sphere to be considered to find the ML solution according to equation: min.sub.s A{tilde over (y)}Rs.sup.2C.sub.prop.sup.2, in step 204. The radius selection method according to the embodiments of the invention guarantees that at least one point is found inside the sphere (which corresponds at worst to the ZF-DFE point) from the initial radius value.

(134) In the SB-stack decoding embodiment, the closest vector to the vector representing the received signal may be estimated in step 205 of FIG. 2 by taking into account the node information stored in the stack, and in particular the path(s) stored in the stack when such information is available. For example, if a binary estimation (hard decision) is applied, the construction of the tree implements a single iteration of steps 302 to 315 enabling a single path to be determined corresponding to a hard estimation of the transmitted data signal. Alternatively, if a probabilistic estimation (soft decision) is applied, the decoding method may deliver soft-output information in the form of Log-Likelihood Ratio (LLR) values. In this case, several iterations of steps 302 to 315 may be performed. Each iteration provides a different path from the root node to leaf nodes (representing candidate lattice point). These different paths (representing candidate lattice points) may then be stored in an auxiliary stack together with their paths. A probabilistic estimation of the information signal can be determined based on these paths.

(135) Referring to FIG. 4, a flowchart depicting additional details of the initial radius determination step (step 201 of FIG. 2) is shown, according to a first embodiment. In this embodiment, the initial radius of the sphere C.sub.prop may be determined as the minimum between:

(136) A first quantity (referred to hereinafter as intermediate radius) determined from at least one of a first radius C.sub.1, which is a function of the noise variance .sup.2, and a second radius C.sub.2, which is a function of the minimum of the diagonal elements of the Gram matrix diag(H.sup.tH) of the channel matrix; and

(137) A second quantity C.sub.d.sub.DFE represented by the linear function f( ) depending on the ZF-DFE estimate.

(138) Specifically, in step 400, a first auxiliary radius C.sub.1 depending on the noise variance .sup.2 may be determined:
C.sub.1=2n.sup.2(22)

(139) In step 402, a second auxiliary radius C.sub.2 depending on the Gram matrix may be determined as:
C.sub.2=min(diag(H.sup.tH))(23)

(140) In step 404, a resulting radius may be determined as the minimum between the first auxiliary radius and the second auxiliary radius:
C.sub.0=min(C.sub.1,C.sub.2)(24)

(141) In step 406, the initial radius C.sub.prop of the sphere is determined as the minimum between C.sub.0 and C.sub.d.sub.DFE=(d.sub.DFE):
C.sub.prop=min(C.sub.0,C.sub.d.sub.DFE)(25)

(142) In certain embodiments, the radius function ( ) which takes d.sub.DFE as parameter may be a linear function of the type (d.sub.DFE)=a.sub.1.Math.d.sub.DFE+a.sub.2, where a.sub.1 designates the slope coefficient and a.sub.2 designates the intercept coefficient. The radius function ( ) may be for example a purely multiplicative function with a null intercept coefficient (a.sub.2=0) or a purely additive function with a slope coefficient equal to 1 (a.sub.1=1).

(143) In particular, at least one of the radius function coefficients a.sub.1 and a.sub.2 may depend on a predetermined parameter (referred to hereinafter as radius function parameter). It should be noted that the radius function parameter may be chosen arbitrarily. Alternatively, the parameter may be selected so that its value satisfies a constraint with respect to a lower threshold .sub.min such as:
.sub.min(26)

(144) In certain embodiments, the lower threshold .sub.min may depend on d.sub.DFE, C.sub.1, and/or C.sub.2.

(145) In one embodiment, the slope coefficient a.sub.1 of the radius function may be equal to

(146) $\frac{1}{\sqrt{}}.$
Specifically, it has been demonstrated that the following multiplicative function (a.sub.2=0) may improve the total complexity:

(147) $\begin{array}{cc}f\left(d_{\mathrm{DFE}}\right)=\frac{d_{\mathrm{DFE}}}{\sqrt{}}& \left(27\right)\end{array}$

(148) In equation (27), (radius function parameter) represents a real-value strictly positive parameter (.sup.+).

(149) It should be noted that when is equal to 1 (=1), the radius C.sub.d.sub.DFE=(d.sub.DFE) coincides with the Euclidean distance from the received signal to the ZF-DFE solution.

(150) FIG. 5 illustrates the probability of having C.sub.d.sub.DFEC.sub.0 in a 22 MIMO communication system n.sub.r=n.sub.t=2 comprising a Sphere Decoder using spatial multiplexing and 16-QAM modulations for different values of the parameter as used in equation (27), and over 10.sup.5 channel realizations.

(151) FIG. 5 shows that for low and moderate SNR values, the probability that the radius C.sub.d.sub.DFE be inferior or equal to C.sub.0 is larger than 50%. Accordingly, considering C.sub.d.sub.DFE as the initial radius C.sub.prop in such cases rather than C.sub.0 is sufficient to find the ML solution. However, it can be seen from FIG. 5 that in high SNR regime, the radius C.sub.0 has a smaller value than C.sub.d.sub.DFE with a very high probability (almost 99%).

(152) In embodiments where the slope coefficient a of the radius function is equal to

(153) 0$\frac{1}{\sqrt{}},$
the lower threshold .sub.min of the radius function parameter may depends on d.sub.DFE, C.sub.1.sup.2, and/or C.sub.2.sup.2. Specifically, the lower bound .sub.min in embodiments where the slope coefficient a.sub.1 of the radius function is equal to

(154) $\frac{1}{\sqrt{}}$
may be defined as:

(155) $\begin{array}{cc}{}_{\min }=\max \left(\frac{d_{\mathrm{DFE}}^2}{4n^2{}^4},d_{\mathrm{DFE}}^2{\min }^2\left(\mathrm{diag}\left(H^{t}H\right)\right)\right)& \left(28\right)\end{array}$

(156) In another embodiment, the linear radius function ( ) may comprise an intercept coefficient a.sub.2 equal to .

(157) In particular, the radius function ( ) used to define C.sub.d.sub.DFE=(d.sub.DFE) may be an additive function (slope coefficient a.sub.1=1) such as the following additive positive-value function for which the intercept coefficient a.sub.2=
(d.sub.DFE)=d.sub.DFE(29)

(158) In embodiments where the intercept coefficient a.sub.2 is equal to , the lower threshold .sub.min of the radius function parameter may depend on d.sub.DFEC.sub.1 and/or d.sub.DFEC.sub.2. For example, the lower bound .sub.min may be defined as:
.sub.min=max(d.sub.DFE2n.sup.2,d.sub.DFEmin(diag(H.sup.tH))(30)

(159) FIG. 6 illustrates the total complexity in terms of number of multiplications obtained for different values of the parameter in a 22 MIMO communication system (n.sub.t=n.sub.r=2) using spatial multiplexing and 16-QAM modulation, and comprising a sphere decoder where the radius function ( ) is a multiplicative function according to equation (27) having a linear coefficient

(160) $\frac{1}{\sqrt{}}$

(161) FIG. 6 shows that initial radius determined from C.sub.d.sub.DFE=(d.sub.DFE) where is defined according to equation (27) provides a reduced complexity particularly in the low and moderate SNR range compared to an initial radius equal to C.sub.0. It should be noted that larger values of , result in smaller values of C.sub.0, thereby allowing a lower complexity while guaranteeing no decoding failure (i.e. using this radius, the algorithm is able to find the ML solution inside the underlying sphere).

(162) FIG. 7 illustrates the total complexity in terms of number of multiplications obtained for different values of the parameter in a 22 MIMO communication system (n.sub.t=n.sub.r=2) using spatial multiplexing and 16-QAM modulation, and comprising a sphere decoder where the radius function ( ) is an additive function according to equation (29). The results obtained are similar to FIG. 6. It should be noted that the initial radius C.sub.d.sub.DFE allows to find the ML solution while reducing the total decoding complexity compared to the case where the radius C.sub.0 is considered.

(163) When applied to the Sphere Decoder, it has been determined that the decoding method provides a complexity gain of at least 12% over a Sphere decoder implementing a conventional radius selection approach.

(164) It should be noted that the examples of FIGS. 6 and 7 are simplified examples provided to illustrate the total complexity which can be obtained with the present invention and are not intended to limit the scope of the invention.

(165) The invention is not limited to sphere-constrained decoders and may apply more generally to other types of tree-search based decoding algorithms, such as sequential decoders. FIG. 8 is a general flowchart depicting the processing of a current node implemented by such tree-search based algorithms, according to certain embodiments of the invention. The previously processed node and the next node of the tree to be processed depend on the specific tree search strategy implemented by the tree-search based algorithm. For the current node being processed (block 800), the child nodes or a subset of the child nodes of the current nodes are generated (step 802). For each child node, a search interval I.sub.Metric-i (step 803) and a metric (step 804) are then determined. In step 803, at least one of the lower and the upper bounds of the search interval are determined from the bound parameter which is derived from the linear function (1). In step 804, the metric may be determined as described in relation with block 307 of FIG. 3. In step 806, the child node is selected as a component of a candidate lattice point only if the metric of the child node is comprised in the search interval defined from the bound parameter.

(166) Depending on the decoding algorithm, each node of the decoding tree may generate a limited set of child nodes in step 802. For example, in a zigzag decoding approach as described in patent application EP No. 14306517.5, the decoding algorithm uses a stack similarly to the SB-stack decoder but does not search the candidate lattice points in a sphere. Instead, at each level, the zigzag decoding algorithm generates at most three child nodes comprising a reference child node of the current node determined from the vector representing the received data signal, a first neighbor child node determined by subtracting a positive integer parameter from the value of the reference node, and a second neighbor child node determined by adding the positive integer parameter to the value of the reference child node (step 802). Child nodes are selected in step 806 among the three child nodes. The selected child node can then be stored in a stack similarly to the SB-stack decoder together with their respective metric, the stack being then reordered by increasing order of the node metrics. The top node of the stack, thus obtained, is selected as the new current node to iterate the recursive search operation.

(167) FIG. 9 represents an exemplary architecture of a space/time decoder 30 of the receiver 3 in a SB-stack embodiment of the invention. As shown, the space/time decoder 30 may include the following elements, which are linked together by a data and address bus 64:

(168) a microprocessor 61 (or CPU), which is, for example, a digital signal processor (DSP);

(169) a non-volatile memory 62 (or ROM, read-only memory);

(170) a random access memory RAM 63;

(171) an interface 65 for receiving input signals coming from the time/frequency converter;

(172) an interface 66 for transmitting decoded data to the demodulator 31.

(173) The non-volatile ROM memory 62 may include for example:

(174) a register Prog 620;

(175) the biais parameter b in parameterized embodiments 621;

(176) the constellation bounds C.sub.min and C.sub.max 622;

(177) the radius function parameter 623.

(178) The algorithms for implementing the method according to this embodiment of the invention can be stored in the program 620. The CPU processor 41 may be configured to download the program 620 to the RAM memory and runs the corresponding instructions. Specifically, the CPU comprises instructions for calculating the initial estimate of a transmitted symbol vector carried by the received signal vector, and calculate the bound parameter from the linear function (1) of the initial estimate of the transmitted symbol vector. The CPU further comprises instructions for: determining estimated symbols representative of the transmitted symbols carried by the received signal, the estimated symbols being determined from the set of candidate lattice points, each component of a candidate lattice point being searched in a search interval having at least one search interval bound computed from the bound parameter; and determining the estimated symbols from the closest lattice point to the received signal vector among the candidate lattice points.

(179) The RAM memory 63 may include:

(180) in a register Prog 630, the program run by the microprocessor 61 and downloaded in an active mode of the space/time decoder 30;

(181) input data in a register 631;

(182) data related to the nodes in a register 632;

(183) likelihood probabilities or LLR in a register 634;

(184) The data stored in the register 632 may include, for a node of the decoding tree, metric parameters associated with this node (path from the root to said node, and/or the depth in the tree).

(185) More generally, the decoding techniques described herein may be implemented by various means. For example, these techniques may be implemented in hardware, software, or a combination thereof. For a hardware implementation, the processing elements of decoder can be implemented for example according to a hardware-only configuration (for example, in one or more FPGA, ASIC or VLSI integrated circuits with the corresponding memory) or according to a configuration using both VLSI and DSP.

(186) While embodiments of the invention have been illustrated by a description of various examples, and while these embodiments have been described in considerable detail, it is not the intent of the applicant to restrict or in any way limit the scope of the appended claims to such detail. Particularly, although the invention has been described mainly in relation with a sphere decoding algorithm or a SB-stack decoding algorithm, and a Zigzag Stack decoding algorithm, the invention also applies to other types of tree-search based decoding algorithms, such as the M-decoding algorithm.

(187) Further, while certain embodiments of the invention have been described in relation to a wireless single-user MIMO system, it should be noted that the invention is not limited to such application. The invention may be integrated in any receiver device operating in any linear communication system characterized by a lattice representation of the channel output. The communication system may be wired, wireless or optical fiber-based accommodating single or multiple users, using single or multiple antennas, and single or multi-carrier communication techniques. For example, the present invention may be integrated in a receiver device implemented in a wireless distributed MIMO system. Distributed MIMO may be used for example in cellular uplink communications applied in 3G, 4G and LTE standards. Cooperative communications applied for example in ad-hoc networks (wireless sensor networks, machine-to-machine communications, internet of things . . . ) are also examples of distributed MIMO systems. In addition to wireless networks, the present invention may be integrated in optical receiver devices implemented in optical fiber-based communication systems such as Polarization Division Multiplexing-OFDM (PDM-OFDM) systems.

(188) Further, the invention is not limited to communication devices and may be integrated in signal processing devices such as electronic filters of finite impulse response (FIR) used in audio applications like audio crossovers and audio mastering. Accordingly, certain embodiments of the invention may be used to determine an estimate of an input sequence, given an output sequence of a FIR filter of order M.

(189) Additional advantages and modifications will readily appear to those skilled in the art. The invention in its broader aspects is therefore not limited to the specific details, representative methods, and illustrative examples shown and described. Accordingly, departures may be made from such details without departing from the spirit or scope of applicant's general inventive concept, such as different definitions of the slope and intercept coefficients a.sub.1 and a.sub.2 of the radius function ( ).

(190) Further, the various embodiments of the invention are not limited to particular types of decoding, and apply both to hard and soft decoding.