007-FFT.rar
(31.88 KB)
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之前，还是先谈谈如何写程序。因为在程序中用到了这些思想。
| 
楼主
标题置顶
标题高亮
乱码就乱码吧。，这不是黑桃、红心、方片、梅花吗？呵呵，是的，意思是放松一下，对如何分割RAM感兴趣者可以先思考一下，答案稍后揭晓，先来看看更简单的问题：三层循环的实现。
