3 Adaptive Linear Prediction

Figure 2.9: Block diagram of the general forward prediction problem.

The general block diagram of a forward prediction system is shown in Fig. 2.9. In this application it is required to estimate the current sample of the input sequence $x(n)$ as a linear combinations of the past $M$ input samples $x(n-\Delta), x(n-\Delta-1), \cdots, x(n-\Delta-M+1)$. To achieve this goal, the desired signal is taken as the system input $d(n) = x(n)$ and the adaptive filter input is a delayed version of the system input $x(n-\Delta)$. The filter output $y(n)$ is the required linear combination of the past input samples. The adaptive algorithm adjusts the coefficients of the adaptive filter so that the error signal $e(n) = d(n) - y(n)$ is minimized in some sense. Upon convergence the error signal $e(n)$ becomes uncorrelated with the filter input signal $x(n-\Delta)$. This indicates that $x(n)$ can be uniquely expressed as the linear combination of $y(n)$ plus the residual uncorrelated term $e(n)$. The adjustable filter in the above system is called the forward predictor, which might have any underlying filter structure. The most widely used filter structures in prediction applications are the transversal and lattice filters. Fig. 2.10 shows the forward predictor with a transversal adaptive filter of order M and the delay $\Delta = 1$. The filter output in this case is referred to as the $M^{th}$ order forward prediction of the input $x(n)$ and is given by [11]

$$y(n) = \sum \limits_{i=1}^{M} a_i \; x(n-i).$$ (17)

The error signal $e_f(n) = x(n) - y(n)$ is referred to as the $M^{th}$ order forward prediction error. Minimizing $\vert e_f(n)\vert^2$ results in a conventional Wiener filtering problem with a solution for the optimal forward predictor coefficients $\va$ given by

$$\va = \mR \; \vr .$$ (18)

Defining the autocorrelation function of the input at lag $k$ as $r(k) = E[x(n) x(n-k)]$, then $\mR$ and $\vr$ in (2.18) can be expressed as

$$\begin{array}{cc} \mR =\; \left[ \begin{array}{cccc} ... ... \vdots \\ r(m) \\ \end{array} \right] \end{array}$$ (19)

Figure 2.10: Block diagram of the transversal forward prediction problem.

The system that has its input as $x(n)$ and its output $e(n)$ is known as the forward prediction-error filter. Similarly, the backward predictor of order M has its desired signal $d(n) = x(n-M)$ and its input $x(n)$ as shown in Fig. 2.11. The backward predictor estimates $x(n-M)$ as a linear combination of $x(n), x(n-1), \cdots, x(n-M+1)$ by minimizing the error signal $e_b(n) = x(n-M) - y(n)$ in some sense. The filter output in this case is referred to as the $M^{th}$ order backward prediction of the input $x(n)$ and is given by

$$y(n) = \sum \limits_{i=1}^{M} b_i \; x(n-i+1).$$ (20)

The error signal $e_b(n)$ is referred to as the $M^{th}$ order backward prediction error. Minimizing $\vert e_b(n)\vert^2$ results in a conventional Wiener filtering problem with a solution for the optimal backward predictor coefficients $\vb$ given by

$$\vb = \mR \; \vr _b.$$ (21)

Where $\mR$ is the same as in (2.19) since $x(n)$ is considered to be a stationary process and $\vr _b$ is given by

$$\vr _b=\; \left[ \begin{array}{c} r(m) \\ r(m-1) \\ \vdots \\ r(1) \\ \end{array} \right],$$ (22)

which is the same as $\vr$ in (2.19) with the elements arranged in reverse order. This indicates that the optimal backward predictor coefficients are the same as the optimal forward predictor coefficients of the same order but arranged in reverse order such that

$$b_i = a_{M+1-i}, \;\; for \; i=1,2, \cdots, M.$$ (23)

The backward prediction-error filter is the system with input $x(n)$ and output $e(n)$. For the backward predictor with optimal coefficients it also holds that the input sequence $x(n)$ and the backward prediction error $e_b(n)$ are uncorrelated. Moreover, the $J^{th}$ order backward prediction error $e_{b_J}(n)$ for $J = 0,1,\cdots,M$ are uncorrelated with one another. This latter property is used in the lattice joint process estimators to decorrelate the input sequence samples as discussed in Section 2.2.4.

Figure 2.11: Block diagram of the transversal backward prediction problem.

Besides the transversal predictors, the lattice predictor has also found a wide range of practical applications. Transversal and lattice predictors are closely related, namely there is a unique relationship between the coefficients of the optimum (forward and backward) transversal predictor of order M and the optimum reflection coefficients of the lattice predictor of the same order as mentioned in Section 2.2.4.