Реферат Основы теории конечных динамических систем
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ
(государственный технический университет)
филиал «Восход»
Кафедра: ИТИиУ
«Утверждаю»
Преподаватель ___________ Мирошникова Е.Н.
« »
КУРСОВАЯ РАБОТА
По дисциплине: О.Т.К.Д.С.
Студент гр. ДА 2-44 Корсаков А.А.
« »
г. Байконур 2009 год
Содержание
Введение
1 Расчет первой функции
1.1 Минимизация исходной функции с помощью метода
элементарных преобразований
1.2 Минимизация функции с помощью карты Карно
1.3 Нахождение минимальных покрытий
1.4 Нахождение цены по Квайну
1.5 Нахождение нулевого покрытия функции и МКНФ
1.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски
1.7 Минимизация исходной функции с применением метода метод Петрика
1.8 Построение комбинационной схемы с однофазными входами
1.9 Факторное преобразование и построение схемы с однофазными
входами и двухвходовыми элементами
1.10 Сравнение двух схем по задержке и цене по Квайну
2 Расчет второй функции
2.1 Минимизация исходной функции с помощью метода
элементарных преобразований
2.2 Минимизация функции с помощью карты Карно
2.3 Нахождение минимальных покрытий
2.4 Нахождение цены по Квайну
2.5 Нахождение нулевого покрытия функции и МКНФ
2.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски
2.7 Минимизация исходной функции с применением метода Петрика
2.8 Построение комбинационной схемы с однофазными входами
2.9 Факторное преобразование и построение схемы с однофазными
входами и двухвходовыми элементами
2.10 Сравнение двух схем по задержке и цене по Квайну
3 Расчет третьей функции
3.1 Минимизация исходной функции с помощью метода
элементарных преобразований
3.2 Минимизация функции с помощью карты Карно
3.3 Нахождение минимальных покрытий
3.4 Нахождение цены по Квайну
3.5 Нахождение нулевого покрытия функции и МКНФ
3.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски
3.7 Минимизация исходной функции с применением метода Петрика
3.8 Построение комбинационной схемы с однофазными входами
3.9 Факторное преобразование и построение схемы с однофазными
входами и двухвходовыми элементами
3.10 Сравнение двух схем по задержке и цене по Квайну
4 Расчет четвертой функции
4.1 Минимизация исходной функции с помощью метода
элементарных преобразований
4.2 Минимизация функции с помощью карты Карно
4.3 Нахождение минимальных покрытий
4.4 Нахождение цены по Квайну
4.5 Нахождение нулевого покрытия функции и МКНФ
4.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски
4.7 Минимизация исходной функции с применением метода Петрика
4.8 Построение комбинационной схемы с однофазными входами
4.9 Факторное преобразование и построение схемы с однофазными
входами и двухвходовыми элементами
4.10 Сравнение двух схем по задержке и цене по Квайну
Заключение
Список используемой литературы
Приложение А
Приложение Б
Введение
В данной курсовой работе необходимо рассмотреть два метода минимизации функций: метод элементарных преобразований и минимизацию функций с помощью карт Карно, для трех и четырех элементных функций. Будет необходимо найти минимальное покрытие для данных функций, нулевые покрытия и минимальные канонические нормальные формы, определить цены по Квайну. Также необходимо определить множество минимальных покрытий с помощью двух методов: метода Квайна-Мак-Класски и метода Петрика.
В дальнейшем необходимо построение комбинационной однофазной схемы без ограничения на вход. При получении минимальных канонических нормальных форм провести факторизацию и построить комбинационные однофазные схемы с двухвходовыми элементами.
1 Расчет первой функции
1.1 Минимизация исходной функции с помощью метода элементарных преобразований
1.2 Минимизация функции с помощью карты Карно
Рисунок 1.1 – Карта Карно для ДНФ
1.3 Нахождение минимальных покрытий
| 1 | 0000 | + | | | 1 | 000X | (1-2) | m | | | | | |
2 | 0001 | + | | 2 | 0X10 | (3-5) | m | | XX01 | m | (6-8) | |||
3 | 0010 | + | | 3 | 01X1 | (4-6) | m | | | | (9-11) | |||
4 | 0101 | + | | 4 | 10X1 | (7-9) | m | | | | | |||
5 | 0110 | + | | 5 | X010 | (3-8) | m | | | 000X | | | ||
6 | 0111 | + | | 6 | 1X01 | (7-10) | + | | 0X10 | | | |||
7 | 1001 | + | | 7 | 00X0 | (1-3) | m | | 01X1 | | | |||
8 | 1010 | + | | 8 | 0X01 | (2-4) | + | | 10X1 | | | |||
9 | 1011 | + | | 9 | X001 | (2-7) | + | | X010 | | | |||
| 10 | 1101 | + | | | 10 | X101 | (4-10) | + | | 00X0 | | | |
| | | | | 11 | 011X | (5-6) | m | | 011X | | | ||
| | | | | 12 | 101X | (8-9) | m | | 101X | | | ||
| | | | | | | | | XX01 | | |
1.4 Нахождение цены по Квайну
1.5 Нулевое покрытие функции и МКНФ
Рисунок 1.2 – Карта Карно для КНФ
- МКНФ
| 1 | 0011 | m | | | 1 | X100 | (2-4) | m | | | X100 |
2 | 0100 | + | | | 2 | 11X0 | (4-5) | m | | 11X0 | ||
3 | 1000 | + | | 3 | 111X | (5-6) | m | | 111X | |||
4 | 1100 | + | | 4 | 1X00 | (3-4) | m | | 1X00 | |||
5 | 1110 | + | | | | | | 0011 | ||||
6 | 1111 | + | | | | | | | |
1.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски
По данным пункта 1.3 составляем таблицу 1.1
Таблица 1.1
| | 0000 | 0001 | 0010 | 0101 | 0110 | 0111 | 1001 | 1010 | 1011 | 1101 |
A | 000X | + | + | | | | | | | | |
B | 0X10 | | | + | | + | | | | | |
C | 01X1 | | | | + | | + | | | | |
D | 10X1 | | | | | | | + | | + | |
E | X010 | | | + | | | | | + | | |
F | 00X0 | + | | + | | | | | | | |
G | 011X | | | | | + | + | | | | |
H | 101X | | | | | | | | + | + | |
I | XX01 | | + | | + | | | + | | | + |
1.7 Минимизация исходной функции с применением метода Петрика
По данным таблицы 1.1 находятся минимальные покрытия:
Из всего количества минимальных покрытий, больше всего подходят следующие покрытия:
1.8 Построение комбинационной схемы с однофазными входами
Рисунок 1.3 – Комбинационная схема с однофазными входами
1.9 Факторное преобразование и построение схемы с однофазными входами и двухвходовыми элементами
Рисунок 1.4 – Комбинационная схема с однофазными входами и двухвходовыми элементами
1.10 Сравнение двух схем по задержке и цене по Квайну
После факторизации задержка и цена по Квайну увеличились.
2 Расчет второй функции
2.1 Минимизация исходной функции с помощью метода элементарных преобразований
2.2 Минимизация функции с помощью карты Карно
Рисунок 2.1 – Карта Карно для ДНФ
2.3 Нахождение минимальных покрытий
| 1 | 0000 | + | | | 1 | 00X0 | (1-2) | m | | | | | |
2 | 0010 | + | | 2 | 001X | (2-3) | m | | | X1X1 | m | (5-10) | ||
3 | 0011 | + | | 3 | X010 | (2-7) | m | | | | | (6-7) | ||
4 | 0101 | + | | 4 | 0X11 | (3-5) | m | | | | | | ||
5 | 0111 | + | | 5 | 01X1 | (4-5) | + | | 00X0 | | | |||
6 | 1001 | + | | 6 | X101 | (4-9) | + | | 001X | | | |||
7 | 1010 | + | | 7 | X111 | (5-10) | + | | X010 | | | |||
8 | 1100 | + | | 8 | 1X01 | (6-9) | m | | 0X11 | | | |||
| 9 | 1101 | + | | | 9 | 110X | (8-9) | m | | 1X01 | | | |
| 10 | 1111 | + | | | 10 | 11X1 | (9-10) | + | | 110X | | | |
| | | | | | | | | X1X1 | | | |||
| | | | | | | | | | | | |
2.4 Нахождение цены по Квайну
2.5 Нулевое покрытие функции и МКНФ
Рисунок 2.2 – Карта Карно для КНФ
- МКНФ
| 1 | 0001 | m | | | 1 | 01X0 | (2-3) | m | | 0001 |
2 | 0100 | + | | | 2 | X110 | (4-5) | m | 1000 | ||
3 | 0110 | + | | 3 | | (3-6) | m | 1011 | |||
4 | 1000 | m | | | | | 01X0 | ||||
5 | 1011 | m | | | | | | X110 | |||
6 | 1110 | + | | | | | | |
2.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски
По данным пункта 2.3 составляем таблицу 2.1
Таблица 2.1
| | 0000 | 0010 | 0011 | 0101 | 0111 | 1001 | 1010 | 1100 | 1101 | 1111 |
A | 00X0 | + | + | | | | | | | | |
B | 001X | | + | + | | | | | | | |
C | X010 | | + | | | | | + | | | |
D | 0X11 | | | + | | + | | | | | |
E | 1X01 | | | | | | + | | | + | |
F | 110X | | | | | | | | + | + | |
G | X1X1 | | | | + | + | | | | + | + |
2.7 Минимизация исходной функции с применением метода Петрика
По данным таблицы 2.1 находятся минимальные покрытия:
2.8 Построение комбинационной схемы с однофазными входами
Рисунок 2.3 – Комбинационная схема с однофазными входами
2.9 Факторное преобразование и построение схемы с однофазными входами и двухвходовыми элементами
Рисунок 2.4 – Комбинационная схема с однофазными входами и двухвходовыми элементами
2.10 Сравнение двух схем по задержке и цене по Квайну
После факторизации задержка и цена по Квайну увеличились.
3 Расчет третьей функции
3.1 Минимизация исходной функции с помощью метода элементарных преобразований
3.2 Минимизация функции с помощью карты Карно
Рисунок 3.1 – Карта Карно для ДНФ
3.3 Нахождение минимальных покрытий
| 1 | 0001 | + | | 1 | X001 | (1-6) | + | | | X0X1 | (1-6) |
2 | 0010 | + | 2 | 00X1 | (1-3) | + | | | (2-10) | |||
3 | 0011 | + | 3 | 001X | (2-3) | + | | 0X1X | (3-7) | |||
4 | 0110 | + | 4 | 0X10 | (2-4) | + | | | (4-5) | |||
5 | 0111 | + | 5 | 0X11 | (3-5) | + | | XX11 | (5-11) | |||
6 | 1001 | + | 6 | X011 | (3-7) | + | | | (6-9) | |||
7 | 1011 | + | 7 | 011X | (4-5) | + | | X11X | (7-13) | |||
8 | 1100 | + | 8 | X110 | (4-9) | + | | | (8-9) | |||
9 | 1110 | + | 9 | X111 | (5-10) | + | | | | | ||
10 | 1111 | + | 10 | 10X1 | (6-7) | + | | | 11X0 | | ||
| | | | 11 | 1X11 | (7-10) | + | | X0X1 | | ||
| | | | 12 | 11X0 | (8-9) | m | | 0X1X | | ||
| | | | 13 | 111X | (9-10) | + | | XX11 | | ||
| | | | | | | | | | X11X | |
3.4 Нахождение цены по Квайну
3.5 Нулевое покрытие функции и МКНФ
Рисунок 3.2 – Карта Карно для КНФ
- МКНФ
| 1 | 0000 | + | | | 1 | 0X00 | (1-2) | m | | | 0X00 |
2 | 0100 | + | | 2 | X000 | (1-4) | m | | X000 | |||
3 | 0101 | + | | 3 | 010X | (2-3) | m | | 010X | |||
4 | 1000 | + | | 4 | X101 | (3-6) | m | | X101 | |||
5 | 1010 | + | | 5 | 10X0 | (4-5) | m | | 10X0 | |||
6 | 1101 | + | | | | | | |
3.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски
По данным пункта 3.3 составляем таблицу 3.1
Таблица 3.1
| | 0001 | 0010 | 0011 | 0110 | 0111 | 1001 | 1011 | 1100 | 1110 | 1111 |
A | 11X0 | | | | | | | | + | + | |
B | X0X1 | + | | + | | | + | + | | | |
C | 0X1X | | + | + | + | + | | | | | |
D | XX11 | | | + | | + | | + | | | + |
E | X11X | | | | + | + | | | | + | + |
| | | | | | | | | | | |
3.7 Минимизация исходной функции с применением метода Петрика
По данным таблицы 3.1 находятся минимальные покрытия:
Из всего количества минимальных покрытий, больше всего подходят следующие покрытия:
3.8 Построение комбинационной схемы с однофазными входами
Рисунок 3.3 – Комбинационная схема с однофазными входами
3.9 Факторное преобразование и построение схемы с однофазными входами и двухвходовыми элементами
Рисунок 3.4 – Комбинационная схема с однофазными входами и двухвходовыми элементами
3.10 Сравнение двух схем по задержке и цене по Квайну
После факторизации задержка и цена по Квайну увеличились.
4 Расчет четвертой функции
4.1 Минимизация исходной функции с помощью метода элементарных преобразований
4.2 Минимизация функции с помощью карты Карно
Рисунок 4.1 – Карта Карно для ДНФ
4.3 Нахождение минимальных покрытий
| 1 | 000 | + | | | 1 | 0Y0 | (1-2) | m | | | 0Y0 | | |
2 | 010 | + | | 2 | Y00 | (1-4) | m | | Y00 | | | |||
3 | 011 | + | | 3 | 01Y | (2-3) | m | | 01Y | | | |||
4 | 100 | + | | 4 | 10Y | (4-5) | m | | 10Y | | | |||
5 | 101 | + | | | | | | | | | | |
4.4 Нахождение цены по Квайну
4.5 Нулевое покрытие функции и МКНФ
Рисунок 4.2 – Карта Карно для КНФ
- МКНФ
| 1 | 000 | + | m | | 1 | 11Y | (2-3) | m | | | 000 | | |
2 | 110 | + | | | | | | | | 11Y | | | ||
3 | 111 | + | | | | | | | | | | |
4.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски
По данным пункта 4.3 составляем таблицу 4.1
Таблица 4.1
| | 000 | 010 | 011 | 100 | 101 |
A | 0Y0 | + | + | | | |
B | Y00 | + | | | + | |
C | 01Y | | + | + | | |
D | 10Y | | | | + | + |
4.7 Минимизация исходной функции с применением метода Петрика
По данным таблицы 3.1 находятся минимальные покрытия:
Из всего количества минимальных покрытий, больше всего подходят следующие покрытия:
4.8 Построение комбинационной схемы с однофазными входами
Рисунок 4.3 – комбинационная схема с однофазными входами
Функция представлена в приложении А
4.9 Факторное преобразование и построение схемы с однофазными входами и двухвходовыми элементами
Рисунок 4.4 – Комбинационная схема с однофазными входами и двухвходовыми элементами
Функция представлена в приложении Б
4.10 Сравнение двух схем по задержке и цене по Квайну
После факторизации цена по Квайну уменьшилась.
Заключение
В данной курсовой работе были рассмотрены: метод элементарных преобразований с использованием двенадцати законов и метод минимизации с помощью карт Карно, используемый при упрощении функций, для трех и четырех элементных функций.
Найдены минимальные покрытия для данных функций, были рассмотрены покрытия булевых функций на наборах для которых х=1 такие покрытия можно назвать единичными, наряду с единичными покрытиями существуют и нулевые для которых покрываемые наборы аргументов на которых х=0, то есть покрытия реализуются для существенных вершин, но не для самих функций, а для их отрицания нулевые покрытия строятся также как и единичные, но только для отрицания исходной функции и минимальной канонической нормальной формы, с помощью построения комбинационной парафазной схемы без ограничения на вход элементов и подсчетом количества входов, были определены цены по Квайну, которые строятся по нормальной форме соответствующие этому покрытию.
Также определены множества минимальных покрытий с помощью двух методов: построение таблицы с существенными вершинами и максимальных кубов и получены минимальные покрытия с помощью метода Квайна-Мак-Класки, составлены логические выражения, которые представляют собой условные покрытия всех вершин с помощью метода Петрика.
В дальнейшем необходимо построение комбинационной однофазной схемы без ограничения на вход, при построении такой схемы необходимо выбирать такую минимальную форму, которая содержит наименьшее число инверсий над различными элементами. Проводится факторизация, ее задача сводится к вынесению за скобки общих частей термов, что приводит к уменьшению цены схемы, после чего проводится построение комбинационной однофазной схемы с двухвходовыми элементами. После построения схем надо измерить задержку распространения сигналов от входа к выходу элементов и измерить цену по Квайну, далее произвести сравнение задержки до факторизации и после факторизации, так же производится сравнение цены по Квайну.
Список используемой литературы
1. Конспект лекций по О.Т.К.Д.С.
Приложение А
Приложение Б