答案-8讲第四章

《现代数字信号处理》第八讲快速傅里叶变换(FFT)国家短波通信工程技术研究中心徐以涛4.1.1直接计算DFT的运算量4.1.2减少运算量的途径4.1

直接计算DFT的运算量及改进途径4.2时间抽取法(DIT)基2FFT算法4.2.1

DIT-FFT算法原理4.2.2

DIT-FFT运算量分析与比较复习复习（1）N点DFT分解为几个短序列的DFT

奇偶分解、前后分解（2）利用旋转因子的周期性、运算规律和对称性

FFT算法就是不断地把长序列的DFT分解成几个短序列的DFT，并利用旋转因子的周期性和对称性来减少DFT的运算次数。减少运算量的基本途径偶序列奇序列DIT－FFT蝶形运算完成一个蝶形运算，需要一次复数乘和两次复数加法运算。

DIT－FFT蝶形运算第一次分解第二次分解第三次分解第一级第二级第三级完整的DIT-FFT运算流图（N＝8）当N＝2M时，其运算流图应有M级蝶形，每一级都由N/2个蝶形运算构成。

每个蝶形需要一次复数乘法、两次复数加法；

DIT-FFTDFT直接计算X(k)的计算量复数乘法复数加法例如N=1024时，运算效率提高约180倍。DIT－FFT算法运算量第七讲4.1～4.2

直接计算DFT的运算量及改进途径时间抽取法(DIT)基2FFT算法第八讲4.2

～4.5

时间抽取法(DIT)基2FFT算法频域抽取法(DIF)基2FFT算法

快速傅里叶逆变换(IFFT)算法

FFT算法的工程实现考虑4快速傅里叶变换（FFT）第八讲4.2时间抽取法(DIT)基2FFT算法

4.2.3

DIT-FFT的运算规律

4.2.4

DIT-FFT的其它形式流图4.3频域抽取法(DIF)基2FFT算法

4.3.1

DIF-FFT算法原理

4.3.2

DIT-FFT与DIF-FFT的比较4.4

快速傅里叶逆变换(IFFT)算法4.5

FFT算法的工程实现考虑

4.5.1旋转因子的生成

4.5.2旋转因子的使用

4.5.3实序列的FFT计算（重点、难点）（重点）（难点）4.2.3DIT-FFT的运算规律如何编程实现FFT算法，如何画FFT的运算流图？1.原位计算在计算蝶形时，输出数据可存入原输入数据占用的存储单元

，即原位计算。节省存储开销，降低设备成本。

蝶形特点：（1）每个蝶形的输入数据只对计算本蝶形有用；（2）每个蝶形的输入和输出数据在同一水平线上。4.2.3DIT-FFT的运算规律2.位码倒序000001111101110100011010000100111101011001110010

DIT-FFT算法的输入数据必须按倒序存储，这在DSP芯片中容易实现，在TMS320等芯片中有专门的倒序寻址。4.2.3DIT-FFT的运算规律3.蝶形运算规律第一级第二级第三级第m级共有2m－1个不同的旋转因子

4.2.3DIT-FFT的运算规律4.2.4DIT-FFT的其它形式流图库利－图基第八讲4.2时间抽取法(DIT)基2FFT算法

4.2.3

DIT-FFT的运算规律

4.2.4

DIT-FFT的其它形式流图4.3频域抽取法(DIF)基2FFT算法

4.3.1

DIF-FFT算法原理

4.3.2

DIT-FFT与DIF-FFT的比较4.4

快速傅里叶逆变换(IFFT)算法4.5

FFT算法的工程实现考虑

4.5.1旋转因子的生成

4.5.2旋转因子的使用

4.5.3实序列的FFT计算4.3.1DIF-FFT算法原理

DIF-FFT是在频域对X(k)进行M级奇偶抽取，并利用对称性将N点DFT变成M级DIF-FFT蝶形运算。1.算法推导设序列x(n)的长度为 ，将x(n)前后对半分开，得到两个子序列，将X(k)分解成偶数组与奇数组，当k取偶数当k取奇数4.3.1DIF-FFT算法原理2.DIF-FFT蝶形运算DIF-FFT蝶形运算流图符号偶序列奇序列DFTDFT4.3.1DIF-FFT算法原理3.DIF-FFT算法分解流程图DIF-FFT的一次分解运算流图（N=8）4.3.1DIF-FFT算法原理第一次分解第二次分解DIF-FFT的二次分解运算流图（N=8）3.DIF-FFT算法分解流程图4.3.1DIF-FFT算法原理DIF-FFT的运算流图（N=8）3.DIF-FFT算法分解流程图第八讲4.2时间抽取法(DIT)基2FFT算法

