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

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

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х} .

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

Таблица 15

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

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

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

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

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

Специальные логические операции алгоритма Рота: *, ∩ , #

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

Операция умножения кубов (*).Операцияумножения кубов а=а₁а₂...а_n и b=b₁b₂...b_n обозначается как с=а*b и служит для образования r-куба, противоположные (r-1) грани которого содержатся в кубах а и b. Предварительные координаты куба c определяются в соответствии с таблицей, приведенной ниже.

*			х
		Y
ai 1	у
x			х

^{î ______________}_Ú^{_________________þ}

b_i

Окончательно координаты куба формируются:

m(a₁*b₁)m(a₂*b₂) ... m(a_n*b_n), если a_i*b_i=y только для одного i,

a*b=

Æ, если a_i*b_i=y для i ³ 2,

где m(a_i*b_i) – окончательная i-я координата куба с; m(0)=0; m(1)=1; m(x)=x;

y – условное обозначение того, что координаты a_i и b_i противоположны.

Эта операция соответствует операции склеивания: образуется новый r-куб, если кодовое расстояние двух исходных кубов равно 1.

Рассмотрим некоторые примеры, графическая интерпретация которых приведена на рис. 26.

1) 011 2) 11х

*001*01х

0y1 Þ 0x1– ребро покрывает две вершины у1х Þ х1х – грань

3) 0х1 4) х1х

*1х0 *011

уху Þ Æ – две координаты имеют значение у. 011

Операция пересечения кубов (∩).Операция пересечения кубов а=а₁а₂...а_n и b=b₁b₂...b_n обозначается как с=а∩b и служит для выделения куба с=с₁с₂...с_n , являющегося общей частью кубов а и b. Координаты с₁с₂...с_n определяются согласно следующей таблице.

∩			x
		Æ
ai 1	Æ
x			x

^{î______________}_Ú^{_________________þ}

b_i

m(a₁∩b₁)m(a₂∩b₂) ... m(a_n∩b_n,),

a∩b=

Æ, если существует такое i, для которого a_i ∩ b_i =Æ,

где m(a_i*b_i) – окончательная i-я координата куба с; m(0)=0; m(1)=1; m(x)=x.

Рассмотрим примеры и их графическую интерпретацию (рис. 27).

1) _Ç100 2) _Ç1х0

00110х

Æ0Æ Þ Æ общей части у 100 Þ 100 общая часть

кубов нет кубов (рёбер) - вершина

3) _Çх1х 4) _Ç0хх

0хх 0х0

01х Þ 01х общая часть – ребро 0х0 ( совпадает с

операцией *)

Операция вычитания кубов (#).Операция вычитания из куба а=а₁а₂...а_n куба b=b₁b₂...b_n обозначается как с=а#b и служит для удаления из куба а общей части кубов а и b.

Координаты куба с формируются согласно следующей таблице.

#			x
	z	y	z
ai 1	y	z	z
x			z

^{î ______________}_Ú^{_________________þ}

b_i

Æ, если для любого i а_i#b_i=z,

c=а#b= a, если существует такое i, что а_i#b_i=y,

U а₁а₂...а_i-1 a_i а_i+1 ... а_n, если a_i равно 0 или 1 для одного или

ⁱ⁼¹ нескольких i,

где z означает, что координаты совпадают, а y, как для операции *, означает, что координаты a_i и b_i противоположны.

По этим a_i-координатам производится объединение (U) кубов, получаемых в результате замены в кубе а символа х на соответствующее значение (0,1) координаты a_i. Рассмотрим примеры выполнения операции # и их графическую интерпретацию (рис. 28).

1) _#х1х 2) _# х1x

x11110

zz0 Þ x10 0z1 Þ 01x

3) _#хx1 4) _#х11 x11

x10 xx1

z0y Þ xx1 zzz Þ Æ

5) _# 0ххx

хх01

zz10 Þ 0x1x

0xx0

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

Рис. 29. Геометрическое задание исходного покрытия

Исходное покрытие С₀ задано объединением множеств кубов L и N. Кубы комплекса N − это наборы, на которых функция не определена и которые включаются в покрытие ради возможного дополнительного упрощения комплекса L в процессе минимизации. Минимальное покрытие комплексов L и N, С _min называется К-покрытием L.

Общий алгоритм построения минимального К-покрытия называется алгоритмом извлечения и состоит в следующем:

▪ нахождении множества Z простых импликант комплекса К;

▪ выделении L-экстремалей на множестве Z;

▪ применении алгоритма ветвления при отсутствии L-экстремалей;

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