FFT原理

,

,

将数据进行奇偶分组可以得到

由于：

所以：

对于：

K=0,1,…N/2-1

所以：

数据流图

FFT设计描述

设计框图

蝶形运算

为了减少资源使用，模块仅包含一个基2碟形运算模块，通过分时复用完成FFT运算，蝶形运算模块框图如下：

由于每次蝶形运算定点位宽都会增加一位，因此为了统一蝶形运算的位宽，在输出对数据除2.即公式为

y1 = (x1+x2*w)/2;

y2 = (x1-x2*w)/2;

控制状态机

1. 根据FFT判断数据输入是否结束，没有结束则将RAM的输入选到输入接口，否则选到蝶形运算单元。
2. 将RAM的数据根据地址计算模块的地址依次读出送到蝶形运算单元。
3. 由于蝶形运算的延迟，判断蝶形运算是否完成，完成则到下一步。
4. 判断FFT运算是否完成，没有则进行下一次蝶形运算。完成则从RAM中依次读出数据。

地址产生模块

地址产生模块根据当前运行状态计算如何从RAM以及相位旋转因子ROM中读出数据，地址产生算法如下:

定义一下4个变量：

1. M=log2(NFFT)
2. fft-stage: 蝶形运算stage索引
3. n:  蝶形运算分组索引 n
4. b: 蝶形运算索引 b

地址产生公式如下：

x1Idx = b + n*2^(M-fft_stage);

x2Idx = x1Idx + 2^(M-fft_stage-1);

wIdx = bitswap(2*n,M);

由于相位旋转的地址固定为0-4095，因此需要对原始地址进行重新映射。

wIdx = bitswap(2*n,M)*2^(12-M);

缓存RAM

缓存RAM为一个32x4K的的简单双口RAM。

相位旋转因子ROM

为了节省空间，只需存储1/4个周期的数据，其他数据可以通过计算算出。因此只需要32x1K的ROM，但是为了简化地址计算，地址计算模块仍按给出正常地址，ROM模块内部根据当前地址完成相应的地址换算和数据操作。

输出延迟

由于内部仅采用1个基2蝶形运算模块，因此输出延迟根据NFFT点数不同而有差异，输出延迟的计算由FFT最后1个输入结束开始，到第一个输出结束。计算公式如下：

单位为clk周期。