多符号差分酉空时系统的低复杂度M算法设计

学报【理学版第38卷第1期Journal ofrsity( Science Edition)o11年1月ls zju. edu. cn/seiJan. 2011DOI:10.3785/j.isn.10089497.2011.01.013多符号差分酉空时系统的低复杂度M算法设计金小萍,应樱果,金宁(中国计量学院信息工程学院,浙江杭州310018)摘要:为了解决多符号差分检测(MSDD)高计算复杂度的问题,已经提出了一系列低复杂度次优的检测算法,其中,M算法因其具有固定的复杂度和时延被广泛关注.当前,M算法在多符号差分检测中的运用大多假设每层的保留分支数M僬是相同的,而这种方法在复杂度的角度来看并不是最佳的方法,鉴于此本文提出了一种动态M算法,即每层保留分支数设为不同的僬,通过仿真分析得出该方法与恒定M值的方法比较不仅使扩展和更新的分支数减少,而且在高信噪比时其性能更优越.另外目前对M算法的研究主要集中在通过减少节点扩展分支数来降低复杂度,而对每层选取最佳M条路径的排序方法的研究凡乎是空白,因此基于多符号差分检测系统对一种低复杂度的排序方法进行了研究。分析表明这种方法相比传统冒泡排序方法可以节约75.39%的比较交换次数,该方法的运用使得M算法更有利于在实际当中的运用关键词:多符号差分检测;动态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)算法(,然而该算法的复杂度随着发射天线数、星座点数以及分组长度为了缩短相关检测和差分检测之间3dB的性成指数级增长为了克服这个问题,当前提出了一系收稿日期:201004-21基金项目:浙江省自然科学基金资助项目(Y107650)作者简介:金小萍(1978-),女,讲师硕土,主要从事MIMO系统的检测技术研究第1期金小萍,等:多符号差分酉空时系统的低复杂度M算法设计51列低复杂度算法2-51,如文献[2]中的球形译码采用差分编码得到发送矩阵为了SE策略,虽然没有减少度量值的计算,但是降低S[k]=V[k]S[k-1],S[0]=Ix,(2)了比较次数;文献[5]提出的BID(边界交集检测)算其中S[0]为初始单位矩阵,不携带任何数据信息法,通过半径约束选择较好的星座,从而减少分支度假设衰落信道H中的元素是相互独立的,具有量值的计算来降低复杂度.然而这些算法大多存在相同的时间统计特性,并且服从经典的瑞利信道模两大问题:一是它们采用的序列搜索方法使得流水型.进一步假设在N+1个发送符号时间内衰落系线和并行操作非常困难;二是操作时延的随机性数保持不变(准静态衰落信道),那么对应于发送符M算法(或称为 K-best算法)因为具有相同的号Sk]的NXNk维接收信号矩阵可以表示为历史路径长度,使其不具有上面的缺陷,所以也被应RCk]=SCk]HLk]+W[k]用于多符号差分检测当中6-.简单地说,M算法就其中噪声矩阵Wk]中的元素是零均值复高斯白噪声是在每一检测层保留M条较好的路径,从而具有稳在多符号差分检测系统中,接收机连续接收N定的复杂度的优点但M算法的运用目前还存在着+1个符号来检测N个符号.文献[5]主要介绍了以下问题:一是每层保留的路径数,即M值都是取BID算法在多符号差分检测系统中的应用,其度量固定的值,从复杂度角度上分析这种方法并不是最值计算的公式同样可以应用在本文提出的算法中佳的方法,且其依然较高的复杂度使得该算法还不因此在此不再详细描述根据文献[5],其判决度量能应用于实际中;二是当前对M算法的研究集中在可得通过降低路径扩展数来降低计算复杂度,并没有对+N=每层排序的复杂度进行深入分析针对上面两个问题,本文进行了改进:一是采用argmin‖R[+k-1动态M算法,即每层的M取不同的值,基本原则是高层的M值比低层的M值要大,通过仿真分析得a(Ivm])×R[计+k-1]1.(4)出,这种方法不仅在路径扩展数和更新数上大大减这里令a,=1,表示检测的开始时刻少,而且在高信噪比时其性能比传统的M算法要优越针对第二个问题本文在每层的排序上采用了2动态M算法Batcher合并排序算法,这个算法相比传统的冒泡排序法能大大降低比较交换的次数通过动态M算M算法是一种宽度优先的序列搜索算法.它法和 Batcher合并排序算法的结合,较低的复杂度的基本原理是根据某种准则保留M条路径,然后将使得该算法更有利于实际的运用这M条路径进行延伸,组成新的bM条路径,并计算这些所有路径的判决度量,最后将(b-1)M条最1系统模型差的路径删除,如此一直持续到所有的信息全部判决出来.传统的M算法中每层保留的路径数M是考虑在平坦衰落信道下,一个具有N1个发射固定的文献12]中提出了一种自适应M算法,它天线与NA个接收天线的差分酉空时调制系统发根据信道状态对树的不同层取不同的M值,这种方送符号由一个固定的星座集v={V,l=0,1法的前提是要求接收端已知信道状态信息,这对于1}产生的.特别地,笔者采用对角星座,西矩差分检测来说是无法满足的本文在M算法基础上阵V(VVH=ⅠN,)的映射如下提出一种动态M算法,它的基本思想是在早期的检测层使用较大的M值,在检测低层的时候减少MI=diage值.其原理是:在第i(比较大)层检测的时候,在到l∈{0,1,…,L-1}(1)达最后分支的时候还有i-1层的分支度量值需要式中,(i=1,2,…,N)由文献[10]可以得到,在这计算,若每层保留的分支数M较小,则在早期删除里不再详细介绍,它的选择能够达到最大分集,获得最大似然值的几率会增大,M值的增大可以减少这较好的增益L=2,R代表传输速率.本文中假设种情况发生的可能性;随着i的递减,分支度量值越R=l bit/来越接近最后的结果,最大似然值被删除的几率就首先将毎NR个信息比特映射成星座V[k],越来越小,因此在检测低层的时候减少M值,这样V[A]是星座集中的NXNr维矩阵,对V[k进行可以降低计算复杂度却同时保证了算法的性能由浙江大学学报(理学版)第38卷于针对差分检测系统,如何自适应地改变每层的M值并没有一定的规律本文通过了大量的仿真测试获得M的较佳取值状态.其流程如图1所示初始化L,N+1,每层分支数M,M、1,M,…,M10计算L个星座点的度量值,保留M条路径M=[I6161M=[1281扩展M个节点到子节点,组成新的LM条路径日-M叫16161616☆-…M-[168881叶算新路径的度量值。保留较小的M条141618图3瑞利衰落信道下,N=4,NR=1,分组长度为4和6时图1动态M算法流程图M算法和动态的M算法及C.D相关检测的性能比较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算法、动态M算法和相关检Rayleigh Fading Channel, when Nr=4, NR=1测(CD)算法分别在发送天线数为3和4的性能比the block length is 4 and 6 respectively较图.在仿真过程中,使用的是准静态的平坦瑞利衰落信道,发送天线之间假设是相互独立的,并设归从图2和图3中可以看出,动态M算法在低信化最大多普勒频移foT为0.0075图2中M=[8噪比的时候,能够過近M算法的性能在高信噪比81]代表分组长度N+1为4时,各层分别保留8的时候,动态M算法的性能甚至优于M算法,这是条、8条1条路径,即传统M算法的取值方法;而M由于通过减少度量值较大的分支数,从而促使发生[841]代表分组长度N+1为4时,各层分别保错误的概率减少.如图2中所示,在误码率为10-3时,分组长度N+1为4的情况下,动态M算法的留8条、8条、1条路径,即动态M算法的取值方法、信噪比降低了16.23-15.88=0.35dB,而在误码M=[88881]和M=[86641]代表分组长度为N+1为6时,传统M算法和动态M算法的取值分率为10,分组长度为6的情况下,动态M算法的布情况.图3同上,信噪比降低了18.56-18.20=0.36dB.图3中所示,在误码率为10-时,分组长度N+1为4的情况-e-M=88IM=[841下,动态M算法的信噪比降低了13.12-12.70=0.42dB而在误码率为10-3,分组长度为6的情况☆-…M={86641x--.C D下,动态M算法的信噪比降低了12.20-11.80=0.40dB.由图2和图3对比可知,动态M算法具有较好的空间分集能力3改进的排序方法在M算法中,过多的比较次数也是其计算复杂度高的原因之一.针对如何减少比较次数,本文采用SNR/dB了一种改进的排序方法,称为 Batcher合并排序算图2瑞利衰落信道下,N=3N=1,分组长度为4和6时,法,该排序的前提是每个扩展节点已经经过简单的M算法和动态M算法及C.D相关检测的性能比较升序排列.这种改进的排序方法比起传统的冒泡排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的排序结构,主要由两个有16the block length is 4 and 6 respectively个已经升序排列的阵列和16个最小输出组成.8*第1期金小萍,等:多符号差分酉空时系统的低复杂度M算法设计8、4*4、2*2的比较模块也已在图中表示.显而易又由2个2“2加上两个额外的C&S构成.每个最见,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时,用冒泡法排序能够将比较次数降低70%假设M,表示上一层保的情况下,每一层需要63+62+…+56=476次比留分支数,M,-1表示当前层要保留的分支数,L是星较而用 Batcher合并排序算法,只要7个8“8模座点数.表1中列出了几种检测情况的比较次数.从块的比较就足够了.每个8*8模块由2个4*4加表1中可以得出改进的排序方法的比较次数比起传上4个额外的C8S(比较和交换)组成而一个4*4统的冒泡排序降低了70%~80%数位的奇数传的数合并比较合片比较比较模块合井比较位嫩微图4改进的排序结构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)路径的更新对于每个存活节点都需要更复杂度分析新它们的度量值,用于接下去的路径度量值计算.对于M算法,总共8*4=32条路径需要更新,需要计本节主要对应用了动态M算法和改进的排序算8*1+8*2+8*3+8“4=80个乘法数和加法算法的多符号差分酉空时系统的复杂度进行分析.数;而对于动态M算法,只需8+6+6+4=24条路以3发1收的差分酉空时调制系统,分组长度N+1径需要更新,需要计算8*1+6*2+6*3+4*4=为6为例.54个乘法数和加法数,节省了25%左右的计算M算法中,M取8即M=[88881],动态M(3)排序对于M算法,在每一检测层(除了算法中,M=[86641].从以下3个方面进行分析:第一层),需要从8*8=64条路径中选出8条度量(1)路径的扩展对于M算法来说,在顶层需值比较小的分支,用传统的冒泡法排序,总共需要要计算8个PEDs(部分欧氏距离)(每个PED计算476*3+63=1491(最后一层是从64条路径中保由一个乘法,两个加法和1个MAX操作构成),留1条)次比较而动态M算法与改进的排序算法接下去几层需要对每个存活节点扩展8个子节点,结合之后,顶层不需要排序第二层从64条中选6直至检测到最后一层得出最佳路径因此总共需要条因此需要20*6+19=139次比较,第三层从48计算8+8*8+8*8+8*8+8*8=264个PEDs.条中保留6条,需要20*4+19=99次比较,第四层而对于动态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%的比较次数比较次数.通过将动态M算法与改进的排序方法进假设发送天线为N,星座点数为L,接收机连行结合应用于多符号差分酉空时系统得出它比传续接收N+1个符号检测N个符号.经大量仿真测统的M算法在高信噪比时性能得到提高,并且计算试,动态M算法,每一检测层保留的分支分别为复杂度获得较大幅度的下降该方法的应用可以节M,M、-1,M、-2;…,M1条,而M箅法则MN=省大量资源,利于硬件实现MN-1=…=M2.表2用同上2的方法,用公式显示了两种算法的比较次数情况.这里M算法和动态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时,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可以观察到,改进后的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算法和动态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,分组长度为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加法数乘法数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结论[ll] ANDERSON J B, MOHAN S. Sequential coding al本文提出了一种动态M算法.经仿真测试,这and cost analysis[J]. IEEE Trans种算法在低信噪比的时候性能能够通近传统的MCommun,1984,32(2):169-176.算法,在高信噪比的时候性能优于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复杂度另外,还提出了一种改进的排序方法,与传统的冒泡排序法相比,该方法能够减少75.39%的(责任编辑涂红)