Page 111 - DSP Integrated Circuits

96 Chapter 3 Digital Signal Processing

3.16.3 Winograd's Fast Algorithm

A more recent development is the WFTA (Winograd's fast Fourier transform algo-
rithm) [6, 7, 10, 21], which requires only O(N) multiplications. However, the num-
ber of additions is larger than for the ordinary FFTs and computations of memory
addresses etc. are more irregular in the WFTA algorithm. In practice, this irregu-
larity may more than offset the reduction in the arithmetic work load. Further, the
algorithm requires that the sequence of length N can be factored into a product of
the following lengths: 2, 3, 4, 5, 7, 8, 9, and 16. Each factor corresponds to a short
Winograd algorithm.

3.16.4 IFFT (The Inverse FFT)
The inverse FFT can be computed by a simple modification of the input read
process. The IFFT is obtained by computing the FFT of the following sequence:

Thus, the first value is stored at address 0 while the rest are stored in
reverse order. This operation can easily be implemented in hardware by chang-
ing the address lines to the memory or by using an up-down counter that is
properly initiated.
Another method to compute the IFFT is to first interchange the real and imag-
inary parts, then perform the FFT, and, finally, interchange the real and imaginary
parts. We will use this method in an implementation of an FFT processor.

3.17 FFT PROCESSOR—CASE STUDY 1

As mentioned before, FFTs are used in many DSP applications. It is therefore
interesting to develop an FFT processor as a widely usable VLSI building block. In
order to be flexible so that the processor can be used in a variety of applications
without major redesign, the performance in terms of computational throughput,
word length, and transform length should be; easily modifiable.
There are two main approaches to solving this problem. We can build either
an FFT processor with characteristics that can be changed by the end-user after
manufacture, by setting some parameters, or a fixed-function processor whose
characteristics are defined at design time.
The first approach leads to a more flexible solution, but the FFT processor
must be designed on a worst-case basis. This alternative leads to the standard or
ASIC processor approaches.
In the second case, the FFT processor can be designed to meet the perfor-
mance requirements exactly, and the cost in terms of chip area and power con-
sumption can be minimized. Here we elect to design such a fixed-function high-
performance FFT processor. By selecting a reasonably general design we believe it
may serve as a basis for such a "parameterized" building block. The required chip
area and power consumption should be minimized.