Method for slicing K-best detection in multiple-input multiple-output wireless communications system

Abstract

In a MIMO detector, a slicing list detection scheme employs a complex plane to represent symbols in an alphabet, in which all decision regions are bounded by either vertical lines or horizontal lines. A K-best scheme accesses the complex plane and an offline-generated lookup table to detect elements of a received vector. At each level, the system prunes all but the K-best candidates from each surviving node through the slicing list detector.

Claims

1. A method of detecting a MIMO signal transmitted from N antennas, the MIMO signal representing a transmitted vector of N elements, each of the N elements being transmitted by a different one of the N antennas and each of the N elements including a selected symbol from an alphabet ofM symbols, the MIMO signal represented as a received vector of N.sub.R elements, in which each of the N.sub.R elements corresponds to a different receiver antenna of an array of receiver antennas, the method comprising the steps of: (a) defining a finite number of decision regions within a complex plane , each decision region defined to encompass a different combination of K symbols in the alphabet, in which each decision region is bounded by threshold lines consisting of horizontal threshold lines that are parallel to the real axis and vertical threshold lines that are parallel to the imaginary axis, and in which K is a selected number taken from a set of integers; (b) modifying the received vector to be represented as a complex point p having a real component and an imaginary component; (c) nulling a reconstructed transmitted vector and then performing a loop of steps including: (i) mapping the complex point p onto the complex plane; (ii) then comparing the real component of the complex point p to the vertical threshold lines and imaginary component of complex point p to the horizontal threshold lines to determine which decision region encompasses the complex point p; (iii) then accessing a lookup table, in which the lookup table has been compiled offline, to determine which K symbols associated with the decision region that encompasses the complex point p are closest to the complex point p and adding the closest K symbols to a candidate set of detected symbol vectors; (iv) then subtracting the detected symbol from the complex decision point and returning to the mapping step; and (v) then when N detected symbols have been detected in the reconstructed transmitted vector, exiting the loop; and (d) after exiting the loop, returning the reconstructed transmitted vector.

2. The method of claim 1, further comprising the steps of: (a) choosing the horizontal threshold lines so that each of the horizontal threshold lines intersects the imaginary axis at integers ranging from {square root over (M)} to {square root over (M)}, and (b) choosing the vertical threshold lines so that each of the vertical threshold lines intersects the real axis at integers ranging from {square root over (M)} to {square root over (M)}.

3. The method of claim 2, employed in quadrature modulated (QAM) communications employing the alphabet of M symbols in which each symbol includes a real component and an imaginary component in which the real components and imaginary components consist of odd integers from {square root over (M)}+1 to {square root over (M)}1, wherein the step of defining a finite number of decision regions comprises the step of dividing the complex plane into a total of 4 ({square root over (M)}+1).sup.2 sub-regions, in which 4M of the sub-regions are defined to be square in shape are grouped together in a center portion of the complex plane, while 4(1 +2{square root over (M)}) of the sub-regions are placed at edges and the corners of the center portion and are of a semi-infinite rectangular in shape.

4. The method of claim 1, further comprising the step of selecting boundaries for each selected decision region so that each of the K symbols associated with the selected decision region is one of K best selections for a complex point p mapped into the selected decision region.

5. The method of claim 4, where compilation of the lookup table comprises the steps of: (a) associating each decision region with a list .sub.i associated with an i-th sub-region i; and (b) choosing the i-th sub-region i so as to minimize a following mean-squared-error (MSE) metric of the difference in Euclidean distances as follows: ${}_i=\arg \underset{}{\min }E\left[\frac{1}{K}\underset{k=1}{\overset{K}{.Math.}}{\left\{{\hat{d}}_k\left(p\right)-d_k\left(p\right)\right\}}^2|p{}_i\right],i=1,\mathrm{.Math.},4{\left(\sqrt{M}+1\right)}^2,$ wherein {circumflex over (d)}.sub.1(p){circumflex over (d)}.sub.1(p) . . . d.sub.k(p) are the sorted distances from a point pC to each of the K symbols in a list , and d.sub.1(p)d.sub.2(p) . . . d.sub.K(p) are the sorted distances from the point p to each of the closest K symbols in the minimum-distance list, in which the point p is a complex random variable that is defined by p=x+n, where x ( including all symbols in the alphabet) is a uniformly distributed complex symbol, and n is zero-mean circularly-symmetric complex Gaussian noise.

