数字信号处理-数字信号处理-快速傅里叶变换直接计算DFT的问题及改进途径

第一节直接计算DFT的问题及改进途径1、问题的提出设有限长序列x(n)，非零值长度为N，若对x(n)进行一次DFT运算，共需多大的运算工作量？计算成本?计算速度?2.DFT的运算量回忆DFT和IDFT的变换式：计算机运算时（编程实现）：以DFT为例：运算量(a+jb)(c+jd)=(ac-bd)+j(bc+ad)计算一个N点DFT，共需N2次复乘。以做一次复乘1μs计，若N=4096，所需时间为石油勘探，有24个通道的记录，每通道波形记录长度为5秒，若每秒抽样500点/秒，1）每道总抽样点数：500*5=2500点2）24道总抽样点数：24*2500=6万点3）DFT复乘运算时间：N2=(60000)2=36*108次由于计算量大，且要求相当大的内存，难以实现实时处理，限制了DFT的应用。长期以来，人们一直在寻求一种能提高DFT运算速度的。FFT便是Cooley&Tukey在1965年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。1、利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率。1）对称性2）周期性3）可约性第二节改善DFT运算效率的基本途径2、将长序列DFT利用对称性和周期性分解为短序列DFT的思路因为DFT的运算量与N2成正比的，如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。N点DFT复乘：