Signals: Linear Prediction and Coding

Linear prediction is a cornerstone of modern signal processing, enabling efficient compression and analysis by exploiting the predictability of signals. From speech coding in mobile phones to financial time series forecasting, this technique reduces data rates while preserving essential information. Mastering linear prediction allows you to build systems that transmit, store, and analyze signals with remarkable efficiency.

The Linear Prediction Model and Prediction Error

At its core, linear prediction models a signal by approximating its current value as a weighted sum of its past samples. This is based on the observation that many real-world signals, like speech or economic data, exhibit short-term correlation where future values are influenced by recent history. Formally, for a discrete-time signal $x[n]$, the predicted value $\hat{x}[n]$ is calculated as:

$$\hat{x}[n]=\sum _{k=1}^p{a}_{k}x[n-k]$$

Here, $p$ is the model order, and $a_k$ are the linear prediction coefficients or weights. The difference between the actual sample $x[n]$ and its predicted value is the prediction error $e[n]$:

$$e[n]=x[n]-\hat{x}[n]$$

This error sequence is crucial because it carries the new, unpredictable information in the signal. In an ideal linear prediction system, if the model perfectly captures the signal's correlations, the prediction error becomes a white noise sequence—uncorrelated and containing the minimal information necessary to reconstruct the original signal. This principle is the foundation for compression: instead of transmitting the full signal $x[n]$, you can transmit the smaller set of coefficients $a_k$ and the compact error signal $e[n]$, achieving significant data reduction.

Computing Optimal Coefficients: The Levinson-Durbin Recursion

The goal is to find the set of coefficients $a_k$ that minimize the average power of the prediction error $E[e^2[n]]$. This minimization leads to a set of equations known as the Yule-Walker equations, which relate the optimal coefficients to the signal's autocorrelation function. Solving these directly requires matrix inversion, which is computationally intensive. The Levinson-Durbin recursion provides an elegant and efficient $O(p^2)$ algorithm to compute these optimal coefficients recursively.

This recursion works by solving for predictors of increasing order. It starts with a first-order model ( $p=1$ ) and iteratively refines the coefficients for higher orders, using the reflection coefficients (also known as partial correlation or PARCOR coefficients). The steps are:

1. Initialize the error energy for order 0 as the signal variance: $E_0=r[0]$, where $r[m]$ is the autocorrelation at lag $m$.
2. For each order $i$ from 1 to $p$:

a. Compute the reflection coefficient $k_i$ using the current autocorrelation and previous coefficients. b. Update the $i$-th coefficient: $a_i^{(i)}=k_i$. c. Update the lower-order coefficients: $a_j^{(i)}=a_j^{(i-1)}-k_i{a}_{i-j}^{(i-1)}$ for $j=1,...,i-1$. d. Update the error energy: $E_i=(1-k_i^2)E_{i-1}$.

This algorithm not only computes the coefficients but also yields the progressively minimized error energies $E_i$, which is vital for analysis. It's numerically stable for positive definite autocorrelation matrices and is widely implemented in software libraries for signal processing.

Applications: Speech Coding and Connection to AR Modeling

One of the most successful applications of linear prediction is in speech coding, specifically in Linear Predictive Coding (LPC). The human vocal tract can be modeled as a tube whose shape determines speech sounds; this shape changes slowly relative to the speech rate. LPC uses linear prediction to estimate the vocal tract parameters (the coefficients $a_k$) from speech samples. The prediction error approximates the excitation source (e.g., glottal pulses for voiced sounds like vowels, or noise for unvoiced sounds like fricatives). By transmitting only these coefficients and a simplified error signal, LPC codecs can achieve very low bit rates, essential for early mobile phones and secure communications.