6. The method of claim 1, wherein the step of subtracting the detected symbol from the complex point p comprises the steps of: (a) choosing xA.sup.N to minimize $\begin{array}{c}{J}_N\left(x\right)=||y-\mathrm{Hx}{||}^2\\ =||\hat{y}-\mathrm{Rx}{||}^2=\underset{l=1}{\overset{N}{.Math.}}|{\hat{y}}_l-\underset{j=1}{\overset{l}{.Math.}}{R}_{\mathrm{lj}}{x}_j{|}^2,\end{array}$ in which =Q.sup.Hy , where Q is a unitary matrix in the QR decomposition H=QR of a channel matrix, and where R is a lower-triangular matrix with positive real diagonal elements; (b) interpreting J.sub.N(x) as being a sum of N branch metrics in a path through an M-ary tree with N layers, whose M.sup.N leaf nodes represent all possibilities for x.sup.N, so that each -th layer of the tree has nodes, one for each possible combination of {x.sub.1, . . . , x.sub.l}; (c) assigning to a branch from a node at an (1)-th layer to a child at the -th layer a metric that is rewritten as: B=R.sub.ll.sup.2, where ${\hat{y}}_l={\hat{y}}_l-\underset{j=1}{\overset{l-1}{.Math.}}{R}_{\mathrm{lj}}{x}_j$ represents an observation for the -th layer after contributions from previous layer symbols {x.sub.1, . . . , .sub.1} have been subtracted.

7. A signal processing circuit that is programmed to execute the method recited in claim 1.

8. A detecting method for detecting a MIMO signal transmitted from N antennas, the MIMO signal representing a transmitted vector of N elements, each of the N elements being transmitted by a different one of the N antennas and each of the N elements including a selected symbol from an alphabet of M symbols, the MIMO signal represented as a received vector of N.sub.R elements, in which each of the N.sub.R elements corresponds to a different receiver antenna of an array of receiver antennas, the method comprising the steps of: (a) defining a finite number of decision regions within a complex plane, each decision region defined to encompass a different combination of K symbols in the alphabet, in which each decision region is bounded by threshold lines consisting of horizontal threshold lines that are parallel to the real axis and vertical threshold lines that are parallel to the imaginary axis, and in which K is a selected number taken from a set of integers, wherein the horizontal threshold lines are chosen so that each of the horizontal threshold lines intersects the imaginary axis at integers ranging from {square root over (M)} to {square root over (M)} and wherein the vertical threshold lines are chosen so that each of the vertical threshold lines intersects the real axis at integers ranging from {square root over (M)} to {square root over (M)}; (b) wherein each symbol includes a real component and an imaginary component in which the real components and imaginary components consist of odd integers from {square root over (M)}+1 to {square root over (M)}1, wherein the step of defining a finite number of decision regions comprises the steps of dividing a complex plane into a total of 4 ({square root over (M)}+1).sup.2 sub-regions, in which 4M of the sub-regions are defined to be square in shape are grouped together in a center portion of the complex plane, while 4(1 +2{square root over (M)}) of the sub-regions are placed at edges and the corners of the center portion and are of a semi-infinite rectangular in shape and selecting boundaries for each selected decision region so that each of the K symbols associated with the selected decision region is one of K best selections for a complex point p mapped into the selected decision region; (c) modifying the received vector to be represented as a complex point p having a real component and an imaginary component; (d) nulling a reconstructed transmitted vector and then performing a loop of steps including: (i) mapping the complex point p onto the complex plane; (ii) then comparing the real component of the complex point p to the vertical threshold lines and imaginary component of complex point p to the horizontal threshold lines to determine which decision region encompasses the complex point p; (iii) then accessing a lookup table, in which the lookup table has been compiled offline, to determine which K symbols associated with the decision region that encompasses the complex point p are closest to the complex point p and adding the closest K symbols to the reconstructed transmitted vector; (iv) then subtracting the detected symbol from the complex decision point and returning to the mapping step; and (v) then when N detected symbols have been detected in the reconstructed transmitted vector, exiting the loop; and (e) after exiting the loop, returning the reconstructed transmitted vector.

