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

Изучение примеров приводит к следующим выводам, которые ниже по тексту уточняются и дополняются:

1. представление в виде скобочной формулы по сравнению с ДНФ эффективно по показателям LБ, LF и LS (уменьшает величины), но для показателей глубины DepF и DepS может уменьшать, увеличивать или оставлять их значения без изменения;

2. при представлении в классе схем ветвление на основе самой сложной (по показателю FБ) подформулы уменьшает значение показателя LS, но может увеличить значение показателя DepS;

3. увеличение числа n переменных функции не уменьшает значения показателей сложности; только по одному показателю имеется сохранение, а по всем остальным увеличение.

8. Функциональные и разностные уравнения

8.1. Функциональные уравнения

Для оптимизации синтеза необходимо иметь больше фактов из теории булевых функций и использовать их в алгоритмах синтеза. Новые знания удобно получать при помощи функциональных уравнений (ФУ) [38- 48].

Определение 8.1. Пусть X - множество булевых переменных, g(2) - двухместная булева функция, задающая начальный член f(2) последовательности изучаемого класса функций f (n)(X), n ³2, и h(2) - функция рекурсии, входящие в базис G или представляется через базисные функции. Тогда рекуррентное соотношение, получаемое на основе операции суперпозиции,

(8.1)

где X1ÈX2 = X, X1ÇX2 = Æ, n1,n2ÎN, n=n1+n2, назовем основным функциональным уравнением (ФУ), несмотря на частный характер местности функций g(2 ) и h(2), которые выбраны двухместными для учета замечания 7.1 (для изучения порождающих базисов). Но ниже имеется обобщение на различную местность функций g(n¢ ) и h(n¢¢ )). Данное определение ФУ отлично от - [18, 19].

Соотношение (8.1) применяется к аргументам функции h и так далее, позволяя получить суперпозиционную формулу F, реализующую функцию f(n). Таким образом, ФУ представляет собой конструктивный метод построения булевых функций определенного класса на основе заданных, используя соответствующее рекуррентное соотношение.

При n1=n–1, n2=1 получаем ФУ типа 1

f (n) = h ( f (n-1) , xn), (8.2)

для симметрических функций при n =2s, s = 1,2,…, n1 = n2 = n/2 получаем ФУ типа 2

f (n)(X) = h ( f (n/2)(X1), f (n/2)(X2)), (8.3)

т. е. конечное n-множество аргументов разбивается пополам;

при n1=n–2, n2=2 это будет ФУ типа 3

f (n) = h(3)( f (n-2) , xn-1, xn), (8.4)

где h(3) –трехместная булева функция.

Соотношение (8.4) имеет обобщения, например,

f (n¢+(s-1)×(n¢¢-1 )) = h ( f (n¢+(s-2)×(n¢¢ -1)), xn¢¢–1,…, xn), (8.5)

где n =n¢+ (s-1)×(n¢¢–1), s = 1,2, …, s0 .

ФУ и базис G с функциями g(n¢ ) и h(n¢¢ ) (n¢ ³ 2 и n¢¢ ³ 2) полностью (с показателями качества) определяют формулу F и схему S.

В общем случае, ФУ (8.1) для заданного n ³ 2 применяется как уравнение относительно искомой функции f (n) и ставится задача ее нахождения в определенном базисе (с показателями качества) или метод декомпозиции заданной булевой функции f (n), или метод получения классов эквивалентностей. Поэтому решение указанных задач следует сводить к получению таких уравнений.

Метод ФУ применим для получения классов как симметрических, так и несимметрических булевых функций, используя различные базисы. ФУ для данных функций g(2) и h(2) в зависимости от базиса G допускают различные преобразования, характеризующиеся своими показателями качества, например, преобразование (8,2) в f (n) = h (xn , f (n-1) ) для симметрической функции h сохраняет ее, а для несимметрической функции это, в общем случае, новая функция) .

На основе ФУ типа 1 рассмотрим примеры получения функций, симметрических по отдельным группам переменных [20].

Пример 8.1. Для f (2)= g(2)(x1, x2)= x1 ® x2, h(2) = t1×t2 и n=5 за четыре итерации получаем симметрическую функцию f (5)= (((x1 ® x2)×x3)×x4)×x5 по переменным x3, x4, x5 .

Пример 8.2. Для f (2)= g(2)(x1, x2)= x1×x2, h(2) = t1 ®t2 и n=5 аналогично получаем симметрическую функцию f (5)= (((x1×x2) ®x3) ®x4) ® x5 по переменным x1 и x2 .

