一种1-D/2-D混合架构FFT处理器

摘要

本发明公开了一种1-D/2-D混合架构FFT处理器，其特征在于：处理器采用一维FFT运算模式进行32点到8K点的任意2

说明书

技术领域

本发明公开了一种一维/二维（1-D/2-D）混合架构FFT处理器，属于数字信号处理领域。

背景技术

目前，快速傅立叶变换(FFT)在数字通信、图像处理、语音识别、雷达处理等领域有着广 泛的应用，硬件实现FFT有软件不可比拟的速度优势，其基于现场可编程门阵列(FPGA)的实 现方法有着重要的研究价值。通常采用基-2FFT算法来处理长度为2ⁿ信号的FFT运算。N点 基-2的快速傅里叶变换因为其广泛的用途和自身的特殊性，要求其硬件实现的运算速度快， 而且要兼顾硬件面积，两者之间必须有良好的均衡。

现有技术中，1-D FFT处理器和2-D大点数FFT处理器均可实现任意2ⁿ点(n=5,6…14)单 精度浮点数FFT/IFFT运算，但它们在具体实现上各有缺陷，现分别讨论：

1、1-D FFT处理器

1-D FFT处理器如图1所示，内部集成FFT控制器、存储控制单元、FFT运算单元和2 组4*4K片上数据存储器。FFT运算单元内部集成读写地址生成单元、2个蝶形运算单元、旋 转因子生成器。对于N点FFT运算需要2N个数据存储单元RAM，存储资源太大。

1-D FFT处理器采用基-2算法和固定寻址结构，每个时钟周期能够并行完成2个蝶形运 算，即每个时钟周期从片上存储器并行读取4个操作数和两个系数，产生4个结果并写到片 上存储器。

2、2-D FFT处理器

2-D FFT处理器如图2所示，内部集成控制器、存储控制单元、FFT运算单元、数据传 输单元、3组4*256临时存储器(Memory0/1/2_x)和一块16K片上数据存储器。FFT运算单元 内部集成读写地址生成单元、2个蝶形运算单元、旋转因子生成器。2-D FFT处理器增加传输 模块进行一维行列数据传输。FFT处理的最大点数为16K，需要16K片上数据存储器作为二 维FFT缓存。

1-D FFT处理器的数据存储资源很大，2-D大点数FFT处理器对于N点FFT运算只需要 N个数据存储单元RAM，大大压缩内部存储资源。由于多个数据传输延时、蝶形单元流水延 时和访存延时的叠加，使的2-D大点数FFT处理器大大增加FFT运算时钟周期.

终上所述一维(1-D)FFT处理器，运算速度较快，但数据存储资源较大。二维(2-D)FFT处 理器可以实现一维大点数FFT运算，大大压缩内部存储资源，但运算速度较慢，而且仅限于 大点数FFT运算。

发明内容

本发明为避免上述现有技术所存在的不足之处，综合考虑FFT运算速度、存储资源消耗 以及灵活性，提供一种1-D/2-D混合架构FFT处理器，以期可以达到速度和资源之间的均衡。

本发明解决技术问题，采用如下技术方案：

本发明1-D/2-D混合架构FFT处理器，其特点在于：所述处理器包括控制器、存储系统、 数据交换网络、数据传输单元及FFT运算单元；

所述控制器用于控制数据传输单元和FFT运算单元；

所述存储系统包括2组4*2K片上数据存储器(Memory0/1_x)和3组4*32临时储存器 (Memory2/3/4_x)，2组4*2K片上数据存储器和3组4*32临时储存器采用简单双口RAM； 根据16K=128*128，二维FFT处理模式需要处理的最大一维FFT为128点，为了节省存储资 源，FFT处理器采用3组4*32的临时存储器乒乓操作完成行列一维FFT运算。

所述数据交换网络包括内存储控制单元、外存储控制单元及多路选择器；

所述内存储控制单元用于对2组4*2K片上数据存储器和3组4*32临时储存器进行灵活 的地址分配和管理以满足FFT/IFFT计算过程中并行数据读取和存储的要求，避免地址冲突的 产生，并为FFT运算单元和数据传输单元访问5组数据存储器提供统一接口，使每一个数据 端口（包括操作数端口、传输数据端口、运算结果端口）都能对各块片上存储器的任意存储 单元进行访存，而无需关心该存储单元属于哪一块片上存储器；

