蝶形运算k的取值_怎么判断k的取值范围_蝶形运算流图(3)

从上式我们可以看到不同输入项所乘的旋转因子个数(注意这里是个数，就算是wn^0，也被考虑进去了，因为在没有放大时wn^0等于1，放大后所有旋转因子指数模均不为1，因此需要考虑)。这就导致输入不平衡，运算结果不正确。经查阅相关资料，比较妥善的做法是，首先对所有旋转因子都放大2^Q倍，Q必须要大于等于L，以保证不同旋转因子的差异化。旋转因子放大，为了保证其模为1，在每一次蝶形运算的乘积运算中我们需要将结果右移Q位来抵消这个放大，从而得到正确的结果。之所以采用放大倍数必须是2的整数次幂的原因也在于此，我们之后可以通过简单的右移位运算将之前的放大抵消，而右移位又代替了除法运算，大大节省了时间。

4.计算过程中的溢出问题

最后需要注意的一个问题就是计算过程中的溢出问题。在实际应用中，AD虽然有12位的位宽，但是采样得到的信号可能较小，例如可能在0~8之间波动，也就是说实际可能只有3位的情况。这种情况下为了在计算过程中不丢失信息，一般都需要先将输入数据左移P位进行放大处理，数据放大可能会导致溢出，从而使计算错误，而溢出的极限情况是这样：假设我们数据位宽为D位(不包括符号位)，AD采样位数B位，数字放大倍数P位，旋转因此放大倍数Q位，FFT级联运算带来的最大累加倍数L位。我们得到:

假设AD位宽12，数据位宽32，符号位1位，因此有效位宽31位，采样点数N，那么我们可以得到log2(N)+P+Q<=19,假设点数128,又Q>=L可以得到放大倍数P<=5。

FFT代码示例

根据以上的分析，我整理了一份128点的FFT代码如下，该代码在keil中仿真运行，未发现问题。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-44987-3.html