Пример 8.3. Для f (3)= g(3)(x1, x2, x3)= x1 Å x2 Åx3, h(2) = t1×t2 и n=5 за три итерации получаем симметрическую функцию f (5)= ((x1 Å x2 Åx3) ×x4)×x5 по переменным x1, x2, x3 и - x4, x5 .

8.2. Разностные уравнения. Основному ФУ для каждого показателя сложности-качества соответствует свое разностное уравнение, которое назовем функциональным уравнением показателя качества (ФУПК). Для решения ФУПК записываем как разностное уравнение типа (8.6), в стандартной форме [21,22]. С тем, чтобы не решать ФУПК для каждого показателя полезно их трансформировать в свои разностные уравнения (в совокупности возможно меньшим числом) и численно или аналитически получить решение.

Во встречающихся ниже случаях часто получаем разностное уравнение первого порядка линейное неоднородное, приводимое к виду

un = qn-1 ×un-1 + dn-1, (8.6)

где заданные: qn-1 –коэффициенты; dn-1 –свободные члены, n ³ 3. Для заданного начального условия u2 (при n=2) уравнение (8.6) имеет единственное решение. Из (8.6) последовательно определяем, получая решение

u3 = q2 ×u2 + d2, u4 = q3 ×q2 ×u2 + q3 ×d2 + d3,

u5 = q4 × q3 ×q2 ×u2 + q4 ×q3 ×d2 + q4 ×d3 + d4, … ,

un = qn-1 … q3 ×q2 ×u2 + qn-2 … q3 ×d2 + … + qn-1 ×dn-2 + dn-1 =

= (8.7)

Для уравнения (8.6) с постоянными коэффициентами qi = q ≠1 и - правой частью di = d решение (8.7) принимает вид

un = (8.8)

Если же q =1, то получаем арифметическую прогрессию и решение

un = u2 + d×(n – 2), (8.9)

где 2 есть значение переменной n и номер индекса переменной для начального условия.

Некоторые ФУПК трансформируются в разностные уравнения второго порядка

un = qn-2 ×un-2 + dn-2, (8.10)

где заданные: qn-2 –коэффициенты; dn-2 –свободные члены, n ³ 3 ; для которого начальные условия определяются при помощи соответствующего ФУПК.

В случае, если решением уравнения (8.6) является многочлен, то его коэффициенты определяются решением специальной системы k линейных уравнений с k неизвестными, определитель которой отличен от нуля,

a0 n k-1 + a1 n k-2 +… + a k-2 n + a k-1 = b k-1, n= n1 , n2 , …, n k, (8.11)

эффективной процедурой последовательного исключения неизвестных за число только арифметических операций (сравнение и выбор главного элемента не используются, см. раздел 9):

(k + 1) (( k –1) + ( k –2) + … + 1 ) + (k + 2) ( k –1) =

= (k + 1) k ( k –1) / 2 + (k + 2) ( k –1) =

= (k3 + 2k2 +k – 4)/2 . (8.12)

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

Замечание 8.1. Изучение ФУ приводит к выводу о том, что метод ФУ полезно рассматривать с разных позиций – функциональной и структурной. Первая позволяет получать классы функций f(n) - задающие их суперпозиционные формулы F. Вторая же – позволяет составить общую структурно-функциональную схему S из ФЭ (выделяя начальные условия, итерации, завершающую итерацию) и получать значения показателей сложности (см. раздел 9.6).

Моделирование ФУПК также используется для получения оценок показателей качества. Упрощая или конкретизируя правую часть ФУПК, получаем некоторое приближение для оценки показателя качества (см. замечание 8.1). Эквивалентно преобразуя ФУ, будем получать требуемую функцию, задаваемую, возможно, другой суперпозиционной формулой, и, в общем случае, другие значения показателей качества, то есть представляется возможность минимизировать требуемое представление исходной функции в классах формул и схем.

Отметим схематично основные этапы метода ФУ, которые в процессе применения его могут ниже корректироваться: выбор ФУ, используемого для построения суперпозиционной формулы F и схемы S из ФЭ; на основе ФУ получение семейства ФУПК и начальных условий для них; замена ФУПК соответствующими разностными уравнениями (в совокупности, возможно меньшим числом); решение разностных уравнений, с получением сеточной функции или аналитического решения; интерпретация полученных решений к исходным показателям качества ФУПК.

8.3. Некоторые эквивалентности на основе ФУ:

1. fÚ(n) = (x1 Å 1) (x2 Å 1) … (xn Å 1) Å 1, т. е.