9. The detecting method of claim 8, wherein compilation of the lookup table comprises the steps of: (a) associating each decision region with a list .sub.i associated with an i-th sub-region i; and (b) choosing the i-th sub-region i so as to minimize a following mean-squared-error (MSE) metric of the difference in Euclidean distances as follows: ${}_i=\arg \underset{}{\min }E\left[\frac{1}{K}\underset{k=1}{\overset{K}{.Math.}}{\left\{{\hat{d}}_k\left(p\right)-d_k\left(p\right)\right\}}^2|p{}_i\right],i=1,\mathrm{.Math.},4{\left(\sqrt{M}+1\right)}^2,$ wherein {circumflex over (d)}.sub.1(p){circumflex over (d)}.sub.1(p) . . . d.sub.k(p) are the sorted distances from a point pC to each of the K symbols in a list , and d.sub.1(p)d.sub.2(p) . . . d.sub.K(p) are the sorted distances from the point p to each of the closest K symbols in the minimum-distance list, in which the point p is a complex random variable that is defined by p=x+n, where x ( including all symbols in the alphabet) is a uniformly distributed complex symbol, and n is zero-mean circularly-symmetric complex Gaussian noise.

10. The detecting method of claim 8, wherein the step of subtracting the detected symbol from the complex point p comprises the steps of: (a) choosing xA.sup.N to minimize $\begin{array}{c}{J}_N\left(x\right)=||y-\mathrm{Hx}{||}^2\\ =||\hat{y}-\mathrm{Rx}{||}^2=\underset{l=1}{\overset{N}{.Math.}}|{\hat{y}}_l-\underset{j=1}{\overset{l}{.Math.}}{R}_{\mathrm{lj}}{x}_j{|}^2,\end{array}$ in which =Q.sup.Hy , where Q is a unitary matrix in the QR decomposition H=QR of a channel matrix, and where R is a lower-triangular matrix with positive real diagonal elements; (b) interpreting J.sub.N(x) as being a sum of N branch metrics in a path through an M-ary tree with N layers, whose M.sup.N leaf nodes represent all possibilities for x.sup.N, so that each -th layer of the tree has nodes, one for each possible combination of {x.sub.1, . . . , }; (c) assigning to a branch from a node at an (1)-th layer to a child at the -th layer a metric that is rewritten as: BM.sub.l=|R.sub.ll.sup.2, where ${\hat{y}}_l={\hat{y}}_l-\underset{j=1}{\overset{l-1}{.Math.}}{R}_{\mathrm{lj}}{x}_j$ represents an observation for the -th layer after contributions from previous layer symbols {x1, . . . , .sub.1} have been subtracted.

11. A signal processing circuit that is programmed to execute the method recited in claim 8.

