Sphere-Decoding of Signals With ISI.doc

精品论文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 commonly 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 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 which 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 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 the 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 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 convolution 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 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 (intersymbol 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 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 denoted 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 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 integer 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 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 simplified 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 =| 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 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 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 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)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 gaussian 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 probability 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 unfavorable 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 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 aec = 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 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=3l=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 when 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 interference channels.”1988 beijing international workshop on information theory, june