Математичекие основы теории систем анализ сигнального графа и синтез комбинационных схем (стр. 7 из 9)

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

2.3.2 Пример минимизации методом Квайна-Мак-Класки.

При минимизации по данному методу предполагается, что минимизируемая функция задана в СДНФ. Метод Квайна – Мак – Класки состоит из последовательного выполнения следующий этапов.

Метод Квайна состоит из последовательного выполнения этапов:

1) Нахождение первичных импликант

2) Расстановка меток

3) Нахождение существенных импликант

4) Вычеркивание лишних столбцов

5) Вычеркивание лишних

6) Получение минимального покрытия

Выполним, приведенные этапы, для функции У₃.

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

СДНФ, которую мы нашли ранее, для функции У₃ имеет вид:

Составим минитермы для этой функции:

Таблица 2.2.1

Минитермы длиной 4		Минитермы длиной 3
Нулевая группа	0000+	Нулевая группа	0-00
Первая группа	0100+	Первая группа	-100, -011
Вторая группа	1100, 1010, 0011	Вторая группа	11-0, 1-10, 101-
Третья группа	1110, 1011

Расстановка меток. Остальные этапы нужны, чтобы отбросить некоторые первичные импликанты. На данном этапе составляется таблица, число строк которой равно числу полученных первичных импликант, число столбцов совпадает с числом минитермов СДНФ. Если в некоторый минитерм СДНФ входит какая – либо из первичных импликант, то на пересечении соответствующего столбца и строки ставится метка. В таблице 2.2.2 приведем результат расстановки меток:

Таблица 2.2.2

		0000	0100	1100	1010	0011	1110	1011
0	1	2	3	4	5	6	7
1	0-00	У	У
2	-100	У	У
3	-011	У	У
4	11-0	У	У
5	1-10	У	У
6	101-	У	У

Нахождение существенных импликант. Если в каком – либо из столбцов таблицы меток стоит только одна метка, то первичная импликанта, стоящая в соответствующей строке, называется существенной импликантой. Все существенные импликанты запоминаются. А из таблицы меток исключаются строки, соответствующие существенным импликантам, и столбцы минитермов «покрываемых» этими существенными импликантами.

Существенными являются импликанты 0-00 и -011. Поэтому вычеркиваем 1-ю и 3-ю строки и столбцы: 1, 5, 2, 7.

Составим сокращенную таблицу меток:

Таблица 2.2.3

	1100	1010	1110
-100	У
11-0	У	У
1-10	У	У
101-	У

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

С учетом существенных импликант получим две МДНФ для этой функции имеет вид:

1.

2.

Число букв составляющих простые импликации в каждом варианте одинаково. Во втором варианте на одно отрицание меньше, поэтому берем его за искомое:

2.3.3 Пример минимизации картами Карно

Данный метод для минимизации функции в коде Грея. В каждую ячейку записывается значение функции на данном наборе. Затем выделяются группы ячеек размером 2^a*2^b , где a, bε[0,1,2…], в которых функция принимает значение «1». В каждую группу должно входить максимальное число ячеек. Таких групп должно быть минимальное количество. Каждой группе будет соответствовать конъюнктивный член размером n-a-b. Для получения МДНФ каждую группу надо просматривать в горизонтальном и вертикальном измерениях, с нахождения таких переменных, которые не меняют своего значения в пределах группы. Если переменная не меняет своего нулевого значения, то она вписывается в конъюнкцию с отрицанием, если не меняет своего единичного значения, то вписывается без отрицания. Если имеются разорванные группы, то карту Карно надо свернуть в цилиндр. На неопределенных наборах следует доопределить нулем или единицей, в соответствии с выбираемой группой ячеек. Каждая единичная ячейка должна быть включена хотя бы в одну группу.

Составим карту Карно для функции У₃ (рисунок 2.3.1).

x3x4
x1x2	00	01	11	10
	00	1	1
	01	1
	11	1	1
	10	1	1

Рис. 2.3.1 Карта Карно для функции У₃

Таким образом, для функции У₃ в МДНФ будет иметь следующий вид:

2.4 Совместная минимизация всех функций

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

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

Составим карты Карно для всех функций таблицы истинности (таблица 2.1.1)

1	*	1	1	*	1	1	*	1	1	*	1	1	*	1
*	*	1	*	*	1	*	*	1	*	*	1	1	*	*	1
*	*	1	1	*	*	1	*	*	1	*	*	1	1	*	*	1
*	1	1	*	1	*	1	1	1	*	1	1	*	1	1

1	*	1	1	1	*	1	1
1	*	*	1	1	*	*
1	*	*	1	*	*	1
1	*	1	*	1	1

Тогда МДНФ этих функций будет иметь вид: