Short note: Linear prediction theory

Linear prediction estimates the present sample of a signal as a linear combination of its past samples. It is the basis of DPCM, ADPCM and speech coders (LPC), because only the small prediction error needs to be transmitted.

Predictor. With $p$ past samples:

$$\hat{x}[n] = \sum_{k=1}^{p} w_k\, x[n-k]$$

The prediction error is

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

x[n] --+------------------>( + )--> e[n]
       |                     ^ -
       v                     |
   [z^-1]->[z^-1]-> ... ->[z^-1]   (tapped delay line)
     |w1     |w2            |wp
     +-------+---- ... -----+--> sum = x^[n]

Optimum coefficients. The weights are chosen to minimise the mean-square error

$$J = E\{e^2[n]\} = E\left\{\left(x[n] - \sum_{k=1}^{p} w_k x[n-k]\right)^2\right\}$$

Setting $\partial J/\partial w_k = 0$ gives the normal (Wiener–Hopf) equations:

$$\sum_{j=1}^{p} w_j\, R_x(k-j) = R_x(k), \qquad k = 1, 2, \ldots, p$$

or in matrix form $\mathbf{R}\mathbf{w} = \mathbf{r}$, so $\mathbf{w}_o = \mathbf{R}^{-1}\mathbf{r}$, where $R_x(k)$ is the autocorrelation of the input. The minimum error is

$$J_{min} = R_x(0) - \mathbf{r}^T\mathbf{w}_o$$

Example: first-order predictor ($p = 1$): $w_1 = R_x(1)/R_x(0) = \rho$, and $J_{min} = R_x(0)(1-\rho^2)$. For highly correlated speech ($\rho \approx 0.9$), the error variance is only 19% of the signal variance.

Key points:

• Prediction gain $G_p = \sigma_x^2/\sigma_e^2$ gives an SQNR improvement in DPCM of $10\log G_p$ dB (typically 4–11 dB for speech).
• If the statistics change with time, an adaptive predictor updates the weights (e.g. by the LMS algorithm), as in ADPCM.
• In DPCM the predictor works on quantised samples, so transmitter and receiver predictions stay identical.