Оригинальные методы реализации булевых функций в классах формул и схем из функциональных элементов в разных базисах (стр. 12 )

un = a0n2 + a1n + a2 (9.49)

Решаем систему линейных уравнений, получаемую из (9.49) (для n = 4, 5, 6) определенным выше способом, находя a0=2; a1=–10; a2 = 15, т. е. решение уравнения (9.48) есть un = 2n2 –10 n +15 . Возвращаемся к показателю LS

LS (F3(n), G3) = 2n2 –10 n +15. (9.50)

Улучшим оценку (9.50), моделируя ФУПК (9.46), то есть получаем F3(4), F3(5), F3(6), … и соответственно LS (F3(4)), LS (F3(5)), LS (F3(6)), … . При этом учитываем повторяющиеся подформулы (с целью ветвления выходов ФЭ) и находим сеточную функцию un (таблица 9.4) для показателя качества LS схемы S.

Таблица 9.4

n	4	5	6	7	8	9	…
un	7	12	17	22	27	32	…

Откуда выводим un =5n – 13 и соответственно индукцией по n, n=4, 5, 6, …, получаем

LS (F3(n), G3)min = 5n – 13, (9.51)

Методом структуризации (см. раздел 9.6) получаем:

- число итераций на основе ФУ типа 1 есть (n–3), причем при реализации начальных условий требуется семь ФЭ, в каждой из последующих (n–4) итерациях используется пять ФЭ; итого, повторили оценку (9.51)

LS(F3(n), G3) min = 5n – 13;

- для каждой из (n–3) итераций по структуре ФУ (9.45) получаем глубину фрагмента синтезируемой схемы, не более пяти, так как за счет уточнения уровней, на которых размещаются ФЭ, возможен их перенос только ко входу, итого,

DepS(F3(n), G3) £ 5n – 15. (9.52)

Заметим, что общий подход к определению глубины формулы (схемы) основывается на математической модели [25] - ФУПК

DepF(F3(n), G3) = max{ DepF(F3(n-1), G3); 1+DepF(F2(n-1), G3)}+1, (9.53)

по которой вычислительным методом находится сеточная функция un (таблица 9.5). При помощи таблицы 9.5 функция un находится аналитически, то есть un =n + 1, и, следовательно,

DepF(F3(n), G3)= n+1. (9.54)

Таблица 9.5

n	4	5	6	7	8	9	…
un	5	6	7	8	9	10	…

Для формулы F, полученной данным методом, изоморфно строится схема S (без ветвления), которая преобразуется на основе ФУ (9.33) и показатель LS минимизируется за счет ветвления, так как ФУ (9.33) и (9.55) это предоставляют. При получении оценок полезно также следующее разложение, в том числе для частичного распараллеливания вычислений и получения новых оценок,

F3(n) = ( F3(n-1) Å( xn × F2(n-1) ))= (F3(n-2) Å( xn-1 × F2(n-2) ))Å( xn × F2(n-1) ) =

= (( F3(n-3) Å( x n-2 × F2(n-3)))Å( x n-1× F2(n-2) ))Å( xn × F1(n-1) )=…=

= (( F3(3) Å( x4 × F2(3)))Å… Å ( x n-1× F2(n-2) ))Å( xn × F2(n-1) )=

= (x3 × F2(2))Å (x4 × F2(3))Å … Å (xn-1× F2(n-2) )Å (xn × F2(n-1) ) =

= Åni=3 (xi × F2(i-1) )= F, (9.55)

где F - искомая суперпозиционная формула, F2(i-1), i=3,4,…,n допускают разложение (9.21).

Таким образом, глубина

DepF(F3(n), G3) = DepS(F3(n), G3) = n+1 . (9.56)

9.5. Сложность ЭСП Жегалкина Fi(n) и Fn-(i-1)(n). Вначале рассмотрим свойства ЭСП Жегалкина Fi(n), 1 £ i £ n, в базисе G3, представляя их парами Fi(n) и Fn-(i-1)(n), i =1, 2, …, ën /2û. Для С-метода (по самим формулам) получаем для элементов пары совпадение основного показателя сложности LБ:

LБ(Fi (n), G3) = i× Cni = i× (n(n–1)… (n– (i–1))) / i! = (n(n–1)×…× (n– (i-1))) / (i-1)!

LБ(F n-(i-1)(n), G3) = (n– (i–1)) × Cn n-(i-1) =(n– (i–1)) × Cni-1 =

= (n– (i–1))× (n(n–1)×… × (n– (i–2))) / (i–1)! , (9.57)

откуда следует

Гипотеза. Если для элементов пары ЭСП Жегалкина Fi(n) и Fn-(i-1)(n), i =1, 2, …, ën /2û , изоморфно выполнять преобразования их ФУ, то при представлении этих ЭСП Жегалкина в классе формул или схем без ветвления соответствующие результаты для показателей качества совпадут.

На основе этих попарно равных основных показателей LБ ЭСП Жегалкина (начальные данные равны), действуя одинаковым образом, можно ожидать совпадение у них других показателей качества, или, получив выражения или оценки для показателей качества ЭСП Жегалкина Fi(n), 1 £ i £ ën /2û , можно ожидать их у ЭСП Жегалкина Fi(n), ën /2û £ i £ n .

Проведем исследование ЭСП Жегалкина

Fn-1(n) = x1 x2 .. xn-2 xn-1Åx1 x2 .. xn-2 xnÅ…Åx2 ..xn-1 xn , (9.58)

получаем ФУ

Fn-1(n) = F n-1(n-1) Å (xn × Fn-2(n-1) ), n ³ 3. (9.59)

Выполним разложение ЭСП Жегалкина Fn-1(n) в ряд по элементарным конъюнкциям с возрастанием числа переменных (от начала вычислений)

Fn-1(n) = F n-1(n-1) Å xn ×( Fn-2(n-2) Å( xn-1×Fn-3(n-2))) = … =

= F n-1(n-1) Å xn ×( Fn-2(n-2) Å xn-1×(Fn-3(n-3) Å … Å x4×( F2(2) Å x3×F1(2))…))=

= F n-1(n-1) Å xn ×( Fn-2(n-2) Å xn-1×(Fn-3(n-3) Å … Å x4×( F2(2) Å x3×(F1(1) Å x2))…))=

=((x1×…×xn-2) ×xn-1 ) Åxn×(x1×…×xn-2Åxn-1×(x1×…×xn-3Åxn-2×(x1×…×xn-3Å…

…Åx4×((x1×x2)Åx3×(x1Åx2 ))…))) = F , (9.60)

где в последнем равенстве F – искомая суперпозиционная формула, изоморфная схеме S без ветвления, но на ее основе строится схема S с ветвлением, не увеличивая глубину схемы.

Правые части скобочных формул (9.21) и (9.60) различные (как полиномы Жегалкина), первая из них вычисляется слева направо, а вторая – справа налево (порядок вычисления определяется скобками, которые проставляются для каждой итерации), но ФУ (9.21) и (9.60) имеют одно строение. По этой причине их структурные характеристики - показатели сложности-качества представления совпадают, если для синтеза применяется полностью один и тот же метод.

Продолжим исследование, подтверждающее связь соответствующих значений показателей сложности F2(n) и Fn-1(n) при использовании ФУ и их преобразований. Для ЭСП Жегалкина Fn-1(n) получаем ФУ (9.59).

Для (9.59) получаем оценки для показателя качества LБ С-методом и двумя методами на основе ФУПК.

С-методом (1-м способом) по ФУ (9.59) получаем оценку, эффективнее оценки (9.57),

(LБ(Fn-1(n), G3))1 = LБ(Fn-1(n-1), G3) + LБ(F n-2(n-1), G3) + 1=

= (n–1) + (n–2)(n–1) + 1 = n2 – 2 n + 2. (9.61)

Применение метода ФУ (2-й способ), действуя формально и используя связь между левой и правой частями (9.59) только по числу переменных, приводит к ФУПК

(LБ(Fn-1(n), G3))2 = LБ(Fn-1(n-1), G3) + LБ(F n-2(n-1), G3) + 1=

= LБ(Fn-1(n-1), G3)+ (n–2)(n–1) + 1 =

=LБ(F n-1(n-1), G3) + n2 – 3n +3, (9.62)

с начальным условием LБ(F3(3), G3) = u3 = 5.

Для (9.62) получаем разностное уравнение

un – un-1 = n2 – 3n +3, (9.63)

