Минимизация булевых функций и синтез комбинационных схем

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРОМЫШЛЕННЫХ ТЕХНОЛОГИЙ И ДИЗАЙНА»

Институт информационных технологий и автоматизации

Кафедра интеллектуальных систем и защиты информации

Направление подготовки: 10.03.01 Информационная безопасность

КУРСОВАЯ РАБОТА

на тему: «Минимизация булевых функций и синтез комбинационных схем»

Предмет: «Математическая логика»

Санкт-Петербург 2020 год



МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРОМЫШЛЕННЫХ ТЕХНОЛОГИЙ И ДИЗАЙНА»

ЗАДАНИЕ

на курсовую работу

Студенту

Института Информационных технологий и автоматизации

Курс: Группа: (очная форма обучения)

Направление подготовки: 10.03.01 Информационная безопасность

Профиль: Безопасность компьютерных систем (в коммерческих структурах)

Дисциплина: Математическая логика

1. Тема курсовой работы: Минимизация булевых функций и синтез комбинационных схем

2. Сроки сдачи курсовой работы:

3. Исходные данные по курсовой работе: методические указания и Интернет-ресурсы

4. Вопросы, подлежащие разработке в курсовой работе:

· Построить комбинационные схемы в булевом базисе, реализующую не полностью определённую булеву функцию f(x) = f(x1,x2,x3,x4,x5), которая принимает значение 1 при условии: 4 <= (x1x2x3 + x4x5) <= 6; неопределенное значение при условии: (x1x2x3 + x4x5) = 7; по заданному варианту 10, используя методы следующие методы минимизации: Квайна - Мак-Класки, Петрика, карт Карно, факторизации и декомпозиции.

Заключение: итогом работы являются комбинационные схемы, реализующие заданные функции и построенные на логических элементах булева базиса.

Задание выдал:

Задание принял к исполнению:



Введение

Основная цель курсовой работы по дисциплине «Математическая логика» заключается в приобретении и закреплении практических навыков по использованию методов минимизации булевых функций с дальнейшим построением комбинационных схем на их основе.

Цена схемы по Квайну в данной курсовой работе принята в качестве основного критерия эффективности синтезируемой схемы. Непосредственно для успешного синтеза схемы необходимо решить задачи минимизации, факторизации и декомпозиции булевых функций. Используются два основных метода минимизации: Квайна - Мак-Класки и карт Карно. В дальнейшем предлагается сравнить эффективность и удобство использования этих методов. Первый метод основан на кубическом представлении булевых функций, вследствие чего является формализованным. Второй же по большей части интуитивно понятен.

Исходным выражением является не полностью определённая булева функция от пяти переменных. Итогом же курсовой работы являются синтезированные на основе данной функции комбинационные схемы. При синтезе схем учитываются ограничения на коэффициент объединения по входам. Для каждой полученной схемы определяется задержка и цена схемы по Квайну.

Понимание того, для чего нужно минимизировать булеву функцию, крайне важно при выполнении данной работы. Сложность булевой функции прямо пропорциональна количеству логических операций и количеству переменных в ней.

Для упрощения булевой функции имеет смысл использовать алгоритмические методы минимизации, оптимизирующие процесс минимизации - результат получается просто, быстро и с маленькой вероятностью ошибки. В данной работе, как говорилось выше, используются методы Квайна - Мак-Класки и карт Карно, поскольку они наиболее практичны и универсальны для минимизации булевых функций.

таблица истинность декомпозиция булевой



1. Теоретическая часть

Не полностью определенная булева функция - булева функция, значение которой на некоторых наборах не определено.

Булева функция - это функция, аргументами которой являются булевы переменные и которая может принимать значение 0 или 1.

Элементарной конъюнкцией (дизъюнкцией) называется выражение, представляющее собой конъюнкцию (дизъюнкцию) любого конечного множества попарно различимых букв или состоящее из одной буквы.

Нормальная форма - особая форма, которая в своем аналитическом виде сдержит только функции конъюнкции, дизъюнкции и отрицания.

Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (сокращенно ДНФ).

Конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ).

ДНФ называется минимальной, если она содержит наименьшее число литералов среди всех ДНФ, ей эквивалентных.

