Digital filters with thinned numerators

An algorithm is described for designing digital filters that require few multiplies to produce good frequency response. The process of reducing the number of multiplies needed to implement a digital filter is called thinning. The thinning algorithm uses Dynamic Programming techniques to optimally approximate a desired Finite Impulse Response (FIR) filter with another FIR filter that requires significantly fewer non-zero coefficients to produce similar frequency response characteristics. The effects of coefficient quantization and finite-precision computer arithmetic upon the thinned filter structure are also described. Examples of thinned narrowband, broadband, lowpass, and bandpass filters are given. Several of these thinned filters require fewer than one-third the number of multiplies required for the corresponding unthinned filter while still retaining desirable frequency response characteristics