当前位置: 首页 > >

A new faster Sphere decoding for MIMO systems

发布时间:

A NEW FASTER SPHERE DECODER FOR MIMO SYSTEMS
S. Mohammad Razavizadeh Vahid TabaTaba Vakili * Paeiz Azmi

I Iran Telecommunication Research Center (ITRC) 'Iran University of Science and Technology (IUST) Tarbiat Mndarres University (TMU) Tehran, Iran Email: m-mvi@iust.ac.ir

ABSTRACT Sphere decoding technique is an efficient fast algorithm for maximum likelihood (ML) detection. In this paper, we propose a new faster sphere decoding algorithm for multiple-inpnt multiple-output ( 0 ) systems that its complexity is much less than the conventionalalgorithm. In our method, the initial selection of sphere radius is not important. It will be shown that both the performance and the complexity of the proposed algorithm are simultaneously controlled by two parameters. Therefore, there is a trade-off between the performance and the complexity in the proposed algorithm. By computer simulations, we show that the performance of our method is very close to ML decoding algorithm. Furthermore, if we tolerate some degradation in the performance, we can speed up the proposed algorithm to ten times. Our results show that even in the fastest case, the novel decoder outperforms the V-BLAST decoding algorithm.

original decoder. The complexity of this new algorithm is controlled by two parameters. For the values of parameters in which the speed of thealgorithmishigh, there is a loss in performance respect to ML detector. Within this paper, we evaluate the performance of the proposed algorithm by computer simulations and it is shown that the results in all cases are much better than VBLAST technique. This paper is organized as follow. In section 2, we review the sphere decoding technique and the new modified algorithm is introduced in section 3. In section 4, the sphere decoding of multiple antennas systems is presented. Section 5 brings the simulationresults. Finally, section 6 concludes our work.

2. SPFIERE DECODING ALGORITHM
The sphere decoding algorithm deals with the maximum likelihood (ML) decoding of an n-dimensional lattice A [I]-[2]. In general, for ML detection in a Gaussian channel, the decoder must fmd the closest lattice point to the received point in the lattice. The sphere decoding algorithm restricts the search area and only searches through the points of lattice A which are found inside a hyper-sphere of a given radius *centered at the received point. Whenever a point is found inside the sphere, the radius of the search sphere reduces to the value of the distance of this new point to the received vector. This work decreases the number of lattice points that are considered in the metric minimization. More details of the algorithm are brought in [I]. The choice of C in the sphere decoding algorithm is very important. If C is too small. there may he no valid lattice point inside the sphere and if C is too large, there may be too many lattice points that are searchedby the algorithm and therefore the speed of algorithm will he low [l]. In order to be sure that a lattice point always exists inside the sphere, f i must be selected equal to the covering radius of the lattice [5]. In the next section, we propose a modified algorithm in which the initial choice of C is not important.

1. INTRODUCTION
With the recent growth and development in the area of wireless data communications, there is much interest in improving the system capacity and performance of current cellular and PCS systems. The idea of using multiple transmit and receive antennas systems has been considered as a practicable approach to enhance the system capacity [l]. Because of high complexity of the maximum likelihood (ML) detection, suboptimal detection techniques like V-BLAST have been proposed for MIMO systems [4]. Sphere decoding or lattice code decoding is an algorithm that speeds up the maximum likelihood detection by restricting the search area [I]-[2]. This decoder can he wed for ML detection in MIMO systems [3]-[5]. Using this decoder, the decoder can reach to the ML performance with reasonable complexity in multiantennas systems [3]. There are some papers that have tried to decrease the complexity of sphere decoder or equivalently to speed up it [8]-[9]. In this paper, we propose a new modified sphere decoding algorithm that is considerably faster than the

86

-