Совершенной конъюнктивной нормальной формой (СКНФ) называется конъюнктивная нормальная форма, в которой нет одинаковых элементарных дизъюнкций и все элементарные дизъюнкции правильны и полны.

Совершенной дизъюнктивной нормальной формой (СДНФ) называется дизъюнктивная нормальная форма, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильны и полны.

Конституанта нуля (единицы) - дизъюнктивный (конъюнктивный) терм максимального ранга, т.е. он содержит все переменные булевой функции. Принимает значение нуля (единицы) тогда и только тогда, когда все входящие переменные принимают значение, равное нулю (единице).

Покрытием булевой функции f называется такое подмножество кубов из кубического комплекса K(f), которое покрывает все существенные вершины функции.

Покрытие булевой функции, которое соответствует минимальной ДНФ, называется минимальным покрытием. Оно должно состоять только из максимальных кубов. В частном случае, множество максимальных кубов может являться минимальным покрытием, в общем - множество максимальных кубов является избыточным.

В кубическом представлении булевой функции от n переменных всё множество из 2n наборов её аргументов рассматривается как множество координат вершин n-мерного куба с длинной ребра равной 1. В соответствии с этим наборы аргументов, на которых булева функция принимает значение равное 1, принято называть существенными вершинами.

Существенные вершины образуют так называемые ноль-кубы (далее 0-кубы).

Два 0-куба называются соседними если они отличаются только по одной координате. Между соседними 0-кубами может быть проведена операция склеивания.

Ценой покрытия Sa называется сумма цен кубов, образующих покрытие, а именно: сумма количества букв кубов. Ценой покрытия Sb называется сумма цены Sa и количества кубов, входящих в покрытие, т. е. сумма количества букв в кубах, образующих покрытие, и количества термов. В случае дизъюнктивных форм, считаются все знаки дизъюнкции между термами и прибавляется единица.

Сложность схемы оценивается количеством оборудования, составляющего схему. Сложность (цена) по Квайну определяется суммарным числом входов логических элементов в составе схемы. Сложность схемы легко вычисляется по булевым функциям, на основе которых строится схема: для ДНФ сложность схемы равна сумме количества букв (букве со знаком отрицания соответствует цена 2) и количества знаков дизъюнкции, увеличенного на 1 для каждого дизъюнктивного выражения.

Импликанта булевой функции f(X) -- это булева функция g(X) булевой функции f(X), которая для любого набора аргументов, где g(X)=1, f(X) также равна единице. Система импликант называется полной, если любой единичный набор переменных покрывается хотя бы одной импликантой. Система простых импликант называется приведенной, если она является полной, а никакая ее собственная часть уже не образует полную систему импликант. Дизъюнкция всех простых импликант, образующих некоторую приведенную систему называется тупиковой ДНФ булевой функции.

Минимизацией называют процедуру упрощения выражения логической функции, с тем чтобы она содержала минимальное количество членов при минимальном числе переменных.



2. Практическая часть

2.1 Построение таблицы истинности. СДНФ и СКНФ

Вариант №10: 4 <= (x1x2x3 + x4x5) <= 6; условие, когда функция не определена(d) - (x1x2x3 + x4x5) = 7

Таблица 1. Таблица истинности данной булевой функции

№	x1	x2	x3	x4	x5	x1x2x3	x4x5	+	d	F
1	0	0	0	0	0	0	0	0		0
2	0	0	0	0	1	0	1	1		0
3	0	0	0	1	0	0	2	2		0
4	0	0	0	1	1	0	3	3		0
5	0	0	1	0	0	1	0	1		0
6	0	0	1	0	1	1	1	2		0
7	0	0	1	1	0	1	2	3		0
8	0	0	1	1	1	1	3	4		1
9	0	1	0	0	0	2	0	2		0
10	0	1	0	0	1	2	1	3		0
11	0	1	0	1	0	2	2	4		1
12	0	1	0	1	1	2	3	5		1
13	0	1	1	0	0	3	0	3		0
14	0	1	1	0	1	3	1	4		1
15	0	1	1	1	0	3	2	5		1
16	0	1	1	1	1	3	3	6		1
17	1	0	0	0	0	4	0	4		1
18	1	0	0	0	1	4	1	5		1
19	1	0	0	1	0	4	2	6		1
20	1	0	0	1	1	4	3	7	+	d
21	1	0	1	0	0	5	0	5		1
22	1	0	1	0	1	5	1	6		1
23	1	0	1	1	0	5	2	7	+	d
24	1	0	1	1	1	5	3	8		0
25	1	1	0	0	0	6	0	6		1
26	1	1	0	0	1	6	1	7	+	d
27	1	1	0	1	0	6	2	8		0
28	1	1	0	1	1	6	3	9		0
29	1	1	1	0	0	7	0	7	+	d
30	1	1	1	0	1	7	1	8		0
31	1	1	1	1	0	7	2	9		0
32	1	1	1	1	1	7	3	10		0