Theoretical and mathematically, linear prediction is fundamentally linked to autoregressive (AR) modeling in time series analysis. An AR model of order $p$, denoted AR($p$), expresses a value as a linear combination of its past $p$ values plus a white noise innovation term. This is identical to the linear prediction equation, where the prediction error $e[n]$ corresponds to the innovation noise. Therefore, finding the linear prediction coefficients is equivalent to estimating the parameters of an AR model for the signal. This connection allows you to use tools from statistical signal processing, like spectral estimation, where the AR model provides a high-resolution estimate of the signal's power spectrum.

Performance Analysis: Prediction Gain Versus Model Order

The effectiveness of a linear predictor is often measured by its prediction gain $G_p$, which is the ratio of the input signal power to the prediction error power. It is typically expressed in decibels (dB):

$$G_p=10{\log }_{10}\left(\frac{E[x^2[n]]}{E[e^2[n]]}\right)$$

A higher prediction gain indicates better compression potential, as the error power is smaller relative to the original signal. However, gain does not increase indefinitely with model order $p$. Initially, as $p$ increases, the predictor captures more of the signal's correlation, and gain rises sharply. Beyond a certain point, the gains diminish; the predictor starts modeling fine details or even noise specific to the training data, rather than the underlying signal structure. This is the classic bias-variance trade-off.

Analyzing prediction gain versus model order helps you select an appropriate $p$. For speech signals, orders between 8 and 12 are common, matching the number of formants (resonant frequencies) in the vocal tract. For a purely periodic signal, a very low order might suffice, while a more complex, broadband signal might require a higher order. The Levinson-Durbin recursion's intermediate error energies $E_i$ provide a direct way to plot this gain curve and identify the knee point where additional complexity yields minimal benefit.

Common Pitfalls

1. Overfitting by Choosing Excessive Model Order: A high $p$ may yield a very small error on the training data but poorly predict new samples, as it models noise rather than structure. This inflates the coefficient values without real benefit.

Correction: Use criteria like the Akaike Information Criterion (AIC) or simply observe the prediction gain curve to select an order where gain plateaus. Cross-validate on separate data segments.

1. Ignoring Signal Stationarity: Linear prediction assumes the signal is wide-sense stationary, meaning its statistical properties (like mean and autocorrelation) do not change over time. Applying a fixed predictor to a non-stationary signal (e.g., a speech sentence with both silence and voiced segments) results in poor performance.

Correction: Process the signal in short, overlapping frames where stationarity is a reasonable approximation. Update the predictor coefficients periodically for each frame, as done in speech codecs.

1. Numerical Instability in Autocorrelation Estimation: The Levinson-Durbin recursion requires an accurate estimate of the autocorrelation sequence. Using a biased estimator or having insufficient data can lead to ill-conditioned matrices, causing the recursion to produce unreliable coefficients.

Correction: Ensure you have enough signal samples relative to the model order. Use the unbiased autocorrelation estimator or apply windowing techniques when computing correlations from finite data blocks.

1. Confusing Prediction Error with Measurement Noise: The prediction error $e[n]$ contains the "innovation" or new information. In practice, signals also contain external measurement noise. A linear predictor will try to model this noise too, reducing efficiency.

Correction: Pre-process the signal with filtering if possible to reduce noise. Understand that the theoretical minimum error is bounded by the inherent innovation plus any uncorrelated noise present.

Summary

• Linear prediction models a signal's current value as a weighted sum of its past samples. The prediction error represents the unpredictable component and is key for data compression.
• The Levinson-Durbin recursion is an efficient algorithm for computing the optimal prediction coefficients by solving the Yule-Walker equations recursively, providing both coefficients and progressive error energies.
• In speech coding (LPC), linear prediction separates vocal tract parameters (coefficients) from excitation (error), enabling low-bit-rate transmission.
• Linear prediction is mathematically equivalent to autoregressive (AR) modeling, linking it to spectral estimation and time series analysis.
• Prediction gain measures compression efficiency, but it plateaus with increasing model order; selecting the right order involves balancing accuracy with model complexity to avoid overfitting.
• Successful implementation requires attention to signal stationarity, accurate autocorrelation estimation, and distinguishing between innovation error and external noise.