Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Coding and GF(2)

  1. Nov 26, 2007 #1

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    This came up in my logic course.

    The professor writes that in GF(2), the polynomials [tex]3xy^5[/tex] and [tex]\frac{1}{2}x^2y[/tex] respectively can be reduced to [tex]3xy[/tex] and [tex]xy[/tex].

    I understand that [tex]y^5=(y^2)(y^2)y=(1)(1)y=y[/tex], but also in GF(2), for any x, we have x+x=0. So it seems to me that [tex]3xy^5[/tex] can be further reduced to just [tex]xy[/tex] because we have [tex]3xy=xy+xy+xy=0+xy=xy[/tex].

    For the other, I am clueless. Sure, [tex]x^2y=xy[/tex] because in GF(2), for any x, we have x²=x. But what happened to the 1/2? Worse, what is 1/2? It's the inverse of 2. And 2 is 1+1. But 1+1=0, and 0 has no inverse in a field.

    What's going on here?
     
  2. jcsd
  3. Nov 26, 2007 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    First off, just to make sure it's clear, we're talking about polynomial functions, not polynomials. The distinction is subtle, yet vital.

    Secondly, [itex]x^2 \not\equiv 1[/itex]; I'm not sure where you got that idea. The right fact is [itex]x^2 \equiv x[/itex].

    Thirdly, 1/2 doesn't make any sense in GF(2), because as you say, it's equivalent to 1/0.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Coding and GF(2)
  1. Coding Theory (Replies: 4)

  2. Huffman code? (Replies: 4)

Loading...