решением которого un является многочленом 3-й степени (9.39), удовлетворяющий начальному условию. Решаем систему линейных уравнений, получаемую из (9.39) (для n = 3, 4, 5, 6) определенным выше способом, находя a0=1/3; a1=-1; a2 = 5/3 ; a3=0, т. е. решение уравнения (9.63) есть un = n3/3 – n2 +5n/3 . Для показателя LБ получаем оценку

(LБ(Fn-1(n), G3)) 2 = n3/3 – n2 +5n/3. (9.64)

Применяем метод ФУ (3-й способ), учитывающий и сохраняющий связь степени полинома с числом переменных. Для (9.59) получаем ФУПК

LБ(Fn-1(n), G3) = LБ(Fn-1(n-1), G3) + LБ(F n-2(n-1), G3) + 1=

= (n–1) + LБ(F n-2(n-1), G3) + 1 = LБ(F n-2(n-1), G3) + n, (9.65)

с начальным условием LБ(F3(3), G3) = u3 = 5. Для (9.65) получаем разностное уравнение

un – un-1 = n, (9.66)

решением которого является многочлен 2-й степени (9.49) (на основе сеточной функции). Решаем систему линейных уравнений, получаемую из (9.49) для n = 3, 4, 5,

a052 + a15 + a2 = 14,

a042 + a14 + a2 = 9,

a032 + a13 + a2 = 5.

Получаем a0=1/2; a1=1/2; a2 = – 1, т. е.

un = (n2 + n – 2 ) /2, (9.67)

Возвращаемся к соответствующему показателю качества

(LБ(Fn-1(n), G3))3-й способ = (n2 + n – 2 ) /2, (9.68)

В данном случае из сравнения оценок (9.61), (9.64) и (9.68) для показателя LБ следуют неравенства

(LБ(Fn-1(n), G3)) 2 > (LБ(Fn-1(n), G3))1 > (LБ(Fn-1(n), G3))3 , т. е.

при n >1 следует эффективность 3-го способа (сохраняющего связь степени полинома с числом переменных) по сравнению с другими.

Для показателя качества LF получаем на основе (9.59) ФУПК

LF(F n-1(n), G3) = LF(F n-1(n-1), G3) + LF(F n-2(n-1), G3) + 2 (9.69)

и оценки. Первая оценка находится С-методом

(LF(F n-1(n), G3))1 = n –2 +( n – 2)Cn-1n-2 – 1+2 = n2 –2n +1. (9.70)

Вторая оценка определяется на основе ФУПК, учитывающего связь между левой и правой частями (9.59) только по числу переменных,

LF(F n-1(n), G3) = LF(Fn-2(n-1), G3) + (n–2) +2= LF(F n-2(n-1), G3) +n. (9.71)

Разностное уравнение для (3.5.10) совпадает с - уравнением для (3.5.15),

но начальное условие отличается и LF(F 2(3), G3) = u3 = 4 .

Решаем систему линейных уравнений для (9.49) и n = 3, 4, 5, получая a0=1/2; a1=1/2; a2 = – 2, т. е.

un = (n2 + n – 4 ) /2, (9.72)

и

(LF(F n-1(n), G3))2 = (n2 + n – 4 ) /2, (9.73)

Из сравнения оценок (9.70) и (9.73) следует эффективность метода ФУ.

При представлении этого полинома Жегалкина схемой S возможно использование ветвления, поэтому оценка (9.73) для числа подфункций является достижимой верхней оценкой для числа ФЭ в соответствующей схеме S, т. е. (9.72) – решение разностного уравнения здесь и

LS(F n-1(n), G3) = (n2 + n – 4 ) /2, (9.74)

Отметим, что имеют место равенства (в поддержку гипотезы)

LБ(F2(n), G3) = LБ(Fn-1(n), G3) = (n2 + n – 2 ) /2,

LF(F 2(n), G3)= LF(F n-1(n), G3) = (n2 + n – 4 ) /2,

LS(F2(n), G3) = LS(F n-1 (n), G3) = (n2 + n – 4 ) /2, (9.75)

DepS(F2(n), G3) = DepS(F n-1 (n), G3) = 2 n – 3.

9.6. Краткая функциональная характеристика методов. При реализации ЭСП Жегалкина в классах формул и схем в разных базисах разработаны следующие методы и средства минимизации показателей качества [32-48].

С-метод (“скорый”, упрощенный) позволяет непосредственно по имеющейся формуле (формально, без дополнительных преобразований, при необходимости они выполняются вначале) выводить основной показатель сложности LБ и производные от него.

