Designing Combinational Circuits for Scattered Pattern Matching

A combinational module for scattered pattern matching tests whether the digits of a given pattern occur in the proper order and multiplicity within a given search string. We present a unifying high-level synthesis of linear and tree-structured combinational networks for scattered pattern matching based on the theory of list homomorphisms. From a predicate logic specification, we develop standard implementations for tree-structured modules processing the input digits of the search string in parallel. The tree-structured design is systematically specialized to iterative networks processing the search string sequentially from left to right or vice versa. The formal design is parameterized with the type of digits to be matched. Throughout the paper, we explicate functional methods for the structured description of combinational circuits with higher-order list functions.