一种基于宽度优先搜索的多天线系统并行检测方法

摘要

本发明公开了一种基于宽度优先搜索的多天线系统并行检测方法，特征是处理系统由输入接入预处理模块，预处理模块的输出端与树搜索模块的输入端相连接，树搜索模块的输出端与输出模块的输入端相连接，输出模块的输出端为系统输出；引入一种新的复数检测模型到实数检测模型的转换，利用新的实数检测模型下实数信道矩阵经正交上三角分解后上三角矩阵的特殊性质，采用了两层同时计算的方法加速运行，以提高算法的并行度，同时采用子树复用的方法减小运算量，从而减少指令周期数，加快算法运行速度，提高译码的吞吐率。与现有的列表最优（Kbest）检测方法相比，采用本发明方法可以在保证性能不下降的同时，使得多天线系统检测过程所需执行周期数平均减少35%。

说明书

技术领域

本发明属于数字通信中的并行检测方法技术领域，具体涉及多天线系统中基于宽度优先搜索的并行检测方法。 

背景技术

以多天线系统（MIMO）为主要特征的第四代移动通信系统在提高系统的数据速率的同时，随着天线数目的增长和调制阶数的增大，其检测算法的复杂度也呈指数增长。宽度优先球形译码算法（Breadth-First Sphere Decoding）借鉴了经典球形译码算法中的搜索树模型，同时以一种单向的方式逐层向前搜索，并在该过程中按照某种准则去除部分支路，由于其结构简单，适于硬件实现，因而得到广泛应用。 

《国际电子电气工程师协会-通信领域选刊》（IEEE Journal on Selected Areas in Communications，VOL.24，No.3，pp.491-503，2006）介绍了一种易于实现的宽度优先球形译码算法——列表最优（Kbest）算法，该算法每次选出当前计算的部分欧式距离最小的前K条路径，同时去除其它子节点下的支路，这种方法特点是数据流动规整，不存在回溯操作，适合于硬件并行化实现。 

然而在列表最优（Kbest）算法的搜索树中，由于层与层之间是前后依赖的，即后面层的计算依赖于前面层的结果，否则无法计算出该层的代价值，因此算法在层与层之间是严格串行的。为了进一步提高算法的执行效率，需要设法消除层与层之间的相关性，提高计算的并行度，减少计算周期，提高数据吞吐速率。 

发明内容

本发明提出一种基于宽度优先搜索的多天线系统（MIMO）并行检测方法，以提高算法的并行度，从而减少指令周期数，加快算法运行速度，提高译码的吞吐率。 

本发明基于宽度优先搜索的多天线系统并行检测方法，其特征在于处理系统由预处理模块A1、树搜索模块A2、以及输出模块A3按如下配置连接组成：系统的输入接入预处理模块A1，预处理模块A1的输出端与树搜索模块A2的输入端相连接，树搜索模块A2的输出端与输出模块A3的输入端相连接，输出模块A3的输出端为系统输出； 

其中预处理模块A1的结构为：系统的一个复数接收信号矢量y_c输入接入到复实转换单元B1的输入端，系统的另一个复数信道矩阵H_c输入接入到复实转换单元B2的输入端；复实转换单元B2的实数信道矩阵H输出接入到正交上三角分解单元B4的输入端；复实转换单元B1的实数接收信号矢量输出和正交上三角分解单元B4的一个正交矩阵Q输出作为矩阵相乘单元B3的输入；矩阵相乘单元B3的实数矢量y输出和正交上三角分解单元B4的另一个上三角矩阵R输出为预处理模块A1的两个输出； 

所述树搜索模块A2的结构为：预处理模块A1的一个实数矢量y输出接入到偶数层 代价值计算单元C1的输入端和奇数层代价值计算单元C2的输入端，预处理模块A2的另一个上三角矩阵R输出接入到偶数层代价值计算单元C1的输入端和奇数层代价值计算单元C2的输入端；偶数层代价值计算单元C1的输出端和奇数层代价值计算单元C2的输出端接入到求和单元C3的输入端；求和单元C3的输出端接入到排序单元C4的输入端；排序单元C4的两个输出端接入到偶数层代价值计算单元C1的输入端和奇数层代价值计算单元C2的输入端，另一个输出端作为树搜索模块A2的输出； 

