《SphereDecoding of Signals With ISI.doc》由会员分享，可在线阅读，更多相关《SphereDecoding of Signals With ISI.doc（8页珍藏版）》请在三一办公上搜索。
1、精品论文Sphere-Decoding of Signals With ISIYu KeKey Laboratory of Information Processing and Intelligent Technology，Beijing University of Postsand Telecommunications，Beijing（100876）E-mail：feigepp_buptAbstractSphere-Decoding is a newly developed fast MLSD (Maximum Likelyhood Sequence Decoding)algorithm c
2、ommonly used in MIMO (Multiple Input and Multiple Output) System. In this paper, signal sequences with ISI (Intersymbol Interference)is decoded using Sphere-Decoding. The algorithm is modified according to ISI channel with the BER (Bit Error Ratio) simulation results and expected complexity analysis
3、 given.Keywords：ISI；MLSD；Sphere Decoding1. IntroductionISI is usually caused by imperfect impulse forming or unideal channel impulse response. Severe ISI can make the eye diagram close and decrease the BER performance greatly. Kinds of equalization algorithms can be used to suppress the ISI, among w
4、hich the ML equalization or the MLSD is the optimum one. However, the complexity of the traditional MLSD algotithm increases exponentially with the increase of the symbol numbers affected by ISI. Therefore, Sphere-decoding, with its complexity only approximately a cubic polynomial of the frame lengt
5、h when SNR (Signal Noise Ratio) is high, can be used as an fast MLSD algotithm when ISI is severe.1.1 ISI System ModelFirst, suppose one frame contains M consecutive information data- 8 -b = (b1 , b2 ,., bM )(1)of duration T each, and each information data can be taken from a finite set CZ such as t
6、he output constellation of QAM.Then, suppose the shaping pulse is denoted byhs (n)( n = 1, 2,., L )(2)for each information data, where continuous shaping pulsehs (n)can be the sample sequences with equal sample duration of ahs (t ) t 0,T ) .(3)Therefore, the sending signature waveform can be denoted
7、 bysi (n) = bi hs (n) ( n = 1, 2,., L )(4)for eachbi , i = 1, 2,., M .Next, Suppose the discrete time impulse response of the channel ishc (n)( n = 1,., m )(5)the effective shaping pulse of the receiving information signals equals toh(n) = hs (n) hc (n)( n = 1, 2,., L )(6)where denotes the convoluti
8、on operation andL equals to L + m 1 . And the effective signaturewaveform for each bican be denoted bysi (n) = bi h(n) ( n = 1, 2,., L ).(7)s1 (n) 0 L ns2 (n) 0 1 L+1 nsN (n) 0N-1N+L-1 nFig. 1. Structure of an ISI symbol frameLast, the receiving signal sequences can be the sum ofthe sets(i) = si (n
9、i) = bi h(n i) : i = 1, 2,., M ,(8)with each element an i information symbol duration delayed vector ofsi (n) ,M M si = bi h(n i) .(9)i =1i =1The structure of an ISI symbol frame is drawn in figure 1.1.2 Feature of ISI System ModelIts easy to see from figure 1 that there exists severe ISI (intersymb
10、ol interference) between every Lconsecutive information data of the same modulation symbol, but the one to one mapping relation between each modulation symbol and modulated signal still holds according to 1, 2, 3 and 4.In AWGN (Additive White Gaussian Noise) channel, ifw(n)denotes the white Gaussian
11、 noisewith zero mean and variance N0/2, then the input to the receiver in the AWGN channel can be denoted byLetMyn = bi h(n i) + wni =1( n = 1, 2,., M + L 1 ).(11)then (11) can be written asy = ( y1 , y2 , ., yN + L 1 ) ,w = (w1 , w2 , ., wN + L 1 ) ,N=M+L-1,y = Hb + w(12)where H is a N Mmatrix deno
12、ted by h(1)00 h(2)h(1)# #h(2)# h(L )# H = 0h(L ) # .(13) 00# # # h(1) # # # 00 h(L ) N M 1.3 Complexity of TraditionalMLSDAccording to (9), the mapping relation between the N information data in each transmission symbol and the transmission signal is a kind of convolutional operation. Therefore, the
13、 typical MLSD algorithm is the VA (Viterbi Algorithm). And the performance of VA algorithm is studied in 1, 2, and 4. However, according to 3, the complexity of the VA increases exponentially with the increase of L.2. Sphere-decoding statementThe MLSD algorithm tries to find the solution of the inte
14、ger least-squares problem with the following formwhereb = argmin | y Hb |2 ,(14)b cz MCZ M is an M-dimensional product space of CZ .According to 7, instead of finding b that satisfies (14) in finds the b in a set B(d) defined byCZ M , the Sphere-Decoding algorithmand (14) can be written asB(d ) = b
15、:| y Hb |2 d 2 , b CZ M ,(15)b = arg min | y Hb |2 .(16)b B ( d ) And its easy to see that if there exists a solutionb to (16), thenb is also a solution to (14) and therealways exists a solution to (16) as long as d can be taken as large as possible.According to 5 and 6, the Sphere-Decoding can be s
16、implified by making QR factorization of the matrix H RH = Q 0( N M ) M (17)whereR = (rij )M M is an M Mupper triangular matrix, andQ = Q1 , Q2 is an N N orthogonalmatrix. The matrices Q1 and Q2are the first M and the last N M orthonormal columns of Q .Then| y Hb |2can be written as| y Q Q R Q * b |2
17、 =| 1 y R b |2 =| Q * y Rb |2 + | Q * y |2 d 2,(18)1, 2 0 Q * 0 1 2 2 where(.)*denotes complex conjugate transposition of matrix (.). In other words,* 2 2 * 22| Q1 y Rb | d | Q2 y |.(19)1DefiningQ * y = zandd 2 = d 2 | Q * y |2 , (19) can be written term by term asMMi =1| zi ri , j bjj = i|2=2 2| zM
18、 rMM bM |+ | zM 1 rM 1, M bM rM 1, M 1bM 1 |+. d 2 .(20)where the first term depends only onbM , the second term onbM , bM 1 , and so on. In order to find the appropriate b , a necessary condition is| zM rMM bM|2 d 2 .(21)For everybM that satisfies (21), defining2 2d M 1= d | zM rMM bM | ,(22)andthe
19、nbM 1must satisfyzM 1| M = zM 1 rM 1, M bM ,(23)And by defining| z rx| d 2M 1|MM 1, M 1 M 1M 1Mzk |k +1 = zk rk , j bjj = k +1.(24), (25)2 2 2all the bkmust satisfyd k= d k +1 | ( zk +1|k + 2 rk +1, k +1bk +1 ) |k |k +1 k , k k k| z r x |2 d 2.(26)The decoding process described above can be summariz
20、ed as follow :*Input :Q = Q1 , Q2 , R , b , z = Q1 y , d .1.Set k = M ,2d M2 = d 2 | Q * y |2 ,zM | M +1= zM .2.Calculate thebM s possible value.3.Choose a possible value of bM(different from the choice before).4.(Increase k) k = k + 1 ; ifk = M + 1 , terminate algorithm; else, go to 3.5.(Decrease k
21、)If k=1, go to 6; elsek = k 1 ,Mzk |k +1 = zk rk , j bjj = k +12 2 2d k= d k +1 | ( zk +1|k + 2 rk +1, k +1bk +1 ) |, and go to 2.6.Solution found. Save b and its distance form z , go to 3. And according to 5, the parameter d can be set asd 2 = N 2 ,(27)where 2 is the covariance of additive white Ga
22、ussian noise, and satisfies N /2 N /2 1e d = 1 ,(28)0 (/2)where is the probability of finding b in radiusd 2 . If no solution is found, then the algorithm sets = 2 , and repeats the decoding process describe above until a solution is found.3. Simulation Results and Complexity AnalysisBit error proba
23、bility of OvTDM in AWGN channel-110L = 3L = 5-210-3Pb10-410-510-6107 8 9 10 11 12 1314Eb/N0 (dB)Fig. 2 Simulation results of Sphere-Decoding in AWGN channelIn figure 2, the parameters are set as follows:Q = 2 ,L = L = 3; 5 ,M = 10 ,N = M + L 1 , andh(n) =1 1 L 1 ,(29)which represents the most unfavo
24、rable situation form ISI point of view.According to 5 and 6, the expected complexity of Sphere-Decoding can be expressed as follows,(30)C (m, 2 , d 2 ) =M(expected points in k-dim sphere of radius d) .(points) k =1 Ep ( k , d 2 = N 2 )f p=8 k + 24wheref p represents the number of elementary operatio
25、ns per visited node to decodebk , includingmultiplication, addition and subtraction,f p = 8k + 24 ,(31)and Ep(k , d 2 = N 2 ) represents the expected number of the visited nodes to decoderandom variable depending on w.And the complexity exponent of the sphere-decoding is defined by2 2bk , which is a
26、Ec = log2 m C (m, d ) .(32)As shown in figure 4 and figure 5, for a wide range of normalized signal-to-noise ratio (Eb/N0), and different M and L, Ec is drawn, which indicates that the expected complexity of the sphere-decoding in the ISI channel is a polynomial of M. And comparing these two figures
27、 with figure 2, a conclusion can be drawn that all the complexity curve of Ec tends to 3 near the Eb/N0 which achieves the bit error ratio about 1e-5.5.55Ec vs. Eb/N0 when L=3M=5M=10M=154.5Pb43.532.527 8 9 10 11 12131415Eb/N0Fig. 3 Ec of different M in AWGN channel, L = 35.5Ec vs. Eb/N0 when M=10L=3
28、L=54.5Ec43.532.527 8 9 10111213 141516Eb/N0Fig. 4 Ec of different L in AWGN channel, M =104. ConclusionThe sphere-decoding is a fast MLSD algorithm with the expected complexity a polynomial of the transmission length M . And for different M and L, the expected complexity is a cubic polynomial of M w
29、hen the bit error ratio is about 1e-5.References1G. D. Forney, “.Maximum Likelihood Sequence Estimation of Digital Sequences in the Presence ofIntersymbol Interference, ” IEEE Trans. Inform. Theory, May 1972, IT-18, pp. 363378.2 Daoben Li, “Error Bounds for Homogeneous Random Time-Varying Intersymbo
30、l Interference Channels.”1988 Beijing International Workshop on Information Theory, June, 1988.3Andrew J. Viterbi, Jim K. Omura. Principles of Digital Communication and Coding. USA: McGraw-HillBook Company, 1979, pp. 272-286.4Sergio Verdu, “Maximum-likelihood Sequence Detection for Intersymbol Inter
31、ference Channels : A NewUpper Bound on Error Probability,” IEEE Trans. Inform. Theory, Jan. 1987, IT-33. 5 Babak Hassibi and Haris Vikalo, “On the Sphere-Decoding Algorithm I.Expected Complexity”, IEEE Trans. Signal Process, vol. 53, no. 8, August 2005.6 Haris Vikalo and Babak Hassibi, “On the Spher
32、e-Decoding Algorithm II.Generalizations, Second-Order Statistics, and Applications to Communications” IEEE Trans. Signal Process, vol. 53, no. 8, August 2005. 7 U. Fincke and M. Phost, “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis”, Math. Comput., Vol. 44, pp463-471, Apr. 1985.Author Brief Introduction：Yu Ke, master of Beijing University of Posts and Telecommunications, majored in WirelessCommunication .
