Синтез синхронных автоматов по заданной временной вход-выходной последовательности

Особенность синхронного дискретного устройства состоит в необходимости обеспечения синхронизации сигналов при его схемной реализации.

Для синтеза синхронных дискретных устройств используют синхронные (тактируемые) RS-триггеры, имеющие по сравнению с асинхронными вход C, который называют синхронизирующим или тактовым (рис. 1).

Рис. 1. Условное обозначение (а), схема синхронного RS-триггера (б) и временная диаграмма его работы (в)

На вход С поступают синхроимпульсы. Сигналы на входы R и S могут приходить в любой момент времени, однако триггер переключается только в моменты времени, определяемые синхроимпульсами. Логика работы RS-триггера задается уравнением Рассмотрим временную диаграмму его функционирования. Пусть в начальный момент времени триггер находится в состоянии 0 (значения логических сигналов y = 0, ). При поступлении на вход S сигнала логической 1 переключения триггера не происходит, так как в этот момент сигналы с = 0 и S* = 0. Для переключения триггера необходимо, чтобы S* = 1, последнее возможно только при S = 1 и с = 1. Для синхронизации сигналов в автомате на RS-триггерах (рис. 2) используются две последовательности сигналов с₁ и с₂ (рис. 3).

Рис. 2. Структурная схема синхронного автомата

Рис. 3. Временная диаграмма синхроимпульсов

Входные и внутренние переменные на входе логического преобразователя синхронизируются импульсами C₁. В качестве схемы синхронизации можно использовать RS-триггер (рис. 4). В этой схеме управление триггером осуществляется одним входным сигналом x (или y), подаваемым на вход S. На вход R поступает инверсный сигнал, для чего используется элемент НЕ. В результате на входах S и R всегда присутствуют инверсные логические сигналы и в зависимости от значений переменной х (1 или 0) триггер устанавливается в соответствующее состояние (1 или 0) при поступлении импульса синхронизации С₁. Таким образом, если сигнал x асинхронный (изменяется в произвольный момент времени), сигналы x(t) и являются синхронными (изменяются в фиксированный момент времени).

Рис. 4. Схема синхронизации входного сигнала

Рассмотрим работу синхронного автомата (см. рис. 2). В моменты времени t = 1, 2, 3,… по переднему фронту синхроимпульсов С₁ срабатывают схемы синхронизации и на вход логического преобразователя ЛП поступают сигналы x(t) и y(t -1). Логический преобразователь вычисляет новые значения функций y_S(t) и y_R(t). Затем, когда все переходные процессы в ЛП закончены, поступает синхроимпульс С₂ и происходит переключение триггеров. Формируются новые значения сигналов y(t -1) и .

На вход ЛП эти сигналы поступят только в следующий момент времени, когда придет новый синхроимпульс С₁. За это время все переходные процессы в логическом преобразователе закончатся и все триггеры (даже самый медленнодействующий) переключатся в новое состояние. Таким образом исключаются критические состязания элементов памяти. Наряду с этим упрощается сам процесс синтеза, поскольку кодирование состояний может быть произвольным и нет необходимости анализировать схему для выявления критических состязаний элементов памяти.

2. Этапы выполнения курсового проекта

2.1 Исходные данные для проектирования

Исходными данными в курсовом проекте являются вход-выходные временные последовательности (рис. 5).

Рис. 5. Вход-выходные временные последовательности

2.2 Описание автомата по исходным данным

Требуется построить схему, имеющую два входа x₁ и x₂ и два выхода z₁ и z₂. Схема должна реализовать три циклические последовательности сигналов, показанных на рисунке 6. Все последовательности имеют одно и то же исходное состояние на интервале времени t₁: x₁x₂ = 00, z₁z₂ = 00. Последовательности могут сменять друг друга в произвольном порядке.

Рис. 6. Вход-выходные временные последовательности и временные диаграммы к ним

2.3 Построение графа переходов и первичной таблицы переходов

Первым этапом построения графа переходов и первичной таблицы переходов является нумерация состояний по исходным данным.

Анализируя временные диаграммы (рис. 6), следует пронумеровать состояния схемы, используя два правила:

1) вводится начальное устойчивое состояние, соответствующее интервалу времени t₁, когда x₁x₂ = 00, z₁z₂ = 00 (в таблице 1 это состояние (а₁, 1));

