Ordered successive noise projection cancellation algorithm for dual lattice-reduction-aided MIMO detection

Liu Jinzhu Xing Song Shen Lianfeng

(1National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China)

(2School of Electronic & Information Engineering, Nanjing University of Information Science & Technology, Nanjing 210044, China)

(3Department of Information Systems, California State University, Los Angeles, CA 90032, USA)

Among various detection schemes for the multi-input multi-output (MIMO) wireless communication systems, the maximum likelihood (ML) MIMO detector provides optimal detection performance, but its computational complexity increases exponentially when numbers of transmit antennas increase[1]. The reduced-complexity detection algorithms, which are not at all optimal, can be classified as linear and nonlinear detectors. The conventional linear zero forcing (ZF)/minimum-mean-squared-error (MMSE) detectors, for example, typically exhibit a low complexity. The nonlinear ordered successive interference cancellation (OSIC) algorithm which detects each symbol sequentially via classic remodulation and subtraction based canceling operations demonstrates its excellent trade-off between computational complexity and error performance. However, all these suboptimal schemes perform significantly worse than the optimal ML detector[2-4].

Recently, the lattice reduction (LR) has been introduced as a promising technique which can improve the performance of many suboptimal MIMO detectors[5]. Particularly, the OSIC-based LR-aided MIMO detection scheme can achieve full diversity and present near optimal detection performance with acceptable complexity[6]. In MIMO detection applications, LR can aim at the primal lattice which is generated by the channel gain matrix, and the corresponding detection scheme is called the primal LR (PLR)-aided MIMO detection. Correspondingly, the dual LR (DLR)-aided MIMO detection is also feasible, which features that the dual lattice basis, i.e., the Moore-Penrose (MP) inverse of the channel gain matrix, is reduced in the detection procedure[6]. Moreover, in particular scenarios the DLR-aided detection is preferable due to its low computational complexity and/or good performance[6-7].

Nevertheless, the complexity of the traditional OSIC-based MIMO detection scheme (also referred to as the VBLAST algorithm) is still considerably high due to its repeated inverse calculations of the successive deflated channel gain matrix[3]. Specifically, when the OSIC algorithm is used in DLR-aided detections, the overall complexity will be further increased. This is due to the fact that the successive interference cancellation is carried out at the primal lattice side. While what is obtained by the DLR is the reduced dual lattice basis, the MP inverse must be still calculated[6].

In this paper, we propose a novel nonlinear MIMO detection algorithm to improve the performance of the MIMO detector with the conventional OSIC algorithm. Unlike the OSIC algorithm in which the known interferences in the input signal vector are successively cancelled, the proposed algorithm successively cancels the noise projections from the decision statistic vector. Hence we refer to our algorithm as an ordered successive noise projection cancellation (OSNPC) algorithm. Theoretical analysis and simulation results show that the OSNPC algorithm is equivalent to the traditional OSIC algorithm in performance, but it has significantly less complexity in computation. Furthermore, when it is applied to the DLR-aided MIMO detection, the computational complexity is even more reduced due to the avoidance of the inverse of the reduced basis of the dual lattice.

1 OSIC-Based LR-Aided MIMO Detection

Consider a MIMO wireless communication system consisting ofNtransmitters andMreceivers (M≥N). The relationship between theN-dimensional transmitted complex symbol vectorsand theM-dimensional received vectorxis determined by

x=As+w

(1)

whereA∈CM×Nis a complex matrix with full column rank, which presents a flat-fading channel gain matrix; andwis the additive complex noise vector.

1.1 OSIC-based PLR-aided MIMO detection

A complex-valued lattice generated byAis defined as

L(A)={Az,z∈ZN+iZN}

(2)

The columns ofAform a basis of the latticeL(A). The reduced basis ofL(A),A′=AU, can be obtained by using an LR algorithm such as LLL[8]or SA[9], whereUis a unimodular matrix.

Fig.1 OSIC-based PLR-aided MIMO detection scheme

1.2 OSIC-based DLR-aided MIMO detection

LetB∈CN×Mbe the Moore-Penrose (MP) inverse ofA, i.e.,

B=A?=(AHA)-1AH

(3)

whereAHdenotes the Hermitian ofA, and the notation (·)?indicates the MP inverse of a matrix. The dual lattice of the primal latticeL(A)can be defined as

L(B)={zTB,z∈ZN+iZN}

(4)

Accordingly, the rows ofBform a basis of the latticeL(B). The reduced basis ofL(B),B′=VB, can be obtained by using the LR algorithm such as dual LLL or SA[6-7], whereVis a unimodular matrix.

