Тихомирова Л.С. Методы минимизации булевых функций - файл n1.doc

приобрести
Тихомирова Л.С. Методы минимизации булевых функций
скачать (205.9 kb.)
Доступные файлы (1):

n1.doc

1820kb.

23.12.2002 07:54

скачать

n1.doc

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

Далее все производится по методу Квайна, но в кодовых значениях импликант. Рассмотрим это на примере 6.


Заменим исходные импликанты их кодами в двоичных переменных: 0011, 0100, 0101, 0111, 1001, 1011, 1100, 1101.

Разобъем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Можно все это сразу делать в таблице.

Данная функция			Результаты 1-го склеивания			Результаты 2-го склеивания
Коды	группы		Коды	группы		Коды	группы
0011	0-я	-	0-11	1-я	-011	-10-
0100	1-я	0100 *	-011		-100 *	-10-
0101	2-я	0011 *	010-		-101 *
0111		0101 *	0100	2-я	0-11
1001		1001 *	01-1		1-01
1011		1100 *	-101	3-я	01-1
1100	3-я	0111 *	10-1		10-1
1101		1011 *	1-01	4-я	010- *
		1101 *	110-		110- *

Далее строится таблица меток, но в нее вписываются исходные и первичные импликанты в виде двоичных кодов. Обратите внимание, что первичные импликанты записаны в другом порядке (согласно их группам), поэтому таблица меток выглядит иначе, чем в примере 5.

	0100	0011	0101	1001	1100	0111	1011	1101
-011		v					v
0-11		v				v
1-01				v				v
01-1			v			v
10-1				v			v
-10-	v		v		v			v

Обработка таблицы меток производится по методу Квайна.


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

Карта Вейча представляет собою специальную таблицу функции.

Рассмотрим карту для функции 2-х переменных.

								0	1
0	0	1		1	0		0	1	0
0	1	0
1	0	1		1	1		1	1	1
1	1	1

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

	1	0
	1	1

В карту вносятся значения функции, соответ-ствующие наборам переменных.


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

Записав члены СДНФ функции в соответствующих клетках, можно легко увидеть. Например, в приведенной выше карте.








Члены столбца склеиваются той переменной, которой соответствует весь столбец, а строки – вся строка.

Рассмотрим карту Вейча для функции 3-х переменных. Карту будем строить с симметричным расположением аргументов, один из них расположим с одной стороны, два других – с другой.



Разделим карту двумя осями, симметрично которым и будем располагать аргументы (см. карту).

Каждая клетка карты соответствует членам СДНФ функции, содержащим 3 знака.


Обратите внимание, что каждая пара соседних клеток может быть склеена, могут быть склеены любые четыре соседние клетки и все восемь.

Так можно склеить клетки 1 и 5, 1 и 2 и т.д., а также 2, 3, 6, 7; 1, 5, 4, 8 и т.д.

Если представить карту свернутой по вертикали в цилиндр, то крайние клетки окажутся рядом, их тоже можно склеить.



Рассмотрим несколько примеров

	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

нельзя склеить
П



риведем примеры карт Вейча для числа аргументов
































Размещение аргументов в карте Вейча может быть произвольным. Лучше располагать половину их на одной стороне другую половину на другой. Более удобен вариант с симметричным, относительно центральных осей, расположением аргументов.

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














Чтобы упростить отыскание нужной клетки в карте Вейча, целесообразно дополнительно пронумеровать строки и столбцы.

									0	0	0	0	1	1	1	1
									0	0	1	1	1	1	0	0
									0	1	1	0	0	1	1	0
00							00
01							01
11							1 1
10							10

---

5 метод. Метод Мак-Класки