Method to Detect Data Transmitted by Multiple Antennas

[0001] The present invention relates to a system and multistage signal detection method for large multiple-input-output communication systems. Instant discloser deals with a detection technique to determine the data transmitted.

[0002] Wireless communication systems using 2 or 3 antennas at the transmitter and one antenna at the receiver have been defined in the current standards. Systems using 4 to 8 antennas at the transmitter and 4 to 8 antennas at the receiver are being considered for standardization. Also, the maximum spectral efficiency reported to have been achieved in practical/prototype systems so far is often less than 10 bps/Hz.

[0003] Multiple-input multiple-output (MIMO) techniques have become popular in realizing transmit diversity and high data rates through the use of multiple transmit antennas in wireless communication terminals, references [1]-[6]. We consider large MIMO systems having tens of transmit and receive antennas in each communication terminal, which are of interest due to the high spectral efficiencies (of the order of tens to hundreds of bps/Hz) possible in such systems. The key challenges in realizing such large MIMO systems include low-complexity detection, channel estimation,

[0004] RF/IF technologies and communication terminal size to accommodate large number of antennas. There can be several large MIMO applications where lacing of large number of antennas need not be a major issue. An example of such an scenario is to provide high-speed backbone connectivity between base stations using large MIMO links, where large number of antennas can be placed at the backbone base stations.

[0005] The state-of-the art MIMO systems do not achieve the full potential of MIMO communications. Exploitation of large number of communication dimensions (e.g., large number of space dimensions in the case of V-BLAST multi-antenna systems, and large number of space and time dimensions in the case of Space-Time Coded multi-antenna systems) is essential in order to fully reap the MIMO potential. The issue with using large number of antennas is the very high detection complexities involved. For example, optimum ML detection of MIMO signals require complexities exponential in number of antennas, which are prohibitive even for tens of antennas. Even other detectors in the literature which attempt to achieve near-ML performance have complexities cubic or more in number of antennas, which are still prohibitive for tens and hundreds of antennas.

[0006] This disclosure addresses the issue of low-complexity detection in large MIMO systems. Recent approaches to low-complexity multi-user detection and MIMO detection involve application of techniques from belief propagation as in reference [7], neural networks in references [8], [9], [10], Markov Chain Monte-Carlo methods in references [11], [12], and probabilistic data association in references [13], [14], to name a few. Detectors based on these techniques have been shown to achieve an average per-bit complexity that is linear in number of users, while achieving near-ML performance in large multi-user CDMA system settings as in reference [8], [9], [14]. These powerful techniques are increasingly being adopted in MIMO detection. Recently, in reference [9], [10], the present disclosure presents a powerful Hopfield neural network based likelihood ascent search (LAS) algorithm for low-complexity large MIMO detection, where we showed that, in large MIMO systems having hundreds of antennas, the LAS detector achieves i) an encoded bit error rate (BER) performance which is almost the same as the AWGN-only SISO (i.e., no fading) performance given by Q(√{square root over (SNR)}); this excellent performance is achieved with an average per-symbol complexity of just O(NtNr), and ii) a coded BER performance close to within 4.7 dB of the theoretical MIMO capacity using hard decision outputs from the LAS algorithm as input to the turbo decoder.

[0007] A limitation with the LAS algorithm disclosed in reference [9], [10] is that it achieves near-maximum likelihood (ML) performance only with hundreds of antennas. Placing hundreds of antennas can be difficult in communication terminals that have space constraints.

• [0008] [1] A. Paulraj, R. Nabar, and D. Gore, Introduction to Space-Time Wireless Communications, Cambridge University Press, 2003.
• [0009] [2]H. Jafarkhani, Space-Time Coding: Theory and Practice, Cambridge University Press, 2005.
• [0010] [3] D. Tse and P. Viswanath, Fundamentals of Wireless Communication, Cambridge University Press, 2005.
• [0011] [4] G. J. Foschini and M. J. Gans, “On limits of wireless communications in a fading environment when using multiple antennas,” Wireless Pers. Commun., vol. 6, pp. 311-335, March 1998.
• [0012] [5] I. E. Telatar, “Capacity of multi-antenna Gaussian channels,” European Trans. Telecommun., vol. 10, no. 6, pp. 585-595, November 1999.
• [0013] [6] G. J. Foschini, “Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas,” Bell Labs Tech. J1., vol. 1, pp. 41 59, August 1996.
• [0014] [7] X. Yang, Y. Xiong, and F. Wang, “An adaptive MIMO system based on unified belief propagation detection,” Proc. IEEE ICC'2007, Glasgow, June 2007.
• [0015] [8] Y. Sun, “A family of linear complexity likelihood ascent search detectors for CDMA multiuser detection,” Proc. IEEE 6th Intl. Symp. on Spread Spectrum Tech. & App., September 2000.
• [0016] [9] K. Vishnu Vardhan, Saif K. Mohammed, A. Chockalingam, and B. Sundar Rajan, “A low-complexity detector for large MIMO systems and multicarrier CDMA systems,” to appear in IEEE JSAC Spl. Iss. on Multiuser Detection for Advanced Communication Systems and Networks, May 2008.
• [0017] [10] Saif K. Mohammed, K. Vishnu Vardhan, A. Chockalingam, and B. Sundar Rajan, “Large MIMO Systems: A low-complexity detector at high spectral efficiencies,” to appear in Proc. IEEE ICC'2008, Beijing, China, May 2008.
• [0018] [11]H. D. Thu, B. Farhang-Boroujeny, and R.-R. Chen, “On the performance of sphere decoding and Markov chain Monte Carlo detection methods,” IEEE Signal Proc. Letters, vol. 12, no. 10, pp. 669-672, October 2005.
• [0019] [12] B. Farhang-Boroujeny, H. Zhu, and Z. Shi, “Markov chain Monte Carlo algorithms for CDMA and MIMO communication systems,” IEEE Trans. on Sig. Proc., vol. 54, no. 5, pp. 1896-1908, May 2006.
• [0020] [13] D. Pham, K. Pattipati, P. Willett, and J. Luo, “A generalized probabilistic data association detector for multiple antenna systems,” IEEE Commun. Lett., vol. 8, no. 4, pp. 205207, April 2004.
• [0021] [14] P. H. Tan and L. K. Rasmussen, “Asymptotically optimal nonlinear MMSE multiuser detection based on multivariate Gaussian approximation,” IEEE Trans. Commun., vol. 54, pp. 1427-1438, August 2006.
• [0022] [15] B. A. Sethuraman, B. S. Rajan, and V. Shashidhar, “Full-diversity, high-rate space-time block codes from division algebras,” IEEE Trans. Inform. Theory, vol. 49, no. 10, pp. 2596-2616, October 2003.
• [0023] [16] B. Hassibi and B. Hochwald, “High rate codes that are linear in space and time,” IEEE Trans. Inform. Theory, vol. 48, pp. 1804-1824, July 2002.
• [0024] [17] S. M. Alamouti, “A simple transmit diversity technique for wireless communications,” IEEE J1. Sel. Areas in Commun., vol. 16, no. 8, pp. 1451-1458, October 1998.
• [0025] [18] V. Tarokh, N. Seshadri, and A. R. Calderbank, “Space-time codes for high data rate wireless communications: Performance criterion and code construction,” IEEE Trans. Inform. Theory, vol. 44, no. 2, pp. 744-765, March 1998.
• [0026] [19] V. Tarokh, H. Jafarkhani, and A. R. Calderbank, “Space-time block codes from orthogonal designs,” IEEE Trans. Inform. Theory, vol. 45, no. 5, pp. 1456-1467, July 1999.
• [0027] [20] D. Gesbert, H. Bolcskei, D. A. Gore. A. J. Paulraj, “Outdoor MIMO wireless channels: Models and performance prediction.” IEEE Transion Commun., vol. 50, pp. 1926-1934, December 2002.
• [0028] [21] B. Hassibi and B. M. Hochwald, “How much training is needed in multiple-antenna wireless links?” IEEE Trans. Inform. Theory, vol. 49, no. 4, pp. 951-963, April 2003.
• [0029] [22] P. Stoica and G. Ganesan, “Space-time block codes: trained, blind and semi-blind detection,” Proc. IEEE ICASSP'2002, vol. 2, pp. 1609-1612, 2002.
• [0030] [23] A. Zaki, Saif K. Mohammed, A. Chockalingam, and B. S. Rajan, “A training-based iterative detection/channel estimation scheme for large non-orthogonal STBC MIMO systems,” accepted in IEEE ICC'2009, Dresden, June 2009.

[0031] The primary object of the present invention is to provide a system and a multistage signal detection method to jointly detect the data symbols transmitted from multiple transmit antennas in a communication terminal and received using multiple receive antennas in another communication terminal.

[0032] Yet another object of the present invention is to provide novel multistage multiple-symbol update search method that forms a key component of said multistage signal detection method.

[0033] Still another object of the present invention is to provide a novel method to generate soft decision outputs from the multistage signal detection method.

[0034] Accordingly, the present invention provides for a method to detect data transmitted by multiple antennas, said method comprising acts of: selecting a starting data block wherein the starting data block is either a random data block or an output data block from known detectors, changing each symbol of the starting data block one symbol at a time to identify a data block which has minimum euclidean distance from the starting data block as detected data block, changing two symbol of the detected data block at a time to identify a data block which has minimum euclidean distance from the starting data block as second data block, assigning the second data block as the starting data block and repeating above two steps, if the minimum euclidean distance of second data block is better than that of the detected data block, and determining the detected data block as the data transmitted.

[0058] The present disclose is related to a method to detect data transmitted by multiple antennas, said method comprising acts of:

• • [0059] a) selecting a starting data block wherein the starting data block is either a random data block or an output data block from known detectors,
  • [0060] b) changing each symbol of the starting data block one symbol at a time to identify a data block which has minimum euclidean distance from the starting data block as detected data block,
  • [0061] c) changing two symbol of the detected data block at a time to identify a data block which has minimum euclidean distance from the starting data block as second data block,
  • [0062] d) assigning the second data block as the starting data block and repeating said steps ‘b’ and ‘c’, if the minimum euclidean distance of second data block is better than that of the detected data block, and
  • [0063] e) determining the detected data block as the data transmitted.

[0064] In one embodiment of the present invention changing three symbols of the detected data block at a time to identify a data block which has minimum euclidean distance from the starting data block as third data block.

[0065] In one embodiment of the present invention assigning the third data block as the starting data block and repeating said steps ‘b’ to ‘e’, if the minimum euclidean distance of the third data block is better than that of the detected data block and determining the detected data block as the data transmitted.

[0066] In one embodiment of the present invention defining a set of indices of symbols to be checked for possible flip in the steps ‘b’, ‘c’ and in claim 2.

[0067] In one embodiment of the present invention the method provides for generating soft decision outputs for individual bits to be fed as input to turbo decoder. In one embodiment of the present invention providing a pilot block prior to the data block for channel estimation.

[0068] In one embodiment of the present invention the channel estimation determines channel gain to detect the starting data block.

[0069] In one embodiment of the present invention re-estimating the channel gain using the detected data block.

[0070] In one embodiment of the present invention the cannel gain re-estimation is for a predetermined number of iterations.

[0071] In one embodiment of the present invention the method uses brute-force or approximate method to compute cost difference.

[0072] In one embodiment of the present invention the method comprises data transmissions using higher order modulation format selected from a group comprising M-array Quadrature Amplitude Modulation (M-QAM) and M-array Pulse Amplitude Modulation (M-PAM).

[0073] In one embodiment of the present invention the method detects data symbols transmitted from the multiple transmit antennas using MIMO technique selected from a group comprising Space-Time Block Coding (STBC) and V-BLAST.

