Title :
A high-speed CMOS implementation of the Winograd Fourier transform algorithm
Author_Institution :
Dept. of Nat. Defense, Defence Res. Establ. Ottawa, Ont., Canada
fDate :
8/1/1996 12:00:00 AM
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;
Journal_Title :
Signal Processing, IEEE Transactions on
