Digital Filters
Digital filters process sampled time-series signals (e.g., $x_0, x_1, \dots, x_N$). Unlike analog filters, they are implemented through digital signal processing. A representative type of digital filter is the linear filter.
Linear Filters
Linear filters generate output signals as a linear combination of input signals.
FIR (Finite Impulse Response) Filter
FIR filters compute output using only the current input and a finite number of past input samples. Since the impulse response has a finite length, FIR filters are always stable.
$$ y_k = w_0 x_k + w_1 x_{k-1} + \dots + w_N x_{k-N} $$
where $w_i$ are the filter coefficients.
IIR (Infinite Impulse Response) Filter
IIR filters compute output using the current input, a finite number of past input samples, and a finite number of past output samples. Since the impulse response can continue indefinitely, IIR filters may become unstable depending on the design.
$$ y_k = w_0 x_k + w_1 x_{k-1} + \dots + w_N x_{k-N} - v_1 y_{k-1} - \dots - v_M y_{k-M} $$
where $w_i, v_i$ are the filter coefficients.
Adaptive Filters
Adaptive filters are digital filters that automatically adjust (learn) their filter coefficients to adapt to changes in the environment, such as when the statistical properties of input signals change over time or when noise characteristics are unknown. The same approach to filter coefficient design can be applied to both FIR and IIR filter structures.
Input, Output, and Error of Adaptive Filters
- Input: $x_k = x(kT)$ ($k=0, 1, 2, \dots$)
- Output: $y_k = w_0 x_k + w_1 x_{k-1} + \dots + w_{N-1} x_{k-N+1}$ (This shows an FIR filter example, but the same concept applies to IIR filters)
- Desired signal: $d_k$ (ideal output signal)
- Error: $e_k = d_k - y_k$
Define the filter coefficient vector $W$ and input signal vector $X_k$ as:
$$ W = [w_0, w_1, \dots, w_{N-1}]^T $$ $$ X_k = [x_k, x_{k-1}, \dots, x_{k-N+1}]^T $$
Then the filter output $y_k$ can be written as $y_k = W^T X_k = X_k^T W$, and the error $e_k$ becomes:
$$ e_k = d_k - W^T X_k $$
Filter Coefficient Design (Wiener-Hopf Equation)
The goal of adaptive filtering is to find the optimal filter coefficients $W^o$ that minimize the mean squared error $J = \frac{1}{2} \mathbb{E}[e_k^2]$.
Expanding the mean squared error $J$:
$$ J = \frac{1}{2} \mathbb{E}[(d_k - W^T X_k)^2] = \frac{1}{2} (\mathbb{E}[d_k^2] - 2W^T \mathbb{E}[d_k X_k] + W^T \mathbb{E}[X_k X_k^T] W) $$
where:
- $R = \mathbb{E}[X_k X_k^T]$ is the autocorrelation matrix of the input signal
- $R_{dX} = \mathbb{E}[d_k X_k]$ is the cross-correlation vector between the desired signal and the input signal
This gives:
$$ J = \frac{1}{2} (\mathbb{E}[d_k^2] - 2W^T R_{dX} + W^T R W) $$
Taking the derivative of $J$ with respect to $W$ and setting it to zero yields the optimal filter coefficients $W^o$:
$$ \frac{\partial J}{\partial W} = -R_{dX} + R W = 0 $$
Therefore, the optimal filter coefficients $W^o$ satisfy:
$$ R W^o = R_{dX} $$
This relation is called the Wiener-Hopf equation. If the autocorrelation matrix $R$ is nonsingular (has an inverse), $W^o$ can be computed analytically:
$$ W^o = R^{-1} R_{dX} $$
Iterative Coefficient Update (Steepest Descent Method)
In practical systems, the statistical properties of the input signal ($R$ and $R_{dX}$) are unknown or change over time, making it difficult to solve the Wiener-Hopf equation directly. Instead, iterative algorithms like gradient descent are used to update filter coefficients incrementally.
The most basic iterative update algorithm is based on the steepest descent method:
$$ W_{k+1} = W_k - \eta \frac{\partial J}{\partial W_k} $$
where $\eta$ is the learning rate (step size) and $\frac{\partial J}{\partial W_k}$ is the gradient of the error function at the current filter coefficients.
Approximating this gradient using the instantaneous error $e_k$ yields the LMS (Least Mean Squares) algorithm:
$$ W_{k+1} = W_k + \eta e_k X_k $$
Adaptive filters are applied in various signal processing fields, including echo cancellation, noise removal, and channel equalization.
References
- Omatsu, S., “Signal Processing - Digital Filters”