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

第2章基于并行流水线的FFT计算方法及VLSI结构;

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

;

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

利用混合基算法可以将进一步分解为：;

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

;

;

2.2FFT串行流水线计算结构;

;

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

2.2.1延迟反馈VLSI结构

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

;

一般地对于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级蝶形运算单元的输入开始，数据流以两路并行的方式在流水线内单向流动，不存在反馈环路。

;

;

在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对全部数据进行缓存，