Efficient implementation methodology of fast FIR filtering algorithms on DSP

A class of Finite Impulse Response (FIR) filtering algorithms based either on short Fast Fourier Transforms (FFT) or on short length FIR filtering algorithms was recently proposed. Besides the significant reduction of the arithmetic complexity, these algorithms present some characteristics which make them useful in many applications, namely a small delay processing (independent on the FIR filter length) as well as a multiply-add based computational structure. These algorithms are presented in a unified framework, thus allowing an easy combination of any of them. However, a remaining difficulty concerns the implementation of the fast algorithms on Digital Signal Processors (DSP), given the DSP finite resources (number of pointers, registers and memory), while keeping as much as possible the improvement brought by the reduction of the arithmetic complexity. This paper provides an efficient implementation methodology, by organizing the algorithm in such a way that the memory data access is optimized on a DSP. As a result, our implementation requires a constant number of pointers whatever the algorithm combination. This knowledge is used in a DSP code generator which is able to select the appropriate algorithm meeting the application constraints, as well as to generate automatically an optimized assembly code, using macro-instructions available in a DSP-dependent library. An improvement of more than 50% in terms of throughput (number of machine cycles per point) compared to the implementation of the direct convolution is generally achieved.