A new string search hardware architecture for VLSI

Abstract

This paper presents a new architecture for practical string search hardware design. This architecture is based on the finite state automaton design concept using a character control charge transfer model. The resultant hardware is a set of programmable sequential logic (PSL) circuits, each of which consists of a sequential logic and memory parts. The logic part is an array of logical gates, each of which is controlled by the read-out signal from the memory part, to connect the flip-flops. The memory part stores each variable-length pattern string character on a bit line by bit line basis. Then, several pattern strings in the memory part can be compared with the serial input data string in parallel, even at a non-anchor mode and an approximate matching mode. This new hardware can be easily implemented in an LSI chip, which allows 8192 pattern string storage using 1 Mb RAM cells.