Разложение ЭСП Жегалкина (9.21) и (9.55) в ряд по ЭСП Жегалкина, меньшей сложности (степеней полиномов, числа переменных) или по ЭК или линейным функциям - метод синтеза суперпозиционной формулы F, по которой в дальнейшем выводится схема S. Выполняя преобразования ФУ, включая перестановки отдельных подформул, получаем эквивалентные формулы F , в общем случае, различающиеся своими показателями качества. Используем для минимизации.

Синтез схемы методом структуризации позволяет на основе какого-либо ФУ представлять синтезируемую схему S, разбитой на ряд фрагментов. Они могут иметь однородную структуру и быть не подобными, но допускают определение показателей качества LS и DepS. При этом, в общем случае, выделяются три основные этапа: для n=n0 определяем начальный фрагмент схемы и его сложность LS на основе базиса. Для n= n0, n0 +1, …, (n – 1) последовательно повторяем типовой фрагмент схемы S , соответствующий полной итерации для вычисления, при этом для ветвления применяются или линейные функции F1(i), i = 1, 2, …, n–1, или различной местности конъюнкции Fi(i) , i = 1, 2, …, n–1, и последняя итерация, возможно неполная (разбиение итераций на три класса; см. пример: рис.9.1-9.3).

Метод ветвления это каждый метод синтез схем, который содержит алгоритм, позволяющий исследовать повторяющиеся подформулы в F и учитывать результаты с целью минимизации показателя LS (Замечание 9.1).

9.7. Нижние оценки сложности ЭСП Жегалкина. Для того чтобы судить о качестве алгоритмов синтеза, важно знать, насколько получаемая верхняя оценка отличается от минимальной. Но это сравнение осуществить невозможно, по крайней мере, сложно, астрономически трудоемко в вычислительном плане. Поэтому для сравнения полезно получать хорошие нижние оценки.

Рассмотрим отдельный подход для вывода нижних оценок сложности показателя LБ при эффективном представлении ЭСП Жегалкина F2(n)(x1, …, xn)=x1×x2 Åx1×x3 Å … Åxn-1×xn и F3(n)(x1, …, xn)=x1×x2×x3 Å x1×x2×x4 Å … Å xn-2×xn-1×xn в базисе G3.

Выпишем верхние и минимальные оценки показателей, которые получены ранее [33, 37] и рассматриваются в работе,

LБ(F2(n), G3) = (n2 + n – 2 ) /2, (9.76)

LБ(F3(n), G3) = n3/6 – n/6 – 1, (9.77)

LS(F2(n), G3)min = 3×n – 5, (9.78)

LS(F3(n), G3)min = 5×n – 13. (9.79)

Оценки (9.78) и (9.79) позволяют получить нижние оценки показателя LБ.

Пусть F(n) полином Жегалкина Fполином(n) или скобочная формула Fскоб. ф(n) в базисе G3 , представляющая функцию f (n). Напомним [4, 16], что

LБ(F(n)) = LF(F(n)) + 1. (9.80)

При этом для схемы S без ветвления LF = LS и

LБ(F(n)) = LS (F(n)) + 1. (9.81)

Пусть теперь получено LS(F(n))min за счет приведения формулы Fполином(n) к скобочному виду Fскоб. ф(n) в базисе G3 или за счет ветвления выходов ФЭ схемы S, или при использования обоих этих действий (других случаев логически нет). Тогда из условия получения оценки LS(F(n))min и равенства (4.6), с одной стороны, следует неравенство

LБ (F(n))³ LS(F(n))min + 1. (9.82)

С другой стороны, если формула F, задающая функцию f (n), бесповторный полином Жегалкина или приведена к бесповторному скобочному виду, то (9.82) становится равенством.

В общем случае (9.82) определяет нижние оценки сложности показателя LБ(F(n)).

Аналогично, для ЭСП Жегалкина Fi(n), 1£ i £ n, (9.82) принимает вид

LБ (Fi(n)) ³ LS(Fi(n))min + 1, (9.83)

Тогда, используя (9.76) и (9.и (9.79)), для показателя LБ запишем

3n–4 £ LБ (F2(n)) £ (n2 + n – 2 ) /2,

5n–12 £ LБ (F3(n)) £ n3/6 – n/6 – 1.

Данный подход применим также для получения нижних оценок сложности в классе монотонных, симметрических ДНФ в базисе G2.