改进的K－Best检测算法研究及实现

吴 军，王绍伟

(江西理工大学信息工程学院，江西 赣州 341000)

多输入多输出(MIMO)系统是一个具有挑战意义的研究热点［1］，它可以有效地解决未来通信中信道容量紧缺的问题。MIMO通信系统有很高的频谱利用率，在一定的频段上可以获得很高的传输速率，而且理论上与MIMO的天线数成正比，在相同发射功率和传输带宽下，多天线系统比单天线系统的信道容量高40多倍［2］。在MIMO系统中接收端的信号检测部分是整个MIMO系统最重要的一部分，因为信号检测部分如果可以准确地检测，那么系统的性能便可以大大提升，系统可靠度及频谱效率也都可以获得改善。

在MIMO检测中，球形检测算法是一种比特误码率性能接近最佳ML检测，又能大幅降低复杂度的有效方法。目前，对MIMO系统的球形检测算法研究，主要有两种类型，一类是深度优先算法，该算法可以达到与ML相同的性能，缺点是搜索过程中迭代次数较多，吞吐率不高且复杂度不固定，如SESD(Schnorr－Euchner SD)算法、列表球算法(LSD)。另一类是广度优先算法，算法性能相对于ML有一定损失，但采用了备受欢迎的前馈结构，具有硬件友好的特征，在检测信号的每一层，只保留最小的K个度量值对应的路径来确定扩展情况，如K－Best算法［3］。本文在深入研究球形检测算法的基础上，针对K－Best算法采用预测技术和并行排序结合的方法，在不损失性能的情况下，降低了算法的计算复杂度。提出了改进的KBest检测算法的流水线结构实现方案，给出了QR分解的实现结构。

1 系统模型

在一个发射天线与接收天线均为N的MIMO系统，信道为准静态平坦衰落，MIMO系统数学模型可以表示为

式中:y为N维的接收数据列向量;s为发送数据列向量;H为等效基带信道传输矩阵，是N×N维的复矩阵;n为N维的理想加性复高斯白噪声矢量，发送信号空间为Ω，星座点数为NΩ。将系统复数形态转换为实数形态y′=H′s′+n′，并实数分解为

经过实数分解后，复数向量和矩阵转化为实数向量和矩阵，并且维数将是对应复数向量和矩阵的2倍。其中，向量和矩阵的维数虽然增加了，但减少了处理单元的实现复杂度，从而降低了总的计算量，减少了检测方案的硬件资源消耗。

2 算法分析

2.1 传统 K－Best算法

基于上述系统模型对信道矩阵H′进行QR分解，则H′=QR，其中Q为2 N×2 N维正交矩阵，R为2 N×2 N维上三角阵，=QTy为2 N维向量。由式(1)，可得

则最大似然(ML)检测公式为

传统K－Best算法是由信道矩阵H′经过QR分解后，根据最大似然检测算法，将式(4)展开得到

2.2 改进的K－Best算法

传统K－Best检测算法相比于其他球形检测算法的优点是其只有正向搜索的过程，缩小了搜索空间，并且具有固定的复杂度和吞吐率，适于硬件实现。同时，由于传统的K－Best算法的复杂度主要集中在路径成本计算和每一层的排序操作，为了进一步降低检测算法的计算复杂度，本文在深入研究K－Best算法的基础上，提出了预测技术和并行排序结合的改进算法，以降低检测算法的复杂度，使之适合硬件实现。

2.2.1 预测技术

预测技术其核心算法思想是改进了SE策略［4］的实现方法，即在确定每层节点的扩展子节点时，无须计算出此节点所有扩展子节点的欧氏距离，只需要通过式(6)计算此层使PED为零的浮点数^si，然后确定和此^si距离最近的星座点来得到每层节点的扩展子节点。

式中:NR为接收天线数目。于是将本来需要Mc个点的PED计算减少成1次PED计算与几次比较选择，因此较好地降低了检测算法的计算复杂度［5］，从而节省了硬件实现的资源消耗。

2.2.2 改进的K－Best检测算法流程

