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

第2期宫丰奎等：多维映射BICM-ID系统的简化MD-LSD解映射算法115多维映射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-05Simplified MD-LSD demapping algorithm for BICM-IDsystems with multi-dimensional mappingsGONG Feng-kui, GE Jian-hua, WANG Yong（State Key Lab. of Integrated Service Networks, Xidian Univ., Xian 710071, China）Abstract: The soft in soft out MAX-LOG-MAP algorithm of conventional mappings was expanded to the BICM-ID system 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 algorithm, the computational complexity of MD-LSD was decreased significantly. Simulation results show that the performance 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 demapper; multi-dimensional list sphere decoding1 引言收稿日期：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)比特交织编码调制及其迭代译码系统(BICM-ID)1由于适合瑞利衰落信道以及高斯信道，并具有高谱效率、低复杂度等方面的优势，已经成为新一代无线传输链路技术的一个热点课题。对于BICM-ID系统，星座信号的不同标识映射方法对其性能影响较大2。但这些映射仅考虑了一般的二维空间，为了进一步提高渐进性能，最近提出了一种多维映射的思想36，即将一组比特映射到一个符号矢量，而不是原来的单独一个符号，通过增加欧氏距离提高性能。其中Tran等5研究多维超立方体映射，给出了一种针对QPSK的最优多维映射的设计方法，并搜索得到8PSK最优四维映射6，性能有很大改进，代价是更高的接收复杂度。然而，对多维映射BICM-ID的研究目前主要集中在映射构造上，还没有针对接收端软输入软输出解映射的实现算法提出。在文献7中提出一种多维树搜索解映射算法，但实现时不能根据信道状态自适应变化的。本文考虑到多维解映射和多天线系统软检测算法的相似，将多天线系统下的列表球形译码算法进行了推广，提出一种MD-LSD算法，通过在一个以半径为参数的球面内搜索，用可能性较大的发送序列集合代替整个符号矢量集合，极大地降低了多维解映射复杂度，且搜索可以通过递推完成。通过计算机仿真，验证了算法的性能，在列表长度满足一定范围时，简化后的MD-LSD算法较MD-MAX- LOG-MAP算法造成的性能损失可以忽略。2 多维映射BICM-ID系统模型多维映射BICM-ID系统框图如图1所示，信息序列u经编码为编码序列c，再经比特交织器表示为c，和传统的二维映射不同，这里将每组K=mN编码比特映射为N个连续的M进制星座符号。由于M进制星座由I/Q部分构成，因此，将生成一2N维的超几何体星座，且N个M进制星座符号就存在2mN种不同的组合方式，表示为，其中，表示第l个通常的M进制符号，复数表示为。图1 多维映射BICM-ID系统图2 QPSK调制时的四维超立方体最佳映射和通常的二维映射相同，当2N维超几何体用作BICM-ID系统中的信号星座时，每一个顶点即代表一个发送信号，用K个二进制比特加以标识：。si或xi定义了发送信号在欧氏空间的位置，如何选择相应的标识ai是一个主要考虑问题36。图2给出了QPSK调制时四维超立方体映射的示意图6，等效的矢量映射关系为=0 9 10 3 12 5 6 15 7 14 13 4 11 2 1 8。其中，图2中方括号表示发送信号的坐标形式si，圆括号表示对应的映射比特ai。迭代解调和译码过程同一般的二维映射，仅解映射算法有所不同，本文不再累述，具体参考文献2等。3 针对多维映射的SISO解映射算法3.1 多维映射下的MAX-LOG-MAP解映射公式假定接收复映射符号矢量y=y1, yN，对任意发送符号矢量，由于比特交织器的作用，序列c中的比特认为近似统计独立，于是，利用贝叶斯准则，第k(k=0, , K1)比特的对数似然信息为8 (1)其中，ak表示a中第k个元素，表示满足ak=b的2K1个比特矢量a构成的集合，x为二进制标识序列a对应的发送符号矢量。由于软解映射器的外部信息为 ，且对复高斯信道，条件概率密度函数为(2)考虑到对多维映射，式(2)为N个连续M进制符号的概率乘积，结合式(1)、式(2)并利用MAX-LOG近似简化，考虑信道衰落的影响后得(3)其中，ak表示删除a中第k个元素ak后的子矢量，上标I、Q分别表示实、虚部，hl表示第l个发送M进制符号的幅度衰落。式(3)即为多维映射下的MD-MAX-LOG-MAP解映射公式，可见，其复杂度和K成指数关系，当N较大或者为高阶调制时，算法复杂度很高，因此需要考虑其简化算法。3.2 多维映射下的简化MD-LSD解映射算法球形列表检测算法是针对多天线系统提出的一种软输入软输出算法9，一方面可以大幅降低复杂度，另一方面，性能又接近最大后验概率检测算法。本文首次将其推广到单天线多维解映射中以降低复杂度，简称为MD-LSD（multi-dimensional list sphere decoding）算法。 估计式(4)的一种简化方法就是考虑到使得式较大的值可以不加考虑，因此，类似LSD算法中的半径参数，设置参数r，即仅需要考虑满足式 的点。因为上述和式各项都是正数，根据注水原理，上述符合条件发送信号点的搜索可以采用递推的方法。初始化列表长度为零，Ncand为定义的列表长度，算法描述如下：1) 令l=1，得(4)将式(4)实部和虚部分开考虑，即，其中(5)2) 根据式(5)枚举满足条件的，计算相应的距离矢量，作为式(6)输入，其中表示矢量的的第idx个元素。(6)由于式(6)的计算按顺序执行，以下为了简化，省略了下标idx。3) 根据式(6)枚举满足条件的，同理，令l=k，定义(7)则(8)4) 直到l=N结束，意味着已经找到一个新列表点。计算该新点的距离：。如果满足，L=L+1，将该点添加到列表集以及相应的距离集合，即；否则，如果列表已经为满，则比较该矢量的距离和列表中的最大距离，用新点替换原列表中的最大距离点，即。注意到上述搜索过程可能出现其中的某一个环节找不到符合条件的信号点，如xt，认为解映射在x1xt1选择了至少一个差点，此时修改xt1的候选点重新尝试，如果仍然没有其他符合条件的候选点，则再修改xt2的候选点尝试，依次类推即可。这样，定义最终选择的候选发送符号矢量集合为，于是在MD-LSD算法下，式(3)可以简化为(9)其中，表示对应矢量a的距离。3.3 复杂度分析如果MD-LSD算法在搜索过程完成后列表仍然不满，说明半径选择过小，应增加半径r。半径如果选择越大，则搜索时间越长，因此，和多天线系统下的LSD算法一样，其半径参数的选择是一个必须考虑的问题。通常的MD-MAP算法的复杂度和星座大小、维数成指数关系，MD-LSD算法为多项式复杂度。如果将本文的星座维数对应多天线系统中的发射天线数，则两种算法复杂度关系等价于多天线系统中MAP算法和LSD算法的关系，具体参见文献9。考虑到提出的算法属于非线性检测算法，难以给出理论计算复杂度，通过统计给定信噪比下固定块长数据的检测所需要的浮点运算数（包括浮点加法、浮点乘法等）进行比较。相对于文献7的多维树搜索解映射算法，MD-LSD算法的复杂度和信道优化有关，这就决定了前者比较适合对实时性要求较高的系统，而后者比较适合信道条件好的系统。4 计算机仿真为了说明简化MD-LSD算法性能和给定列表长度的关系，可以利用随机的六维超立方体映射加以仿真说明，=23 21 39 62 11 4 32 13 17 51 57 30 40 16 25 45 22 43 33 9 36 48 56 28 8 29 44 63 3 19 31 15 53 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的卷积码，交织器为长度等于12 288的随机交织器，球面半径选择足够大，如本例1.6左右即可。列表长度Ncand选择为4,16,32,64，当Ncand=64时，算法等价于MD-MAX-LOG-MAP算法。由图3可见，Ncand取值32、16时，算法和MD-MAX-LOG-MAP算法性能接近，且错误平层几乎相同，相较计算复杂度却分别约下降为原来的1/2、1/4，说明MD-LSD算法明显优于MD-MAX-LOG-MAP算法；但当Ncand取值很小的时候，如Ncand=4时，中低信噪比时，错误平层明显上升，性能较MD-MAX-LOG-MAP算法明显下降。图4针对高阶16QAM调制四维映射的简化进行仿真，采用瑞利准静态衰落信道，纠错码仍采用7 5卷积码。可见，列表长度选择为64时，算法和原MD-MAX-LOG-MAP(Ncand = 256)算法的各次迭代性能非常接近。图3 AWGN信道下六维解映射MAP算法和MD-LSD算法的比较（QPSK调制）图4 16-QAM调制时，准静态瑞利衰落信道下简化四维解映射算法性能5 结束语本文重点研究了多维映射BICM-ID系统下的软输入软输出解映射算法，利用列表球形译码算法选择可能发送符号矢量空间，从而得到一种更为简化的MD-LSD算法，算法复杂度根据信道质量自适应变化。论文通过计算机仿真说明了简化MD-LSD算法性能和其列表长度的关系。参考文献：1LI X D, RITCEY J A. Bit-interleaved coded modulation with iterative decoding and 8PSK Signaling J. IEEE Transactions on Communications, 2002, 50(8): 1250-1257.2宫丰奎，葛建华，李兵兵. BISTCM-ID系统的标识映射设计及性能分析J. 计算机学报, 2006, 29(4): 561-569.GONG F K, GE J H, LI B B. Desing and analysis of labeling map methods for BISTCM-ID systemJ. Journal of Computers, 2006, 29(4): 561-569.3GRESSET N, BOUTROS J J, BRUNEL L. Multidimensional mappings for iteratively decoded BICM on multiple-antenna channels J. IEEE Trans on Information Theory, 2005, 51(9):3337-3346.4SIMOENS F, WYMEERSCH H, BRUNEEL H, et al. Multi-dimensional mapping for bit-interleaved coded modulation with BPSK/QPSK signaling J. IEEE Communications Letters, 2005, 9(5): 453-455.5TRAN 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.6TRAN N H, NGUYEN H H. Design and performance of BICM-ID systems with hypercube constellationsJ. IEEE Trans Wireless Commun,