Skip to main content
SpringerLink
Log in

On reduced polynomial-based split algorithms

  • Published:
Circuits, Systems and Signal Processing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N. Levinson, The Wiener RMS (root-mean-square) error criterion in filter design and prediction,J. Math. Phys., vol. 25, pp. 261–278, 1947.

    Google Scholar 

  2. J. Durbin, The fitting of time-series models,Rev. Inst. Int. Statist., vol. 28, pp. 233–244, 1960.

    Google Scholar 

  3. P. Delsarte and Y. Genin, The split Levinson algorithm,IEEE Trans. Acoust. Speech Signal Process., vol. 34, no. 3, pp. 470–478, June 1986.

    Google Scholar 

  4. 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.

    Google Scholar 

  5. 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.

    Google Scholar 

  6. 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.

  7. 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.

    Google Scholar 

  8. 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.

    Google Scholar 

  9. 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.

    Google Scholar 

  10. 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.

    Google Scholar 

  11. A. Brukstein and T. Kailath, Some matrix factorization identities for discrete inverse scattering,Linear Algebra Appl., vol. 74, pp. 157–172, 1986.

    Google Scholar 

  12. B. W. Dickinson, An inverse problem for Toeplitz matrices,Linear Algebra Appl., vol. 59, pp. 79–83, 1984.

    Google Scholar 

  13. 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.

    Google Scholar 

  14. 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.

  15. 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.

    Google Scholar 

  16. 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.

  17. 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.

  18. 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.

    Google Scholar 

  19. 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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical and Computer Engineering, Link Hall, Syracuse University, 13244-1240, Syracuse, New York, USA

    Hari Krishna

Authors
  1. Hari Krishna
    View author publications

    You can also search for this author in PubMed Google Scholar

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

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01187546

Keywords

Search

Navigation