СДНФ:

(¬X1 ? ¬X2 ? X3 ? X4 ? X5) ? (¬X1 ? X2 ? ¬X3 ? X4 ? ¬X5) ? (¬X1 ? X2 ? ¬X3 ? X4 ? X5) ? (¬X1 ? X2 ? X3 ? ¬X4 ? X5) ? (¬X1 ? X2 ? X3 ? X4 ? ¬X5) ? (¬X1 ? X2 ? X3 ? X4 ? X5) ? (X1 ? ¬X2 ? ¬X3 ? ¬X4 ? ¬X5) ? (X1 ? ¬X2 ? ¬X3 ? ¬X4 ? X5) ? (X1 ? ¬X2 ? ¬X3 ? X4 ? ¬X5) ? (X1 ? ¬X2 ? X3 ? ¬X4 ? ¬X5) ? (X1 ? ¬X2 ? X3 ? ¬X4 ? X5) ? (X1 ? X2 ? ¬X3 ? ¬X4 ? ¬X5)

СКНФ:

(X1 ? X2 ? X3 ? X4 ? X5) ? (X1 ? X2 ? X3 ? X4 ?¬ X5) ? (X1 ? X2 ? X3 ? ¬X4 ? X5) ? (X1 ? X2 ? X3 ? ¬X4 ? ¬X5) ? (X1 ? X2 ? ¬X3 ? X4 ? X5) ? (X1 ? X2 ? ¬X3 ? X4 ? ¬X5) ? (X1 ? X2 ? ¬X3 ? ¬X4 ? X5) ? (X1 ? ¬X2 ? X3 ? X4 ? X5) ? (X1 ? ¬X2 ? X3 ? X4 ? ¬X5) ? (X1 ? ¬X2 ? ¬X3 ? X4 ? X5) ? (¬X1 ? X2 ? ¬X3 ? ¬X4 ? ¬X5) ? (¬X1 ? ¬X2 ? X3 ? ¬X4 ? X5) ? (¬X1 ? ¬X2 ? X3 ? ¬X4 ? ¬X5) ? (¬X1 ? ¬X2 ? ¬X3 ? X4 ? ¬X5) ? (¬X1 ? ¬X2 ? ¬X3 ? ¬X4 ? X5) ? (¬X1 ? ¬X2 ? ¬X3 ? ¬X4 ? ¬X5)

Доопределение не полностью определённой булевой функции. Если значение булевой функции на некоторых наборах не определено, оно может до определяться произвольно. Выходные сигналы на этих наборах могут принимать любые значения - 0 или 1. Входные наборы, которые дают неопределенное значение функции называются запрещенными. При синтезе схем, реализующих не полностью определенные функции выходным сигналам, соответствующим запрещенным наборам, придают такие значения, при которых можно построить наиболее простую схему. В этом случае доопределение функции целесообразно производить таким образом, чтобы ее минимальная нормальная форма имела наименьшее число букв из всех возможных вариантов доопределения.



2.2 Минимизация булевой функции

2.2.1 Метод Квайна - Мак-Класки и метод Петрика

Алгоритм минимизации основан на кубическом представлении булевых функций - множество 2ⁿ наборов её аргументов, где n - число переменных, входящих в функцию, рассматривается как множество координат вершин n-мерного куба с длиной ребра, равной 1. Ноль-кубами (К⁰) называются существенные вершины (дающие 1). Между соседними кубами (отличающимися по одной координате) определена операция склеивания. Склеивание 2-х соседних ноль-кубов, даёт 1-куб (К¹). Аналогично получают 2- и 3-кубы (при склеивании соседних r-кубов, получается куб r+1 в количестве r+1 экземпляров, что можно видеть в следующей таблице). Операция склеивания над кубами соответствует применению закона склеивания к конъюктивным термам, отождествляемым с этими кубами.

