Original title:
Srovnání implementačních strategií DFA
Translated title:
Comparison of Implementation Strategies of the DFA
Authors:
Balgar, Marek ; Šimek, Václav (referee) ; Kaštil, Jan (advisor) Document type: Bachelor's theses
Year:
2009
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Tato bakalářská práce podrobně popisuje výběr metod pro uložení automatu na FPGA a následnou implementaci. Byly vybrány metody bit-split, compress metoda a hashovací tabulka. Dále jsou zde porovnávány jednotlivé paměti, které automaty v reprezentaci jednotlivých metod zaberou. Jsou zde prováděny různé testy s velkou škálou vzorků. Z výsledků jsou zde pak zhodnoceny výhody a nevýhody jednotlivých metod, ale hlavně je zde obsaženo rozhodnutí, která metoda je nejvýhodnější pro uložení automatu na FPGA.
This bachelor thesis focuses upon the choices of methods, which are used to store automata on FPGA. There have been chosen these methods: bit-split, compress method and hash table. Then there are being compared the sizes of used memory, which are taken by automata in representation of these methods. The importaint part of this work is testing many kinds of samples. After the results have been achieved, I was able to examine the advantages and disadvantages of each method. Finally the analysis reveals which of the chosen methods is the best to store the automata on FPGA.
Keywords:
bit-split; C++; comparison of the memory; compress method; deterministic finite automaton; filling of the transitions; FPGA; hash table; matrix representation; regular expresions; states; symbols; testing; tests; transitions; bit-split; C++; compress metoda; deterministický konečný automat; FPGA; hash tabulka; maticová reprezentace; porovnání celkové paměti; přechody; regulární výrazy; stavy; symboly; testování; testy; zaplněnost přechodů
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/54643