基于FFT算法的复序列互相关在FPGA上的加速实现方法及系统

技术领域

本发明涉及数字信号处理领域，具体涉及一种基于FFT算法的复序列互相关在FPGA上的加速实现方法及系统。

背景技术

信号处理领域中根据处理信号的类型，分为模拟信号处理与数字信号处理，数字信号处理是研究如何用数字或符号序列来表示信号以及如何对这些序列进行处理的一门学科。相比于模拟信号处理领域，数字信号处理具有精度高、可靠性高、灵活性强、便于大规模集成化、便于加密处理以及低频信号处理成其优越。由于数字信号本身的特点以及高速数字计算机和微处理的应用，使得一些数字信号处理算法应运而生。

FPGA(Field－Programmable Gate Array)，即现场可编程门阵列，它是在PAL、GAL、CPLD等可编程器件的基础上进一步发展的产物。它是作为专用集成电路(ASIC)领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。以硬件描述语言(Verilog或VHDL)进行电路设计，可以经过简单的综合与布局，快速的烧录至FPGA上进行测试，完成产品的快速成型。FPGA所有逻辑单元均由时钟驱动来工作，所有电路行为均并行执行，这使得基于FPGA来做算法(硬件加速)成为主流。

现有技术中，目前类似的专利技术如专利名称为：一种基于FPGA实现互相关运算的方法，公开号为108089839A，其公开了一种基于FPGA实现互相关运算的方法，其有以下两个主要特征：1、该运算方法通过AD采样模块进行数据采集，将模拟信号转换为数字信号，然后利用FPGA硬件资源丰富的特点，采用硬件电路实现两路信号的互相关运算；2、该方法比传统的从FPGA的RAM地址取出单一数据进行乘累加运算具有更高的速度和效率，可以充分利用FPGA并行运算的特点，降低运算时间。

上述公开专利申请中，其设计架构如图1所示，基于FPGA硬件平台，AD采集后得到的是两路实序列，系统只能处理两路实序列的互相关，运算直接在时域展开，具体地，根据序列的类型，分为实数序列及复数序列：

两个实离散时间序列x(n)与y(n)的互相关函数定义为：

定义x(n)为本地短序列，n＝0,1,…,N-1,短序列长度为N；

定义y(n)为待检长序列，n＝0,1,…,M-1,长序列长度为M；

实序列x(n)与y(n)互相关实域计算结构如图2所示，完成一次实序列x(n)与y(n)的互相关计算，所需乘法次数为：N*(M-N)。

两个复离散时间序列a(n)与y(n)的互相关函数定义为：

其中，a(n)＝R

定义a(n)为本地短复序列，n＝0,1,…,N-1,短序列长度为N；

定义b(n)为待检长复序列，n＝0,1,…,M-1,长序列长度为M；

复序列相关计算结构如图3、图4所示，其中，图3为实部结果，用公式表示为：R＝R

计算复序列互相关的结果r

通过上述运算过程可以发现，现有基于时域直接计算两个序列的互相关，需要大量的乘法运算，占用大量的乘法器资源，会造成系统较大的时延，时序收敛效果差。为此，急需一种能够节约乘法器资源并能优化时序的方法，提高FPGA实现互相关的性能。

发明内容

本发明的目的在于提供一种基于FFT算法的复序列互相关在FPGA上的加速实现方法及系统，用以解决现有复序列互相关的实现占用大量的乘法运算，造成系统较大的时延，时序收敛效果差，对整个FPGA系统的性能造成很大影响的问题。

为实现上述目的，本发明的技术方案为基于FFT算法的复序列互相关在FPGA上的加速实现方法，包括以下步骤：

FFT运算步骤，利用FFT算法分别将两个待互相关的复序列从时域转换到频域；

共轭点乘运算步骤，将两个完成时域到频域转换的复序列在频域进行共轭点乘运算；

IFFT运算步骤，利用IFFT算法将共轭点乘运算结果从频域变换到时域，得到时域复序列；

能量计算步骤，计算出IFFT运算步骤得到的时域复序列中每个点的能量，并输出能量结果序列；

判决步骤，搜索出能量计算步骤中所得到的能量最大值，该能量最大值的点所在的位置即为两个复序列相关性最大点的位置。

进一步地，作为优选技术方案，还包括补零处理步骤，当两个复序列长度不等时，通过补零处理步骤先对两个复序列中较短的复序列进行补零处理，以使两个复序列长度相等，完成补零处理后，再进行FFT运算。

进一步地，作为优选技术方案，所述FFT运算步骤和IFFT运算步骤中，利用FPGA内置的IP core来实现FFT/IFFT运算。

进一步地，作为优选技术方案，所述FFT运算步骤中，通过FPGA内置的CoreGenerator工具来生成两个FFT单元，用于实现两个复序列的FFT运算。

进一步地，作为优选技术方案，所述FFT运算步骤和IFFT运算步骤中，利用FPGARTL编码来实现FFT/IFFT运算。