[0074] In one embodiment of the present invention the known detector is selected from a group comprising of matched filter, zero-forcing filter and Minimum Mean-Squared Error (MMSE) filter.

[0075] In one embodiment of the present invention the method provides for detection in multi-user OFDM/OFDMA and MIMO-OFDM systems with multiple subcarriers.

[0076] In one embodiment of the present invention the method provides for detection in Ultra-wide band (UWB) systems or impulse radio systems with multiple users and multiple channel taps.

[0077] In one embodiment of the present invention the method provides for detection in underwater acoustic communications with multiple nodes deployed to sense and send information.

[0078] In one embodiment of the present invention the method detects data symbols transmitted from the multiple transmit antennas wherein number of transmit antennas is less than number of receiving antennas.

[0079] The present system also discloses a MIMO system using method as described above.

[0080] The multistage LAS (MLAS) detector we propose in this disclosure overcomes the limitation of references [9], [10] by achieving near-ML performance even with tens of antennas1 and that too at low complexity. This is made possible by adopting a multiple-symbol updates based multiple search strategy which incurs a small increase in complexity but achieves near-ML performance even with tens of antennas. Further present M-LAS work in this disclosure differs from the references [9], [10] in two key aspects, namely, i) while the LAS algorithm operates on single-symbol updates based search, in the present M-LAS algorithm we devise a low-complexity, multi-symbol updates based multiple search strategy that results in improved performance compared to that of LAS in the tens of antennas regime, while incurring only a small increase in complexity, and ii) in addition, instant discloser presents a method to generate soft decision M-LAS outputs to be fed as input to the turbo decoder; soft decision outputs generation for LAS is not available in references [9], [10].

[0081] In terms of performance, the proposed M-LAS detector achieves an uncoded BER performance which is very close to the AWGN-only SISO performance (within about 1 dB) even with tens of antennas, whereas the LAS needed hundreds of antennas to achieve such nearness to AWGN-only SISO performance. This performance advantage of M-LAS over LAS in the regime of tens of antennas has interesting and significant practical implications, since tens of antennas can be easily placed in moderately sized communication terminals (e.g., laptops, set top boxes) which can enable large MIMO systems to be viable in practice. With a rate-¾ outer turbo code and 4-QAM, the proposed M-LAS detector with soft decision outputs is shown to perform close to within about 4.5 dB and 4 dB of the theoretical MIMO capacity with 64 and 128 antennas at spectral efficiencies of 96 bps/Hz and 192 bps/Hz, respectively. With the proposed soft decision outputs, M-LAS/LAS with hundreds of antennas can perform closer to capacity by an extra 1.5 dB compared to the nearness results reported in reference [10]. For example, in a 600×600 V-BLAST system with rate-⅓ turbo code and BPSK, at a spectral efficiency of 200 bps/Hz, the M-LAS/LAS with the proposed soft decision method performs close to within 3.2 dB of the theoretical capacity. This is by far the best nearness to capacity result reported with a practical low complexity detector in a large MIMO system with such large number of antennas.

[0082] In addition, the proposed M-LAS algorithm is successfully adopted for the low complexity decoding of high-rate, non-orthogonal space-time block codes (STBC) from Division Algebras (DA) as in reference [15], which, because of their full-rate attribute, can achieve high spectral efficiencies with less number of antennas. We present interesting uncoded and coded BER performance of n×n STBCs from DA in reference [15] for n=4, 8, and 16 with M-LAS decoding. Quite interestingly, an uncoded BER performance very close to that of AWGN-only SISO performance (within 0.5 dB) is achieved with a 16×16 STBC with 4-QAM and Nt=Nr=16. This is a significant result because with STBCs from DA, the M-LAS is able to achieve AWGN-only SISO performance with just 16 antennas, whereas a similar performance was achieved only using 64 antennas in V-BLAST. This is because of the transmit diversity and coding gains possible with the full-rate STBC approach compared to the VBLAST approach. Further, with an outer turbo code, the M-LAS is shown to perform close to within about 1 to 3 dB of the theoretical capacity, which again is a remarkable result considering that practical low-complexity decoding of such large size non-orthogonal STBCs with such nearness to capacity performance has not been reported in the literature so far. This distinctly establishes the superiority of the proposed M-LAS algorithm in terms of both low complexity and nearness to capacity performance. Given that 4 antenna systems are already defined in the current wireless standards like IEEE 802.11n and IEEE 802.16e, the proposed M-LAS algorithm has good potential for practical application.

[0083] Large MIMO systems having tens to hundreds of transmit and receive antennas in a communication terminal is the area of this invention. The key advantage of large MIMO systems is their potential to deliver high data rates at high spectral efficiencies (of the order of tens to hundreds of bps/Hz) that can enable several interesting high data rate wireless applications. The key technical issues involved in large MIMO systems are i) low-complexity MIMO detection, ii) channel estimation, and iii) RF and antenna technologies that include physical placement of large number of antennas in communication terminals. This invention addresses and provides an efficient solution to the issue of low-complexity MIMO detection in large MIMO systems. A block schematic of a MIMO system with multiple transmit and multiple receive antennas is shown in FIG. 13. The present invention is concerned with the MIMO detector block in FIG. 12.

[0084] Known MIMO detectors in the literature, including sphere decoder and several of its variants, can achieve near-maximum likelihood (ML) performance, but at the cost of high complexity (cubic complexity or more in number of antennas). Other well known detectors including ZF (zero forcing), MMSE (minimum mean square error), and ZF/SIC (ZF with successive interference cancellation) detectors are attractive from a complexity view point (quadratic or cubic complexity), but achieve relatively poor performance (non-ML performance). The complexity limitation in known ML-achieving detectors prohibits the use of large number of antennas, and hence they can achieve only limited spectral efficiencies typically less than 10 bps/Hz.

[0085] A unique feature of the present invention is that it presents a multistage MIMO detection algorithm that achieves near-ML performance (i.e., performs very close to the theoretical capacity) for tens to hundreds of antennas with low detection complexity, and this can enable the practical realization of high spectral efficiencies of the order of tens to hundreds of bps/Hz. The present invention differs from the prior art in that it achieves near-ML performance for tens to hundreds of antennas with low detection complexity. The non-obviousness of the present invention comes from the successful adoption of multiple symbol updates in the search procedure that incurs only a small increase in complexity compared to single symbol updates based search. In addition, the proposed method to generate soft decision outputs from the search algorithm in the invention is non-obvious.

[0086] Consider a V-BLAST system with N_t transmit antennas and N_r receive antennas, N_t≦N_r, where N_t symbols are transmitted from N_t transmit antennas simultaneously. Let ∈X_c∈C^NtX1 be the symbol vector transmitted. Each element of x_c is an M-PAM or M-QAM symbol. M-PAM symbols take discrete values from {A_m, m=1, 2, . . . , M}, where Am=(2m−1−M), and M-QAM is nothing but two PAMs in quadrature. Let H_c∈C^Nr×Nt be the channel gain matrix, such that the (p, q)th entry h_p,q is the complex channel gain from the qth transmit antenna to the pth receive antenna. Assuming rich scattering, we model the entries of H_c as i.i.d CN(0, 1). Let yc∈C^NtX1 and n_c∈C^NtX1 denote the received signal vector and the noise vector, respectively, at the receiver, where the entries of n_c are modeled as i.i.d CN (0, σ²). The received signal vector can then be written as

y_c=H_cx_c+n_c.  (1)

[0087] Let y_c, H_c, x_c, and n_c be decomposed into real and imaginary parts as follows:

y_c=y_I+jy_Q, x_c=x_I+jx_Q, n_c=n_I+jn_Q, H_c=H_I+jH_Q.  (2)

[0088] Further, we define H_r∈R^2Nr×2Nt, yr∈R^2Nr×1, X_r∈R^2Nt×1, and n_r∈R^2Nr×1 as

$\begin{array}{cc}H_r=\left(\begin{array}{cc}{H}_I& -H_Q\\ H_Q& H_I\end{array}\right),y_r={\left[\begin{array}{cc}{y}_I^T& y_Q^T\end{array}\right]}^T,x_r={\left[\begin{array}{cc}{x}_I^T& x_Q^T\end{array}\right]}^T,n_r={\left[\begin{array}{cc}{n}_I^T& n_Q^T\end{array}\right]}^T.& \left(3\right)\end{array}$

[0089] Now, (1) can be written as

y_r=H_rx_r+n_r.  (4)

Henceforth, we shall work with the real-valued system in (4). For notational simplicity, we drop subscripts r in (4) and write

y=Hx+n.  (5)

where H=H_r∈R^2Nr×2Nt, y=y_r∈R^2Nr×1, x=x_r∈R^2Nt×1 and n=n_r∈R^2Nr×1. With the above real-valued system model, the real-part of the original complex data symbols will be mapped to [x₁, . . . , x N_t] and the imaginary-part of these symbols will be mapped to [x_Nt+1, . . . , x2_Nt]. For M-PAM, [x_Nt+1, . . . , x2_Nt] will be zeros since M-PAM symbols take only real values. In the case of M-QAM, [x₁, . . . , x N_t] can be viewed to be from an underlying M-PAM signal set and so is [x_Nt+1, . . . , x2_Nt]. Let A_i denote the M-PAM signal set from which x_i takes values, i=N_t+1, . . . , 2N_t. For example, for 4-PAM, A_i={−3, −1, 1, 3} for i=1, 2, . . . , N_t and A_i={0} for i=N_t+1, . . . , 2N_t. Similarly, for 4-QAM, after transforming the system into an equivalent real-valued system, A_i={1, −1} for i=1, 2, . . . , N_t. Now, define a 2N_t dimensional signal space S to be the Cartesian product of A1 to A_2Nt. For ML detection, the solution is given by

$\begin{array}{cc}\begin{array}{c}{d}_{\mathrm{ML}}=\underset{d\epsilon S}{\arg \min }{y-\mathrm{Hd}}^2\\ =\underset{d\epsilon S}{\arg \min }d^TH^T\mathrm{Hd}-2y^T\mathrm{Hd}.\end{array}& \left(6\right)\end{array}$

whose complexity is exponential in N_t. We present a low-complexity, near-ML performance achieving detector, termed as multistage likelihood ascent search (M-LAS) detector, in the following section.

[0090] The proposed M-LAS algorithm essentially consists of a sequence of likelihood-ascent search stages, where the likelihood increases monotonically with every search stage. Each search stage consists of several iterations, where updating one symbol per iteration such that the likelihood monotonically increases from one iteration to the next until a local minima is reached. (Local minima is the minimum euclidean distance, i.e. distance between two signal points is the energy is the difference between the two signal points) Upon reaching this local minima, a 2-symbol and/or a 3-symbol update is tried in order to further increase the likelihood. If this likelihood increase happens, then initiate the next search stage starting from this new point. The algorithm terminates at the stage from where further likelihood increase does not happen.

[0091] The M-LAS algorithm starts with an initial solution d^(o), given by d^(o)=By, where B is the initial solution filter, which can be a matched filter (MF) or zero-forcing (ZF) filter or MMSE filter. The index m in d^(m) denotes the iteration number in a given search stage. The ML cost function after the k^th iteration in a given search stage is given by

C^(k)=d^(k)TH^THd^(k)−2y^THd^(k).  (7)

[0092] Each search stage would involve a sequence of 1-symbol updates followed by a 2 and/or a 3 symbol update.

[0093] Let us assume that we update the pth symbol in the (k+1) th iteration; p can take value from 1, . . . N_t for M-PAM and 1, . . . 2N_t for M-QAM. The update rule can be written as