x1Ú x2 Ú … Ú xn = (x1 Å 1) (x2 Å 1) … (xn Å 1) Å 1,

2. fÚ(n) Å 1 = (x1 Å 1) (x2 Å 1) … (xn Å 1), т. е.

= (x1 Å 1) (x2 Å 1) … (xn Å 1).

9. Элементарные симметрические булевы функции

Напомним, что булева функция f(n), значения которой не меняются при любой перестановке ее переменных x1 , x2 , …, xn, называется симметрической, то есть

f (x1 , x2 , …, xn) = .

Если для набора a=(a1 , a2 , …, an) значений переменных x1 , x2 , …, xn, симметрическая функция f(n)(a) = 1 и набор a содержит ровно i, 1 £ i £ n единиц (остальные нули), то для любого набора a¢ значений переменных x1 , x2 , …, xn, содержащего также ровно i единиц, функция f(n)(a¢ ) = 1. В этом случае число i называется рабочим числом симметрической функции f(n).

Назовем симметрическую функцию с одним рабочим числом i, 1 £ i £ n, элементарной СБФ, обозначая ее как fi(n) [4,20]. Их число n и каждые две из них ортогональны, т. е. произведение двух различных элементарных СБФ есть константа 0.

9.1. Элементарные симметрические полиномы (ЭСП) Жегалкина.

Имеется n ЭСП Жегалкина, зависящих от переменных множества X = {x1, …, xn} (n ³2)

F1(n)(x1, …, xn) = x1 Å … Åxn,

F2(n)(x1, …, xn)=x1×x2 Å x1×x3 Å … Å xn-1×xn , (9.1)

…

Fn(n)(x1, …, xn) = x1×… ×xn ,

где в их обозначениях верхний индекс n – число переменных; нижний - i, 1 £ i £ n, - степень ЭСП Жегалкина, т. е. Fi(n) – понимается как сумма по mod 2 ЭК (числом Cn i), содержащих i всевозможных множителей из n переменных (1 £ i £ n) [23] . Применяются также частные случаи: ЭСП Fi(j), где верхний индекс j, j £ n, есть число переменных; назначение нижнего индекса i сохраняется - степень ЭСП Жегалкина. Аналогично определяются симметрические полиномы в классе монотонных ДНФ в базисе G2 [40-48].

Для ЭСП Жегалкина Fi (n), 1 £ i £ n, получаем “грубые” оценки показателей сложности на основе прямого подсчета и использования метода структурно-функциональной декомпозиции [31-37]. Это, так называемый, С-метод вывода показателей сложности для формул вида ЭСП Жегалкина (см. раздел 9.6):

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

1 £ i £ n (при i=1 или n минимальные), откуда получаем оценки

LF(Fi (n), G3) = LS(Fi (n), G3) = LБ(Fi (n), G3) – 1, (9.3)

DepF(F i(n), G3) = DepS (Fn-(i-1)(n), G3) £ élog2 (LБ(Fi (n), G3))ù +1.

Эти оценки будем сравнивать с оценками, получаемыми ниже. Заметим, что оценка (9.4) получена на основе распараллеливающей декомпозиции [31].

9.2. Сложность функций из простых классов. При i=1 или n приходим к ЭСП Жегалкина F1(n)=f (n) и Fn(n)=f (n), где функция f (n) одного класса из - & или Å с одинаковыми алгебраическими свойствами. Поэтому исследование их выполнено на примере функции из класса & (можно любой из них) методами структурно-функциональной декомпозиции (последовательной и параллельной), где в совокупности получены минимальные значения рассматриваемых показателей качества [31],

LБ(f (n), g&(2) ) min = n,

LF(f (n), g&(2) ) min = n - 1,

DepF(f (n), g&(2)) min = élog2 nù, (9.4)

LS (f (n), g&(2) ) min = n - 1,

DepS(f (n), g&(2)) min = élog2 nù,

где g&(2) - двухместная базисная функция для класса &.

Повторим результаты, получая их методами ФУ. Из (8.2) получаем следующее ФУ типа 1:

f (n)(X)= h(2)( f (n-1), xn)= (f (n-1) & xn), (9.5)

где n=3, 4, …, начальные условия f&(2)(x1, x2)=g&(2)(x1, x2)=(x1x2), функция рекурсии h&(2)( t1, t2)=(t1t2). Для показателей сложности (по числу букв, подформул и глубине формулы F ; числу ФЭ и глубине схемы) устанавливаем рекуррентные соотношения - ФУПК

