Polynomial Codes and some lore about Polynomials

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 find this remainder 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 individual bits ( 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, can correct the
message to determine the sent message, 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 and your task is to create the next column. If the top bit is 0
you shift the current column upward by 1 into the next column; if the top bit is 1 you add
the code column except for its top entry to the current column and shift up by 1 to create
the next column. That is what long division does (looked at sideways)

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, when you divide the encoded
message mp by the encoding polynomial p:

= message
last entry is x2 term in remainder
last entry is x term in remainder
last entry is constant term of remainder

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 message part of the received word r(x) by
division as done here. I like the remainder table addition method for computing
remainders better than the long division 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 power 2k-1 is 1 to subtract 2k-1 from
that sum).

For example, with our old remainder table:

Power binary number

we define the product of 110 and 111, which are the third and fifth powers of x, to be x tp
the three plus five, or 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 because it makes it impossible to find
inverses for such 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 tells us that c is uniquely determined in a field
from a and b so long as a is not 0.

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.

And we are done! 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 to p(x)=0 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

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 which obeys the condition

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

and so on, to correct more errors.

In the next chapter we address the two questions that arise here.

How do we find polynomials and and 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.

Prev Next