Improved FCLSD algorithm based on LTE/LTE-A system

Published Online August 2011 in MECS

3GPP Long Term Evolution (LTE) project is the largest new technology research project in recent years ,and with the 3GPP2 Ultra Mobile Broadband (UMB) technology is referred to as "Evolved 3G". In order to meet the high data rate, large capacity and low latency in LET, advanced MIMO technology has been introduced in LTE system, which becomes one of the core technologies of physical layer. As an important application form of MIMO technology, space multiplexing can gain higher data transfer rate than the antenna diversity. But for spatial multiplexing MIMO systems, space de-multiplexing (or signal detection) at

Footnotes: 8-point Times New Roman font;

Manuscript received January 1, 2008; revised June 1, 2008; accepted July 1, 2008.

Copyright credit, project number, corresponding author, etc.

the receiver is a problem as concerned: how to get tradeoffs between performance and complexity, how to make the designed algorithms conducive to hardware implementation, but also can get a good performance, it’s largely related to weather the advantages of MIMO technology can effectively play in the actual system.

In a variety of MIMO detection algorithms, zero forcing algorithms (ZF, Zero Forcing) is the most simple and direct, the algorithm can completely eliminate the interference between the antennas, but caused the noise signal amplification. It’s not proper to use the algorithm in bad channel environment. Maximum likelihood method (MLD, Maximum Likelihood) can obtain optimal detection performance, but because of the need to search of all possible send vectors, the complexity increased exponentially with the number of antennas and modulation orders, so MLD algorithm can not be applied to practical, it is a theoretically optimal algorithm. Inspired by the theory of MLD algorithm, sphere decoding (SD, Sphere Decoding) is mentioned and widespread of its superior performance and lower complexity. The idea of the algorithm is searching space maximum likelihood point in a sphere of multidimensional constellation with limited radius, this algorithm in the case of sufficiently large radius can achieve the same performance with ML detection, while in a certain range of system parameters, the complexity is polynomial class. In view of these outstanding advantages of SD algorithm, theorists do extensive and in-depth study of the algorithm in recent years, many advanced algorithm developed based on the SD algorithm, Complex List Sphere Decoding (CLSD) is a representative of an advanced algorithms. The reason why consider of soft output is that the actual communication system requires MIMO signal detector to generate soft information to get better channel decoding. In this case, the system needs to retain paths as much as possible which contain ML solutions and have smaller weight. But the traditional sphere detection based on hard decision, which is search the maximum likelihood solution path in the tree, can not meet this requirement. Then we need to consider choosing some survival paths for the soft bit output algorithm based on the maximum a posteriori (MAP). The basic idea of CLSD algorithm is generated a large enough list L by sphere decoding, which include the maximum likelihood point and its neighborhood, then the given bit soft information can be obtained by the L. The results show that the BER performance of CLSD algorithm is close to MLD algorithm, and the computational complexity is much lower than the MLD algorithm [2] [3] [4].

Although CLSD has the similar performance with MLD algorithm and can be realized in practice, but for its computational complexity is changed with channel conditions, the number of antennas and modulation order, its computational complexity is variable in practice. In specific implementations, the system needs to take the range of complexity into account and ensure adequate headroom, which will inevitably reduce the efficiency of the algorithm and bring hardware implementation difficulties. To solve this problem, an improved suboptimal CLSD algorithm - fixed complex list sphere decoding (FCLSD) was put out. Compared with CLSD algorithm, this algorithm has two important characteristics: the fixed complexity and parallel process, which is very benefit to hardware implementation.

Based on advanced FCLSD algorithm and combined with LTE / LTE-A practical system applications, this article designed two improved algorithms, which is combined with ZFLLR/MMSELLR algorithm. In some extreme scenarios the algorithm can greatly reduce computational complexity and improve the scope of application; with the reference of channel matrix reordering algorithm, it can further improve the detection reliability. The two improved algorithms can be flexibly and adaptively used in various antenna configurations and modulation scene in LTE / LTE-A spatial multiplexing MIMO system. The Simulation results show that the improved algorithm can achieve a approximate performance to the original FCLSD algorithm, in addition, it has a fixed complexity and could be carried out by parallel processing.

This article is organized as follows: chapter 2 mainly introduced the system model based on the algorithms, chapter 3 describes the basic principles of he CLSD and FCLSD algorithms; Chapter 4 give a detail description on improved algorithm and its characteristics based on the actual The LTE / LTE-A system; Chapter 5 discussed the performance and complexity of the improved algorithm and showed the simulation results; Chapter 6 concluded the paper and presented conclusion

• II.    System model

The diagram of a typical complex baseband MIMO system is shown in Figure 1. Suppose there are M transmit antennas and N receive antennas (M≤N), and the channel gain between the transmit antennas i and receive antennas j the Rayleigh distribution. Source bit symbol ‘a’ belongs to set {+1,-1}, where the logic '1 'corresponds to +1, logic '0 ' corresponds to -1. First Turbo coding and symbol interleaving for bit symbol ‘a’. Then grouping the interleaved symbols, each consisting M*Mc bits, Mc refer to modulation order. Then constellation mapping and spatial sign processing for each group separately, which constellation mapping can type cn = {bn, 1, bn, 2 ... bn, Mc}, in turn. The symbols are mapped to the transmitting antenna after spatial signal processing, and then sent by the antenna after OFDM modulation and radio-frequency processing. In the receiver, the receiver first make OFDM demodulation and channel estimation of the received N parallel data streams , and then get the channel matrix H by using the channel estimation for signal detection ,constellation demapping, deinterleaving and channel decoding. At last recover the original information bits.

Figure 1. The MIMO-OFDM System

The mathematical model of MIMO baseband transmission is shown in Equation (1)

y = Hx + n          (1)

Where X = [X1, X2, ■■■, XM ]Г refer to transmit signal vector Xi G S2 (S refer to finite real/virtual constellation set), and E {XXH } = M^M ;

y = [ У 1 , y 2 , ••• , y N Г

refer to received signal vector ( y i G C ( C refer to complex field)); H refer to N x M dimensional channel matrix.

H reflected channel fading.

different antennas transmit power and H can obtain by channel estimation module through detection n = [ n1, n2, ■■■, nN ] refer to complex Gaussian white noise which is N dimensional independent and identically distributed circular symmetric. And E {nnH } = <72IN .All the description of detection algorithm is based on this system diagram and mathematical model.

• III.    Theory of CLSD and FCLSD algorithm

MIMO detector and channel decoder is a continuous cascade structure, they exchange soft information, and it’s shown in Figure 2. Among them, the received signal vector ‘y’ and prior information LA from the decoder are sent to the input of the detector, while the soft output of the detector will also serve as the decoder’s prior information, then the detector / decoder should calculation the log-likelihood-ratio of each bit (LLR). Because the system uses a decoder based on soft information, so it required MIMO detector detecting soft information of each bit.

L E ( c n , m

(

| y ) = max ^{x E} X + i

II y ^- Hx I²

M M c

+ У У c k, L _A ( c k ,) k = 1 l = 1

( k * n )( l * m )              _

- max

X E X I

-

II y ^- Hx I²

a ²

A. Complex List Sphere Decoding (CLSD)

In order to describe the algorithm later, this section will give a brief introduction on CLSD algorithm based on MAP.

M M c

⁺ У У c k , l^LA ⁽ c k , l ) k = 1 l = 1

( k * n )( l * m )              _

Transfer the calculated extrinsic information L_E to

F igure 2. t he p rocess of m aximum a p osteriori p robability of s oft - bit output CLSD

To detect intertwined symbol group c, we need to

SISO channel decoder to get original data bit stream. Because the soft input soft output channel decoding algorithm does not belong to this research area, we will not repeat them here.

Although the computational complexity of L _E has

calculate log-likelihood-ratio corresponding [2] to c _n

been simplified, it still increases exponentially with the order of modulation. In order to improve the speed of calculation, a list spherical decoding algorithm was proposed by Hochwald ， etc [3].The basic principle of this algorithm is: construct a list ^L by the sphere decoding algorithm and make sure that the Mapping Points ^{N cand} searched out can make

when the received signal is y. All this according to CLSD algorithm.

L d ( C nm ly ) = ln p ^[ c =⁺ 1| y ^] , ¹ <  n <  M ,1 <  m <  M c   ⁽²⁾

P [ c n,m = ^{- 1} । У ]

L = { x ||| y - Hx ||²<  R ²}

the smallest. The candidate

The original bit stream c after channel coding and interleaving can be considered statistical independence of each element. According to Bayes theory, (2) can be simplified as:

L D ( c n , т\ У ) = L A ( c n , m ) ⁺ L E ⁽ c n , m )            ⁽³⁾

