A high-speed CMOS implementation of the Winograd Fourier transform algorithm

Author

Lavoie, Pierre

Author_Institution

Dept. of Nat. Defense, Defence Res. Establ. Ottawa, Ont., Canada

Volume

44

Issue

8

fYear

1996

fDate

8/1/1996 12:00:00 AM

Firstpage

2121

Lastpage

2126

Abstract

A technique for partitioning hardware implementations of the Winograd (1976) Fourier transform algorithm (WFTA) into separate modules is presented. Instead of the prime factor algorithm, this technique is based on the Winograd nesting method and thus preserves the minimum number of multiplications in the WFTA. An integrated circuit capable of computing over 2 million 20-point discrete Fourier transforms/s is described. Using five of these integrated circuits, the partitioning technique can be applied to increase the transform length to 60 points

Keywords

CMOS digital integrated circuits; digital signal processing chips; discrete Fourier transforms; Winograd Fourier transform algorithm; Winograd nesting method; discrete Fourier transforms; hardware implementations; high-speed CMOS IC; integrated circuit; multiplications; partitioning technique; transform length; Adaptive signal processing; Array signal processing; Concurrent computing; Fourier transforms; Hardware; Jacobian matrices; Least squares methods; Partitioning algorithms; Signal processing algorithms; Systolic arrays;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/78.533738

Filename

533738