12. A receiver for receiving a MIMO signal transmitted from N antennas, the MIMO signal representing a transmitted vector of N elements, each of the N elements being transmitted by a different one of the N antennas and each of the N elements including a selected symbol from an alphabet of M symbols, the MIMO signal represented as a received vector of N.sub.R elements, in which each of the N.sub.R elements corresponds to a different receiver antenna of an array of receiver antennas, the receiver comprising: (a) an array of N.sub.R antennas; (b) a memory on which is stored a lookup table that has been compiled offline and that relates values of the received vector to symbols from the alphabet; (c) a signal processing circuit, responsive to the antennas and in data communication with the memory, that is programmed to execute steps, including: (i) define a finite number of decision regions within a complex plane, each decision region defined to encompass a different combination of K symbols in the alphabet, in which each decision region is bounded by threshold lines consisting of horizontal threshold lines that are parallel to the real axis and vertical threshold lines that are parallel to the imaginary axis, and in which K is a selected number taken from a set of integers; (ii) modify the received vector to be represented as a complex point p having a real component and an imaginary component; (iii) null a reconstructed transmitted vector and then execute a loop of steps including: (1) map the complex point p onto the complex plane; (2) then compare the real component of the complex point p to the vertical threshold lines and imaginary component of complex point p to the horizontal threshold lines to determine which decision region encompasses the complex point p; (3) then access the lookup table to determine which K symbols associated with the decision region that encompasses the complex point p are closest to the complex point p and adding the closest one of the K symbols to the reconstructed symbol vector; (4) then subtract the detected symbol from the complex decision point and returning to the mapping step; and (5) then when N detected symbols have been detected in the reconstructed transmitted vector, exit the loop; and (iv) after exiting the loop, return the reconstructed transmitted vector.

13. The receiver of claim 12, wherein the signal processing circuit is further programmed to execute steps including: (a) choose the horizontal threshold lines so that each of the horizontal threshold lines intersects the imaginary axis at integers ranging from {square root over (M)} to {square root over (M)}; and (b) choose the vertical threshold lines so that each of the vertical threshold lines intersects the real axis at integers ranging from {square root over (M)} to {square root over (M)}.

14. The receiver of claim 13, employing quadrature modulated (QAM) communications employing the alphabet of M symbols in which each symbol includes a real component and an imaginary component in which the real components and imaginary components consist of odd integers from {square root over (M)}+1 to {square root over (M)}1, wherein the finite number of decision regions are defined by dividing the complex plane into a total of 4 ({square root over (M)}+1).sup.2 sub-regions, in which 4M of the sub-regions are defined to be square in shape are grouped together in a center portion of the complex plane, while 4(1+2{square root over (M)}) of the sub-regions are placed at edges and the corners of the center portion and are of a semi-infinite rectangular in shape.

15. The receiver of claim 12, wherein the signal processing circuit is further programmed to select boundaries for each selected decision region so that each of the K symbols associated with the selected decision region is one of K best selections for a complex point p mapped into the selected decision region.

16. The receiver of claim 15, wherein the signal processing circuit is further programmed to: (a) associate each decision region with a list .sub.i associated with an i-th sub-region i; and (b) choose the i-th sub-region i so as to minimize a following mean-squared-error (MSE) metric of the difference in Euclidean distances as follows: ${}_i=\arg \underset{}{\min }E\left[\frac{1}{K}\underset{k=1}{\overset{K}{.Math.}}{\left\{{\hat{d}}_k\left(p\right)-d_k\left(p\right)\right\}}^2|p{}_i\right],i=1,\mathrm{.Math.},4{\left(\sqrt{M}+1\right)}^2,$ wherein {circumflex over (d)}.sub.1(p){circumflex over (d)}.sub.1(p) . . . {circumflex over (d)}.sub.k(p) are the sorted distances from a point pC to each of the K symbols in a list , and d.sub.1 (p)d.sub.2 (p) . . . d.sub.K (p) are the sorted distances from the point p to each of the closest K symbols in the minimum-distance list, in which the point p is a complex random variable that is defined by p=x+n, where x ( including all symbols in the alphabet) is a uniformly distributed complex symbol, and n is zero-mean circularly-symmetric complex Gaussian noise.

17. The receiver of claim 12, wherein the signal processing circuit subtracts the detected symbol from the complex point p by executing the steps of: (a) choose xA.sup.N to minimize $\begin{array}{c}{J}_N\left(x\right)=||y-\mathrm{Hx}{||}^2\\ =||\hat{y}-\mathrm{Rx}{||}^2=\underset{l=1}{\overset{N}{.Math.}}|{\hat{y}}_l-\underset{j=1}{\overset{l}{.Math.}}{R}_{\mathrm{lj}}{x}_j{|}^2,\end{array}$ in which =Q.sup.Hy , where Q is a unitary matrix in the QR decomposition H=QR of a channel matrix, and where R is a lower-triangular matrix with positive real diagonal elements; (b) interpret J.sub.N(x) as being a sum of N branch metrics in a path through an M-ary tree with N layers, whose M.sup.N leaf nodes represent all possibilities for x.sup.N, so that each -th layer of the tree has nodes, one for each possible combination of {x.sub.1, . . . , }; (c) assign to a branch from a node at an (1)-th layer to a child at the -th layer a metric that is rewritten as: B=|R.sub.ll.sup.2 where ${\hat{y}}_l={\hat{y}}_l-\underset{j=1}{\overset{l-1}{.Math.}}{R}_{\mathrm{lj}}{x}_j$ represents an observation for the -th layer after contributions from previous layer symbols {x.sub.1, . . . , .sub.1} have been subtracted.

18. The receiver of claim 12, disposed in a cellular telephone.

Description

BRIEF DESCRIPTION OF THE FIGURES OF THE DRAWINGS

(1) FIG. 1 is a schematic diagram of one example of a prior art MIMO communications system.

(2) FIGS. 2A-2F are graphical representations of a complex plane used in a prior art minimum-distance list detector.

(3) FIG. 3 is a flow chart demonstrating one represented embodiment of a method for detecting values from a MIMO signal.

(4) FIGS. 4A-4B are graphical representations of a complex plane employed in one representative embodiment of the invention, in which the complex plane is divided into slicing decision regions with corresponding decision lists.

(5) FIG. 5A-5F are graphical representations of a complex plane employed in one representative embodiment of the invention, in which the complex plane is divided into slicing decision regions.

(6) FIG. 6 is a graph comparing bit error rate versus E.sub.b/N.sub.0 in simulations of MIMO detectors for uncoded systems, including one representative 44 MIMO embodiment of the present invention.

(7) FIG. 7 is a graph comparing bit error rate versus E.sub.b/N.sub.0 in simulations of MIMO detectors for coded systems, including one representative 88 MIMO embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

(8) A preferred embodiment of the invention is now described in detail. Referring to the drawings, like numbers indicate like parts throughout the views. Unless otherwise specifically indicated in the disclosure that follows, the drawings are not necessarily drawn to scale. As used in the description herein and throughout the claims, the following terms take the meanings explicitly associated herein, unless the context clearly dictates otherwise: the meaning of a, an, and the includes plural reference, the meaning of in includes in and on.

(9) U.S. Pat. No. 6,636,568, issued to Kaous, discloses a MIMO system and is incorporated herein by reference for the purpose of disclosing such systems. U.S. Pat. No. 7,720,169, issued to Reuven et al., discloses multiple-input multiple-output (MIMO) detectors and a MIMO detector employing a K-best detection scheme, and is incorporated by reference herein for the purpose of disclosing such schemes.

(10) As shown in FIG. 3, one embodiment of a MIMO detector performs the following operations: Define a finite number of decision regions in a complex plane, each encompassing a different combination of K symbols from the alphabet, each bounded by threshold lines, including horizontal threshold lines parallel to real axis and vertical threshold lines parallel to imaginary axis 112; Modify received vector to be represented as a complex point p having a real component and an imaginary component 114; Null reconstructed transmitted vector 116 and then execute loop 120. In loop 120 the following steps are executed: Mapping the complex point p onto complex plane 122; Comparing real component to vertical threshold lines and imaginary component to horizontal threshold lines to determine which decision region encompasses the complex point p 124; Access lookup table to determine which K symbols are closest to the complex point p and add the closest K symbols to reconstructed transmitted vector 126; Subtracting detected symbol from the complex decision point 128; and Determining if N detected symbols have been detected in the reconstructed transmitted vector 130. Once loop 120 has been exited, the reconstructed transmitted vector is returned 132 for further processing.