Fig.2 OSIC-based DLR-aided MIMO detection scheme

2 OSNPC Algorithm and OSNPC-Based DLR-Aided MIMO Detection

2.1 OSIC algorithm review

First, we briefly review the OSIC algorithm[3]in the LR-aided MIMO detection. As mentioned above, the transformed symboldcan be detected fromx=A′d+win PLR-aided detection (or fromx=B′?d+win DLR-aided detection) by using the OSIC algorithm, which is described as follows.

1) ComputeA′?, the MP inverse ofA′. LetB′=A′?, then multiplyB′ to the received vectorxto obtain the decision statistic vector

y=B′x=d+B′w

(5)

2) Findykinywith the highest signal-to-noise ratio (SNR) and detect the corresponding symboldk,

(6)

(7)

2.2 Proposition of MP inverse of deflated matrix

(8)

(9)

Then we have

(10)

(11)

(12)

(13)

Thus,

(14)

2.3 OSNPC algorithm

By applying the proposition of the MP inverse of the deflated matrix in the LR-aided MIMO detection, we can construct the OSNPC algorithm as follows.

Take the PLR-aided MIMO detection for example. Suppose that the received signal vectorx=A′d+wand channel gain matrixA′ are known inputs, then the transformed symbol vectordcan be detected by using the following steps. Note that steps 1) and 2) are the same as those of the OSIC algorithm.

1) ComputeA′?, the MP inverse ofA′. LetB′=A′?, then multiplyB′ to the received vectorxto obtain the decision statistic vectory=d+B′w.

3) Compute the estimate of the noise term inykby

(15)

(16)

(17)

(18)

2.4 Performance and complexity comparison of OSNPC and OSIC

From the aforementioned proposition of the MP inverse of the deflated matrix we can arrive at the conclusion that the OSNPC algorithm is equivalent to the traditional OSIC in performance, which can be explained as follows.

In the OSIC, afterdkis detected and its corresponding interferences are cancelled fromx, the updatingxis

(19)

(20)

In the OSNPC, afterdkis detected and the corresponding noise projections are cancelled fromy, the updatedyis obtained, and its expression is explained as follows.

(21)

It can be clearly seen that Eqs.(20) and (21) are the same, which means that the decision statistics in the OSNPC algorithm are always equal to those in the OSIC algorithm. Thus, we conclude that the OSNPC algorithm is equivalent to the OSIC in performance.

Now we compare the complexity of the OSNPC with that of the OSIC briefly. To compute the MP inverse of a matrixA, the most efficient method is based on the Cholesky factorization of the matrixAHA[11]. If this calculation method is applied, the numbers of multiplications and additions of the OSIC algorithm are (9/4)N4+(4/3)N3M+(29/6)N3+(5/2)N2Mand (9/4)N4+(4/3)N3M+(25/6)N3+(5/2)N2M, respectively[11]. HereNis the number of transmitters andMthe number of receivers in the MIMO system, and the terms below the third order are ignored for brevity. Note that the multiplications and additions herein refer to complex value operations. By contrast, when applying the same MP inverse calculation method to the OSNPC-algorithm, it is easily obtained that the numbers of multiplications and additions of the OSNPC algorithm are(2/3)N3+3N2Mand(1/2)N3+(5/2)N2M, respectively. These results reveal that the complexity of the OSNPC algorithm is considerably lower than that of the OSIC algorithm.

2.5 OSNPC-based DLR-aided MIMO detection

Although the aforementioned OSNPC algorithm is described on the basis of the PLR-aided MIMO detection, it can also be applied to the DLR-aided MIMO detection. The OSNPC-based DLR-aided MIMO detection scheme is shown in Fig.3. In contrast to the OSIC block in Fig.2 whose inputs are signal vectorxand MP inverseB′?of the reduced basis of the dual lattice, the OSNPC block in Fig.3 needsxand reduced basisB′as its inputs. Obviously, the inverse calculation of the reduced basisB′ is avoided in the OSNPC-based DLR-aided MIMO detection scheme, which further reduces the overall computational complexity of the detector.

Fig.3 OSNPC-based DLR-aided MIMO detection scheme

3 Simulation Results

Numerical simulations are performed to evaluate the complexity and performance of the proposed OSNPC-based DLR-aided MIMO detection scheme (OSNPC-DLR). They are also conducted on the OSIC-based DLR-aided MIMO detection scheme (OSIC-DLR) for comparison.

