4.2　课后习题详解
4-1  如果一台通用计算机的速度为平均每次复乘40ns ，每次复加5ns ，用它来计算512点的DFT[x （n ）]，问直接计算需要多少时问?用FFT 运算需要多少时间?若做128点快速卷积运算，问最低抽样频率应是多少?
解：①直接利用DFT 计算：复乘次数为N 2，复加次数为N （N-1）。
②利用FFT
计算：复乘次数为
，复加次数为N㏒
2
N 。
（1）直接计算复乘所需时间
复加所需时间
所以（2）用FFT 计算复乘所需时间
复加所需时间
所以
4-2  N ＝16时，画出基-2按频率抽选法的FFT 流图采用输入自然顺序，输出倒位序），统计所需乘法次数（乘±1，乘±j 都不计在内）。根据任一种流图确定序列x （n ）
＝4cos （n π／2）（0≤n ≤15）的DFT 。
解：按频率抽取法的FFT 流图中的复数乘法出现在减法之后，其运算量为
复数乘法：；复数加法：；由于N ＝16，有，
，，不需要乘法。
按频率抽取，见图4-1（a ）。图4-1（a ）
运算量：
复数乘法：
由于，，，不需要乘法。由图P4.2（a ）可知，共有
的个数为
1＋2＋4＋8＝15
有的个数为
1＋2＋4＝7
所以总的乘法次数为
32-15-7＝10（个）复数加法：
举例：对序列x （n ）＝4cos （n π／
2）（0≤n ≤15）可表示为
由于N ＝16，可采用P4.2（b ）的流图。设Xi （k ）＝（i ＝1，2，3
，
4
）分别为第i 级蝶形结构的输出序列，则由P4.2（b ）的流图可知
由于采用的是顺序输入、逆序输出的结构，因此输出X （k ）与X 4（k ）为逆序关系，即
，
为k 二进制逆序值
由此可知，x （n ）的DFT 为
X （4）＝X 4（2）＝32，
X （12）＝X 4（3）＝12
图4-1（b ）
4-3  用MATLAB 或C 语言编制以下几个子程序。
（1）蝶形结运算子程序；
（2
）求二进制倒位序子程序；
（3）基-2 DIT FFT 流程图，即迭代次数计算子程序。
解：（1）蝶形结运算子程序
（2）求二进制倒位序子程序
（3）基-2 DIT FFT 流程图，即迭代次数计算子程序
4-4  试用N 为组合数时的FFT 算法导出N ＝30＝3×2×5的结果，画出流图，并统计
短时傅里叶变换matlab程序
所需乘法次数（乘±1，乘±j 都不计在内）。
解：由题意有N ＝r 0r 1r 2＝3×2×5，即r 0＝3，r 1＝2，r
2＝5。采用输入n 按正序排列，输出k
按倒序排列的方法，则有其中各n
i
、k i 的取值范围为
列出混合基运算的表达式
以上推导中应用了
又因为
（
N
／N i ＝整数时），则有其中