[Math] Polynomial representation of binary

binarypolynomials

It is well known that we can represent binary using polynomial. For example, $11$ can be represented as $x+1$. So when we compute $11\times11$, we should obtain $1001$, which is equal to $9$ in decimal. But if I use polynomial representation to compute, I obtain $(x+1)(x+1)=x^2+1$, which is $101$ in binary. Clearly it is not $9$ in decimal. Can anyone explain to me where I got wrong.

Remark: Another question: If we use different irreducible polynomial to compute the multiplication table of a Galois Field, say $GF(2^4)$, we will get different multiplication table for sure. I know the tables are isomorphic under with respect to multiplication. But would it affect computation if I use different irrducible polynomial in computer?

Best Answer

Is $9+1=0$ in decimal? No, but modulo 10 it does.

That is where you have a problem here is that you aren't carrying over the term in the polynomial as if you treat the $2x$ as making another $x^2$ term, so you then have $2x^2$ for a moment, this then generates an $x^3$ term which would be the representation you seek. The question is whether $2=10$ or does $2=0$ in your binary representation?

Consider the simple example of $1 + 1$. Does this equal $x$ in your polynomial representation or $0$? I'd look at this as how do you handle numerical overflow?

If you take $11 * 11 = 121$ and then apply modulo 2 on each digit, you would get 101 which is what you have. The lack of carrying is what you have as a problem here, IMO.

To take this one step further. Consider if you could evaluate "121" using powers of 2 for each digit: $4+ 2*2 +1 = 9$. However, if you take out the middle term, this will leave you with the troubled answer you have. If the polynomial representation is to have the same positional notation then some things may have to be redefined, I believe.

Related Solutions

[Math] Binary long division for polynomials in CRC computation

the vonbrand answer is slightly off. This is the correct operations in GF(2) -

        11111001
    ------------
1101(10011010000
     1101
     ----
      1001
      1101
      ----
       1000
       1101
       ----
        1011
        1101
        ----
         1100
         1101
         ----
            1000
            1101
            ----
             101

In GF(2) X^10+X^7+X^6+X^4 MOD (X^3+X^2+1) = X^2+1

Therefor your text book's answer is correct.

[Math] What makes a floating point number finite

As you pointed out, irrationals never have a terminating representation. So let's restrict our attention to rationals.

I believe that a rational number $p/q$ (in lowest terms) is representable as a terminating floating point expression in base $b$ if and only if each prime factor of $q$ is a divisor of $b$.

This is because if you write the fractional part of a number as $x=0.a_1a_2a_3\ldots$, then it terminates if there is integral $n$ with $x=0.a_1a_2a_3\ldots a_n$ in base $b$. That's the same as saying $b^n x=m\in \mathbb{Z}$, so you can write $$x=\frac{m}{b^n}$$ Supposing for simplicity that the original number is between $0$ and $1$ (so you only have to deal with the fractional part--that's okay because adding integers doesn't affect the part past the radix point), this means you can write the number as a fraction whose denominator is a power of $b$ (this form will probably not be in lowest terms).

That's another way to say it--there is a terminating base $b$ floating point representation of $x$ if and only if $x=m/b^n$ for some integers $m$ and $n$.

Best Answer

Related Solutions

[Math] Binary long division for polynomials in CRC computation

[Math] What makes a floating point number finite

Related Question