(11) One representative embodiment of the invention includes a modification of the K-best detector for the case of QAM alphabets that significantly reduces complexity when K<M, without compromising performance. The present detector is based on a scalar list detector for M-ary QAM that uses a slicing operation to approximate the minimum-distance list detector, a modification that provides two benefits: it reduces the number of metric computations for each node from M to K, and it reduces the number of candidates to be sorted at each layer from KM to K.sup.2. Simulation results show that the present slicing K-best scheme provides almost identical performance to that of the conventional K-best scheme, but with significantly reduced complexity. Since the slicing list detection is performed at each node in every layer of the detection process, the complexity reduction is especially significant for a MIMO system with a large number of antennas N and with a large alphabet size M.

(12) The Slicing List Detector

(13) One embodiment is a suboptimal list detector with significantly reduced complexity called the slicing list detector. Like the minimum-distance list detector, the slicing list detector has a finite number of decision regions, and every point in a given region gets mapped to the same decision list. Unlike the minimum-distance detector, however, the invention imposes the constraint that the thresholds that divide adjacent decision regions be either horizontal or vertical lines. This simple constraint enables us to determine in which decision region a given complex point lies by a simple operation commonly known as slicing: by separately comparing the real and imaginary parts of the given point with a set of fixed threshold values. By constructing a lookup table that maps each decision region to the corresponding decision list, the slicing list detector can be implemented with extremely low complexity.

(14) There are two primary degrees of freedom in the design of a slicing list detector: (i) choosing the slicing thresholds which defines the decision regions, and (ii) choosing the decision list that corresponds to each decision region. These two choices are examined in the following two subsections.

(15) 1) Slicing Thresholds: Given that the real and imaginary parts of the M-QAM symbols consist of the odd integers from {square root over (M)}+1 to {square root over (M)}1, the threshold values for both the real and imaginary parts can be placed at all integers from {square root over (M)}+ to {square root over (M)}. This choice leads to dividing the complex plane into a total of 4 ({square root over (M)}+1).sup.2 sub-regions, 4M of which in the middle are square in shape, while 4(1+2{square root over (M)}) at the edges and the corners are semi-infinite rectangular in shape.

(16) 2) Decision Lists: Once the thresholds are defined, it remains to identify the decision list of K alphabet symbols with each corresponding decision region. The list .sub.i associated with the i-th sub-region can be chosen so as to minimize the following mean-squared-error (MSE) metric of the difference in Euclidean distances:

(17) $\begin{array}{cc}{}_i=\arg \underset{}{\min }E\left[\frac{1}{K}\underset{k=1}{\overset{K}{.Math.}}{\left\{{\hat{d}}_k\left(p\right)-d_k\left(p\right)\right\}}^2|p{}_i\right],i=1,\mathrm{.Math.},4{\left(\sqrt{M}+1\right)}^2,& \left(5\right)\end{array}$
where {circumflex over (d)}.sub.1(p){circumflex over (d)}.sub.1(p) . . . {circumflex over (d)}.sub.k(p) are the sorted distances from the point p to each of the K symbols in the list , and d.sub.1(p)d.sub.2(p) . . . d.sub.K(p) are the sorted distances from the point p to each of the closest K symbols in the minimum-distance list. Here, the point p is a complex random variable that is defined by p=x+n, where x is a uniformly distributed complex symbol, and n is zero-mean circularly-symmetric complex Gaussian noise. Strictly speaking, the decision lists found through (5) are a function of SNR. Nevertheless, in practice the invention has achieved good performance by obtaining a single list at a single nominal SNR value, then using that list for all encountered SNR values. This is possible because when a change in SNR causes the decision list for a complex point p to change, the change is at the end of the list (corresponding to the symbol furthest from p), where one distant symbol with a low probability of being transmitted is replaced by another distant symbol with a similarly low probability of being transmitted.