d^(k+1)=d^(k)+λ_p^(k)c_p.  (8)

where ep denotes the unit vector with its pth entry only as one, and all other entries as zero. Also, for any iteration k, d^(k) should belong to the space S, and therefore λ_p^(k) can take only certain integer values. For example, in case of 4-PAM or 16-QAM (both have the same signal set Ap={−3, −1, 1, 3}), λ_p^(k) can take values only from {−6, −4, −2, 0, 2, 4, 6}. Using (7) and (8), and defining a matrix G as

GH^TH.  (9)

we can write the cost difference ΔC_p^k+1C^(k+1)−C^(k) as

ΔC_p^k+1=λ_p^(k)2(G)_p,p−2λ_p^(k)z_p^(k),

where h_p is the pth column of H, z^(k)=H^T (y−Hd^(k), z_p^(k) is the pth entry of the z^(k) vector, and (G)_p,p is the (p, p)th entry of the G matrix. Also, let us define a_p and l_p^(k) as

a_p=(G)_p,p, l_p^(k)=|λ_p^(k)|.  (10)

[0094] With the above variables defined, we can rewrite (10) as

ΔC_p^k+1=l_p^(k)2a_p−2l_p^(k)|z_p^(k)|sgn(λ_p^(k))sgn(z_p^(k)).  (11)

where sgn(.) denotes the signum function. For the ML cost function to reduce from the kth to the (k+1)th iteration, the cost difference should be negative. Using this fact and that ap and l_p^(k) are non-negative quantities, we can conclude from (11) that the sign of λ_p^(k) must satisfy

sgn(λ_p^(k))=sgn(z_p^(k)).  (12)

[0095] Using (12) in (11), the ML cost difference can be rewritten as

(l_p^(k))ΔC_p^k+1=l_p^(k)2a_p−2l_p^(k)|z_p^(k)|.  (13)

[0096] For F(l_p^(k)) to be non-positive, the necessary and sufficient condition from (13) is that

$\begin{array}{cc}{l}_p^{\left(k\right)}<\frac{2z_p^{\left(k\right)}}{a_p}.& \left(14\right)\end{array}$

[0097] However, we can find the value of l_p^(k) which satisfies (14) and at the same time gives the largest descent in the ML cost function from the kth to the (k+1)th iteration (when symbol p is updated). Also, l_p^(k) constrained to take only certain integer values, and therefore the brute-force way to get optimum l_p^(k) is to evaluate F(l_p^(k)) at all possible values of l_p^(k). This would become computationally expensive as the constellation size M increases. However, for the case of 1-symbol update, we could obtain a closed-form expression for the optimum l_p^(k) that minimizes F(l_p^(k)), which is given by

$\begin{array}{cc}{l}_{p.\mathrm{opt}}^{\left(k\right)}=2\lfloor \frac{z_p^{\left(k\right)}}{2a_p}\rfloor ,& \left(15\right)\end{array}$

where └.┐ denotes the rounding operation. If the pth symbol in d^(k), i.e., d_p^(k), were indeed updated, then the new value of the symbol would be given by

{tilde over (d)}_p^(k+1)=d_p^(k)+l_p^(k)sgn(z_p^(k)).  (16)

[0098] However, {tilde over (d)}_p^(k+1) can take values only in the set Ap, and therefore we need to check for the possibility of {tilde over (d)}_p^(k+1) being greater than (M−1) or less than −(M−1). If {tilde over (d)}_p^(k+1)>(M−1), then l_p^(k) adjusted so that the new value of {tilde over (d)}_p^(k+1) with the adjusted value of l_p^(k) (using (16)) is (M−1). Similarly, if {tilde over (d)}_p^(k+1)<−(M−1), then l_p^(k) is adjusted so that the new value of {tilde over (d)}_p^(k+1) is −(M−1). That is, if {tilde over (d)}_p^(k+1)>(M−1), the adjustment equation is

l_p^(k)=l_p^(k)−sgn(z_p^(k))({tilde over (d)}_p^(k+1)−(M−1)).  (17)

and if {tilde over (d)}_p^(k+1)<−(M−1), the adjustment equation is

p=l_p^(k)−sgn(z_p^(k))({tilde over (d)}_p^(k+1)+(M−1)).  (18)

[0099] Let ĩ_p,opt^(k) be obtained from l_p,opt^(k) by using the adjustment equations (17) and (18). It can be shown that if F(l_p,opt^(k)) is non-positive, then F(ĩ_p,opt^(k)) is also non-positive. We compute F(ĩ_p,opt^(k)), ∀p=1, . . . 2N_t. Now, given F(l_p,opt^(k)), ∀p, let

$\begin{array}{cc}\text{?}=\begin{array}{c}\arg \min \\ p\end{array}\left({\stackrel{\_}{l}}_{p.\mathrm{opt}}^{\left(k\right)}\right).\text{?}\text{indicates text missing or illegible when filed}& \left(19\right)\end{array}$

[0100] If F(ĩ_s,opt^(k))<0, the update for the (k+1)th iteration is

d^(k+1)=d^(k)+l_s^(k)sgn(z_s^(k))c_s,  (20)

z^(k+1)=z^(k)−l_s^(k)sgn(z_s^(k))g_s,  (21)

where gs is the sth column of G. The update in (21) follows from the definition of z^(k)(k) in (10). If F(ĩ_s,opt^(k))≧0, then the 1-symbol update search terminates. The data vector at this point is referred to as ‘1-symbol update local minima.’ After reaching the 1-symbol update local minima, we look for a further decrease in the cost function by updating multiple symbols simultaneously.

[0101] The motivation for trying out multiple symbol updates can be explained as follows. Let ⊂ denote the set of data vectors such that for any d∈ if a K-symbol update is performed on d resulting in a vector d′ then ∥y−Hd′∥≧∥y−Hd′∥. We note that d_ML∈L_K,=1, 2, . . . , 2N_t, because any number of symbol updates on d_ML will not decrease the cost function. We define another set M_k=∩_J=1^kL_j. Note that d_ML∈M_K,∀K=1, 2, . . . , 2N_t and ={d_ML}, i.e., , is a singleton set with dML as the only element. Also, ≦ K=1, 2, . . . , 2N_t−1. For any d∈ K=1, 2, . . . , 2N_t and d≠d_ML, it can be seen that d and d_ML will differ in K+1 or more locations. Since d_ML∈ and decreases monotonically with increasing K, there will be lesser non-ML data vectors to which the algorithm can converge to for increasing K. In addition, at moderate to high SNRs, d_ML=x with high probability. Therefore, the separation between any d∈ x will monotonically increase with increasing K with high probability. Therefore, the probability of the noise vector n inducing an error would decrease with increasing K. This indicates that K-symbol updates with large K could get near to ML performance. However, the overall complexity with up to K-symbol simultaneous updates allowed would be of order ( )(N_t^K). So, in order to limit the complexity to ( )(N_t²) per symbol, we restrict the updates to K=3. Since only up to 3-symbol updates are considered in the proposed algorithm, it follows that the algorithm would always converge to a data vector in As we will see in Sec. 4, close-to ML performance is achieved with the M-LAS algorithm even for K=3.

[0102] Let us consider 2-symbol update in this subsection. Let us assume that we update the pth and qth symbols in the (k+1)th iteration; p and q can take values from 1, . . . , N_t for M-PAM and 1, . . . , 2N_t for M-QAM. The update rule for the 2-symbol update can be written as

d^(k+1)=d^(k)+λ_p^(k)c_p+λ_q^(k)c_q.  (22)

[0103] For any iteration k. d^(k) should belong to the space S, and therefore λ_p^(k) and λ_q^(k) can take only certain integer values. In particular, λ_p^(k)∈ and λ_q^(k)∈ If is the M-PAM signal set, then {x|(x+d_p^(k))∈, x≠1)} and so is the definition for . Here, d_p^(k) refers to the pth symbol in the data vector d(k). For example, both 4-PAM and 16-QAM will have the same set A_p={−3, −1, 1, 3}, and if d(k) p is −1, then A_p^(k)={−2, 2, 4}.

[0104] Similar definitions can be obtained for non-square M-QAM signal sets as well. If the symbols were updated as given by (22), then using (7), we can write the cost difference function ΔC^k+1(λ_p^(k), λ_q^(k))C^(k+1)−C^(k) as

ΔC_p,q^k+1(λ_p^(k),λ_q^(k))=λ_p^(k)2(G)_q,q+2λ_p^(k),λ_q^(k)(G)_p,q−2λ_p^(k),_p^(k)−2λ_q^(k),_q^(k).  (23)

where λ_p^(k)∈ and λ_q^(k)∈. We can write this compactly (λ_p^(k), λ_q^(k))∈ where denotes the Cartesian product of and For a given p and q, in order to decrease the ML cost function, we would like to choose a pair (λ_p^(k), λ_q^(k)) such that ΔC_p,q^k+1 given by (23) is negative. If multiple pairs exist for which ΔC_p,q^k+1 is negative, we choose the pair which results in the most negative value of ΔC_p,q^k+1. Unlike 1-symbol update, for 2-symbol update ΔC_p,q^k+1(λ_p^(k), λ_q^(k)) in (23) s a function of two discrete valued variables, and so we do not have a closed-form expression for (λ_p,opt^(k), λ_q,opt^(k)). Consequently, a brute-force method is to evaluate ΔC_p,q^k+1(λ_p^(k), λ_q^(k)) over all possible values of (λ_p^(k), λ_q^(k)), i.e.,

$\begin{array}{cc}\left({\lambda }_{p.\mathrm{opt}}^{\left(k\right)},{\lambda }_{q.\mathrm{opt}}^{\left(k\right)}\right)=\begin{array}{c}\arg \min \\ \left({\lambda }_p^{\left(k\right)},{\lambda }_q^{\left(k\right)}\right)\in {}_{p,q}^{\left(k\right)}\end{array}\Delta C_{p,q}^{k+1}\left({\lambda }_p^{\left(k\right)},{\lambda }_q^{\left(k\right)}\right).& \left(24\right)\end{array}$

[0105] We denote the minimum value of ΔCk+1ΔC_p,q^k+1(λ_p^(k), λ_q^(k)) obtained from the above minimization as

ΔC_p,q,opt^k+1ΔC_p,q^k+1(λ_p,opt^(k),λ_q,opt^(k))  (25)

[0106] The computational complexity in (24) for M-PAM and O(M) for M-QAM. Approximate methods can be adopted to solve (24) using lesser complexity. One such method which can give closed-form expression for the solution is as follows. The cost difference function in (23) can be rewritten as

ΔC_p,q^k+1(λ_p^(k),λ_q^(k))=Δ_p,q^(k)TF_p,qp,q^(k)−2_p,q^(k)Tz_p,q^(k).  (26)

where
Λ_p,q^(k)[λ_p^(k), λ_q^(k)]^T and z_p,q^(k)[z_p^(k), z_q^(k)]^T. Also F_p,q∈ is the 2×2 sub-matrix of G containing only the elements in the pth and qth rows and columns. Therefore, (F_p,q)_1.1(G)_p,p, (F_p,q)_1.2(G)_p,q, (F_p,q)_2.1(G)_q,p, and (F_p,q)_2.2(G)_q,q. Since ΔC_p,q^k+1(λ_p^(k), λ_q^(k)) is a strictly convex quadratic function (the Hessian F_p,q is always positive definite), a unique global minima exists, and is given by

Λ_p,q^(k)=F_p,q⁻¹z_p,q^(k).  (27)

