Printer Friendly

Efficiency improvement of the fixed-complexity sphere decoder.

1. Introduction

Multiple-input multiple-output (MIMO) spatial multiplexing techniques linearly increase the channel capacity without requiring additional spectral resources which are not only expensive but also scarce [1]. At the transmitter side, signals are transmitted simultaneously from sufficiently-separated antennas, whereas at the receiver side signals are recovered by means of detection algorithms.

The maximum-likelihood detector (MLD) is the optimum receiver for MIMO spatial multiplexing systems [2]. Nevertheless, MLD becomes infeasible for systems employing large number of transmit antennas and high order modulations due to its exponential complexity increase. Therefore, suboptimal detection schemes were proposed in the literature to achieve a tradeoff between performance and complexity as below.

Linear detection schemes including zero-forcing (ZF) and minimum mean square error (MMSE) treat the received signal by the pseudo-inverse and a regularized pseudo-inverse of the channel matrix, respectively. Although linear detection schemes are simple in terms of computational complexity, they lead to degradation in the performance due to the independent processing of the transmitted signals [3].

Successive interference cancellation (SIC) schemes detect signals iteratively, where already-detected signals are subtracted out from the received vector leading to a system with fewer interferers. ZF and MMSE VBLAST (vertical Bell Laboratories layered space-time) detection schemes [2], which are the first proposed SIC schemes, outperform linear algorithms. Nonetheless, VBLAST detection schemes have high computational complexity because of requiring a matrix pseudo-inversion at each iterative detection stage. Low complexity SIC detection algorithms based on the QR decomposition (QRD) of the channel matrix were proposed in the literature [4][5][6]. Although QRD-based SIC schemes are favorable in terms of computational complexity, their performance is still far from the optimum performance of the MLD.

Several detection algorithms have been proposed in the literature achieving quasi-ML performance while requiring lower computational complexity. Among these suboptimal algorithms, sphere decoding (SD) achieves quasi-ML performance with polynomial average computational complexity [7]. It is shown; however, that SD has variable complexity which depends on the channel condition and the instantaneous noise power, where the worst-case complexity of SD is consequently comparable with that of MLD [8][9]. That is, the extreme-case complexity of SD is exponential. Also, in terms of implementation complexity, SD is inefficient due to its sequential nature in the tree search stage that limits the possibility of pipelining, where consequently the detection latency is increased [10][11].

To overcome the two aforementioned drawbacks of SD, fixed-complexity sphere decoder (FSD) was proposed in [10][11][12]. Analysis on the error performance of the FSE was introduced in [13]. The main idea of the FSD is to perform the search over a fixed number of hypotheses of the transmitted vector independently of the noise power and the channel condition. The complexity of FSD is, therefore, fixed and known prior to the tree search phase of the detection algorithm. Moreover, the hypotheses are tested in parallel leading to reduction in the algorithm latency, i.e., increase in the detector throughput. To achieve a quasi-ML performance, FSD requires a specific signal ordering in which signals suffering from the highest noise amplification are detected in levels where all signal candidates are retained. As a consequence, weak signals don't affect the performance of the detection algorithm. The conventional VBLAST algorithm is, therefore, used to obtain accurate signal ordering [14]. Despite that VBLAST ordering algorithm obtains a precise signal ordering, its complexity is shown to be O([N.sup.4]), with N as the number of transmit antennas. This is computationally heavy when signal ordering is frequently performed [15].

Our original contributions: In this paper, we propose two schemes to reduce the complexity of FSD algorithm in the ordering and tree-search phases as follows [16]:

* QRD-based FSD signal ordering: In the ordering stage, we propose to embed the signal ordering required by the FSD in the QRD. Thus, the proposed ordering scheme requires a few additional complex multiplications and additions compared to the unsorted QRD algorithm with negligible degradation in the performance. Therefore, the proposed ordering scheme requires only a small fraction of the computational effort required by the conventional FSD-VBLAST sorting algorithm. ZF and MMSE performance-based criteria are used in the proposed FSD-ZF-SQRD and FSD-MMSE-SQRD, respectively, where SQRD refers to sorted QR decomposition.

* Analysis of the computational complexity: We give analytical formulas for the computational complexities of the conventional and proposed ordering schemes.

