玩转VHDL007-FFT-ucx的回答

玩转VHDL007-FFT

2020-02-02 11:48发布

站内问答 / FPGA

8750 6

007-FFT.rar (31.88 KB, 下载次数: 8) 2017-10-6 12:13 上传点击文件名下载附件
007-FFT

FFT算法
每当想介绍一下FFT算法的FPGA实现时，又总是觉得千头万绪不知从何处开始。每编辑一帖，总是力求达到如下目的：
①  给FPGA工程师提供一个取之即用的免费IP核。这要求程序实现的功能尽可能通用和常用，外部接口尽可能简单明了。使用者可以不关心内部实现细节，也与使用的硬件语言是VHDL或verilog无关。
②  通过对程序设计过程的分析，给同仁们分享设计过程中采用的技巧、以及优化资源提高速率的注意事项。这也与语言是VHDL还是verilog无关。
③  通过代码的呈现，让读者感受到通过打造自己的库函数可以使VHDL书写起像C语言一样自由。
既然不知何处说起，那么就按照编辑帖子的目的顺序来叙说吧。先介绍FFT算法的功能模块DIT_FFT的参数、接口和性能。
FFT算法模块接口和性能
模块DIT_FFT实现N个点的FFT或IFFT算**能，其实体头部：
Entity DIT_FFT is generic(
      N :integer := 1024;  DW :integer := 24; IFFT : boolean := false
      );
      Port(
      clock                         : in std_logic;
      bgn                            : in std_logic;
      dReal,dImag          : in std_vector(DW-1 downto 0) :=(others=>'0');
      qReal,qImag          : out std_vector(DW-1 downto 0);
      qEn,busy                  :out std_logic
      );
End DIT_FFT;
类属参数N是FFT点数，其值只能为2的整数次幂否则编译报错，这里默认为1024点FFT。DW代表运算数据宽度，需要根据实际情况选取。例如，数据来自16位AD，要实现256点FFT，那么DW至少选择24才能保证计算结果不溢出。而对于2048点，DW要选取27位或以上。因为IFFT的表达式中有除以N的项，所以结果不会溢出。类属参数IFFT为真时DIT_FFT实现的是IFFT功能，这里默认为假，即实现的是FFT计算。
端口clock：时钟，对常见FPGA，上限可工作在130M。
bgn：脉宽为一个时钟周期的开始运算脉冲，高电平有效。要求必须在输出busy为低电平状态下发起。
dReal,dImag：从名称可以看出分别表示输入数据的实部和虚部，格式为定点有符号数。在bgn有效的下一周期开始N个周期内连续输入N个数。不使用虚部输入时，则默认为全0输入。如果dReal数据源来自AD，那么需要按照有符号数规则把AD值扩展到DW位输入到dReal。
qReal,qImag：结果输出，实部和虚部，顺序输出。
qEn：为1表示计算结束，qReal,qImag正在输出结果，持续时间N个周期。
busy：在bgn下一周期置高，在qEn指示输出第N个结果后拉低。busy为低指示可以进行新一轮运算。
DIT_FFT可划分为前后三步：数据输入、蝶形运算迭代、数据输出。数据输入和输出均刚好需要N个时钟周期，蝶形运算时间为N/2*lOG2(N)个时钟周期。busy指示忙的时间为这三个时间的总和。在N=10，DW=24条件下Quartus II默认设置编译消耗926个逻辑单元，乘法器16个，选用器件EP4CE30F23I7时最高时钟超过150M。
本人在256点模式下做了一次仿真，全部仿真文件见附件007-FFT.rar，仿真运行32us时间见结果。fft_data.txt存放256个用17位表示的数据，取值范围是-32768到+32768。以这256个数据进行FFT运算，结果保存在<fft_结果.txt>文件中，实部在第一列，虚部在第二列。在FFT结果输出的同时，又进行IFFT运算，其结果保存在<ifft_结果.txt>文件中。
FFT运算结果与按照double型计算的FFT结果进行比较，误差绝对值不超过8。IFFT运算结果与fft_data.txt中的输入数据比较，误差绝对值不超过1。
FFT或IFFT运算需要用到wi=e^(-j*i*2p/N)，FPGA用到这些数值的可以用005帖中介绍的方法。这里为简化设计，直接用查表得实部和虚部，初始化数据分别存放在real.mif文件和imag.mif中。为了适合FFT运算，wi采用i的比特逆序形式存放，即wi=e^(-j*i反序*2p/N)。如此，我们发现对不同的N值，只要i相同则wi相同。由于wi要以定点数格式存放，所以乘以2^16 = 65536后取整。那么wi的实部和虚部的范围是-2^16到2^16，故而用18比特表示。
附件中给出的mif文件是以4096点生成的，当实际使用N<4096时，Quartus II编译器自动截取前N个初始化ROM。当大于4096点时，程序中DIT_FFT.vhd的第34行设置一个编译错误。如果需要超过4096点的FFT，则需要重新产生mif文件并修改或删除此34行。然而当用modelsim仿真时，mif文件必须刚刚好和实际的N值匹配。如果仿真N=256情况，那么需要把mif文件中原来的DEPTH=2048;改成DEPTH=128;只保留00到7F地址的内容，其余删除。
模块的接口和性能的介绍，是为了给使用者提供参考，便于考量模块是否适宜于自己的设计。如果你已经是成熟的FPGA工程师，只是懒得动脑再考虑FFT编程实现，那么下载附件返回，余下的内容就不需要再看了。
在解读DIT_FFT之前，还是先谈谈如何写程序。因为在程序中用到了这些思想。

