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

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

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

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

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

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

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

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

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

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

Входные сигналы: n_вх=2, log₂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 с.