學報【理學版第38卷第1期Journal ofrsity( Science Edition)o11年1月ls zju. edu. cn/seiJan. 2011DOI:10.3785/j.isn.10089497.2011.01.013多符號差分酉空時系統(tǒng)的低復雜度M算法設(shè)計金小萍,應(yīng)櫻果,金寧(中國計量學院信息工程學院,浙江杭州310018)摘要:為了解決多符號差分檢測(MSDD)高計算復雜度的問題,已經(jīng)提出了一系列低復雜度次優(yōu)的檢測算法,其中,M算法因其具有固定的復雜度和時延被廣泛關(guān)注.當前,M算法在多符號差分檢測中的運用大多假設(shè)每層的保留分支數(shù)M僬是相同的,而這種方法在復雜度的角度來看并不是最佳的方法,鑒于此本文提出了一種動態(tài)M算法,即每層保留分支數(shù)設(shè)為不同的僬,通過仿真分析得出該方法與恒定M值的方法比較不僅使擴展和更新的分支數(shù)減少,而且在高信噪比時其性能更優(yōu)越.另外目前對M算法的研究主要集中在通過減少節(jié)點擴展分支數(shù)來降低復雜度,而對每層選取最佳M條路徑的排序方法的研究凡乎是空白,因此基于多符號差分檢測系統(tǒng)對一種低復雜度的排序方法進行了研究。分析表明這種方法相比傳統(tǒng)冒泡排序方法可以節(jié)約75.39%的比較交換次數(shù),該方法的運用使得M算法更有利于在實際當中的運用關(guān)鍵詞:多符號差分檢測;動態(tài)M算法;復雜度;排序中圖分類號: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)算法(,然而該算法的復雜度隨著發(fā)射天線數(shù)、星座點數(shù)以及分組長度為了縮短相關(guān)檢測和差分檢測之間3dB的性成指數(shù)級增長為了克服這個問題,當前提出了一系收稿日期:201004-21基金項目:浙江省自然科學基金資助項目(Y107650)作者簡介:金小萍(1978-),女,講師碩土,主要從事MIMO系統(tǒng)的檢測技術(shù)研究第1期金小萍,等:多符號差分酉空時系統(tǒng)的低復雜度M算法設(shè)計51列低復雜度算法2-51,如文獻[2]中的球形譯碼采用差分編碼得到發(fā)送矩陣為了SE策略,雖然沒有減少度量值的計算,但是降低S[k]=V[k]S[k-1],S[0]=Ix,(2)了比較次數(shù);文獻[5]提出的BID(邊界交集檢測)算其中S[0]為初始單位矩陣,不攜帶任何數(shù)據(jù)信息法,通過半徑約束選擇較好的星座,從而減少分支度假設(shè)衰落信道H中的元素是相互獨立的,具有量值的計算來降低復雜度.然而這些算法大多存在相同的時間統(tǒng)計特性,并且服從經(jīng)典的瑞利信道模兩大問題:一是它們采用的序列搜索方法使得流水型.進一步假設(shè)在N+1個發(fā)送符號時間內(nèi)衰落系線和并行操作非常困難;二是操作時延的隨機性數(shù)保持不變(準靜態(tài)衰落信道),那么對應(yīng)于發(fā)送符M算法(或稱為 K-best算法)因為具有相同的號Sk]的NXNk維接收信號矩陣可以表示為歷史路徑長度,使其不具有上面的缺陷,所以也被應(yīng)RCk]=SCk]HLk]+W[k]用于多符號差分檢測當中6-.簡單地說,M算法就其中噪聲矩陣Wk]中的元素是零均值復高斯白噪聲是在每一檢測層保留M條較好的路徑,從而具有穩(wěn)在多符號差分檢測系統(tǒng)中,接收機連續(xù)接收N定的復雜度的優(yōu)點但M算法的運用目前還存在著+1個符號來檢測N個符號.文獻[5]主要介紹了以下問題:一是每層保留的路徑數(shù),即M值都是取BID算法在多符號差分檢測系統(tǒng)中的應(yīng)用,其度量固定的值,從復雜度角度上分析這種方法并不是最值計算的公式同樣可以應(yīng)用在本文提出的算法中佳的方法,且其依然較高的復雜度使得該算法還不因此在此不再詳細描述根據(jù)文獻[5],其判決度量能應(yīng)用于實際中;二是當前對M算法的研究集中在可得通過降低路徑擴展數(shù)來降低計算復雜度,并沒有對+N=每層排序的復雜度進行深入分析針對上面兩個問題,本文進行了改進:一是采用argmin‖R[+k-1動態(tài)M算法,即每層的M取不同的值,基本原則是高層的M值比低層的M值要大,通過仿真分析得a(Ivm])×R[計+k-1]1.(4)出,這種方法不僅在路徑擴展數(shù)和更新數(shù)上大大減這里令a,=1,表示檢測的開始時刻少,而且在高信噪比時其性能比傳統(tǒng)的M算法要優(yōu)越針對第二個問題本文在每層的排序上采用了2動態(tài)M算法Batcher合并排序算法,這個算法相比傳統(tǒng)的冒泡排序法能大大降低比較交換的次數(shù)通過動態(tài)M算M算法是一種寬度優(yōu)先的序列搜索算法.它法和 Batcher合并排序算法的結(jié)合,較低的復雜度的基本原理是根據(jù)某種準則保留M條路徑,然后將使得該算法更有利于實際的運用這M條路徑進行延伸,組成新的bM條路徑,并計算這些所有路徑的判決度量,最后將(b-1)M條最1系統(tǒng)模型差的路徑刪除,如此一直持續(xù)到所有的信息全部判決出來.傳統(tǒng)的M算法中每層保留的路徑數(shù)M是考慮在平坦衰落信道下,一個具有N1個發(fā)射固定的文獻12]中提出了一種自適應(yīng)M算法,它天線與NA個接收天線的差分酉空時調(diào)制系統(tǒng)發(fā)根據(jù)信道狀態(tài)對樹的不同層取不同的M值,這種方送符號由一個固定的星座集v={V,l=0,1法的前提是要求接收端已知信道狀態(tài)信息,這對于1}產(chǎn)生的.特別地,筆者采用對角星座,西矩差分檢測來說是無法滿足的本文在M算法基礎(chǔ)上陣V(VVH=ⅠN,)的映射如下提出一種動態(tài)M算法,它的基本思想是在早期的檢測層使用較大的M值,在檢測低層的時候減少MI=diage值.其原理是:在第i(比較大)層檢測的時候,在到l∈{0,1,…,L-1}(1)達最后分支的時候還有i-1層的分支度量值需要式中,(i=1,2,…,N)由文獻[10]可以得到,在這計算,若每層保留的分支數(shù)M較小,則在早期刪除里不再詳細介紹,它的選擇能夠達到最大分集,獲得最大似然值的幾率會增大,M值的增大可以減少這較好的增益L=2,R代表傳輸速率.本文中假設(shè)種情況發(fā)生的可能性;隨著i的遞減,分支度量值越R=l bit/來越接近最后的結(jié)果,最大似然值被刪除的幾率就首先將毎NR個信息比特映射成星座V[k],越來越小,因此在檢測低層的時候減少M值,這樣V[A]是星座集中的NXNr維矩陣,對V[k進行可以降低計算復雜度卻同時保證了算法的性能由浙江大學學報(理學版)第38卷于針對差分檢測系統(tǒng),如何自適應(yīng)地改變每層的M值并沒有一定的規(guī)律本文通過了大量的仿真測試獲得M的較佳取值狀態(tài).其流程如圖1所示初始化L,N+1,每層分支數(shù)M,M、1,M,…,M10計算L個星座點的度量值,保留M條路徑M=[I6161M=[1281擴展M個節(jié)點到子節(jié)點,組成新的LM條路徑日-M叫16161616☆-…M-[168881葉算新路徑的度量值。保留較小的M條141618圖3瑞利衰落信道下,N=4,NR=1,分組長度為4和6時圖1動態(tài)M算法流程圖M算法和動態(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算法、動態(tài)M算法和相關(guān)檢Rayleigh Fading Channel, when Nr=4, NR=1測(CD)算法分別在發(fā)送天線數(shù)為3和4的性能比the block length is 4 and 6 respectively較圖.在仿真過程中,使用的是準靜態(tài)的平坦瑞利衰落信道,發(fā)送天線之間假設(shè)是相互獨立的,并設(shè)歸從圖2和圖3中可以看出,動態(tài)M算法在低信化最大多普勒頻移foT為0.0075圖2中M=[8噪比的時候,能夠過近M算法的性能在高信噪比81]代表分組長度N+1為4時,各層分別保留8的時候,動態(tài)M算法的性能甚至優(yōu)于M算法,這是條、8條1條路徑,即傳統(tǒng)M算法的取值方法;而M由于通過減少度量值較大的分支數(shù),從而促使發(fā)生[841]代表分組長度N+1為4時,各層分別保錯誤的概率減少.如圖2中所示,在誤碼率為10-3時,分組長度N+1為4的情況下,動態(tài)M算法的留8條、8條、1條路徑,即動態(tài)M算法的取值方法、信噪比降低了16.23-15.88=0.35dB,而在誤碼M=[88881]和M=[86641]代表分組長度為N+1為6時,傳統(tǒng)M算法和動態(tài)M算法的取值分率為10,分組長度為6的情況下,動態(tài)M算法的布情況.圖3同上,信噪比降低了18.56-18.20=0.36dB.圖3中所示,在誤碼率為10-時,分組長度N+1為4的情況-e-M=88IM=[841下,動態(tài)M算法的信噪比降低了13.12-12.70=0.42dB而在誤碼率為10-3,分組長度為6的情況☆-…M={86641x--.C D下,動態(tài)M算法的信噪比降低了12.20-11.80=0.40dB.由圖2和圖3對比可知,動態(tài)M算法具有較好的空間分集能力3改進的排序方法在M算法中,過多的比較次數(shù)也是其計算復雜度高的原因之一.針對如何減少比較次數(shù),本文采用SNR/dB了一種改進的排序方法,稱為 Batcher合并排序算圖2瑞利衰落信道下,N=3N=1,分組長度為4和6時,法,該排序的前提是每個擴展節(jié)點已經(jīng)經(jīng)過簡單的M算法和動態(tài)M算法及C.D相關(guān)檢測的性能比較升序排列.這種改進的排序方法比起傳統(tǒng)的冒泡排Fig 2 Performance comparison among the m algorithm.the dynamic M algorithm and the C.d algorithm over序,可以大大減少比較次數(shù),而不改變系統(tǒng)的性能Rayleigh Fading Channel, when N=3, NR=l,圖4顯示了16*16的排序結(jié)構(gòu),主要由兩個有16the block length is 4 and 6 respectively個已經(jīng)升序排列的陣列和16個最小輸出組成.8*第1期金小萍,等:多符號差分酉空時系統(tǒng)的低復雜度M算法設(shè)計8、4*4、2*2的比較模塊也已在圖中表示.顯而易又由2個2“2加上兩個額外的C&S構(gòu)成.每個最見,6*6、5*5、3*3比較模塊能從8*8、4*4、2*2小模塊2*2只需3個C&S.因此總共需要(2*3+等模塊中推導得出2)*2+4=20次比較.由此可見,改進的排序方法例如,M=8,N=3,Ng=1時,用冒泡法排序能夠?qū)⒈容^次數(shù)降低70%假設(shè)M,表示上一層保的情況下,每一層需要63+62+…+56=476次比留分支數(shù),M,-1表示當前層要保留的分支數(shù),L是星較而用 Batcher合并排序算法,只要7個8“8模座點數(shù).表1中列出了幾種檢測情況的比較次數(shù).從塊的比較就足夠了.每個8*8模塊由2個4*4加表1中可以得出改進的排序方法的比較次數(shù)比起傳上4個額外的C8S(比較和交換)組成而一個4*4統(tǒng)的冒泡排序降低了70%~80%數(shù)位的奇數(shù)傳的數(shù)合并比較合片比較比較模塊合井比較位嫩微圖4改進的排序結(jié)構(gòu)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改進的排序20,7=140204+19=9948*15=720814+44=716(2)路徑的更新對于每個存活節(jié)點都需要更復雜度分析新它們的度量值,用于接下去的路徑度量值計算.對于M算法,總共8*4=32條路徑需要更新,需要計本節(jié)主要對應(yīng)用了動態(tài)M算法和改進的排序算8*1+8*2+8*3+8“4=80個乘法數(shù)和加法算法的多符號差分酉空時系統(tǒng)的復雜度進行分析.數(shù);而對于動態(tài)M算法,只需8+6+6+4=24條路以3發(fā)1收的差分酉空時調(diào)制系統(tǒng),分組長度N+1徑需要更新,需要計算8*1+6*2+6*3+4*4=為6為例.54個乘法數(shù)和加法數(shù),節(jié)省了25%左右的計算M算法中,M取8即M=[88881],動態(tài)M(3)排序?qū)τ贛算法,在每一檢測層(除了算法中,M=[86641].從以下3個方面進行分析:第一層),需要從8*8=64條路徑中選出8條度量(1)路徑的擴展對于M算法來說,在頂層需值比較小的分支,用傳統(tǒng)的冒泡法排序,總共需要要計算8個PEDs(部分歐氏距離)(每個PED計算476*3+63=1491(最后一層是從64條路徑中保由一個乘法,兩個加法和1個MAX操作構(gòu)成),留1條)次比較而動態(tài)M算法與改進的排序算法接下去幾層需要對每個存活節(jié)點擴展8個子節(jié)點,結(jié)合之后,頂層不需要排序第二層從64條中選6直至檢測到最后一層得出最佳路徑因此總共需要條因此需要20*6+19=139次比較,第三層從48計算8+8*8+8*8+8*8+8*8=264個PEDs.條中保留6條,需要20*4+19=99次比較,第四層而對于動態(tài)M算法我們只需要計算8+8*8+6從48條中保留4條,需要20*4+18=98次比較8十6*8十4*8=200個PEDs,這比M算法降低五層從32條中保留1條最佳路徑,不需要采用改進了24.2%左右的復雜度的排序算法,需要31次比較,則總共需要139+99+浙江大學學報(理學版)第38卷98+31=367次比較,降低了75.39%的比較次數(shù)比較次數(shù).通過將動態(tài)M算法與改進的排序方法進假設(shè)發(fā)送天線為N,星座點數(shù)為L,接收機連行結(jié)合應(yīng)用于多符號差分酉空時系統(tǒng)得出它比傳續(xù)接收N+1個符號檢測N個符號.經(jīng)大量仿真測統(tǒng)的M算法在高信噪比時性能得到提高,并且計算試,動態(tài)M算法,每一檢測層保留的分支分別為復雜度獲得較大幅度的下降該方法的應(yīng)用可以節(jié)M,M、-1,M、-2;…,M1條,而M箅法則MN=省大量資源,利于硬件實現(xiàn)MN-1=…=M2.表2用同上2的方法,用公式顯示了兩種算法的比較次數(shù)情況.這里M算法和動態(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數(shù).其中[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時,J=3*2.IEEE Trans Info Theory, 2007,55(8): 1567-1576總的復雜度結(jié)果如表3所示,其中MAX表示[4] PUN P K M, HO P K M. Fano multiple-symbol differ-平方的次數(shù).從表3可以觀察到,改進后的M算法detectors for differential unitary space- time modula比傳統(tǒng)的M算法復雜度大大降低了,從而在硬件上J]. IEEE Trans on Comms, 2007, 55(3):540-550[5] CUI T. Chinthananda tellambura. bound-Intersection節(jié)省了資源detection for multiple symbol differential unitary space表2M算法和動態(tài)M算法的總的比較次數(shù)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,分組長度為6時總的復雜度比較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加法數(shù)乘法數(shù)c&s[9] HOCHWALD B M, SWELDENS算法tary space-time modulation[J]. IEEE Trans Commun改進的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結(jié)論[ll] ANDERSON J B, MOHAN S. Sequential coding al本文提出了一種動態(tài)M算法.經(jīng)仿真測試,這and cost analysis[J]. IEEE Trans種算法在低信噪比的時候性能能夠通近傳統(tǒng)的MCommun,1984,32(2):169-176.算法,在高信噪比的時候性能優(yōu)于M算法,而且與2] LAIK C, LIN Li-wei. Low-complexity adaptive tree傳統(tǒng)的M算法相比降低了多符號差分檢測的計算search algorithm for MIMO detection[J].IEEE TransCommun,2009,8(7):3716-3726復雜度另外,還提出了一種改進的排序方法,與傳統(tǒng)的冒泡排序法相比,該方法能夠減少75.39%的(責任編輯涂紅)