A Pipelined Non-Deterministic Finite Automaton-Based String Matching Scheme Using Merged State Transitions in an FPGA.
This paper proposes a pipelined non-deterministic finite automaton (NFA)-based string matching scheme using field programmable gate array (FPGA) implementation. The characteristics of the NFA such as shared common prefixes and no failure transitions are considered in the proposed scheme. In the implementation of the automaton-based string matching using an FPGA, each state transition is implemented with a look-up table (LUT) for the combinational logic circuit between registers. In addition, multiple state transitions between stages can be performed in a pipelined fashion. In this paper, it is proposed that multiple one-to-one state transitions, called merged state transitions, can be performed with an LUT. By cutting down the number of used LUTs for implementing state transitions, the hardware overhead of combinational logic circuits is greatly reduced in the proposed pipelined NFA-based string matching scheme.
School of Electronics and Electrical Engineering, Dankook University, Yongin-si, Republic of Korea.
HyunJin
http://orcid.org/0000-0001-5017-3995
H
Kim
Advanced Communications Research Laboratory, Electronics and Telecommunications Research Institute, Daejeon, Republic of Korea.
Kang-Il
KI
Choi
D000465:Algorithms; D003198:Computer Simulation; D003201:Computers; D008128:Logic; D016571:Neural Networks, Computer
PLoS One. 2015 May 04;10(5):e0126517
25938779
PLoS One. 2015 Oct 05;10(10):e0139301
26437335