Синтез синхронных и асинхронных автоматов
Министерство образования науки молодежи и спорта
Украины
Севастопольский национальный технический университет
Кафедра Кибернетики и
вычислительной техники
Пояснительная записка
к курсовому проекту по дисциплине
"Прикладная теория цифровых автоматов"
«Синтез синхронных и асинхронных автоматов»
Выполнила:
ст. гр. М – 22д
Павленко Л.О.
Вариант 23
№зач. Кн.:100922
Проверила:
Козлова Е.В.
Севастополь 2012
Содержание
Введение…………………………………………………………
1.Постановка задачи……………………………
2. Синтез синхронного автомата……………………………………………….6
2.1.Таблица переходов
и выходов автомата………………………………
2.2.Кодирование состояний* и система уравнений………………………....8
2.3.Функциональная схема и расчет ее характеристик……………………..10
2.4.Логическое моделирование схемы на наборах
функционального теста………………………………………………………....
3.Синтез асинхронного
автомата……………………………………………....
3.1.Примитивная таблица
переходов и выходов автомата……
3.2.Минимизация числа состояний автомата……………………………… .15
3.3.Кодирование состояний
и система уравнений………………………….
3.4.Функциональная
схема и расчет ее
Заключение……………………………………………………
Библиографический список…………………………………………………….24
*для автомата секретный замок
Введение
Прикладная теория цифровых автоматов изучает модели цифровых устройств (вычислительных, управляющих, измерительных). Рассматриваются модели и методы описания, проектирования (синтеза и анализа) и диагностики цифровых автоматов.
В соответствии с классификацией цифровых автоматов (далеко не полной), данную пояснительную записку можно условно разделить на 2 части:
1.проектирование, синтез и диагностика синхронного автомата;
2.проектирование, синтез и диагностика асинхронного автомата;
Кроме этого, в конце каждой части приведён расчет технических характеристик синтезированных схем для серии микросхем 531.
1.Постановка задачи
1.Построить функциональную схему синхронного автомата.
1.1.Построить схему n-
Тип устройства - регистр; количество разрядов – 3; тип триггеров – RS;
Х1 |
Х2 |
Микрооперация |
0 |
0 |
Прием кода а3 а2 а1 |
0 |
1 |
Сдвиг вправо циклический |
1 |
0 |
Сдвиг влево с заполнением освобождающегося разряда а0 |
1 |
1 |
Хранение кода |
1.2.Построить схему автомата типа секретный замок по заданным ключевым последовательностям:
Открывающая последовательность – 4 6 2
Закрывающая последовательность – 2 6 2
Серия микросхем – 531
Кодирование состояний автомата выполнить по критерию простоты структуры.
2.Построить функциональную
схему асинхронного автомата
типа секретный замок по
Открывающая последовательность – 4 6 2
Закрывающая последовательность – 2 6 2
Серия микросхем – 531
Кодирование состояний автомата выполнить по критерию надежности функционирования.
Для проверки схемы синхронного автомата использовать логическое моделирование на наборах функционального теста, для проверки схемы асинхронного автомата – временное моделирование на наборах функционального теста.
Функциональный тест для счетчика или регистра должен включать наборы, обеспечивающие проверку всех режимов функционирования автомата. Функциональный тест для секретного замка должен включать набор установки в начальное состояние, наборы открывающей последовательности и набор, проверяющий закрытие замка.
Комбинационные схемы синхронного и асинхронного автоматов должны быть реализованы логическими элементами И-НЕ и содержать подсхемы установки в начальное состояние. Память синхронного автомата должна быть реализована двухступенчатыми триггерами типа RS.
2.Синтез синхронного автомата
Синхронный автомат – это автомат, который совершает переход из одного состояния в другое в строго определённый момент времени, которое задается внешним генератором временных интервалов. Синхронный автомат характеризуется тем, что функционирует под управлением тактовых сигналов, имеющих постоянную длительность и постоянную частоту, если квантование времени выбрано равномерно. Такт времени ti совмещается с фронтом i-го такта сигнала. Входные сигналы xk(t) могут воздействовать на автомат лишь при наличии тактового сигнала и не изменяются в течение его длительности.
В данном курсовом проекте реализуется регистр в виде синхронного автомата. Регистр – последовательное или параллельное логическое устройство, используемое для хранения n-разрядных двоичных чисел и выполнения преобразований над ними.
2.1. Таблица переходов и выходов автомата
t t+1
Х1 |
X2 |
Z1 |
Z2 |
Z3 |
Z1 |
Z2 |
Z3 |
R1 |
S1 |
R2 |
S2 |
R3 |
S3 |
0 |
0 |
x |
x |
x |
A3 |
A2 |
A1 |
A3 |
A2 |
A1 | |||
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
x |
0 |
x |
0 |
x |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
x |
0 |
1 |
0 | ||
0 |
1 |
0 |
0 |
0 |
1 |
x |
0 |
1 |
0 |
0 |
1 | ||
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
x | ||
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
x |
0 | ||
1 |
0 |
1 |
1 |
1 |
0 |
0 |
x |
0 |
1 |
1 |
0 | ||
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
x |
0 |
1 | ||
1 |
1 |
1 |
1 |
1 |
1 |
0 |
x |
0 |
x |
0 |
x | ||
1 |
0 |
0 |
0 |
0 |
а0 |
0 |
0 |
а0 |
х |
0 |
х |
0 | |
0 |
0 |
1 |
а0 |
1 |
0 |
а0 |
0 |
1 |
1 |
0 | |||
0 |
1 |
0 |
а0 |
0 |
0 |
а0 |
1 |
0 |
х |
0 | |||
1 |
0 |
0 |
а0 |
0 |
1 |
а0 |
х |
0 |
0 |
1 | |||
1 |
0 |
1 |
а0 |
0 |
1 |
а0 |
х |
0 |
0 |
х | |||
1 |
1 |
0 |
а0 |
0 |
1 |
а0 |
1 |
0 |
0 |
1 | |||
1 |
1 |
1 |
а0 |
1 |
1 |
а0 |
0 |
х |
0 |
Х | |||
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
х |
0 |
х |
0 |
х |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
х |
0 |
х |
0 |
0 |
х | ||
0 |
1 |
0 |
0 |
1 |
0 |
х |
0 |
0 |
х |
х |
0 | ||
0 |
1 |
1 |
0 |
1 |
1 |
х |
0 |
0 |
х |
0 |
х | ||
Х1 |
X2 |
Z1 |
Z2 |
Z3 |
Z1 |
Z2 |
Z3 |
R1 |
S1 |
R2 |
S2 |
R3 |
S3 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
х |
х |
0 |
х |
0 | ||
1 |
0 |
1 |
1 |
0 |
1 |
0 |
х |
х |
0 |
0 |
х | ||
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
х |
0 |
1 | ||
1 |
1 |
1 |
1 |
1 |
1 |
0 |
х |
0 |
х |
0 |
х |
2.2. Функция возбуждения RS триггеров
Построим матрицы системы булевых уравнений:
Получили следующую систему булевых функций:
R1=x1x2z3˅ x2 z3 z2˅ x1x2a3˅ x1x2a0
S1= x1x2z3˅ x1x2a3˅ x1x2a0
R2= x1x2z3˅ x1x2z3z1˅ x1x2a2
S2= x1x2a2˅ x2z1z2z3˅ x1x2z1z3˅ x1x2z1z3
R3= x1x2z1z2˅ x1x2z2z3˅ x1x2a1
S3= x1x2a1˅ x1x2z1z3˅ x2z1z2z3˅ x1x2z2z3
По данной системе булевых функций построим функциональную схему. Комбинационную схему реализуем в базисе и-не, память реализуем с помощью RS триггеров
2.3. Функциональная схема и расчет ее характеристики
Согласно варианту задания автомат должен быть собран на микросхемах серии 531
Напряжение питания - .5В+5%
Ток потребления
“нуля” - не более 36 мА;
“единицы” - не более 16 мА .
Время переключения
из “0” в “1” - не более 5 нс;
из “1” в “0” - не более 4.5 нc.
Микросхема |
Аналог |
Назначение |
Р, мВт |
Tз,нс |
КР531ЛА7 |
74S22 |
2 логических элемента 4 И-НЕ с открытым коллектором |
8 |
120 |
КР531ТМ2 |
74S74 |
2 RS триггер |
100 |
- |
Максимальное время срабатывания схемы:
Так как самый длинный путь сигнала от входа к выходу составляет 5 логических элементов, то время, которое потребуется сигналу для прохождения этого пути ( максимальное время срабатывания схемы ) будет равно:
tзадержки=120*5=600нс
Потребляемая мощность:
Рпост=720мВт
2.4. Логическое моделирование схемы на наборах функционального теста
x1 |
x2 |
x1 |
x2 |
a0 |
a1 |
a2 |
a3 |
z1 |
z2 |
z3 |
z1 |
z2 |
z3 |
F1 |
F2 |
F3 |
F4 |
F5 | |||||||||||||||
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 | |||||||||||||||||||||
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 | |||||||||||||||
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 | |||||||||||||||
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 | |||||||||||||||
F6 |
F7 |
F8 |
F9 |
F10 |
F11 |
F12 |
F13 |
F14 |
F15 |
F16 |
F17 |
F18 |
F19 |
F20 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
F21 |
F22 |
F23 |
F24 |
F25 |
F26 |
F27 |
F28 |
F29 |
F30 |
F31 |
F32 |
F33 |
F34 |
F35 |
F36 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
F37 |
F38 |
F39 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
3. Синтез асинхронного автомата
Асинхронный автомат – это автомат, у которого длительность интервала времени, в течение которого остается неизменным состояние входных сигналов xk(t), является величиной переменной и определяется временем, которое необходимо автомату для установки соответствующих выходных сигналов yz(t) и завершения перехода в новое состояние aj(t).
Одна из моделей асинхронного автомата предложена Хаффманом. Эта модель строиться на основании следующих двух предположений.
1) на любом переходе меняет значение одна и только одна входная переменная. Входной набор сменяется только после окончания переходного процесса на предыдущем наборе.
2) полные состояния автомата разделяются на два класса: устойчивые и неустойчивые. В устойчивом полном состоянии Si следующее состояние равно Si, поэтому автомат сохраняет полное состояние Si до тех пор, пока не изменится входной набор. В неустойчивом состоянии Si следующее внутреннее состояние Si не равно Si, поэтому возникает переходный процесс смены состояний: Si -> Sj, если полное состояние Sj неустойчиво, переходный процесс продолжается: Sj -> Sk и т.д. до тех пор, пока либо процесс дойдёт до устойчивого состояния SL (бх SL -> SL), либо замкнется на одно из уже пройденных состояний (возникает переходный процесс по кольцу неустойчивых состояний - генерация). Других вариантов не может быть, т.к. общее число состояний в автомате конечно. В правильно построенном автомате Хаффмана процесс, проходя по цепочке устойчивых состояний, должен заканчиваться в устойчивом состоянии. Нельзя допускать проектирование автомата с генерацией по кольцу неустойчивых состояний.
Для описания алгоритма работы автомата Хаффмана используется таблица переходов и выходов.
Процесс синтеза асинхронного автомата содержит следующие этапы: описание автомата на языке таблицы переходов и выходов Хаффмана, минимизация числа состояний, кодирование состояний, переход к системе булевых функций и построение функциональной схемы.
Секретный замок – цифровой автомат, который управляет открыванием двери или включает сигналы тревоги. Дверь открывается при подаче на вход замка единственной открывающей последовательности входных переменных. При подаче любой другой последовательности дверь остаётся закрытой и включается сигнал тревоги. Пользователь имеет возможность выключить сигнал тревоги, если он знает одну верную последовательность сброса тревоги. После сброса тревоги можно набирать открывающую последовательность. Длины открывающей последовательности и сброса тревоги входных сигналов могут быть различны. Замки характеризуются собственными последовательностями.
3.1. Примитивная таблица переходов и выходов автомата
Примитивной называется таблица переходов и выходов, в которой в каждом столбце Si имеется только одно устойчивое состояние Si. В этой таблице используются только непосредственные переходы из неустойчивого состояния в устойчивое, т.е. длина цепочки перехода равна единице. Примитивная таблица используется при начальном описании алгоритма работы автомата.
Построим таблицу переходов и выходов для нашей последовательности открытия двери и снятия тревоги.
S0 |
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
S7 |
S8 |
S9 |
S10 |
S11 |
S12 |
S13 |
S14 |
S15 |
S16 | |
000 |
S0 |
S7 |
x |
S15 |
S7 |
х |
S0 |
S7 |
S15 |
х |
S15 |
х |
x |
x |
S15 |
S15 |
S0 |
001 |
S8 |
х |
x |
x |
х |
х |
х |
x |
S8 |
S16 |
х |
x |
x |
S16 |
x |
S16 |
S16 |
011 |
х |
x |
х |
х |
S9 |
x |
х |
S9 |
S9 |
S9 |
S9 |
x |
S9 |
х |
х |
x |
x |
010 |
S10 |
x |
S3 |
S3 |
S4 |
S6 |
S6 |
S4 |
x |
S4 |
S10 |
S4 |
х |
х |
x |
х |
х |
110 |
х |
S2 |
S2 |
x |
S5 |
S5 |
х |
S11 |
х |
x |
S11 |
S11 |
S11 |
x |
S11 |
x |
x |
111 |
х |
х |
S12 |
x |
x |
S12 |
х |
x |
x |
S12 |
х |
S12 |
S12 |
S12 |
x |
х |
х |
101 |
x |
S13 |
х |
х |
x |
x |
х |
х |
S13 |
х |
x |
х |
S13 |
S13 |
S13 |
x |
x |
100 |
S1 |
S1 |
S14 |
x |
x |
S14 |
х |
х |
х |
x |
х |
S14 |
х |
S14 |
S14 |
x |
x |
00 |
00 |
00 |
00 |
10 |
01 |
01 |
01 |
01 |
01 |
01 |
01 |
01 |
01 |
01 |
01 |
01 |
3.2. Минимизация числа состояний автомата
Для минимизации числа состояний необходимо ввести некоторые определения:
Состояния Si и Sj автомата эквивалентны, если при всех входных последовательностях поведение автомата одинаково независимо от того, находится ли он исходно в состояниях Si или Sj. Состояния Si и Sj тождественно эквивалентны, если в них функции выхода и следующего состояния одинаковы при всех входных наборах. Состояния Si и Sj тождественно не эквивалентны, если хотя бы для одного входного набора значения входных функций в этих состояниях различны. Если состояния Si и Sj не являются тождественно неэквивалентными или эквивалентными, то проверка их эквивалентности приводит к проверке эквивалентности влекомых пар, т.е. пар следующих состояний, в которые автомат переходит из состояний Si и Sj под воздействием одного входного набора. Дискретный автомат называется полным (полностью определённым), если у него определены следующие состояния и значения выходных функций при всех входных наборах во всех внутренних состояниях. Минимизацию числа состояний начинаем с построения матрицы отношения эквивалентности состояний.
S1 |
S2 |
….. |
Sk |
||
S0 | |||||
S1 | |||||
… | |||||
… | |||||
Sk-1 | |||||
Сначала все элементы этой матрицы не определены. Заполняем нулями элементы матрицы, пары состояний которых тождественно не эквиваленты, и единицами – пары состояний которых тождественно эквивалентны.
При сравнении двух состояний эквивалентными в данном случае будут состояния, у которых при одном входном наборе переходы в другие состояния одинаковые, либо у одного из состояний нет перехода вообще, но его можно дописать таким же, как и во втором. При минимизации следует не забывать дописывать такие состояния в поглощающий столбец.
Причиной минимизации в данном случае служит то, что состояния, полученные при построении таблицы переходов и выходов нельзя закодировать при помощи трех переменных. Для подобной кодировки необходимо минимизировать количество состояний путем объединения ортогональных наборов
Построим матрицу отношений эквивалентности состояний:
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
S7 |
S8 |
S9 |
S10 |
S11 |
S12 |
S13 |
S14 |
S15 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
S0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
S1 | |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
S2 | ||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
S3 | |||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
S4 | ||||
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
S5 | |||||
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
S6 | ||||||
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
S7 | |||||||
1 |
1 |
1 |
1 |
1 |
1 |
1 |
S8 | ||||||||
1 |
1 |
1 |
1 |
1 |
1 |
S9 | |||||||||
1 |
1 |
1 |
0 |
0 |
S10 | ||||||||||
1 |
1 |
1 |
1 |
S11 | |||||||||||
1 |
1 |
1 |
S12 | ||||||||||||
1 |
1 |
S13 | |||||||||||||
1 |
S14 |