4.2.3

DIT-FFT的运算规律

4.2.4

DIT-FFT的其它形式流图4.3频域抽取法(DIF)基2FFT算法

4.3.1

DIF-FFT算法原理

4.3.2

DIT-FFT与DIF-FFT的比较4.4

快速傅里叶逆变换(IFFT)算法4.5

FFT算法的工程实现考虑

4.5.1旋转因子的生成

4.5.2旋转因子的使用

4.5.3实序列的FFT计算4.3.2DIF-FFT与DIT-FFT的比较相同点：4.3.2DIF-FFT与DIT-FFT的比较DIF-FFT蝶形运算流图符号DIT-FFT蝶形运算流图符号偶序列奇序列DFTDFT偶序列奇序列DFTDFT4.3.2DIF-FFT与DIT-FFT的比较不同点：DIT-FFTDIF-FFT蝶形运算输入序列自然顺序倒序排列先相乘后加(减)先加(减)后相乘输出序列自然顺序倒序排列时域频域奇偶分开前后对半开奇偶分开前后对半开蝶形张口由小到大由大到小第八讲4.2时间抽取法(DIT)基2FFT算法

4.2.3

DIT-FFT的运算规律

4.2.4

DIT-FFT的其它形式流图4.3频域抽取法(DIF)基2FFT算法

4.3.1

DIF-FFT算法原理

4.3.2

DIT-FFT与DIF-FFT的比较4.4

快速傅里叶逆变换(IFFT)算法4.5

FFT算法的工程实现考虑

4.5.1旋转因子的生成

4.5.2旋转因子的使用

4.5.3实序列的FFT计算4.4快速傅里叶逆变换（IFFT）算法1.DFT和IDFT的区别和联系DFTIDFT变换对象旋转因子修正因子无1/N需替换FFT中的变换对象、旋转因子，增加修正因子。2.IFFT的运算流图时间抽取法FFT（DIT－FFT）频率抽取法IFFT（DIF－IFFT）

4.4快速傅里叶逆变换（IFFT）算法2.IFFT的运算流图频率抽取法FFT（DIF－FFT）时间抽取法IFFT（DIT－IFFT）时间抽取法FFT（DIT－FFT）频率抽取法IFFT（DIF－IFFT）

4.4快速傅里叶逆变换（IFFT）算法2.IFFT的运算流图4.4快速傅里叶逆变换（IFFT）算法3.直接调用FFT程序来计算IDFT

先将X(k)取共轭，然后直接调用FFT子程序，再取共轭并乘以1/N得到序列x(n)。取共轭再取共轭4.4快速傅里叶逆变换（IFFT）算法第八讲4.2时间抽取法(DIT)基2FFT算法

4.2.3

DIT-FFT的运算规律

4.2.4

DIT-FFT的其它形式流图4.3频域抽取法(DIF)基2FFT算法

4.3.1

DIF-FFT算法原理

4.3.2

DIT-FFT与DIF-FFT的比较4.4

快速傅里叶逆变换(IFFT)算法4.5

FFT算法的工程实现考虑

4.5.1旋转因子的生成

4.5.2旋转因子的使用

4.5.3实序列的FFT计算1.旋转因子的生成：精度高，运算量大，适于非实时处理；：查表法，速度快，占用内存，精度受限。直接计算预先计算4.5FFT算法的工程实现考虑1次复数乘法＝4次实数乘法＋2次实数加法4.5FFT算法的工程实现考虑2.旋转因子的使用4.5FFT算法的工程实现考虑DIT-FFT运算流图（N＝8）第一级第二级第三级2.旋转因子的使用一类蝶形单元运算：包含所有旋转因子二类蝶形单元运算：去掉旋转因子三类蝶形单元运算：再去掉旋转因子四类蝶形单元运算：再去掉旋转因子蝶形单元类型越多乘法运算量越小编程越复杂4.5FFT算法的工程实现考虑2.旋转因子的使用4.5FFT算法的工程实现考虑2.旋转因子的使用3.实序列的FFT计算（1）用一个N点FFT计算两个N点实序列的FFT一个序列为实部另一个序列为虚部共轭对称部分共轭反对称部分4.5FFT算法的工程实现考虑3.实序列的FFT计算（2）用N/2点FFT计算一个N点实序列的FFT原序列的偶数点为新序列的实部原序列的奇数点为