基于FFT算法的复序列互相关在FPGA上的加速实现系统，包括：

FFT运算单元，利用FFT算法，用于分别将两个待互相关的复序列从时域转换到频域；

共轭点乘运算单元，用于将两个完成时域到频域转换的复序列在频域进行共轭点乘运算；

IFFT运算单元，利用IFFT算法，用于将共轭点乘运算结果从频域变换到时域，得到时域复序列；

能量计算单元，用于计算出IFFT运算步骤得到的时域复序列中每个点的能量，并输出能量结果序列；

判决单元，用于搜索出能量计算步骤中所得到的能量最大值，该能量最大值的点所在的位置即为两个复序列相关性最大点的位置。

进一步地，作为优选技术方案，还包括补零处理单元，当两个复序列长度不等时，通过补零处理单元先对两个复序列中较短的复序列进行补零处理，以使两个复序列长度相等，完成补零处理后，再进行FFT运算。

进一步地，作为优选技术方案，所述FFT运算单元和IFFT运算单元来自FPGA内置的IP core硬件加速器，用以实现FFT/IFFT运算。

进一步地，作为优选技术方案，所述FFT运算单元通过Core Generator工具生成，用于实现两个复序列的FFT运算。

进一步地，作为优选技术方案，所述FFT运算单元和IFFT运算单元通过FPGA RTL编码来实现FFT/IFFT运算。

本发明相对于现有技术，具有如下有益效果：

(1)本发明通过先利用FFT算法先将时域信号转换至频域，再在频域进行共轭点乘运算，再通过IFFT算法将运算结果从频域搬移至时域，快速得到复序列互相关结果，相对于现有传统的直接时域开展相关运算来说，大大减少了乘法运算次数，真正做到低延时、高效率及时序易收敛，对FPGA硬件来说，大大减少了对乘法器资源的占用，优化了FPGA时序，节约了硬件资源，本发明很好地解决了现有复序列互相关运算过程中产生过量乘法运算的问题，能够让FPGA系统的硬件发挥出最佳性能。

(2)本发明可很好地应用于无线电信号相关捕获过程，并能够在很大程度上提升系统性能，使单FPGA系统具备更强大的性能。

(3)本发明能够同时支持实序列及复序列的互相关处理，并同样具有低延时、高效率及时序易收敛等特性。

附图说明

图1为现有专利实现两路实序列互相关的方法架构图；

图2为实序列互相关实域计算结构图；

图3为基于实部的复序列互相关实域计算结构图；

图4为基于虚部的复序列互相关实域计算结构图；

图5为本发明的方法流程图；

图6为本发明的结构组成图；

图7为本发明基于FPGA IP core实现FFT/IFFT时的组成结构图；

图8为本发明基于FPGA RTL实现FFT/IFFT时的组成结构图。

具体实施方式

以下实施例用于说明本发明，但不用来限制本发明的范围。

实施例

如图5所示，本实施例所述的基于FFT算法的复序列互相关在FPGA上的加速实现方法，包括以下步骤：

FFT运算步骤，利用FFT算法分别将两个待互相关的复序列从时域转换到频域；

共轭点乘运算步骤，将两个完成时域到频域转换的复序列在频域进行共轭点乘运算；

IFFT运算步骤，利用IFFT算法将共轭点乘运算结果从频域变换到时域，得到时域复序列；

能量计算步骤，计算出IFFT运算步骤得到的时域复序列中每个点的能量，并输出能量结果序列；

判决步骤，搜索出能量计算步骤中所得到的能量最大值，该能量最大值的点所在的位置即为两个复序列相关性最大点的位置。

下面以具体实例对本发明的实现过程作具体说明。

假定复序列a(n)与复序列b(n)为待互相关的两个复序列，复序列a(n)的长度为N，复序列b(n)的长度为M，当N＞M时，需要对复序列b(n)进行补零处理，补充N-M个零，反之，当N＜M时，则需要对复序列a(n)进行补零处理，补充M-N个零。

完成补零处理后，对两个复序列进行FFT运算，分别得到序列A(k)、B(1)，序列A(k)、B(1)的表达式如下：

A(k)＝R

B(l)＝R

对序列A(k)、B(l)进行共轭点乘运算，得到复序列D(m)，复序列D(m)的表达式如下：

D(m)＝A(m).*B(m)＝R

完成共轭点乘运算后，对复序列D(m)进行IFFT运算，实现复序列D(m)从频域到时域的变换，输出时域复序列d(n)，其表达式如下：

d(n)＝R

对时域复序列d(n)中的每个点进行能量计算，并输出能量结果序列E(n),E(n)的表达式如下：

最后，完成对能量最大值点的搜索，能量最大点的位置就是a(n)与b(n)相关性最大点的位置。

