Автор: Пользователь скрыл имя, 24 Декабря 2010 в 16:58, курсовая работа
Построить устройство для преобразования последовательного двоично-десятичного кода X = (хЗ, х2, х1, х0), который подаётся на вход устройства z = (z3, z2, z1, z0). Десятичный эквивалент X двоично-десятичного кода может быть вычислен: Х=Ë xi pi , где xi = 0, 1 - цифра двоично-десятичного кода, a pi - вес i-ro разряда.
Задание 2
Введение 4
Понятие о дискретном (цифровом) автомате. 5
Основные понятия алгебры логики. 6
Понятия теории графов 11
Граф-дерево автомата Мура. 13
Граф-дерево автомата Мили. 14
Таблица переходов по автомату Мили 15
Таблица выходов по автомату Мили 15
Минимизация цифрового автомата Мили. 15
Таблица переходов с распределением неопределённостей. 15
Исключение недостижимых состояний. 16
Определение класса совместимости. 16
Классы единичной совместимости 17
Классы двоичной совместимости 18
Классы троичной совместимости Ошибка! Закладка не определена.
Классы четверичной совместимости Ошибка! Закладка не определена.
Таблица состояний и выходов нормализованного автомата 24
Структурный синтез цифрового автомата 26
Выбор триггера 27
Представление функции возбуждения 29
Таблица состояний и выходов нормализованного автомата
Минимизирующие карты 32
Минимизация функций по методу Квайна 33
Минимизация функций по методу Мак-Класки 33
Заключение 44
Литература 45
| x/a | a22 | a23 | a24 | a25 | a26 | a27 | a28 | a29 | a30 | a31 | a32 | a33 | a34 | a35 | a.36 | a37 | a38 | a39 | a40 |
| 0 | a32 | a33 | a34 | a35 | a36 | a37 | a38 | a39 | a40 | a0 | a0 | a0 | a0 | a0 | a0 | a0 | a0 | a0 | a0 |
| 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
Таблица выходов по автомату Мили
| x/a | a0 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 | a12 | a13 | a14 | a15 | a16 | a17 | a18 | a19 | a20 | a21 |
| 0 | 0 | 0 | - | 0 | 0 | - | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | - | - | - | - | - | - | - | - | - | - | - |
| x/a | a22 | a23 | a24 | a25 | a26 | a27 | a28 | a29 | a30 | a31 | a32 | a33 | a34 | a35 | a.36 | a37 | a38 | a39 | a40 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
Минимизация цифрового автомата Мили.
Абстрактный автомат, построенный по техническому заданию формальным или эвристическим методами, обычно не является минимальным по количеству состояний. Построение эквивалентного ему абстрактного цифрового автомата с наименьшим числом состояний и является задачей оптимизации. При минимизации числа состояний уменьшается стоимость, как блока памяти автомата, так и его входной и выходной комбинационных схем.
Два полностью определённых автомата называются эквивалентными, если они индуцируют (производят) одно и то же отображение множества входных слов во множество выходных слов. Частичный цифровой автомат А называется эквивалентным продолжением частичного автомата В, если индуцируемое им отображение совпадает с отображением, индуцируемым автоматом В на всех допустимых для автомата В словах.
Полностью определённый автомат является частным случаем частичного автомата.
Таблица переходов с распределением неопределённостей.
Первым
(предварительным) этапом всякой минимизации
является выделение неопределенных
выходных сигналов и состояний и
внесение соответствующей
Исключение недостижимых состояний.
Если в автомате имеется состояние (но только не начальное), в которое он не может попасть под воздействием любого допустимого входного слова, то такое состояние называется недостижимым. Недостижимые состояния исключаются из описания абстрактного автомата без изменения, индуцируемого автоматом отображения. Автомат, все состояния которого достижимы, является связным автоматом.
Определение класса совместимости.
Состояния аi и aj называются совместимыми, если, двигаясь из этих состояний под воздействием любого входного сигнала, автомат индуцирует одинаковое его отображение.
Состояния называются i-совместимыми для i=1, 2,..., если результат применения к этим состояниям любого слова длины i будет одинаковым. Классы совместимых состояний могут быть найдены непосредственно по таблице выходов. В один и тот же 1 - класс зачисляются состояния, обозначающие совпадающие (с точностью до неопределённых выходных сигналов) столбцы таблицы выходов. Классы (i+1) - совместимости получаются из классов i - совместимости путём их расщепления на классы (i+1) - совместимости. Для этого у каждого состояния, принадлежащего j - классу i - совместимости Cj(i), номера классов (индексы), в которые автомат переходит под воздействием каждой входной буквы. Если номер класса не определён, то ставится специальный символ, например, прочерк. Индексы классов, в которые переходит автомат под действием входного сигнала, образуют отметку. Множество состояний с одинаковыми отметками в классе Cj(i) образуют классы (i+1) - совместимости. При выполнении операции расщепления классов специальный символ неопределённости может быть заменён номером (индексом) любого класса. Если операцию расщепления i-классов применить последовательно, начиная с 1-класса, то через конечное число шагов процесс расщепления закончится. Нерасщепляемые далее классы образуют классы совместимых состояний. Иногда отметки состояний разных классов совпадают, но объединять такие состояния в один класс (i+1) - совместимости совершенно недопустимо.
Классы единичной совместимости
В классы единичной совместимости поместим:
| C1(1) | 0 | 1 | C2(1) | 0 | 1 | C3(1) | 0 | 1 | ||
| 0 | 1 | 1 | 9 | 1 | 2 | 8 | 2 | 1 | ||
| 1 | 1 | 1 | 10 | 2 | 2 | |||||
| 2 | - | 1 | 14 | 1 | - | |||||
| 3 | 1 | 1 | 15 | 2 | - | |||||
| 4 | 3 | 2 | 18 | 1 | - | |||||
| 5 | - | 2 | 19 | 2 | - | |||||
| 6 | 1 | 1 | 20 | 2 | - | |||||
| 7 | 1 | 2 | 23 | 2 | - | |||||
| 11 | 1 | - | 25 | 2 | - | |||||
| 12 | 1 | - | 27 | 1 | - | |||||
| 13 | 2 | - | 29 | 1 | - | |||||
| 16 | 1 | - | 30 | 2 | - | |||||
| 17 | 2 | - | 32 | 1 | - | |||||
| 21 | 1 | - | 33 | 1 | - | |||||
| 22 | 2 | - | 34 | 1 | - | |||||
| 24 | 2 | - | 35 | 1 | - | |||||
| 26 | 1 | - | 40 | 1 | - | |||||
| 28 | 1 | - | ||||||||
| 31 | 1 | - | ||||||||
| 36 | 1 | - | ||||||||
| 37 | 1 | - | ||||||||
| 38 | 1 | - | ||||||||
| 39 | 1 | - |
Классы двоичной совместимости
| D1(2) | 0 | 1 | D2(2) | 0 | 1 | D6(2) | 0 | 1 | ||
| 0 | 1 | 1 | 4 | 7 | 5 | 10 | 6 | 6 | ||
| 1 | 1 | 2 | D3(2) | 0 | 1 | 15 | 6 | - | ||
| 2 | - | 3 | 5 | - | 6 | 19 | 1 | - | ||
| 3 | 1 | 3 | 7 | 4 | 5 | 20 | 6 | - | ||
| 6 | 1 | 1 | D4(2) | 0 | 1 | 23 | 5 | - | ||
| 11 | 1 | - | 13 | 6 | - | 25 | 5 | - | ||
| 12 | 4 | - | 17 | 5 | - | 30 | 5 | - | ||
| 16 | 1 | - | 22 | 5 | - | D7(2) | 0 | 1 | ||
| 21 | 1 | - | 24 | 5 | - | 8 | 6 | 1 | ||
| 26 | 1 | - | D5(2) | 0 | 1 | |||||
| 28 | 1 | - | 9 | 4 | 5 | |||||
| 31 | 1 | - | 14 | 4 | - | |||||
| 36 | 1 | - | 18 | 1 | - | |||||
| 37 | 1 | - | 27 | 1 | - | |||||
| 38 | 1 | - | 29 | 1 | - | |||||
| 39 | 1 | - | 32 | 1 | - | |||||
| 33 | 1 | - | ||||||||
| 34 | 1 | - | ||||||||
| 35 | 1 | - | ||||||||
| 36 | 1 | - | ||||||||
| 40 | 1 | - |