First, we compare the computational complexity of the two schemes. It is well known that for a common floating point implementation of an algorithm, the floating-point operations (flops) dominate the calculation, and the number of flops is a consistent measure of the algorithm computational complexity, independent of what machine it runs on. Therefore, we carry out numerical experiments to count the number of flops in computation used in the detection schemes. In our experiments, the dual LLL[7]is selected as the DLR algorithm in both OSNPC-DLR and OSIC-DLR. Because the computational complexity of the dual LLL algorithm is randomly varying, we calculate the average flops on 106experiments for each case. Fig.4 shows the average number of flops of OSNPC-DLR and OSIC-DLR withN=M. It is observed that the number of flops of OSNPC-DLR increases much more slowly than OSIC-DLR asNincreases.

Fig.4 Average number of flops of OSNPC-DLR and OSIC-DLR vs. number of transmitters with N=M

Fig.5 illustrates the performance comparison of the two schemes in terms of symbol error rate (SER). The corresponding performance of the optimum ML detector is also depicted in Fig.5 for further comparison. In Fig.5, the SNR is defined asEs/N0withEsdenoting the average received energy per symbol per receiving antenna andN0the power spectrum density of additive white Gaussian noise, respectively. It turns out that OSNPC-DLR performs nearly the same as OSIC-DLR in terms of SER at different values ofNandM.

4 Conclusion

We propose an OSNPC algorithm to improve the performance of the MIMO detector with the conventional OSIC algorithm. The OSNPC-based DLR-aided MIMO detection scheme is further proposed. Analyses and simulation results show the better quality properties of our proposed detector regarding both the error performance and computational complexity. It is noteworthy that the application of the OSNPC algorithm is not restricted to DLR-aided MIMO detection. In fact, it has wider applicability as a general detection algorithm for all the non-orthogonal signaling communication systems (e.g., for non-orthogonal multi-user signal detection). Besides, the proposition of the MP inverse of the deflated matrix proposed in this paper provides some useful insights on the MP inverse problems and needs further investigation of the related works.

Fig.5 Symbol error rate of OSNPC-DLR and OSIC-DLR in an N×M uncoded MIMO system using 16-QAM.(a) N=M=4;(b) N=M=8;(c) N=8,M=10

[1]Viterbo E, Boutros J. A universal lattice code decoder for fading channels [J].IEEETransactionsonInformationTheory, 1999,45(7): 1639-1642.

[2]Hanzo L, Münster M, Choi B J, et al.OFDMandMC-CDMAforbroadbandmulti-usercommunications,WLANsandbroadcasting[M]. John Wiley & Sons, 2003.

[3]Wolniansky P W, Foschini G J, Golden G D, et al. V-BLAST: an architecture for realizing very high data rates over the rich-scattering wireless channel [C]//1998URSIInternationalSymposiumonSignals,Systems,andElectronics. Pisa, Italy, 1998: 295-300.

[4]Li X, Huang H C, Lozano A, et al. Reduced-complexity detection algorithms for systems using multi-element arrays [C]//ProceedingsofIEEEGlobalTelecommunications. San Francisco, CA, USA, 2000:1072-1076.

[5]Gan Y H, Ling C, Mow W H. Complex lattice reduction algorithm for low-complexity full-diversity MIMO detection [J].IEEETransactionsonSignalProcessing, 2009,57(7): 2701-2710.

[6]Wübben D, Seethaler D, Jaldén J, et al. Lattice reduction: a survey with applications in wireless communications [J].IEEESignalProcessingMagazine, 2011,28(3):70-91.

[7]Ling C, Mow W H, Gan L. Dual-lattice ordering and partial lattice reduction for SIC-based MIMO detection [J].IEEEJournalofSelectedTopicsinSignalProcessing, 2009,3(6): 975-985.

[8]Lenstra A K, Lenstra H W Jr, Lovsz L. Factoring polynomials with rational coefficients [J].MathAnnual, 1982,261(4): 513-534.

[9]Seysen M. Simultaneous reduction of a lattice basis and its reciprocal basis [J].Combinatorica, 1993,13(3): 363-376.

[10]Ben-Israel A, Greville T N E.Generalizedinverses:theoryandapplications[M]. New York: Springer-Verlag, 2003.

[11]Kusume K, Joham M, Utschick W. Cholesky factorization with symmetric permutation applied to detecting and precoding spatially multiplexed data streams [J].IEEETransactionsonSignalProcessing, 2007,55(6): 3089-3103.