[0107] However, the solution given by (27) need not lie in and, therefore, we first round-off the solution to the nearest elements in , where Ap,q is the Cartesian product of and . We do the rounding as follows

{circumflex over (Λ)}_p,q^(k)=2└0.5{circumflex over (Λ)}_p,q^(k)┐.  (28)

[0108] In (28), the operation is done element-wise since {circumflex over (Λ)}_p,q^(k) is a vector. Further, let [{circumflex over (λ)}_p^(k){circumflex over (λ)}_q^(k)]^T{circumflex over (Λ)}_p,q^(k). It is possible that the solution {circumflex over (Λ)}_p,q^(k) in (28) need not lie in This would result in l_p^(k+1)∉. For example, if is M-PAM, then d_p^(k+1)∉ if d_p^(k)+{circumflex over (λ)}_p^(k)>(M−1). In such cases, we propose the following adjustment to {circumflex over (λ)}_p^(k)

$\begin{array}{cc}{\hat{\lambda }}_p^{\left(k\right)}=\{\begin{array}{cc}\left(M-1\right)-d_p^{\left(k\right)},& \mathrm{when}{\hat{\lambda }}_p^{\left(k\right)}+d_p^{\left(k\right)}>\left(M-1\right)\\ -\left(M-1\right)-d_p^{\left(k\right)},& \mathrm{when}{\hat{\lambda }}_p^{\left(k\right)}+d_p^{\left(k\right)}<-\left(M-1\right).\end{array}& \left(29\right)\end{array}$

[0109] Similar adjustment is done for {circumflex over (λ)}_q^(k) also. After these adjustments, we are guaranteed that {circumflex over (λ)}_p,q^(k)∈. We can therefore evaluate the cost difference function value as _Ck+1 ΔC_p,q^k+1({circumflex over (λ)}_p^(k), {circumflex over (λ)}_q^(k)). It is noted that the complexity of this approximate method does not depend on the size of the set i.e., it has constant complexity. Through simulations, we have observed that this approximation results in a performance close to that of the brute-force method. We define the optimum pairs, (r, s) from the brute-force method and (r, s) from the approximate method, respectively, as

$\begin{array}{cc}\left(r,s\right)=\begin{array}{c}\arg \min \\ \left(p,q\right)\end{array}\Delta C_{p.q.\mathrm{opt}}^{k+1},\text{and}& \left(30\right)\\ \left(\stackrel{.}{r},\stackrel{.}{s}\right)=\begin{array}{c}\arg \min \\ \left(p,q\right)\end{array}\Delta C_{p.q}^{k+1}\left({\hat{\lambda }}_p^{\left(k\right)},{\hat{\lambda }}_q^{\left(k\right)}\right).& \left(31\right)\end{array}$

[0110] The corresponding minimum values of the cost difference functions are given by

ΔC_opt^k+1ΔC_r,s,opt^k+1.  (32)

and

ΔĈ_opt^k+1ΔC_r,s^k+1({circumflex over (λ)}_r^(k),{circumflex over (λ)}_s^(k)).  (33)

[0111] The update rule for the z(k) vector is given by

z^(k+1)=z^(k)−(λ_r,opt^(k)g_r+λ_s,opt^(k)g_s)  (34)

d^(k+1)=d^(k)+λ_r,opt^(k)c_r+λ_s,opt^(k)c_s  (35)

for the brute-force method, and

z^(k+1)=z^(k)−({circumflex over (λ)}_r^(k)g_r+{circumflex over (λ)}_s^(k)g_s)  (36)

d^(k+1)=d^(k)+({circumflex over (λ)}_r^(k)c_r+{circumflex over (λ)}_s^(k)c_s)  (37)

for the approximate method. A similar procedure can be devised for the 3-symbol update as well. The 3-symbol update procedure is summarized in Appendix A. The overall algorithmic summary of the proposed M-LAS is given in Table-I. The complexity of the M-LAS algorithm can be shown to be ( )(N_tN_r) per symbol, which is given in Appendix B.

[0112] In this section, we present the uncoded and coded BER performance of the M-LAS detector in V-BLAST, evaluated through simulations for hard as well as soft decision M-LAS outputs.

[0113] Performance for increasing N_t=N_r. In FIG. 1, we present the uncoded BER performance of the M-LAS detector for different values of N_t=N_r and 4-QAM. MMSE filter is used as the initial filter. We label the M-LAS detector with MMSE initial filter as ‘MMSEMLAS’ in all the figures. MMSE filter (without M-LAS) performance as well as AWGN only (without fading) SISO performance are also plotted for comparison. Perfect knowledge of the channel coefficients is assumed at the receiver in the simulations (this assumption will be relaxed in later coded BER simulations). From FIG. 1, it can be observed that the performance of the proposed MMSE-MLAS improves with increasing N_t=N_r, such that for N_t=N_r=64 it achieves an uncoded BER of 10⁻³ at just 1 dB away from the SNR required in a AWGN-only SISO system with 4-QAM. With N_t=N_r=128 and 256, the MMSEMLAS performance moves even closer to the AWGN-only SISO performance (to within 0.5 dB) This is an impressive result which illustrates the ability of the proposed MMSE-MLAS to achieve single-antenna, no-fading, AWGN performance in a large multi-antenna fading scenario, essentially removing ‘almost’ all the spatial interference from other antennas.

[0114] M-LAS versus LAS: it is pointed out that the LAS detector presented in reference [9], [10] also achieves near AWGN-only SISO performance, but only when the number of antennas is of the order of hundreds. Whereas, a key advantage of the present M-LAS detector is that it is able to achieve near AWGN-only SISO performance even with tens of antennas (e.g., N_t=N_r=64). This observation is illustrated in FIG. 2, where we compare the uncoded BER performance of the MMSE-MLAS with that of the MMSE-LAS in reference [9], [10] (i.e., LAS with MMSE initial filter), for N_t=N_r=64, 32 and 4-QAM. It can be seen that MMSE-MLAS outperforms MMSELAS. This performance improvement is due to the 2- and 3-symbol updates performed in MLAS, in addition to the 1-symbol updates performed in LAS. As we pointed out earlier, the 2- and 3-symbol updates in M-LAS increase the complexity a little, but the average per-symbol complexity (defined as total complexity divided by the total number of complex symbols, Nt) still remains as ( )(N_tN_r) as illustrated in Appendix B. Also, the performance advantage of M-LAS over LAS in the regime of tens of antennas has interesting practical implications, since tens of antennas can be placed in moderately sized communication terminals (e.g., laptops, set top boxes) which can enable large MIMO systems to be viable in practice.

[0115] We next evaluated the coded BER performance of the M-LAS detector with a focus on establishing its nearness to theoretical MIMO capacity. For a MIMO system model in Sec. 2 with perfect channel state information (CSI) at the receiver, the ergodic capacity is given by [5]

C=E[log d (l_Nr+(N_t)HH^H)].  (38)

where l_Nr is the N_r×N_r identity matrix and is the average SNR per receive antenna.

[0116] In FIG. 3, we plot the capacity curves for 64×64 and 128×128 MIMO systems evaluated through Monte-Carlo simulations. It can be seen that the minimum SNRs required to achieve a capacity of 96 bps/Hz in a 64×64 system and 192 bps/Hz in a 128×128 system are both 4.3 dB. We consider two practical MIMO system designs that use a rate-¾ turbo code and 4-QAM; one having a spectral efficiency of 96 bps/Hz by using 64×64 V-BLAST, and another having a spectral efficiency of 192 bps/Hz by using 64×64V-BLAST. In both these systems; we establish how close the M-LAS detector's performance can go near the theoretical capacity; these results are explained herein below (shown in FIGS. 4 and 5).

[0117] A method for generating soft output from M-LAS is proposed. Generating soft values at the M-LAS output for all the individual bits that constitute the modulation symbols (M-PAM/M-QAM) mounted on all the transmit antennas as follows. These soft output values are then fed as inputs to the turbo decoder. Let d=[{circumflex over (x)}₁, {circumflex over (x)}₂, . . . , {circumflex over (x)}_2Nt], {circumflex over (x)}_i∈ denote the detected output vector from the M-LAS algorithm. Let {circumflex over (x)}_i map to the bit vector b_i=[b_i,1, b_i,2, . . . , b_i,K]^T, where K_i=log₂|A_i|, and b_ij∈{+1, −+} i=1, 2, . . . 2N_t and j=1, 2, . . . K_i {tilde over (b)}_ij∈ denote the soft value for the jth bit of the ith symbol. Given d, we need to find ∀(i, j). Now, define vectors b_i^j+ and b_i^j− to be the b_i vector with its jth entry forced to +1 and −1, respectively. Let b_i^j+ and b_i^j− demap to and respectively, where , ∈ Also, define vectors d_i^j+ and d_i^j− to be the d vector with its ith entry forced to and respectively. Using the above definitions, we obtain the soft output value for the jth bit of the ith symbol as

$\begin{array}{cc}{\tilde{b}}_{i,j}=\frac{{y-{\mathrm{Hd}}_i^{j-}}^2-{y-{\mathrm{Hd}}_i^{j+}}^2}{{b_i}^2}.& \left(39\right)\end{array}$

[0118] The RHS of the above equation can be efficiently computed in terms of the known variables z and G as follows. Since d_jⁱ+ and d_jⁱ− differ only in the ith entry, we can write

d_i^j−=d_i^j++λ_i,j.  (40)

[0119] Since we know d_jⁱ− and d_jⁱ+, we know λij, from (40). Substituting (40) in (39), we can write

$\begin{array}{cc}{\tilde{b}}_{i,j}{h_i}^2={y-{\mathrm{Hd}}_i^{j+}-{\lambda }_{i,j}h_{\text{?}}}^2-{y-{\mathrm{Hd}}_{\text{?}}^{j+}}^2& \\ ={\lambda }_{i,j}^2{h_i}^2-2{\lambda }_{i,j}h_i^T\left(y-{\mathrm{Hd}}_i^{j+}\right)& \left(41\right)\\ =-{\lambda }_{i,j}^2{h_i}^2-2{\lambda }_{i,j}h_i^T\left(y-{\mathrm{Hd}}_{\text{?}}^{j-}\right).& \left(42\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$

[0120] If d_i^j=1, then d_jⁱ+=d, and substituting this in (41) and dividing by llh_ill², we get

$\begin{array}{cc}{\hat{b}}_{i,j}={\lambda }_{i,j}^2-2{\lambda }_{i,j}\frac{z_i}{{\left(G\right)}_{\text{?}}}.\text{?}\text{indicates text missing or illegible when filed}& \left(43\right)\end{array}$

[0121] On the other hand, if b_i^j, =−1, then d_jⁱ−=d, and substituting this in (42) and dividing by llh_ill², we get

$\begin{array}{cc}{\hat{b}}_{i,j}=-{\lambda }_{i,j}^2-2{\lambda }_{i,j}\frac{z_{\text{?}}}{{\left(G\right)}_{i,j}}.\text{?}\text{indicates text missing or illegible when filed}& \left(44\right)\end{array}$

[0122] It is noted that z and G are already available upon the termination of the M-LAS algorithm, and hence the complexity of computing b_ij in (43) and (44) is constant. Hence, the overall complexity in computing the soft values for all the bits is O(N_t log₂M). It is observed from (43) and (44) that the magnitude of b_ij depends upon λ_ij. For large size signal sets, the possible values of λ_i,j will also be large in magnitude. Therefore b_ij has to be normalized for the turbo decoder to function properly. It has been observed through simulations that normalizing b_ij by

${\left(\frac{{\lambda }_{i,j}}{2}\right)}^2$

resulted in good performance.

[0123] Turbo Coded BER Results

[0124] FIG. 4 shows the rate-¾ turbo coded BER performance of the proposed M-LAS detector for N_t=N_r=64, 128, 4-QAM and MMSE initial vector. It is also shown the minimum SNR limit of 4.3 dB required to achieve theoretical capacity. Turbo coded BER plots for hard decision as well as soft decision M-LAS outputs are shown. It can be observed that with hard decision input to the turbo decoder, the M-LAS detector for 64×64 V-BLAST performs close to within about 6 dB from the theoretical capacity. With the proposed soft decision inputs, it performs close to within about 4.5 dB from theoretical capacity. In a 128×128 V-BLAST system, the M-LAS detector is found to perform close to within about 4 dB and 5.5 dB from theoretical capacity for soft decision and hard decision, respectively, which is an impressive result from a nearness to capacity viewpoint. Further, FIG. 5 shows the uncoded and rate-⅓ turbo coded BER performance of the M-LAS detector with hard and soft decision for N_t=N_r=600, MF initial filter and BPSK. (For such large number of antennas, the performance of M-LAS and LAS with MF, ZF, and MMSE initial vectors are almost the same, since, in this case, the near-ML performance point will be reached in the first search stage with 1-symbol update itself, and therefore 2- and 3-symbol updates will be less likely to further increase the likelihood. Also, the matrix inversion involved in the MMSE/ZF initial filters can be avoided if MF is used instead) It can be seen that M-LAS with soft decision performs close to within just about 3.2 dB from theoretical IMO capacity. This is by far the best nearness to capacity result reported with a practical low-complexity detector in a large MIMO system with such large number of antennas.

[0125] Effect of Channel Estimation Errors: The effect of channel estimation errors on the performance of the M-LAS detector is evaluated. Considering a channel estimation error model where the estimated channel matrix. Ĥ, is taken to be Ĥ=H+ΔH, where ΔH is the estimation error matrix, the entries of which are assumed to be i.i.d. complex Gaussian with zero mean and variance 0⁻²_e. In FIG. 4, also plotted the coded BER performance of the M-LAS detector with soft decision for 64×64 V-BLAST with a channel estimation error variance of 0⁻²_e=0.02. It can be observed that the loss in coded BER performance is only about 1 dB compared to the case of perfect channel estimates, indicating the robustness of the M-LAS to channel estimation errors. Along this line, low-complexity channel estimation algorithms and their performance in large MIMO systems are being investigated as further extension to this work.

[0126] Decoding of STBCs from DA Using M-LAS

[0127] High-rate, non-orthogonal STBC_s (an STBC is represented by a p×N_t matrix with complex entries, where N_t and p denote the number of transmit antennas and time slots, respectively. Rate of an STBC, r, is defined as r=k/p, where k and p denote the number of complex symbols sent and number of time slots, respectively, in one STBC matrix) from Division Algebras (DA) in reference [15] are attractive for achieving high spectral efficiencies in addition to achieving full transmit diversity, using large number of transmit antennas. Well known orthogonal STBCs have the advantages of low decoding complexity and full transmit diversity, but suffer from rate loss for increasing number of transmit antennas as in reference [2], [17], [18], [19]. Non-orthogonal STBCs which achieve full-rate can be constructed from DA for arbitrary number of transmit antennas, n, using the following construction [15]: (An n×n STBC is said to be full-rate if the number of complex symbols transmitted per channel use is equal to min (N_t,N_r). For example, the well known Alamouti code as in reference [17] is of full-rate when received with one antenna and not of full-rate when received with more than one antenna)

$\begin{array}{cc}& \left(45\right)\end{array}[\begin{array}{ccccc}{\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& \text{?}{\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& \text{?}{\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& \dots & \text{?}{\sum }_{\text{?}=0}^{\text{?}-1}\text{?}\\ {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& \text{?}{\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& \dots & \text{?}{\sum }_{\text{?}=0}^{\text{?}-1}\text{?}\\ {\sum }_{\text{?}=0}^{\text{?}1}\text{?}& {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& \dots & \text{?}{\sum }_{\text{?}=0}^{\text{?}-1}\text{?}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& \dots & \text{?}{\sum }_{\text{?}=0}^{\text{?}-1}\text{?}\\ {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}& \dots & {\sum }_{\text{?}=0}^{\text{?}-1}\text{?}\end{array}],\text{?}\text{indicates text missing or illegible when filed}$

where n is an integer,

$\text{?}=t^{\frac{\mathrm{j2}\pi }{n}},j=\sqrt{-1},\mathrm{and}\text{?},0\le \text{?}\le \text{?}-1$ $\text{?}\text{indicates text missing or illegible when filed}$

are the data symbols from a QAM alphabet. When δ=√{square root over (5)}j and i=, the code in (45) achieves full transmit diversity (under ML decoding) as well as information-losslessness [15]. When δ=t=1, the code ceases to be of full-diversity, but continues to be information-lossless, reference [16]. High spectral efficiencies with large n can be achieved using the above code construction. For example, with n=16 transmit antennas, the 16×16 STBC from (45) with 4-QAM and rate-¾ turbocode achieves a high spectral efficiency of 24 bps/Hz. This high spectral efficiency is achieved along with the full-diversity of order nN_r. However, since the code is non-orthogonal, ML decoding gets increasingly impractical for large n (there are n² symbols in a code matrix). Consequently, a key challenge in realizing the benefits of these large DA codes in practice is that of achieving near-ML performance for large n at low decoding complexities. In this context, a significant contribution in this disclosure is that we have successfully adopted the proposed M-LAS algorithm to decode large STBCs (the STBC received signal model in an equivalent V-BLAST form, and apply the M-LAS algorithm on this equivalent signal model) from DA, and show that the algorithm achieves near capacity performance with low decoding complexity for large n.
BER Performance of STBCs from DA

[0128] Uncoded BER Performance: In FIG. 6, we present the uncoded BER performance of the M-LAS detector in decoding n×n full-rate, non-orthogonal STBCs from DA in (45) for n=4, 8, 16 and 4-QAM. It can be observed that as the STBC code size n increases, the M-LAS performs increasingly better such that it achieves close to AWGN-only SISO performance (within 0.5 dB at 10⁻³ BER and less) with the 16×16 STBC having 256 complex symbols in it. We emphasize that due to the high complexities involved in decoding large size STBCs using other known detectors, the BER performance of STBCs with large n has not been reported in the literature so far. The very fact that we could show the simulated BER plots (both uncoded as well as turbo coded) for a 16×16 STBC with 256 complex symbols in one code matrix in itself is a clear indication of the superior low-complexity attribute of the proposed M-LAS algorithm. To our knowledge, we are probably the first to report the simulated BER performance of a 16×16 STBC from DA; this became feasible because of the low-complexity feature of the proposed M-LAS algorithm. In addition, the achievement of near-AWGN SISO performance with 16×16 STBC is a significant result from an implementation view point as well, since 16 antennas can be easily placed in communication terminals of moderate size, which can make large MIMO systems practical.

[0129] Large Asymmetric MIMO Architecture: Large asymmetric MEMO systems where the transmitter and receiver have unequal number of transmit and receive antennas are of interest. For example, the base station (BS) with a lesser constraint on terminal size and cost can be provided with a larger number of transmit antennas, while a more cost/space constrained user terminal can use fewer number of receive antennas. This asymmetric architecture can reduce the cost and hardware complexity at the user terminals. Note that such an asymmetric approach has been provided for in the IEEE 806.16e standards; e.g., 4 transmit antennas at the BS and 2 receive antennas at the user terminal. We point out that, with the availability of the proposed low-complexity M-LAS algorithm for decoding large size STBCs, asymmetric STBC MIMO systems with even larger number of antennas can be made possible (e.g., 16 transmit antennas at the BS employing a 16×16 STBC, and 12 receive antennas at the user terminals). The advantage of this large asymmetric STBC MIMO approach is that we can achieve high spectral efficiencies (by way of using a large size non-orthogonal STBC, and hence large number of transmit antennas at the BS), while keeping the cost and hardware complexity at the user terminal low (by way of using fewer number of receive antennas at the user terminal). To illustrate this point, in FIG. 7, we show the uncoded BER plots for the 8×8 STBC from DA decoded using the M-LAS algorithm for different number of receive antennas, N_r=1, 2, . . . , 8. It can be seen that Nr=8 achieves a BER performance close to within 2 dB of the AWGN-only SISO performance. The M-LAS detector achieves reasonably good performance even for N_r=7 indicating its ability to perform reasonably well even with slightly lesser number of receive antennas. With an outer turbo code, the coded BER with N_r=7 could be acceptable, though not as good as that for N_r=8. This can allow a useful tradeoff between cost/complexity versus performance at the user terminal. FIG. 8 shows a similar uncoded BER plot for the 16×16 STBC in (45) for different values of N_r.

[0130] Turbo Coded BER Performance: FIG. 9 shows the uncoded as well as rate-½ turbo coded BER performance of the 4×4 STBC from DA in (45) with N_r=4 and 4-QAM at a spectral efficiency of 4 bps/Hz. The minimum SNR required to achieve capacity in this system (1.2 dB) is also shown. From FIG. 9, we can see that the proposed M-LAS with soft decision achieves a performance close to within about 1 dB of the theoretical capacity. In FIG. 10, we show the coded BER performance for the 16×16 STBC using different turbo code rates of ⅓, ½, and ¾. With 4-QAM, these turbo code rates along with the 16×16 STBC in (45) correspond to spectral efficiencies of 10.6 bps/Hz, 16 bps/Hz and 24 bps/Hz, respectively. The minimum SNRs required to achieve these capacities are also shown in FIG. 10. It can be observed that the proposed M-LAS with soft decision performs to within about 4 to 4.5 dB of the theoretical capacity. Such nearness to capacity is a remarkable result from a theoretical view point, in addition to the low-complexity attribute of the M-LAS being remarkable from a large MIMO implementation view point. We further point out that although performance results are presented here only for n×n square STBC designs, the M-LAS algorithm can efficiently decode large n₁×n₂, n₁≠n₂ rectangular non-orthogonal STBC designs.

[0131] We point out that while the V-BLAST approach in large MIMO is attractive in terms of high spectral efficiency, large MIMO systems employing high-rate, non-orthogonal STBCs are quite attractive for practical implementation for the following reasons:

• [0132] 1. Number of transmit/receive antennas and IF/RF chains can be quite less in an STBC approach than in the spatial multiplexing (V-BLAST) approach; this can significantly reduce the hardware complexity and cost of the communication terminal,
• [0133] 2. Fewer channel coefficients need to be estimated in an STBC approach than in the VBLAST approach; for example, with an n×n STBC and one receive antenna (with quasi-static fading) only n fade coefficients need to be estimated, whereas in an n transmit and n receive antenna V-BLAST system, the number of fade coefficients to be estimated is n² which would require a more elaborate pilot symbols design and increased pilot power resulting in increased loss in throughput,
• [0134] 3. Availability of transmit diversity and coding gains in the STBC approach allows one to get much closer to capacity than the V-BLAST approach, and
• [0135] 4. Feasibility of an asymmetric MIMO architecture with the STBC approach, where large numbers of antennas are provided at the BS and fewer antennas at the user terminal, can reduce the hardware complexity and cost of the user terminal. For example, a 32×32 STBC from DA with 32 transmit antennas at the BS and 24 antennas at the user terminal could be practical; with 4-QAM and rate-¾ turbo code this system will offer a spectral efficiency of 48 bps/Hz.

[0136] The drawbacks with the STBC approach are the decoding delays and the quasi-static fading assumption. In indoor channels (e.g., in environments where systems like IEEE 802.11n operate) and fixed wireless channels (e.g., IEEE 802.16 fixed wireless standard), the channel coherence times are typically large for the quasi-static fading assumption to be valid.

[0137] Rectangular non-orthogonal STBCs with more number of transmit antennas than the number of time slots could be devised to alleviate the decoding delay issue while retaining high spectral efficiencies; the proposed M-LAS could be employed in decoding of such rectangular non-orthogonal STBCs as well.

[0138] The instant disclosure provides a low-complexity M-LAS algorithm for detection/decoding in large MIMO systems including V-BLAST as well as high-rate non-orthogonal STBCs from division algebras with tens of transmit/receive antennas. The proposed M-LAS algorithm was shown to have excellent features in terms of both low complexity as well as nearness to capacity performance. We believe that with the availability of low-complexity detectors (like the proposed M-LAS), large MIMO systems using V-BLAST and high-rate STBCs with large number of antennas will become practical, enabling interesting spectrally efficient high data rate wireless applications (e.g., wireless IPTV). Issues in channel estimation, pilot symbols allocation, and antenna/RF technologies in the large MIMO context are being investigated. Given that 4 antenna systems are already defined in the current wireless standards like IEEE 802.11n and IEEE 802.16e, the proposed M-LAS algorithm has good potential for application in practical wireless standards.

[0139] In this appendix, we present the 3-symbol update procedure in the proposed M-LAS algorithm. Let us assume that we update the pth, qth and rth symbols in the (k+1)th iteration; p, q and r can take values from 1, . . . , N_t for M-QAM and 1, . . . , 2N_t for M-QAM. As in the case of 2-symbol update, the update rule for 3-symbol update can be written as

d^(k+1)=d^(k)+λ_p^(k)c_p+λ_q^(k)c_q+λ_r^(k)c_r.  (46)

[0140] For any iteration k, d^(k) should belong to the signal space S, and therefore λ_p^(k), λ_q^(k), and λ_r^(k) can take only certain integer values. In particular, λ_p^(k)∈ λ_q^(k)∈ and λ_r^(k)∈

[0141] If Ap is the M-PAM signal set, then {x∈, x≠|(r+d_p^(k))|≦(M−1)}, and so is the definition for A_q^(k) and A_r^(k). Similarly, if A_p is square M-QAM signal set, then {x∈≠0|(r+d_p^(k))|≦(√{square root over (M)}−1)}, and so is the definition for A_q^(k) and A_r^(k). Similar definitions can be obtained for non-square M-QAM signal sets as well.

[0142] If the symbols were updated as given by (46), we can write the cost difference function ΔC_p,q,r^k+1(λ_p^(k), λ_q^(k), λ_r^(k))C^(k+1)−C^(k) as

ΔC_p,q,r^k+1(λ_p^(k),λ_q^(k),λ_r^(k))=λ_p^(k)2(G)_p,p+λ_q^(k)2(G)_q,q+λ_p^(k)2(G)_r,r+2λ_p^(k)λ_q^(k)(G)_p,q+2λ_p^(k)λ_r^(k)(G)_p,r+2λ_q^(k)λ_r^(k)(G)_q,r−2λ_p^(k)z_p^(k)−2λ_q^(k)z_q^(k)−2λ_r^(k)z_r^(k).  (47)

[0143] As before, λ_p^(k)∈A_p^(k), λ_q^(k)∈A_q^(k), and λ_r^(k)∈A_r^(k), and which can be compactly written as (λ_p^(k), λ_q^(k), λ_r^(k))∈ where denotes the Cartesian product of A_p^(k), A_q^(k), and A_r^(k). For the ML cost function to decrease, we would like to choose a 3-tuple (λ_p^(k), λ_q^(k), λ_r^(k)) such that ΔC_p,q,r^k+1 given by (47) is negative. If multiple 3-tuples exist for which ΔC_p,q,r^k+1 is negative then we choose the 3-tuple which results in the most negative value of ΔC_p,q,r^k+1.

[0144] For 3-symbol update, ΔC_p,q,r^k+1(λ_p^(k), λ_q^(k), λ_r^(k)) is a function of three discrete-valued variables. As in the case of 2-symbol update, here also we have a brute-force method as well as an approximate method to minimize ΔC_p,q,r^k+1(λ_p^(k), λ_q^(k), λ_r^(k)) over over The brute-force solution is given by

$\begin{array}{cc}\left({\lambda }_{p.\mathrm{opt}}^{\left(k\right)},{\lambda }_{q.\mathrm{opt}}^{\left(k\right)},{\lambda }_{r.\mathrm{opt}}^{\left(k\right)}\right)=\begin{array}{c}\arg \min \\ \left({\lambda }_p^{\left(k\right)},{\lambda }_q^{\left(k\right)},{\lambda }_r^{\left(k\right)}\right)\in {}_{p.q.r}^{\left(k\right)}\end{array}\Delta C_{p.q.r}^{k+1}\left({\lambda }_p^{\left(k\right)},{\lambda }_q^{\left(k\right)},{\lambda }_r^{\left(k\right)}\right).& \left(48\right)\end{array}$

[0145] We denote the minimum value of the ΔC_p,q,r^k+1(λ_p^(k), λ_q^(k), λ_r^(k)) obtained from the above minimization as

ΔC_p,q,r,opt^k+1ΔC_p,q,r^k+1(λ_p,opt^(k),λ_q,opt^(k),λ_r,opt^(k)).  (49)

[0146] The computational complexity in this brute-force method is O(M³) for M-PAM and O(M^1.5) for M-QAM. As in the case of 2-symbol update, we can obtain an approximate low-complexity solution to (48) as follows. We define ∈R^3×3 as the 3×3 submatrix of containing only the elements in the pth, qth and rth rows and columns, and z_p,q,r^(k)[z_p^(k), z_q^(k), z_r^(k)]^T. With these definitions, we can write

{circumflex over (Λ)}_p,q,r^(k)≡[{circumflex over (λ)}_p^(k),{circumflex over (λ)}_q^(k),{circumflex over (λ)}_r^(k)]^T=2└0.5┐.  (50)

[0147] We carry out adjustments on {circumflex over (λ)}_p^(k), {circumflex over (λ)}_q^(k), {circumflex over (λ)}_r^(k) (similar to those in (29)), and obtain the solutions for (48) using the brute-force and the approximate methods, respectively, as

$\begin{array}{cc}\left(u,v,w\right)=\begin{array}{c}\arg \min \\ \left(p,q,r\right)\end{array}\Delta C_{p,q,r,\mathrm{opt}}^{k+1}.\text{And}& \left(51\right)\\ \left(\stackrel{.}{u},\text{?},w\right)=\begin{array}{c}\arg \min \\ \left(p,q,r\right)\end{array}\Delta C_{p,q,r}^{k+1}\left({\hat{\lambda }}_p^{\left(k\right)},{\hat{\lambda }}_q^{\left(k\right)},{\hat{\lambda }}_r^{\left(k\right)}\right).\text{?}\text{indicates text missing or illegible when filed}& \left(52\right)\end{array}$

[0148] The corresponding minimum values of the cost difference functions are given by

ΔC_opt^k+1ΔC^k+1.  (53)

And

ΔĈ_opt^k+1ΔC^k+1({circumflex over (λ)}_p^(k),{circumflex over (λ)}_q^(k),{circumflex over (λ)}_r^(k)).  (54)

[0149] The update rule for the z^(k) vector is given by

$\begin{array}{cc}\begin{array}{c}z^{\left(k+1\right)}=z^{\left(k\right)}-G\left(d^{\left(k+1\right)}-d^{\left(k\right)}\right)\\ =z^{\left(k\right)}-\left({\lambda }_{\text{?}}^{\left(k\right)}g\text{?}+{\lambda }_{\text{?}}^{\left(k\right)}g\text{?}+{\lambda }_{\text{?}}^{\left(k\right)}g\text{?}\right)\end{array}\text{?}\text{indicates text missing or illegible when filed}& \left(55\right)\end{array}$

for the brute-force method, and

z^(k+1)=z^(k)−({circumflex over (λ)}^(k)g_u+{circumflex over (λ)}^(k)g+{circumflex over (λ)}^(k)g)  (56)

for the approximate method.

[0150] In this appendix, we present the complexity of the proposed M-LAS algorithm listed in Table-I. Step 1 is the initialization step, which involves the computation of the initial filter B, the matrix G and the initial data vector d⁽⁰⁾. If the initial filter is MMSE or ZF, then the computational complexity of the initialization step is O(N²_tN_r).

[0151] Steps 2 to 48 represent one search stage of the proposed algorithm. The algorithm goes through a sequence of such search stages until it terminates in Step 49. In each search stage, the algorithm first undergoes multiple iterations of 1-symbol updates till it reaches a 1 symbol update local minima, which is carried out in Step 4 to Step 18 of the algorithm. The computational complexity of one iteration (i.e., from Step 6 to Step 18) is 0(N_t). The number of these iterations is a random variable, and the mean number of iterations per search stage, evaluated through simulations, has been found to be proportional to Nt; the proportionality constant depends on M, the signal set (PAM/QAM), average received SNR, and the initial vector (this can be observed from FIG. 11 for MMSE initial filter and 4-QAM). Therefore, in each search stage, the computational complexity from Step 2 to Step 19 is O(N²_t). Upon reaching a 1-symbol update local minima (in Step 15), the algorithm jumps to Step 19 and starts a 2-symbol update.

[0152] Steps 20 to 33 represent the 2-symbol update. In Steps 22 and 23, we employ the approximate method (instead of the brute-force method in order to reduce complexity) for the minimization of Eqn. (26) for each (p, q) pair. In Step 28, the algorithm checks to see if it has been able to find a pair of symbols, such that updating the pair would result in a decrease in the ML cost function. If the check passes, then the z and d vectors are appropriately updated in Steps 29 and 30, respectively. The initial vectors d(0) and z(0) for the next search stage are properly initialized (Step 31) and the control is transferred back to Step 2, from where the next search stage would start. It can be seen that the computational complexity of the 2-symbol update (Step 20 to 34 using the approximate method) is O(N²_t). If the brute-force technique were to be used, then the complexity would be O(M²N²_t) for M-PAM and O(M N²_t) for square M-QAM. If the check in Step 28 fails, it implies that the algorithm could not find a 2-symbol update which would result in a decrease in the ML cost function. Therefore, the algorithm jumps to Step 34, and starts a 3-symbol update.

[0153] Steps 35 to 48 represent the 3-symbol update. It can be seen that the computational complexity of the 3-symbol update (Steps 35 to 48) is O(N³_t) for the approximate method. If the brute-force technique were to be used, then the complexity would be O(M³ N³_t) for M-PAM and O(M^1.5N³_t) for square M-QAM. We note that the algorithm tries a 3-symbol update only when any 2-symbol update does not lead to a decrease in the cost function. Therefore, if the check in Step 43 fails and we terminate, it is an indication that with the current data vector no 1-, 2- or 3-update would lead to a decrease in the cost function. This, therefore, guarantees that indeed the final detected output vector belongs to the set M3.

[0154] Combining the complexities involved with the various steps discussed in the above, it can be seen that the complexity of one search stage of the algorithm is upper bounded by O(N³_t). The total complexity would depend upon the number of stages till the algorithm terminates. Through simulations, it has been observed that the mean number of search stages is almost constant (this can be observed in FIG. 12 for MMSE initial filter and 4-QAM). Therefore, the total computational complexity of the proposed algorithm is O(N²_t N_r), i.e., an average per-symbol complexity of O(N_tN_r). It can be seen that the proposed algorithm can be easily extended such that the algorithm does not terminate after 3-symbol update, i.e., a general K-symbol update algorithm can be devised. A large K can offer better performance at the cost of increased complexity of O(N^K_t). However, as we will show in the simulation results, even with K=3 (i.e., up to 3-symbol update) the proposed algorithm is able to achieve near-ML performance in a system with tens of antennas.

[0155] The present invention achieves both complexity gain as well as performance gain compared to a well known MIMO detector in prior art (i.e., ZF-SIC) when the number of antennas is more than 20. When the number of antennas is less than 20, the present invention achieves only complexity gain compared to ZF-SIC detector.

[0156] The present invention achieves near-ML performance only for large number of antennas. Typically, near-ML performance is achieved for more than 60 antennas. Placement of tens to hundreds of antennas in communication terminals is a challenge when the communication terminals are small in size. This would require a high carrier frequency operation, i.e., small carrier wavelengths for λ/2 separation to ensure independence between multi-antennas fade coefficients. Communication terminals of reasonable size (e.g., laptops, set top box, etc.) can have tens of antennas (e.g., 32 or 64 antennas) using which the present invention can achieve near-ML performance. Fixed communication terminals in indoor environments can have even higher number of antennas. Also, a much larger number of antennas can be embedded in the body of vehicles in moving platform applications (e.g., cars, trucks, tanks, jeeps, autonomous under water vehicles in under water acoustic communications, etc.).

[0157] Since a high-rate space-time block code (STBC) multi-antenna approach typically involves lesser number of antennas compared to a V-BLAST multi-antenna approach, the antenna placement issue can be alleviated by the use of high-rate STBC approach. Accurate channel estimation at the receiver is a requirement in the proposed invention.

[0158] In addition to being applicable to the V-BLAST multi-antenna systems and STBC multi-antenna systems, the present invention is also applicable to the following large MIMO systems:

• • [0159] Distributed MIMO systems and networks with large number of cooperating nodes.
  • [0160] Ultra-wide band (UWB) systems with large number of users and large number of channel taps (caused by frequency selectivity of the channel).
  • [0161] Multiuser OFDM and MIMO-OFDM systems with large number of users and large number of subcarriers.
  • [0162] Underwater acoustic communications with large number of sensor/communication nodes deployed to sense and send information through the underwater acoustic channel to a data collection platform provided with multiple receive antennas.

[0163] Our results further show that providing asymmetry in number of antennas such that N_r>N_t keeping the total receiver array length same as that for N_r=N_t, the detector is able to pick up the extra receive diversity thereby significantly improving the BER performance.

[0164] Asymmetry in Number of Antennas with N_r>N_t: FIG. 14 illustrates that the LAS detector can achieve substantial improvement in uncoded as well as coded BER performance compared to N_r=N_t by increasing N_r beyond N_t for 16-QAM in i.i.d. fading. For example, by comparing the LAS detector performance in decoding 12×12 STBC from DA with (N_t=N_r=12) versus (N_t=12, N_r=18) we observe that the uncoded BER performance with (N_t=12, N_r=18) improves by about 14 dB compared to (N_t=N_r=12) at 10-3 BER. Even the uncoded BER performance with (N_t=12. N_r=18) is significantly better than the coded BER performance with (N_t=N_r=12). This improvement is essentially due to the ability of the LAS detector in effectively picking up the additional diversity orders provided by the increased number of receive antennas. With a rate-¾ turbo code (36 bps/Hz spectral efficiency), at a coded BER of 10-4, the LAS detector achieves a significant performance improvement of about 12.5 dB with (N_t=12, N_r=18) compared to that with (Nt=Nr=12). In fact, with (N_t=12, N_r=18) the vertical fall of coded BER is such that it is only about 7 dB from the theoretical minimum SNR to achieve capacity. A similar advantage of exploiting antenna asymmetry with N_r>N_t and 16-QAM in correlated fading is illustrated in FIG. 15, where we have maintained Nrdr=72 cm and dt=dr in both the cases of symmetry (i.e., N_t=N_r=12) as well as asymmetry (i.e., N_t=12, N_r=18). From FIG. 15, it can be observed that with asymmetry and rate-¾ turbo code (i.e., 36 bps/Hz), the LAS detector achieves near-capacity performance to within just about 8 dB, which is a significant result which points to the potential of realizing practical high spectral efficiency multi-gigabit large MIMO systems that can achieve near-capacity performance even in the presence of spatial correlations.

[0165] While the spectral efficiencies achieved in current MIMO wireless standards (e.g., IEEE 802.11n and 802.16e) are only about 10 bps/Hz or less, the practical feasibility of the proposed LAS detector and its ability to perform well at much higher spectral efficiencies through the use of 16×16 and 12×12 non-orthogonal STBCs can enable practical implementation of multi-gigabit MIMO wireless systems with spectral efficiencies in excess of 10 bps/Hz. This approach can also be relevant in multi-gigabit 60 GHz WPAN/VHT systems under NLOS conditions: the advantages being higher spectral efficiencies and robustness to blockages (e.g., obstruction due to moving persons/objects) in indoor environments.

[0166] The perfect codes under ML decoding can provide coding gain in addition to ILL and FD. Decoding of perfect codes has been reported in the literature for only up to 5 antennas using sphere/lattice decoding as in reference [21]. The complexity of these decoders are prohibitive for decoding large sized perfect codes, although large sized codes are of interest from a high spectral efficiency view point. Further, because of its low complexity attribute, the proposed M-LAS detector is able to decode perfect codes of large dimensions. FIGS. 16 and 17, shows the simulated BER performance of perfect codes in comparison with those of ILL-only and FD-ILL STBCs for up to 32 transmit antennas using 1-LAS detector.

[0167] FIG. 16, shows uncoded BER comparison between perfect codes and ILL-only STBCs for different N_t=N_r and 4-QAM using 1-LAS detection. From FIG. 16, it can be seen that the 1-LAS detector achieves better performance for ILL-only STBCs than for perfect codes, when codes with small number of transmit antennas are considered (e.g., N_t=4, 6, 8). While perfect codes are expected to perform better than ILL-only codes under ML detection for any N_t, it is observed that the opposite behavior under 1-LAS detection for small N_t (i.e., performance for ILL only STBCs being better than that for perfect codes for small dimensions). This behavior could be attributed to the nature of the LAS detector, which achieves near-optimum performance only when the number of dimensions is large, and it appears that, in the detection process, LAS is able to more effectively disentangle the symbols in STBCs when δ=t=1 (i.e., in ILL-only STBCs) than in perfect codes. The performance gap between perfect codes and ILL-only STBCs with 1-LAS detection diminishes for increasing code sizes such that the performance for 32×32 perfect code and ILL-only STBC with 4-QAM are almost same and close to the SISO AWGN performance. In FIG. 17, we show a similar comparison between perfect codes, ILL-only and FD-ILL only STBCs when larger modulation alphabet sizes (e.g., 16-QAM) are used in the case of 16×16 and 32×32 codes. It can be seen that with higher order QAM like 16-QAM, perfect codes with 1-LAS detection perform poorer than ILL-only and FD-ILL STBCs, and that ILL-only and FD-ILL STBCs perform almost same and close to the SISO AWGN performance. The results in FIGS. 16 and 17 suggest that, with LAS detection, owing to the simplicity and good performance in using δ=t=1, ILL-only STBCs can be a good choice for practical large STBC MIMO systems.

[0168] The perfect CSIR assumption and estimate the channel matrix based on a training based iterative detection/channel estimation scheme is disclosed. In order to train the channel, a known training matrix X∈ (referred to as the pilot matrix) is transmitted. The pilot matrix is followed by N_d data STBC matrices X∈ i=1, 2, . . . , N_d. Consequently, a block of transmitted pilot and data matrices is of dimension N_t×N_t(1+N_d), and can be written as

  (57)

[0169] Let the transmit power be allotted to the pilot phase and data transmission phase in a block in the ratio

$\frac{\text{?}}{\text{?}}$ $\text{?}\text{indicates text missing or illegible when filed}$

such that

$\frac{\text{?}N\text{?}}{N_d}=1.$ $\text{?}\text{indicates text missing or illegible when filed}$

We impose a power constraint on the pilot matrix such that

$\text{?}\left(X\text{?}X\text{?}\right)=\frac{N\text{?}E\text{?}}{\text{?}}=\text{?}N_t.\text{?}\text{indicates text missing or illegible when filed}$

where

$\rho \stackrel{\Delta }{=}\frac{N_tE\text{?}\beta \text{?}}{\beta \text{?}}$ $\text{?}\text{indicates text missing or illegible when filed}$

and Es is the average energy of the transmitted symbol. The pilot matrix should be such that X^(P)X^(P)H=β1_N[26]. Let H_c∈ denote the channel matrix, which we want to estimate. We assume block fading, where the channel gains remain constant over one block consisting of (1+N_d)N_t channel uses, which can be viewed as the channel coherence time. This assumption can be valid in slow fading scenarios like BS-to-BS backbone connectivity and BS-to-CPE wireless IPTV distribution applications mentioned before. For this training based system and channel model, Hassibi and Hochwald have presented a lower bound on the capacity in [26]; we will illustrate the nearness of the performance achieved by the proposed iterative detection/estimation scheme to this bound. The received block is of dimension Nr×Nt(1+Nd), and can be expressed as

=[Y^(P)Y⁽¹⁾Y_c⁽²⁾Y]=H.  (58)

where
N_c=|N_iN . . . N_{is the Nr}×N_t (1+N_d) noise matrix and its entries are modeled as i.i.d.

$\mathrm{}\left(\text{?},{\sigma }^2=\frac{N_tE\text{?}}{\text{?}\beta \text{?}}\right).\text{?}\text{indicates text missing or illegible when filed}$

where γ is the average SNR per receive antenna. Equation (58) can be decomposed into two parts, namely, the pilot transmission part and the data transmission part, as

$\begin{array}{cc}Y_c^{\left(P\right)}=H_cX_{\text{?}}^{\left(P\right)}+N_{\text{?}}^{\left(P\right)}& \left(59\right)\\ \text{and}& \\ \begin{array}{c}Y\text{?}=\left[\begin{array}{cccc}{Y}_c^{\left(1\right)}& Y_c^{\left(2\right)}& \dots & Y_c^{\text{?}}\end{array}\right]\\ =H_c\left[\begin{array}{cccc}X\text{?}& X\text{?}& \dots & X\text{?}\end{array}\right]+\left[\begin{array}{cccc}{N}_c^{\left(1\right)}& N_c^{\left(2\right)}& \dots & N_c^{\left(N_d\right)}\end{array}\right]\end{array}& \left(60\right)\\ \text{?}\text{indicates text missing or illegible when filed}& \end{array}$

[0170] One method to detect the transmitted symbols with estimated channel coefficients is as follows:

• • [0171] 1) Estimate the channel gains via an MMSE estimator from the signal received during the first Nt channel uses (i.e., during pilot transmission); i.e., given Y(P)c and X(P)c, an estimate of the channel matrix H_c is found as

H_c^cet=√{square root over ()}Y_c^(P)(X_c^(P))^H[σ²I_Nt+μX_c^(P)(X_c^(P))^H]⁻¹  (61)

• • [0172] 2) Use the above H_c^cst in place of Hc in the M-LAS algorithm and detect the transmitted data symbols.

[0173] We refer to the above scheme as the ‘MMSE estimation scheme.’ In the absence of the knowledge of σ², a zero-forcing estimate can be obtained at the cost of some performance loss compared to the MMSE estimate. The performance of the estimator can be improved by using a cyclic minimization technique for minimizing the ML metric [22]

[0174] The proposed ‘iterative detection/estimation scheme’ works as follows:

• • [0175] 1) Obtain an initial estimate of the channel using the MMSE estimator in (61).
  • [0176] 2) Using the channel estimate, detect the data STBC matrices X_c⁽ⁱ⁾, i=1, 2, □ □ □, Nd using the M-LAS detector. Substituting these detected STBC matrices into (57), form .
  • [0177] 3) Re-estimate the channel using from the previous step, via

H_c=^H[σ^2H]⁻¹.  (62)

• • [0178] 4) Iterate steps 2 and 3 until convergence or for a specified number of iterations.

[0179] It can be seen that the complexity of obtaining the initial estimator (i.e., MMSE estimator) is O(Nt²) per symbol, and each estimation/detection iteration includes one M-LAS detection operation. Since the number of iterations is typically small (our simulations showed that the performance gain saturates beyond 4 iterations), the overall complexity order remains same as that of the M-LAS algorithm.

BER Performance with Estimated CSIR

[0180] We evaluated the BER performance of the M-LAS detector using estimated CSIR, where we estimate the channel gain matrix through the training based estimation schemes described in the above subsections. We consider the BER performance under three scenarios, namely, i) under perfect CSIR, ii) under CSIR estimated using the MMSE estimation scheme, and iii) under CSIR estimated using the iterative detection/estimation scheme. In the case of estimated CSIR, we show plots for 1P+1D and 1P+8D training, where by 1P+nD training we mean a training scheme with a block of size 1+n matrices, with 1 pilot matrix followed n data STBC matrices. For this 1P+nD training scheme, a lower bound on the capacity is given by [21]