Таблица 2. Получение кубов различной размерности кубического комплекса K(f) и выделение из них простых импликант

№	К0	№	K1		№	K2		K3	Z(f)
1	00111	1	0x111	(1-6)	1	01x1x	(2-6) (3-4)	отсутствует	0x111
2	01010	2	0101x	(2-3)	2	100xx	(7-14) (8-11)		011x1
Z3	01011	3	01x10	(2-5)	3	10x0x	(7-16) (9-12)		01x1x
4	01101	4	01x11	(3-6)	4	1x00x	(7-19) (10-13)		100xx
5	01110	5	011x1	(4-6)	5	10xx0	(8-17) (9-15)		10x0x
6	01111	6	0111x	(5-6)	6	1xx00	(9-20) (10-18)		10xx0
7	10000	7	1000x	(7-8)					1xx00
8	10001	8	100x0	(7-9)
9	10010	9	10x00	(7-11)
10	10011	10	1x000	(7-14)
11	10100	11	100x1	(8-10)
12	10101	12	10x01	(8-12)
13	10110	13	1x001	(8-15)
14	11000	14	1001x	(9-10)
15	11001	15	10x10	(9-13)
16	11100	16	1010x	(11-12)
		17	101x0	(11-13)
		18	1x100	(11-16)
		19	1100x	(14-15)
		20	11x00	(14-16)

Примечание: цветом отмечены кубы, не имеющие дальнейших склеек(Z(f)).

После получения простых импликант, составляется таблица следующего вида (таблица 3): слева по вертикали расположены простые импликанты, сверху по горизонтали - существенные вершины (дающие 1). При покрытии импликантой соответствующей существенной вершины ставится точка. После составления таблицы происходит её первое упрощение (таблица 4) - происходит выделение ядра покрытия путём выделения импликант, покрывающих вершины, не покрываемых другими импликантами, и получения упрощённой импликантной таблицы (таблица 5). Затем возможны два пути получения ДНФ: составление из упрощённой импликантной таблицы КНФ с преобразованием её к ДНФ с применением закона дистрибутивности (метод Петрика) и дальнейшее упрощение импликантной таблицы по методу Квайна - Мак-Класки, работая с отношением «множество-подмножество» (таблица 6).

Таблица 3. Импликантная таблица

Импликанты

Существенные вершины

0 0 1 1 1

0 1 0 1 0

0 1 0 1 1

0 1 1 0 1

0 1 1 1 0

0 1 1 1 1

1 0 0 0 0

1 0 0 0 1

1 0 0 1 0

1 0 1 0 0

1 0 1 0 1

1 1 0 0 0

0X111

*

*

011X1

*

*

01X1X

*

*

*

*

100XX

*

*

*

10X0X

*

*

*

*

1X00X

*

*

*

10XX0

*

*

*

1XX00

*

*

*

Таблица 4. Упрощение импликантной таблицы

Примечание: жёлтым цветом отмечены существенные импликанты и вершины, затрагиваемые ими, зелёным - узлы существенных импликант, красным цветом вычёркиваются существенные импликанты - они образуют ядро покрытия T, синим вычёркиваются вершины, затрагиваемые существенными импликантами

Таблица 5. Таблица существенных импликант (упрощённая импликантная таблица)

Импликанты	0-куб
	1 0 0 0 0	1 0 0 0 1	1 0 0 1 0	1 0 1 0 0	1 1 0 0 0
	a	b	c	d	e
100XX	A	*	*	*
1X00X	B	*	*			*
10XX0	C	*		*	*
1XX00	D	*			*	*

T = {0X111, 011X1, 01X1X, 10X0X} - ядро покрытия

Определение минимального покрытия (метод Петрика):

Y = (A ? B) ? (A ? C) ? (A ? D) ? (B ? C) ? (B ? D) ? (C ? D) - (КНФ)

Преобразование КНФ в ДНФ (последовательное применение закона дистрибутивности к термам):