* Threshold-based complexity reduction: In the tree-search stage, based on the reliability of the weakest received signal, i.e., signal with the lowest received signal to noise ratio (SNR), the number of retained symbol replicas is controlled. Thus, when the received SNR of the weakest signal is larger than a pre-defined threshold, unnecessary computations by the FSD are avoided while achieving a quasi-ML performance.

The rest of this paper is organized as follows. In section II, we introduce the system model and review the FSD. In section III, we introduce the proposed FSD-ZF-SQRD and FSD-MMSE-SQRD schemes, and in section IV we derive the formulas for the computational complexities of the introduced sorting algorithms. In section V, threshold-based complexity reduction scheme is proposed. Simulation results are shown in section VI, and conclusions are drawn in section VII.

2. System Description and Review of the FSD

We consider a MIMO multiplexing system employing N transmit and M receive antennas, where M [greater than or equal to] N. Under the assumption of narrowband flat-fading channel, the received vector r [member of] [C.sup.Mx1] is given by:

r = Hx + n, (1)

where x [member of] [C.sup.Nx1] is the transmitted vector whose elements are drawn from the modulation set [OMEGA] satisfying E[xx*] = [I.sub.N], where [I.sub.N] is the NxN identity matrix. n [member of] [C.sup.Mx1] is the additive white Gaussian noise with zero mean and unity variance. H [member of] [C.sup.MxN] is the channel matrix whose row-column element [h.sub.i,j] the complex channel coefficient between the j-th transmit and i-th receive antennas, is modeled as circularly symmetric complex Gaussian random variable with zero mean and unity variance.

Working on x, the matrix H generates the lattice

[DELTA](H) = {Hx :x[member of][[OMEGA].sup.N]}, (2)

where the columns of H, i.e., ([h.sub.1], [h.sub.2], ..., [h.sub.N]), are the bases of the lattice. The received vector r is then represented as the lattice point Hx perturbed by the noise vector n. As a consequence, the MLD finds the closest lattice point Hx to the received vector r, where x is the estimate of the transmitted vector x. That is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

SD restricts the search in (3) to the lattice points that reside in the hyper-sphere of radius d and centred at the received vector r. Therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

To perform the search in (4) successively, the channel matrix H is factorized into the multiplication of a unitary matrix Q and an upper triangular matrix R.

[FIGURE 1 OMITTED]

Therefore, the search problem in (4) is simplified to:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

where y = [Q.sup.H] r. The accumulative metric in (5) is then calculated successively, where the metric at the N-th detection level is given by:

[E.sub.N] = [([y.sub.N] - [R.sub.N,N][[??].sub.N]).sup.2], (6)

and the accumulative metric at the (N-1)-th detection level is given as follows:

[E.sub.N-1] = [E.sub.N] +([y.sub.N-1] - [R.sub.N-1,N-1] [[??].sub.N-1] - [R.sub.N-1,N][x.sub.N]).sup.2], (7)

and so on.

Although the average complexity of SD is known to be polynomial, its extreme-case complexity is believed to be exponential, particularly for high noise power and when the channel matrix is ill-conditioned. Also, due to the sequential nature of the SD, it can't be pipelined leading to high latency in the detection algorithm.

To overcome the aforementioned problems of the SD, FSD was proposed by Barbero et al. FSD achieves a quasi-ML performance by performing the following two-stage tree search:

* Fixed expansion stage: In the first p detection levels, a full expansion of the retained nodes is performed, where all the resulting branches are retained for the next levels.

* Single expansion stage: All retained branches in the precedent level are extended independently to all possible nodes. The accumulative metrics of the resulting branches are calculated as in (5), and only the branch with the smallest accumulative metric is retained for the next level. This can be done using Schnorr-Euchner strategy [17], where only the metric of the node with the smallest accumulative metric is calculated.

Fig. 1 shows an example of the FSD for quadratic phase shift keying (QPSK) signalling, N = 3, and p = 1. Each node represents a constellation point belonging to the QPSK constellation set [OMEGA] = At the 3rd level, all the symbol replica candidates for [x.sub.3] are retained for the next detection levels, and the metric of each node, given inside the node in Fig. 1, is calculated as in (6). At the 2nd level, each retained node at the precedent level is extended independently from others, and the best child node is selected such that the accumulative metric is minimized. This strategy is repeated up to the 1st level, where the node with the smallest accumulative metric and its connected nodes are considered as the final estimate of the transmitted vector. For the example in Fig. 1, [??] = and is indicated by the thick branches and nodes.

