
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Programmable Pattern Matching Machine for High Speed Recognition of Regular Sets
Shin'ichi WAKABAYASHI Tohru KIKUNO Noriyoshi YOSHIDA Takashi FUJII
Publication
IEICE TRANSACTIONS (19761990)
Vol.E67
No.7
pp.363370 Publication Date: 1984/07/25
Online ISSN:
DOI:
Print ISSN: 00000000 Type of Manuscript: PAPER Category: VLSI Algorithms Keyword:
Full Text: PDF(491KB)>>
Summary:
The great technological progress in very large scale integration (VLSI) of electronic circuits has made it possible to implement a large distributed computing system on a single VLSI chip. Distributed algorithms suited for VLSI implementation are generally called 'VLSI algorithms', and many VLSI algorithms have been devised for solving several kinds of problems. This paper discusses a VLSI algorithm for pattern matching. We propose a new VLSIoriented pattern matching algorithm in which regular expressions are adopted to represent a pattern. The proposed algorithm will be implemented on a configurable multiprocessor system, which can dynamically change its interconnections among the processors according to the external inputs. Thus the pattern may be arbitrarily changed after the chip fabrication. We call such an algorithm the 'programmable' pattern matching machine (PPM for short). The programmability makes it possible for PPM to have wide applications which the previously known algorithms could hardly have. PPM consists of n(n1)/2 processors, where n is the length of a pattern, and can recognize a string of length m in m (independent of n) clock periods. PPM also has preferable properties, such as a regular structure and a simple control mechanism, for VLSI implementation.

