无线通信系统-FFT与信道译码VLSI设计 课件第2 章基于并行流水线的FFT计算方法及VLSI结构

第2章基于并行流水线的FFT计算方法及VLSI结构2.1面向硬件实现的radix-2k

FFT算法原理2.2FFT串行流水线计算结构2.3FFT并行流水线计算方法2.4FFT混合抽取多路延迟反馈VLSI结构2.5理论分析与硬件测试本章小结

2.1面向硬件实现的radix-2kFFT算法原理

对于输入序列xn

，其

点FFT运算表示为：其中n和k分别表示时间与频率次序。系数

被称为旋转因子，其表达式为

传统的Cooley-Turkey按频率抽取的radix-2FFT算法将(2.1)按照奇偶频率划分为两部分，即

利用混合基算法可以将

进一步分解为：

图2.1以16点FFT计算为例，分别给出了radix-22算法和radix-2算法下的信号流图，其中非平凡旋转因子的数量与分布很好地印证了结论。

2.2FFT串行流水线计算结构

串行流水线结构是中低速率FFT计算单元的常用VLSI实现方式，例如在Xilinx公司提供的FFTIP核中，串行流水线就是一类典型的硬件结构。串行流水线结构易于根据FFT计算长度的不同进行裁剪或扩展，计算吞吐量与工作时钟相同，其顶层如图2.2所示，可以分为FFT计算电路、旋转因子存储电路和数据排序电路三部分。

图2.2FFT串行流水线计算结构顶层方案

流水线计算单元具有两种典型的电路结构：延迟反馈结构和延迟换向结构。利用这些结构，将数据按正确次序两两送入蝶形运算单元进行计算。另一方面，旋转因子存储及数据排序单元的设计方案，直接影响着串行流水线计算结构的存储开销。下面首先说明流水线计算单元VLSI结构和工作方式，然后给出数据排序单元和旋转因子存储单元的优化设计方案。

2.2.1延迟反馈VLSI结构

1984年，Wold首次提出了延迟反馈（Single-pathDelayFeedback，SDF）的串行流水线FFT计算结构。SDF结构中的反馈连接使得每一级运算单元的输入和输出数据能够共用同一存储器，这保证了整个FFT计算模块对存储资源的最小消耗。延迟反馈VLSI结构示意图如图2.3所示。

图2.3延迟反馈VLSI结构示意图（以16点FFT计算为例）

一般地对于N点FFT运算，延迟反馈结构的典型电路特征为：

从信号输入端开始，在第n级（n=1,2,...,log2N）蝶形运算单元配置长度为N/2n的移位寄存器，因此延迟反馈结构的寄存器开销总计N-1；

移位寄存器与蝶形运算单元之间存在数据反馈，即移位寄存器的输出数据作为蝶形运算单元的输入，并且蝶形运算单元的输出数据作为因为寄存器的输入。

在SDF结构中，通过控制数据选择器调整数据流向，第n级蝶形运算单元以N/2n-1个输入数据为执行周期，循环执行以下步骤：

步骤1：当第1至第N/2n个有效数据输入时，将其依次送入移位寄存器，同时移位寄存器中缓存的有效数据依次移出，乘以相应的旋转因子后送至下一级蝶形运算单元；

步骤2：当第N/2n+1至第N/2n-1个有效数据输入时，与移位寄存器移出数据共同进行radix-2蝶形运算，其中相加结果乘以相应的旋转因子后送至下一级蝶形运算单元，相减结果反馈至移位寄存器缓存。

2.2.2延迟换向VLSI结构

将SDF流水线结构的反馈环打开，并把运算单元的输入和输出数据缓存在不同存储器中，这样就得到了延迟换向（Multi-pathDelayCommutator，MDC）的FFT流水线结构。延迟换向VLSI结构示意图如图2.4所示，对于N点FFT运算，其典型电路特征为：

在第1级蝶形运算单元的输入端，利用长度为N/2的移位寄存器缓存第1至第N/2个输入数据，缓存数据与第N/2+1至第N个输入数据组成2路并行数据流送入第1级蝶形运算单元；在第2级至第log2N级蝶形运算单元的输入端配置双路延迟换向器，用于对前一级蝶形运算单元的并行输出数据进行次序调整，其中第n级（n=1,2,...,log2N）蝶形运算单元输入端采用的延迟换向器集成了2组长度为N/2n的移位寄存器；因此延迟换向结构的寄存器开销总计3N/2-2

；

从第1级蝶形运算单元的输入开始，数据流以两路并行的方式在流水线内单向流动，不存在反馈环路。

图2.4延迟换向VLSI结构及数据次序变换示意图（以16点FFT计算为例）

在MDC结构中，蝶形运算单元仅需对输入并行数据进行求和与相减运算，然后并行输出计算结果即可，对数据流的调整通过蝶形运算单元输入端的延迟换向器来实现。具体而言，第n级蝶形运算单元输入端配置的延迟换向器，以N/2n-1个上支路或下支路输入数据为执行周期，循环执行以下步骤：

步骤1：配置延迟换向器中的数据选择器，将上支路第1至第N/2n个有效数据写入上支路移位寄存器，将下支路第1至第N/2n个有效数据写入下支路移位寄存器；与此同时，将两个移位寄存器移出的数据送至下一级蝶形运算单元；

步骤2：调整数据选择器，将上支路第N/2n+1至第N/2n-1个有效数据通过下支路输出端口送至下一级蝶形运算单元；将下支路第N/2n+1至第N/2n-1个有效数据写入下支路移位寄存器，同时其移出数据作为上支路移位寄存器输入；上支路移位寄存器移出数据送至下一级蝶形运算单元；

2.2.3数据排序单元VLSI结构

在FFT计算模块内，数据排序单元用于实现数据在自然序和倒位序之间的转换。为了对长度为

的数据序列进行次序调整，传统方案首先利用存储深度为M的RAM对全部数据进行缓存，然后再生成读地址将数据以新次序从RAM中读出。为了能够处理连续数据流，用于数据缓存的RAM需要构建成乒乓操作结构，此时的数据存储开销将达到2M

；如果RAM单元能够以双端口的方式同时支持读写操作，存储器消耗可以减小至M，而控制复杂度会相应提升。为了确定出数据排序单元的最小存储开销，首先需要对其中的数据进行寿命分析。

图2.5以M=16为例给出了倒位序排序的数据寿命分析图，其中左侧是时钟周期标号；数据的寿命周期在图中用粗实线表示，它起始于数据产生或者输入的时刻，到数据执行完全部相关运算或输出时刻结束；特别地当数据产生和终止于同一时刻时，数据的寿命周期为0，在图中标记为“”；图右侧统计了在同一时刻的有效数据个数，需要注意每个数据在其产生时刻被看作是无效数据；有效数据个数在全部时刻的最大值即为最小存储开销。从分析结果不难发现M=16的倒位序数据排序所对应的最小存储开销为9，这低于传统方案中16或32个数据的缓存需求。

图2.4延迟换向VLSI结构及数据次序变换示意图（以16点FFT计算为例）

图2.6数据排序单元最小存储器消耗Lmin的物理意义

图2.7达到最小存储器消耗的流水线结构数据排序单元

将M=2q代入(2.6)不难验证L=Lmin，这保证了所提出的次序变换方法能够最高效地利用存储资源。在硬件结构方面，整个数据排序单元可以用一个nR级流水线来实现，其中流水线的第i级执行第i轮排序操作。如图2.8所示，流水线的第

级由一个长度为Lmin(i)的移位寄存器和共用同一信号ci的两个数据选择器构成。

图2.8倒位序次序变换方案的硬件实现结构

当ci=1时，第i级当前输入数据被直接送至第i+1级；反之若ci=0，当前输入数据被送至移位寄存器进行缓存，同时移位寄存器的输出被送至下一级。为了产生流水线每一级数据选择器的控制信号，需要在流水线输入端设置一个与输入数据同步的q比特的计数器bq-1,...,b1b0，那么ci可以按照如下方式产生：

2.2.4旋转因子优化存储结构

在FFT计算过程中，中间结果需要乘以相应的旋转因子以实现数据旋转。旋转因子的非线性使其实时求解具有较高的计算复杂度，相比之下采用查找表的方式预先将离线计算出的旋转因子存储在FFT计算模块内是一种更常用的做法，不过这也带来了额外的存储资源消耗。利用正余弦函数的对称特性，旋转因子

所对应的查找表只要涵盖

相位范围内的取值即可，位于其他相位范围的旋转因子可以在此基础上通过改变实虚部符号以及交换实虚部数值来产生，这一变换规则在表2.1中进行了具体描述。

以旋转因子实部的压缩存储为例，图2.9对上面介绍的数据压缩过程进行了描述。图2.9旋转因子的压缩存储（以数据实部压缩为示意）

在上述方案中，参数λ1的最优值λ1*需要最小化查找表的存储资源消耗，即

图2.10不同参数配置下旋转因子压缩存储的最优分组长度

利用压缩的数据正确恢复旋转因子的步骤和硬件结构如图2.11所示。图2.11利用压缩存储的数据恢复旋转因子

2.3FFT并行流水线计算方法

一般地，N=2u点的FFT和IFFT运算可以分别定义为下面的形式：

图2.12FFT并行计算的顶层结构框图

2.4FFT混合抽取多路延迟反馈VLSI结构

2.4.1基于折叠变换的延迟反馈结构分析

图2.13利用折叠变换将DIFFFT数据流图转化为SDF流水线结构

图2.13利用折叠变换将DIFFFT数据流图转化为SDF流水线结构

图2.13利用折叠变换将DIFFFT数据流图转化为SDF流水线结构

图2.14利用折叠变换将DITFFT数据流图转化为SDF流水线结构

图2.14利用折叠变换将DITFFT数据流图转化为SDF流水线结构