(18) The decision lists of the slicing list detector for 16-QAM with K=4 and K=12 are illustrated in FIGS. 4A-4B, where the thresholds are shown as solid black lines. In the figures, the decision lists associated with the decision regions are obtained by the criterion given in (5) at SNR=0 dB. The decision lists for the remaining decision regions follow from symmetry considerations.

(19) The decision regions of the slicing list detector for 16-QAM with different values of K (assuming SNR=0 dB) are shown in FIGS. 5A-5F. Comparing these figures to the corresponding prior art figures shown in FIGS. 2A-2F, it can be sees how the slicing list detector approximates the decision regions of the minimum-distance list detector, subject to its constraint that the boundaries be horizontal and vertical lines.

(20) The performance of a scalar list detector is quantified by its list error probability (LEP), which is defined as the probability that the transmitted symbol is not included in the decision list. In a comparison between an LEP of the slicing list detector and the minimum-distance list detector in a Rayleigh fading channel for the case of 16-QAM, the LEP of the slicing list detector closely matches that of the minimum-distance list detector. It should be noted that the list error probability closely matches with that of the minimum-distance list detector in a Rayleigh fading channel for 16-QAM with K {4, 8, 12, 14}.

(21) Also, in the performance of an alternative design strategy for a list detector, the set of K candidates are determined by first quantizing the point p to the closest symbol, then obtaining the list of neighboring K1 symbols from the closest symbol. Since the distance between adjacent thresholds is fixed to the minimum distance between symbols, it suffers from performance degradation. Furthermore, the discrete Gaussian distribution of the point p is not accounted for in mapping the decision lists. Accordingly, FIG. 4 shows that the closest-symbol list detector suffers an SNR loss of between 0.5 dB and 1.8 dB, depending on the value of K.

(22) The Slicing K-Best MIMO Detector

(23) The prune-as-you-go strategy discussed above can be built on the concept of scalar list detection, since the process of determining the K best of the M children from a given survivor node is equivalent to applying the interference-reduced channel observation for the node to the minimum-distance list detector. This leads to the slicing K -best detector, presented in the pseudocode of Algorithm 2. Unlike Algorithm 1, which extends each survivor to all M children, Algorithm 2 uses a list detector to extend each survivor to only K of its children. If the minimum-distance list detector in line 7, then Algorithm 2 is used, it would produce exactly the same decisions as Algorithm 1. Instead, the present detector employs the slicing list detector, such that SlicingList( ) in line 7 maps its input argument {tilde over (y)}.sub.l/R.sub.ll to the decision list A determined above, where =K . At the first layer of the tree there are ||=K candidates, while at all remaining layers there are ||=K.sup.2 candidates. The previous path metric .sub.1(s) in line 10 remains constant for all children from the same node, so adding the term does not alter the choice of K best children from each node. The K best survivors from K.sup.2 candidates are determined in line 15 while taking into account K different values of the previous path metrics, so the ordering within the K children from each node is not required. Thus, a simple slicing operation that yields an unsorted list of K best children from each node suffices in line 7.

(24) TABLE-US-00002 Algorithm 2 The Proposed Slicing K-Best MIMO Detector 1: = 2: J.sub.0() = 0 3: for l = 1 to N do 4: = 5:for s do 6:{tilde over (y)}.sub.l = {tilde over (y)}.sub.l .sub.j=1.sup.l1 R.sub.ljs.sub.j 7:L = SlicingList(y.sub.l/R.sub.ll) 8:for x.sub.l L do 9:c = [ s | x.sub.l ] 10:J.sub.l(c) = J.sub.l1(s) + |{tilde over (y)}.sub.l R.sub.llx.sub.l|.sup.2 11: .sub.c 12:end for 13:end for 14:if l < N then 15: = prune( ), keeping only the K best 16:else 17:{circumflex over (x)}= Best( ) 18:end if 19: end for

(25) There are two immediate benefits from the fact that the slicing list detector in Algorithm 2 extends a survivor node only to K of its children, as opposed to all M children in Algorithm 1: (1) The number of metrics computations in each layer is reduced by K/M; and (2) The number of metrics to be sorted to prune to K survivors in each layer is reduced by K/M.

