Introduction

The most common type of filter dealt with in practice is a linear, causal, and time-invariant operator on the vector space consisting of arbitrary real-valued functions of time. Since we are dealing with the space of functions of time, we will use the terms vector, function, and signal interchangeably. When time is a continuous variable, the vector space is infinite-dimensional even when time is restricted to a finite interval. Digital filters are simpler in many ways theoretically because finite-time digital signals occupy a finite-dimensional vector space. Furthermore, every linear operator on the space of digital signals may be represented as a matrix.^H.1If the range of time is restricted to N samples then the arbitrary linear operator is an N by N matrix. In the discussion that follows, we will be exclusively concerned with the digital domain. Every linear filter will be representable as a matrix, and every signal will be expressible as a column vector.

Linearity implies the superposition principle which is presently indispensible for a general filter response analysis. The superposition principle states that if a signal $X$ is represented as a linear combination of signals $\{x_1,x_2,\ldots\}$ , then the response $Y$ of any linear filter $H$ may written as the same linear combination of the signals $\{y_1,y_2,\ldots\}$ where $y_i=Hx_i$ . More generally,

$$Y = HX = H\sum_{i=-\infty }^\infty \alpha_ix_i = \sum_{i=-\infty }^\infty \alpha_iHx_i = \sum_{i=-\infty }^\infty \alpha_iy_i .$$

A set of signals that can be used to express every signal in the space is called a set of basis functions. An example of a basis set is the familiar set of sinusoids at all frequencies. The most crucial use of linearity for our purposes is the representation of an arbitrary linear filter as a matrix operator.

Causality means that the filter output does not depend on future inputs. This is necessary in analog filters where time is a real entity, but for digital filters causality is highly unnecessary unless the filter must operate in real-time. Requiring a filter to be causal results in a triangular matrix representation.

A time-invariant filter is one whose response does not depend on the time of excitation. This allows superposition in time in addition to the superposition of component functions given by linearity. A matrix representing a linear time-invariant filter is Toeplitz (each diagonal is constant). The chief value of time-invariance is that it allows a linear filter to represented by its impulse response which, for digital filters, is the response elicited by the signal $(1,0,0,\ldots)$ . A deeper consequence of superposition in time together with superposition of component signal responses is the fact that every stable linear time invariant filter emits a sinusoid at frequency $f$ in response to an input sinusoid at frequency $f$ after sufficient time for start-up transients to settle. For this reason sinusoids are called eigenfunctions of linear time-invariant systems. Another way of putting it is that a linear time-invariant filter can only modify a sinusoidal input by a constant scaling of its amplitude and a constant offset in its phase. This is the rationale behind Fourier analysis. The Laplace transform of the impulse response gives the transfer function and the Fourier transform of the impulse response is the frequency response. It is important to note that relaxing time-invariance only prevents us from using superposition in time. Consequently, while we can no longer uniquely characterize a filter in terms of its impulse response, we may still characterize it in terms of its basis function response.

This will be developed below for the particular basis functions used in the Discrete Fourier Transform (DFT). These basis functions are defined for the N-dimensional discrete-time signal space as

$$W_N^n(k)=e^{j2\pi \frac{kn}{N}},\qquad k,n = 0,1,2,\ldots N-1$$

where $n$ is the time index, and $k$ is the discrete frequency index. To be more concrete we could define $\omega_k=2\pi f_s k/N$ as the $k^{th}$ raidan frequency and $t_n=nT$ as the time of the $n^{th}$ sample, where the sampling rate $f_s=1/T$ . Note that $W_N^n(k)$ is a sampled version of the continuous time sinusoidal basis function $e^{j\omega t}$ used in the Fourier transform. There are no eigenfunctions for general time-varying filters and so there is no fundamental reason to prefer the Fourier basis over any other basis. The basis set may be chosen according to the most natural decomposition of the input signal space without a penalty in complexity.