图2.14利用折叠变换将DITFFT数据流图转化为SDF流水线结构

2.4.2延迟反馈结构计算调度优化

(2.26)和(2.29)表明，无论采用DIF算法或DIT算法构建SDF流水线，折叠矩阵中包含的空操作都将使得计算单元在某些时隙处于空闲状态，这导致整个FFT计算模块对计算资源的利用率只能达到50%左右。为解决这一问题，需要用有效运算将折叠矩阵中的空操作进行填充，这就涉及到了对折叠矩阵进行变换。从本质上讲，折叠矩阵的变换实际上是对相应数据流图中的运算操作进行重新调度的过程，又因为折叠矩阵形式与具体电路结构相对应，在变换过程中能够实现对电路结构的相应调整以使之适应新的运算操作调度方式。具体而言，我们通过如下方式对SDF流水线的折叠矩阵进行变换以提升计算资源的使用效率：

图2.15能同时执行DITFFT和DIFFFT的SDF流水线结构

图2.15中DIFSDF流水线与DITSDF流水线的结合将改变计算单元的底层结构。根据原计算单元对复数乘法器利用率的不同，新计算单元将具有两种硬件实现方式，如图2.16所示。

图2.16用于同时执行DITFFT和DIFFFT的SDF计算单元结构

图2.16用于同时执行DITFFT和DIFFFT的SDF计算单元结构

2.4.3混合抽取多路延迟反馈VLSI结构设计

对于图2.12给出的FFT并行计算顶层结构，用于执行横向DFT运算的

条SDF流水线可以利用前面描述的运算操作调度方法进行优化设计，这便引出了M2DF并行流水线结构。我们首先以

的radix-2M2DF结构（简记为R2M2DF结构）为例来对硬件设计方案进行说明。如图2.17所示。

图2.17R2M2DF并行流水线结构（N=32,P=2）

2.5理论分析与硬件测试

2.5.1并行流水线FFT结构的资源消耗估计与比较在流水线FFT计算结构中，蝶形运算单元的构建需要用到复数加法器，而数据旋转则依靠复数乘法器来完成。复数乘法器可以进一步分为通用复数乘法器和常数复数乘法器，前者可以基于任意旋转因子来旋转数据，而后者只适用于某些特定的旋转因子，如实部与虚部模值相同的旋转因子

或其他给定的旋转因子。

另一方面，流水线FFT计算模块还需要利用存储器来缓存中间计算结果，存储旋转因子以及调整数据次序。用于缓存中间计算结果的存储器通常以移位寄存器的形式分布在流水线的每一级，它们在数据选择器的控制下将数据按正确次序送至运算单元完成计算。存储旋转因子的存储器以查找表的形式集成在FFT计算模块内，它保证了计算过程中旋转因子的实时获取。

表2.2对不同并行度下MDF结构、M2DF结构以及MDC结构的硬件资源消耗与计算时延进行了估计，其中FFT计算模块的输入和输出数据流分别具有(2.19)中

和

的形式，计算时延被定义为FFT计算模块的首组输入数据和首组输出数据之间的时钟周期个数。

2.5.2M2DF结构的硬件实现与测试

我们在XilinxVirtex6FPGA上对本章设计的M2DF结构和其他流水线FFT计算结构进行了硬件实现，其中FPGA型号为XC6VLX240T-3FF784，所用的编译器版本为ISE12.4。

在不同配置方式下各流水线FFT计算结构的硬件资源开销和计算时延、吞吐量等性能记录在了表2.3中

以radix-和radix-FFT算法对应的应用场景为例，图2.20统计了不同流水线FFT计算结构的算术运算与逻辑操作对sliceLUTs的消耗情况。整体来看，构建M2DF结构所需的sliceLUTs最少，MDC结构次之，而MDF结构消耗的sliceLUTs最多。此外可以发现三种流水线结构均在蝶形运算单元的实现上消耗了大量的sliceLUTs资源，由于MDF结构和其他两种方案相比需要更多的加法器来完成运算，因而其对sliceLUTs的需求量也更大。M2DF结构的计算单元需要同时对DIT数据流的DIF数据流进行控制，这使其在数据流控制方面消耗的sliceLUTs略高于MDC结构和MDF结构。MDC结构的数据流排序比其他两种方案更为复杂，因此在这一操作上利用到的sliceLUTs最多。

图2.20FFT计算模块内的不同操作对sliceLUTs消耗情况统计

图2.20FFT计算模块内的不同操作对sliceLUTs消耗情况统计

不同流水线FFT计算结构的存储资源消耗在表2.3中通过所占用的块RAM个数来体现，需要指出的是在实现过程中所有方案都采用的相同的旋转因子存储方法，因此块RAM个数的区别主要来自于流水线结构设计。前面在对表2.2中的数据进行分析时指出，MDF结构和M2DF结构能够比MDC结构更为有效地利用存储资源，这一结论从表2.3的实验结果中也得到了很好的印证。另一方面，我们发现