可用于嵌入式计算的定点FFT算法.doc

可用于嵌入式计算的定点FFT算法
可用于嵌入式计算的定点FFT算法 1
推荐
！
简介
本示例程序演示了如何计算定点和浮点各个长度和位数的按时间抽取FFT算法。所有程序在VC6下编译通过。
最精确的FFT计算最好采用浮点，但浮点对于嵌入式设备计算量太大，有的朋友想采用定点，但网上资料不多，且长度位数要求不一，于是本人制作了这个版本。
此程序可以实现对长度为64，128，256，512，1024，2048的数据进行定点FFT（如果需要其他长度可自行修改）以及浮点版本。
根据处理器处理能力不同，对于数据类型的长度，提供了8位版本，16位版本和32位版本，可用于单片机等不同位数的嵌入式处理器。当然，三个版本主要是给定了不同的处理精度。
此程序采用了运算级间动态缩放舍去最低位，保证了输出不溢出，且提供了尽可能高的精度。具有自动适应输入值大小的能力。因此有较高的信噪比。
使用说明
，可将其加入到图形环境中或者控制台中，正如示例所示。
有两个值需要根据环境修改：
长度通过#define N 长度值
决定，长度值可取上文所述六种，主要是考虑嵌入式设备处理能力，一般来讲8位机用256点，这样可以保证下标在8bits以内，16位机可以考虑稍大的点数。
类型数据位数通过：
#define BIT 位数
决定，只能取8，16，32
， CWaveAnalysisView::OnDraw(CDC* pDC)函数中。
测试数据采用两个正弦波的叠加，即sin(2**i/8)+sin(2**i/64);
并将其扩大到最大值之间。
绘图的版本频域图像模值没有开根号，表示的是模值的平方。
如果时域直流量过大，则会引起频率的0点值过大，图像变得缩放的太小，如果为了绘图方便，可将其归零。
，和一个控制台结合形成的。 其演示的是一个门函数引发的sinc函数。
定点算法原理和精度分析
由于定点运算位数为定值，因此不能像浮点一样进行各种乘法和加法处理，因为这两种运算会产生溢出。同时，对于旋转因子的小数模式也需要修整为可以运算的整数模式，这便是FFT定点的两个需要处理的难点。
本算法采用了运算量较大但效果较好的动态溢出检查。也就是说在计算每一级之前，对所有值进行遍历，如果发现有超过溢出允许输入值的变量，则对整个数组进行右移缩小处理。这样就保证了数值较小的输入不会被过度缩放，而数值很大的数据也能够通过FFT运算。由于对所有的数组值进行缩放，因此不会造成失真，但是幅度大小会有变化。因此可以理解为定点算法只求解相对值。在使用过程中，尽量不要叠加过多直流分量，因为这将导致频率0点处值很大，其它的值被缩放殆尽。影响精度。
下面详细介绍缩放方法：
一个乘加运算可以理解为：
X1+X2*WN
我们需要找出在什么情况下输出会最大，并在设定输出在此数据类型允许值下时，输入最大取多少。
由于X1，X2，WN都为复数，且abs(X2)=abs(X2*WN)，因此最坏的情况是，在模