Where the first part is refer to prior soft

P [ ^c _{n m} = + 1] information L. ( c ) = In---- ^,------- ; the second part is

An , m

P ^[ c n , m = - 1]

points are illustrated in Figure 3, where R is the radius of sphere. In order to get the list L ， CLSD algorithm modified SD algorithm in two parts: Firstly, there is no need to produce the new radius along with the new point which is searched in initial radius. That is, not reduce the radius. Secondly, if the list L is not full, add the new point to the list, else, compare the radius of new point with the point which has the largest radius in L . If the radius of the former is smaller than the latter, then, replace the latter by the former. Therefore, the list L which contains the maximum likelihood estimated value

refer to extrinsic soft information.

_t M M c

У p ( y|x )exp 1 У У C k , i L a ( C k , 1 )

X E X + ,                    ² k = 1 l = 1

T                                      V (k*n)( i*m)

LE (cn, m ) = ln                   7

1 M M c

У p ⁽ y | x ^)e xp - У У c k , 1 L A ⁽ c k , i )

X E X - 1                   ² k = 1 l = 1

V (k * n)(i * m)

And note X + 1 = ^{{ x} | c n , m = ^{+ 1}} , ^X - 1 = ^{{ x} | c n , m = ^{- 1}} .

We know the output of MIMO detector can be signed as the sum of prior information and extrinsic information. It’s shown in figure 2.

The most important part to calculate the log-likelihood ratio is to calculate likelihood function p ( y | x ) . By (1),

and its N _cand - 1 neighbors, will make || y - Hx || small.

After obtained the list L , (5) can be approximated as:

L E ⁽ c n , m I y ) = ^max x e L n X + 1

II y - Hx |l²

—

V

- max x e L n X-1

we know that:

P ⁽ У । ^X ) =

( n^ ²) N

exp[ -

|| У - Ях ||² ] a ²

According to Max-Log approximation estimation method, put (4) into (3), then, L _E can be simplified as:

a ²

M M c

+ У У c_k,L A ( c_kJ ) k = 1 l = 1

( k * n ) ( l * m )

II y - Hx |I²

2 a

V

If N c _a n _d = 2 MM c , then the becomes equation. However,

_

C

M  M c

+ У У c k,l L A ( ck, ) k = 1 l = 1

( k * n ) ( l * m )

approximate to consider the

realization, N _cand is generally small. So, it is

_

equation concrete

faster to

calculate (6) than (5).

The approximate extent of (6) to (5) is measured by N_cand . For a given N_cand ， suppose two equations have reached the degree of approximation ,thus ,we need to get N_cand candidate points in the list L by selecting

radius R .If R is too small, no matter how large N_cand is, we can select out very little points in sphere, conversely, if R is too large, it will reduce the efficiency of CLSD

algorithm. Because it needs to select N _cand best candidate point sets from many candidate points. It should be noted that, a possible method to select the radius was proposed by Hochwald etc [3]. However, in their method, ^R is related to noise variance and list length etc. So, it needs to be determined repeatedly and the result may still not be the best.

Figure 3. List Sphere Decoding Candidate Points

id points Hx

Total grid points 2 M • Mc

c

• B. Fixed complexity soft-output complex list sphere decoding(FCLSD)

