Fast algorithms for linear prediction and system identification filters with linear phase

A general finite impulse response (FIR) filter can be used as a linear prediction filter, if given only an input sample sequence, or as a system identification model, if given the input and output sequences from an unknown system. With known correlation, the coefficients of the FIR filter that minimize the mean square error in both applications are found by solution of a set of normal equations with Toeplitz structure. Using only data samples, the coefficients that yield the least squared error in both applications are found by solution of a set of normal equations with near-to-Toeplitz structure. Computationally efficient (fast) algorithms have been published to solve for the coefficients from both types of normal equation structures. If the FIR filter is constrained to have a linear phase, then the impulse response must be symmetric. This then leads to normal equations with Toeplitz-plus-Hankel or near-to-Toeplitz-plus-Hankel structure. Fast algorithms for solving these normal equations for the filter coefficients are developed in this paper. They have computational complexity proportional to M²and parameter storage proportional to M, where M is the filter order. An application of one of these algorithms for spectral estimation concludes the paper.