Because all possible symbol candidates are retained in the first p levels, the reliability of signals does not affect the final detection performance. Therefore, signals with the least robustness are detected in the full expansion stage. On the other hand, in the remaining (N - p) levels, signals are sorted based on their reliability, where signals with the least noise amplification are detected first.

In the conventional FSD, VBLAST signal sorting is iteratively used to decide the order in which signals are detected. Although reduced complexity VBLAST ordering schemes were proposed in the literature [15][18], it is still complex compared to other QRD-based signal sorting schemes.

In the following section, we propose a low-complexity ordering scheme that achieves the required performance while reducing the computational complexity. Also, computational complexity comparison among different ordering schemes is performed.

3. Proposed QRD-based FSD Signal Ordering Schemes

In the pre-detection stage, the channel matrix is decomposed into the multiplication of a unitary matrix Q and an upper triangular matrix R. Due to the structure of the upper triangular matrix R, the detection is performed successively starting by the last component of the vector x, i.e., [x.sub.N]. In the conventional QR-decomposition, the diagonal elements of R are obtained in opposite order of signal detection. In the sorted QR-decomposition (SQRD), the columns of the channel matrix are reordered prior to each orthogonalization step, where [R.sub.1,1] is minimized over all the columns of the channel matrix, followed by [R.sub.2,2], and so on. Unfortunately, the SQRD does not sort signals in the order required by FSD.

In FSD, the efficient VBLAST algorithm is used to obtain the signal ordering prior to the QR-decomposition of the channel matrix. Despite that FSD achieves a quasi-ML performance using VBLAST ordering, the computational effort required by the ordering stage becomes exhaustive as the channel varies rapidly, where ordering is performed frequently.

The main idea of the proposed signal ordering algorithm is to obtain the (p+1)th minimum diagonal element of R prior to the orthogonalization step. Now, let p = 1, then [R.sub.1,1] is simply the norm of the channel matrix column whose order is the second in the norm sense. So, the column of H with the 2nd minimum norm is permuted with the first column. Thereafter, [R.sub.2,2] is computed in the same manner by considering only the remaining (N-1) columns, etc. At the last iteration, the order of signal detection is same as that required by FSD algorithm.

Fig. 2 depicts an example of the proposed FSD-SQRD for p = 1, where p is the permutation vector. At the first iteration, the column with the 2nd minimum norm is permuted with the first column of H and the remaining (N-1) vectors are orthogonalized. In the next iteration, the orthogonalized column with the 2nd minimum norm is permuted with the first remaining orthogonalized column. At the [(N - 1).sup.th] iteration, the remaining two columns correspond to the strongest and the weakest signals, i.e., the largest and the smallest received signal to noise ratio (SNR), respectively. Thus, the selected column corresponds to the signal with the largest SNR and the remaining one corresponds to the weakest signal. By doing so, the required order by FSD is obtained.

The introduced FSD signal sorting scheme is applied with the ZF and the MMSE performance-based criteria in the proposed FSD-ZF-SQRD and FSD-MMSE-SQRD algorithms, respectively. To apply the FSD-MMSE-SQRD, the channel matrix is extended to take into consideration the noise effect; that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

Table 1 gives a detailed algorithmic description of the proposed FSD-MMSE-SQRD algorithm where the input n equals (p + 1). [0.sup.N] is the NXNmatrix whose elements are all zeros, and mink is the k-th minimum. The FSD-ZF-SQRD is obtained by simply replacing [H.sub.ext] by H, and line (7) in Table 1 by the following line.

(7) Exchange columns i and ki in Q, R, norm, and p.

4. Analysis on the Computational Complexity

In this section, the computational complexities of the introduced signal ordering schemes are investigated. The complex floating points (flops) are given as a function of N and M, where the complex addition and multiplication operations are counted as one and three flops, respectively. Other operations are tracked back to the complex operations. For instance, real addition requires half a flop.

Table 2 gives the formulas for the computational complexities of the aforementioned signal sorting schemes. Hassibi's sorting scheme is a low complexity VBLAST algorithm used herein for comparison [6] and the assorted-ZF-QRD refers to the zero-forcing QRD without signal ordering.

[FIGURE 2 OMITTED]
Table 1. The proposed FSD-MMSE-SQRD algorithm.