能量计算可以通过FPGA里面的DSP单元实现，判决则可以采用两个寄存器来实现，一个寄存器用于寄存能量最大值，比如寄存器flip_flop，另一个寄存器用于寄存最大值点对应的位置。

下面对上述方法给出论证，具体如下：

首先，将实离散时间序列x(n)与y(n)的互相关函数定义为：

可以证明，r

R

其中:X(k)＝DFT[x(n)]，Y(k)＝DFT[y(n)]，R

证：将x(n)、y(n)的逆离散傅里叶变换代入互相关函数定义式

因x(n)是实序列，所以x(n)＝x

因为

故

证毕。

复离散时间序列a(n)与b(n)的互相关函数定义为

根据DFT的性质，时域卷积等效于频域相乘，r

R

其中:A(k)＝DFT[a(n)]，B(k)＝DFT[b(n)]，R

如图6所示，本实施例在上述方法的基础上，还公开了一种基于FFT算法的复序列互相关在FPGA上的加速实现系统，包括：

FFT运算单元，利用FFT算法，用于分别将两个待互相关的复序列从时域转换到频域；

共轭点乘单元，用于将两个完成时域到频域转换的复序列在频域进行共轭点乘；

IFFT运算单元，利用IFFT算法，用于将共轭点乘运算结果从频域变换到时域，得到时域复序列；

能量计算单元，用于计算出IFFT运算步骤得到的时域复序列中每个点的能量，能量计算单元可采用FPGA内的DSP单元来实现。

判决单元，用于搜索出能量计算步骤中所得到的能量最大值，该能量最大值的点所在的位置即为两个复序列相关性最大点的位置。判决单元可采用两个寄存器来实现，一个寄存器用于寄存能量最大值，比如寄存器flip_flop，另一个寄存器用于寄存最大值点对应的位置。

在上述结构的基础上，本实施例还包括补零处理单元，当两个复序列长度不等时，通过补零处理单元先对两个复序列中较短的复序列进行补零处理，以使两个复序列长度相等，完成补零处理后，再进行FFT运算。

如图7所示，本实施例的FFT运算单元和IFFT运算单元来自FPGA内置的IP core硬件加速器，用以实现FFT/IFFT运算。FPGA内置有专门的FFT/IFFT IP core硬件加速器，IPcore不额外占用FPGA逻辑资源，并且时序已经在出厂前已完成优化处理，不会对用户设计逻辑造成时序影响，具体地，可以通过Core Generator工具生成两个M点的FFT单元，用于完成复序列a(n)、b(n)序列的FFT运算。另外，需要说明的是，IP core全称为IntelligenceProperty Core，意为知识产权核心，IP Core是指可用来生成ASIC和PLD的逻辑功能块。

如图8所示，实施例也可采用FPGA RTL编码来实现FFT/IFFT运算，通过FPGA RTL来生成FFT/IFFT单元，在FPGA上完成硬件加速。RTL全称为Register Transfer Level，意为寄存器传输级，其用于利用硬件描述语言对进行电路设计。

通过上述方法及结构可以看出，本发明在实现复序列相关时，不再从时域进行运算，而是先利用FFT算法先将时域信号转换至频域，再在频域进行共轭点乘运算，再通过IFFT算法将运算结果从频域搬移至时域，快速得到互相关结果,即在频域内完成互相关的快速运算。

现有传统的互相关算法，完成一个长度为N的a(n)短序列与一个长度为M的长序列b(n)之间的互相关运算，需要的乘法次数为N*4*(M-N)。

而基于本发明所述的方法，分别以基2/基4FFT算法计算运算量，具体如下：

采用基2FFT算法计算N点的FFT/IFFT需要的乘法运算的次数为：

采用基4FFT算法计算N点的FFT/IFFT需要的乘法次数为：

以1024点的长复序列与256点的短复序列互相关为例，传统方法的直接时域互相关需要的乘法次数为：786432次，而采用本发明所给出的方法则只需要17920次，约为直接时域互相关所需要次数的2％，极大地减少了乘法运算次数，优化了FPGA时序，真正做到低延时、高效率及时序易收敛，同时还能节约硬件资源，以便让硬件发挥最佳性能。随着FPGA技术的发展，FPGA全电路并行处理特征使得算法的应用成为现实，而通过发明方案所示进行RTL代码设计、仿真，能够保证电路行为完成符合算法描述。另外，若本发明应用于无线电信号相关捕获过程，在很大程度上提升了系统性能，使单FPGA系统具备更强大的性能。

另外，将复序列的虚部设置为0时，本发明还可完成实序列的互相关处理，因此，本发明能同时支持实序列及复序列的互相关处理，并同样具有低延时、高效率及时序易收敛等特性。

虽然，上文中已经用一般性说明及具体实施例对本发明作了详尽的描述，但在本发明基础上，可以对之作一些修改或改进，这对本领域技术人员而言是显而易见的。因此，在不偏离本发明精神的基础上所做的这些修改或改进，均属于本发明要求保护的范围。