Структурный синтез конечных автоматов

 

В инженерной практике используются различные методы структурного синтеза конечных автоматов, каждый из которых имеет свои достоинства и недостатки. Ниже рассмотрен наиболее простой метод, получивший название канонического. Согласно этому методу структурный синтез автомата проводится в такой последовательности.

1. Кодирование входных, выходных сигналов и состояний автомата.

2. Выбор элементов памяти.

3. Запись уравнений функций выходов и возбуждения автомата.

4. Построение структурной схемы автомата.

Рассмотрим последовательно этапы структурного синтеза автомата на примере конечного автомата Мили, заданного таблицами переходов и выходов на рис. 29.

Кодирование. Входной, выходной сигналы и состояния автомата кодируются двоичными векторами. Пусть n - число входных сигналов. Тогда число двоичных векторов k_вх, необходимых для кодирования входных сигналов, определяется как ближайшее большее целое число от log₂n. Так, при n =3, log₂3 =1,58, следовательно k_вх =2. Аналогично определяется число k_вых двоичных векторов для кодирования выходных сигналов и число k_{сост .} - для кодирования состояний.

Далее составляют таблицы кодирования. В таблицах указываются все сигналы и соответствующие им двоичные векторы.

В качестве примера составим таблицы кодирования для автомата, заданного таблицами на рис. 29. Определим количество двоичных векторов для кодирования.

Входные сигналы: n_вх =2, l og₂2 =1, k_вх =1.

Выходные сигналы: n_вых =3, log₂3 =1,58, k_вых =2.

Число состояний: n_{сост .}=4, log₂4 =2, k_сост. =2.

Таблицы кодирования показаны на рис. 47.

 

Рис. 47. Таблицы кодирования

 

После того, как составлены таблицы кодирования, составляют структурные таблицы переходов и выходов (рис. 48). Эти таблицы строятся на основании исходных таблиц переходов и выходов (рис. 29). В каждой клетке таблицы переходов, расположенной на пересечении строки входного сигнала x _i и столбца состояния a _j вписывают код состояния, в которое автомат переходит из состояния a _j под воздействием входного сигнала x _i, а в таблице выходов - код выходного сигнала, который при этом переходе появляется на выходе автомата.

Выбор элементов памяти. При каноническом методе структурного синтеза в качестве элементов памяти используют элементарные автоматы Мура, обладающие полной системой переходов и выходов. Такими автоматами являются триггеры D, T, R-S, J-K.

Обобщенная структурная схема автомата. Обобщенные структурные схемы автомата Мура и автомата Мили показаны на рис. 49. Количество элементов памяти автомата должно быть равно числу компонент вектора его состояний. Каждому переходу

Рис. 48. Структурные таблицы: а) переходов; б) выходов

 

автомата из одного состояния в другое должно соответствовать переключение одного из элементов памяти. Переключения осуществляются комбинационной схемой функции возбуждения, подключаемой к информационным входам элементарных автоматов. Для выработки выходных сигналов автомата служит своя комбинационная схема.

Составление уравнений функций возбуждения и выходов автомата. Для составления уравнений функций возбуждения строят структурную таблицу функций возбуждения автомата.

 

 

Рис. 49. Обобщенная структурная схема:

а) автомата Мура; б) автомата Мили

 

Эта таблица строится на основании структурной таблицы переходов и выходов и выбранных элементов памяти.

Предположим, что для рассматриваемого примера в качестве элементов памяти выбраны Т -триггеры. Таблица функций возбуждения показана на рис. 50. Таблица строится следующим образом. В верхней строке таблицы указаны коды состояний автомата, как и в таблицах на рис. 48.

 

Рис. 50. Таблица функций возбуждения для Т- триггеров

 

В крайней левой колонке указаны коды входных сигналов. Рассмотрим клетку таблицы, стоящей на пересечении строки b =0 и столбца (Q₁, Q₂)=(0, 0). Из таблицы переходов следует, что под воздействием входного сигнала b =0 автомат из состояния (0, 0) переходит в состояние (0, 1). Для выбранных элементов памяти (Т-триггер) это означает, что первый триггер не изменил своего состояния, а второй триггер изменил свое состояние. Чтобы переключение триггеров соответствовало этому условию, сигнал на входе первого триггера должен быть равен нулю (U ₁=0), а сигнал на входе второго триггера должен быть равен единице (U ₂=1). Подобным же образом заполняются остальные клетки таблицы.

