While contemplating the convolution relationships in Eq. (5-31) and Figure 5-41, digital signal processing practitioners realized that convolution could sometimes be performed more efficiently using FFT algorithms than it could be using the direct convolution method. This FFT-based convolution scheme, called fast convolution, is diagrammed in Figure 13-28.

Figure 13-28. Processing diagram of fast convolution.

The standard convolution equation for an M-tap nonrecursive FIR filter, given in Eq. (5-6) and repeated here, is

where h(k) is the impulse response sequence (coefficients) of the FIR filter and the * symbol indicates convolution. It has been shown that when the final y(n) output sequence has a length greater than 30, the process in Figure 13-28 requires fewer multiplications than implementing the convolution expression in Eq. (13-67) directly. Consequently, this fast convolution technique is a very powerful signal processing tool, particularly when used for digital filtering. Very efficient FIR filters can be designed using this technique because, if their impulse response h(k) is constant, then we don't have to bother recalculating H(m) each time a new x(n) sequence is filtered. In this case the H(m) sequence can be precalculated and stored in memory.

The necessary forward and inverse FFT sizes must of course be equal, and are dependent upon the length of the original h(k) and x(n) sequences. Recall from Eq. (5-29) that if h(k) is of length P and x(n) is of length Q, the length of the final y(n) sequence will be (P+Q–1). For this fast convolution technique to give valid results, the forward and inverse FFT sizes must be equal and greater than (P+Q–1). This means that h(k) and x(n) must both be padded with zero-valued samples, at the end of their respective sequences, to make their lengths identical and greater than (P+Q–1). This zero padding will not invalidate the fast convolution results. So to use fast convolution, we must choose an N-point FFT size such that N (P+Q–1) and zero pad h(k) and x(n) so they have new lengths equal to N.

An interesting aspect of fast convolution, from a hardware standpoint, is that the FFT indexing bit-reversal problem discussed in Sections 4.5 and 4.6 is not an issue here. If the identical FFT structures used in Figure 13-28 result in X(m) and H(m) having bit-reversed indices, the multiplication can still be performed directly on the scrambled H(m) and X(m) sequences. Then an appropriate inverse FFT structure can be used that expects bit-reversed input data. That inverse FFT then provides an output y(n) whose data index is in the correct order!


Prev don't be afraid of buying books Next

Chapter One. Discrete Sequences and Systems

Chapter Two. Periodic Sampling

Chapter Three. The Discrete Fourier Transform

Chapter Four. The Fast Fourier Transform

Chapter Five. Finite Impulse Response Filters

Chapter Six. Infinite Impulse Response Filters

Chapter Seven. Specialized Lowpass FIR Filters

Chapter Eight. Quadrature Signals

Chapter Nine. The Discrete Hilbert Transform

Chapter Ten. Sample Rate Conversion

Chapter Eleven. Signal Averaging

Chapter Twelve. Digital Data Formats and Their Effects

Chapter Thirteen. Digital Signal Processing Tricks

Appendix A. The Arithmetic of Complex Numbers

Appendix B. Closed Form of a Geometric Series

Appendix C. Time Reversal and the DFT

Appendix D. Mean, Variance, and Standard Deviation

Appendix E. Decibels (dB and dBm)

Appendix F. Digital Filter Terminology

Appendix G. Frequency Sampling Filter Derivations

Appendix H. Frequency Sampling Filter Design Tables

Understanding Digital Signal Processing
Understanding Digital Signal Processing (2nd Edition)
ISBN: 0131089897
EAN: 2147483647
Year: 2004
Pages: 183 © 2008-2020.
If you may any questions please contact us: