计算机应用 ›› 2010, Vol. 30 ›› Issue (10): 2777-2780.

• 软件过程技术与先进计算 • 上一篇    下一篇

频域抽取多维向量基快速傅里叶变换

徐妮妮1,于海艳2,肖志涛3   

  1. 1. 天津工业大学信息与通信工程学院
    2.
    3. 天津工业大学
  • 收稿日期:2010-04-14 修回日期:2010-06-12 发布日期:2010-09-21 出版日期:2010-10-01
  • 通讯作者: 徐妮妮
  • 基金资助:
    国家青年自然科学基金资助项目;国家自然科学基金资助项目;天津工业大学校基金资助项目

Multi-dimensional vector radix fast Fourier transform with decimation in frequency domain

  • Received:2010-04-14 Revised:2010-06-12 Online:2010-09-21 Published:2010-10-01

摘要: 给出了频域抽取(DIF)多维向量基快速傅里叶变换(FFT)算法。对多维频域信号的每一维,采用向量基2频域抽取法,导出了快速算法蝶形运算的一般形式。该FFT算法适合于维数为任意整数的情况,当维数为1时,算法退化为著名的频域抽取向量基2 FFT算法。为了便于编程实现,以频域抽取3维向量基FFT算法为例,给出了快速算法实现流程,该流程易于向任意整数维推广。计算量比较结果显示,频域抽取多维向量基FFT算法比多维分离式FFT算法计算量低。

关键词: 多维离散傅里叶变换, 频域抽取, 多维向量基, 快速傅里叶变换, 多维分离式FFT算法

Abstract: A multi-dimensional vector radix Fast Fourier Transform (FFT) algorithm with Decimation In Frequency (DIF) was proposed. Using vector radix 2 DIF for each dimension of the multi-dimensional frequency domain signal, the general form of butterfly computation of the FFT algorithm was obtained. This FFT algorithm can be used with arbitrary integer dimensions. For 1-dimension, the algorithm will be simplified as the well-known DIF vector radix 2 FFT. To facilitate the programming, flow chart with DIF 3-dimension vector radix FFT was given. And this flow chart can be extended to any integer dimensions easily. The comparison results show that, compared with multi-dimensional separable FFT, the DIF multi-dimensional vector radix FFT algorithm has lower calculation load.

Key words: multi-dimensional discrete fourier transform, Decimation in Frequency (DIF), multi-dimensional vector radix, Fast Fourier Transform (FFT), multi-dimensional separable FFT algorithm

中图分类号: