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

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.

• Ying-Wen Bai
• Ju-Maw Chen

• FIR Filter
• Overlapped-save Algorithm
• ParallelStructure

<p>[1] M. Aziz, S. Boussakta, D.C.McLernon, &ldquo;Parallelisation of the 1-D block filter algorithm to run on multiple DSPs&quot;, 9th International Conference on Electronics, Circuits and Systems, Vol. 3, 15-18 Sept. 2002, pp. 943-946.
[2] I. D. Moldovan, &ldquo;Parallel processing from applications to systems&quot;, Morgan Kaufmann Publishers Inc., 1993, ch. 1.
[3] P. P.Vaidyanathan, &ldquo;Multirate Systems and Filter Banks&quot;, Englewood Cliffs, NJ, Prentice-Hall, 1993, ch. 10.
[4] P. P. Vaidyanathan and S. K. Mitra, &ldquo;Polyphase networks, block digital filtering, LPTV systems, and alias-free QMF banks: a unified approach based on pseudocirculants&quot;, 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, &ldquo;Overlapped block digital filtering&quot;, 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, &ldquo;Fast FIR Filtering Algorithms Based On Overlapped Block Structure&quot;, 1993 IEEE International Symposium on Circuits and Systems, 3-6 May 1993, pp. 363-366.
[7] Sanjit K. Mitra, &ldquo;Digital Signal Processing: A Computer-Based Approach&quot;, McGraw-Hall, 2001, ch. 3.</p>