所述输出模块A3的结构为：树搜索模块A2的输出作为实复转换单元D1的输入，实复转换单元D1的输出作为输出模块A4的输出； 

并行检测操作按如下步骤进行：首先将多天线系统复数检测模型转换成实数检测模型，即：将复数接收信号矢量和复数发送信号矢量的每个元素的实部和虚部交替安排，即按照“实部-虚部-实部-虚部”的顺序排列；对复数信道矩阵变换之后的实数信道矩阵进行正交上三角分解之后分别得到正交矩阵和上三角矩阵，利用奇数层代价值的计算不依赖于其前一层的结果这一性质，对相邻的奇数层和偶数层进行同时计算：对等价出的搜索树模型的每两层分别计算其代价值，然后将对应在同一条路径上的两节点的代价值相加求和得到当前层子节点的代价值；并且在计算偶数层代价值的时候采用子树复用的方法减小其运算量，即利用搜索树的偶数层与奇数层在计算的时候相互独立的性质，在计算奇数层在偶数层扩展出的log2(M)*log2(M)个子节点的代价值时，只计算前log2(M)个，然后复制log2(M)次，其中的M为调制阶数。 

由于本发明基于宽度优先搜索的多天线系统并行检测方法中引入了一种新的复数检测模型到实数检测模型的转换，利用新的模型下正交上三角分解（QR分解）后上三角矩阵的特殊性质，采用了两层同时计算的方法加速运行，以提高算法的并行度，同时采用子树复用的方法减小运算量，从而减少指令周期数，加快算法运行速度，提高译码的吞吐率。与现有的列表最优（Kbest）检测方法相比，采用本发明方法可以在保证性能不下降的同时，使得多天线系统检测过程所需执行周期数平均减少35%。 

附图说明

图1为本发明基于宽度优先搜索的多天线空分复用系统并行检测方法的处理系统示意图。 

图2为本发明基于宽度优先搜索的多天线空分复用系统并行检测方法中两层同时计算以及相应的子树复用操作的从树搜索角度理解的示意图。 

具体实施方式

下面结合附图通过具体实施例对本发明做进一步的详述。 

实施例1： 

图1给出了基于宽度优先搜索的多天线空分复用系统并行检测方法的处理系统示意图。采用本发明方法的处理系统由预处理模块A1、树搜索模块A2、以及输出模块A3按如下配置连接组成：系统的输入接入预处理模块A1，预处理模块A1的输出端与树搜 索模块A2的输入端相连接，树搜索模块A2的输出端与输出模块A3的输入端相连接，输出模块A3的输出端为系统输出。 

其中预处理模块A1的结构为：系统的一个复数接收信号矢量y_c输入接入到复实转换单元B1的输入端，系统的另一个复数信道矩阵H_c输入接入到复实转换单元B2的输入端；复实转换单元B2的实数信道矩阵H输出接入到正交上三角分解单元B4的输入端；复实转换单元B1的实数接收信号矢量输出和正交上三角分解单元B4的一个正交矩阵Q输出作为矩阵相乘单元B3的输入；矩阵相乘单元B3的实数矢量y输出和正交上三角分解单元B4的另一个上三角矩阵R输出为预处理模块A1的两个输出； 

所述树搜索模块A2的结构为：预处理模块A1的一个实数矢量y输出接入到偶数层代价值计算单元C1的输入端和奇数层代价值计算单元C2的输入端，预处理模块A2的另一个上三角矩阵R输出接入到偶数层代价值计算单元C1的输入端和奇数层代价值计算单元C2的输入端；偶数层代价值计算单元C1的输出端和奇数层代价值计算单元C2的输出端接入到求和单元C3的输入端；求和单元C3的输出端接入到排序单元C4的输入端；排序单元C4的两个输出端接入到偶数层代价值计算单元C1的输入端和奇数层代价值计算单元C2的输入端，另一个输出端作为树搜索模块A2的输出；其中计算奇数层代价值时采用子树复用以减小计算量。 

