SYSTOLIC ARRAYS FOR THE RECOGNITION OF PERMUTATION-INVARIANT SEGMENTS

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 permu ted according to P, A program is said to recognize P-invariant segment s when it determines for each segment of N successive input values whe ther it is P-invariant. In this paper we derive a program scheme that generates efficient parallel programs for the recognition of P-invaria nt segments. The programs consist of a chain of cells extended with a linear number of links between non-neighbouring cells. Under reasonabl e conditions on P, these programs correspond to systolic arrays with b oth constant response lime and constant latency (independent of N). Ef ficient 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.