丁⽟美《数字信号处理》（第3版）（课后习题快速傅⾥叶变换（FFT））
第4章　快速傅⾥叶变换（FFT）
1．如果某通⽤单⽚计算机的速度为平均每次复数乘需要4µs，每次复数加需要1µs，⽤来计算N＝1024点DFT，问直接计算需要多少时问。⽤FFT计算呢？照这样计算，⽤FFT进⾏快速卷积对信号进⾏处理时，估计可实现实时处理的信号最⾼频率。
解：当N＝1024＝210时，直接计算DFT的复数乘法运算次数为
N2＝1024×1024＝1048576次
复数加法运算次数为
N（N－1）＝1024×1023＝1047552次
直接计算所⽤计算时间T D为
⽤FFT计算1024点DFT所需计算时间T F为
快速卷积时，需要计算⼀次N点FFT（考虑到H（k）＝DFT[h（n）]已计算好存⼊内存）、N次频域复数乘法和⼀次N点IFFT。所以，计算1024点快速卷积的计算时间T c约为
所以，每秒钟处理的采样点数（即采样速率）
由采样定理知，可实时处理的信号最⾼频率为
应当说明，实际实现时，f max还要⼩⼀些。这是由于实际中要求采样频率⾼于奈奎斯特速率，⽽且在采⽤重叠相加法时，重叠部分要计算两次。重叠部分长度与h（n）长度有关，⽽且还有存取数据和指令周期等消耗的时间。
2．如果将通⽤单⽚机换成数字信号处理专⽤单⽚机TMS320系列，计算复数乘和复数加各需要10ns。请重复做上题。
解：与第1题同理。
直接计算1024点DFT所需计算时间T D为
⽤FFT计算1024点DFT所需计算时间T F为
快速卷积计算时间T c约为
可实时处理的信号最⾼频率f max为
由此可见，⽤DSP专⽤单⽚机可⼤⼤提⾼信号处理速度。所以，DSP在数字信号处理领域得到⼴泛应⽤。机器周期⼩于1ns的DSP产品已上市，其处理速度更⾼。
3．已知X （k ）和Y （k ）是两个N 点实序列x （n ）和y （n ）的DFT ，希望从
X （k ）和Y （K ）求x （n ）和y （n ），为提⾼运算效率，试设计⽤⼀次N 点IFFT 来完成的算法。
解：因为x （n ）和y （n ）均为实序列，所以，X （k ）和Y （n ）为共轭对称序列，jY （k ）为共轭反对称序列。可令X （k
）和jY （k ）分别作为复序列F
（k ）的共轭对称分
量和共轭反对称分量，即计算⼀次
N 点IFFT 得到
由DFT 的共轭对称性可知
故
4．设x （n ）是长度为2N 的有限长实序列，X （k ）为x （n ）的2N 点DFT 。
（1）试设计⽤⼀次N 点FFT 完成计算X （k ）的⾼效算法。
（2）若已知X （k ），试设计⽤⼀次N 点IFFT 实现求X （k ）的2N 点IDFT 运算。解：本题的解题思路就是DIT-FFT 思想。
（1）在时域分别抽取偶数和奇数点x （n ），得到两个
N 点实序列x1（n ）和
x2（n ）：
根据DIT-FFT 的思想，只要求得x 1（n ）和x 2（n ）的N 点DFT ，再经过简单的⼀级蝶形运算就可得到x （n ）的2N 点DFT 。因为x 1（n ）和x 2（n ）均为实序列，所以根据DFT 的共轭对称性，可⽤⼀次N 点FFT 求得X 1
（k ）和
X 2（k ）。具体⽅法如下：
令
则
2N 点DFT[x （n ）]＝X （k ）可由
X 1（k ）和X 2（k ）得到
这样，通过⼀次N 点IFFT 计算就完成了计算2N 点DFT 。当然还要进⾏由Y （k ）求X 1（k ）、X 2（k ）和X （k
）的运算（运算量相对很少）
。（2）与（1）相同，设
则应满⾜关系式
短时傅里叶变换matlab程序由上式可解出
由以上分析可得出运算过程如下：
①由X （k ）计算出
X 1（k ）和X 2（k ）：
②由X 1（k ）和X
2（k ）构成N 点频域序列Y （
k ）：
其中，进⾏N 点IFFT ，得到
由DFT 的共轭对称性知
③由x 1（n
）和x 2（n ）合成x （n ）：
在编程序实现时，只要将存放x 1（n ）和x 2（n ）的两个数组的元素分别依次放⼊存放x （n ）的数组的偶数和奇数数组元素中即可。5．分别画出16点基2DIT-FFT 和DIF-FFT 运算流图，并计算其复数乘次
数，如果考虑三类碟形的乘法计算，试计算复乘次数。
解：本题⽐较简单，仿照教材中的8点基2DIT-FFT 和DIF-FFT 运算流图很容易画出16点基2DIT-FFT 和DIF-FFT 运算流图。
6．按照下⾯的IDFT 算法编写MATLAB 语⾔IFFT 程序，其中的FFT 部分不⽤写出出
清单，可调⽤fft 函数。并分别对单位脉冲序列、矩形序列、三⾓序列和正弦序列进⾏FFT 和IFFT 变换，验证所编程序。
解：为了使⽤灵活⽅便，将本题所给算法公式作为函数编写
ifft46．
m 如下：
％函数ifft46．in
％按照所给算法公式计算WET
％对Xk 取复共轭
％按照所给算法公式计算IFFT
分别对单位脉冲序列、长度为8的矩形序列和三⾓序列进⾏FFT ，并调⽤函数ifft46计算IFFT 变换，验证函数ifft46的程序ex406.m 如下：％程序ex406.m
％调⽤fft 函数计算IDFT
x1n ＝1；％输⼊单位脉冲序列x1n
x2n ＝[1 1 1 1 1 1 1 1]；％输⼊矩形序列向量x2n
x3n ＝[1 2 3 4 4 3 2 1]；％输⼊三⾓序列序列向量x3nN ＝8：
X1k ＝fft （x1n ，N ）；％计算x1n 的N 点DFTX2k ＝fft （x2n ，N ）；
％计算x2n 的N 点DFTX3k ＝fft （x3n ，N ）；％计算x3n 的N 点DFT
x1n ＝ifft46（X1k ，N ）％调⽤ifft46函数计算X1k 的IDFT
x2n ＝ifft46（X2k ，N ）％调⽤ifft46函数计算X2k 的IDFT
x3n ＝ifft46（X3k ，N ）％调⽤ifft46函数计算X3k 的IDFT
运⾏程序输出时域序列如下所⽰，正是原序列x1n 、x2n 和x3n 。