所述输出模块A3的结构为：树搜索模块A2的输出作为实复转换单元D1的输入，实复转换单元D1的输出作为输出模块A4的输出。 

本实施例中设通信系统的参数为：4根发射天线，4根接收天线16QAM星座调制，选择列表长度参数K=4。该通信系统在接收端的复数检测模型为y_c＝H_cs_c+n_c，其中y_c是复数接收信号矢量，s_c是待检测的发送信号矢量，H_c是复数信道矩阵，n_c是高斯白噪声矢量。上述复数检测模型按元素展开的具体展开形式如下： 

$\left(\begin{array}{c}{y}_{c1}\\ y_{c2}\\ y_{c3}\\ y_{c4}\end{array}\right)=\left(\begin{array}{cccc}{H}_{C11}& H_{C12}& H_{C13}& H_{C14}\\ H_{C21}& H_{C22}& H_{C23}& H_{C24}\\ H_{C31}& H_{C32}& H_{C33}& H_{C34}\\ H_{C41}& H_{C42}& H_{C43}& H_{C44}\end{array}\right)\left(\begin{array}{c}{s}_{c1}\\ s_{c2}\\ s_{c3}\\ s_{c4}\end{array}\right)+\left(\begin{array}{c}{n}_{c1}\\ n_{c2}\\ n_{c3}\\ n_{c4}\end{array}\right)$

（1）预处理模块A1操作 

首先，将复数接收信号矢量y_c和复数信道矩阵H_c分别输入到图1中预处理模块的矩阵相对应的复实转换单元B1和B2中。 

在复实转换单元B1中，将上述复数检测模型按照“实部-虚部-实部-虚部”的排列顺序转换为实数检测模型如下，其中即为变换之后的实数接收信号矢量并作为复制转换 单元B1的输出： 

$\hat{y}={\left(\begin{array}{ccccccc}\mathrm{Re}\left(y_{c1}\right)& \mathrm{Im}\left(y_{c2}\right)& ·& ·& ·& \mathrm{Re}\left(y_{c3}\right)& \mathrm{Im}\left(y_{c4}\right)\end{array}\right)}^T$

在复实转换单元B2中，按照如下方式将复数信道矩阵Hc转换为实数信道矩阵H，并作为复实转换单元B2的输出： 

在正交上三角分解单元B4中，对复实转换单元B2的输出实数信道矩阵H进行正交上三角分解（QR分解）H=QR，其中Q为正交矩阵，连接到矩阵相乘单元B3的输入端；R为上三角矩阵，作为预处理模块A1的输出，并且上三角矩阵R具有特殊性质：所有偶数列的对角线元素的下一个元素为0，即R_2k,2k+1＝0,k＝1,2,3,4。 

在矩阵相乘模块B3中，将实数接收信号矢量与正交上三角分解单元输出的上三角矩阵Q的转置相乘，得到实数矢量y，即具体过程如下所示： 

（2）树搜索模块A2操作 

将来自预处理模块A1的输出实数矢量y和上三角矩阵R分别接入到偶数层代价值计算单元C1和奇数层代价值计算单元C2中，初始累积代价值PED₉(s⁹)＝0。 

