How to reduce algebraic degree of Boolean Functions?

**stylenerd** · April 3rd 2009, 04:07 AM

Hi everybody,

I would much appreciate if anyone could assist me with the following problem:

Given:
consider a 4-bit input vector
$x=(a,b,c,d)$ , with $a,b,c,d \in GF(2)$ .

Now consider a function
$S(x) = (S_3(x),S_2(x),S_1(x),S_0(x))$ , with $S:GF(2)^4 \rightarrow GF(2)^4$ and $S_3,S_2,S_1,S_0:GF(2)^4 \rightarrow GF(2)$ ,
i.e. the component functions $S_3,S_2,S_1,S_0$ are Boolean functions of algebraic degree $\leq 3$ .

Now consider two functions $Z,Y: GF(2)^4 \rightarrow GF(2)^4$ that have the following properties:
$Y(x)=(e(x),f(x),g(x),h(x))=y$
$Z(y)=(i(y),j(y),k(y),l(y))=z$
with the component functions
$e,f,g,h,i,j,k,l:GF(2)^4 \rightarrow GF(2)$ also being Boolean functions but only with an algebraic degree $\leq 2$ .
$y,z \in GF(2)^4$ denote the two 4-bit output vectors of $Y$ and $Z$ .

Wanted:
I am looking for Boolean functions $e,f,g,h,i,j,k,l$ with algebraic degree $\leq 2$ , such that
$S(x) = Z(y) = Z(Y(x))$ holds.

I have already looked at Matlab, but it seems that it does not supports Boolean algebra

Does anyone has any idea how to approach this problem?

Thanks!

Thread: How to reduce algebraic degree of Boolean Functions?

LinkBack

Thread Tools

Display

How to reduce algebraic degree of Boolean Functions?

Similar Math Help Forum Discussions

Algebraic Topology-The Brouwer Degree

Boolean Functions

b algebraic of what degree?

Solving Polynomial Functions With a Degree of 4

Boolean function of Degree n

Search Tags