- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

【 FPGA 】16点并行DIT FFT的实现

李锐博恩发表于 2021/07/15 04:13:27 2021/07/15

【摘要】目录整体架构介绍旋转因子介绍代码文件结构重点难点易错点整体架构介绍 16点并行FFT分为4级蝶形运算，每一级蝶形运算有一个基本的蝶形单元：如下是16点DIT FFT的数据流图：可见，第0级蝶形运算的输入的顺序是： x(0)、x(8)、x(4)、x(12)、x(2)、x(10)、x(6)、x(14)、x(1)、x(9)、x(5)、x(1...

整体架构介绍

16点并行FFT分为4级蝶形运算，每一级蝶形运算有一个基本的蝶形单元：

如下是16点DIT FFT的数据流图：

可见，第0级蝶形运算的输入的顺序是：

x(0)、x(8)、x(4)、x(12)、x(2)、x(10)、x(6)、x(14)、x(1)、x(9)、x(5)、x(13)、x(3)、x(11)、x(7)、x(15)；

只有这样排列输入，才能得到最终顺序的输出：

x(0)、x(1)、x(2)、x(3)、x(4)、x(5)、x(6)、x(7)、x(8)、x(9)、x(10)、x(11)、x(12)、x(13)、x(14)、x(15)；

旋转因子介绍

蝶形因子通用的表示为： $W_{^{N}}^{k}$ ，从DIT FFT的数据流图可以看出，第0级蝶形运算的旋转因子为 $W_{^{2}}^{0}$ ；第1级蝶形运算的旋转因子为： $W_{^{4}}^{0}，W_{^{4}}^{1}，$ ， $W_{^{4}}^{1}$ ；第2级蝶形运算的蝶形因子为： $W_{^{8}}^{0}$ ， $W_{^{8}}^{1}$ ， $W_{^{8}}^{2}$ ， $W_{^{8}}^{3}$ ；第3级蝶形运算的蝶形因子为： $W_{^{16}}^{0}$ ， $W_{^{16}}^{1}$ ， $W_{^{16}}^{2}$ ， $W_{^{16}}^{3}$ ， $W_{^{16}}^{4}$ ， $W_{^{16}}^{5}$ ， $W_{^{16}}^{6}$ ， $W_{^{16}}^{7}$ 。

那么这些蝶形因子在Verilog中如何表示呢？

$W_{^{N}}^{k} = e^{-j\frac{2\pi}{N}k}$ ，这样的话：

$W_{^{N}}^{0} = 1$ ；

$W_{^{N}}^{1} = e^{-j\frac{2\pi}{N}} = cos(\frac{2\pi}{N}) - jsin(\frac{2\pi}{N})$ ；

$W_{^{N}}^{2} = e^{-j\frac{4\pi}{N}} = cos(\frac{4\pi}{N}) - jsin(\frac{4\pi}{N})$ ；

$W_{^{N}}^{3} = e^{-j\frac{6\pi}{N}} = cos(\frac{6\pi}{N}) - jsin(\frac{6\pi}{N})$ ；

$W_{^{N}}^{4} = e^{-j\frac{8\pi}{N}} = cos(\frac{8\pi}{N}) - jsin(\frac{8\pi}{N})$ ；

$W_{^{N}}^{5} = e^{-j\frac{10\pi}{N}} = cos(\frac{10\pi}{N}) - jsin(\frac{10\pi}{N})$ ；

$W_{^{N}}^{6} = e^{-j\frac{12\pi}{N}} = cos(\frac{12\pi}{N}) - jsin(\frac{12\pi}{N})$ ；

$W_{^{N}}^{7} = e^{-j\frac{14\pi}{N}} = cos(\frac{14\pi}{N}) - jsin(\frac{14\pi}{N})$ .

如此：

第0级蝶形因子：

$W_{^{2}}^{0} = 1$ ；

第1级蝶形因子：

$W_{^{4}}^{0} = 1$ ；

$W_{^{4}}^{1} = e^{-j\frac{2\pi}{4}} = cos(\frac{\pi}{2}) - jsin(\frac{\pi}{2})=-j$ ;

第2级蝶形因子：

$W_{^{8}}^{0} = 1$ ；

$W_{^{8}}^{1} = e^{-j\frac{2\pi}{8}} = cos(\frac{\pi}{4}) - jsin(\frac{\pi}{4}) = \sqrt{2}/2 - j\sqrt{2}/2=0.7071-j0.7071$ ；

$W_{^{8}}^{2} = e^{-j\frac{4\pi}{8}} = cos(\frac{\pi}{2}) - jsin(\frac{\pi}{2}) = -j$ ；

$W_{^{8}}^{3} = e^{-j\frac{6\pi}{8}} = cos(\frac{3\pi}{4}) - jsin(\frac{3\pi}{4})=-0.7071-j0.7071$ ;

第3级蝶形因子：

$W_{^{16}}^{0} = 1$ ；

$W_{^{16}}^{1} = e^{-j\frac{2\pi}{16}} = cos(\frac{\pi}{8}) - jsin(\frac{\pi}{8})= 0.9239 - j 0.3827$ ；

$W_{^{16}}^{2} = e^{-j\frac{4\pi}{16}} = cos(\frac{\pi}{4}) - jsin(\frac{\pi}{4})=0.7071-j0.7071$ ；

$W_{^{16}}^{3} = e^{-j\frac{6\pi}{16}} = cos(\frac{3\pi}{8}) - jsin(\frac{3\pi}{8})=0.3827-j0.9239$ ；

$W_{^{16}}^{4} = e^{-j\frac{8\pi}{16}} = cos(\frac{\pi}{2}) - jsin(\frac{\pi}{2})=-j$ ；

$W_{^{16}}^{5} = ^{-j\frac{10\pi}{16}} = cos(\frac{5\pi}{8}) - jsin(\frac{5\pi}{8})= -0.3827-j0.9239$ ；

$W_{^{16}}^{6} = e^{-j\frac{12\pi}{16}} = cos(\frac{3\pi}{4}) - jsin(\frac{3\pi}{4}) =-0.7071-j0.7071$ ；

$W_{^{16}}^{7} = e^{-j\frac{14\pi}{16}} = cos(\frac{7\pi}{8}) - jsin(\frac{7\pi}{8})=-0.9239-j0.3827$ ;

在Verilog设计中，蝶形因子肯定要使用parameter来定义，定义成参数，如何去做呢？

FPGA擅长进行定点数的运算，所以，我们要想办法将上述蝶形因子进行扩大，例如扩大512倍，得到：

第0级蝶形因子：

$W_{^{2}}^{0} = 512$ ；

第1级蝶形因子：

$W_{^{4}}^{0} = 512$ ；

$W_{^{4}}^{1} =-j512$ ;

第2级蝶形因子：

$W_{^{8}}^{0} = 512$ ；

$W_{^{8}}^{1} = 364-j364$ ；

$W_{^{8}}^{2} = -j512$ ；

$W_{^{8}}^{3} =-364-j364$ ;

第3级蝶形因子：

$W_{^{16}}^{0} = 512$ ；

$W_{^{16}}^{1} =471-j195$ ；

$W_{^{16}}^{2} = 364-j364$ ；

$W_{^{16}}^{3} = 195-j471$ ；

$W_{^{16}}^{4} =-j512$ ；

$W_{^{16}}^{5} =-195-j471$ ；

$W_{^{16}}^{6} =-364-j364$ ；

$W_{^{16}}^{7} = -471-j195$ ;

蝶形因子虽然扩大了，但是后面运算还需要注意了，保证同时扩大，同时缩小，得到最终正确结果。

代码文件结构

我们对这个16点并行FFT算法进行描述的时候，采用的结构是从层层例化，从该算法的最顶层fft16，到4级蝶形运算，以及每级蝶形运算包含的8个蝶形单元，在到蝶形单元里面的复数乘法，加法器，减法器等等。从顶层开始描述到最底层，到达最底层，其实只用到了一个复数乘法器，一个加法器，一个减法器。蝶形因此采用参数的方式进行传递。

我的程序结构：