Vlsi Algorithms for Solving Recurrence Equations and Applications

Oscar H. Ibarra, Michael A. Palis

Research output: Contribution to journalComment/debatepeer-review

19 Scopus citations

Abstract

Optimal linear-time algorithms for solving recurrence equations on simple systolic arrays are presented. The systolic arrays use only one-way communication between processors and communicate with the external environment through only one I/O port. Because of their architectural simplicity, the arrays are well suited for direct VLSI implementation. Applications to some pattern recognition and sequence comparison problems are given. For example, it is shown that the set of (k + 2)-tuples of strings (x1, …, xk +1, y) such that y is a shuffle of x1, …, xk+1 can be recognized by a one-way k-dimensional systolic array in (k + l) n - k time. The longest common subsequence (LCS) problem and the string-to-string correction problem are also considered: the length of an LCS of k + 1 sequences can be computed by a one-way k-dimensional systolic array in (k + 1) n - k time; the edit distance between two strings can be computed by a one-way dimensional systolic array in 2n - 1 time. Applications to other related problems, e.g., dynamic time warping and optimum generalized alignment, as well as optimal-time simulations of multihead acceptors and multitape transducers are also given.

Original languageEnglish (US)
Pages (from-to)1046-1064
Number of pages19
JournalIEEE Transactions on Acoustics, Speech, and Signal Processing
Volume35
Issue number7
DOIs
StatePublished - Jul 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing

Fingerprint

Dive into the research topics of 'Vlsi Algorithms for Solving Recurrence Equations and Applications'. Together they form a unique fingerprint.

Cite this