Back to Search
Start Over
A Design Method of a Regular Expression Matching Circuit Based on Decomposed Automaton
- Source :
- IEICE Transactions on Information and Systems. :364-373
- Publication Year :
- 2012
- Publisher :
- Institute of Electronics, Information and Communications Engineers (IEICE), 2012.
-
Abstract
- SUMMARY This paper shows a design method for a regular expression matching circuit based on a decomposed automaton. To implement a regular expression matching circuit, first, we convert a regular expression into a non-deterministic finite automaton (NFA). Then, to reduce the number of states, we convert the NFA into a merged-states non-deterministic finite automaton with unbounded string transition (MNFAU) using a greedy algorithm. Next, to realize it by a feasible amount of hardware, we decompose the MNFAU into a deterministic finite automaton (DFA) and an NFA. The DFA part is implemented by an off-chip memory and a simple sequencer, while the NFA part is implemented by a cascade of logic cells. Also, in this paper, we show that the MNFAU based implementation has lower area complexity than the DFA and the NFA based ones. Experiments using regular expressions form SNORT shows that, as for the embedded memory size per a character, the MNFAU is 17.17-148.70 times smaller than DFA methods. Also, as for the number of LCs (Logic Cells) per a character, the MNFAU is 1.56-5.12 times smaller than NFA methods. This paper describes detail of the MEMOCODE2010 HW/SW co-design contest for which we won the first place award.
- Subjects :
- TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Finite-state machine
Computer science
Powerset construction
String (computer science)
Automaton
Nondeterministic finite automaton with ε-moves
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Deterministic finite automaton
DFA minimization
Artificial Intelligence
Hardware and Architecture
Computer Vision and Pattern Recognition
Regular expression
Electrical and Electronic Engineering
Arithmetic
Generalized nondeterministic finite automaton
Algorithm
Software
Subjects
Details
- ISSN :
- 17451361 and 09168532
- Database :
- OpenAIRE
- Journal :
- IEICE Transactions on Information and Systems
- Accession number :
- edsair.doi...........f3d2eef686d50530086cf86715bd2c9f