((B ? C) ? A) ? (A ? D) ? (B ? C) ? (B ? D) ? (C ? D)

((B ? C ? D) ? A) ? (B ? C) ? (B ? D) ? (C ? D)

((B ? C ? D) ? (A ? C) ? (A ? B)) ? (B ? D) ? (C ? D)

((B ? C ? D) ? (A ? C ? D) ? (A ? B)) ? (C ? D)

(B ? C ? D) ? (A ? C ? D) ? (A ? B ? D) ? (A ? B ? C)

Итоговая ДНФ:

Y = (B ? C ? D) ? (A ? C ? D) ? (A ? B ? D) ? (A ? B ? C)

Возможны следующие варианты покрытия:

С₁ = {TBCD}: S_a = 23, S_b = 30

C₂ = {TACD}: S_a = 23, S_b = 30

C₃ = {TABD}: S_a = 23, S_b = 30

C₄ = {TABC}: S_a = 23, S_b = 30

В нашем случае все варианты покрытия имеют одинаковые цены, потому можно выбрать любой из них для МДНФ.

MДНФ по выбранному варианту покрытия (С₁):

F = (¬X1 ? X3 ? X4 ? X5) ? (¬X1 ? X2 ? X3 ? X5) ? (¬X1 ? X2 ? X4) ? (X1 ? ¬X2 ? ¬X4) ? (X1 ? ¬X3 ? ¬X4) ? (X1 ? ¬X2 ? ¬X5) ? (X1 ? ¬X4 ? ¬X5)

Определение минимального покрытия (дальнейшее упрощение импликантной таблицы по методу Квайна - Мак-Класки):

Кроме метода Петрика, для определения минимального покрытия можно также продолжать упрощать импликантную таблицу. В отношении «множество-подмножество» находятся отметки следующих пар столбцов: a - b, a - c, a - d, a - e. Таким образом из таблицы можно удалить столбец a после чего получим новую таблицу.

Таблица 6. Конечная импликантная таблица

Импликанты	0-куб
	1 0 0 0 1	1 0 0 1 0	1 0 1 0 0	1 1 0 0 0
	b	c	d	e
100XX	A	*	*
1X00X	B	*			*
10XX0	C		*	*
1XX00	D			*	*

Дальнейшие упрощения для таблицы невозможны. Дальше ДНФ составляется как дизъюнкция всех возможных вариантов конъюнкций импликант:

Y = (B ? C ? D) ? (A ? C ? D) ? (A ? B ? D) ? (A ? B ? C)

Можно видеть, что полученная ДНФ полностью совпадает с полученной методом Петрика, потому для неё справедливы те же варианты покрытия и полученная МДНФ, как и выведенные из ДНФ метода Петрика.

По ДНФ для метода Петрика полином Жегалкина выглядит следующим образом (используем метод неопределённых коэффициентов):

Y = (B ? C ? D) ? (A ? C ? D) ? (A ? B ? D) ? (A ? B ? C)