Input: R = [0.sub.N], Q = [H.sub.ext], p = [1,2, ... N], n

1: for i = 1 to A^ do
2:   [norm.sub.i] = [||[q.sub.i]||.sup.2]
3: end for
4: for i = 1 to N do
5:   k = min (". Ar - i + 1)
6:   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
7:   Exchange columns i and [k.sub.i] in R, norm, and p, and in
     the first (M + i -1) rows of Q
8:   [R.sub.i,i]
9:   [q.sub.i] = [q.sub.i]/[R.sub.i,i]
10:  for j = i + 1 to N do
11:       [R.sub.i,j] = [q.sup.H.sub.i] [q.sub.j]
12:       [q.sub.i] = [q.sub.j] - [R.sub.i,j] * [q.sub.i]
13:       [norm.sub.j] = [norm.sub.j] - [R.sup.2.sub.i,j]
14:    end for
15: end for
Output: Q. R, p


[FIGURE 3 OMITTED]

Fig. 3 shows the computational complexities of the proposed algorithms with the conventional ones. Clearly, the proposed algorithms require much lower computational efforts compared to Hassibi's scheme. For instance, in 8X8 MIMO system, the proposed FSD-ZF-SQRD and FSD-MMSE-SQRD only require 19.5% and 26.3%, respectively, of the computational efforts required by Hassibi's scheme. The proposed signal sorting algorithms require only 1.25 x ([N.sup.2] - N) additional flops compared to the assorted algorithms, i.e., without signal ordering.

The complexity of the conventional norm sorting FSD-norm is considered to be equivalent to that of the assorted QRD algorithm.

5. Threshold-based Complexity Reduction for the FSD

The first detected signal in the FSD, i.e., [x.sub.N], is the signal that suffers the largest noise amplification. Therefore, all the remaining (N-1) signals are more robust than the first ranked signal. Thus, if xN experiences low noise amplification, the number of retained symbol replica candidates can be reduced without affecting the final performance. In contrast to the common adaptive symbol replica selection proposed in [19], FSD can have more reliable decision about the number of retained symbol replicas because its decision is based on the reliability of the signal suffering the largest noise amplification, whereas the algorithm in [19] does not take into consideration the weak signals.

Due to the structure of the matrix R, the signal [x.sb.N] is interference-free, therefore, the robustness of the signal is directly proportional to |[R.sub.N,N]|. Thus, based on the value of |[R.sub.N,N]|, we decide the number of retained symbol replicas at the first full expansion stage. To accomplish that, we introduce three threshold vectors and the corresponding number of retained symbol replicas for the first full expansion level as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

Due to the fact that

P{[R.sub.N,N] [less than or equal to] 0.4} <P {[R.sub.N,N] [less than or equal to] 0.5} <P {[R.sub.N,N] [less than or equal to] 0.75}, (12)

more complexity reduction can be achieved when the threshold vector [p.sub.3] is used as compared to the case of using the threshold vector [P.sub.2] or [P.sub.1]. This is because the three aforementioned probabilities in (12) are the cases in which the proposed approach fails to achieve any complexity reduction using [P.sub.3], [P.sub.2], and [P.sub.1], respectively. Note that we obtained the threshold vectors using intensive simulations. In practice, the channel models are usually known, which indicates that an offline optimization of these threshold vectors is possible. Another alternative is to compute the probability density function (pdf) of [R.sub.N,N] and set the threshold vector as a trade-off between complexity reduction and performance degradation. The later option is suitable for systems that have preambles. These preambles can be used in the training phase to obtain optimized values of the threshold vector.

6. Simulation Results and Discussions

In this section, we investigate the bit error rate (BER) performance of the FSD in 4X4 MIMO spatial multiplexing system. Transmitted symbols are modulated using 4-QAM, 16-QAM, or 64-QAM mappers. The channel state information (CSI) is considered to be perfectly known at the receiver and unknown at the transmitter.

Fig. 4 shows the BER performance of the FSD for different signal ordering schemes in a 4x4 MIMO system using 4-QAM modulation. Without signal ordering, the performance of FSD is highly degraded and the diversity order, i.e., the slope of the BER curve, is lower than that of SD. When applying FSD-norm signal ordering, the BER performance is improved by approximately 2.7dB at BER of 10-4 whereas no improvement in the diversity order is achieved. On the other hand, when FSD-VBLAST ordering is applied, FSD algorithm achieves the same diversity order of SD with a 0.2dB performance lagging at BER = [10.sup.-4]. When the proposed FSD-ZF-SQRD signal ordering is employed, FSD attains the diversity order of SD with a degradation of less than 0.6dB compared to SD at BER of [10.sup.-4]. At the same target BER, FSD lags the optimum performance by only 0.4dB when the proposed FSD-MMSE-SQRD sorting algorithm is employed. This small degradation in the BER performance is tolerable considering the low computational complexity of the proposed algorithms compared with the conventional FSD-VBLAST signal ordering. Due to space limitation, we consider the proposed FSD-ZF-SQRD for the following comparisons.

Fig. 5 depicts the performance of the FSD employing the proposed FSD-ZF-SQRD algorithm using different QAM schemes. At BER of 10-4, a degradation of 0.6dB, 0.3dB, and 0.25dB are remarked in the BER performance of the FSD when employing FSD-ZF-SQRD in a 4x4 system using 4-QAM, 16-QAM, and 64-QAM, respectively. That is, as the modulation order increases, the degradation due to the use of the proposed FSD-SQRD algorithms vanishes compared with the performance of FSD employing the complex FSD-VBLAST sorting scheme.

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

Fig. 6 shows the BER performance of the FSD when the number of retained symbol replicas at the first detection level is controlled by the threshold vectors [P.sub.1], [P.sub.2], or [P.sub.3]. In the case of using [P.sub.1], the complexity reduction does not have any effect on the achieved performance of FSD for the different applied modulation schemes. By contrast, when the threshold vector [P.sub.2] is used, the performance of FSD using 4-QAM is degraded at medium Eb/No values, whereas the performance is still intact when 16-QAM or 64-QAM is used.

Therefore, the vector [P.sub.3], which is tighter than [P.sub.1] and [P.sub.2], is not used with 4-QAM signalling scheme. In the case of using [P.sub.3], we remark a slight degradation in the BER performance when 16-QAM or 64-QAM is used. For instance, at BER of [10.sup.-3], the maximum degradation is about 0.5dB and 0.3dB for 16-QAM and 64-QAM, respectively. This degradation in the performance is tolerable due to the remarkable reduction in the computational complexity.

Table 3 gives the achieved percentage of reduction in the computational complexity of FSD for different modulation schemes and threshold vectors. When the threshold vector [P.sub.1] is used, about 12% of complexity reduction is achieved for all modulation schemes. On the other side, when [P.sub.2] is used, the reduction in the complexity of FSD increases as the modulation order increases attaining 31.1% reduction in the case of 64-QAM. In the case of [P.sub.3], 37.14% and 46.33% of the computational efforts required by the conventional FSD are avoided when 16-QAM and 64-QAM are used, respectively.

We conclude that for high modulation orders, the set of candidates for each symbol becomes large. Therefore, when we apply a high complexity reduction, e.g., using [P.sub.3], there will still be enough retained candidates to obtain a quasi-ML solution. However, in the case of low modulation orders, e.g., QPSK, when the threshold vector [P.sub.3] is applied, there will be a few retained candidates at each detection level. These retained candidates might not be sufficient to obtain a quasi-ML performance.

7. Conclusions

In this paper, we proposed two techniques to reduce the computational complexity of FSD in the ordering and tree search stages, respectively. In the ordering stage, we proposed QRD-based FSD signal ordering scheme (FSD-SQRD) that leads to quasi-ML performance while requiring only a fraction of the computational complexity of the conventional FSD-VBLAST ordering algorithm. The proposed ordering algorithm is then extended to the MMSE case, where better performance is obtained. In the tree-search stage, we introduced a complexity reduction approach for FSD algorithm based on the reliability of the signal with the lowest received SNR value. That is, if the lowest SNR of the received signals is higher than a pre-defined threshold, the number of retained symbol replicas is reduced leading to the reduction in the computational complexity of the FSD algorithm with negligible degradation in the BER performance. The proposed improvements for FSD remarkably reduce the computational efforts required to achieve quasi-ML performance. As a consequence, FSD can be considered as a prominent detection scheme for next generation communication systems.

Received November 25, 2010; revised January 14, 2011; accepted February 5, 2011; published March 31, 2011

References

[1] E. Telatar, "Capacity of multi-antenna Gaussian channels," European Transactions on Telecommunications, vol. 10, pp. 585-595, Dec. 1999. Article (CrossRef Link)

[2] W. Van Etten, "Maximum likelihood receiver for multiple channel transmission systems," IEEE Transactions on Communications, pp. 276-283, Feb. 1976. Article (CrossRef Link)

[3] Q. H. Spencer et al., "An introduction to the multi-user MIMO downlink," IEEE Communications Magazine, vol. 42, no. 10, pp. 60-67, Oct. 2004. Article (CrossRef Link)

[4] D. Shiu and J. Kahn, "Layered space-time codes for wireless communications using multiple transmit antennas," in Proc. the International Conference on Communications, Vancouver, Canada, pp. 436-440, Jun. 1999. Article (CrossRef Link)

[5] D. Wubben et al., "Efficient algorithm for decoding layered space-time codes," Electronics Letters, vol. 37, no. 22, pp. 1348-1350, Oct. 2001. Article (CrossRef Link)

[6] D. Wubben et al., "MMSE extension of V-BLAST based on sorted QR decomposition," in Proc. IEEE Vehicular Technology Conference, Lake Buena Vista, USA, pp. 508-512, Oct. 2003. Article (CrossRef Link)

[7] E. Agrell et al., "Closest point search in lattices," IEEE Transactions on Information Theory, vol. 48, no. 8, pp. 2201-2214, Nov. 2002. Article (CrossRef Link)

[8] B. Hassibi and H. Vikalo, "On the expected complexity of sphere decoding," in Proc. Asilomar Conference on Signals, Systems and Computers, Pacific Grove, USA, pp. 1051-1055, Nov. 2001. Article (CrossRef Link)

[9] J. Jalden and B. Ottersten, "On the complexity of sphere decoding in digital communications," IEEE Transactions on Signal Processing, vol. 53, no. 4, pp. 1474-1484, Apr. 2005. Article (CrossRef Link)

[10] L. Barbero and J. Thompson, "Fixing the complexity of the sphere decoder for MIMO detection," IEEE Trans. on Wireless Communications, vol. 7, no. 6, pp. 2131-2142, Jun. 2008. Article (CrossRef Link)

[11] L. Barbero and J. Thompson, "Extending a fixed-complexity sphere decoder to obtain likelihood information for turbo-MIMO systems," IEEE Trans. on Vehicular Technology, vol. 57, no. 5, pp. 2804-2814, Sep. 2008. Article (CrossRef Link)

[12] J. Jalden et al., "Full diversity detection in MIMO systems with a fixed-complexity sphere decoder," in Proc. of IEEE International Conference on Acoustics, Speech, and Signal Processing, Honolulu, USA, pp. 49-52, Apr. 2007. Article (CrossRef Link)

[13] J. Jalden et al., "The error probability of the fixed-complexity sphere decoder," IEEE Trans. On Signal Processing, vol. 57, no. 7, pp. 2711-2720, Jul. 2009. Article (CrossRef Link)

[14] P. Wolniansky et al., "V-BLAST: An architecture for realizing very high data rates over the rich-scattering wireless channel," in Proc. URSI International Symposium on Signals, Systems, and Electronics, Pisa, Italy, pp. 295-300, Oct. 1998. Article (CrossRef Link)

[15] B. Hassibi, "An efficient square-root algorithm for BLAST," in Proc. IEEE International Conf. Acoustics, Speech, Signal Processing, Istanbul, Turkey, pp. 737-740, Jun. 2000. Article (CrossRef Link)

[16] M. Mohaisen and K.H. Chang, "On improving the efficiency of the fixed-complexity sphere decoder," in Proc. IEEE VTC--Fall, Sep. 2009, Session 3B-1. Article (CrossRef Link)

[17] C. Schnorr and M. Euchner, "Lattice basis reduction: Improved practical algorithms and solving subset sum problems," Mathematical Programming, vol. 66, pp. 181-199, Sep. 1994. Article (CrossRef Link)

[18] H. Zhu, Z. Lei and F. P. S. Chin, "An improved square-root algorithm for BLAST," IEEE Signal Processing Letters, vol. 11, no. 9, pp. 772-775, Sep. 2004. Article (CrossRef Link)

[19] K. J. Kim et al., "AQRD-M/Kalman filter based detection and channel estimation algorithm for MIMO-OFDM systems," IEEE Transactions on Wireless Communications, vol. 4, no. 2, pp. 710-721, Mar. 2005. Article (CrossRef Link)

DOI: 10.3837/tiis.2011.03.002

Manar Mohaisen and KyungHi Chang

The Graduate School of IT & T, Inha University 402-751 Incheon, Republic of Korea [e-mail: manar.subhi@kut.ac.kr, khchang@inha.ac.kr]

This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MEST) (No. R01-2008-000-20333-0). Part of this paper is presented at IEEE VTC-Fall, 2009.

