A Highly Concurrent Algorithm and Pipelined Architecture for Solving Toeplitz Systems

Sun Yuan Kung, Yu Hen Hu

Research output: Contribution to journalArticlepeer-review

95 Scopus citations

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 the O(N log2N) 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.

Original languageEnglish (US)
Pages (from-to)66-76
Number of pages11
JournalIEEE Transactions on Acoustics, Speech, and Signal Processing
Volume31
Issue number1
DOIs
StatePublished - Feb 1983
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing

Fingerprint Dive into the research topics of 'A Highly Concurrent Algorithm and Pipelined Architecture for Solving Toeplitz Systems'. Together they form a unique fingerprint.

Cite this