多维映射BICM-ID系统的简化MD-LSD解映射算法

多维映射BICM-ID系统的简化MD-LSD解映射算法 第29卷第2期 通 信 学 报 Vol.29 No.2 2008年2月 Journal on Communications February 2008 多维映射BICM-ID系统的简化MD-LSD解映射算法 宫丰奎, 葛建华, 王勇 (西安电子科技大学 ISN国家重点实验室, 陕西 西安 710071) 摘 要:将二维映射下的软输入软输出解映射MAX-LOG-MAP算法扩展到多维映射比特交织编码调制及迭代译 码(BICM-ID)系统，并首次结合多天线系统下的列表球形译码，提出一种简化MD-LSD(multi-dimensional list sphere decoding)算法。新算法大幅降低了多维解映射的计算复杂度。仿真结果表明，列表长度满足一定范围时，采用 简化MD-LSD算法解映射算法的性能损失可以忽略。 关键词:BICM-ID; 多维映射;软输入软输出解映射;多维列表球形译码 中图分类号:TN911 文献标识码:A 文章编号:1000-436X(2008)02-0111-05 Simplified MD-LSD demapping algorithm for BICM-ID systems with multi-dimensional mappings GONG Feng-kui, GE Jian-hua, WANG Yong (State Key Lab. of Integrated Service Networks, Xidian Univ., Xi’an 710071, China) Abstract: The soft in soft out MAX-LOG-MAP algorithm of conventional mappings was expanded to the BICM-ID sys- tem with multi-dimensional mappings. A multi-dimensional list sphere decoding (MD-LSD) algorithm was also proposed by using the list sphere decoding algorithm of multi-antenna systems. Compared with the MD-MAX-LOG-MAP algo- rithm, the computational complexity of MD-LSD was decreased significantly. Simulation results show that the perfor- mance degradation of the simplified MD-LSD algorithm can be ignored when the list length is in a certain range. Key words: bit-interleaved coded modulation with iterative decoding; multi-dimensional mapping; soft in soft out de- mapper; multi-dimensional list sphere decoding 空间，为了进一步提高渐进性能，最近提出了一种1 引言 [3~6]，即将一组比特映射到一个符多维映射的思想 比特交织编码调制及其迭代译码系统号矢量，而不是原来的单独一个符号，通过增加欧 [1][5](BICM-ID)由于适合瑞利衰落信道以及高斯信道，氏距离提高性能。其中Tran等研究多维超立方体 并具有高谱效率、低复杂度等方面的优势，已经成映射，给出了一种针对QPSK的最优多维映射的设 [6]为新一代无线传输链路技术的一个热点课题。对于计方法，并搜索得到8PSK最优四维映射，性能 BICM-ID系统，星座信号的不同标识映射方法对其有很大改进，代价是更高的接收复杂度。 [2]性能影响较大。但这些映射仅考虑了一般的二维然而，对多维映射BICM-ID的研究目前主要集 收稿日期:2007-01-30;修回日期:2007-10-15 基金项目:国家高技术研究发展计划(“863”计划)基金资助项目(2006AA01Z270);国家自然科学基金资助项目(60496316); 陕西省自然科学基金资助项目(2007F07) Foundation Items: The National High Technology Research and Development Program of China (863 Program)(2006AA01Z270); The National Natural Science Foundation of China (60496316); The Natural Science Foundation of Shanxi Province (2007F07) ?112? 通 信 学 报 第29卷 中在映射构造上，还没有针对接收端软输入软输2 多维映射BICM-ID系统模型 出解映射的实现算法提出。在文献[7]中提出一种多维映射BICM-ID系统框图如图1所示，信息多维树搜索解映射算法，但实现时不能根据信道序列u经编码为编码序列c，再经比特交织器表示状态自适应变化的。本文考虑到多维解映射和多为c′，和传统的二维映射不同，这里将每组K=mN天线系统软检测算法的相似，将多天线系统下的编码比特映射为N个连续的M进制星座符号。由于列表球形译码算法进行了推广，提出一种M进制星座由I/Q部分构成，因此，将生成一2N维MD-LSD算法，通过在一个以半径为参数的球面mN的超几何体星座，且N个M进制星座符号就存在2内搜索，用可能性较大的发送序列集合代替整个，，x,xx,,种不同的组合方式，表示为，其中iiiN,1,，，符号矢量集合，极大地降低了多维解映射复杂度， ，，xss,,，表示第l个通常的M进lN,[1]ililil,,21,2,，，且搜索可以通过递推完成。通过计算机仿真，验 制符号，复数表示为。 xsjs,，证了算法的性能，在列表长度满足一定范围时，ililil,,21,2,简化后的MD-LSD算法较MD-MAX- LOG-MAP和通常的二维映射相同，当2N维超几何体用算法造成的性能损失可以忽略。 作BICM-ID系统中的信号星座时，每一个顶点即 图1 多维映射BICM-ID系统 图2 QPSK调制时的四维超立方体最佳映射 第2期 宫丰奎等:多维映射BICM-ID系统的简化MD-LSD解映射算法 ?113? 2,，代表一个发送信号，用K个二进制比特加以标识:QQT (3) yhxL,，aa，，，，,lllkk[]A[],,，，sa,,,,aa,,。s或x定义了发送信号在，,iiiiiiK,1,，， 欧氏空间的位置，如何选择相应的标识a是一个主其中，a表示删除a中第k个元素a后的子矢量，i[k]k[3~6]要考虑问题。 上标I、Q分别表示实、虚部，h表示第l个发送l 图2给出了QPSK调制时四维超立方体映射M进制符号的幅度衰落。式(3)即为多维映射下的[6]的示意图，等效的矢量映射关系为μ=[0 9 10 3 12 MD-MAX-LOG-MAP解映射公式，可见，其复杂5 6 15 7 14 13 4 11 2 1 8]。其中，图2中方括号表度和K成指数关系，当N较大或者为高阶调制时，示发送信号的坐标形式s，圆括号表示对应的映射算法复杂度很高，因此需要考虑其简化算法。 i 比特a。 3.2 多维映射下的简化MD-LSD解映射算法 i 迭代解调和译码过程同一般的二维映射，仅解球形列表检测算法是针对多天线系统提出的 [9]映射算法有所不同，本文不再累述，具体参考文献一种软输入软输出算法，一方面可以大幅降低复[2]等。 杂度，另一方面，性能又接近最大后验概率检测算 法。本文首次将其推广到单天线多维解映射中以降3 针对多维映射的SISO解映射算法 低复杂度，简称为MD-LSD(multi-dimensional list 3.1 多维映射下的MAX-LOG-MAP解映射公式 sphere decoding)算法。 假定接收复映射符号矢量y=[y,„, y]，对估计式(4)的一种简化方法就是考虑到使得式1N N22任意发送符号矢量，由于比特交织器的作用，序IIQQ，，较大的值可以不加考yhxyhx,，,，，，，,llllll,,，，列c中的比特认为近似统计独立，于是，利用贝,l1 叶斯准则，第k(k=0, „, K?1)比特的对数似然信虑，因此，类似LSD算法中的半径参数，设置参数r，[8]N22息为 IIQQ，，即仅需要考虑满足式yhxyhx ,，,，，，，,llllll,,，，,l1KPLayx|exp2，，，，,,Aj?r的点。因为上述和式各项都是正数，根据注水a,,,11xkj，，,,;1jkaj (1) 原理，上述符合条件发送信号点的搜索可以采用递,，LaLayln，，，，AkkKPLayx|exp，，，，,,Aj推的方法。初始化列表长度为零，N为定义的Lcanda,,，，,01xkj,,;1jkaj列表长度，算法描述如下: 1) 令l=1，得 其中，a表示a中第k个元素，xkbaab,|,,，，,,kk22IIQQ2K?1yhxyhxr,，,? (4) ，，，，111111表示满足a=b的2个比特矢量a构成的集合，k 将式(4)实部和虚部分开考虑，即 x为二进制标识序列a对应的发送符号矢量。由 ILaLay,,于软解映射器的外部信息为 ，，y，，rrEkkIIII1ˆˆˆx, ，其中 (5) xx?，x,?1111hhhLa，且对复高斯信道，条件概率密度函数为 1，，11AkIx2) 根据式(5)枚举满足条件的，计算相应的122IIQQ2，，IIIyxyx,，,，，，，1iiii,,,yhx距离矢量，作为式(6)输入，其，，,,1,id111,idxx (2) expPyx,,，，ii22,,,,22II,xx中表示矢量的的第idx个元素。 1,idx1，， 2I2Ir,,r,,xx1,id1,idQQQ考虑到对多维映射，式(2)为N个连续M进制ˆˆ (6) xx,??x，111hh11符号的概率乘积，结合式(1)、式(2)并利用 由于式(6)的计算按顺序执行，以下为了简化，MAX-LOG近似简化，考虑信道衰落的影响后得 省略了下标idx。 N22Q1,IIQQ，，x3) 根据式(6)枚举满足条件的，同理，令l=k， Layhxyhx,,,，,，max，，1，，，，,,Ekllllll2,,a,(,1)xk，，,2,1l,定义 kN222IQ1,,TII，，，rr,,，,, (7) aaLyhx,,,,，maxiik，，，，，，，，,,,[]A[]kklll2,a,,(,0)k，,i1,2,,1l, ?114? 通 信 学 报 第29卷 则 加法、浮点乘法等)进行比较。相对于文献[7]的 多维树搜索解映射算法，MD-LSD算法的复杂度rrk,1k,1，，，，IIIˆˆxx,??x， kkk和信道优化有关，这就决定了前者比较适合对实hhkk时性要求较高的系统，而后者比较适合信道条件 (8) 2I2I好的系统。 r,,r,,kkk,1k,1，，，，QQQˆˆxx,??x， kkkhhkk4 计算机仿真 4) 直到l=N结束，意味着已经找到一个新列表为了说明简化MD-LSD算法性能和给定列表长N2IQ点。计算该新点的距离:。如果d,，,,，，,newii度的关系，可以利用随机的六维超立方体映射加以,i1仿真说明，μ=[23 21 39 62 11 4 32 13 17 51 57 30 40 满足，L=L+1，将该点添加到列表集以LN,,cand16 25 45 22 43 33 9 36 48 56 28 8 29 44 63 3 19 31 15 22及相应的距离集合，即;否则，如果列dd,ΩLnew53 24 54 34 2 46 52 0 60 38 10 7 12 26 20 5 59 49 55 表已经为满，则比较该矢量的距离和列表中的最大50 14 1 18 35 42 61 27 41 6 58 47 37]，其他仿真参数距离，用新点替换原列表中的最大距离点，即为QPSK调制，纠错码采用生成多项式为[7 5]的卷22dd,。 maxnew积码，交织器为长度等于12 288的随机交织器，注意到上述搜索过程可能出现其中的某一个球面半径选择足够大，如本例1.6左右即可。列表环节找不到符合条件的信号点，如x，认为解映射t长度N选择为4,16,32,64，当N=64时，算法candcand在x~x选择了至少一个差点，此时修改x的候1t?1t?1等价于MD-MAX-LOG-MAP算法。由图3可见，选点重新尝试，如果仍然没有其他符合条件的候N取值32、16时，算法和MD-MAX-LOG-MAPcand选点，则再修改x的候选点尝试，依次类推即t?2算法性能接近，且错误平层几乎相同，相较计算复可。 杂度却分别约下降为原来的1/2、1/4，说明这样，定义最终选择的候选发送符号矢量集合MD-LSD算法明显优于MD-MAX-LOG-MAP算为，于是在MD-LSD算法下，式(3)可以简化为 ,法;但当N取值很小的时候，如N=4时，中candcand 1低信噪比时，错误平层明显上升，性能较,,2TLadLaa,,，,max，，，，,,kkkaE[]A[]2,,axk(,1),2MD-MAX-LOG-MAP算法明显下降。图4针对高,, 1阶16QAM调制四维映射的简化进行仿真，采用瑞,,2TdLaa (9) ,，max，，,,akk[]A[]2,,axk(,0),2,,利准静态衰落信道，纠错码仍采用[7 5]卷积码。可 见，列表长度选择为64时，算法和原2d其中，表示对应矢量a的距离。 aMD-MAX-LOG-MAP(N = 256)算法的各次迭代cand3.3 复杂度分析 性能非常接近。 如果MD-LSD算法在搜索过程完成后列表仍 然不满，说明半径选择过小，应增加半径r。半径 如果选择越大，则搜索时间越长，因此，和多天线 系统下的LSD算法一样，其半径参数的选择是一个 必须考虑的问题。 通常的MD-MAP算法的复杂度和星座大小、 维数成指数关系，MD-LSD算法为多项式复杂度。 如果将本文的星座维数对应多天线系统中的发射 天线数，则两种算法复杂度关系等价于多天线系统 中MAP算法和LSD算法的关系，具体参见文献[9]。 考虑到提出的算法属于非线性检测算法，难以给 出理论计算复杂度，通过统计给定信噪比下固定图3 AWGN信道下六维解映射MAP算法和 MD-LSD算法的比较(QPSK调制) 块长数据的检测所需要的浮点运算数(包括浮点 第2期 宫丰奎等:多维映射BICM-ID系统的简化MD-LSD解映射算法 ?115? [4] SIMOENS F, WYMEERSCH H, BRUNEEL H, et al. Multi-dimensional mapping for bit-interleaved coded modulation with BPSK/QPSK sig- naling [J]. IEEE Communications Letters, 2005, 9(5): 453-455. [5] TRAN N H, NGUYEN H H. Multi-dimensional mappings of M-ary constellations for BICM-ID systems [J]. IEICE Trans Fundamentals, 2006, E89-A(7): 2088-2091. [6] TRAN N H, NGUYEN H H. Design and performance of BICM-ID systems with hypercube constellations[J]. IEEE Trans Wireless Com- mun, 2006, 5(5): 1169-1179. [7] 宫丰奎, 葛建华, 王勇. 多维映射BICM-ID系统的SISO解映射算 法[J]. 西安电子科技大学学报, 2007, 34(6): 895-899. GONG F K, GE J H, WANG Y. Soft in soft out demapper for 图4 16-QAM调制时，准静态瑞利衰落信道下简化四维解映射算法性能 BICM-ID system with multidimensional mappings[J]. Journal of Xi- dian University, 2007, 34(6): 895-899. 5 结束语 [8] BRINK S T, SPEIDEL J, YAN R H. Iterative demapping and decoding for multilevel modulation[A]. Proceedings of GLOBECOM [C]. Syd-本文重点研究了多维映射BICM-ID系统下的ney:IEEE, 1998. 579-584. 软输入软输出解映射算法，利用列表球形译码算法[9] HOCHWALD B M, BRINK S T. Achieving near-capacity on a mul-选择可能发送符号矢量空间，从而得到一种更为简tiple-antenna channel[J]. IEEE Trans on Comm, 2003, 51(3): 389-399. 化的MD-LSD算法，算法复杂度根据信道质量自适 应变化。论文通过计算机仿真说明了简化MD-LSD作者简介: 算法性能和其列表长度的关系。 宫丰奎(1979-)，男，山东潍坊人， 博士，西安电子科技大学讲师，主要研究方参考文献: 向为新一代无线通信关键技术。 [1] LI X D, RITCEY J A. Bit-interleaved coded modulation with iterative decoding and 8PSK Signaling [J]. IEEE Transactions on Communica- tions, 2002, 50(8): 1250-1257. [2] 宫丰奎，葛建华，李兵兵. BISTCM-ID系统的标识映射设计及性能 分析[J]. 计算机学报, 2006, 29(4): 561-569. 葛建华(1961-)，男，江苏南通人，西安电子科技大学GONG F K, GE J H, LI B B. Desing and analysis of labeling map 教授、博士生导师，主要研究方向为无线通信、高清晰度数methods for BISTCM-ID system[J]. Journal of Computers, 2006, 字电视技术。 29(4): 561-569. [3] GRESSET N, BOUTROS J J, BRUNEL L. Multidimensional map- 王勇(1976-)，男， 陕西西安人，博士，西安电子科pings for iteratively decoded BICM on multiple-antenna channels [J]. 技大学讲师，主要研究方向为新一代无线通信关键技术。 IEEE Trans on Information Theory, 2005, 51(9):3337-3346.