LБ(f (n), g&(2) ) = LБ(f (n-1), g&(2) )+1,

LF(f (n), g&(2) ) = LF(f (n-1), g&(2) )+1,

DepF(f (n), g&(2))= DepF( f (n-1), g&(2) )+ 1, (9.6)

LS(f (n), g&(2) ) = LS(f (n-1), g&(2) )+1,

DepS(f (n), g&(2))= DepS( f (n-1), g&(2) )+ 1.

ФУПК (9.6), отвлекаясь от их назначения, являются разностными уравнениями (по [25] это рекуррентные соотношения), причем им со своими начальными условиями

LБ( f&(2), g&(2))=2, (9.7)

LF(f&(2), g&(2))= DepF( f&(2), g&(2))=LS(h&(2), g&(2))= DepS( f&(2), g&(2))=1,

соответствует одно разностное уравнение

un – un-1 = 1 . (9.8)

Решая (9.8) (начальные условия в скобках), получаем оценки сложности

LБ(f (n), g&(2) ) min = n, (u2=2),

LF(f (n), g&(2) ) min = n - 1, (u2=1),

DepF(f (n), g&(2)) = n -1, (u2=1), (9.9)

LS (f (n), g&(2) ) min = n - 1, (u2=1),

DepS(f (n), g&(2))= n -1, (u2=1).

ФУ типа 1 позволяет проводить последовательную декомпозиции, качество которой характеризуется минимальными значениями показателей LБ и LF для формул и LS для схем.

Если n =2k, k = 2,3,…, то n1=n2=n/2 и из (8.3) приходим к ФУ типа 2

f (n)(X) = h( f (n/2)(X1), f (n/2)(X2)) = (f (n/2)(X1) & f (n/2)(X2)), (9.10)

или f (k)(X) = h( f (k-1)(X1), f (k-1)(X2)) = (f (k-1)(X1) & f (k-1)(X2)),

где X1ÈX2 = X, X1ÇX2 = Æ. На основе (9.10) получаем ФУПК для показателей сложности

LБ(f (k)(X), g&(2)) = 2LБ(f (k-1)(X1), g&(2)),

LF (f (k), g&(2) ) = 2LF (f (k-1)(X1), g&(2) )+1,

Dep F(f (k), g&(2))= Dep F( f(k-1)(X1), g&(2) )+ 1, (9.11)

LS(f (k), g&(2) ) = 2LS(f (k-1)(X1), g&(2) )+1,

DepS(f (k), g&(2))= DepS( f(k-1)(X1), g&(2) )+ 1,

которым соответствуют три разностных уравнения с уточненными начальными условиями (9.7) .

Причем показателю LБ соответствует разностное уравнение

uk – 2uk-1 = 0 , u2=4, (9.12)

показателям LF и LS соответствует -

uk – 2uk-1 = 1, u2=3, (9.13)

показателям Dep F и DepS соответствует -

uk – uk-1 = 1, u2=2. (9.14)

Решая уравнения (9., получаем оценки показателей сложности

LБ(f (n), g&(2) )min =2k = n, k = 2,3,…,

LF (f (n), g&(2) ) min =2k-1= n - 1,

DepF(f (n), g&(2)) min = k = log2 n = élog2 nù , (9.15)

LS (f (n), g&(2) ) min =2k-1= n - 1,

DepS(f (n), g&(2)) min = k = log2 n = élog2 nù.

ФУ типа 2 позволяет проводить параллельную декомпозицию и строить параллельно-последовательные схемы, минимальной сложностью по всем рассматриваемым показателям, совпадающей с - последовательной декомпозицией по показателям LБ, LF и LS.

9.3. Сложность ЭСП Жегалкина F2(n). Представление ЭСП Жегалкина

F2(n)= x1×x2 Å x1×x3 Å … Å xn-1×xn , n ³2, (9.16)

в базисе G3 получено на основе ФУ типа 1

F2(n) = (F2(n-1) Å( xn × F1(n-1))), n ³3. (9.17)

Реализация функции F2(n) на основе ФУ (9.17) характеризуется следующими пятью ФУПК, сводимых к трем разностным уравнениям,

LБ(F2(n), G3) = LБ(F2(n-1), G3) + LБ(F1(n-1), G3) + 1 ,

LF(F2(n), G3) = LF(F2(n-1), G3) + LF(F1(n-1), G3) + 2 ,

DepF(F2(n), G3) = max{DepF(F2(n-1), G3); 1+DepF(F1(n-1), G3)} + 2, (9.18)

LS(F2(n), G3)= LF(F2(n), G3),

DepS(F2(n), G3)= DepF(F2(n), G3),

причем здесь схемы S без ветвления (см. ниже Замечание 9.1).

Решение этих ФУПК с начальные условия для n =2:

F1(2) (x1, x2) = x1 Å x2, F2(2)(x1, x2) = x1 x2,

LБ(F2(2), G3)=2, LБ( F1(2), G3)=2, LF(F2(2), G3)=1, LF(F2(2), G3)=1, (9.19)

DepF(F2(2), G3) = 1, DepF(F1(2), G3) = 1, LS(F2(2), G3) = 1, LS(F1(2), G3) = 1, DepS(F2(2), G3) = 1, DepS(F2(2), G3) = 1,

получим методом математического моделирования. Его результаты

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

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

DepF(F2(n), G3) = 2×n –3, (9.20)

LS(F2(n), G3) = (n2 + n – 4 ) /2,

DepS(F2(n), G3) = 2×n -3.

Для схемы S (без ветвления) оценки (9.20) являются верхними, и рассмотрим задачу минимизации показателя LS на основе метода ветвления (ветвление выходов ее ФЭ, см. раздел 9.6; ветвление входов не учитывается). Для ее решения эффективно следующее разложение ЭСП Жегалкина второй степени через – первой степени, получаемое на основе (9.17). Скобки проставляются с целью определения порядка операций (иногда только для упрощения опускаются):

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

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

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

= Åni=2 xi × F1(i-1) = (9.21)

=(((x1×x2)Å x3 (x1Åx2))Å x4×((x1Åx2)Åx3)) Å …

… Å xn-1×(x1Å…Åxn-2) Åxn×((x1Å…Åxn-2) Åxn-1) = F,

где F искомая суперпозиционная формула. Первое, начальное равенство (9.21) представляет собой преобразование ФУ (9.17), повторение таких преобразований приводит к полному разложению ЭСП Жегалкина F2(n) в ряд по линейным функциям (с возрастанием числа переменных) и получению суперпозиционной формулы F.

Замечание 9.1. В правой части (9.17) неявно записана возможность ветвления для класса схем из ФЭ, в последнем равенстве (9.21) она присутствует, можно сказать, очевидно (сумма в скобках умножается на переменную и следом суммируется с ней же). В соответствии с этим ветвление применяется по-разному: оно выполняется и подсчитывается при лексической обработке формул в момент работы программы синтеза и не учитывается в получаемых ниже оценках; выбираются ФУ в таком виде, что по нему однозначно строится схема для одной итерации и применяется ветвление. Во втором случае оптимизация может быть возможной за счет преобразования ФУ и ветвления и это, обязательно, при наличии определенных свойств булевой функции.

На основе ФУ (9.17) и разложения (9.21) (последняя формула) получаем ФУПК

LS(F2(n), G3) = LS(F2(n-1), G3) + LS(F1(n-1), G3) +2, LS(F2(3), G3) = 4. (9.22)

ЭСП Жегалкина F1(n-1) участвует в построении формулы F дважды, но в схеме S за счет ветвления показатель LS уменьшается. Поэтому второе слагаемое в (9.22) для каждой итерации, кроме последней, то есть для n = 3,4,5, .., n-1, увеличивает значение LS на единицу (один ФЭ, который участвует в ветвлении), а ФУПК (9.22) принимает вид

LS(F2(n), G3) = LS(F2(n-1), G3) +3, LS(F2(3), G3) = 5. (9.23)

Итак, для (9.23) разностное уравнение с начальным условием есть

un – un-1=3, u3=5 . (9.24)

Решение уравнения (9.24) имеет вид

un = 3n – 4, n ³3. (9.25)

Возвращаемся к исходному показателю, учитывая, что последняя итерация неполная (соответственно уменьшаем оценку (9.25) на единицу),

LS(F2(n), G3) = 3n – 5, n ³3. (9.26)

Таким образом, за счет использования ветвления на выходе ФЭ порядок многочлена (9.20), оценки показателя LS, уменьшен на единицу. Докажем минимальность оценки (9.26) методом математической индукции.

При реализации функции F2(3) схемой из ФЭ получение F1(3) не требуется, но для больших значений n, n ³4, обязательно, см. рис.9.1).

F2(3)

Å

F1(3)

&

Å

F1(2)

&

Å

x1

x2

x3

Рис. 9.1. Начальный фрагмент схемы, реализующей ЭСП