Background Information

Contents
Home
The Problem
The ARMA Model
[Autocorrelation]
What we did
The Data
Conclusions
A Word on Decoding
Acknowledgements
Who we are

   Linear prediction methods are used extensively in the processing of random signals. Speech, although it is a random signal, has certain properties that make it suitable for simple prediction methods. This discussion will try to provide some physical intuition about the meaning of the ARMA linear prediction method and relate it to familiar material.

   On short intervals, the speech signal does not change appreciably, and is almost periodic. Speech is thus said to be a local stationary random signal, or process. In ELEC 241 and 301, we learned how to represent a signal in terms of its frequency components, or spectrum. Random signals have a finite spectrum if they are stationary (or in our case local stationary). Recall that if a signal varies rapidly with time, its Fourier representation is going to show large weighting values for the higher frequencies, and likewise for a slow varying signal at low frequencies. To compute a random signal's spectrum we need to get a measure the average rate of change of these values.

    The ARMA linear prediction model looks at a random signal's autocorrelation function, or the similarity of a signal to previous values of itself. The autocorrelation Rx(t1,t2) of a random signal X(t) is defined as the joint moment of X(t1) and X(t2):
    Rx(t1,t2) = E[X(t1)X(t2)] = òòxyf(x,y)dxdy (the bounds are from +/- infinity]

where f(x,y) is the second order pdf of X(t). In general, the autocorrelation is a function of t1 and t2. For a stationary random signal, the autocorrelation function is a measure of the rate of change of the random signal. Consider the change in the signal, from time t to t + T, we have:

P[ | X(t + T) - X(t) | > c] = P[ X(t + T) - X(t)^2 > c^2 ] < = E[ X(t + T) - X(t)^2 ] / c^2 = 2{ Rx(0) - Rx(T) } / c^2,
where we used the Markov inequality P[X >= a ] <= E[X] / a, for X nonnegative. Our results tell us that if Rx(0) - Rx(T) is small (which means that Rx(T) decreases slowly) then the probability of a large change in X(t) in T seconds is small. If a random signal changes slowly with time, then it remains correlated with itself for a long period of time, and Rx(T) decreases slowly as a function of T. On the other hand, a rapidly varying random process quickly becomes uncorrelated with itself, since Rx(T) decreases rapidly with T. The bridge between the autocorrelation function and our familiar notion of spectrum is made with the Einstein-Wiener-Khinchin theorem, which states that the power spectral density of a wide-sense stationary random process is given by the Fourier transform of the autocorrelation function. (Our process is a wide-sense stationary random process because it has a constant mean, and its autocovariance or autocorrelation is a function of t1 - t2 only). We shall now discuss the optimum linear filter.

    In our application we wish to observe a speech signal, and then predict a future value of the signal based on the observed past values. We assume that our signal has zero-mean over a certain time interval I = { t - a,..., t + b}, and we will then use a + b + 1 samples of the signal to make our estimate for the future value. This estimate will be linear, and can be written as:

                           t + b                     a

          Y[t] = S ht-nXn   = ShnXt-n      where hn are prediction coefficients.
                            n = t - a              n = -b

   We are now interested in minimizing the mean square error using this approximation. Given that the true value of the signal at time t is Zt, we want E[et^2] = E[(Zt - Yt)^2] to be minimum (e is the error at time t). It can be shown that the filter that minimizes this expression must satisfy the orthogonality condition, which states that the error must be orthogonal to all the observations X
0 = E[etXi] = E[(Zt - Yt)Xi] for all i e I, or equivalently E[ZtXi] = E[YtXi].

    Using our definition of Y[t] and our last expression, after some manipulation, we obtain that the optimum linear filter must satisfy a set of a + b + 1 linear equations given by:

                                                                                  a
                                            RZ,X(m) = ShnRx(m - n)                -b <= m <= a

                                                            n = -b
where R is the autocorrelation function we already presented.
   This set of equations are known collectively as the Yule-Walker equations. However, their solution requires that the matrix be inverted, an operation that normally takes O[N³] time. To avoid this, we can use the Levinson algorithm, which exploits the symmetries in the Toeplitz matrix, to bring the time down to O[N²].

Copyright (c) 2000 by the Oracle Gang.