《Sphere-Decoding of Signals With ISI.doc》由会员分享，可在线阅读，更多相关《Sphere-Decoding 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_AbstractSphere-Decoding is a newly developed fast MLSD (Maximum Likelyhood Sequence Decoding)algorithm commo
2、nly 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 giv
3、en.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 which
4、 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 length wh
5、en 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 the o
6、utput 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 bys
7、i (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 convolution o
8、peration 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 i) =
9、 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 (intersymbol i
10、nterference) 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 noi
11、sewith 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 denoted
12、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 typ
13、ical 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 integer
14、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 :| y
15、 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 simpl
16、ified 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 rMM
18、 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)andthenbM
19、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 summarized a
20、s 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)If
21、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 Gaussi
22、an 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 probabili
23、ty 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 unfavorabl
24、e 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 operations p
25、er 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 aEc =
26、 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 wit
27、h 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=3L=54
28、.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 when
29、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 Intersymbol In
30、terference 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 Interfere
31、nce 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 Sphere-De
32、coding 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 .