Абстрактный синтез конечного автомата

2. СТРУКТУРНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА

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

Для кодирования состояний, входных и выходных сигналов конечного автомата, необходимо вычислить число элементов памяти:

а) рассчитаем число элементов памяти: Н = ] log2h [, где h - число состояний после минимизации D = {}

H = ] log2 12 [ = 4

б) рассчитаем число входных (L) и выходных (М) шин:
L = ] log2n[

М =] log2m [,

где n, m - число букв входного и выходного алфавитов

Z = {0, 1} L = ] log2 2 [ = 1

W = {0, 1} M = ] log2 2 [ = 1

Из приведённого выше следует, что для кодирования состояний необходимо 4 элемента памяти, обозначим их Q0, …, Q3. Закодируем состояния (таблица 5) случайными кодами.

Таблица 5. Таблица кодированных состояний

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

По минимизированному графу переходов абстрактного автомата (Приложение 2) можно составить таблицу переходов, выходных сигналов и сигналов возбуждения D-триггеров автомата Мили (таблица 6), Т-триггеров автомата Мили (таблица 7), RS-триггеров (таблица 8), JK-триггеров (таблица 9).

D-триггер - элемент задержки - имеет один информационный вход D и один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт. Состояние, в которое переходит триггер, совпадает с поступившим на его вход сигналом D(t).

Таблица 6. Таблица переходов, выходных сигналов и сигналов возбуждения D-триггеров

Из таблицы следует, что выходные сигналы автомата Мили описываются следующими выражениями:

= d20 d21 d50 d60 d80 d81 d101= d2 d50 d60 d8 d101

= d00 d01 d10 d11 d31 d41 d51 d71 d90= d0 d1 d31 d41 d51 d71 d90

Также следует, что сигналы возбуждения D-триггеров автомата Мили описываются следующими выражениями:

D3 = d21 d50 d51 d60 d71 d80 d90 d101= d21 d5 d60 d71 d80 d90 d101

D2 = d11 d20 d31 d41 d81

D1 = d01 d10 d20 d41 d50 d51 d60 d80 d90 d101=

=d01 d10 d20 d41 d5 d60 d80 d90 d101

D0 = d00 d10 d20 d31 d50 d51 d60 d71 d81 d90 d101=

=d00 d10 d20 d31 d5 d60 d71 d81 d90 d101

Функциональная схема автомата Мили на D-триггерах, построенная по выражениям, описывающим выходные сигналы, приведена в Приложении 3.

Таблица 7. Таблица переходов, выходных сигналов и сигналов возбуждения T-триггеров

Из таблицы следует, что сигналы возбуждения T-триггеров автомата Мили описываются следующими выражениями:

T3 = d21 d50 d51 d60 d71 d81= d21 d5 d60 d71 d81

T2 = d11 d20 d31 d50 d51 d60 d71 d81= d11 d20 d31 d5 d60 d71 d81

T1 = d01 d10 d21 d31 d41 d50 d51 d71 d80 d90= d01 d10 d21 d31 d41 d5 d71 d80 d90

T0 = d00 d20 d60 d81 d101

Функциональная схема автомата Мили на T-триггерах, построенная по выражениям, описывающим выходные сигналы, приведена в Приложении 4.

Таблица 8. Таблица переходов и сигналов возбуждения RS-триггеров

Из таблицы следует, что сигналы возбуждения RS-триггеров автомата Мили описываются следующими выражениями:

R3 = d81

S3 = d21 d50 d51 d60 d71 d90= d21 d5 d60 d71 d90

R2 = d50 d51 d60 d71= d5 d60 d71

S2 = d11 d20 d31 d81

R1 = d21 d31 d71

S1 = d01 d10 d41 d50 d51 d80= d01 d10 d41 d5 d80

R0 = d11

S0 = d00 d20 d60 d81 d101

Функциональная схема автомата Мили на RS-триггерах, построенная по выражениям, описывающим выходные сигналы, приведена в Приложении 5.

Таблица 9. Таблица переходов и сигналов возбуждения JK-триггеров

Из таблицы следует, что сигналы возбуждения RS-триггеров автомата Мили описываются следующими выражениями:

J3 = d21 d50 d51 d60 d71 d90= d21 d5 d60 d71 d90

K3 = d81

J2 = d11 d20 d31 d81

K2 = d50 d51 d60 d71= d5 d60 d71

J1 = d01 d10 d41 d50 d51 d80= d01 d10 d41 d5 d80

K1 = d21 d31 d71

J0 = d00 d20 d60 d81 d101

K0 = d11

Функциональная схема автомата Мили на JK-триггерах, построенная по выражениям, описывающим выходные сигналы, приведена в Приложении 6.

ЗАКЛЮЧЕНИЕ

В процессе выполнения работы мной были закреплены знания о синтезе конечных автоматов и получена практика в построении комбинационных схем.

В данной работе мной было выполнено проектирование конечного автомата по алфавитному отображению с использованием канонического метода структурного синтеза автоматов. Построены граф переходов абстрактного автомата с 17 состояниями и таблицы переходов-выходов. Минимизация состояний автомата выполнена путем разбиения на группы эквивалентных между собой состояний. После чего был построен минимальный граф Мили с 11 состояниями. Выполнен структурный синтез конечного автомата. Построены функциональные схемы автомата Мили на D, T, RS и JK-триггерах.

СПИСОК ЛИТЕРАТУРЫ

1. Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). - 2-е изд., перераб. и доп. - Л.: Энергия, 1979. - 232 с., ил.

2. Дегтярев В.М., Ерош И.Л., Михайлов В.В. Проектирование цифровых автоматов.-Л.:ЛИАП, 1974г.

3. Козин И.В., Иванов Н.М., Лупал А.М. Проектирование управляющих автоматов по алфавитному отображению. Учебное пособие по курсовому проектированию/ЛИАП. - Л., 1991. - 82 с., ил.

4. Лупал А.М. Теория автоматов. Учебное пособие/СПбГУАП. - СПб., 2000. - 120 с., ил.

5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. Учебник для вузов по спец. «Электронные вычислительные машины». - 2-е изд., перераб. и доп. - Мн.: Выш. школа, 1980. - 336 с., ил.

6. Конспект лекций по дисциплине «Теория автоматов», преподаватель Глебов Е.А., 2005-2006 уч.г.

Страницы: 1, 2