10. Polynomial Codes and some lore about Polynomials
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 aj into ajxj-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 interpret 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).
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 + 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 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*102 + 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 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 5 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 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.
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 +x2 + x3 and the reverse one is 1+x+x2.
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 x2 and an odd number of terms is 1 + x + x2, 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 x3 as terms are 1 + x + x3 and 1+ x2 + x3 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 + x4, 1 + x3 + x4, which are reverses of one another and 1+x+x2+x3+x4. 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+x2) is 1+x2+x4)
By similar reasoning the candidates for primes of degree 5 are 1+ x+ x5, 1+x2 + x5, all terms except x, all terms except x2 and the reverses of these 4 polynomials
Of these (1+x+x2)(1+x+x3) 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 x8, which form 28 pairs of a polynomial and its reverse, and 8 symmetric polynomials. Of these about half are primes.
10.3 Which Polynomials Make Good Codes?
The polynomials we want are those that are not only prime, but primitive as well. A primitive polynomial is one such that every possible remainder is a remainder of a power of x.
Consider the simplest non-trivial example, which is the polynomial 1+x+x3.
What are possible remainders?
Because our polynomial has degree 3, a remainder is a polynomial of the form a+bx+cx2; that is, a polynomial of degree one less than that of our polynomial, such that a b and c are each chosen from (0,1), and not all are 0. (If xk were to have 0 remainder that means our polynomial is a factor of a monomial so it would have to be a monomial, and that is too silly for us to consider)
If our polynomial has degree k, the number of such possible remainders is 2k-1, which for k=3 is 7. The possible remainders are 1,x,x2, 1+x, 1+x2, 1+x+x2. and x+x2.
It is slightly more convenient to represent these remainders as 3 (or more generally k) component vectors, in which form we would write them as 100, 010, 001, 110, 101, 111, and 011.
Sometimes, when you want to recognize them easily you can interpret them as numbers. The way I like to do it is perhaps not the best but it works. I treat them as binary numbers read backwards; they then read 1,2,4,3,5,7, and 6 in the order given.
Our polynomial will be primitive if every one of these remainders is the remainder of some power of x. We can test for this by writing out the remainders of powers in ascending order. We know that x0 =1 has remainder 1.
We will be able to write out the remainders of all powers if we give a rule for finding the remainder of xj+1 given the remainder of xj.
We will be able to apply this rule on a spreadsheet by entering the rule on one row, and then copying it down, so we will be able to investigate whether a polynomial is primitive or not very quickly on a spreadsheet.
So what is the rule for finding the remainder of xj+1 from that for xj?
Suppose we have Remainder of xj = rem(xj) = a +bx + cx2 …sxk-2 +txk-1.
We get xj+1 from xj by multiplying it by x. We know that xj = p(x)q(x) + rem(xj) for some q(x)..
We therefore have xj+1 = p(x) [xq(x)] + xrem(xj), the first term of which has no remainder so we have rem(xj+1) = rem(xrem(xj)).
If the coefficient, t, of xk-1, is 0, the effect of multiplying rem(xj) by x is to increase each power by 1, so that we would have rem(xj+1) = ax + bx2 + cx3 … if t=0.
If instead t=1, the last term in rem(xj), when multiplied by x becomes xk whose remainder is (p(x)-xk).
We conclude, that the general form for the remainder of xj+1 here is
rem(xj+1) = ax +bx2 + cx3 + … sxk-1 +t(p(x)-1).
Suppose we consider the polynomial p given by p(x) = x3 + x + 1. Its remainder has three coefficients and let us denote them as a b and c as above.
The rule for going from xj to xj+1 in is then (a,b,c) becomes (c, a+c, b). The a and b terms move over 1 place to the right and c goes to the 1 + x places.
The remainders of powers, according to this rule are
Power 1 x x2 binary number
0 1 0 0 1
1 0 1 0 2
2 0 0 1 4
3 1 1 0 3
4 0 1 1 6
5 1 1 1 7
6 1 0 1 5
7 1 0 0 1
We call this a remainder table for the polynomial p(x).
You will notice that every remainder appears on this list, which means that the first time 1 appears as a remainder for the second time is at the 7th power, more generally for a primitive power the remainder of 1 first happens at the (2k-1)st power. This is the behavior of a primitive polynomial.
Notice that the matrix appearing in the middle of the chart up to the 7th row which is the power 6 row here is essentially a Z type matrix with an identity matrix on top. Thus iif we start at the power 3 row and take 7 rows in order starting there, we get our old friend, the message destroyer, D.
How can we test a polynomial for primitivity?
We can set up a spreadsheet to generate the remainders of powers, and locate the first power for which the binary number is 1. If that power is 2k -1 we have a primitive polynomial, and otherwise not.
Once you have set up a test spreadsheet this way, you can change the polynomial to be tested by changing the line on which you enter its succession rule, and copy it down to apply it everywhere. This involves modifying at most k-1 entries and copying.
(the a entry is always t so it never changes.)
You can test polynomials for primitivity without a spreadsheet by using tricks. Thus the remainder of x2j is the square of the remainder of xj. If you only write the remainders of the even powers from k to 2k-2, you can compute all the remainders of powers of the form 2j from these, and if you find that the remainder of the 2k th power is not x, you know that the polynomial is not primitive. It can happen that the remainder of 2k is x and the code is not primitive, if the remainder of some lower power is also x. You can check this by checking whether the remainders powers that are factors of 2k-1 are 1. If not the polynomial is primitive.
In our example, we have rem(x4) = x+x2
Squaring we get rem(x8) = rem (x2 + x4) = x, and our code is a candidate for primitivity. Since 2k – 1 is a prime, this implies that the polynomial is primitive.
Why is primitivity important to us?
Our plan for decoding is to divide the received message, r(x), by the encoding polynomial, p(x), and examine its remainder, rem(r(x)). Since the encoded message, m(x)p(x), has no remainder, this will be our message killer. The remainder comes entirely from errors.
If the error was in one bit only, suppose that bit corresponds to the monomial xe.
` We can find the error location, (called e here,) by finding the power of x that has remainder rem(r(x)), something that can be read off from the remainder table.
We can do this, so long as no two rows of the remainder table are the same, which means that no two powers have the same remainder.
A primitive polynomial will have the first repetition in the remainder table occur at the highest possible power for its degree. Repetition is inevitable if every non-zero remainder has appeared already, and for a primitive polynomial all non-zero remainders do appear in its remainder table before any repetition.
Notice that once there is a repetition in the remainder table, it cycles. The remainder of the next power depends only on the remainder of the present one. Therefore, if the remainder of xa is the same as that of xb, this will be true of xa+s and xb+s for all s.
10.4 Decoding a Single Error Correcting Code Generated by a Primitive Polynomial
As outlined just above, to decode we first find the remainder of our received message, r(x) upon dividing by the primitive polynomial p(x).
The obvious way to do this is to divide and look at the remainder, as we have said. But there is an easier way which is based upon the fact that the remainder of a sum of polynomials is the sum of their remainders:
rem(a(x) + b(x)) = rem(a(x)) + rem(b(x)).
This means we can find the remainder of r(x) by summing up the remainders of the 1's (called monomials) in it. This can be achieved very easily with a spreadsheet from the remainder table.
(You construct a second table whose rows are the entries of the remainder table each multiplied by the bit of r corresponding to that row. You then sum these rows mod 2, compute the binary number corresponding to that sum, and identify the row of the remainder table with that binary number. Switching that bit will produce the sent message, m(x)p(x).
Once you have found the remainder of the error and located it, you must then divide the sent message m(x)p(x) by p(x) to find m(x). This can also be accomplished on a spreadsheet, without a huge amount of effort.
To do so, write the message to be divided from right to left as a column, (say it is 0111001), and then write the code polynomial (say 1101) similarly from right to left as a column, to its left next to it. At each stage there are two possibilities: either the top bit in the previous column is 1 or 0. If it is 0 you shift the column upward by 1 into the next column; if it is 1 you add the code column except for its top entry to it , and shift the sum you have obtained up by one. That is what long division does.
Shifting the column over corresponds to looking at the next lower power. Adding the code polynomial except for its top entry corresponds to replacing the highest power in the column by the corresponding lower powers of the code polynomial, and entering the fact that you have done so in the next column.
Here is what you get for the example given
p mp 1 0 1 0 = message
1 1 0 1 0 0 last entry is x2 term in remainder
0 0 1 0 0 0 last entry is x term in remainder
1 0 0 1 0 0 last entry is constant term of remainder
1 1 1 1 0
1 1 0
What appears in the last column here is the remainder with the most significant bit at the top. Thus if the top bit were a, the next bit b, and the bottom one c, this would correspond to the remainder cba in our previous notation, or c + bx + ax2, if our code was defined by the polynomial 1 +x +x3.
Notice that you can get rid of the received word r(x) by division as done here. I like the remainder table addition method because the table has other uses.
So far, we have introduced multiplication of polynomials as a way to code, and seen a way to find and describe Hamming codes with k check bits using one polynomial of degree k, instead of filling in a 2k-k-1 by k matrix of check bits.
The method of finding errors we have described here, by finding the remainder of r(x) and discovering which power has that remainder, seems quite different from the method used for general matrix codes. That consisted of matrix multiplying the remainder r vector by the message killing D matrix and seeing what row of D the answer agreed with.
If we find the remainder by long division, the methods of error location seem quite different.
However if you compute the remainder by adding up the remainders of the powers in r(x) you are actually matrix multiplying the r(x) row vector by the remainder table matrix, and comparing the result with the rows of the remainder table matrix. Since the remainder table matrix when multiplied on the left by any code word will give the 0 vector, the procedure from this point of view is identical to the previous one. The remainder table provides the message killing D matrix for the code.
The code generated by a polynomial p can be considered a matrix code, in which the first row contains the encoding polynomial written lowest power first followed by a string of 0's, and successive rows have that polynomial shifted by 1 to the right from their immediate predecessors; in the final row the last polynomial bit reaches the last column.
The remainders we encounter when dividing by a primitive polynomial can be added in the usual way. But if we have our remainder table, we can also multiply them.
Each non-zero remainder is remainder of a power of x, which power can be determined from the remainder table. We define the product of two remainders to be the remainder corresponding to the power that is the sum of their powers. (when this sum exceeds 2k-1 we can use the fact that x raised to that power is 1 to subtract 2k-1 from that sum).
For example, with our old remainder table:
Power 1 x x2 binary number
0 1 0 0 1
1 0 1 0 2
2 0 0 1 4
3 1 1 0 3
4 0 1 1 6
5 1 1 1 7
6 1 0 1 5
we define the product of 110 and 111, which are the third and fifth powers of x, to be x8, which is x or 010.
The addition and multiplication defined here for a primitive polynomial satisfy all the standard laws that addition and multiplications of numbers obey; the 0 polynomial plays the role of 0, and the polynomial 1 plays the role of 1. Obviously the product of two powers is another power and that is never 0, and the sum of two remainders is another remainder.
Such remainders therefore form what mathematicians call a field, which implies that they can be considered as number systems, like the real numbers or the rational numbers or the complex numbers or GF(2).
This is not true for remainders upon dividing by a factorable polynomial, like p(x)q(x) with each factor of degree at least 1. The problem is that the remainder of the product of p(x) by q(x) is the 0 polynomial. This means that two non-zero remainders can have product 0. This is unacceptable for numbers.
A very important fact about real and complex numbers, which we want all number systems to preserve is: (It is a part of the fundamental theorem of algebra.)
A polynomial equation of degree k can have at most k solutions.
This statement is true if the coefficients of the polynomial are elements of a field and generally false otherwise.
This statement will be important to us so we now prove it.
Suppose we have a polynomial equation of degree k with coefficients in a field.
If k is 1 the equation takes the form ax-b =0 for non-zero a. If c is a solution we must have ac=b which implies c = b/a, which makes c a unique element of the field.
We suppose now that the statement (that an equation of given degree d has at most d solutions) is true for all polynomials of degree k-1, and prove that it is true for any p(x) of degree k.
Suppose c is a solution to the equation p(x)=0. Then (x-c) must divide p without a remainder. Otherwise we would have p(x) = (x-c)q(x) + r and p(c) = r and not p(c)=0.
This means the we can write p(x) as (x-c) q(x), where q(x) has degree k-1 and q has at most k-1 solutions by our induction hypothesis..
Any solution to p(x) =0 therefore obeys (x-c)q(x)=0.
x-c has only one solution and q(x), being of degree k-1, has at most k-1 of them by the induction hypothesis.
Since no two non zero field elements have product 0, the only solutions occur where one or another of the factors of p is 0.
So p(x)=0 can have at most k solutions, as we set out to prove.
Now we ask: what can we possibly do to correct more errors in a polynomial code?
Using a primitive polynomial, p(x) as encoding polynomial works splendidly to correct one error, and we certainly want to maintain this power. To correct two errors we will use a polynomial that is the product of a primitive polynomial and a second polynomial which we choose to provide the additional information that we need to locate two errors.
What second polynomial do we choose here?
We will choose a polynomial p3(x) which obeys the condition
rem(p3(x3)) = 0
where we take the remainder on dividing by our primitive polynomial p as before.
And it will turn out that we can correct 3 errors by having a factor, p5 in the encoding polynomial that obeys
rem(p5(x5)) = 0,
and so on, to correct more errors.
In the next chapter we address the two questions that arise here.
How do we find polynomials p3 and p5 and p7 and so on?
How can we locate and correct two or more errors if our encoding polynomial has such factors in it? Which will answer the question: Why do we want such factors?
Codes of the form outlined here are called BCH codes, after the three people who discovered them: Bose, Ray-Chaudhuri, and Hocquenam (do not count on the accuracy of my spelling.)
Exercises:1. Find all primitive polynomials of degree 6 (over the two element field GF(2) defined by 2=0.)
2. Pick a primitive polynomial of degree 5. Construct a spreadsheet encoder for it, that takes any binary message of length 26 and converts it into a coded message using that polynomial as encoding polynomial.
3. Construct a spreadsheet single error corrector for it, that starting with any received message of length 31 takes its matrix product with the remainder table, locates the error and corrects it.
4. Construct a spreadsheet divider that takes the corrected code word and finds the message that was encoded to it.