DFT在实际运用中非常主要，可以打算旗子暗记的频谱，功率谱和线性卷积等。
离散傅里叶变换的公式：
个中：
称为旋转因子。
由欧拉公式可得：
直接按DFT变换进行打算，当序列长度N很大时，打算量非常大，所需的韶光非常长。
FFT是 快速傅里叶变换。其算法事理这里不再赘述，网上资料或者干系书本的先容很多。紧张分为按韶光抽取法和按频率抽取法。
这里先容按韶光抽取的基2算法的硬件实现。
下面先容的部分须要理解蝶形运算是什么，这里不做剖析。
先来看一张16点的蝶形运算图：
第1级（第1列）每个蝶形的两节点“间隔”为1，第2级每个蝶形的两节点“间隔”为2，第3级每个蝶形的两节点“间隔”为4，第4级每个蝶形的两节点“间隔”为8。由此推得，第m级蝶形运算，每个蝶形的两节点“间隔”L=2^(m-1)。
对付16点的FFT，第1级有8组蝶形，每组有1个蝶形；第2级有4组蝶形，每组有2个蝶形；第3级有2组蝶形，每组有4个蝶形；第4级有1组蝶形，每组有8个蝶形。由此可推出，对付N点的FFT，第m级有N/2L组蝶形，每组有L=2^(m-1)个蝶形。
从上图我们可以剖析出左边输入端与右边输出真个顺序关系，用二进制表示为：
左边 右边
0000 0000
1000 0001
0100 0010
1100 0011
0010 0100
1010 0101
0110 0110
1110 0111
0001 1000
······· ·······
不丢脸出，右边的逆序正是左边的正序，利用这一点，可以事先将输入序列重新排序。
关于旋转因子，可以事先打算出来 ，由于FPGA不善于做浮点运算，须要将打算出的旋转因子扩大2^n倍。然后以.mif的格式存放在FPGA片上ROM中。
关于输入序列的长度N，最好是2的整数次幂。
为了提高速率，可将FFT的输入序列存放在FPGA片上RAM中，以是在利用FFT的项目中，选取FPGA芯片时，要考虑片上RAM的容量。
将片上RAM设置为TRUE DPRAM，两个口读，两个口写，提高存取效率，实际利用中自有妙用。
根据上图的蝶形运算图，可以大致确定 FFT的打算量。
直接的DFT算法运算量：
NN ，单位为复数乘法的韶光MT；
利用FFT算法的运算量：
N/2log2(N)，单位为数乘法的韶光MT；
算法运算量 比较：
根据蝶形运算图，可以将FPGA设计层级构造分为3层：
蝶形级数循环层，
蝶形组数循环层，
蝶形个数循环层。
复数乘法可直策应用FPGA片内自带的乘法器，把稳数据位宽，严防溢出。
其余，被乘数和乘数必须为原码，做乘法时必须考虑数据的正负符号问题。
设计加法器和减法器时，由于存在符号问题，包括正数+正数，正数+负数，负数+负数，以及正数-正数，正数-负数，负数-正数，负数-负数，这些判断操作非常繁琐，设计时格外把稳数据的大小及正负。
这里我们可以将设计变的大略：
将输入到加法器和减法器的两个数据先转换为补码，然后做加法运算，输出时再将补码转换成原码即可。
为了节省资源，尽可能利用移位代替乘法和除法。为了提高速率，可在适当的地方加入流水线操作。
关于精度问题：由于FPGA不善于做浮点运算，一定存在精度问题。
首先，对存入ROM的旋转因子进行了放大，引入精度问题。
然后，在旋转因子的乘法中，引入精度问题。
再后续旋转因子的还原中，也引入精度问题。
提高精度，一方面在放大旋转因子时，可以适当提高放大倍数，另一方面，旋转因子还原中，只管即便把还原除法放在末了输出的地方。
版权所有权归卿萃科技，转载请注明出处
作者：卿萃科技ALIFPGA
原文地址：卿萃科技FPGA极客空间 微信"大众年夜众号