友情提示: 此问题已得到解决，问题已经关闭,关闭后问题禁止继续编辑，回答。

6条回答

2020-02-02 16:40

本帖最后由 ucx 于 2017-10-6 12:17 编辑

N点FFT算法描述
完整的FFT算法可分为三大步：数据输入、蝶形运算迭代、结果输出。这三部分细节如下所述。
顺序输入N个数存入数组X[N]，按照W=e^(-j*i反序*2p/N)初始化数组W[N/2]。
迭代算法用C语言完整精确描述为：
for(D=N/2; D > 0; D /= 2){
   R= D*2;
   for(j=0; j < N/R; j++) {
         for(i=0; i < D; i++) {
1.       a = i+j*R;
2.       b = a + D;
3.       wb = W[j] * X[b];
4.       X[b] = X[a] - wb;
5.       X[a] = X[a] + wb;
         }
   }
}
按照索引比特逆序读取数组X[N]，即得FFT计算结果。
算法由外、中、内三层循环构成。称外层循环为轮循环，中层和内层循环合称轮内循环。呵呵，写到这里，好像凭空多了轮循环和轮内循环两个概念。其实，如果你对FFT算法认识还不够清晰的话，这个概念有助于理解FFT。内层循环就是一次蝶形运算，而一次蝶形运算完成了两个点的数值更新。如果要把X[N]全部更新一遍，可以形象地定义为一轮，也就是中层和内层循环合起来完成的功能。
轮内循环为N/2次，轮循环为LOG2(N)次，则总循环次数为M=N/2*LOG2(N)，正如教科书中介绍的一样。为了在叙述FPGA实现的时候便于和算法对应，接下来继续引入几个概念，一切都是为了后面的叙述方便。
称蝶形运算第1步为选出蝶形上翅X[a]的位置a，第2步为选出下翅X位置b，第3步求出旋转因子Wn与下翅的乘积WB，第4,5步为更新蝶形双翅。轮循环中的D为翅距，D的两倍R为蝶距。在不引起混淆的情况下，以下也常简称上翅的位置为上翅，简称下翅的位置为下翅。
在轮循环中可看出，每过一轮后翅距减半，最后一轮翅距为1，最后一轮结束则蝶形运算结束。

查看其它6个回答

一周热门更多>