Abstract
In this work we analyze the mathematical structure associated with the split algorithms for computing the reflection coefficients for a given real, symmetric, positive-definite Toeplitz matrix. A new form of three-term recurrence relation is derived and computationally efficient alternatives to the Levinson-Durbin, Schur, lattice, and normalized lattice algorithms are obtained. The computational complexity of the new algorithms is the same as those of the split algorithms described in the recent literature. The relationships between the various algorithms are also established. These algorithms also provide further insight into the mathematical properties of the structurally rich Toeplitz matrices.
Similar content being viewed by others
References
N. Levinson, The Wiener RMS (root-mean-square) error criterion in filter design and prediction,J. Math. Phys., vol. 25, pp. 261–278, 1947.
J. Durbin, The fitting of time-series models,Rev. Inst. Int. Statist., vol. 28, pp. 233–244, 1960.
P. Delsarte and Y. Genin, The split Levinson algorithm,IEEE Trans. Acoust. Speech Signal Process., vol. 34, no. 3, pp. 470–478, June 1986.
Y. Bistritz, Zero location with respect to the unit circle of discrete time linear system polynomials,Proc. IEEE, vol. 27, pp. 1131–1142, Sept. 1984.
J. LeRoux and C. Gueguen, A fixed point computation of partial correlation coefficients,IEEE Trans. Acoust. Speech Signal Process., vol. 25, pp. 257–259, 1977.
F. Itakura and S. Saito, Digital filtering techniques for speech analysis and synthesis,Proc. 7th Int. Congr. on Acoustics, paper 25-C-1, pp. 261–264, Budapest, 1971.
A. H. Gray and J. D. Markel, A normalized digital filter structure,IEEE Trans. Acoust. Speech Signal Process., vol. 23, no. 3, pp. 268–277, June 1975.
P. Delsarte and Y. Genin, On the splitting of classical algorithms in linear prediction theory,IEEE Trans. Acoust. Speech Signal Process., vol. 35, no. 5, pp. 645–653, May 1987.
G. Cybenko, The numerical stability of the Levinson-Durbin algorithm for Toeplitz systems of equations,SIAM J. Sci. Statist. Comput., vol. 1, pp. 303–319, 1980.
R. E. Caflisch, An inverse problem for Toeplitz matrices and the synthesis of discrete transmission lines,Linear Algebra Appl., vol. 38, pp. 207–225, 1981.
A. Brukstein and T. Kailath, Some matrix factorization identities for discrete inverse scattering,Linear Algebra Appl., vol. 74, pp. 157–172, 1986.
B. W. Dickinson, An inverse problem for Toeplitz matrices,Linear Algebra Appl., vol. 59, pp. 79–83, 1984.
B. W. Dickinson, Properties and applications of Gaussian autoregressive processes in detection theory,IEEE Trans. Inform. Theory, vol. 27, no. 3, pp. 343–347, May 1981.
Y. Bistritz, H. Lev-Ari, and T. Kailath, Immitance-domain Levinson algorithms,Proc. Int. Conf. on Acoust., Speech, and Signal Process., pp. 253–256, Tokyo, April 1986.
B. Krishna and H. Krishna, Computationally efficient reduced polynomial based algorithms for hermitian Toeplitz matrices,SIAM J. Appl. Math., vol. 49, no. 4, pp. 1275–1282, August 1989.
A. K. Kok, D. G. Manolakis, and U. K. Ingle, Efficient algorithms for 1-D and 2-D non-causal autoregressive system modelling,Proc. IEEE Int. Conf. on Acoust., Speech, and Signal Process., pp. 1977–1980, Dallas, 1987.
D. C. Farden and J. R. Bellegarda, A fast algorithm for the recursive design of linear phase filters,Proc. IEEE Int. Conf. on Acoust., Speech, and Signal Process., pp. 916–919, Dallas, 1987.
H. Krishna and S. D. Morgera, The Levinson recurrence and fast algorithms for solving Toeplitz system of linear equations,IEEE Trans. Acoust. Speech Signal Process., vol. 35, no. 6, pp. 839–848, June 1987.
K. P. Bube and R. Burridge, The one-dimensional inverse problem of reflection seismology,SIAM Rev., vol. 25, no. 4, pp. 497–559, Oct. 1983.
Author information
Authors and Affiliations
Additional information
This research was supported by the SDIO/IST and managed by the Army Research Office under Contract DAAL03-87-K-0027.
Rights and permissions
About this article
Cite this article
Krishna, H. On reduced polynomial-based split algorithms. Circuits Systems and Signal Process 10, 263–284 (1991). https://doi.org/10.1007/BF01187546
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01187546