Автор: Пользователь скрыл имя, 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
Первичная импликанта функции - импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой.
Задача минимизации по методу
Квайна решается путём по парного
сравнения всех импликант, входящих в
ФАЛ, с целью выявления возможности их
неполного склеивания по какой-то переменной
на промежуточных этапах. При склеивании
снижается ранг термов. Склеивание проводится
до тех пор, пока не останется ни одного
терма, допускающего склеивание с каким-либо
другим термом. Термы, подвергшиеся склеиванию,
отмечаются. Неотмеченные термы представляют
собой первичные импликанты. После получения
множества всех первичных импликант исследуется
возможность нахождения простейшей записи
ФАЛ. Для этого составляется таблица, в
первой строке которой записаны минтермы
исходной ФАЛ, а в первом столбце записаны
все найденные первичные импликанты. Клетки
этой таблицы помечаются в том случае,
если первичная импликанта входит в состав
какого –
либо минтерма исходной ФАЛ. После этого
задача упрощения сводится к тому, чтобы
найти такое минимальное количество первичных
импликант, которые покрывают все столбцы
минтермов исходной ФАЛ.
Минимизируем Y:
Y=000011v000100v000101v0010
Группа 0: пустая;
Группа 1: 000100;
Группа 2: 000011, 000101, 001001, 001100, 010100;
Группа 3: 001011, 001110, 010110;
Группа 4: 001111;
Таблица сравнения групп 1 и 2:
| Термы | 000011 | 000101 | 001001 | 001100 | 010100 |
| 000100 | 00010§ | 00§100 | 0§0100 |
Таблица сравнения групп 2 и 3:
| Термы | 000011 | 000101 | 001001 | 001100 | 010100 |
| 001011 | 00§011 | 0010§1 | |||
| 001110 | 0011§0 | ||||
| 010110 | 0101§0 |
Таблица сравнения групп 3 и 4:
| Термы | 001011 | 001110 | 010110 |
| 001111 | 001§11 | 00111§ |
Таблица сравнения групп 1-2 и 2-3:
| Импл. | 00010§ | 00§100 | 0§0100 |
| 00§011 | |||
| 0010§1 | |||
| 0011§0 | 00§1§0 | ||
| 0101§0 | 0§01§0 |
Таблица сравнения групп 2-3 и 3-4:
| Импликант | 00§011 | 0010§1 | 0011§0 | 0101§0 |
| 001§11 | 00§§11 | 001§§1 | ||
| 0011й§ | 0011§§ |
Первичные импликанты:
00§1§0, 0§01§0, 00§§11, 001§§1, 0011§§;
Расстановка меток:
| Терм\имп. | 00§1§0 | 0§01§0 | 00§§11 | 001§§1 | 0011§§ |
| 000011 | 000011 | ||||
| 000100 | 000100 | 000100 | |||
| 000101 | |||||
| 001001 | 001001 | ||||
| 001011 | 001011 | ||||
| 001100 | 001100 | 001100 | |||
| 001110 | 001110 | 001110 | |||
| 001111 | 001111 | 001111 | |||
| 010100 | 010100 | ||||
| 010110 | 010110 |
Y(a4a3a2a1a0x)= 00§1§0, 0§01§0, 00§§11, 000101;
Минимизируем D4
D4=000000v000100v001000v001
v011000v000111v001010v00110
Группа 0: 000000;
Группа 1: 000100, 001000;
Группа 2: 001100, 010001, 010010, 010100, 011000, 001010;
Группа 3: 001011, 010011, 010101, 010110, 000111, 001101;
Группа 4: 001111, 010111;
Таблица сравнения групп 0 и 1:
| Термы | 000100 | 001000 |
| 000000 | 000§00 | 00§000 |
Таблица сравнения групп 1 и 2:
| Термы | 001100 | 010001 | 010010 | 010100 | 011000 | 001010 |
| 000100 | 001§00 | 0§0100 | ||||
| 001000 | 00§100 | 0§1000 | 0010§0 |
Таблица сравнения групп 2 и 3:
| Термы | 001100 | 010001 | 010010 | 010100 | 011000 | 001010 |
| 001011 | 00101§ | |||||
| 010011 | 0100§1 | 01001§ | ||||
| 010101 | 010§01 | 01010§ | ||||
| 010110 | 010§10 | 0101§0 | ||||
| 000111 | ||||||
| 001101 | 00110§ |
Таблица сравнения групп 3 и 4:
| Термы | 001111 | 010111 |
| 001011 | 001§11 | |
| 010011 | 010§11 | |
| 010101 | 0101§1 | |
| 010110 | 01011§ | |
| 000111 | 00§111 | |
| 001101 | 0011§1 |
Таблица сравнения групп 0-1 и 1-2:
| Импл. | 001§00 | 00§100 | 0§0100 | 0§1000 | 0010§0 |
| 000§00 | 00§§00 | 0§0§00 | |||
| 00§000 | 00§§00 | 0§§000 | 00§0§0 |
Таблица сравнения групп 1-2 и 2-3:
| Импл. | 001§00 | 00§100 | 0§0100 | 0§1000 | 0010§0 |
| 00110§ | 001§0§ | 00§100 | |||
| 0100§1 | |||||
| 010§01 | |||||
| 01001§ | |||||
| 010§10 | |||||
| 01010§ | 0§010§ | ||||
| 0101§0 | 0§01§0 | ||||
| 00101§ | 0010§§ |