A NEW EFFICIENT ALGORITHM TO COMPUTE THE TWO-DIMENSIONAL DISCRETE FOURIER-TRANSFORM

被引：40

作者：

GERTNER, I

机构：

[1] Israel Inst of Technology, Haifa, Isr, Israel Inst of Technology, Haifa, Isr

来源：

IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING | 1988年 / 36卷 / 07期

关键词：

DATA PROCESSING - MATHEMATICAL TECHNIQUES - Algorithms;

D O I：

10.1109/29.1627

中图分类号：

O42 [声学];

学科分类号：

070206 ; 082403 ;

摘要：

An algorithm is presented for computation of the two-dimensional discrete Fourier transform (DFT). The algorithm is based on geometric properties of the integers and exhibits symmetry and simplicity of realization. Only one-dimensional transformation of the input data is required. The transformations are independent; hence, parallel processing is feasible. It is shown that the number of distinct N-point DFTs needed to calculate N multiplied by N-point two-dimensional DFTs is equal to the number of linear congruences spanning the N multiplied by N grid. Examples for N equals 3, N equals 4, and N equals 10 are presented. A short APL code illustrating the algorithm is given.

引用

页码：1036 / 1050

页数：15