10. 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. This allows us a natural way to define multiplication and division for them. Given a sequence, say 1011, we can make it into a polynomial by converting each bit aj into aj xj-1 and adding the results, For the given sequence we get 1 + x2 + x3 . 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+x2 by 1+x2+x3 which using the distributive law comes to 1 + x +2x2+ 2x3 + 2x4 + x5 which we take to be 1 + x + x5. We will describe encoding by use of an encoding polynomial p(x) and our rule for encoding will be cm(x) = p(x) m(x). Now, if our rule for encoding is multiplication, what is our rule for decoding? How do you undo multiplication? Division! We want codes that will correct one error. What does a single error look like in a polynomial code? It looks like a monomial, xt. And when we undo our multiplication by dividing by p(x), we will recognize this error by looking at the remainder of xt divided by p(x). We will explain this in much more detail later, but first, we need to know some more properties of polynomials. 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 = 01*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. (A field is a set of entities that can be added, subtracted, multiplied, and divided while obeying the same rules as ordinary numbers obey. Examples are the real numbers, the rational numbers, the complex numbers, and 0 and 1 subject to the rules for multiplication and addition just stated.) Here is a polynomial of degree five: 1 + x2 + x5. 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, say p(x), by another, say q(x), you can get both a quotient polynomial (whose degree will be the degree of p minus that of q) and perhaps a remainder (whose degree wil be strictly less than that of q). 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*102 + 4*10 + 3, with 10 here replacing the variable x.) The rules you learned as a child for dividing numbers having several digits are exactly the rules to be used for dividing polynomials, except here 2=0 holds and there is no carrying. 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 non-zero coefficient of our polynomials is 1. We give an illustration of division of polynomials. Suppose we want to divide x8 by 1 + x2 + x5. The latter goes x3 times into the former, with a remainder of x5 + x3. It goes once into this remainder with x3 + x2 + 1 left over. The resultant quotient is therefore x3 + 1 with remainder x3 + x2 + 1. A polynomial is said to be prime if it cannot be factored into polynomials of lower degree. The polynomial of degree five above happens to be prime. On the other hand the polynomial (1 + x2 + x4) is not prime, being (1 + x + x2)2. We will now look at polynomials defined over our field GF(2) of low degree (there aren't many) and identify which are primes. A monomial corresponds to a bit stream of Hamming weight 1. We can immediately see that x is the only monomial that is prime; the rest have x 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. And 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) . We conclude that r=r(1) = 0, and this means (1+x) divides any polynomial with an even number of terms without a remainder. Any polynomial without a 1 term is divisible by x. Further, Any polynomial p(x) whose terms all have even degree is the square of the polynomial whose terms have degree half of the terms of p(x), so p(x) 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. The resulting terms of a square are then olyn the squares of the terms in the original polynomial. 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 +x2 + x3 and the reverse one is 1+x+x3. 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 primality 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 …