2014-02-02
639
Реализация конечных автоматов сводится к синтезу соответствующей комбинационной схемы, преобразующей входные переменные x( n ) и s( n ) в выходные переменные y( n ) и s( n +1) в соответствии с заданными характеристическими s( n +1)= d (x( n ), s( n )) и y( n ) = l (x( n ), s( n )). Для сохранения состояний s( n +1) до следующего такта в цепь обратной связи вводится необходимое количество элементов памяти.
При реализации автоматов в двоичном структурном алфавите можно использовать методы синтеза комбииационных схем. Но для этого необходимо закодировать состояния схемы и предоставить характеристические функции в виде булевых функций двоичных переменных. Такое кодирование можно осуществить преобразованием общей таблицы перехода автомата к таблице соответствия в двоичном структурном алфавите. Если элементы множеств X, Y и S пронумерованы порядковыми числами, начиная с нуля, то им соответствуют коды, представляющие собой двоичные эквиваленты этих чисел. Например, для автомата, заданного графом на рис. 2, таблицу переходов можно преобразовать к виду (табл. 5).
|
|
|
Таблица 5
| x( n ) | |||||||||||||||||||
| s( n ) | |||||||||||||||||||
| s( n +1) | |||||||||||||||||||
| y( n ) |
Заменяя десятичные числа их двоичными эквивалентами, читаемыми сверху вниз, получаем таблицу соответствия, в которой значения функций s( n +1) и y( n ) представлены двоичными кодами (табл. 6).
Таблица 6
x( n ){
| |||||||||||||||||||
s( n ){
| |||||||||||||||||||
s( n +1) {
| |||||||||||||||||||
| y( n ){y1( n ) |
Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x1( n ), x2( n ) и переменным состояния s1( n ), s2( n ), а также три выхода, соответствующие переменным состояния s1( n +1), s2( n +1) и выходной переменной y1( n ). Синтезировав комбинационную схему, соответствующую полученной таблице, и введя два элемента задержки З1 и З2,получим структурную схему автомата (рис. 5).
 |
Рис. 5
