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

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

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

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

Операция умножения кубов (*).Операцияумножения кубов а=а₁а₂...а_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-экстремалей;

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