所述外存储控制单元为数据传输单元访问2组4*2K片上数据存储器提供统一接口；

所述多路选择器用于选择内存储控制单元或外存储控制单元进行访问2组4*2K片上数 据存储器；

所述数据传输单元用于完成2组4*2K片上数据存储器和3组4*32临时储存器之间的数 据传输，实现实时行或列数据搬运，为FFT运算单元提供将要进行的行或列FFT运算操作数， 并把FFT运算单元计算结果传回2组4*2K片上数据存储器中；

所述FFT运算单元用于实现数据的FFT或IFFT运算。所述FFT运算单元包括内部集成 读写地址生成单元、2个蝶形运算单元和旋转因子生成器。

本发明1-D/2-D混合架构FFT处理器，其特点也在于：所述处理器采用基-2算法和固定 寻址结构；所述处理器采取两种方法来隐藏数据路径上的时间消耗，即采用简单双口RAM 预读操作隐藏蝶形单元流水延时和访存延时，采用3组RAM乒乓操作来隐藏数据搬运的时 间消耗；此外，它还采用采用旋转因子压缩算法压缩外部旋转因子ROM存储资源。

所述处理器集成一维和二维混合FFT处理模式，在进行32点到8K点的任意2ⁿ点32位 单精度浮点数的FFT或IFFT运算时采用一维FFT运算，在进行16K点32位单精度浮点数 的FFT或IFFT运算时采用二维FFT运算。

所述处理器按如下一维FFT运算模式进行32点到8K点的任意2ⁿ点32位单精度浮点数 的FFT或IFFT运算：2组4*2K片上数据存储器进行乒乓操作，通过控制器依次配置为操作 数存储器组和运算结果存储器组，FFT运算单元通过内存储控制单元和多路选择器同时访问 操作数存储器组和运算结果存储器组，每个时钟周期从操作数存储器组并行读取4个操作数 进行FFT或IFFT运算，同时产生4个中间运算结果写入运算结果存储器组；FFT运算完一 级，2组4*2K片上数据存储器进行一次乒乓操作，操作数存储器组和运算结果存储器组相互 切换；经过n级乒乓操作获得最终结果数据；

所述处理器按如下二维FFT运算模式进行16K点32位单精度浮点数的FFT或IFFT运 算：两组4*2K片上数据存储器作为16K缓存，组成128*128的矩阵；3组4*32临时储存器 进行内外乒乓操作，通过控制器依次配置为操作数存储器组、运算结果存储器组及数据传输 存储器组；

所述数据传输单元通过外存储控制单元及多路选择器，每个时钟周期并行读取16K缓存 矩阵第一列或行2个原始数据，再通过内存储控制单元写入数据传输存储器组，完成第一列 或行128个数据传输；

第一列或行数据传输完成后，操作数存储器组、运算结果存储器组及数据传输存储器组 进行一次外乒乓操作，将数据传输存储器组变为操作数存储器组，将操作数存储器组变为运 算结果存储器组，将运算结果存储器组变为数据传输存储器组；数据传输单元读取第二列或 行原始数据，并写入数据传输存储器组，在数据传输的同时，FFT运算单元每个时钟周期从 操作数存储器组并行读取4个操作数，产生4个结果数据写进运算结果存储器组；操作数存 储器组与运算结果存储器组进行内乒乓操作完成第一列或行FFT或IFFT运算；

在上一列或行FFT或IFFT运算完成时，3组4*32临时储存器再进行一次外乒乓操作， 相互切换；所述数据传输单元通过外存储控制单元每个时钟周期并行读取2个上一列或行FFT 运算结果，再通过外存储控制单元及多路选择器写入16K缓存矩阵相应的列或行；然后所述 数据传输单元通过外存储控制单元及多路选择器，每个时钟周期并行读取下一列或行2个原 始数据，再通过内存储控制单元写入数据传输存储器组；在数据传输的同时，FFT运算单元 对操作数存储器组与运算结果存储器组进行内乒乓操作完成本列或行FFT或IFFT运算；下 一时刻，操作数存储器组、运算结果存储器组及数据传输存储器组进行一次外乒乓操作，直 至完成所有一维列或行FFT或IFFT运算；

