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

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

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

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

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

*	0	1	х
0	0	Y	0
ai 1	у	1	1
x	0	1	х

^{ }_^{}

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 определяются согласно следующей таблице.

∩	0	1	x
0	0		0
ai 1		1	1
x	0	1	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

001 10х

0   общей части у 100  100 общая часть

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

3) _х1х 4) _0хх

0хх 0х0

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

операцией *)

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

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

	0	1	x
0	z	y	z
ai 1	y	z	z
x	1	0	z

^{ }_^{}

b_i

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

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

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

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

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

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

1) _х1х 2) _ х1x

x11 110

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-экстремалей;

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