Results 1 to 1 of 1

Math Help - How to reduce algebraic degree of Boolean Functions?

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    1

    How to reduce algebraic degree of Boolean Functions?

    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!
    Last edited by stylenerd; April 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: January 14th 2012, 12:00 AM
  2. Boolean Functions
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: October 6th 2011, 02:01 AM
  3. b algebraic of what degree?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 26th 2009, 02:31 PM
  4. Replies: 2
    Last Post: March 4th 2009, 11:27 AM
  5. Boolean function of Degree n
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 30th 2007, 08:03 AM

Search Tags


/mathhelpforum @mathhelpforum