3. FAST SPHERE DECODING ALGORITHM
As it was said in the previous section, one important factor in the conventional sphere decoding algorithm is the initial value of search radius C. In this section, we propose a modified sphere decoding algorithm in which the initial value of search radius C is not so important. In this algorithm, fmst, we select the radius C very large (e.g. +m ) then with some modifications in the original sphere decoder, we compensate this selection and decrease the complexity of the algorithm. In the original decoder, whenever a point is found inside the sphere, the radius of search sphere reduces to the value of the distance of this new point to the received point [I]. The main idea in our proposed method is that wecan increase the decreasing rate of the radius. In the proposed algorithm, whenever a point is found inside the sphere, the new radius is selected as d * = k * 2' , where 2' is the squared distance of the previous founded point to the center. The scale parameter 0 5 k 5 1 increases the rate of decreasing of the sphere radius. First, radius Cmaybe selected very 1argge.g. +m ). In other words, in the first stage, the search area is not limited. But, whenever the first point is found, the search radius will be set to the squared distance value of this point to the center. Now, the main question is how should the scale parameter k be chosen? In general, we can say that as much as the parameter k is smaller, the algorithm will be faster. But a problem will arise whenever the algorithm reaches to the points near the received point. In these cases, if the distance of the last visited point kom the answer point is less than llk distance of the ML solution point from the center, the ML solution point will not he selected and the previous point will be chosen erroneously. Hence, we must change the parameter k adaptively. As it is stated before, the main part of sphere decoding algorithm is the determination of lattice points inside lattice. For this aim, the algorithm splits the problem into N one-dimensional problems. Whenever the possible values for sphere points in the mth dimension are determined, for each of them the points in the (m+l)* dimension will be determined. In the proposed algorithm, whenever the possible values for each dimension are determined the number of these possible values in the nth dimension, t, is used for calculating k. In general, we can say that if this number is large, the number of points that lie inside the sphere with radius C will be large too. Hence, the coefficient k should be chosen smaller. But on the other hand, if this number is small, the coefficient k must be near to one. Especially, if this number decreases to two or less, the k must be one. We obtained a function that has our desired properties as follow:

*

Fig.1. The coefficientk for (a) different o (b)different

(b)

: .

where t is the number of points in the nth dimension of lattice and a , p are the parameters that control this function and should be determined appropriately. Fig.1 shows the values of k versus a and p. The parameters a and p control the slope and the position of the curves. For the case of a-, the value of k is one, which is equivalent to the original sphere decoding algorithm. Decreasing a from m, increases the speed of algorithm. But a very small value of a may produce error in ML detection. We can choose the parameter a according to the maximum number of t for a specific application. The maximum number of t depends on the constellation that the signals are selected from. For example, in 64-QAMthe maximum value o f t is 8 ([-7, 5,-3,-1,+1,+3,+5,+7]). In the conventional sphere decoding algorithm, the path that passes through visited (candidate) lattice points has a zigzag shape. For example in fig.2a the operation of sphere decoder and the tested points for a two-dimensional lattice is shown. In the modified algorithm the width of zigzag shape is decreased (fig.2b). Decreasing this width results in decreasing the number of visited points and therefore it will speed up the sphere decoding algorithm. The parameter p also determines the slope of the curves.

87

r
where
* <

= %.H + ii

r = [real(r) imug(r)],

*
. "

*

x

*

*

*

r

Fii.2. Visited points by (a) original sphere decoding algorithm (b)

(a)

(h)

reu/(H) imag(H) H=[ and nl = [real(n) imug(n)] -imag(H) rea/(H) It is seen that H makes a lattice of dimension 2M. Hence, we can represent an MrmO system by a lattice and can apply the sphere decoder to it.

1

(3) i i = [real(a) imag(a)] ,

--

new dgorithm

5. SIMULATION RESULTS
OUT simulations, we consider an MIMO system with M=4 antennas at the transmitter and N=6 antennas at the receiver. The information symbols are selected fiom a 16QAM constellation. The transfer matrix H is modeled by independent Gaussian random variables of variance 0.5 per real dimension. At the beginning, the value of C is selected equal to m. Then, the performance of FSDis compared with original sphere decoder (SD) and VBLAST method. The performance of FSD depends on the values of parameters a andp . Our computer simulations have been done for the values of a = [m,10,8,5] and p = [8,5,2] . It should be noted that the case a = m (k=l) is the original sphere decoder (SD). For all these values of a and p (FSD), both the performance of the receiver and the average number of visited points in the algorithm have been obtained. It was noted in section 3 that this number is a proper criterion for complexity and equivalently for the speed of the algorithm. Fig.3 presents the BER performance of FSD over a Rayleigh fading channel. We can see that for high values of a and p the performance of FSD is very close to the performance of SD and the loss is negligible. Even in small values of a and p , in which the speed of decoder is very high, the performance of FSD is still much better than V-BLAST method. Fig.4 presents the average number of visited points in the FSD algorithm. We can see that the number ofvisited points is decreased significantly respect to the original sphere decoder ( a = m ). For example, for the case of a = p = 8 , the number of visited points is decreased about 20 percent and for a = 5, p = 2 this reduction is more than 80 percent. The FSD with these parameter values has complexity of ahout 0.1 of original sphere decoder (SD) or it is IO times faster than SD.

By decreasing p ,the speed of algorithm increases. But similar to a if the parameter p is decreased very much it may produce some errors and degrade the performance. Here, the number of visited points in the algorithm before reaching to the ML solution is OUT criterion for complexity. The sphere decoder algorithm is an iterative algorithm and the number of iterations is equal to the number of visited points. Hence, if this number decreases, the complexity of algorithm will be decreased. In the proposed method, this number decreases very much. The number of visited points is related to parameters a and p . It should be noted that this method does notintroduce additional complexity to the original algorithm due to calculating the parameter k. The various values of k can he saved in a look-up table and be used during the operation of the algorithm.
4.

In

SPHERE DECODING FOR MLMO SYSTEMS

I

-

In section 2, it was stated that the sphere decoding algorithm is a method for finding the closest point in a lattice to the received point and it is the ML solution in a Gaussian channel. In this section, we consider the MIMO systems and show that these systems can also be represented by lattice and then we can apply the sphere decoder to them. Consider an MIhfO system with M transmit and N receive antennas. The input data stream is multiplexed into M substreams, and each substream is modulated independently and fed to its respective antenna. It is assumed that the same constellation is used for all substreams In this paper. we consider the case of M 5 N . But the generalization to arbitrary M and N is possible [4]. The transmission is done over a quasi-static Rayleigh fading channel. The received signal at each instant time is given by: r = a.H+n (2) where a = [a,,a2,...,U, ] denotes the transmitted vector which belongs here to the constellation QAM, and U is a 1 x N complex AWGN vector with variance d. Moreover, H is an M x N transfer matrix of the channel with entries h, which is the fading gain between the transmitter i and receiver j.We can transform the above complex equation into real matrix equation as:

.

6. CONCLUSION
In this paper, we have proposed a new faster sphere decoder for MIMO systems. In the proposed decoding algorithm, the rate of reducing the search sphere radius is more than the original sphere decoder. Therefore, the new

. . . . . . . !........!.......I

. . .\ . : > . . . . . . . .

. . . . . 1. . . . . . .

. . . . . . .. . . . . .: . . . . . . .: . . . . . . .: . . . . . . .. . . . . . .

..............................,..................
. . . .

10.‘

a

2

4

6

B SNRCB)