2) для каждого последующего такта вводится новое устойчивое состояние (рис. 7).

Рис. 7. Нумерация состояний

Таблица 1 Таблица переходов

Рассмотрим первый цикл работы: из состояния (а₁, 1) со значением входов x₁x₂ = 00 и выходов z₁z₂ = 00 схема под воздействием входного сигнала 01 переходит в состояние (а₂, 2) со значением выходов z₁z₂ = 00. Затем под воздействием входного сигнала 11 схема переходит в состояние (а₄, 3) со значением выходов z₁z₂ = 01. В состояние 4 (а₃, 4) схема переходит под воздействием входного сигнала 10, под воздействием сигнала 01, схема переходит в состояние 5 (а₂, 5) со значением выходов z₁z₂ = 11. Завершается циклическая вход-выходная первая последовательность подачей входного сигнала 00 и переходом схемы в начальное состояние (а₁, 1).

Затем таблица переходов расширяется с учетом второй и третьей вход-выходных последовательностей. При этом их начальные состояния совпадают с начальным состоянием первой последовательности.

Построим граф переходов (рис. 8).

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

Итак, для примера рассмотрим построение графа для первой вход-временной последовательности: из состояния 1, 00 под входным воздействием 01 схема переходит в состояние 2, 00, далее под воздействием 11 схема переходит в состояние 3, 01, затем под входным воздействием 10 - в состояние 4, 10, под воздействием 01 - в состояние 5, 11, наконец, под воздействием 00 - в исходное состояние 1, 00. Устойчивые состояния на графе показываются дугами, исходящими и входящими в одну и ту же вершину графа с подписью значений входов схемы.

Рис. 8. Граф переходов

Аналогично строится граф для оставшихся циклов работы схемы.

2.4 Минимизация числа строк таблицы переходов

E_1,2,4,7 = {1}

E_1,2,4,12 = {1,12}

E_1,2,6,3 = {1}

E_1,2,6,7 = {1,6}

E_1,2,6,12 = {1,12}

E_1,2,9,3 = {1,9}

E_1,2,9,7 = {1,9}

E_1,2,9,12 = {1,9,12}

E_1,2,11,3 = {1}

E_1,2,11,7 = {1}

E_1,2,11,12 = {1,11,12}

E_10,2,4,3 = {3}

E_10,2,4,7 = {Ш}

E_10,2,4,12 = {Ш}

E_10,2,6,3 = {2}

E_10,2,6,7 = {6}

E_10,2,6,12 = {Ш}

E_10,2,9,3 = {Ш}

E_10,2,9,7 = {Ш}

E_10,2,9,12 = {Ш}

E_10,2,11,3 = {10}

E_10,2,11,7 = {10}

E_10,2,11,12 = {10,11}

E_1,5,4,3 = {3,4,5}

E_1,5,4,7 = {4,5}

E_1,5,4,12 = {4,5,12}

E_1,5,6,3 = {5}

E_1,5,6,7 = {5,6}

E_1,5,6,12 = {5,12}

E_1,5,9,3 = {5,9}

E_1,5,9,7 = {5,9}

E_1,5,9,12 = {5,9,12}

E_1,5,11,3 = {5}

E_1,5,11,7 = {5}

E_1,5,11,12 = {5,11,12}

E_10,5,4,3 = {3,4}

E_10,5,4,7 = {4}

E_10,5,4,12 = {4}

E_10,5,6,3 = {Ш}

E_10,5,6,7 = {6}

E_10,5,6,12 = {Ш}

E_10,5,9,3 = {Ш}

E_10,5,9,7 = {Ш}

E_10,5,9,12 = {Ш}

E_10,5,11,3 = {10}

E_10,5,11,7 = {10}

E_10,5,11,12 = {10,11}

E_1,8,4,3 = {3}

E_1,8,4,7 = {7}

E_1,8,4,12 = {12}

E_1,8,6,3 = {Ш}

E_1,8,6,7 = {6,7}

E_1,8,6,12 = {12}

E_1,8,9,3 = {8,9}

E_1,8,9,7 = {7,8,9}

E_1,8,9,12 = {8,9,12}

E_1,8,11,3 = {Ш}

E_1,8,11,7 = {7}

E_1,8,11,12 = {11,12}

E_10,8,4,3 = {3}

E_10,8,4,7 = {7}

