Parallel Discrete Fourier Transform for Fast FIR Filtering Based on Overlapped-save Block Structure

Authors: Ying-Wen Bai, Ju-Maw Chen

Abstract:

To successfully provide a fast FIR filter with FTT algorithms, overlapped-save algorithms can be used to lower the computational complexity and achieve the desired real-time processing. As the length of the input block increases in order to improve the efficiency, a larger volume of zero padding will greatly increase the computation length of the FFT. In this paper, we use the overlapped block digital filtering to construct a parallel structure. As long as the down-sampling (or up-sampling) factor is an exact multiple lengths of the impulse response of a FIR filter, we can process the input block by using a parallel structure and thus achieve a low-complex fast FIR filter with overlapped-save algorithms. With a long filter length, the performance and the throughput of the digital filtering system will also be greatly enhanced.

Keywords: FIR Filter, Overlapped-save Algorithm, ParallelStructure

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1059471

References:

[1] M. Aziz, S. Boussakta, D.C.McLernon, “Parallelisation of the 1-D block filter algorithm to run on multiple DSPs", 9th International Conference on Electronics, Circuits and Systems, Vol. 3, 15-18 Sept. 2002, pp. 943-946.
[2] I. D. Moldovan, “Parallel processing from applications to systems", Morgan Kaufmann Publishers Inc., 1993, ch. 1.
[3] P. P.Vaidyanathan, “Multirate Systems and Filter Banks", Englewood Cliffs, NJ, Prentice-Hall, 1993, ch. 10.
[4] P. P. Vaidyanathan and S. K. Mitra, “Polyphase networks, block digital filtering, LPTV systems, and alias-free QMF banks: a unified approach based on pseudocirculants", IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. 36, Issue: 3, March 1988, pp. 381-391.
[5] Ing-Song Lin and S. K. Mitra, “Overlapped block digital filtering", IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, Vol. 43, Issue: 8, Aug. 1996, pp. 586-596.
[6] Ing-Song Lin and S. K. Mitra, “Fast FIR Filtering Algorithms Based On Overlapped Block Structure", 1993 IEEE International Symposium on Circuits and Systems, 3-6 May 1993, pp. 363-366.
[7] Sanjit K. Mitra, “Digital Signal Processing: A Computer-Based Approach", McGraw-Hall, 2001, ch. 3.