The soft-output MIMO detection algorithm CLSD was analyzed in the former section, the difficulty lies in how to choice the appropriate radius to select the candidate points within the super ball. If radius is too small, performance will be significantly lower, however, if too large, the computational complexity will greatly enhance. So, the uncertain value of R leads to an uncertain computational complexity. In addition, from the perspective of the realization of hardware, the algorithm should be able to make parallel processing and has a fixed complexity. Because of these problems in the soft-output MIMO detection algorithm CLSD, it prefers to use the soft-output complex list sphere decoding ( FCLSD ) with fixed complexity in the real system. The basic principle of FCLSD algorithm is: not search candidate points in a ball of certain radius, but choose the candidate points which are nearest to the center of the sphere according to set C .

For a model of MIMO system, as shown in Figure 1, assume the set of candidate points searched by the receiver is:

^C = ^{{ C} 1 C 2 L C_M ^}               (7)

where , 1 <  _c <  2 M c i = 1 L M , the final number of candidate points is N ad = c 1 • c ₂ ■ • c_M .

For each i = 1, ■, M , consider the following formula by complex sphere decoding：

( x - x)^H H^H H ( x - x) <  R²

Where, x = (HHH) 1HHy is the center of a super ball and it can be obtained by ZF algorithm. U is an upper triangular matrix ( m x M dimension). By the Cholesky decomposition of channel matrix H , we can obtain UHU = HHH .The elements in u are noted as uj, i < j = 1,L, M .Without loss

of generality,

assume ui. >  0 , then,(8) is noted as:

M

( x - ~) ^HU^HU ( x - ~) = £ u 2

M u 1 2

x-~ +    —(xi-x/)

In FCLSD algorithm, for each i = 1,•••,M , it only needs to search c_i constellation points which are nearest

M uij to the center of the sphere .xi — ^ —(xs — .xj.) in the j=i+1 Uli constellation diagram, and not need to consider the restriction of radius R. In the process of searching candidate points, choose ci candidate points which are nearest to the center of sphere in the i layer by the order ofi = M,M -1,l,1 . Thus, it can search out Ncmd sets of candidate points. Then, it can obtain the result of soft-output of FCLSD algorithm according to the computational method of log-likelihood ratio in the previous section.

VI. Design of improved algorithm

In the former section, it has not mentioned how to determine the number set C in the FCLSD algorithm. However, in actual application, the determined algorithm of the set C will determine the whole performance of detection and computational complexity of FCLSD algorithm. According to the analysis of the literature [6] ，the diagonal elements of matrix U fulfill：

E[^UMM ] < E[^UM-1M-1] < L< E[^u11]       ⁽¹⁰⁾

Therefore, the number of the candidate points c_i in the layer i should fulfill:

E[cm] > E[cm-1] > ■ > E[ci]            (11)

It’s found in [7] that, in order to achieve the performance of detection which is close to the MLD algorithm and obtain the same diversity characteristics with the ML detector, the number of sets of candidate points must fulfills:

ci

• 1    for i = 1, — , M - P

2Mc for i = M - P +1,— ,M with P > VM -1

In the downlink MIMO system of LTE, the maximum number of transmit antennas is 4 and the maximum order of modulation is 6, that’s 64QAM. According to (12), in this extreme case, the set of candidate points is C = {1 1 1 64} and the total number of candidate points is Ncand = 64 , the computational complexity for real systems is acceptable at this time. However, when LTE system transfers to LTE - A system, the case is different. The maximum number of transmit antennas can be supported by LTE - A system is 8, at this time, C = {1 1 1 1 1 1 64 64} and Ncand = 4096 , thus, the complexity has increased dramatically and the advantage of FCLSD algorithm will decline significantly.

In order to solve the problem effectively, this paper proposes a ZFLLR (or MMSELLR)-FCLSD joint detection algorithm which is inspired by [8]. Here, take ZFLLR as an example, the specific algorithm is described below:

• (1)    First, detect the received vector of signal y by ZF, then:

XZ,F = w_ZFy = x + (HHH )^-1HHn = x + ~_ZF    (13)

where, wZF = (HHH)-1 HH ((•)H refers to the conjugate transposed operation), and wi,ZF is the i th row of wZF . (2) Calculate the signal-to-noise (SNR) of each detection symbols ~i ZF (i = 1, l , M ) ,which is given by snr, =    Ex 2 =1        , 1 ^ i ^ M (14)