P(A, B, C, D) = C0 ? C4D ? C3C ? C34CD ? C2B ? C24BD ? C23BC ? C234BCD ? C1A ? C14AD ? C13AC ? C134ACD ? C12AB ? C124ABD ? C123ABC ? C1234ABCD P(0, 0, 0, 0) = C0 = 0P(0, 0, 0, 1) = C0 ? C4 = 0 => 0 ? C4 = 0 => C4 = 0P(0, 0, 1, 0) = C0 ? C3 = 0 => 0 ? C3 = 0 => C3 = 0P(0, 0, 1, 1) = C0 ? C4 ? C3 ? C34 = 0 => 0 ? 0 ? 0 ? C34 = 0 => 0 ? C34 = 0 => C34 = 0P(0, 1, 0, 0) = C0 ? C2 = 0 => 0 ? C2 = 0 => C2 = 0P(0, 1, 0, 1) = C0 ? C4 ? C2 ? C24 = 0 => 0 ? 0 ? 0 ? C24 = 0 => 0 ? C24 = 0 => C24 = 0P(0, 1, 1, 0) = C0 ? C3 ? C2 ? C23 = 0 => 0 ? 0 ? 0 ? C23 = 0 => 0 ? C23 = 0 => C23 = 0P(0, 1, 1, 1) = C0 ? C4 ? C3 ? C34 ? C2 ? C24 ? C23 ? C234 = 1 => 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? C234 = 1 => 0 ? C234 = 1 => C234 = 1P(1, 0, 0, 0) = C0 ? C1 = 0 => 0 ? C1 = 0 => C1 = 0P(1, 0, 0, 1) = C0 ? C4 ? C1 ? C14 = 0 => 0 ? 0 ? 0 ? C14 = 0 => 0 ? C14 = 0 => C14 = 0P(1, 0, 1, 0) = C0 ? C3 ? C1 ? C13 = 0 => 0 ? 0 ? 0 ? C13 = 0 => 0 ? C13 = 0 => C13 = 0P(1, 0, 1, 1) = C0 ? C4 ? C3 ? C34 ? C1 ? C14 ? C13 ? C134 = 1 => 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? C134 = 1 => 0 ? C134 = 1 => C134 = 1P(1, 1, 0, 0) = C0 ? C2 ? C1 ? C12 = 0 => 0 ? 0 ? 0 ? C12 = 0 => 0 ? C12 = 0 => C12 = 0P(1, 1, 0, 1) = C0 ? C4 ? C2 ? C24 ? C1 ? C14 ? C12 ? C124 = 1 => 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? C124 = 1 => 0 ? C124 = 1 => C124 = 1P(1, 1, 1, 0) = C0 ? C3 ? C2 ? C23 ? C1 ? C13 ? C12 ? C123 = 1 => 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? C123 = 1 => 0 ? C123 = 1 => C123 = 1P(1, 1, 1, 1) = C0 ? C4 ? C3 ? C34 ? C2 ? C24 ? C23 ? C234 ? C1 ? C14 ? C13 ? C134 ? C12 ? C124 ? C123 ? C1234 = 1 => 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 1 ? 0 ? 0 ? 0 ? 1 ? 0 ? 1 ? 1 ? C1234 = 1 => 0 ? C1234 = 1 => C1234 = 1

P(A, B, C, D) = BCD ? ACD ? ABD ? ABC ? ABCD

По этому полиному также будет построена комбинационная схема.

2.2.2 Метод карт Карно

Минимизируем булеву функцию с помощью двух карт Карно, различающихся по переменной Х5. Для МДНФ используем единичное покрытие функции. На картах выделены максимальные кубы, которые образуют минимальное покрытие булевой функции от пяти переменных.

Таблица 7. Карта Карно для истинных наборов аргументов булевой функции (развёртка кубов на плоскости)

X5 = 0 X5 = 1

Полученное минимальное единичное покрытие (S1 - S6) С_min(f) = {10101, 1X00X, 011XX, 01X1X, 0X111, 10XX0}

S_a = 21, S_b = 27

МДНФ:

F = (X1 ? ¬X2 ? X3 ? ¬X4 ? X5) ? (X1 ? ¬X3 ? ¬X4) ? (¬X1 ? X2 ? X3) ? (¬X1 ? X2 ? X4) ? (¬X1 ? X3 ? X4 ? X5) ? (X1 ? ¬X2 ? ¬X5)

Для МКНФ используем нулевое покрытие функции. Аналогично развёртке для единичных значений, определяется минимальное нулевое покрытие функции.



Таблица 8. Карта Карно для ложных наборов аргументов булевой функции

X5 = 0 X5 = 1

Полученное минимальное нулевое покрытие (S1 - S8) С_min(f) = {11101, 00101, 11X1X, 1X11X, 0X00X, 000XX, 001X0, X1100}

S_a = 30, S_b = 38

MКНФ:

F = (X1 ? X2 ? X3 ? ¬X4 ? X5) ? (¬X1 ? ¬X2 ? X3 ? ¬X4 ? X5) ? (X1 ? X2 ? X4) ? (X1 ? X3 ? X4) ? (¬X1 ? ¬X3 ? ¬X4) ? (¬X1 ? ¬X2 ? ¬X3) ? (¬X1 ? ¬X2 ? X3 ? ¬X5) ? (X2 ? X3 ? ¬X4 ? ¬X5)

Можно отчётливо наблюдать, что полученная методом карт Карно МДНФ является наиболее подходящей, так как её цена меньше, чем у МКНФ, полученной тем же способом, и меньше, чем у МДНФ, полученной методом Петрика.

