Bit-sequential array for pattern matching

1 January 1986

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the IEEE

Vol. 74 (10) , 1465-1466
https://doi.org/10.1109/proc.1986.13652

Abstract

This letter presents the design and analysis of a bit-sequential array for pattern matching applications. The architecture makes multiple use of each data sample, has built-in concurrency and pipelining, and is based on a highly modular design with only nearest neighbor connections between array modules. The array computes all occurrences of a pattern of length m, in the string of length n, in O(m + n) time and O(m) hardware. The pattern and the string are fed in sequentially and the match indicators come out in the same fashion, leading to a significant reduction in silicon area.

Keywords

PATTERN MATCHING
COMPUTER ARCHITECTURE
HARDWARE
NEAREST NEIGHBOR SEARCHES
PATTERN ANALYSIS
CONCURRENT COMPUTING
PIPELINE PROCESSING
SIGNAL RECONSTRUCTION
SOFTWARE ALGORITHMS
INFORMATION SYSTEMS

This publication has 0 references indexed in Scilit: