球解码及其一种改进算法

凌春红，刘 陈

(南京邮电大学，江苏 南京 210003)

多输入多输出MIMO(Multiple-InputMultiple-Output)，在发射端，各子信号同时发送到信道且占用同一频带，实现多个数据子流同时间同频带地传输。与传统单输入单输出 (SISO)系统相比，MIMO系统能提供更大的信道容量。然而，接收端接收到的信号在时间和频带上都是相互重叠的，导致了MIMO信号检测的高复杂度问题。为得到较低误码率的解码效果，接收端往往采用最大似然准则(ML)检测，但该检测方案的计算量很大。目前，球解码算法(SD)凭借其近似ML的检测性能和较低的复杂度而引起广泛的关注[1-6]。然而，当信噪比较低、收发天线数较多、调制星座图较大时，球解码的平均复杂度仍然很高，因此，近来球解码的研究重心是如何进一步降低检测复杂度上。

本文介绍了一种球解码的改进算法。

1 无线MIMO系统模型

考虑一个发射天线数为M、接收天线数为N的MIMO系统，该系统可描述如下：

式中，yc是接收矢量；Hc=[hij]N×M是复值信道矩阵，hij代表从第j根发射天线到第i根接收天线的信道增益，且满足均值为0、方差为1的独立同分布复高斯分布；xc是发射符号矢量；nc是均值为 0、方差为σ2nc的复白高斯噪声。若仅考虑N＞M时实数范围内的解码，则式(1)可等效如下：

2 球解码算法

发送向量的空间经信道矩阵H作用后生成格形空间：Λ(H)={Hx：x∈Ω}，发送符号 x可看作是格型点坐标，若将接收点y看作是受高斯噪声n干扰的格型点，则MIMO系统的ML检测可等效为在格型空间Λ(H)中寻找一个离y最近的格点由此可得MIMO系统的ML检测解：

球检测法只在1个给定半径的球内检验其中的每1个格点，而不是对整个格型空间进行搜索。假使给定初始球搜索半径C0，则在以接收点y为球心、C0为半径的球S(y，C0)内进行搜索，若球内不存在Λ(H)中的格点，则放大球半径，在放大的球内继续搜索；反之，若找到了1个属于Λ(H)的格点Hx1，则将球半径缩小为 C=‖y-Hx1‖，继续在缩小后的球内进行下一轮迭代搜索。如此下去，直到找到使C=‖y-Hx‖最小的格点为止，则该点即为所求的ML解，这就是球解码算法的基本思想。现将SE(Schnor-Euchner)准则下的球解码算法详细说明如下：

根据球解码的基本思想，Hx∈S(y，C0)的条件可描述为：

对矩阵H进行QR分解，可得：

其中，Q1、Q2分别为 N×M 和 N×(N-M)的酉矩阵，R为 M×M的上三角矩阵，0为(N-M)×M的零矩阵。将式(5)代入式(4)中，整理可得：

借助R的上三角特性，可将上式展开如下

假设只考虑不等式左边的第j=M这一项，可得

SE准则从距离上、下界的中间值最近的元素开始，对候选符号集里的元素进行升序排序。检测时，每选定第i维候选符号集内的1个元素，就能确定第i-1维分量的候选符号集，若得到的候选符号集为空，则返回上一维，选取候选符号集内的下一个元素；若不为空，则继续寻找下一维的候选符号集，直到第1维分量的候选符号集被确定，得到同时缩小球半径，继续在缩小后的球内搜索新的解码向量，直到球内所有的向量被检测完毕。

3 一种球解码改进算法

球检测算法虽然能得到近似ML的检测效果，但其计算量仍然较大。因此，希望在保证检测性能的基础上进一步降低复杂度。目前，人们以球检测法为基础，提出了一些解码性能接近ML但计算量大大减小的改进算法。

由上节描述可知，球解码通过放松不等式的约束来确定各维的估计区间，从而实现递归检测，这势必会造成估计区间[Li，Ui]的放大和Ji中元素的增多。为了改善这种由约束放松产生的不利影响，本文给出了一种新的区间估算方法。

对于K=2k且k为偶数的矩形信号星座，若QAM信号星座等效为在2个正交载波上的PAM信号，K元QAM调制就转化为元PAM调制。而元PAM的符号错误概率即可表示为[7]：

将式(5)代入式(2)，可得

由于Q1的列相互正交，所以n′和n的方差皆为σ2=/2。将式(15)按第i维展开，得：

可见，fi-xi服从均值为 0、方差为σ2的高斯分布。

现将PAM的符号错误概率应用到第i维，为保证对xi进行检测的正确概率大于 1-P(i)，以fi为中心的检测半径 c′i应满足

整理可得：

利用Q(.)函数的递减特性，有

从而可得分量 xi的检测区间为[L′i，U′i]。 其中，L′i=fi-c′i，U′i=fi+c′i。

将[L′i，U′i]用于 SE 准则下球解码算法的每一维解码分量，即可构建一种新的球检测算法。首先为保证有解，由SE准则得到第1个检测结果，然后从第2轮检测开始，xi的候选符号集 Ji选取为[Li，Ui]与[L′i，U′i]在Ω中的交集[LLi，UUi]，这样就能对每一维分量的检测区间进行有效控制。现以第i维分量为例，说明如何确定区间[LLi，UUi]。 设 yi为接收信号分量，ci为按 SE准则更新后的搜索半径，c′i为由上述区间估计确定的搜索半径，ω为调制星座图中的任意符号 。 若ci＜c′i， 则 up=yi+ci，down=yi-ci；否则，up=yi+c′i，down=yi-c′i。若 up＜min(ω)，则 LL(i)=UU(i)=min(ω)； 若 down ＜min(ω)、min(ω)≤up≤max(ω)，则 LL(i)=min(ω)、UU(i)=up；若 down＞min(ω)、up＜max(ω)，则 LL(i)=down、UU(i)=up；若 min(ω)≤down≤max(ω)、up＞max(ω)，则 LL(i)=down、UU(i)=max(ω)；若 down＞max(ω)，则 LL(i)=UU(i)=max(ω)。

图1 16QAM中SD和MSD在不同信噪比下的性能曲线

图2 16QAM中SD和MSD在不同信噪比下的复杂度曲线

图3 64QAM中SD和MSD在不同信噪比下的性能曲线

图4 64QAM中SD和MSD在不同信噪比下的复杂度曲线

4 仿真结果及分析

在仿真试验中，采用8×12未编码系统，调制星座分别采用了16QAM和64QAM，平均符号能量分别为10和42，每个仿真结果均为运行5 000次结果的平均。仿真结果分别如图 1，2，3，4 所示。

实验表明，MSD与SD相比，在高信噪比处，性能略有下降，但复杂度有很明显的改善，星座图越大，计算量下降越明显；在低信噪比处，计算量下降达一个数量级，证明了该改进方法的有效性。

本文提出一种新的区间估算方法，并将其与SE准则下的球检测法相结合，实现对球解码的改进。仿真结果表明，该改进算法相对于SE准则下的球检测法误码性能下降很少，计算量却显著下降。

[1]AGRELL E， ERIKSSON T， VARDY A， et al.Closest point search in lattices[J].IEEE Transaction on information Theory， 2002(48)：2201-2214.

[2]DAMEN M O，CHKEIF A，BELFORE J C.Lattice codes decoder for space-time codes[J].IEEE Communication Letters， 2000(4)：161-163.

[3]VITERBO E，BOUTROS J.A universal lattice code decoder for fading channel[J].IEEE Trans.Inform.Theroy，1999(45)：1639-1642.

[4]HOCHWALD B，BRINK S T.Achieving near-capacity on a multiple antenna channel[J].IEEE Transaction on Communications，2003(51)：389-399.

[5]DAMEN M O， GAMAL H E， CAIRE G.On maximumlikelihood detection and the search for the closest lattice point[J].IEEE Transaction on Information Theory，2003(49)：2389-2402.

[6]ALBERT M C，INKYU L.A new reduced-complexity sphere decoder for multiple antenna systems[C].IEEE Inter.Conf.Commun.， 2002(1)：460-464.

[7]普罗金斯.数字通信(第四版)[M].张力军，张宗橙，等译.北京：电子工业出版社，2003.