CT 21 w zf||    Mo 2| w zf|| where, Ex represents the signal energy from each of the transmitting antenna.

• (3)    Then {SNR₁, SNR₂, L , SNR_M } shall be in descending

order, and the subscript is { k₁, k₂,L, k_M } respectively, which is given by

SNR_k1 = max{ SNR1, SNR₂, l , SNRM}

M                         M                                  (15)

SNRkM = min{ SNR1, SNR 2, l , SNRM} where, k1, k2, l , kM e {1,2, l, M} and k1 * k2 * l * kM .

• (4)    For the first LM/2j ~_i,_ZF ( i = k 1,k₂,l,kl_M/2j )

with a better SNR can use ZFLLR algorithm for the lower complexity to detect directly. The detail about ZFLLR(or MMSELLR)algorithm is given by [9].

• (5)    Remove the i th (i = k 1, k₂, l , k^_M / ₂j) column from the original channel matrix H , result in a new N x (M - ^M / 2 J) -dimensional matrix H'. Then remove the corresponding element x,ZF (i = k 1, k₂, l , k_{M /2}j) from original vector ^~x_ZF , results in a new (M - LM / 2 J) _x1 -dimensional vector ~_ZF' . In terms of H' and ^~x_ZF ' . For the remaining symbols (i.e. the symbol of poor quality signal to noise ratio), refer to the relevant contents of section 3 and use FCLSD algorithm to detect.

In some extreme cases previously mentioned, a issues of the computational complexity may appear a surge will be resolved effectively through applying the above improved algorithm. Still eight transmit antennas, 64QAM modulation as an example. If using the above improved algorithm, the number of the candidate points

C = {1 1 1 64} set                   , the total number of candidate points Ncand = 64 , in addition ZFLLR algorithm itself also has very low complexity. Therefore, compared with only using the FCLSD detection, using the improved algorithm will significantly reduce the computational complexity. Although there will be some performance losses, taking into account the actual spatial multiplexing MIMO systems will consider the number of large antennas and high order modulation when the systems are generally in the scene with quite a good quality of signal to noise ratio. Therefore using the improved algorithm will not cause a large decline in detection performance. Return to (12) we can observe, when i = M - P +1, l , M , the corresponding layer uses an exhaustively search method, namely all of constellation points under this modulation mode were selected into the candidate set. When i = 1, l , M - P , the corresponding layer uses a single-point search method, namely only under the conditions selected   the   nearest point from

Mu ij center х^ - > ^-(Xj - Xj) .Taking into account the j=i+1Ui^

characteristics of each search method and combining the thought of channel matrix reordering, this paper suggests the original FCLSD optimization algorithm as follows:

(1)~(3)：Here is similar to (1) ~ (3) of ZFLLR-FCLSD joint detection algorithm above the text.

• (4)    Calculating matrix П , and

  П

  
  

~~   ~

X1,ZF, X2,ZF, •••, XM,ZF

T

T

~~~~~~

XkM-P,ZF, • ••, Xk2,ZF, Xk,.ZF, XkM,ZF, XkM-1,ZF, • ••, XkM_P+,ZF I

n

= XZF where, the definition ofP is the same as (12),

P is integer and P > MM -1.

• (5)    Calculating H) = ИП^-1.

(6)After the above pretreatment, then substituting H for H and replacing x⁾_ZF with ^~x_ZF . Refer to the relevant content and equation (20) of section 3, detecting by the original FCLSD algorithm.

In the above optimization algorithm based on the original FCLSD algorithm and considered the impact of SNR_i (i = 1, l, M ) , the design idea of the algorithm can be summarized in the following two points:

• >    The SNR, corresponding to the layer using a exhaustion search method is less than that corresponding to the layer using ingle-point search, which lead to optimize the detection performance accordingly;

• >    For the same kind of search method for each layer, the SNR_i corresponding to the first-serching layer is reater than that corresponding to the later-searching layer, thus it can avoid the error transfer as possible.

