第四章  快速傅立叶变换
 
解:  解: ⑴ 直接计算:
      复乘所需时间:printf直接输出数字
      复加所需时间:
    ⑵用FFT计算:
      复乘所需时间:
      复加所需时间:
流图如下图所示:
由（1）式可得的路径，如下表所示:
  k
0    1    2    3    4    5    6    7    8    9 
 
0.8  0.67  0.56  0.46  0.39  0.32  0.27  0.22  0.19  0.16
arg []
                 
10. 当实现按时间抽取快速傅立叶变换算法时，基本的蝶形计算
       
  利用定点算术运算实现该蝶形计算时，通常假设所有数字都已按一定
比例因子化为小于1。因此在蝶形计算的过程中还必须关心溢出问题。
(a) 证明如果我们要求
      则在蝶形计算中不可能出现溢出，即
     
似乎更容易些，也更适合些。问这些条件是否足以保证在蝶形
计算中不会出现溢出？请证明你的回答。
证明：(a)
 
 
 
 
 
   
   
     
     
解：(a)
若直接利用10点快速傅立叶变换算法，则：
将n为偶数与n为奇数的部分分开，可得：
(b) 如考虑利用线性调频z变换算法，
则
12.我们希望利用一个单位抽样响应为N=50个抽样的有限冲激响应滤波
  器来过滤一串很长的数据。要求利用重叠保留法通过快速傅立叶变换
  来实现这种滤波器，为了做到这一点 ,则:
(1)输入各段必须重叠P个抽样点 ；
(2)我们必须从每一段产生的输出中取出Q个抽样点，使这些从每一段得
到的抽样连接在一起时，得到的序列就是所要求的滤波输出。假设输
入的各段长度为100个抽样点，而离散傅立叶变换的长度为128点。
进一步假设，圆周卷积的输出序列标号是从n=0到n=127。
则：(a)求P ；  (b)求Q；  (c)求取出来的Q个点之起点和终点的标
    号，即确定从圆周卷积的128点中要取出哪些点，去和前一段的