III Международная студенческая научная конференция Студенческий научный форум - 2011

Задача кодирования состояний является одной из основных задач канонического метода структурного синтеза управляющих автоматов. Кодирование заключается в установлении взаимно-однозначного соответствия между множеством состояний автомата А={а₁,...,а_m} и множеством R-компонентных векторов {К₁, ...,К_m),  К_m = (е_m1, ..., emR}, где е_mR - состояние r-го элемента памяти r =1,...,R.

Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Так, если автомат переходит из состояния а_m с кодом 0101 в состояние а_s, с кодом 1001, то это означает, что триггер Т₁, переходит из состояния 0 в состояние 1, триггер Т₂ - из состояния 1 в состояние 0, а состояния триггеров Т₃, и Т₄ не изменяются.

Целью данной работы является  анализ влияния кодирования состояний автомата на сложность комбинационной схемы. Большое число работ, начало которых было по­ложено Хартманисом и Стирном, посвящено получению такого кодирования, при котором уменьшается зависимость функций возбуждения памяти от переменных обратной связи. Хартманис  и Стирн показали, что этот подход тесно связан с существо­ванием определенных разбиений множества состояний автомата. Как правило, нахожде­ние вариантов кодиро­вания состояний, кото­рые обеспечивают ос­лабленную функцио­нальную зависимость для функций возбужде­ния, дает более эко­номичную схему, чем при других типах коди­рования.  Методы кодирования состояний с ослаблением функциональной зависимости тесно связаны с декомпозицией автомата.

В процессе работы были исследованы два метода кодирования состояний автомата. В первом случае состояния автомата по возможности были закодированы соседними кодами. Во втором применялся эвристический алгоритм кодирования состояний, минимизирующий суммарное число изменений элементов памяти на всех переходах автомата [1]. При таком критерии уменьшается сложность схем, реализующих дизъюнкции на входах элементов памяти, вследствие чего  минимизируется комбинационная схема.  Для данного способа  кодирования состояний был разработан алгоритм (рисунок 1) и программа  в среде Delphi 7.0. 

Код для цитирования: Скопировать