控制器协调数据传输单元和FFT运算单元进行有序工作，依次完成所有组列或行的FFT 或IFFT运算，最终完成16K点32位单精度浮点数的FFT或IFFT运算。

所述一维FFT运算模式须满足式1：

M_d+C_d<n/8      (1)

所述二维FFT运算模式须满足式2：

M_d+C_d<min{L,C}/8      (2)

式中：M_d为访存延时；C_d为蝶形单元流水延时；n为FFT的点数，L为行数，C为列数。

与已有技术相比，本发明的有益效果体现在：

1、本发明FFT处理器采用一维二维混合的模式对数据进行FFT或IFFT运算，综合考虑 了FFT运算速度、存储资源消耗以及灵活性，集成了一维FFT处理器运算速度快及二维FFT 处理器存储资源少的优点，达到了速度和资源之间的均衡；

2、本发明处理器采取两种方法来隐藏数据路径上的时间消耗，即采用简单双口RAM预 读操作隐藏蝶形单元流水延时和访存延时，采用3组4*32临时储存器进行乒乓操作来隐藏数 据搬运的时间消耗，更有效的提高了速度；此外，它还采用旋转因子压缩算法压缩外部旋转 因子ROM存储资源；

3、本发明处理器采用一维FFT运算模式进行32点到8K点的任意2ⁿ点32位单精度浮 点数的FFT或IFFT运算，采用二维FFT运算模式进行16K点32位单精度浮点数的FFT或 IFFT运算的固定配置模式，在保证较高运算速度的同时，实现硬件资源的最小化；

4、本发明处理器的FFT运算单元采用2个蝶形单元并行操作，完成32点到16K点的任 意2ⁿ点32位单精度浮点数的FFT或IFFT运算，有效的提升了运算速度。

附图说明

图1为现有一维FFT结构示意图；

图2为现有二维FFT结构示意图；

图3为本发明1-D/2-D混合架构FFT处理器的结构示意图；

图4为本发明1-D/2-D混合架构FFT处理器的一维FFT运算模式流程图；

图5为本发明1-D/2-D混合架构FFT处理器的二维FFT运算模式流程图；

图6为预读取操作流水线示意图；

图7为FFT运算拓扑结构图；

图8为FFT相对加速比线性曲线；

图9为FFT单位存储资源相对加速比线性曲线。

具体实施例

如图3所示，本实施例1-D/2-D混合架构FFT处理器包括控制器、存储系统、数据交换 网络、数据传输单元及FFT运算单元；

控制器用于控制数据传输单元和FFT运算单元；

存储系统包括2组4*2K片上数据存储器(Memory0/1_x)和3组4*32临时储存器 (Memory2/3/4_x)，2组4*2K片上数据存储器和3组4*32临时储存器采用简单双口RAM； 根据16K=128*128，二维FFT处理模式需要处理的最大一维FFT为128点，为了节省存储资 源，FFT处理器采用3组4*32的临时存储器乒乓操作完成行列一维FFT运算。

数据交换网络包括内存储控制单元、外存储控制单元及多路选择器；

内存储控制单元用于对2组4*2K片上数据存储器和3组4*32临时储存器进行灵活的地 址分配和管理以满足FFT/IFFT计算过程中并行数据读取和存储的要求，避免地址冲突的产生， 并为FFT运算单元和数据传输单元访问5组数据存储器提供统一接口，使每一个数据端口（包 括操作数端口、传输数据端口、运算结果端口）都能对各块片上存储器的任意存储单元进行 访存，而无需关心该存储单元属于哪一块片上存储器；

外存储控制单元为数据传输单元访问2组4*2K片上数据存储器提供统一接口；

多路选择器用于选择内存储控制单元或外存储控制单元进行访问2组4*2K片上数据存 储器；

数据传输单元用于完成2组4*2K片上数据存储器和3组4*32临时储存器之间的数据传 输，实现实时行或列数据搬运，为FFT运算单元提供将要进行的行或列FFT运算操作数，并 把FFT运算单元计算结果传回2组4*2K片上数据存储器中；

FFT运算单元用于实现数据的FFT或IFFT运算。FFT运算单元包括内部集成读写地址 生成单元、2个蝶形运算单元和旋转因子生成器。

