A simplified computational algorithm for implementing FIR digital filters

An N-point finite impulse response (FIR) digital filter, when implemented in software, generally requires N multiplications, N additions, and (N - 1) shifts per output sample. An obvious simplification is to implement the shift register required to store x(n) to x(n - N + 1) using a moving pointer, thereby eliminating the (N - 1) shifts per sample required in the most straightforward implementation. However, this simplification requires a check on the index of every sample to see if the end of the linear storage array has been passed, thereby voiding most of the gain in speed which was obtained. A simple technique is discussed for trading N storage locations for the (N - 1) shifts (or the (N - 1) index checks), thereby leading to an implementation in which only N multiplications, N additions, and one indexing operation are required per output sample. For implementing symmetric (i.e., linear phase) FIR filters, the resulting savings is even somewhat greater because two index pointers are required, and each must normally be checked to see that it remains within the bounds of the array.