《数字信号处理》真题强化教程(第1讲 快速傅里叶变换FFT)

《数字信号处理》真题强化教程

快速傅里叶变换FFT

主讲人：杨治丽

网学天地

http://

考点重点

考点1：基-2按时间抽取FFT算法的原理，流图，特点考点2：按时间抽取的FFT算法的变体

考点3：基-2按频率抽取FFT算法的原理，流图，特点考点4：FFT的计算量

考点5：FFT的性质

考点6：一个N点FFT同时计算两个N点实序列

考点7：一个N点FFT运算一个2N点实序列

考点8：利用FFT求卷积、相关

考点9：N为复合数的FFT算法。

考点10：分裂基FFT算法。

网学天地（http://）

版权所有

考点1：基-2按时间抽取FFT算法的原理，流图，特点。

例1：给出按时间抽取（DIT）基2FFT算法的蝶形运算公式，画出N=8

时相应的算法流程图，并说明其特点。

网学天地（http://）

版权所有

N=8的算法流图：

它的特点：原位运算，输入反序，输出自然顺序。

每列的蝶形类型（系数）比前一列增加一倍，参加蝶形运算的两个数据点的间距也增大一倍。

网学天地（http://）

版权所有

例2：

网学天地

（http://）版权所有

网学天地（http://）

版权所有

考点2：按时间抽取的FFT算法的变体

例3：根据按时间抽取的基-2FFT算法的思想，推导出用3个2点DFT计算一个6点DFT的快速算法，并画出算法流程图。提示：6点数据按3个2点的分发为：{x(0), x(3)}，{x(1), x(4)}，{x(2), x(5)}

。

解：

网学天地（http://）

版权所有

网学天地（http://）

版权所有

gg336x280();=936.jpg" alt="《数字信号处理》真题强化教程(第1讲 快速傅里叶变换FFT)" />

网学天地

（http://）版权所有

网学天地（http://）

版权所有

例4：根据按时间抽取的基2 FFT算法的思想推导出利用16点FFT实现48点x(n)的DFT的快速算法，并对具体步骤作

简要说明。

网学天地（http://）

版权所有

网学天地（http://）

版权所有

例5：假设有一按时间抽取方式实现的8点FFT芯片，试问如何利用这些芯片来计算24点的DFT？请写出推导过程，并作

简要说明。

网学天地（http://）

版权所有

X(k)=F(k)+WG(k)+WG(k),k=0,1,....15k

242k24

同理，可得：

X(k+8)=F(k)+Wk+8

24G(k)+W2(k+8)

24G(k)

X(k+16)=F(k)+Wk+16

24G(k)+W2(k+16)

24G(k)

网学天地（http://）

版权所有

考点3：基-2按频率抽取FFT算法的原理，流图，特点。例6：给出按频率抽取（DIF）基-2FFT算法的蝶形运算公式，画出N=8

时相应的算法流图，并说明其特点。则有：

网学天地（http://）

版权所有

令k=2r及k=2r+1,r=0,1,2,…, N/2-1。得：

N x1 (n)= x(n)+ x(n+ ) 2其中： x (n)=[ x(n) x(n+ N )]W n, n= 0,1... N 1 2 N 2 2网学天地(http://)版权

所有