处理器采用基-2算法和固定寻址结构；处理器采取两种方法来隐藏数据路径上的时间消 耗，即采用简单双口RAM预读操作隐藏蝶形单元流水延时和访存延时，采用3组RAM乒乓 操作来隐藏数据搬运的时间消耗；此外，它还采用旋转因子压缩算法压缩外部旋转因子ROM 存储资源。

处理器集成一维和二维混合FFT处理模式，在进行32点到8K点的任意2ⁿ点32位单精 度浮点数的FFT或IFFT运算时采用一维FFT运算，在进行16K点32位单精度浮点数的FFT 或IFFT运算时采用二维FFT运算。

如图4所示，处理器按如下一维FFT运算模式进行32点到8K点的任意2ⁿ点32位单精 度浮点数的FFT或IFFT运算：2组4*2K片上数据存储器进行乒乓操作，通过控制器依次配 置为操作数存储器组和运算结果存储器组，FFT运算单元通过内存储控制单元和多路选择器 同时访问操作数存储器组和运算结果存储器组，每个时钟周期从操作数存储器组并行读取4 个操作数进行FFT或IFFT运算，同时产生4个中间运算结果写入运算结果存储器组；FFT 运算完一级，2组4*2K片上数据存储器进行一次乒乓操作，操作数存储器组和运算结果存储 器组相互切换；经过n级乒乓操作获得最终结果数据；

如图5所示，处理器按如下二维FFT运算模式进行16K点32位单精度浮点数的FFT或 IFFT运算：两组4*2K片上数据存储器作为16K缓存，组成128*128的矩阵；3组4*32临时 储存器进行内外乒乓操作，通过控制器依次配置为操作数存储器组、运算结果存储器组及数 据传输存储器组；

数据传输单元通过外存储控制单元及多路选择器，每个时钟周期并行读取16K缓存矩阵 第一列或行2个原始数据，再通过内存储控制单元写入数据传输存储器组，完成第一列或行 128个数据传输；

第一列或行数据传输完成后，操作数存储器组、运算结果存储器组及数据传输存储器组 进行一次外乒乓操作，将数据传输存储器组变为操作数存储器组，将操作数存储器组变为运 算结果存储器组，将运算结果存储器组变为数据传输存储器组；数据传输单元读取第二列或 行原始数据，并写入数据传输存储器组，在数据传输的同时，FFT运算单元每个时钟周期从 操作数存储器组并行读取4个操作数，产生4个结果数据写进运算结果存储器组；操作数存 储器组与运算结果存储器组进行内乒乓操作完成第一列或行FFT或IFFT运算；

在上一列或行FFT或IFFT运算完成时，3组4*32临时储存器再进行一次外乒乓操作， 相互切换；数据传输单元通过外存储控制单元每个时钟周期并行读取2个上一列或行FFT运 算结果，再通过外存储控制单元及多路选择器写入16K缓存矩阵相应的列或行；然后数据传 输单元通过外存储控制单元及多路选择器，每个时钟周期并行读取下一列或行2个原始数据， 再通过内存储控制单元写入数据传输存储器组；在数据传输的同时，FFT运算单元对操作数 存储器组与运算结果存储器组进行内乒乓操作完成本列或行FFT或IFFT运算；下一时刻， 操作数存储器组、运算结果存储器组及数据传输存储器组进行一次外乒乓操作，直至完成所 有一维列或行FFT或IFFT运算；

控制器协调数据传输单元和FFT运算单元进行有序工作，依次完成所有组列或行的FFT 或IFFT运算，最终完成16K点32位单精度浮点数的FFT或IFFT运算。

FFT运算单元对于N点FFT运算需要运行log₂N级，每一级都有蝶形单元流水延时(C_d) 和访存延时(M_d).那么，一维FFT运算模式计算N点FFT总延时周期为：

Total_delay＝log₂N(M_d+C_d)        (3)

二维FFT运算模式计算N点FFT总延时周期为：

Total_delay＝(Clog₂L+Llog₂C)(M_d+C_d)    (4)

其中：M_d为访存延时；C_d为蝶形单元流水延时。我们采取预读取操作减少这些由于延时 带来的额外时钟消耗。

