При n=3 для реализации F2(3) = x1 x2 Å x3 (x1Åx2) используем для двух базисных функций g&(2) и gÅ(2) соответствующие по два ФЭ (рис. 9.1, иллюстрацию можно проводить на основе ФУ), обозначаемые прямым шрифтом g&(2) и gÅ(2), получая LS(F2(3), G3) = 4, т. е. для начальных условий утверждение имеет место.
Предположим, что для n утверждение LS(F2(n), G3) = 3n – 5 истинно.
На основе ФУ (9.17) запишем F2(n+1) =( F2(n) Å( xn+1 × F1(n) )).
Рассмотрим показатель LS(F2(n+1), G3) и преобразуем его следующим образом, применяя (9.23),
LS(F2(n+1), G3) = LS(F2(n), G3) +3 = 3n – 2, (рис. 9.2 и 9.3), что и требовалось вывести,
LS(F2(n), G3)min = 3n – 5. (9.27)
Оценка (9.27) справедлива также в классе монотонных симметрических булевых функций, задаваемых ДНФ, представляемых на основе ФУ типа 1 в базисе G2 = {&, Ú }. Она также получается следующим методом синтеза схем на основе метода структуризации ФУ (см. раздел 9.6):
для ЭСП F2(n), n ³2, в базисе G3 на основе ФУ типа 1 число итераций есть (n–2), причем при реализации начальных условий требуется 5 ФЭ (см. (9.17); рис.9.1); в каждой из первых (n–4) итерациях используется три ФЭ ( см. (9.17); рис.9.2); в последней итерации – два ФЭ (см. (9.17); рис. 9.3). Итого, вычисляя 5 + 3(n – 3) –1, повторяем оценку (9.27).
В отношении глубины заметим, что оценки DepF и DepS – (9.20) получены на основе ФУ (9.17) и ФУПК
DepS(F2(n), G3) = DepS(F2(n-1), G3) + DepS (F1(n-1), G3) +1. (9.28)
При построении схемы S предполагается ветвление выходов ФЭ при реализации ЭСП Жегалкина F1(n-1): один выход идет на образование конъюнкции с переменной xn, другой – на получение F1(n) для следующей итерации. При этом участвующие в этом две операции чередуются, образуя цепочку, как бы параллельную основной цепочке вычислений F2(n), меньшей глубины. Вклад, который вносит второе слагаемое правой части (9.28) в значение глубины за счет ветвления равен единице. Поэтому приходим к разностному уравнению
un – un-1=2, u3=3. (9.29)
Для (9.29) получаем решение ФУПК (9.20), оценки DepF и DepS есть un = 2n-3. Эти оценки улучшаются следующим образом.
Определим глубину ЭСП Жегалкина F2(n) в базисе G3 на основе определения [25] и ФУ (9.17)
DepF(F2(n), G3) = max{ DepF(F2(n-1), G3); 1+DepF(F1(n-1), G3)}+1. (9.30)
Моделируя процесс построения формулы F для n = 4, 5, 6, …, вычислительным методом находится сеточная функция un (таблица 9.1) для DepF(F2(n), G3), откуда она находится аналитически, то есть
DepF(F2(n), G3)= n.
Для формулы F, полученной данным методом, изоморфно строится схема S (без ветвления), которая преобразуется на основе ФУ (9.17) и показатель LS минимизируется за счет ветвления, так как ФУ (9.17) это позволяет. Таким образом,
DepF(F2(n), G3) = DepS(F2(n), G3) = n . (9.31)
Таблица 9.1
n | 4 | 5 | 6 | 7 | 8 | 9 | … |
un | 4 | 5 | 6 | 7 | 8 | 9 | … |
9.4. Сложность ЭСП Жегалкина F3(n) . Заметим, что в работе предлагаются различные методы, способы реализации булевых функций в классах формул и схем из ФЭ и получаемые при этом оценки для соответствующих показателей сложности. Исследуем сложность представления ЭСП Жегалкина F3(n)
F3(n) = x1 x2 x3 Å x1 x2 x4 Å … Å xn-2xn-1 xn , n ³ 3, (9.32)
в базисе G3 разными способами. С целью ознакомления с этой техникой изложим некоторые из них.
Для ЭСП Жегалкина F3(n) (9.32) получим ФУ типа 1
F3(n) = F3(n-1) Å (xn × F2(n-1)), n ³ 4. (9.33)
Точное ФУПК на основе (9.33) для показателя сложности LБ есть
LБ(F3(n), G3) = LБ(F3(n-1), G3) + LБ(F2(n-1), G3) +1 (9.34)
Используя некоторые приближения для правой части (9.34), получим различные оценки показателя LБ:
- начиная с конкретизации оценки (9.2), то есть по формуле (9.32), С-методом (первым способом),
(LБ(F3(n), G3) С-метод)1 =(n3 – 3 n2 + 2n ) / 2; (9.35)
- С-методом (вторым способом) по ФУПК (9.34), подсчитывая суммарную сложность первых двух слагаемых
(LБ(F3(n), G3) С-метод)2= 3 C3n–1 + 2 C2n–1 + 1 = (n3 – 4 n2 + 5n ) / 2 ; (9.36)
- подсчитывая сложность второго слагаемого ФУПК (9.34) на основе (9.20), получаем приближение
LБ(F3(n), G3) = LБ(F3(n-1), G3)+((n–1)2+(n–1)–2) / 2 +1 =
=LБ(F3(n-1), G3)+(n2 –n –2) / 2 +1 = LБ(F3(n-1), G3) + (n2 – n ) / 2 , (9.37)
начальное условие LБ(F3(3), G3) = u3 = 3 .
Заметим, что ФУПК (9.34) есть точное, остальные дают соответствующие приближения - верхнюю оценку показателю LБ.
Таким образом, приходим к разностному уравнению
un – un-1= (n2 – n ) / 2, (9.38)
решение которого можно получить разными методами: численно как сеточную функцию un, представленную в таблице 9.2; аналитически – из общего решения уравнения (сумма общего решения однородного уравнения и частного решения неоднородного уравнения), удовлетворяющего начальному условию, или следующим образом. Составляя для решения un (сеточной функции) конечные разности первого, второго и других порядков (таблица 9.2), устанавливаем тип решения: функция un является многочленом 3-й степени [24].
Таблица 9.2
n | 3 | 4 | 5 | 6 | 7 | 8 | 9 | … |
un | 3 | 9 | 19 | 34 | 55 | 83 | 119 | … |
Dun =un+1 – un | 6 | 10 | 15 | 21 | 28 | 36 | ||
D2un =Dun+1 – Dun | 4 | 5 | 6 | 7 | 8 | |||
D3un | 1 | 1 | 1 | 1 | ||||
D4un | 0 | 0 | 0 |
Поэтому находим не частное решение для правой части, а ищем решение уравнения (9.38), удовлетворяющее начальному условию, в виде многочлена 3-й степени с неопределенными коэффициентами,
un = a0n3 + a1n2 + a2n + a3. (9.39)
Решаем систему линейных уравнений, получаемую из (9.39) (для n = 3, 4, 5, 6) следующим образом, минимизируя вычислительную сложность: из 1-го уравнения вычитаем 2-е, из 2-го вычитаем 3-е, из 3-го вычитаем 4-е, затем выполняется эта же процедура для полученных первых трех уравнений и т. д., то есть
a063 + a162 + a26 + a3 = 34,
a053 + a152 + a25 + a3 = 19,
a043 + a142 + a24 + a3 = 9,
a033 + a132 + a23 + a3 = 3, (9.40)
и, окончательно, находим a0=1/6; a1=0; a2 = –1/6 ; a3=–1. Итак, решение уравнения (9.38) есть un = n3/6 –n/6 – 1. Для показателя LБ получаем оценку
LБ(F3(n), G3) = n3/6 –n/6 – 1. (9.41)
Для показателя LБ при сравнении оценок (9.35), (9.36) и (9.41) устанавливаем (LБ(F3(n), G3) С-метод)1 >(LБ(F3(n), G3) С-метод)2 >LБ(F3(n), G3) при n >4, т. е. следует эффективность метода ФУ (9.37) по сравнению с С-методом.
Теперь получим ФУПК для показателя качества LF, используя ранее найденный результат (9.20) для LF(F2(n), G3)) ,
LF(F3(n), G3) = LF(F3(n-1), G3) + LF(F2(n-1), G3) + 2=
= LF(F3(n-1), G3) +((n–1)2+(n–1)–4) / 2 +2 =LF(F3(n-1), G3) +(n2 – n ) / 2. (9.42)
Так как ФУПК (9.37) и (9.42) структурно совпадают (различие только в обозначении некоторых индексов переменных, то для показателей качества LБ(F3(n), G3) и LF(F3(n), G3) получаем одно разностное уравнение (9.38). Случаи различаются начальными условиями (здесь LF(F3(3),G3)=u3 =2).
Решение (9.38) также ищется в виде (9.39), аналогично предыдущему случаю: получение сеточной функции, конечных определенных разностей и вывод – третья степень многочлена с неопределенными коэффициентами. Решение получаемой системы линейных уравнений для (n = 3, 4, 5, 6) есть a0=1/6; a1=0; a2 = –1/6 ; a3=–2, т. е. un = n3/6 –n/6 – 2. Возвращаемся к показателю
LF(F3(n), G3) = n3/6 –n/6 – 2. (9.43)
При представлении этого полинома Жегалкина схемой S в случае отсутствия ветвления оценка (9.43) для числа подфункций в суперпозиционной формуле F является достижимой верхней оценкой для числа ФЭ в соответствующей схеме S, т. е.
LS(F3(n), G3) = n3/6 –n/6 – 2. (9.44)
Улучшим оценку (9.43) в классе схем с ветвлением. Для минимизации синтеза формул и схем преобразуем ФУ (9.17), представляя его как
F3(n) = F3(n-1) Å( xn×( F2(n-2) Å (xn-1 ×F1(n-2) ))), n ³ 4. (9.45)
Для (9.45) определим ФУПК в классе схем S с ветвлением
LS(F3(n), G3) = LS (F3(n-1), G3) + LS (F2(n-2), G3) +LS (F1(n-2), G3) +4. (9.46)
Для (9.46) находим для второго и третьего слагаемых правой части соответствующие приближения (9.27) и (9.9) и действуем формально, получая
LS(F3(n), G3) = LS (F3(n-1), G3) + LS (F2(n-2), G3) +LS (F1(n-2), G3) +4=
= LS (F3(n-1), G3) + 3(n–2)–5+n–3 +4 = LS (F3(n-1), G3) +4n–10. (9.47)
Для (9.47) разностное уравнение с начальным условием есть
un – un-1=4n–10, u4 = 7. (9.48)
Составляя для решения un (сеточной функции) конечные разности первого, второго и других порядков, устанавливаем тип решения: функция un (таблица 9.3) является многочленом второй степени [27].
Таблица 9.3
n | 4 | 5 | 6 | 7 | 8 | 9 | … |
un | 7 | 17 | 31 | 49 | 71 | 97 | … |
Dun =un+1 – un | 10 | 14 | 18 | 22 | 26 | ||
D2un =Dun+1 – Dun | 4 | 4 | 4 | 4 | |||
D3un | 0 | 0 | 0 | 0 |
Поэтому находим решение уравнения (9.48), удовлетворяющее начальному условию, в виде многочлена второй степени
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