$\begin{array}{cc}\text{?}\frac{T-\tau }{T}\left[\log \mathrm{de}\text{?}\left(I_{N_t}+\frac{\text{?}\tau }{N_t\left(1+{\beta }_d\right)+{\beta }_p\tau }\frac{H_cH_c^H}{N_c{\sigma }_{H_c}^2}\right)\right],\text{?}\text{indicates text missing or illegible when filed}& \left(63\right)\end{array}$

where T and τ, respectively, are the block size (i.e., channel coherence time) and pilot duration in number of channel uses, and

${\sigma }_{H\text{?}}^2=\frac{1}{N\text{?}N}\left[\text{?}H\text{?}H^H\text{?}\right]$ $\text{?}\text{indicates text missing or illegible when filed}$

where H=Ξ|H is the MMSE estimate of the channel gain matrix. We computed the capacity bound in (63) through simulations for 1P+8D and 1P+1D training for a 16×16 MIMO channel. For 1P+8D training T=(1+8)16=144, τ=16, and for 1P+1D training T=(1+1)16=32, τ=16. Also, in computing the bounds (shown in FIG. 19) and in BER simulations (in FIGS. 20 and 21), we have used the following pilot and data power allocation: for 1P+8D training

${\beta }_{\text{?}}=\frac{1}{2},R_d=1-\frac{\text{?}}{N_d}=1-\frac{1}{1\text{?}}=\frac{1\text{?}}{1\text{?}}{\beta }_{\text{?}}={\text{?}}_d=\frac{1}{2}.\text{?}\text{indicates text missing or illegible when filed}$