改进的K－Best算法的关键在于预测技术和并行排序的结合，首先在确定每层节点扩展子节点的顺序时采用上述预测技术大大减少了计算子节点PED的次数，简化了扩展子节点的排序过程，从而降低了检测算法的计算复杂度。然后再采用并行排序替代冒泡排序的方法从K个扩展分组中选出具有K个最小PED的扩展子节点作为一个子组，进一步降低了算法的复杂度。改进K－Best算法主要过程如下:

1)将系统模型转化成实数模型，并对信道矩阵H进行实数QR分解。

2)初始化根节点，由i+1层保留K个扩展子节点得到第i层节点，从第2NT层开始进行检测;当i=2NT时，该层每个节点扩展得到Mc个扩展子节点，采用预测技术确定第i层每个节点的扩展子节点的顺序，即保留每个节点的前K个扩展子节点并按升序排列;在基于预测技术的方法确定K个扩展子节点序列后，每一层得到K个按升序排列的节点分组，每个分组有K个按升序排列的扩展子节点。

3)对K个按升序排列的节点分组，采用并行排序方法从上述K个扩展节点分组中选出具有K个最小PED的扩展子节点作为一个子组输出到下一层。

4)逐层检测，重复步骤2)和3)，直至i=1时，将具有最小PED所对应的子组，即候选矢量^s作为最终的检测结果。

2.3 算法性能仿真

基于上述球形检测算法的分析、提出的预测技术以及并行排序结合的K－Best算法，本文对该检测算法进行了MATLAB性能仿真。图1采用4发4收的MIMO通信系统，调制方式为16QAM，K=4，信道为准静态瑞利平坦衰落信道，对检测算法进行MATLAB仿真，比较了两种检测算法之间的误码率性能。

图1 传统K－Best算法和改进K－Best算法性能比较

从图1可以看出，改进的K－Best检测算法在降低计算复杂度的情况下与传统K－Best算法性能基本一致，这说明在保证降低算法复杂度的前提下改进的K－Best检测算法仍然具有较高的分集增益，满足MIMO通信系统低误码率的设计要求。

3 算法的FPGA实现设计

根据算法的特点，由于该算法较为复杂，运算较多，为达到速度的要求，在设计中采用流水线操作并进行并行处理，节省了处理时间。该流水线架构可允许在每个时钟周期中进行数据处理，在检测信号的每一层，只保留最小的K个度量值对应的路径来确定扩展情况。因此，检测结构的每级只需要一个PE单元，对该系统而言，PE单元的总数为8。图2给出了该检测算法流水线操作并行处理结构实现框图。

图2 检测算法流水线结构实现框图

图2中，PE单元表示该层节点扩展和子节点排序操作，预计算Γ是星座点和上三角矩阵R相乘的结果。在检测发送信号时基于广度优先的准则，在检测信号的每一层，只保留最小的K个度量值对应的路径，搜索结束后把具有最小PED所对应的候选矢量^s作为最终的检测结果。在进行PED排序并选出最小的K个路径进行下一次搜索时，若使用冒泡法排序，所需的比较选择单元虽然较少，但需要消耗很多个时钟周期，例如对于16QAM调制，K取10时，完成一次排序至少需要40个时钟周期［6］，下一环节的PED计算单元需要等待较长的时间，这意味着算法的吞吐率很低。因此，本文检测算法采用预测技术和并行排序结合的方法，降低了计算复杂度，并采用并行流水结构实现，节省了处理时间，实现了较高的数据吞吐量。

信道矩阵预处理单元负责对矩阵H进行QR分解以便于检测单元进行排序筛选操作，下面给出了QR分解的实现电路结构。

3.1 QR分解的Givens旋转实现

在信道矩阵预处理过程中，主要负责对信道矩阵H进行QR分解，本文中QR分解基于吉文斯旋转使用一阵列电路实现［7］。QR分解通过一系列Givens旋转变换得到，即Q矩阵是一系列二维旋转矩阵的乘积。每一次旋转将信道矩阵H的某一列中的一个非零元素变换为零，这样反复旋转直到信道矩阵H中剩下的非零元素全部在上三角部分，就得到了上三角矩阵R。如图3所示，其中的六边形和正方形模块都表示Givens旋转单元。六边形单元处在第一行的最左边位置称为边界单元(boundary cell)，用于产生Givens旋转的半径、正弦和余弦并存储结果。正边形单元又称为内部单元(interior cell)用于生成Givens变换后的向量。

