頻率抽選快速傅立葉變換算法

頻率抽選快速傅立葉變換算法(decimation-in-frequency fast Fourier transform algorithm)一種計算離散傅立葉變換的快速算法

頻率抽選快速傅立葉變換算法(decimation-in-frequency fast Fourier transform algorithm)一種計算離散傅立葉變換的快速算法.這類算法的基本思路是:將離散傅立葉變換(DFT)的輸人序列在頻域進行抽選(參見“離散傅立葉變換”)，逐次分解成越來越短的子序列，然後將其所對應的較短的時間序列分別進行離散傅立葉變換，最後再按照一定的規律逐次組合，構成原序列的離散傅立葉變換.以序列的長度N為2的整冪次基2 FFT為例(參見“快速傅立葉變換”).設二((n)為N點時間序列，N一2z',v為正整數.二((n)的DFT為X <k>，是N點頻序列.將X <k>分解成偶數點和奇數點子序列，則