В инженерной практике используются различные методы структурного синтеза конечных автоматов, каждый из которых имеет свои достоинства и недостатки. Ниже рассмотрен наиболее простой метод, получивший название канонического. Согласно этому методу структурный синтез автомата проводится в такой последовательности.
1. Кодирование входных, выходных сигналов и состояний автомата.
2. Выбор элементов памяти.
3. Запись уравнений функций выходов и возбуждения автомата.
4. Построение структурной схемы автомата.
Рассмотрим последовательно этапы структурного синтеза автомата на примере конечного автомата Мили, заданного таблицами переходов и выходов на рис. 29.
Кодирование. Входной, выходной сигналы и состояния автомата кодируются двоичными векторами. Пусть n - число входных сигналов. Тогда число двоичных векторов kвх, необходимых для кодирования входных сигналов, определяется как ближайшее большее целое число от log2n. Так, при n =3, log23 =1,58, следовательно kвх =2. Аналогично определяется число kвых двоичных векторов для кодирования выходных сигналов и число kсост . - для кодирования состояний.
Далее составляют таблицы кодирования. В таблицах указываются все сигналы и соответствующие им двоичные векторы.
В качестве примера составим таблицы кодирования для автомата, заданного таблицами на рис. 29. Определим количество двоичных векторов для кодирования.
Входные сигналы: nвх =2, l og22 =1, kвх =1.
Выходные сигналы: nвых =3, log23 =1,58, kвых =2.
Число состояний: nсост .=4, log24 =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 и столбца (Q1, Q2)=(0, 0). Из таблицы переходов следует, что под воздействием входного сигнала b =0 автомат из состояния (0, 0) переходит в состояние (0, 1). Для выбранных элементов памяти (Т-триггер) это означает, что первый триггер не изменил своего состояния, а второй триггер изменил свое состояние. Чтобы переключение триггеров соответствовало этому условию, сигнал на входе первого триггера должен быть равен нулю (U 1=0), а сигнал на входе второго триггера должен быть равен единице (U 2=1). Подобным же образом заполняются остальные клетки таблицы.
На основании таблицы функций возбуждения составляют таблицы истинности функций возбуждения, а затем определяют минимальные формы этих функций (рис. 51).
Рис. 51. а) Таблица истинности функций возбуждения и функций выхода:
б) карта Карно для функции u1; в) карта Карно для функции u2
Для получения таблицы истинности функций выхода воспользуемся структурной таблицей выходов. Таблица истинности составляется следующим образом. В таблице рис. 48 для комбинации b =0, Q1 =0, Q2 =0 значения векторов выходного сигнала следующие: w1 =0, w2 =1. В таблице истинности (рис. 51, а) в строке b =0, Q1 =0, Q2 =0 вносим значения w1 =0, w2 =1 и т.д.
Рис. 52. Функциональная схема автомата, выполненного на Т -триггерах
Функции возбуждения и функции выходов для рассматриваемого примера равны:
Функциональная схема автомата на Т -триггерах показана на рис. 52.
Рассмотрим еще один пример структурного синтеза того же автомата, но с использованием в качестве элементов памяти R-S- триггеров. Исходные таблицы переходов и выходов те же, что и в первом примере.
Таблица функций возбуждения приведена на рис. 53. Таблица составляется следующим образом. Рассмотрим клетку таблицы, стоящей на пересечении строки b =0 и столбца (Q1, Q2)=(0, 0). Из таблицы переходов (рис. 29) следует, что под воздействием входного сигнала x1 (b =0) автомат из состояния а 0 -(0,0) переходит в состояние а 1 -(0,1). Элемент памяти Т1 из состояния 0 переходит в состояние 0. Для R-S- триггера переход 0-0 возможен при условии R =0, S =0 или при условии R =1 и S =0 (см. рис. 40). Из этого следует, что на входе R сигнал может быть любой (0 или 1), а на входе S сигнал должен быть равен нулю. Поэтому в клетке (b =0, а = а 0) для R1S1 проставляем на первом месте прочерк, что означает неопределенность, а на втором месте 0. Элемент памяти Т2 из состояния 0 переходит в состояние 1. Из табл. На рис. 40 видим, что переход 0-1 для R-S -триггера происходит при подаче на его входы сигналов R =0 и S =1, поэтому в клетке (b =0, а = а 0) на втором месте проставляем 01 и т.д.
| b | Q1 | Q2 | R1 | S1 | R2 | S2 | w1 | w2 |
| - | ||||||||
| - | ||||||||
| - | - | |||||||
| - | - | |||||||
| - | ||||||||
| - | ||||||||
а)
Рис. 54. а) Таблицы истинности для R1, S1, R2, S2, w1, w2;
Карты Карно для функции: б) R1; в) S1; г) R2; д) S2; е) w2.
Рис. 55. Структурная схема автомата на R-S -триггерах
По таблице функций возбуждения и по структурной таблице выходов (рис. 48 б) строим таблицу истинности для функции R1, S1, R2, S2, w1, w2 (рис. 54).
Минимальные формы функций возбуждения и функций выходов:
Функциональная схема автомата, выполненного на R-S -триггерах, показана на рис. 55.
Литература
1. Сигорский В. П. Математический аппарат инженера. - К.: Техника, 1975. - 766с.; ил.
2. Вавилов Е. Н., Портной Г. П. Синтез схем электронных цифровых машин.- М.: Cоветское радио, 1963. - 437 с. ил.
3. Вавилов Е. Н., Портной Г. П. И др. Синтез схем на пороговых элементах. - М.: Советское радио, 1970. - 367 с. ил.
4. Прикладная теория цифровых автоматов /К. Г. Самофалов, А. М. Романкевич, Р. Н. Валуйский и др. - К.: Высш. шк., 1987.-375 с.
5. Электронные промышленные устройства: Учеб. Для вузов /В. И. Васильев, Ю. М. Гусев, В. Н. Миронов и др. - М., 1988. - 303 с.