先计算出第8层和第7层，直接计算第8层代价值（即该层的部分欧式距离） 1＜p＜4，1＜q＜4，其中星座点集合矢量S的取值为{-3,-1,1,3}。这里在计算第7层代价值只需要算4个，而不是16个，利用子树复用的性质。然后偶数层代价值计算单元C1的输出和奇数层代价值计算单元C2的输出输入到求和单元C3中，计算出此时的累积代价值 ${\mathrm{PED}}_7^l\left(s^7\right)=D_8^{1/4}\left(s^8\right)+D_7^{l\%4}\left(s^7\right),$1＜l＜16作为求和单元C3的输出并输入到排序单元C4中，在排序单元C4中对这16个值排序，保留最小的4个，相应的代价值记为 1＜k＜4，将幸存路径节点信息输入到偶数层代价值计算单元Cl和奇数层代价值计算单元C2中，对应的幸存路径代价值信息输入到求和单元C4中，用于下一轮计算的代价值求和。 

图2为本发明基于宽度优先搜索的多天线空分复用系统并行检测万法中两层同时计算以及相应的子树复用操作的从树搜索角度理解的示意图。图2中下部的局部放大箭头符号表示将计算第6层和第5层过程部分进行局部放大后的进一步细化内容。 

所述子树复用的具体操作过程如下: 

接下来计算第6层和第5层，在偶数层代价值计算单元Cl中计算剩余向量 $b_6^k\left(s^7\right)=y_6-\underset{j=7}{\overset{8}{\Sigma }}{R}_{6,j}{s}_j^k,$1＜k＜4，$D_6^{k,p}\left(s^6\right)={|b_6^k\left(s^7\right)-R_{\mathrm{6,6}}{S}^p|}^2,$1＜p＜4，在奇数层代价值计算单元中计算$b_5^k\left(s^7\right)=y_5-\underset{j=7}{\overset{8}{\Sigma }}{R}_{5,j}{s}_j^k,$1＜k＜4，$D_5^{k,p}\left(s^6\right)={|b_5^k\left(s^7\right)-R_{\mathrm{5,5}}{S}^q|}^2,$1＜q＜4，注意这里利用了子树复用的性质，如图2局部放大区域所示，也就是只计算图2局部放大区域中第5层的16个扩展子节点中的前4个，即1～4号扩展子节点，如图2局部放大区域中小虚线框所示，然后将这4个节点的代价值直接依次赋给5～8号、9～12号和13～16号扩展子节点的代价值，这就是子树复用过程。然后偶数层代价值计算单元C1的输出 和奇数层代价值计算单元C2的输出输入到求和单元C3中，并和上一次从排序单元C4中输入过来的幸存路径代价值信息一起求和，计算出此时的累积代价值为${\mathrm{PED}}_5^{16(k-1)+l}\left(s^7\right)={\mathrm{PED}}_7^k\left(s^7\right)+D_6^{k,l/4}\left(s^5\right)+D_5^{k,l\%4}\left(s^5\right),$1＜l＜16,1＜k＜4，这样计算得到第5层64个待选子节点的代价值输入到排序单元C4中，经过排序之后保留代价值最小的4个幸存子节点，相应的代价值记为1＜k＜4，将幸存路径节点信息输入到偶数层代价值计算单元C1和奇数层代价值计算单元C2中，对应的幸存路径代价值信息输入到求和单元C4中，用于下一轮计算的代价值求和。 

重复依照上述过程接着计算出第3层累积代价值1＜k＜4，然后计算到64个最后一层（即第1层）累积代价值PED₁(s¹)的值时，直接从这64个值中选出累积代价值最小的一个值所对应的幸存节点作为树搜索模块A2的输出。 

（3）输出模块A3操作 

在输出模块A3中的实复转换单元D1中将来自树搜索模块A2的最后一层幸存节点按照“实部-虚部-实部-虚部”的排列顺序逆向转换为复数向量，并作为系统的最终输出。 

下面的表1为采用16QAM调制且列表长度参数K=4的情形下，不同天线数时的采用本发明方法与采用传统的列表最优（Kbest）检测方法在并行计算平台上所需的执行周期数的比较。 

表1 

从表1可以看出，采用本发明方法在并行计算平台上所需的执行周期数明显的少于传统的列表最优（Kbest）检测方法。平均说来，采用本发明方可以使执行周期数减少35%左右，从而大大加快了运行时间，提高了译码的数据吞吐率。