Реферат Основы теории конечных динамических систем

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 23.11.2024

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(государственный технический университет)

филиал «Восход»
Кафедра: ИТИиУ
«Утверждаю»

Преподаватель ___________ Мирошникова Е.Н.

«        »                        2009 г.

КУРСОВАЯ РАБОТА
По дисциплине: О.Т.К.Д.С.
Студент гр. ДА 2-44                          Корсаков А.А.

«        »                        2009 г.
г. Байконур 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	~~XX01~~		(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	~~X1X1~~		(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	~~X110~~	(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)	+	~~X0X1~~	(2-10)
3	0011	+	3	001X	(2-3)	+	0X1X	(3-7)
4	0110	+	4	0X10	(2-4)	+	0X1X	(4-5)
5	0111	+	5	0X11	(3-5)	+	XX11	(5-11)
6	1001	+	6	X011	(3-7)	+	~~XX11~~	(6-9)
7	1011	+	7	011X	(4-5)	+	X11X	(7-13)
8	1100	+	8	X110	(4-9)	+	X~~11X~~	(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.                      Конспект лекций по О.Т.К.Д.С.

Приложение А

Приложение Б

Bukvasha