30 Метод Квайна −Мак-Класки

Этот метод ориентирован на числовое задание ФАЛ в виде кубического комплекса, состоящего из 0-кубов. Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Основной недостаток метода Квайна – необходимость выполнения полного сравнения (склеивания) всех первичных импликант. В случае большого их количества сложность этого сравнения существенно возрастает

f _СДНФ(x₁x₂x₃x₄) = V (2, 3, 4, 6, 9, 10, 11, 12).

Сформируем кубический комплекс K, состоящий из 0-кубов:K=(0010, 0011, 0100, 0110, 1001, 1010, 1011, 1100).

Выполнив разбиение комплекса K на группы, получим:

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

После выполнения первого шага алгоритма простых импликант не выявлено. Полученные 1-кубы разобьем на n групп кубов в зависимости от местоположения свободной координаты в кубе.

, .

Далее выполняется сравнение кубов внутри каждой из групп. В результате могут быть получены 2-кубы, которые, в свою очередь, аналогично 1-кубам будут объединены в группы по совпадению свободных координат и вновь будет выполнено сравнение. На каждом шаге сравнения выявляются кубы, не участвовавшие в образовании новых кубов, и исключаются из дальнейшего упрощения. Для рассматриваемого примера сравнение в группах …привело к образованию двух новых кубов х01х и х01х и кубов, не образовавших новых {х100, 0х10, 10х1, 01х0}..

Дальнейшее сравнение не приводит к формированию новых кубов . Таким образом, получено множество простых импликант:

f_{сокр.ДНФ}={х100, 0х10, 10х1, 01х0, х01х} .

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

простая импликант	Конституенты единицы
	0010	0100	0011	1100	0110	1001	1010	1011
Х100		*		*
0х10	*				*
10х1						*		*
01х0		*			*
Х01х	*		*				*	*

Из табл =>, что простые импликанты x100, 10x1, x01x являются обязательными. Оставшиеся две простые импликанты не являются обязательными и образуют следующие две тупиковые формы.

f _МДНФ = {х100, 10х1, х01х, 0х10} – 1-я тупиковая форма;

f _МДНФ = {х100, 10х1, х01х, 01x0} – 2-я тупиковая форма.

31 Алгоритм извлечения (Рота)

алгоритм извлечения (Рота) на примере минимизации булевой функции, заданной покрытием С₀

Исхе покрытие С₀задано объедин-ем мн-в кубовLиN. Кубы комплексаN− это наборы, на к-ых ф-ция не опред-а и к-ые включаются в покрытие ради возможного дополнит упрощения комплексаLв процессе минимизации. Мин покрытие комплексовLиN, С_minназывается К-покрытиемL.Общ алгоритм построения мин К-покрытия наз-ся алгоритмом извлечения и состоит:1) нахождении множества Z простых импликант комплекса К; 2) выделении L-экстремалей на множестве Z; 3) применении алгоритма ветвления при отсутствии L-экстремалей; 4) нахождении абсолютно минимального покрытия из некоторого множества избыточных покрытий. Нахождение множества простых импликант

Преобразование исходного покрытия С₀ комплекса К в мн-во простых импликант Z осущ-ся с помощью операции * кубов. В результате первого шага (С₀*С₀) предусматривается выявление как новых кубов С_y (1-ой и более высокой размерности), так и кубов, к-ые не образуют нов кубов (вкл-ся в мн-во Z₀). Из пол-ных нов кубов обр-ся мн-во А₁. Также формируется мн-во В₁=С₀-Z₀. Для следующего шага получения мн-ва Z формируется мн-во С₁=А₁U В₁. Для уменьшения мощности мн-ва кубов С₁ выполним операцию поглощения (удаления) кубов, образующих множество С₁, кубами из множества А₁ (А₁Í С₁).

С0*С0	х010	0х10	0000	0х01	1110	1x10
х010	-
0х10	0010	-
0000	00у0	00у0	-
0х01	ø	ø	000у	-
1110	1у10	у110	ø	ø	-
1х01	ø	ø	ø	ух01	ø	-
А1	00х0	х110	000х	хх01
	1х10

Для рассматриваемого примера получим: (см дальше)

Среди кубов С₀, возможно, находятся такие кубы, которые с кубами множества А₁ могут дать новые кубы или оказаться простыми импликантами после второго шага (С₁*С₁). При формировании таблицы для выполнения операции С₁*С₁ (табл. 17) следует учесть, что В₁*В₁ уже выполнялось на шаге С₀*С₀. => С₁*С₁=(А₁*А₁)U(А₁*В₁).

00х0

1х10

00х0 000х А₁ 00х0

1х10 х110 1х10

А₁ = х110 хх01 после выполнения 000х

000х С₁= х010  операции  С₁= х110

хх01 0х10 поглощения хх01

0000 В₁ х010

Z₀=Ø 0х01 0х10

1110

1х01

С1*С1	00х0	1х10	000х	х110	хх01
00х0	-
1х10	у010	-
000х	0000	ø	-
х110	0у10	1110	ø	-
хх01	000у	ø	0001	ø	-
х010	0010	1010	00у0	ху10	Ø
0х10	0010	ух10	00у0	0110	Ø
А2	ø	хх10	ø	хх10	Ø

В результате выполнения умножения С₁*С₁ получим:

А₂={хх10},

Z₁=

00х0 _.

000х Куб хх01 не дал нового куба. Но это куб второй размерности и новые кубы может дать на третьем шаге (С₂*С₂).Поэтому его не следует включать в число кубов, образующих множество Z₁.

1х10 хх10

х110 1х10

В

C₂=А₂UB₂=

=

₂ = хх01 , х110 хх10 _.

х010 х010 хх01

0х10 0х10

С2*С2	хх10
хх10	-
хх01	Ø
А3	Ø

Таким образом, получим А₃= Ø, следовательно, новых кубов нет.

Z₂=

хх10_.

хх01 В₃=С₂-Z₂= Ø; C₃=A₃UB₃= Ø.

На этом процесс выявления простых импликант окончен.,

00х0

Z=Z₀UZ₁UZ₂=

- сформированное множество простых импликант.

000х

хх01

хх10 Необходимо выяснить, не содержатся ли в этом множестве “лишние” простые импликанты.