Учебное пособие 800647

Рис. 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