10

12

14

7

6

5
befr

4

3

J

2

Performance O ~ N RFaster Sphere Decoder

Average numberofririled P ~ I ~nS d8Kerentvalue9 afparameler alpha

g
. . . . . . . , . . . . . . . . . . . . . . . , . . . . . . . . . . . . . . . , . . . . . . . . . . . . . . .

do

;

4

6
SNR(dB)

8

10

12

14

’10

95

9

85

8

75 alpha

7

65

6

55

5

Fig. 3. Performance of new faster sphere decoder @?XI)

Fig. 4. The average number ofvisited points versus a and

p

algorithm is much faster than the original decoder. We also showed that in contrast to the original sphere decoding algorithm, the proposed algorithm do not restrict the search area at the first stage. Therefore, the initial choosing of the sphere radius is not important. It was shown that the proposed technique is faster than the original sphere decoder and its performance is better than other detection method like V-BLAST.

REFERENCES
[l] E. Viterbo, J. Bouros, “A universal lattice code

decoder for fading channels”, IEEE Trans. Inform. Theory ,vol. 45, pp. 1639-1642, July 1999. [2] E. Agrell, T. Eriksson, A. Vardy, K. Zeger, “Closest point search in lattices”, IEEE Trans. Inform. Theory, vol. 48, pp. 2201-2214, Aug. 2002. [3] M.O. Damen, A. Chkeif, and J.-C. Belfiore, ‘$Lattice code decoder for space-time codes,” IEEE Commun. Lett., vol. 4, pp. 161-163, May 2000.

[4] M. 0. Damen, K. Abed-Meraim, J.C. Belfiore, “Generalised sphere decoder for asymmetrical space-time communication architecture”, Electronics Letters, vo1.36, pp.166-167, Jan. 2000. [5] M.O. Damen, K. Abed-Meraim, M.S. Lemdani, “Further results on the sphere decoder”, IEEE Intern. Symp. on Info. Theory. Washington DC, USA, June 2001. 161 G.J. Foschini and M.J. G a s , “On limits of wireless communications in a fading environment when using multiple antennas”, Wireless Personal Commun., vol. 6, no. 3, pp. 311-335, Mar. 1998. [7] P.W.Wolniansky, G.J.Foschini, G.D.Golden, R.A.Valenzuela, “V-BLAST: An Architecture for Realizing Very High Data Rates Over the Rich-Scattering Wireless Channel”, Bell Labs., Technical Report,1999 [SI A.M.Chan, LLee, “A New reduced-Complexity Sphere Decoder for multiple Antenna Systems” E E E Int. Conf. on Comm.,ICCO2, pp.460-464,2002. [9] L.Beygi, A.R. Ghadeflpoor, K. Dnlatyar, “A fast decoding for space time block codes“, IEEE Workshop on Sensor Array and Multichannel Signal Processing, 2002

09




友情链接: