基于Grover算法的通信系统信号检测
摘要：该文设计了一种基于Grover算法的MIMO-OFDM系统信号检测方案，将Grover算法应用于寻找最小判决值以此来判决发送序列。通过MATLAB仿真，将Grover的改进算法与传统检测算法在性能和复杂度方面做了分析比较，可以在有效降低经典最佳检测算法复杂度的同时，达到与经典最佳接收算法基本相同的性能。
关键词： Grover量子搜索算法；量子并行计算；MIMO-OFDM检测技术
Signal Detection Of Communication Systems Based On Grover Algorithm
ZHOU Li zhi1 LI Fei2
(College of Communication&Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003)
[Abstract] A investigation of the signal detection scheme with Grover Algorithm in the MIMO-OFDM system has been developed in this paper,and Grover algorithm is applied to find the minimum in order to decide the sending sequence.In order to test the efficiency and reliability of this algorithm, the analysis and comparison between improved Grover algorithm and other traditional algorithms is made by MATLAB simulation.It can reduce the complexity of the traditional optimum detection algorithm efficiently ,while achieving the same performance.
[Key words] Grover quantum search algorithm;quantum parallel computation; MIMO-OFDM detection
1 引言 自MIMO通信结构提出以来，通信界已对MIMO信号检测进行了广泛、深入的研究，并提出了很多信号检测算法，例如迫零(ZF)算法、最小均方误差(MMSE)算法、等等。然而，这些算法普遍都是基于平坦衰落MIMO 信道的，对于信道为频率选择性的宽带MIMO通信系统，其接收信号存在严重的码间干扰，是MIMO检测算法所无法克服的，必须采用能够对抗频率选择性衰落的技术。将OFDM技术引入MIMO，不仅能克服信道的频率选择性，还能进一步提高频带利用率。利用量子算法实现该系统的信号检测，可以利用量子算法的高度并行处理【1-3】运算特性大幅度降低算法的复杂度。
1996 年，Grover提出了一种量子搜索算法Grover算法，在量子计算机上对长度为N 的无序数据库进行求解，其时间复杂度为 ，而无序数据库的搜索问题在经典计算机上实现的时间复杂度为 【4-5】。本文提出一种基于Grover搜索算法的MIMO-OFDM检测方案，在有效降低经典最佳检测算法复杂度的同时，达到与经典最佳接收算法基本相同的性能。
2 MIMO-OFDM 系统
本论文中采用的信道模型来源于文献【6】。基于空间复用的无编码MIMO-OFDM系统检测框图如图1所示。
设发送端有M根天线，接收端有N 根天线，第m（m=1，…，M）根发送天线和第n（n=1，…，N）根接收天线间的信道为每径服从瑞利分布的多径衰落信道，OFDM子载波个数为K。在发送端，输入的比特流经过串/并转换后分成M个并行的数据流，以实现多天线的输出。对每一路子流，都要先进行信号映射再进行IFFT变换。这里的IFFT实现的是OFDM调制的功能，即将低速的多路并行数据流同时调制到相互正交的K个子载波上。为了减小系统的符号间干扰（ISI），在IFFT变换后，还要在符号间加入保护间隔。通常，为了减小子载波间的干扰，保护间隔采用循环前缀的形式。最后进行并串转换后发送。在接收端，每副天线接收到从M副不同天线发送并经过MIMO-OFDM信道线性叠加的信号后，首先对每一路数据流都要进行串并转换并去掉循环前缀；然后按照接收天线分别做K点的FFT变换，从时域变换到频域；最后，并行的数据流经过检测器处理后，送入解调器，并通过并/串转换器得到恢复的信息比特流。
图1 MIIMO-OFDM系统信号检测框图
在图1所示的MIMO-OFDM系统原理图中，对于具有K个子载波的OFDM系统，可以假设接收端完全知道信道H的状态信息，在一个OFDM符号的持续时间内，信道特性不变，循环前缀大于信道的时延扩展，系统不存在符号间干扰。那么在一个OFDM符号的持续时间内，任意一对天线之间的多径信道可以表示为K个具体复传输系数的并行频域子信道【7】。
3 量子Grover算法
Grover算法的意图是通过对初始等幅叠加态进行幺正变换，不断增加目标量子态的概率幅，同时减少其它非目标量子态的概率幅。最后目标量子态的概率幅越大，搜索（即测量）到正确目标的概率也越大。
Grover算法【4】描述如下：
（1）初始化。通过Walsh-Hadamard变换作用在量子态 上，使所有基矢的振幅相等。
（2）进行Grover迭代。反复进行下述(a)、(b)J次， 其中M为正确解的个数， 表示取整。
(a)选择性旋转变换 （相当于对解集作标记）：设 为输入中的一个基矢：当 时把矢量 旋转 ；当 时，不变。
(b)用变换 作用在各输入分量上。 的定义如下： 可以表示成 ，其中 是 变换矩阵， 是条件相移矩阵。矩阵 的作用是把满足 的量子态 的概率幅取反， 的定义如下：
（3）对输入进行测量，观察结果为 。若 ，则得到结果，否则重新开始算法。
Grover算法能够有效地对数据库进行搜索。但是它存在不足之处，在某些情况下Grover算法是无效的【6】。(1) 可以看到，当 时， ，无论迭代次数为多少， ，迭代与不迭代而直接测量的效果一样。因此此时算法是无效的。
(2) 在 时，为保证算法有较大成功概率需要的迭代次数不满足 关系。
为了解决上述Grover 算法存在的问题，文献【8】对Grover 算法加以了改进，下面将研究比较Grover算法及其改进的算法对MIMO-OFDM信号检测的效果。
4 基于Grover及其改进算法的信号检测设计方案
我们首先需要构造两个数据库，第一个数据库中有 个寄存器，保存所有可能的发送序列，相关矩阵 和接收信号作为进行判决的必要信息存储于计算机中，把每一种可能发送序列与相关矩阵和信道矩阵 根据 进行计算就可以得到 个判决值，将这些判决值存放于第二个数据库中。第一个数据库中的消息发送序列与第二个数据库中的判决值构成一一对应的关系。对应于 最小判决值的消息序列即为最佳检测方案检测出的发送序列。所以下面要做的工作就是寻找最小的判决值，以此来判决发送序列，可以使用Grover算法解决这一问题。
基本思想为：假设数据库二中有一组判决值为 ，对应于量子系统的 个量子基态 ，将它们存放于一个量子寄存器。在第二个数据库中有 ，现在求其在数据库中的位置。由于数据库二中的判决值与量子寄存器中的量子态是对应的，那么一旦在量子寄存器中找到 所对应的量子态的位置，也就确定了 在数据库二中的位置，从而找到 所对应的发送序列，将其作为判决得到的消息序列，这样使得利用量子搜索算法解决经典问题成为可能。
具体算法描述如下：
(1) 构造 位量子寄存器，包含量子基态 ，分别对应判决值 。表示为函数形式 。
(2) 使用Walsh-Hardamard变换初始化量子寄存器，此时量子寄存器的量子态为 ，其中 均为 。
(3) 在量子寄存器中随机取一量子基态，将其所对应的判决值作为门限值。将量子寄存器中首个量子基态 所对应的判决值 作为门限值。现在所要做的工作就是利用Grover算法找出量子寄存器中所对应判决值小于等于 的量子基态。使用旋转操作 将其概率幅旋转，否则保持不变。
(4) 对于量子基态概率幅向量应用矩阵 进行幺正变换，放大所要寻找量子基态的概率幅。
(5) 通过 算子和 算子的迭代作用后，便找出了量子寄存器中对应判决值小于等于 的所有量子基态，将目标量子态的寻找范围大大缩小。对所有搜索到的量子态重复(3)(4)操作，利用Grover算法搜索到所1126