A highly concurrent algorithm and pipeleined architecture for solving Toeplitz systems
- 1 February 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Acoustics, Speech, and Signal Processing
- Vol. 31 (1) , 66-76
- https://doi.org/10.1109/tassp.1983.1164051
Abstract
The design of VLSI parallel processors requires a fundamental understanding of the parallel computing algorithm and an appreciation of the implementational constraint on communications. Based on such consideration, this paper develops a highly concurrent Toeplitz system solver, featuring maximum parallelism and localized communication. More precisely, a highly parallel algorithm is proposed which achieves O(N) computing time with a linear array of O(N) processors. This compares very favorably to theO(N \log_{2} N)computing time attainable with the traditional Levinson algorithm implemented in parallel. Furthermore, to comply with the communication constraint, a pipelined processor architecture is proposed which uses only localized interconnections and yet retains the maximum parallelism attainable.Keywords
This publication has 23 references indexed in Scilit:
- A highly concurrent algorithm and pipeleined architecture for solving Toeplitz systemsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1983
- VLSI Processor Arrays for Matrix ManipulationPublished by Springer Nature ,1981
- A Matrix Data Flow Language/Architecture for Parallel Matrix Operations Based on Computational Wavefront ConceptPublished by Springer Nature ,1981
- On a generalized Szegö- Levinson realization algorithm for optimal linear predictors based on a network synthesis approachIEEE Transactions on Circuits and Systems, 1978
- Fast inversion of banded Toeplitz matrices by circular decompositionsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1978
- A view of three decades of linear filtering theoryIEEE Transactions on Information Theory, 1974
- Algorithms for Triangular Decomposition of Block Hankel and Toeplitz Matrices with Application to Factoring Positive Matrix PolynomialsMathematics of Computation, 1973
- Toeplitz Matrix Inversion: The Algorithm of W. F. TrenchJournal of the ACM, 1969
- An Algorithm for the Inversion of Finite Toeplitz MatricesJournal of the Society for Industrial and Applied Mathematics, 1964
- Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind.Journal für die reine und angewandte Mathematik (Crelles Journal), 1917