Примечание. После минимизации функция становится полностью определённой. Доопределение d до 1 в карте Карно, использующей единичные значения, и до 0 в карте Карно, использующей нулевые значения, помогает уменьшить цену схемы, поскольку оно соответственно уменьшает количество букв в результирующей нормальной форме.



2.3 Факторизация и декомпозиция

Факторизация (факторное преобразование) булевой функции сводится к определению общих частей термов и вынесению их за скобки для ДНФ и из скобок для КНФ (приведение к скобочной форме), как в данном случае, что, как правило, приводит к уменьшению цены синтезируемой схемы.

Целесообразность преобразования можно оценить выражением

ДS_Q = m (k-1) + p -D,

где m - количество вынесенных букв из k термов, p - число термов, в которых после вынесения m букв остается одна буква; D=1, при вынесении из всех термов МНФ, или D=2, в обратном случае. Так, в некоторых случаях, вынесение букв может не изменить цену схемы. Учитывая это, преобразуем МДНФ (используем выражение, полученное методом карт Карно, так как оно является минимальным по цене).

Исходное выражение

F = (X1 ? ¬X2 ? X3 ? ¬X4 ? X5) ? (X1 ? ¬X3 ? ¬X4) ? (¬X1 ? X2 ? X3) ? (¬X1 ? X2 ? X4) ? (¬X1 ? X3 ? X4 ? X5) ? (X1 ? ¬X2 ? ¬X5)

S_a = 21

Факторизованное выражение

F = X1 ¬X2 (X3 ¬X4 X5 ? ¬X5) ? X1 ¬X3 ¬X4 ? ¬X1 X2 X3 ? ¬X1 X2 X4 ? ¬X1 X3 X4 X5

ДS_a = 1, S_a = 20

Вторично факторизованное выражение

F = X1 ¬X2 (X3 ¬X4 X5 ? ¬X5) ? ¬X1 X2 (X3 ? X4) ? X1 ¬X3 ¬X4 ? ¬X1 X3 X4 X5

ДS_a = 1 + 2 = 3, S_a = 20 - 2 = 18

Цена схемы уменьшилась на 3, что говорит о правильности факторизации.

Суть декомпозиции заключается в представлении (выражении) одной булевой функции через другую (выделение вспомогательных функций) и целесообразно, если:

1) Функции похожи настолько, что принимают одинаковые значения на одинаковых наборах аргументов

2) Функции различаются настолько, что принимают противоположные значения на одинаковых наборах аргументов

За исходную функцию принимается та, которая обладает наименьшей ценой реализации.

В нашем случае декомпозиция не имеет смысла, так как выражение не содержит в себе похожих (сходных) или полностью противоположных термов.

2.4 Построение комбинационных схем

Разрешив задачу минимизации, факторизации и декомпозиции, приступаем к синтезу комбинационных схем (самой простой части работы после построения таблицы истинности исходной булевой функции, на мой взгляд). Учитывая ограничения на коэффициент объединения по входам (равен 2, как видно в следующих схемах), составляем схемы следующим образом:

· Берём за основу иерархическую структуру, где логические операции разделены по уровням в порядке их выполнения (по приоритетам)

· Располагаем наверху «пирамиды» операторы, идущие последними при выполнении с учётом ограничения коэффициента на объединение по входам; по аналогии располагаем операторы, идущие раньше при выполнении вплоть оператора с максимальным приоритетом (отрицание)

· В итоге самые первые входы к операционным блокам должны соответствовать расположению переменных в минимизированной функции - это позволяет без особых затруднений соединить узлы-переменные с соответствующими входами

2.4.1 По методу Квайна - Мак-Класки и Петрика

F = (¬X1 ? X3 ? X4 ? X5) ? (¬X1 ? X2 ? X3 ? X5) ? (¬X1 ? X2 ? X4) ? (X1 ? ¬X2 ? ¬X4) ? (X1 ? ¬X3 ? ¬X4) ? (X1 ? ¬X2 ? ¬X5) ? (X1 ? ¬X4 ? ¬X5)

Цена схемы по Квайну S = 49

Задержка схемы ф = 6

2.4.2 По методу карт Карно (схема построена на базе полученной МДНФ, как обладающей наименьшей ценой покрытия)