图3 QR分解电路实现

开始时，所有运算单元中的寄存器值都置零。随着矩阵H不断进入寄存器中，分别由边界单元和内部单元计算Givens变换，并将计算结果存放于计算单元的寄存器中。

图4a所示为边界单元的电路结构。设寄存器的初始值为x，输入值为y，边界单元设计生成吉文斯旋转的3个值:x′=，cosθ=x/x′，sinθ=y/y′。其中x′存入x所在的寄存器，寄存器置零。边界单元的输出值cosθ和sinθ被放在同一行的内部单元，用于计算Givens变换后的2维向量。内部单元的电路如图4b所示。内部单元计算后将寄存器x与y中的值替换为新得到的x′和y′，其中x′作为QR分解中R矩阵的元素保留，y′将在计算下一行的Givens变换时被利用。

图4 单元电路实现

3.2 硬件仿真实现

基于上述球形检测算法的分析和提出的FPGA实现设计方案，本文对改进的K－Best检测算法进行了硬件编程实现。该球形检测算法采用Verilog语言编写代码，使用ISE10.1软件等进行综合、布线，并在Xilinx公司的Virtex－5系列的XC5VLX330 FPGA上完成了板级验证。

通过试验，在Virtex－5系列FPGA芯片中，按方案实现了4发4收16QAM系统的K－Best检测算法，该算法实现资源消耗为使用Slice 10860个，占资源21%，使用块RAM为102个，占总资源的25%，设计工作时钟频率为135 MHz。与文献［8］相比，本文检测算法实现资源消耗得到了有效降低，在资源开销不大的情况下，达到了较高的吞吐率。表1列举了此MIMO球形检测算法FPGA实现的资源耗用情况。

表1 K－Best检测算法实现资源耗用

4 结论

本文在研究MIMO系统球形检测算法的基础上，针对传统K－Best算法做出了改进，给出了该检测算法流水线操作并行处理结构实现方案。改进算法采用预测技术和并行排序相结合的方法，降低了算法复杂度，并采用并行流水线结构实现，节省了处理时间。经软件仿真和硬件实现表明，该检测算法在性能损失不大的情况下降低了算法的计算复杂度，减少了硬件资源消耗，硬件实现的性能与理论性能接近，验证了实现方案的正确性和有效性。

［1］张建忠，李宏伟，邓冬虎.一种低复杂度的空时分组码检测算法［J］.电视技术，2011，35(2):67－68.

［2］FOSCHINI G J.Layered space－time architecture for wireless communication in fading environment when using multiple antennas［J］.Bell Labs Technical Journal，1996，1(2):41－59.

［3］LI Qingwei，WANG Zhongfeng.Improved K－Best sphere decoding algorithms for MIMO system［C］//Proc.2006 IEEE International Symposium on Circuits and Systems.［S.l.］:IEEE Press，2006:110－113.

［4］林云，王宇.MIMO系统K－Best球形译码算法研究［J］.电波科学学报，2009(1):141－145.

［5］BURG A，BORGMANN M，SIMON C.Performance tradeoffs in the VLSI implementation of the sphere decoding algorithm［C］//Proc.IEEE 3G Mobile Communication Conf.［S.l.］:IEEE Press，2004:93－97.

［6］GENTLEMAN W M，KUNG H T.Matrix triangularization by systolic arrays［J］.Real－time signal processing，1981，298(5):19－26.

［7］DICK C，AMIRI K，CAVALLARO J R.Design and architecture of spatial multiplexing MIMO decoders for FPGAs［C］//Proc.42nd Asilomar Conference on Signals，Systems and Computers.［S.l.］:IEEE Press，2008:160－164.

［8］马小晶，刘亮，叶凡，等.基于可配置型K－Best的MIMO信号检测器［J］.计算机工程，2009(24):236－238.