Fast Fourier transforms over finite groups by multiprocessor systems

Author

Roziner, Tatyana D. ; Karpovsky, Mark G. ; Trachtenberg, L.A.

Author_Institution

Coll. of Eng., Boston Univ., MA, USA

Volume

38

Issue

2

fYear

1990

fDate

2/1/1990 12:00:00 AM

Firstpage

226

Lastpage

240

Abstract

The authors present a method for an optimal implementation of general discrete Fourier transform (GDFT) algorithms over finite groups (Abelian and non-Abelian) in a multiprocessor environment. Tradeoffs between hardware complexity/speed and computation time are investigated for different multiprocessor implementations with local nonshared memories (unibus, complete communication network). Formulas are presented for the number of arithmetic operations, for the number of interprocessor data transfers, and for the number of communication links among the processors

Keywords

computational complexity; computerised signal processing; fast Fourier transforms; parallel algorithms; Abelian groups; DFT algorithms; FFT; computation time; fast Fourier transforms; finite groups; general discrete Fourier transform; hardware complexity/speed; interprocessor data transfers; multiprocessor systems; nonAbelian groups; Algorithm design and analysis; Arithmetic; Communication networks; Computer networks; Discrete Fourier transforms; Fast Fourier transforms; Fourier transforms; Hardware; Multiprocessing systems; Spectral analysis;

fLanguage

English

Journal_Title

Acoustics, Speech and Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

0096-3518

Type

jour

DOI

10.1109/29.103058

Filename

103058