FFT and convolution algorithms on DSP microprocessors

This paper develops an approach to deriving special FFT and convolution algorithms, considering the architecture of special-purpose DSP micros with a hardware multiplier and an adjacent accumulator. Because of the build-in accumulator, it is possible to combine multiplications and additions into one operation, and hence the optimality criterion is redefined to minimize the total number of additions, multiplications and combined multiply-additions, which results in new interesting algorithms. The structure of the algorithms depends strongly on the nature of N - the sequence length. Where most conventional fast algorithms decompose convolutions completely, it turns out that because the adjacent accumulator can hides some of the additions, they should only be partly decomposed. The decomposition is done by index mapping and the implementation uses Winograd´s ideas. Discrete Fourier transforms are also only partly decomposed, in contrast to most algorithms. The DFTs are converted into convolutions, and the convolutions are implemented as block processing. Comparisons show up to a 35 % improvement in execution speed.