Frequency-Domain Finite Impulse
Response
Filter Bank
The finite impulse response (FIR) filter is one of the basic operations in
signal processing. This kernel implements a set of M FIR filters. Each FIR filter
m, m ∈ {0, 1, ..., M-1 }, has a set of impulse response coefficients w
m[k], k
∈ { 0 ... K-1 }. If the length of the input vector is N,
the output of filter m, y
m, is the convolution of w
m with the input
x
m:
The frequency-domain FIR filter is implemented using fast convolution with the fast
Fourier transform (FFT). We define two data sets in
Table 1, one for a short filter and one for a long
filter. The frequency-domain implementation of the FIR filter has an
operation count of (M(10Nlog
2N+8N))
The operation counts shown in Table 1 assume complex input and output
data. In addition, the frequency-domain operation count assumes that an FFT
and inverse FFT are implemented using a radix-2 algorithm. Many other
implementations of the FFT are possible: see Van Loan for a discussion of
algorithms for performing the FFT [1]. Because such a wide variety
of FFT implementations exist, and the particular algorithm implemented in a
given library may not be known or may change with data size, it is common
to use the radix-2 operation count to calculate throughput even when a
different algorithm may be in use.
References
1. Charles F. Van Loan. Computational Frameworks for the Fast Fourier Transform. Society
for Industrial and Applied Mathematics, 1992.