We note that improved capacity and BER performance can be achieved if the optimum power allocation derived in [21] is used instead of the above power allocation. In FIG. 19, we plot the computed capacity bounds, along with the capacity under perfect CSIR. We obtain the minimum SNR for a given capacity bound in (63) from the plots in FIG. 19, and show (later in FIG. 21) the nearness of the coded BER performance of the proposed scheme to this SNR limit.

[0181] In all the BER simulations with training, I_Nt is used as the pilot matrix. In FIG. 20, we plot the uncoded BER performance of 1-LAS detector when 1P+1D and 1P+8D training are used for channel estimation in a 16×16 ILL-only STBC MIMO system with Nt=Nr=16 and 4-QAM. BER performance with perfect CSIR is also plotted for comparison. From FIG. 20, it can be observed that, as expected, the BER degrades with estimated CSIR compared to that with perfect CSIR. For example, with 1P+1D training, both the MMSE estimation scheme as well as the iterative detection/estimation Scheme (with 4 iterations between estimation and detection) perform almost the same, which is about 5 dB worse compared to that of perfect CSIR at an uncoded BER of 10⁻³. This indicates that with 1P+nD training, iteration between detection and estimation does not improve performance much over the non-iterative scheme (i.e., the MMSE estimation scheme) for small n. With large n (e.g., slow fading), however, the iterative scheme outperforms the non-iterative scheme; e.g., with 1P+8D training, the performance of the MMSE estimation scheme improves by about 1 dB compared to 1P+1D training at 10⁻³ BER, whereas the improvement is about 2 dB for the iterative detection/estimation scheme.

[0182] In FIG. 21, we present the turbo coded BER of 1-LAS detector using estimated CSIR for the cases of 1P+8D and 1P+1D training. Simulations were done with rate-¾, ½ and ⅓ turbo codes, and the results for rate-¾ code are shown in FIG. 21. From FIG. 21, it can be seen that, compared to that of perfect CSIR, the estimated CSIR performance is worse by about 4.5 dB in terms of coded BER for 1P+8D training. Also, the vertical fall in coded BER occurs at about 4.2 dB away from the capacity bound for 1P+1D and 1P+8D training with MMSE estimation scheme. This nearness to capacity bound improves by about 0.5 dB for the iterative detection/estimation scheme. Finally, we note that for the system in FIG. 21 with parameters 16×16 ILL-only STBC, 4-QAM, rate-¾ turbo code, and 1P+8D training with T=144, τ=16, we achieve a high spectral efficiency of

$1\text{?}\times 2\times \frac{\text{?}}{4}\times \frac{8}{9}=21.3\text{bps/HZ}$ $\text{?}\text{indicates text missing or illegible when filed}$

even after accounting for the overheads involved in channel estimation (i.e., pilot matrix) and channel coding, while achieving good near-capacity performance at low complexity. This points to the suitability of the proposed approach of using M-LAS detection along with iterative detection/estimation in practical implementation of large STBC MIMO systems.

