Systolic trellis automatata †

Abstract

A new type of a systolic automaton, referred to as a systolic trellis automaton, is investigated. It consists of a triangularly shaped system of hexagonally connected processors (functional elements) where the flow of data is uni-directional and there is a fixed delay in all interconnections. Systolic trellis automata can be viewed as a special case of pure systolic systems [3]. Together with systolic tree automata, [6], trellis automata now constitute the most widely studied class of systolic automata, [4],[12]. We describe a variety of programming techniques for trellis automata. The techniques might be of interest for VLSI designers in the sense that a design methodology for VLSI circuits is involved. The power of these techniques is illustrated by several examples. Trellis automata are shown to possess quite surprising 2 capabilities. The languages accepted by trellis automata have time complexity O(n ²)with respect to deterministic Turing machines, and the family of acceptable languages is closed under Boolean operations. Special attention is focused on a subclass of trellis automata with all identical processors, referred to as homogeneous. It has been shown in [2] that the homogeneous trellis automata are exactly equivalent to the real-time one-way cellular automata.