(26) It is known that sorting techniques have an average complexity of O(nlogn) or larger, where n is the length of a sorting list. So, by reducing the size of a sorting list from KM to K.sup.2, the sorting complexity is reduced by a factor of less than K/M. It is also noteworthy that there is no sorting and selection process required at the first layer in the present slicing K-best detector, since the K survivors from the first layer are solely determined by a simple slicing operation, and the ordering within the K survivors is again not required. The overall effect is a net reduction in complexity by a factor of less than K/M.

(27) In a practical implementation of one embodiment of the invention, the computation required for obtaining the lookup table for slicing list detector can be simplified by making the complex random variable p to be uniformly distributed, rather than Gaussian distributed.

(28) The following is an example of a Matlab script for generating the slicing list:

(29) TABLE-US-00003 function Kbest_list(M,K) abc = qammod(0:M1,M); x_start = min(real(abc))20.5; x_end = max(real(abc))+20.5; x = x_start:1:x_end; length_x = length(x); ix_mod = zeros(K,length_x2); for ii=1:length_x for jj=1:length_x z = x(ii) + j*x(jj); dist = abs(zabc); [dist_sort,ix] = sort(dist); ix_mod(:,(ii1)*length_x+jj) = qammod(ix(1:K)1,M).; end end for r=1:length_x Kbest_list_temp(:,1:length_x,r) = ix_mod(:,length_x*(r1)+1:length_x*r); end Kbest_list = Kbest_list_temp(:,2:length_x,2:length_x); filename = sprintf(qam%d_%dbest.mat, M, K); save(filename, Kbest_list); end

(30) As shown in FIGS. 6 and 7, a simulation results for the performance and complexity of several MIMO detection schemes, including the conventional K-best scheme and the slicing K-best scheme of the present invention. The uncoded BER versus E.sub.b/N.sub.0, or SNR per bit of the K-best detector and the slicing K-best detector for 16-QAM with K=12 and 64-QAM and K=16 are shown. Before the QR decomposition, the columns of the channel matrix H are permuted based on the decreasing order of signal-to-interference-plus-noise ratio (SINR). It can be seen that the BER curve for the slicing K-best detector is nearly indistinguishable from the BER curve for a conventional K-best detector.

(31) The black dashed curves indicate the theoretical BER curves of the matched-filter bound (MFB) based on a single-input multiple-output (SIMO) channel. Comparing the BER curves of K-best and slicing K-best schemes to the MFB suggests that both schemes achieve almost full receiver diversity gain up to a certain SNR, even with K<M. This indicates that the slicing K-best schemes can be a good match for a coded system, as it performs relatively well with low complexity at lower SNR. At higher SNR, the diversity gain gets lower for both schemes.

(32) For the sake of simplicity, the embodiment disclosed above restricts the elements of the transmit vector in a one-to-one fashion to the transmit antennas: the first vector element is the symbol transmitted from the first antenna, the second element is the symbol transmitted from the second antenna, etc. However, the invention can apply to a broader class of problems. In one alternate embodiment, N_s<=N symbols can be sent from N transmit antennas, without restricting each symbol to be sent from each antenna. For example, one embodiment might send three symbols from four transmit antennas as follows: construct a 3-by-1 vector of info symbols, hit it by a 4-by-3 precoding or beamforming matrix to produce a 4-by-1 vector, and then transmit each element of this 4-by-1 vector from each of 4 transmit antennas. Changing the transmitter in this way does not change the receiver problem. The above-disclosed solution would apply equally well to a situation like this.

(33) The above described embodiments, while including the preferred embodiment and the best mode of the invention known to the inventor at the time of filing, are given as illustrative examples only. It will be readily appreciated that many deviations may be made from the specific embodiments disclosed in this specification without departing from the spirit and scope of the invention. Accordingly, the scope of the invention is to be determined by the claims below rather than being limited to the specifically described embodiments above.