多符號差分酉空時(shí)系統的低復雜度M算法設計

學(xué)報【理學(xué)版第38卷第1期Journal ofrsity( Science Edition)o11年1月ls zju. edu. cn/seiJan. 2011DOI:10.3785/j.isn.10089497.2011.01.013多符號差分酉空時(shí)系統的低復雜度M算法設計金小萍,應櫻果,金寧(中國計量學(xué)院信息工程學(xué)院,浙江杭州310018)摘要:為了解決多符號差分檢測(MSDD)高計算復雜度的問(wèn)題,已經(jīng)提出了一系列低復雜度次優(yōu)的檢測算法,其中,M算法因其具有固定的復雜度和時(shí)延被廣泛關(guān)注.當前,M算法在多符號差分檢測中的運用大多假設每層的保留分支數M僬是相同的,而這種方法在復雜度的角度來(lái)看并不是最佳的方法,鑒于此本文提出了一種動(dòng)態(tài)M算法,即每層保留分支數設為不同的僬,通過(guò)仿真分析得出該方法與恒定M值的方法比較不僅使擴展和更新的分支數減少,而且在高信噪比時(shí)其性能更優(yōu)越.另外目前對M算法的研究主要集中在通過(guò)減少節點(diǎn)擴展分支數來(lái)降低復雜度,而對每層選取最佳M條路徑的排序方法的研究凡乎是空白,因此基于多符號差分檢測系統對一種低復雜度的排序方法進(jìn)行了研究。分析表明這種方法相比傳統冒泡排序方法可以節約75.39%的比較交換次數,該方法的運用使得M算法更有利于在實(shí)際當中的運用關(guān)鍵詞:多符號差分檢測;動(dòng)態(tài)M算法;復雜度;排序中圖分類(lèi)號:TN914文獻標志碼:A文章編號:10089497(2011)01-050-05JIN Xiao-ping, YING Ying-guo, JIN Ning( Department of In formation Engineering, China Jiliang UniversityHangzhou 310018, China)Reduced complexity M algorithm design for multiple symbol differential unitary space-time systems. Journal of ZhejiangUniversity(Science Edition), 2011, 38(1): 050-054Abstract: To solve the problem of high complexity for multiple symbol differential detection (MSDD), a series oflow complexity and sub-superior detect algorithms have been proposed so far, in which the M algorithm is well appreciated for its fixed complexity and latency. However the retained branches for each stage is assumed the samewhen the m algorithm is applied in the MSDD, but this method is not the best way in the view of complexity. In thispaper, we propose a dynamic M algorithm in which the retained branches of each stage can be set to different value.The simulation analysis shows that the proposed algorithm not only reduce the number of branches from expandedand updated, but also has a better performance than constant M method in high SNR. In addition, the research onM algorithm focus on reducing the extended branches from the nodes to decrease the complexity, but the research onsort method of selecting M best paths is almost blank, so a low complexity sort algorithm is studied based on MSDDsystem. analysis show that this sort architecture can save about 75. 39% of the compare swap operations com-pared with the traditional bubble sort method. The proposed algorithm makes the M algorithm better apply in prKey Words: MSDD: dynamic M algorithm: complexity: sort能間距,提出了多符號差分檢測(MSDD, multiple0引言symbol differential detection)算法(,然而該算法的復雜度隨著(zhù)發(fā)射天線(xiàn)數、星座點(diǎn)數以及分組長(cháng)度為了縮短相關(guān)檢測和差分檢測之間3dB的性成指數級增長(cháng)為了克服這個(gè)問(wèn)題,當前提出了一系收稿日期:201004-21基金項目:浙江省自然科學(xué)基金資助項目(Y107650)作者簡(jiǎn)介:金小萍(1978-),女,講師碩土,主要從事MIMO系統的檢測技術(shù)研究第1期金小萍,等:多符號差分酉空時(shí)系統的低復雜度M算法設計51列低復雜度算法2-51,如文獻[2]中的球形譯碼采用差分編碼得到發(fā)送矩陣為了SE策略,雖然沒(méi)有減少度量值的計算,但是降低S[k]=V[k]S[k-1],S[0]=Ix,(2)了比較次數;文獻[5]提出的BID(邊界交集檢測)算其中S[0]為初始單位矩陣,不攜帶任何數據信息法,通過(guò)半徑約束選擇較好的星座,從而減少分支度假設衰落信道H中的元素是相互獨立的,具有量值的計算來(lái)降低復雜度.然而這些算法大多存在相同的時(shí)間統計特性,并且服從經(jīng)典的瑞利信道模兩大問(wèn)題:一是它們采用的序列搜索方法使得流水型.進(jìn)一步假設在N+1個(gè)發(fā)送符號時(shí)間內衰落系線(xiàn)和并行操作非常困難;二是操作時(shí)延的隨機性數保持不變(準靜態(tài)衰落信道),那么對應于發(fā)送符M算法(或稱(chēng)為 K-best算法)因為具有相同的號Sk]的NXNk維接收信號矩陣可以表示為歷史路徑長(cháng)度,使其不具有上面的缺陷,所以也被應RCk]=SCk]HLk]+W[k]用于多符號差分檢測當中6-.簡(jiǎn)單地說(shuō),M算法就其中噪聲矩陣Wk]中的元素是零均值復高斯白噪聲是在每一檢測層保留M條較好的路徑,從而具有穩在多符號差分檢測系統中,接收機連續接收N定的復雜度的優(yōu)點(diǎn)但M算法的運用目前還存在著(zhù)+1個(gè)符號來(lái)檢測N個(gè)符號.文獻[5]主要介紹了以下問(wèn)題:一是每層保留的路徑數,即M值都是取BID算法在多符號差分檢測系統中的應用,其度量固定的值,從復雜度角度上分析這種方法并不是最值計算的公式同樣可以應用在本文提出的算法中佳的方法,且其依然較高的復雜度使得該算法還不因此在此不再詳細描述根據文獻[5],其判決度量能應用于實(shí)際中;二是當前對M算法的研究集中在可得通過(guò)降低路徑擴展數來(lái)降低計算復雜度,并沒(méi)有對+N=每層排序的復雜度進(jìn)行深入分析針對上面兩個(gè)問(wèn)題,本文進(jìn)行了改進(jìn):一是采用argmin‖R[+k-1動(dòng)態(tài)M算法,即每層的M取不同的值,基本原則是高層的M值比低層的M值要大,通過(guò)仿真分析得a(Ivm])×R[計+k-1]1.(4)出,這種方法不僅在路徑擴展數和更新數上大大減這里令a,=1,表示檢測的開(kāi)始時(shí)刻少,而且在高信噪比時(shí)其性能比傳統的M算法要優(yōu)越針對第二個(gè)問(wèn)題本文在每層的排序上采用了2動(dòng)態(tài)M算法Batcher合并排序算法,這個(gè)算法相比傳統的冒泡排序法能大大降低比較交換的次數通過(guò)動(dòng)態(tài)M算M算法是一種寬度優(yōu)先的序列搜索算法.它法和 Batcher合并排序算法的結合,較低的復雜度的基本原理是根據某種準則保留M條路徑,然后將使得該算法更有利于實(shí)際的運用這M條路徑進(jìn)行延伸,組成新的bM條路徑,并計算這些所有路徑的判決度量,最后將(b-1)M條最1系統模型差的路徑刪除,如此一直持續到所有的信息全部判決出來(lái).傳統的M算法中每層保留的路徑數M是考慮在平坦衰落信道下,一個(gè)具有N1個(gè)發(fā)射固定的文獻12]中提出了一種自適應M算法,它天線(xiàn)與NA個(gè)接收天線(xiàn)的差分酉空時(shí)調制系統發(fā)根據信道狀態(tài)對樹(shù)的不同層取不同的M值,這種方送符號由一個(gè)固定的星座集v={V,l=0,1法的前提是要求接收端已知信道狀態(tài)信息,這對于1}產(chǎn)生的.特別地,筆者采用對角星座,西矩差分檢測來(lái)說(shuō)是無(wú)法滿(mǎn)足的本文在M算法基礎上陣V(VVH=ⅠN,)的映射如下提出一種動(dòng)態(tài)M算法,它的基本思想是在早期的檢測層使用較大的M值,在檢測低層的時(shí)候減少MI=diage值.其原理是:在第i(比較大)層檢測的時(shí)候,在到l∈{0,1,…,L-1}(1)達最后分支的時(shí)候還有i-1層的分支度量值需要式中,(i=1,2,…,N)由文獻[10]可以得到,在這計算,若每層保留的分支數M較小,則在早期刪除里不再詳細介紹,它的選擇能夠達到最大分集,獲得最大似然值的幾率會(huì )增大,M值的增大可以減少這較好的增益L=2,R代表傳輸速率.本文中假設種情況發(fā)生的可能性;隨著(zhù)i的遞減,分支度量值越R=l bit/來(lái)越接近最后的結果,最大似然值被刪除的幾率就首先將毎NR個(gè)信息比特映射成星座V[k],越來(lái)越小,因此在檢測低層的時(shí)候減少M值,這樣V[A]是星座集中的NXNr維矩陣,對V[k進(jìn)行可以降低計算復雜度卻同時(shí)保證了算法的性能由浙江大學(xué)學(xué)報(理學(xué)版)第38卷于針對差分檢測系統,如何自適應地改變每層的M值并沒(méi)有一定的規律本文通過(guò)了大量的仿真測試獲得M的較佳取值狀態(tài).其流程如圖1所示初始化L,N+1,每層分支數M,M、1,M,…,M10計算L個(gè)星座點(diǎn)的度量值,保留M條路徑M=[I6161M=[1281擴展M個(gè)節點(diǎn)到子節點(diǎn),組成新的LM條路徑日-M叫16161616☆-…M-[168881葉算新路徑的度量值。保留較小的M條141618圖3瑞利衰落信道下,N=4,NR=1,分組長(cháng)度為4和6時(shí)圖1動(dòng)態(tài)M算法流程圖M算法和動(dòng)態(tài)的M算法及C.D相關(guān)檢測的性能比較Fig. 1 The flow chart of Dynamic M algorithmFig 3 Performance comparison among the M algorithmthe dynamic M algorithm and the C D algorithm ov圖2和圖3是M算法、動(dòng)態(tài)M算法和相關(guān)檢Rayleigh Fading Channel, when Nr=4, NR=1測(CD)算法分別在發(fā)送天線(xiàn)數為3和4的性能比the block length is 4 and 6 respectively較圖.在仿真過(guò)程中,使用的是準靜態(tài)的平坦瑞利衰落信道,發(fā)送天線(xiàn)之間假設是相互獨立的,并設歸從圖2和圖3中可以看出,動(dòng)態(tài)M算法在低信化最大多普勒頻移foT為0.0075圖2中M=[8噪比的時(shí)候,能夠過(guò)近M算法的性能在高信噪比81]代表分組長(cháng)度N+1為4時(shí),各層分別保留8的時(shí)候,動(dòng)態(tài)M算法的性能甚至優(yōu)于M算法,這是條、8條1條路徑,即傳統M算法的取值方法;而M由于通過(guò)減少度量值較大的分支數,從而促使發(fā)生[841]代表分組長(cháng)度N+1為4時(shí),各層分別保錯誤的概率減少.如圖2中所示,在誤碼率為10-3時(shí),分組長(cháng)度N+1為4的情況下,動(dòng)態(tài)M算法的留8條、8條、1條路徑,即動(dòng)態(tài)M算法的取值方法、信噪比降低了16.23-15.88=0.35dB,而在誤碼M=[88881]和M=[86641]代表分組長(cháng)度為N+1為6時(shí),傳統M算法和動(dòng)態(tài)M算法的取值分率為10,分組長(cháng)度為6的情況下,動(dòng)態(tài)M算法的布情況.圖3同上,信噪比降低了18.56-18.20=0.36dB.圖3中所示,在誤碼率為10-時(shí),分組長(cháng)度N+1為4的情況-e-M=88IM=[841下,動(dòng)態(tài)M算法的信噪比降低了13.12-12.70=0.42dB而在誤碼率為10-3,分組長(cháng)度為6的情況☆-…M={86641x--.C D下,動(dòng)態(tài)M算法的信噪比降低了12.20-11.80=0.40dB.由圖2和圖3對比可知,動(dòng)態(tài)M算法具有較好的空間分集能力3改進(jìn)的排序方法在M算法中,過(guò)多的比較次數也是其計算復雜度高的原因之一.針對如何減少比較次數,本文采用SNR/dB了一種改進(jìn)的排序方法,稱(chēng)為 Batcher合并排序算圖2瑞利衰落信道下,N=3N=1,分組長(cháng)度為4和6時(shí),法,該排序的前提是每個(gè)擴展節點(diǎn)已經(jīng)經(jīng)過(guò)簡(jiǎn)單的M算法和動(dòng)態(tài)M算法及C.D相關(guān)檢測的性能比較升序排列.這種改進(jìn)的排序方法比起傳統的冒泡排Fig 2 Performance comparison among the m algorithm.the dynamic M algorithm and the C.d algorithm over序,可以大大減少比較次數,而不改變系統的性能Rayleigh Fading Channel, when N=3, NR=l,圖4顯示了16*16的排序結構,主要由兩個(gè)有16the block length is 4 and 6 respectively個(gè)已經(jīng)升序排列的陣列和16個(gè)最小輸出組成.8*第1期金小萍,等:多符號差分酉空時(shí)系統的低復雜度M算法設計8、4*4、2*2的比較模塊也已在圖中表示.顯而易又由2個(gè)2“2加上兩個(gè)額外的C&S構成.每個(gè)最見(jiàn),6*6、5*5、3*3比較模塊能從8*8、4*4、2*2小模塊2*2只需3個(gè)C&S.因此總共需要(2*3+等模塊中推導得出2)*2+4=20次比較.由此可見(jiàn),改進(jìn)的排序方法例如,M=8,N=3,Ng=1時(shí),用冒泡法排序能夠將比較次數降低70%假設M,表示上一層保的情況下,每一層需要63+62+…+56=476次比留分支數,M,-1表示當前層要保留的分支數,L是星較而用 Batcher合并排序算法,只要7個(gè)8“8模座點(diǎn)數.表1中列出了幾種檢測情況的比較次數.從塊的比較就足夠了.每個(gè)8*8模塊由2個(gè)4*4加表1中可以得出改進(jìn)的排序方法的比較次數比起傳上4個(gè)額外的C8S(比較和交換)組成而一個(gè)4*4統的冒泡排序降低了70%~80%數位的奇數傳的數合并比較合片比較比較模塊合井比較位嫩微圖4改進(jìn)的排序結構Fig 4 The improved sort architecture表1排序復雜度比較Table 1 Sort complexity comparison(C&S)M=8,M-1=8,L=8M,=8,M,-1=6,L=8M=16,M,;=16,L=16M=16,M1-1=8,L=16冒泡排序63+62+…+56=47647+46+…+42=267255+254+…+240=3960255+254+…+248=2012改進(jìn)的排序20,7=140204+19=9948*15=720814+44=716(2)路徑的更新對于每個(gè)存活節點(diǎn)都需要更復雜度分析新它們的度量值,用于接下去的路徑度量值計算.對于M算法,總共8*4=32條路徑需要更新,需要計本節主要對應用了動(dòng)態(tài)M算法和改進(jìn)的排序算8*1+8*2+8*3+8“4=80個(gè)乘法數和加法算法的多符號差分酉空時(shí)系統的復雜度進(jìn)行分析.數;而對于動(dòng)態(tài)M算法,只需8+6+6+4=24條路以3發(fā)1收的差分酉空時(shí)調制系統,分組長(cháng)度N+1徑需要更新,需要計算8*1+6*2+6*3+4*4=為6為例.54個(gè)乘法數和加法數,節省了25%左右的計算M算法中,M取8即M=[88881],動(dòng)態(tài)M(3)排序對于M算法,在每一檢測層(除了算法中,M=[86641].從以下3個(gè)方面進(jìn)行分析:第一層),需要從8*8=64條路徑中選出8條度量(1)路徑的擴展對于M算法來(lái)說(shuō),在頂層需值比較小的分支,用傳統的冒泡法排序,總共需要要計算8個(gè)PEDs(部分歐氏距離)(每個(gè)PED計算476*3+63=1491(最后一層是從64條路徑中保由一個(gè)乘法,兩個(gè)加法和1個(gè)MAX操作構成),留1條)次比較而動(dòng)態(tài)M算法與改進(jìn)的排序算法接下去幾層需要對每個(gè)存活節點(diǎn)擴展8個(gè)子節點(diǎn),結合之后,頂層不需要排序第二層從64條中選6直至檢測到最后一層得出最佳路徑因此總共需要條因此需要20*6+19=139次比較,第三層從48計算8+8*8+8*8+8*8+8*8=264個(gè)PEDs.條中保留6條,需要20*4+19=99次比較,第四層而對于動(dòng)態(tài)M算法我們只需要計算8+8*8+6從48條中保留4條,需要20*4+18=98次比較8十6*8十4*8=200個(gè)PEDs,這比M算法降低五層從32條中保留1條最佳路徑,不需要采用改進(jìn)了24.2%左右的復雜度的排序算法,需要31次比較,則總共需要139+99+浙江大學(xué)學(xué)報(理學(xué)版)第38卷98+31=367次比較,降低了75.39%的比較次數比較次數.通過(guò)將動(dòng)態(tài)M算法與改進(jìn)的排序方法進(jìn)假設發(fā)送天線(xiàn)為N,星座點(diǎn)數為L(cháng),接收機連行結合應用于多符號差分酉空時(shí)系統得出它比傳續接收N+1個(gè)符號檢測N個(gè)符號.經(jīng)大量仿真測統的M算法在高信噪比時(shí)性能得到提高,并且計算試,動(dòng)態(tài)M算法,每一檢測層保留的分支分別為復雜度獲得較大幅度的下降該方法的應用可以節M(mǎn),M、-1,M、-2;…,M1條,而M箅法則MN=省大量資源,利于硬件實(shí)現MN-1=…=M2.表2用同上2的方法,用公式顯示了兩種算法的比較次數情況.這里M算法和動(dòng)態(tài)M參考文獻( References):算法的最后一層均只要選擇最佳分支即可,即M1=1注:表2中的豆,一=N-1,-2…,2代表取模,[1 DIVSALAR D, SIMONMK.. Multiple symbol differntial detection of MPSK [J]. IEEE Trans Commun即mod(M,,2).3代表最小2*2模塊的比較交換次1990,38(3):300-308數.其中[2] LAMPE L, SCHOBER R, PAULI V, et al. Multiple-K=(162+2+-)·2+2=)*…+)symbol differential sphere decoding [J]. IEEE TransCommun,2005,53(12):1981-1985(422)2=)…+)2[3] PAULI V, LAMPE L. Tree-search multiple-symbol differential decoding for unitary space-time modulation [J].當L=4時(shí),J=3*2.IEEE Trans Info Theory, 2007,55(8): 1567-1576總的復雜度結果如表3所示,其中MAX表示[4] PUN P K M, HO P K M. Fano multiple-symbol differ-平方的次數.從表3可以觀(guān)察到,改進(jìn)后的M算法detectors for differential unitary space- time modula比傳統的M算法復雜度大大降低了,從而在硬件上J]. IEEE Trans on Comms, 2007, 55(3):540-550[5] CUI T. Chinthananda tellambura. bound-Intersection節省了資源detection for multiple symbol differential unitary space表2M算法和動(dòng)態(tài)M算法的總的比較次數time modulation [J]. IEEE Trans Commun, 2005,53Table 2 The total C&S of the M algorithm and(12):2114-2123.he dynamic M algorithm[6] JIA Z, HANDA S, SASAMORI F. Multiple-symbolM,My-1,My-2…,M1differential detection for space-time block codes overM√L-1+MNL-2+…+MxL-Mx-1+MN-1冒泡排序L-1+…+My1L-Mx-x+…+M1L-1fast rayleigh fading channels[C]//Guilin, China,10thInternational Conference of Communications TechnoloBatcher K(MN-2)+J+N1+K(MN-I-2)+J+gy,2006:1461-1464.[7] JIN Ning, JIN Xiao-ping. Reduced complexity MSDD合并排序My2+…+K(M-2)+1+2+M2Lof STBC over fast rayleigh fading channel[C]//In Sig-表3Nr=3,分組長(cháng)度為6時(shí)總的復雜度比較al Processing, 2008 ICSP, 2008: 26-29[8] LI Qing-wei. WANG Zhong-feng. Reduced complexityTable 3 Total complexity comparison when N=3K-best sphere decoder design for MIMO systems[J].the block length is 4Circuits Syst Signal Process, 2008,271491-505加法數乘法數c&s[9] HOCHWALD B M, SWELDENS算法tary space-time modulation[J]. IEEE Trans Commun改進(jìn)的M算法454200048(12):2041-205225.33%26.16%24%75.39%[10] HOCHWALD B M, SWELDENS W. Differential unitary space- time modulation [J]. IEEE Trans Com5結論[ll] ANDERSON J B, MOHAN S. Sequential coding al本文提出了一種動(dòng)態(tài)M算法.經(jīng)仿真測試,這and cost analysis[J]. IEEE Trans種算法在低信噪比的時(shí)候性能能夠通近傳統的MCommun,1984,32(2):169-176.算法,在高信噪比的時(shí)候性能優(yōu)于M算法,而且與2] LAIK C, LIN Li-wei. Low-complexity adaptive tree傳統的M算法相比降低了多符號差分檢測的計算search algorithm for MIMO detection[J].IEEE TransCommun,2009,8(7):3716-3726復雜度另外,還提出了一種改進(jìn)的排序方法,與傳統的冒泡排序法相比,該方法能夠減少75.39%的(責任編輯涂紅)