Multiplierless Implementation of Rotators and FFTs
- PDF / 625,521 Bytes
- 8 Pages / 600 x 792 pts Page_size
- 18 Downloads / 148 Views
Multiplierless Implementation of Rotators and FFTs Malcolm D. Macleod QinetiQ Ltd., St. Andrews Road, Malvern, Worcestershire WR14 3PS, UK Email: [email protected] Received 9 December 2004; Revised 26 June 2005; Recommended for Publication by Markus Rupp Complex rotators are used in many important signal processing applications, including Cooley-Tukey and split-radix FFT algorithms. This paper presents methods for designing multiplierless implementations of fixed-point rotators and FFTs, in which multiplications are replaced by additions, subtractions, and shifts. These methods minimise the adder-cost (the number of additions and subtractions), while achieving a specified level of accuracy. FFT designs based on multiplierless rotators are compared with designs based on the multiplierless implementation of DFT matrix multiplication. These techniques make possible VLSI implementations of rotators and FFTs which could achieve very high speed and/or power efficiency. The methods can be used to provide any chosen accuracy; examples are presented for 12 to 26 bit accuracy. On average, rotators are shown to be implementable using 10, 12, or 15 adders to achieve accuracies of 12, 16, or 20 bits, respectively. Keywords and phrases: FFT implementation, rotator implementation, multiplierless design, VLSI.
1.
INTRODUCTION
Complex rotators, which multiply input values by e jθ for some θ, are used in many important applications, including fast fourier transform (FFT) algorithms, where they are also known as “twiddle factors” [1]. Many current systems require embedded FFTs, including orthogonal frequencydivision multiplexing modems for digital broadcasting, wireless networking, and telecommunications, and many more potential applications are anticipated. Because the real and imaginary parts of e jθ are in general irrational, the computation of such rotations, and of the FFT, is inherently inexact [1], so the requirement is always to achieve sufficient accuracy for an intended application. To reduce power consumption and increase speed, fixed-point arithmetic is often used. Until recently, research into implementation of these functions has concentrated on architectures such as programmable DSP ICs, containing multiplier-accumulators. With recent advances in VLSI technology, “multiplierless” algorithms now provide the option of further lowering power consumption and IC area, or greatly increasing throughput. In multiplierless algorithms, general-purpose multipliers are replaced by binary shifts, adders, subtracters, negaters, and stores. As is common when considering VLSI hardware implementations, binary shifts and data moves are treated as costless, while stores and negaters are assumed to This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
be significantly less costly (in area or power consumption) than adders. Therefore subtracters are assumed to have the same cost as a
Data Loading...
