Comments on "Method of flow graph simplification for the 16-point discrete Fourier Transform"

Author

Johnson, Steven G. ; Frigo, Matteo

Author_Institution

Massachusetts Inst. of Technol., Cambridge, MA, USA

Volume

54

Issue

4

fYear

2006

fDate

4/1/2006 12:00:00 AM

Firstpage

1562

Abstract

The paper "Method of Flow Graph Simplification for the 16-Point Discrete Fourier Transform" by Grigoryan and Bhamidipati presents a "paired transform" fast Fourier transform (FFT) algorithm that is claimed to perform the size-8 and size-16 complex-data discrete Fourier transform (DFT) with 44 and 140 arithmetic operations, respectively. If true, this count would be less than the 56 and 168 operations achieved in the best pre-existing (split-radix) methods. Grigoryan and Bhamidipati\´s count of real additions is erroneous, however, and this comment shows that their algorithm actually has arithmetic complexity identical to that of standard split-radix algorithms.

Keywords

discrete Fourier transforms; signal processing; 16-point discrete Fourier transform; fast Fourier transform; flow graph simplification; split-radix algorithms; Algorithm design and analysis; Arithmetic; Discrete Fourier transforms; Fast Fourier transforms; Flow graphs; Inspection; Laboratories; Signal processing; Arithmetic complexity; discrete Fourier transforms;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/TSP.2006.870622

Filename

1608569