Manar Mohaisen received a B.Eng. in electrical engineering from the University of Gaza (IUG), Gaza, Palestine, in 2001. From 2001 to 2004, he was with the Palestinian Telecommunications Company--JAWWAL, Gaza, Palestine, where he worked as an operation and maintenance engineer, and then as a cell planning engineer. He received his M.S. degree in communication and signal processing from the University of Nice-Sophia Antiplois, Sophia Antipolis, France, in 2005. From March to September 2005, he followed an internship at IMRA Europe Co., Sophia Antipolis, France, as a part of his M.S. degree, where he worked on noise reduction in car environments. In February 2010, he obtained a Ph.D. degree from the Graduate School of Information Technology and Telecommunication, Inha University, Incheon, Korea. Since September 2010, he is with the School of Information Technology Engineering, Korea University of Technology and Education (KUT), Cheonan, where he is an assistant professor. His research interests include 3GPP LTE/LTE-A systems, detection schemes for spatial multiplexing MIMO systems, and precoding techniques for multiuser MIMO systems.

KyungHi Chang received his B.S. and M.S. degrees in electronics engineering from Yonsei University, Seoul, Korea, in 1985 and 1987, respectively. He received his Ph.D. degree in electrical engineering from Texas A&M University, College Station, Texas, in 1992. From 1989 to 1990, he was with the Samsung Advanced Institute of Technology (SAIT) as a member of research staff and was involved in digital signal processing system design. From 1992 to 2003, he was with the Electronics and Telecommunications Research Institute (ETRI) as a principal member of technical staff. During this period, he led the design teams working on the WCDMA UE modem and 4G radio transmission technology (RTT). He is currently with the Graduate School of Information Technology and Telecommunications, Inha University, where he has been a professor since 2003. His current research interests include RTT design for IMT-Advanced system, 3GPP LTE and M-WiMAX system design, cognitive radio, cross-layer design, cooperative relaying systems, RFID/USN, and mobile ad-hoc networks. Dr. Chang has served as a senior member of IEEE since 1998, and as an editor-in-chief of the Korean Institute of Communication Sciences (KICS) proceedings during 2007~2009. Currently, he is an editor-in-chief of the KICS Journal A. He has also served as an editor of ITU-R TG8/1 IMT.MOD, and he is currently an international IT standardization expert of the Telecommunications Technology Association (TTA). He is an recipient of the LG Academic Awards (2006), Haedong Best Paper Awards (2007), IEEE ComSoc Best Paper Awards (2008), and Haedong Academic Awards (2010).
Table 2. Computational complexities of the sorting schemes.

Ordering scheme   Complexity (flops)

Hassibi's         6[N.sup.3] + 12[N.sup.2] M + 40/3 [N.sup.2]
                    + 4NM + 39/2 n - 7M - 30
FSD-MMSE-SQRD     4/3 [N.sup.3] + 4[N.sup.2] M + 5/4 [N.sup.2]
                    - NM - 13/12 N
FSD-ZF-SQRD       4[N.sup.2] M + 3/4 [N.sup.2] -NM - 3/4 N
Assorted ZF-QRD   4[N.sup.2] M - 1/2 [N.sup.2] - NM + 1/2 N

Table 3. Achieved reduction in the complexity of FSD by the
proposed threshold-based approach in a 4x4 MIMO system.

            Reduced Computational Complexity (%)

Threshold      4-QAM      16-QAM   64-QAM

[P.sub.1]      12.04      12.08    12.09
[P.sub.2]      28.03      30.52    31.10
[P.sub.3]   Not applied   37.14    46.33
COPYRIGHT 2011 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Mohaisen, Manar; Chang, KyungHi
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:Mar 1, 2011
Words:5132
Previous Article:A bandwidth adaptive path selection scheme in IEEE 802.16 relay networks.
Next Article:Interference-aware downlink resource management for OFDMA femtocell networks.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters