tailieunhanh - Digital Signal Processing Handbook P8

Overlap-Add and Overlap-Save Methods for Fast Convolution Block Convolution Block Recursion Overlap-Add • Overlap-Save • Use of the Overlap Methods Short and Medium Length Convolution The Toom-Cook Method • Cyclic Convolution • Winograd Short Convolution Algorithm • The Agarwal-Cooley Algorithm • The Split-Nesting Algorithm Multirate Methods for Running Convolution Convolution in Subbands Distributed Arithmetic Multiplication is Convolution • Convolution is Two Dimensional • Distributed Arithmetic by Table Lookup Ivan W. Selesnick Polytechnic University Fast Convolution by Number Theoretic Transforms Number Theoretic Transforms C. Sidney Burrus Rice University . | Selesnick . Burrus . Fast Convolution and Filtering Digital Signal Processing Handbook Ed. Vijay K. Madisetti and Douglas B. Williams Boca Raton CRC Press LLC 1999 1999 by CRC Press LLC Fast Convolution and Filtering Ivan W. Selesnick Polytechnic University C. Sidney Burrus Rice University Introduction Overlap-Add and Overlap-Save Methods for Fast Convolution Overlap-Add Overlap-Save Use of the Overlap Methods Block Convolution Block Recursion Short and Medium Length Convolution The Toom-Cook Method Cyclic Convolution Winograd Short Convolution Algorithm The Agarwal-Cooley Algorithm The Split-Nesting Algorithm Multirate Methods for Running Convolution Convolution in Subbands Distributed Arithmetic Multiplication is Convolution Convolution is Two Dimensional Distributed Arithmetic by Table Lookup Fast Convolution by Number Theoretic Transforms Number Theoretic Transforms Polynomial-Based Methods Special Low-Multiply Filter Structures References Introduction One of the first applications of the Cooley-Tukey fast Fourier transform FFT algorithm was to implement convolution faster than the usual direct method 13 25 30 . Finite impulse response FIR digital filters and convolution are defined by L 1 y n h k x n k k 0 where for an FIR filter x n is a length--N sequence of numbers considered to be the input signal h n is a length-L sequence of numbers considered to be the filter coefficients and y n is the filtered output. Examination of this equation shows that the output signal y n must be a length- N C L 1 sequence of numbers and the direct calculation of this output requires NL multiplications and approximately NL additions actually N 1 L 1 . If the signal and filter length are both length-N we say the arithmetic complexity is of order N2 O N2 . Our goal is calculate this convolution or filtering faster than directly implementing . The most common way to achieve fast convolution is to section or block the .