Results 1 to 1 of 1

Thread: How to reduce algebraic degree of Boolean Functions?

  1. #1
    Apr 2009

    How to reduce algebraic degree of Boolean Functions?

    Hi everybody,

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

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

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

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

    I am looking for Boolean functions $\displaystyle e,f,g,h,i,j,k,l$ with algebraic degree $\displaystyle \leq 2$, such that
    $\displaystyle 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?

    Last edited by stylenerd; Apr 3rd 2009 at 04:08 AM. Reason: typo in label
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algebraic Topology-The Brouwer Degree
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Jan 14th 2012, 12:00 AM
  2. Boolean Functions
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: Oct 6th 2011, 02:01 AM
  3. b algebraic of what degree?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Oct 26th 2009, 02:31 PM
  4. Replies: 2
    Last Post: Mar 4th 2009, 11:27 AM
  5. Boolean function of Degree n
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Sep 30th 2007, 08:03 AM

Search Tags

/mathhelpforum @mathhelpforum