Systolic arrays for the recognition of invariant segments

Share/Save/Bookmark

Katoen, Joost-Pieter and Schoenmakers, Berry (1996) Systolic arrays for the recognition of invariant segments. Science of Computer Programming, 27 (2). pp. 119-137. ISSN 0167-6423

open access
[img]
Preview
PDF
1MB
Abstract:Let P be a permutation defined on sequences of length N. A sequence of N values is said to be P-invariant when it does not change when permuted according to P. A program is said to recognize P-invariant segments when it determines for each segment of N successive input values whether it is P-invariant.

In this paper we derive a program scheme that generates efficient parallel programs for the recognition of P-invariant segments. The programs consist of a chain of cells extended with a linear number of links between non-neighbouring cells. Under reasonable conditions on P, these programs correspond to systolic arrays with both constant response time and constant latency (independent of N). Efficient systolic arrays for problems such as palindrome recognition or perfect shuffle recognition can be constructed automatically in this way. This is illustrated for the palindrome recognition problem.
Item Type:Article
Copyright:© 1996 Elsevier Science
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/17937
Official URL:http://dx.doi.org/10.1016/0167-6423(96)00009-3
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 118456