Учебное пособие 800647
.pdfРис. 2. Алгоритм А4 полиномиального преобразования БФ на основе ЧПНФ
29
ЗАДАНИЕ: записать, аналитический метод получения ПНФ БФ – метод ЧПНФ – в общем виде для БФ, зависящих от n-переменных. Изучить представленный в лабораторной работе алгоритм А4 и оценить возможность его распараллеливания, предложить вариант программно-аппаратных средств, необходимых для его параллельной реализации. Дать оценку параллельной и последовательной реализации алгоритма.
Лабораторная работа №4
АЛГОРИТМ ПОЛИНОМИАЛЬНОГО ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ НА ОСНОВЕ МЕТОДА КОНЕЧНЫХ РАЗНОСТЕЙ
ЦЕЛЬ: изучение метода и алгоритма полиномиального преобразования n – аргументных БФ на основе булева дифференциального исчисления.
Известна [11] математическая модель на основе булева дифференциального исчисления, позволяющая для булевой функции F(x) получать полиномиальное её представление, в котором все искомые коэффициенты сi определяются значениями функции в точке x = c и всеми производными в этой же
точке (x = x1, x2 ,..., xk , с = c1, c2 ,..., ck ). При этом
имеет место полная аналогия с разложением функции в ряд Тейлора в вещественном анализе. В связи с этим, такое представление булевой функции называют разложением функции F(x) в ряд Тейлора в точке c. При этом полиномиальную форму булевой функции находят в соответствии со следующим соотношением (46), использующим операции логического умножения и суммы по модулю 2 ( ):
30
F(x)= F(c) (x |
c ) |
F |
| ... |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
1 |
1 |
x |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x |
|
c |
|
|
) |
F |
| |
... |
(x |
|
c |
)(x |
|
|
c |
|
) |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
k |
|
k |
|
|
xk |
|
1 |
1 |
|
2 |
|
|
|
|
2 |
|
|
|
(46) |
||||
|
|
|
2F |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
| ...... |
(xk 1 |
ck 1 )(xk |
|
|
ck |
) |
|
|
||||||||||||||
|
x1 x2 |
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
2F |
|
|
|
| ... |
(x |
c |
)...(x |
|
c |
|
) |
|
|
|
k F |
|
|
||||||
|
x |
x |
|
|
|
|
x ... x |
|
|
|||||||||||||||||
|
|
k |
1 |
1 |
|
|
k |
|
k |
|
|
k |
||||||||||||||
|
|
|
|
k 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|||||||
Производная первого порядка |
|
|
f |
|
от булевой функции |
|||||||||||||||||||||
|
xi |
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f по переменной xi есть сумма по модулю 2 соответствующих остаточных функций, т.е.:
f |
= f(x ,x |
2 |
,...,x |
,1,....,x |
n |
) |
f(x ,x |
2 |
,...,x |
,0,....,x |
n |
). |
(47) |
||
|
|||||||||||||||
1 |
i 1 |
|
|
1 |
i 1 |
|
|
|
|
|
|||||
xi |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рассмотрим булеву функцию |
F(x,y,z) |
x |
yz |
и полу- |
чим ее полиномиальную форму в соответствии с соотноше-
нием (46).
Полиномиальная форма функции F(x,y,z)будет иметь
следующий вид:
F(x,y,z) x yz (c1 c2c3) |
|
(1 c2c3)(x c1) c1c3(y c2 ) |
|
c1c2(z c3) c3(x c1)(y c2 ) |
(48) |
c2 (x c1)(z c3) c1(y c2 )(z c3)
(x c1)(y c2)(z c3)
Характерной особенностью разложения булевой функции в ряд Тейлора является тот факт [12], что каждая переменная входит в это разложение или всюду с отрицанием, или всюду без него. Имеет ли место тот или иной случай, зависит от точки, в которой произведено разложение. Для сi=0 соот-
31
ветствующая переменная входит без отрицания, а при сi=1 – с отрицанием. При всех сi=0 разложение булевой функции называют полиномом Жегалкина (или положительно поляризованным полиномом Рида–Маллера). При всех других значениях сi получают поляризованные по каким-либо переменным полиномы Рида–Маллера. Ниже представлены полиномы Ри- да–Маллера (включая и полином Жегалкина) на основании (48) при разложении в ряд Тейлора функции
F(x,y,z) x yz .
c=(0,0,0) F 1 x xy xyz |
(49) |
|
c=(0,0,1) |
F 1 x xyz |
(50) |
c=(0,1,0) |
… |
(51) |
c=(0,1,1) |
|
(52) |
c=(1,0,0) |
|
(53) |
c=(1,0,1) |
|
(54) |
c=(1,1,0) |
|
(55) |
c=(1,1,1) |
|
(56) |
Анализ данного метода убеждает, что возможна некоторая строго формализованная процедура, дающая возможность в рамках единого алгоритма получать всё множество поляризованных полиномов, учитывая при этом вектор поляризации. При этом подобный алгоритм должен быть в некотором смысле идентичен взятию производных в определенной точке БФ, например, базирующийся на исчисление конечных разностей.
Конечная разность — математический термин, широко применяющийся в методах вычисления при интерполировании (интерполяция – способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений).
Исчисление конечных разностей изучает функции при дискретном изменении аргументов, в отличие от дифференци-
32
ального и интегрального исчислений, где аргументы изменяются непрерывно.
Пусть функция y f(x) задана в точках xk x0 k h
(h – постоянная, k – целое). Тогда
1yk = fk = f(xk+1 ) f(xk ) – разности первого порядка,
2 y |
k |
= |
2 f |
k |
= f |
k+1 |
|
f |
k |
= f(x |
) f(x |
k+1 |
) f(x |
k+1 |
) f(x |
k |
) |
|
|
|
|
|
|
k+2 |
|
|
|
|
f(xk+2 ) 2f(xk+1 )+ f(xk )
–разности второго порядка,
3 y |
k |
= |
3 f |
k |
= |
|
f |
k+2 |
f |
k 1 |
= f(x |
k+3 |
) 2f(x |
k+2 |
) f(x |
k+1 |
) f(x |
k 2 |
) |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
2 f(xk+1 ) f(xk |
) f(xk+3 ) 3f(xk+2 |
) 3f(xk+1 |
) f(xk ) |
|
|
|
|||||||||||||||||
– разности третьего порядка, |
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
…… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
n y |
k |
= |
|
n f |
k |
= |
n 1 f |
k+1 |
|
n 1 f |
k |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
–разности n-го порядка.
Конечные разности удобно располагать в таблице
(табл. 11).
|
|
|
|
|
|
Таблица 11 |
||
|
|
|
|
|
|
|
|
|
x |
y |
∆y |
∆2y |
∆3y |
… |
|
∆ny |
|
x0 |
y0 |
∆y0 |
∆2y0 |
∆3y0 |
… |
|
|
|
x1 |
y1 |
∆y1 |
∆2y1 |
∆3y1 |
… |
|
|
|
x2 |
y2 |
∆y2 |
∆2y2 |
|
|
|
|
|
x3 |
y3 |
∆y3 |
|
|
|
|
|
|
… |
… |
… |
… |
… |
… |
|
… |
|
|
|
|
|
|
|
|
|
|
xn |
yn |
|
|
|
|
|
|
|
Разность n-го порядка через величины y0, y1… выражается формулой
n yn = yk+n Cn1 yk+n 1 +Cn2 yk+n 2 ...+( 1)n yk
33
где Cn1,Cn2 ,...,( 1)n коэффициенты.
Наряду с разностями вперед ∆yk , употребляются разности назад:
yk = f(xk ) f(xk 1 )
Имеется аналогия исчисления конечных разностей c дифференциальным и интегральным исчислением. Операция отыскания разностей соответствует нахождению производной.
Вычислим конечные разности всех порядков для булевой функции F(x,y,z) x yz и сведем их в табл.12.
|
|
|
|
|
|
|
|
|
|
Таблица 12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
z |
y |
x |
f |
∆1 |
∆2 |
∆3 |
∆4 |
∆5 |
∆6 |
∆7 |
|
0 |
0 |
0 |
f0=1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
f1=0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
|
0 |
1 |
0 |
f2=1 |
0 |
0 |
1 |
0 |
1 |
|
|
|
0 |
1 |
1 |
f3=1 |
0 |
1 |
1 |
1 |
|
|
|
|
1 |
0 |
0 |
f4=1 |
1 |
0 |
0 |
|
|
|
|
|
1 |
0 |
1 |
f5=0 |
1 |
0 |
|
|
|
|
|
|
1 |
1 |
0 |
f6=1 |
1 |
|
|
|
|
|
|
|
1 |
1 |
1 |
f7=0 |
|
|
|
|
|
|
|
|
Каким образом можно интерпретировать полученные конечные разности булевой функции применительно к её полиномиальной нормальной форме общего вида?
Для булевой функции F(x,y,z) x yz , зависящей от n=3 аргументов, полином общего вида запишется в следующей форме:
2n 1 |
|
P(z,y,x) giKiM |
(57) |
i 0
34
где Kiм – монотонная конъюнкция, т.е. логическое произведение только тех логических переменных, которые в i
- ом входном наборе |
равны |
1; gi |
– коэффициенты, |
принимающие значения 0 или 1, и |
обозначающие |
||
вхождение (только при равенстве |
1) соответствующей Kiм в |
полином; конъюнкция K0м всегда принимается равной 1.
Отождествим i-е индексы в соотношении (57) с индексами конечных разностей из табл. 12. При этом и те, и другие индексы будем нумеровать одинаковыми двоичными кодами, которые, в свою очередь, равны значениям наборов аргументов. При таких соглашениях табл. 12 модифицируется в табл. 13.
Таблица 13
|
|
|
|
K1м |
K2м |
|
K3м |
K4м |
|
K5м |
K6м |
K7м |
|
|
z |
y |
x |
f |
001 |
010 |
|
011 |
100 |
|
101 |
110 |
111 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
∆1=g1 |
∆2=g2 |
∆3=g3 |
∆4= g4 |
∆5= g5 |
∆6= g6 |
∆7= g7 |
||||
0 |
0 |
0 |
f0=1 |
1 |
0 |
|
1 |
0 |
|
0 |
0 |
1 |
|
Коэф-ты |
|
|
|
полинома |
|||||||||||
0 |
0 |
1 |
f1=0 |
1 |
1 |
|
1 |
0 |
|
0 |
1 |
|
|
|
0 |
1 |
0 |
f2=1 |
0 |
0 |
|
1 |
0 |
|
1 |
|
|
|
|
0 |
1 |
1 |
f3=1 |
0 |
1 |
|
1 |
1 |
|
|
|
|
|
|
1 |
0 |
0 |
f4=1 |
1 |
0 |
|
0 |
|
|
|
|
|
|
|
1 |
0 |
1 |
f5=0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
f6=1 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
f7=0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Если допустить, |
что |
0 = f0 |
, то на основании (57), |
||||||||
значений |
i = gi |
и значений Kiм |
из табл. 13 получим |
|||||||||||
следующий |
полином |
Жегалкина |
для |
булевой |
функции |
F(x,y,z) x yz :
35
F 1 x xy xyz |
(58) |
Арифметическим операциям сложение и вычитание над одноразрядными двоичными числами соответствует (тождественна) логическая функция суммы по модулю 2 ( ), что видно из табл.14.
Таблица 14
a |
b |
a+ |
a– |
a |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
С учетом данного обстоятельства предлагается следующая дискретная модель полиномиального преобразования булевых функций на основе метода конечных разностей, обеспечивающая определение компонент вектора G (g0,g1,...,gi,...,g2n 1), компоненты которого являются ис-
комыми коэффициентами полинома Жегалкина общего вида:
g0 |
f0 |
; |
(59) |
|
g 1 |
; |
(60) |
||
1 |
|
|
|
|
….. |
i ; |
…. |
||
gi |
|
(61) |
||
g |
n |
|
2n 1 ; |
(62) |
2 |
|
-1 |
|
|
Если в системе уравнений (59)… (62) все ∆i выразить через значения компонент вектора F (f0,f1,...,fi ,...,f2n 1),
то придем к дискретной модели полиномиального преобразования булевой функции на основе метода неопределенных коэффициентов и соответствующим алгоритмам преобразования.
36
Если же остановиться на дискретной модели (59)… (62), то может быть найден иной алгоритм преобразования, для пояснения сущности которого построим табл. 15.
Таблица 15
z |
y |
x |
gi |
f0 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
|
0 |
0 |
0 |
g0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
g1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
g2 |
|
|
0 |
1 |
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
g3 |
|
|
1 |
1 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
g4 |
|
|
|
0 |
0 |
0 |
1 |
|
|
1 |
0 |
1 |
g5 |
|
|
|
0 |
0 |
1 |
|
|
|
1 |
1 |
0 |
g6 |
|
|
|
|
0 |
1 |
|
|
|
1 |
1 |
1 |
g7 |
|
|
|
|
1 |
|
|
|
|
Отметим, что в [13] представлен без какого-либо обос-
нования |
метод |
нахождения |
компонент |
вектора |
G (g0,g1,...,gi,...,g2n |
1) для полинома Жегалкина, |
который |
называют «метод треугольника Паскаля».
Следуя этому методу, получим следующее представление в виде полинома Жегалкина булевой функции
F(x,y,z) x yz :
F 1 x xy xyz |
(63) |
На основании (58) и (63) заключаем, что вариантом реализации дискретной модели метода конечных разностей является вышеописанный словесный алгоритм, который известен как «треугольник Паскаля».
Верхняя и левая стороны треугольника Паскаля являются информативными. Является ли информативной и правая сторона этого треугольника?
37
Ранее отмечалось, что полиномиальное разложение БФ на основе булева дифференциального исчисления, позволяет находить не только полином Жегалкина, но и все возможные поляризованные полиномы Рида–Маллера. Отсюда можно предположить, что правая сторона треугольника Паскаля представляет собой компоненты вектора G* (g0, g1,...,gi ,...,g2n 1), поляризованного по каким-либо
переменным.
Из табл. 15 видно, что правая сторона треугольника Паскаля содержит 5 единичных значений. Выпишем монотонные конъюнкции, соответствующие этим единичным значениям: x, z, xz, yz, xyz. Такой состав монотонных конъюнкций содержит полином (10), но отличие состоит лишь в том, что все переменные в этом полиноме имеют знак инверсии. Такой полином называют поляризованным по всем переменным.
Таким образом, алгоритм полиномиального преобразования БФ на основе метода конечных разностей позволяет за одну реализацию осуществлять преобразование БФ к двум полиномиальным формам: полиному Жегалкина (положительно поляризованный полином Рида–Маллера) и поляризованному по всем переменным полиному Рида– Маллера.
Логично вытекает следующее обобщение этого вывода: при разложении методом конечных разностей БФ, поляризованной по каким-либо переменным, одновременно находятся две полиномиальные нормальные формы, в одной из которых переменные поляризованы так же как и у исходной БФ, а в другой имеют противоположную поляризацию.
Проверим сформулированное обобщение. Применим метод конечных разностей к булевой функции F(x, y, z), поляризованной, например, по переменной z.
38