如图6所示，该FFT处理器采用简单双端口预读取操作隐藏蝶形单元流水延迟和访存延 迟。FFT读取一级操作数完成后，还需等待(M_d+C_d)时钟周期才能将本级运算结果全部写进 目的存储器。预读取操作提前(M_d+C_d)时钟周期读取下一级操作数，即从本级目的存储器另 一个端口读取操作数送入蝶形单元。必须保证读取的下一级操作数已经写进目的存储器，否 则FFT运算结果出错。

FFT处理器采用基-2DIT-FFT算法，固定寻址架构，该运算结构是倒序输入，顺序输出， 拓扑结构如图7所示。

原始运算数据按照一定的规律分别存入存储系统中的一组4块Memory。蝶形运算时， 分别从每个Memory中读取一个操作数，送入运算单元，生成的4个结果数分别送入另一组 4块Memory中。对于一个N点的FFT或IFFT，地址编址方式如下表所示：

表1.无冲突地址编址

根据FFT运算拓扑结构和无冲突地址编址方式，知FFT运算数据的读取和存储过程如下 表所示：

表2.数据读取地址序列

表3.数据存储地址序列

根据运算数据的读取和存储规律，本级运算结果完全写进目的存储器时，从下一级预读 取操作数少于N/2就可保证读取的下一级操作数已经写进存储器。

所述一维FFT运算模式须满足式1：

M_d+C_d<n/8    (1)

所述二维FFT运算模式须满足式2：

M_d+C_d<min{L,C}/8      (2)

本设计中M_d=3；C_d=12，由公式得到n>120或min{L,C}>120。一维FFT运算模式处理小 于128点FFT，不满足公式(1)；二维FFT运算模式处理小于16K点的FFT，不满足公式(2)， 不能采用预读取操作隐藏蝶形单元流水延迟，导致运算速度显著增加。

传统的1-D FFT处理器具有快处理速度，但数据存储资源较大。2-D FFT处理器由于额 外时间消耗，运算速度较慢，但数据存储资源大大压缩。

本发明1-D/2-D混合架构FFT处理器综合二者优点，具有优异的处理速度和较少的存储 资源。详细比较见表4。1-D FFT运算模式处理128到8K点FFT采用预读取操作隐藏蝶形单 元的流水延时和访存延时，运算时钟周期比理论值(T-V)增加16个时钟周期，但是进行小于 128点的FFT运算，采用预读取操作无法隐藏蝶形单元的流水延时和访存延时，所以32点和 64点FFT运算时间比理论值有所增加。2-D FFT运算模式进行16K以下的FFT，采用预读 取操作无法隐藏蝶形单元的流水延时和访存延时，故运算时间与理论值相比较显著增加。

表4FFT运算时钟周期对比表

根据各点FFT运算时钟周期与相应点理论值的比值，我们可以绘出FFT相对加速比线性 曲线，如图8所示。一维FFT处理器和混合架构FFT处理器有理想的处理速度，并且它们的 相对加速比线性曲线几乎相互重合。当进行128到16K点FFT运算时，二者的相对加速比系 数均接近于1。在二维FFT处理器中，能处理的一维FFT最大点数为1K。若FFT点数少 于2K，N被配置为1行N列的矩阵形式，可用二维形式同时进行多组一维FFT运算，否则 N将被配置为L行和C列的矩阵形式。由此导致二维FFT处理器相对加速度比线性曲线在 2K点出现一个转折点。二维FFT处理器运算速度较慢，但当进行大点数16K点FFT运算时 它的运算速度接近理论速度。三组相对加速比线性曲线相交于16K点。

上述三款FFT处理器均已在Virtex-6XC6VLX760FPGA上实现，表5给出详细比较，可 以看出混合FFT处理器达到高速与资源的平衡。

表5FFT综合资源与最大频率对比表

通过FFT处理器的相对加速度比系数除以块RAM的相应值并进行归一化，我们可以绘 出FFT单位存储资源的相对加速比线性曲线，如该图9所示。我们可以看到，与一维FFT处 理器和二维FFT处理器相比，混合架构的FFT处理器有更高的单位存储资源相对加速比系数。 但是在特殊点16K点处，2-D FFT处理器的单位存储资源相对加速比系数比混合架构FFT处 理器的大，并接近于1。整体而言，当进行任意2ⁿ点(n=5,6…14)单精度浮点数FFT或IFFT 运算时，混合架构的FFT处理器具有更高的性能资源比。