TABLE I
Proposed M-LAS Algorithm
1:	d  = By: z  = H  (y − Hd  G = H  H
2:	k = : k  number:
3:	= 2N  2N  for QAM and N  for PAM
4:	(1-symbol update starts here)
5:	for p = 1
6:	o p = ( G )  ?   ? = ? ?  indicates text missing or illegible when filed
7:	if (  =  )
8:	=  +
9:	if  > M − 1)  =  −  (d  k+1) − M + 1)
10:	if dp k+1) < −M + 1)  =  −  (d  k+1) + M − 1)
11:	end, end of if statement in step 7)
12:	Δ  =  −
13:	end; (end of for loop starting at step 4)
14:	=  Δ  = max
15:	if  = 0) goto Step 19: (1-symbol update local minima reached here)
16:	d  = d  +
17:	z  = z  −  (g  column of G)
18:	k = k+ 1. goto Step
19:	(2-symbol update starts here)
20:	for p = 1 to  , q = p + 1 to
21:	F  = [G]  = [  ]T
22:	≡  =
23:	Adjust  using Equ. (29)
24:	Δ  =  F  − 2  z
25:	end; (end of for loop starting at step 20)
26:	=  Δ
27:	Δ  = Δ
28:	if (Δ  < 0,
29:	z  = z  −  +
30:	d  = d  +  +
31:	d  = d  z  =
32:	goto Step 2
33:	end; (end of if statement in step 28)
34:	(3-symbol update starts here)
35:	for p = 1 to  , q = p + 1 to  , r = q + 1 to
36:	F  = [G]  z  =
37:	≡  = 2  F−1  z
38:	Adjust  using Equ. (29)
39:	Δ  =  F  − 2
40:	end. (end of for loop starting at line 35)
41:	=  Δ
42:	Δ  = Δ
43:	if (Δ  < 0)
44:	z  = z  − (  +  +  )
45:	d  = d  +  +  +
46:	d  = d  z  = z
47:	goto Step 2
48:	end; (end of if statement in step 43)
49:	Terminate Algorithm: d  is the detected output vector
indicates data missing or illegible when filed

[0183] A training based iterative LAS detection/channel estimation scheme and its BER performance is presented below.

[0184] In the considered training-based channel estimation scheme, transmission is carried out in frames, where one N_t×N_t pilot matrix (for training purposes) followed by N_d data STBC matrices are sent in each frame as shown in FIG. 22. One frame length, T, (taken to be the channel coherence time) is T=(N_d+1) N_t channel uses.

[0185] A frame of transmitted pilot and data matrices is of dimension N_t×N_t(1+N_d), which can be written as

X_c=└X_c^(P)X_c⁽¹⁾X_c⁽²⁾ . . . X_c^(Nd)┘  (64)

[0186] As in reference [21], let γ_p and γ_d denote the average SNR during pilot and data phases, respectively, which are related to the average received SNR γ as γ(N_d+1)=γ_p+N_dγ_d. Define

${\beta }_p\stackrel{\Delta }{=}\frac{{\gamma }_p}{\gamma },\mathrm{and}$ ${\beta }_d\stackrel{\Delta }{=}\frac{{\gamma }_d}{\gamma }.$

Let E_s denote the average energy of the transmitted symbol during the data phase. The average received signal power during the data phase is given by [tr(X_c⁽ⁱ⁾X_c^(i)H)]=N_t²E_s, and the average received signal power during the pilot phase is

$\left[\mathrm{tr}\left(X_c^{\left(P\right)}X_c^{{\left(P\right)}^H}\right)\right]=\frac{N_t^2E_s{\beta }_p}{{\beta }_d}=\mu N_t,$

where

$\mu \stackrel{\Delta }{=}\frac{N_tE_s{\beta }_p}{{\beta }_d}.$

For optimal training, the pilot matrix should be such that X_c^(P)X_c^(P)H=μI_Nt reference [21]. Let H_c∈ denote the channel matrix, which we want to estimate. We assume block fading, where the channel gains remain constant over one block consisting of (1+N_d)N_t channel uses, which can be viewed as the channel coherence time. This assumption can be valid in slow fading fixed wireless applications (e.g., as in possible applications like BS-to-BS backbone connectivity and BS-to-CPE wireless IPTV distribution). For this training-based system and channel model, Hassibi and Hochwald presented a lower bound on the capacity in reference [21]; we will illustrate the nearness of the performance achieved by the iterative detection/estimation scheme to this bound. The received block is of dimension N_r×N_t(1+N_d), and can be written as

Y_c=└Y_c^(P)Y_c⁽¹⁾Y_c⁽²⁾ . . . Y_c^(Nd)┘=H_cX_c+N_c,  (65)

where N_c=└N_c^(P)N_c⁽¹⁾N_c⁽²⁾ . . . N_c^(Nd)┘ is the N_r×N_t(1+N_d) noise matrix and its entries are modeled as i.i.d.

$\mathrm{C}\left(0,{\sigma }^2=\frac{N_tE_s}{{\mathrm{\gamma \beta }}_d}\right).$

Equation (65) can be decomposed into two parts, namely, the pilot matrix part and the data matrices part, as

Y_c^(P)=H_cX_c^(P)+N_c^(P),  (66)

Y_c^(D)=└Y_c⁽¹⁾Y_c⁽²⁾ . . . Y_c^(Nd)┘=H_c└X_c⁽¹⁾X_c⁽²⁾ . . . X_c^(Nd)┘+└N_c⁽¹⁾N_c⁽²⁾ . . . N_c^(Nd)┘.  (65)