In the actual communication system, the two algorithms can be integrated more flexible and adaptive to apply. For example, there are different requirements for the transmission speed and reliability of different channels. Thus the modulation mode which different channels used is also different. For the channel has a higher requirement for transmission reliability such as the control channel, can use the lower-order of modulation mode (QPSK). And for the channel has a higher requirement of capacity and speed such as the shared channel, are more inclined to use higher-order modulation (16QAM and 64QAM) and more antennas.

So, in practical applications, this paper suggests selecting different detection algorithm self-adaptively according to the different applied scene: For most applied scene (M< 4) , using the optimized FCLSD algorithm can take into account both the performance and complexity. But for a few extreme applied scene (M > 4, M _c = 6), can use ZFLLR (MMSELLR) and optimized FCLSD joint test algorithm, in order to reduce the computational complexity of algorithms as much as possible on the premise of guaranteeing performance.

V. The performance analysis and simulation of

IMPROVED ALGORITHM

A. FCLSD algorithm complexty analysis

The algorithm we designed is more flexible and the complexity mainly comes from the FCLSD. In this section, we will focus on analyzing the complexity of FCLSD instead of the improved algorithm. In general, we choose the most common LTE configuration with 2

TABLE I. list of simulation parameters

Parameters	Values
Link	LTE TDD[3]
Bandwidth	10MHz
Antenna configuration	2x2 Antenna distanceBase Station(10X), Terminal(0.5X)
Coding	1/3 Turbo
Modulation	QPSK/ 16QAM /64QAM
Channel Mode	SCM
Terminal speed	30km/h

transmitting antenna

and modulation order is 2

4.Considering xi

^^^^^^»

~ xi +

M

Z ^ ( x. - .

j=i+1 ii

,we can see,

the complexity of FCLSD algorithm is .When M = 2 ,

Mc = 4,

'P = c₂■ 2Mc -(1 + M-i) + (3 + M-i)• c₂+ 2Mc

-T = c₂■ 2 Mc •( M - i) + 3-c₂+ 2 Mc

. D = c2

Here P、T、D stands for the operation times of addition, multiplication and division respectively. The total computing complexity is P + 4 ■ ( T + 2 ■ D ) .

Figure 4. The Simulation Result of MIMO Detection Algorithm

According to the curve from Fig.4, we can conclude that the MLD algorithm is undoubtedly the best, considering performance. However, from the implementation point of view, improved FCLSD algorithm has incomparable advantages which the former two algorithms don’t have, namely, achieving the perfect trade off between performance and complexity.

B. Simulation of the improved algorithm

We simulate the improved algorithm on the LTE system platform by the steps mentioned above.

The link simulation results of MLD, CLSD, FCLSD algorithms in LTE/LTE-A TDD system were given in the Fig.4 and the simulation conditions were shown in Table 1. The candidate point number of CLSD algorithm is 16, 32, 64 and 128, the candidate point number of FCLSD algorithm is 64.

As can be seen from Fig.4, the performance of soft-output CLSD algorithm is improved continually with the increase of candidate points. But when the number of candidates is greater than 64, its performance will not be significantly improved. When using the Candidate set of 128 points, the performance of CLSD algorithm and BER algorithm is very close, if BER of the target selected is 10-3, then the required SNR between CLSD128 algorithm and MLD algorithm is different at about 0.25dB.The candidate point number of FCLSD algorithm is 64. From the simulation results, we can conclude that it has the same good performance with CLSD algorithm of 64 points.

VI . Conclusion

Based on LTE/LTE-A TDD system, this paper studies the performance of the improved FCLSD algorithm, makes computer simulation for it and analysis the simulation results. Through this study, we can draw the following conclusions: CLSD algorithm can output soft information of each bit and when combined with decoder, its performance is close to MLD, however, its complexity depends on the radius and the size of the list, so it is very unstable and not conducive to hardware implementation. The performance of the improved FCLSD algorithm varies slightly with the CLSD algorithm. It is nonconstrained of spherical radius and has fixed complexity. In addition, hardware implementation of the improved

FCLSD algorithm could be carried out by parallel processing, So it is a high-performance algorithm of great potential and more suitable for practical communication systems.

Acknowledgment

This work was supported by National Natural Science Foundation of China(NO.50775167)