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
    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:
    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.

    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?

    Last edited by stylenerd; Apr 3rd 2009 at 05: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, 01:00 AM
  2. Boolean Functions
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: Oct 6th 2011, 03:01 AM
  3. b algebraic of what degree?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Oct 26th 2009, 03:31 PM
  4. Replies: 2
    Last Post: Mar 4th 2009, 12:27 PM
  5. Boolean function of Degree n
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Sep 30th 2007, 09:03 AM

Search Tags

/mathhelpforum @mathhelpforum