Автор работы: Пользователь скрыл имя, 07 Июня 2014 в 13:31, курсовая работа
Прикладная теория цифровых автоматов изучает модели цифровых устройств (вычислительных, управляющих, измерительных). Рассматриваются модели и методы описания, проектирования (синтеза и анализа) и диагностики цифровых автоматов.
В соответствии с классификацией цифровых автоматов (далеко не полной), данную пояснительную записку можно условно разделить на 2 части:
1.проектирование, синтез и диагностика синхронного автомата;
2.проектирование, синтез и диагностика асинхронного автомата;
Кроме этого, в конце каждой части приведён расчет технических характеристик синтезированных схем для серии микросхем 531.
Введение…………………………………………………………………………3
1.Постановка задачи…………………………………………………………….4
2. Синтез синхронного автомата……………………………………………….6
2.1.Таблица переходов и выходов автомата………………………………....6
2.2.Кодирование состояний* и система уравнений………………………....8
2.3.Функциональная схема и расчет ее характеристик……………………..10
2.4.Логическое моделирование схемы на наборах
функционального теста………………………………………………………....11
3.Синтез асинхронного автомата……………………………………………....12
3.1.Примитивная таблица переходов и выходов автомата…………………14
3.2.Минимизация числа состояний автомата……………………………… .15
3.3.Кодирование состояний и система уравнений………………………….19
3.4.Функциональная схема и расчет ее характеристик……………………..22
Заключение………………………………………………………………………23
Библиографический список…………………………………………………….24
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 |
Информация о работе Синтез синхронных и асинхронных автоматов