F = (X1 ? ¬X2 ? X3 ? ¬X4 ? X5) ? (X1 ? ¬X3 ? ¬X4) ? (¬X1 ? X2 ? X3) ? (¬X1 ? X2 ? X4) ? (¬X1 ? X3 ? X4 ? X5) ? (X1 ? ¬X2 ? ¬X5)



Цена схемы по Квайну S = 45

Задержка схемы ф = 7

2.4.3 Факторизация и декомпозиция

F = X1 ¬X2 (X3 ¬X4 X5 ? ¬X5) ? ¬X1 X2 (X3 ? X4) ? X1 ¬X3 ¬X4 ? ¬X1 X3 X4 X5

Цена схемы по Квайну S = 37

Задержка схемы ф = 8



2.4.4 В базисе Жегалкина

P(A, B, C, D) = BCD ? ACD ? ABD ? ABC ? ABCD

Цена схемы по Квайну S = 30

Задержка схемы ф = 5

Среди представленных выше схем, наиболее эффективной (обладающей как и минимальной ценой по Квайну, так и минимальной задержкой) является схема, построенная на основе полинома Жегалкина, выведенного из ДНФ метода Петрика.

2.5 Условные обозначения

Символьные:

Логическое «И» (конъюнкция) - ? или не обозначается явно

Логическое «ИЛИ» (дизъюнкция) - ?

Логическое «НЕ» (инверсия) - ¬

Логическое «Исключающее ИЛИ» (сложение по модулю 2) - ?

Обозначения элементов схем (соответствуют ГОСТу 2.743-72):

Инвертор Конъюнктор Дизъюнктор Сумматор по модулю 2



Выводы

Результатом выполнения данной курсовой работы является проведённое исследование не полностью определённой булевой функции от набора из пяти переменных, а именно: минимизация данной функции различными способами и построение комбинационных логических схем для каждого из вариантов минимизации. Методы, использованные в данной работе, дают представление о работе с различными вариантами представления булева выражения - аналитическом, табличном и графическом. Каждый из методов имеет как и свои плюсы, так и недостатки. На мой взгляд, наиболее простым из них является метод карт Карно, так как он прост в реализации и интуитивно понятен, что существенно снижает вероятность неправильного разрешения задачи минимизации. Схема, реализованная на базе дважды факторизованного выражения, оказалась проще своих аналогов, построенных с помощью методов Квайна - Мак-Класки/Петрика и карт Карно, но имеет максимальную задержку. Декомпозиция выражения в нашем случае не имеет смысла, поскольку в выражении отсутствуют похожие или противоположные термы. Однако, стоит заметить, что лучшей в реализации оказалась схема, построенная на основе полинома Жегалкина. Она выигрывает у своих аналогов и в цене, и в задержке, особенно это примечательно в сравнении показателей цены по Квайну со схемой, полученной методом Квайна - Мак-Класки/Петрика.

Итогом проведённой курсовой работы является приобретение и закрепление навыков работы с не полностью определённой булевой функцией, её минимизация различными способами и синтез комбинационных схем на основе минимизированных функций.



Список литературы и ссылки на Интернет-источники

1) «Синтез комбинационных схем. Учебно-методическое пособие по дисциплине «Дискретная математика». НИУ ИТМО, Санкт-Петербург 2006 г.

2) «Математическая логика. Курсовая работа. Методические указания к выполнению курсовой работы для студентов направления бакалавриата 10.03.01 - Информационная безопасность». Составитель - Рябова О.Н., СПбГУПТД, Санкт-Петербург 2019 г.

3) «Математическая логика. Курсовая работа. Методические указания к выполнению курсовой работы для студентов направления подготовки бакалавриата 10.03.01 - Информационная безопасность». Составитель - Тёрушкина О.Б., СПбГУПТД, Санкт-Петербург 2017 г.

4) ГОСТы: 2.105-95 (общие требования к документам), ГОСТ 7.32-2017 (структура и правила оформления отчётов о научно-исследовательских работах, изменён 09.2018), ГОСТ Р 7.0.5-2008 (библиографические описания), 2.743-72 (условные обозначения в графических схемах (логические элементы))

Размещено на Allbest.ru

...