На основании таблицы функций возбуждения составляют таблицы истинности функций возбуждения, а затем определяют минимальные формы этих функций (рис. 51).

 

 

Рис. 51. а) Таблица истинности функций возбуждения и функций выхода:

б) карта Карно для функции u₁; в) карта Карно для функции u₂

 

Для получения таблицы истинности функций выхода воспользуемся структурной таблицей выходов. Таблица истинности составляется следующим образом. В таблице рис. 48 для комбинации b =0, Q₁ =0, Q₂ =0 значения векторов выходного сигнала следующие: w₁ =0, w₂ =1. В таблице истинности (рис. 51, а) в строке b =0, Q₁ =0, Q₂ =0 вносим значения w₁ =0, w₂ =1 и т.д.

Рис. 52. Функциональная схема автомата, выполненного на Т -триггерах

 

Функции возбуждения и функции выходов для рассматриваемого примера равны:

Функциональная схема автомата на Т -триггерах показана на рис. 52.

Рассмотрим еще один пример структурного синтеза того же автомата, но с использованием в качестве элементов памяти R-S- триггеров. Исходные таблицы переходов и выходов те же, что и в первом примере.

 

 

Таблица функций возбуждения приведена на рис. 53. Таблица составляется следующим образом. Рассмотрим клетку таблицы, стоящей на пересечении строки b =0 и столбца (Q₁, Q₂)=(0, 0). Из таблицы переходов (рис. 29) следует, что под воздействием входного сигнала x₁ (b =0) автомат из состояния а ₀ -(0,0) переходит в состояние а ₁ -(0,1). Элемент памяти Т₁ из состояния 0 переходит в состояние 0. Для R-S- триггера переход 0-0 возможен при условии R =0, S =0 или при условии R =1 и S =0 (см. рис. 40). Из этого следует, что на входе R сигнал может быть любой (0 или 1), а на входе S сигнал должен быть равен нулю. Поэтому в клетке (b =0, а = а ₀) для R₁S₁ проставляем на первом месте прочерк, что означает неопределенность, а на втором месте 0. Элемент памяти Т₂ из состояния 0 переходит в состояние 1. Из табл. На рис. 40 видим, что переход 0-1 для R-S -триггера происходит при подаче на его входы сигналов R =0 и S =1, поэтому в клетке (b =0, а = а ₀) на втором месте проставляем 01 и т.д.

 

b	Q1	Q2	R1	S1	R2	S2	w1	w2
			-
				-
				-		-
			-		-
			-
					-

а)

 

Рис. 54. а) Таблицы истинности для R₁, S₁, R₂, S₂, w₁, w₂;

Карты Карно для функции: б) R₁; в) S₁; г) R₂; д) S₂; е) w₂.

 

Рис. 55. Структурная схема автомата на R-S -триггерах

 

По таблице функций возбуждения и по структурной таблице выходов (рис. 48 б) строим таблицу истинности для функции R₁, S₁, R₂, S₂, w₁, w₂ (рис. 54).

Минимальные формы функций возбуждения и функций выходов:

Функциональная схема автомата, выполненного на R-S -триггерах, показана на рис. 55.

 

 

Литература

1. Сигорский В. П. Математический аппарат инженера. - К.: Техника, 1975. - 766с.; ил.

2. Вавилов Е. Н., Портной Г. П. Синтез схем электронных цифровых машин.- М.: Cоветское радио, 1963. - 437 с. ил.

3. Вавилов Е. Н., Портной Г. П. И др. Синтез схем на пороговых элементах. - М.: Советское радио, 1970. - 367 с. ил.

4. Прикладная теория цифровых автоматов /К. Г. Самофалов, А. М. Романкевич, Р. Н. Валуйский и др. - К.: Высш. шк., 1987.-375 с.

5. Электронные промышленные устройства: Учеб. Для вузов /В. И. Васильев, Ю. М. Гусев, В. Н. Миронов и др. - М., 1988. - 303 с.