E_10,8,4,12 = {Ш}

E_10,8,6,3 = {Ш}

E_10,8,6,7 = {6,7}

E_10,8,6,12 = {Ш}

E_10,8,9,3 = {8}

E_10,8,9,7 = {7,8}

E_10,8,9,12 = {8}

E_10,8,11,3 = {10}

E_10,8,11,7 = {7,10}

E_10,8,11,12 = {10,11}

Из полученных множеств исключаются те, которые полностью входят в другое множество. Оставшиеся множества E_i1,i2,i3,i4 являются максимальными подмножествами совместимых строк, они обозначаются латинскими буквами:

E_1,2,4,3 = {1,3} = A;

E_1,2,6,7 = {1,6} = B;

E_1,2,9,12 = {1,9,12} = C;

E_1,2,11,12 = {1,11,12} = D;

E_1,5,4,3 = {3,4,5} = E;

E_1,5,4,12 = {4,5,12} = F;

E_1,5,6,7 = {5,6} = G;

E_1,5,9,12 = {5,9,12} = H;

E_1,5,11,12 = {5,11,12} = I;

E_1,8,6,7 = {6,7} = J;

E_1,8,9,7 = {7,8,9} = K;

E_1,8,9,12 = {8,9,12} = L;

E_10,2,6,3 = {2} = M;

E_10,2,11,12 = {10,11} = N;

E_10,8,11,7 = {7,10} = O.

2.4.2 Составление таблицы покрытий

Столбцы таблицы соответствуют множествам A,B, …, O, а строки - строкам первичной таблицы переходов. На пересечении строки и столбца ставится знак «+», если данная строка таблицы переходов входит в данное подмножество совместимых строк.

Решение задачи покрытия.

Находится минимальное множество столбцов W такое, что каждая строка (состояние) входит хотя бы в одно из них. Для этого составляется алгебраическое выражение Q типа конъюнкция дизъюнкций. Каждая дизъюнкция образуется как дизъюнкция тех столбцов, в которых стоит метка «+» в данной строке (табл. 2).

Таблица 2 Таблица покрытий

Для таблицы 2 имеем:

Q = (ABCD)M(AE)(EF)(EFGHI)(BGJ)(JKO)

(KL)(CHKL)(NO)(DIN)(CDFHIL).

2.4.3 Нахождение минимального множества таблицы покрытия

С использованием правил повторения и поглощения выражение Q приводится к виду дизъюнкция конъюнкций. Выбирается любая из минимальных конъюнкций W.

В данном случае: W=MBEKLN.

Объединение строк первичной таблицы переходов:

W=MBEKLN = {2},{1,6},{3,4,5},{7,8,9},{8,9,12},{10,11}.

Далее исключается повторение цифр:

W`= {2},{1,6},{3,4,5},{7,9},{8,12},{10,11}.

Строится таблица с учетом объединения строк (табл. 3).

Таблица 3 Минимизированная таблица переходов

2.4.4 Построение минимизированной таблицы переходов

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

Получаем минимизированную таблицу переходов (ТП) (табл. 4).

Таблица 4 Таблица переходов, после перенумерации

2.5 Кодирование строк таблицы переходов

2.5.1 Определение необходимого числа элементов памяти

Для построения схемы необходимо три элемента памяти: Y₁, Y₂, Y₃.

Число элементов памяти определяется по формуле:

m = ]log₂S[,

где ]a[ - обозначение ближайшего к a целого числа A ? a; m - количество необходимых элементов памяти; S - число состояний автомата.

В таблице 5 представлено кодирование для минимизированной таблицы переходов. Теперь состоянию 1 соответствует комбинация 000, состоянию 2 - 001 и так далее до последнего 6 - 101.

Таблица 5 Кодирование состояний

2.5.2 Кодированные таблица переходов и таблица выходов

Составляются кодированные таблица переходов и таблица выходов. В качестве исходной берется таблица 4, в которой состояния автомата S заменяются соответствующими кодами из таблицы 5.

В таблицах 6 и 7 соответственно представлены таблица переходов и таблица выходов.

Таблица 6 Кодированная таблица переходов

Таблица 7 Кодированная таблица выходов

2.6 Реализация автомата в базисе {И, ИЛИ, НЕ, Триггер}

2.6.1 Вычисление функций управления триггерами по входам S(Y_S) и R(Y_R)