Try our Free Online Math Solver!

Polynomial Codes and some lore about Polynomials
10.1 Introduction:
We will now introduce more structure for our message words and code words,
and use it to get single error correcting codes that can be described more
easily, as well as
codes that can correct several errors.
We do this by treating our sequences as polynomials and defining
multiplication for them .
Given a sequence, say 1011, we can make it into a polynomial by converting each
bit into and adding the results , For the sequence 1011 we get 1 + x^{2} +
x^{3}.
We multiply our sequences by the usual laws of multiplication , again with the
2=0 rule Thus , in multiplying (111) by (1011). We multiply 1+x+x^{2} by 1+x^{2}+x^{3}
which
using the distributive law comes to 1 + x +2x^{2}+ 2x^{3} + 2x^{4} + x^{5} which we
interpret to be
1 +x+x^{5}.
We will describe encoding by use of an encoding polynomial p(x) and our rule for
encoding will be
Thus the task of finding useful codes is, in this context, the task of finding
useful
polynomials. In order to find them we first look at some properties of
polynomials.
10.2 Binary Polynomials
We will find, that if you want to find efficient single error correcting
polynomial
codes, you can do so by choosing an encoding polynomial that is
"primitive". Primitive
means prime, plus one other property we shall soon
describe. So we will begin by
looking at low degree prime polynomials.
Recall that binary numbers obey these rules for addition:
0 + 0 = 1+1 = 0
1 + 0 = 0+1 = 1
and these for multiplication:
0*0 = 0*1 = 1*0 = 0
1*1 = 1.
A polynomial defined over this "field" (the field is called GF(2)) is no more
than a polynomial whose coefficients are each 0 or 1.
Here is a polynomial of degree 5: 1 + x^{2} + x^{5}.
Polynomials have the wonderful property that you can add and subtract them and
also multiply and divide them using all the standard commutative, distributive
and
associative laws of arithmetic.
When you divide one polynomial by another, you get a quotient polynomial, and
perhaps a remainder. The rules for dividing are the rules for long division.
(actually,
when you write a number as say 543 you are treating it as a sort of
polynomial, namely
5*10^{2} + 4*10 + 3, with 10 instead of a variable, so the rules
for dividing same are the
rules for polynomials, except for carrying, which you
do with numbers and not with
polynomials. (in our case, given 2=0, there is no
carrying to do)
With our polynomials life is much more pleasant than what you encountered in
your youth when you want to do arithmetic since the only possible nonzero
coefficient
of our polynomials is 1,
We give an illustration of division of polynomials.
Suppose we want to divide x^{8} by 1 + x^{2} + x^{5}.
The latter goes x^{3} times into the former, with a remainder of x^{5} + x^{3}. It goes
once into this
remainder with x^{3} + x^{2} + 1 left over. The resultant quotient is
therefore x^{3} + 1 with
remainder x^{3} + x^{2} + 1..
A polynomial is said to be prime if it cannot be factored into polynomials of
lower degree.
The polynomial of degree 5 above happens to be prime. On the other hand the
polynomial (1 + x^{2} + x^{4}) is not prime, being (1 + x + x^{2})^{2}.
We will now look at polynomials of low degree and identify which are primes.
We can immediately see that x is the only monomial that is prime ; the rest have
it
as a factor.
Any polynomial, p(x) with an even number of terms has (1 + x) as a factor.
Why?
Because if you set x = 1 you find p(1)=0, when p has an even number of terms.
When you divide p(x) by (1+x) you get a remainder that must have 0 degree and
so
must be 0 or 1.
But we have p(x)=q(x)(1+x) + r(x) with q(x) the quotient
upon dividing p by (1+x), and
r(x) the remainder.
Evaluating this at x=1 we get 0 = p(1) = q(1)*0 + r(1) .
From which we conclude that r=r(1) = 0, and this means (1+x) divides any
polynomial
with an even number of terms
Any polynomial without a 1 term is divisible by x.
Further,
any polynomial whose terms all have even degree is the square of
the
polynomial whose degrees are all half of its, so it cannot be prime.
This is true because the ugly cross terms which normally occur when you square a
polynomial all have factors of 2 multiplying them so they are all 0 here.
There is one more fact that is useful when examining polynomials.
If we take a sequence like 1011 and make it into a polynomial, we can do so in
two ways.
The way we have chosen is to start from the left, and have successive bits
correspond to
increasing powers .
We could just as well have done the same thing starting from the right.
But this gives us a different polynomial, which we call the "reverse polynomial"
to the
first.
In our example, our polynomial is 1 +x^{2} + x^{3} and the reverse one is 1+x+x^{2}.
Now no important property of our code can depend on whether we started from the
left or
the right in turning our sequences into polynomials.
We conclude from this that the properties of a polynomial and its reverse such
as
primitivity and primeness must be the same for each polynomial and its
reverse.
This conclusion will be justified by what we see very soon: that these
properties have a
direct effect on the error correcting properties of the code a
polynomial generates.
So let us explore the polynomials of low degree and classify them as prime or
composite.
There are two polynomials of degree 1, x and 1+x and both are prime
:
The only polynomial of degree 2 with terms 1 and x^{2} and an odd number of terms
is 1 + x + x^{2}, and therefore it is the only possible prime. It is prime, as you
can see
because it is not a product of any combination of the
degree 1 primes. It is symmetric on
reversal of bits
The only possible primes of degree three with odd number of terms having 1 and
x^{3} as terms are 1 + x + x^{3} and 1+ x^{2} + x^{3} which are reverses of one another. If
they were
not primes they would have to have a factor of degree 1, but they do
not, because they
have an odd number of terms.
Among polynomials of degree 4 the only polynomials with an odd number of
terms
not all squares with a constant term and one of degree 4 are 1 + x + x^{4}, 1 + x^{3}
+ x^{4},
which are reverses of one another and 1+x+x^{2}+x^{3}+x^{4}. which is symmetric. By
the
reasoning used for polynomials of degree 3 in the last paragraph, all of
these are prime.
(The square of (1+x+x^{2}) is 1+x^{2}+x^{4})
By similar reasoning the candidates for primes of degree 5 are 1+ x+ x^{5}, 1+x^{2} +
x^{5}, all terms except x, all terms except x^{2} and the reverses of these 4
polynomials
Of these (1+x+x^{2})(1+x+x^{3}) and its reverse are not prime and the others are
prime.
You could, if you wanted to, continue this investigation to degree 6,…,10 at
least.
For example, for degree 8, by my calculation , there are 64 polynomials with an
odd
number of terms including 1 and x^{8}, which form 28 pairs of a polynomial and
its reverse,
and 8 symmetric polynomials. Of these about half are primes.
Prev  Next 