Article

Article title STRUCTURE TRANSFORMATIONS OF DIGITAL STATE MACHINES FOR PATTERN SEARCH WITH MASKS
Authors D.N. Ilchenko
Section SECTION III. SOFTWARE ENGINEERING
Month, Year 06, 2014 @en
Index UDC 004.382.2
DOI
Abstract When implementing digital state machine for searching patterns with masks it is necessary to optimize its logical structure for effective implementation in field programmable gate arrays (FPGAs). In some instances, optimization leads to disruption of the correct operation of the device. This is manifested in the mistaken finding patterns in the input and in the pass pattern when using masks. There is a need in additional structure transformation of digital machines for search patterns and rules to ensure correct work with masks. To solve this problem by combining group machines search in the overall machine by minimizing the equivalent states of the structure are introduced initialization states of the patterns and the device for control initialization. This allows you to uniquely identify what pattern is searching in this moment and generate the correct transitions from states that are common in states corresponding to a specific pattern. For correct work of the search machine when using masks in patterns defined rules for the return functions to the states, which correspond to the masks of patterns. Such transformations allow for a complex optimization of the searching machine structure without limiting its functionality.

Download PDF

Keywords Fpga; digital state machine; pattern search; mask of pattern; optimization of digital state machine structure; equivalent states; vectoring states; initialization of patterns.
References 1. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. – М.: Янус-К, 2003. – 380 с.
2. Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз: 1962. – 476 с.
3. Поликарпова Н.И., Шалыто А.А. Автоматное программирование. – СПб.: СПбГПУ, 2008. – 227 с.
4. www.xilinx.com/support/documentation/user_guides/ug364.pdf (дата обращения: 17.02.2014).
5. Хопкрофт Д., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений: Пер. с англ. – 2-е изд. – М.: Вильямс, 2002. – 528 с.
6. Мельников Б.Ф., Мельникова А.А. Многоаспектная минимизация недетерминированных конечных автоматов (Ч. I. Вспомогательные факты и алгоритмы) // Изв. вузов. Поволжский регион. Физико-математические науки. – 2011. – № 4. – С. 59-69.
7. Мельников Б.Ф., Сайфуллина М.Р. О некоторых алгоритмах эквивалентного преобразования недетерминированных конечных автоматов // Изв. вузов. Математика. – 2009. – № 4. – С. 67-71.
8. Ильченко Д.Н. Применение операции векторизации состояний для синтеза цифровых автоматов [Электронный ресурс] // Инженерный вестник Дона. – 2013. – № 4 – Режим доступа: http://www.ivdon.ru/magazine/archive/n4y2013/2028 (доступ свободный) – Загл. с
экрана. – Яз. рус.

Comments are closed.