The Hamming code was (equivalent to) a cyclic linear code. That it is cyclic means that if b6b5b4b3b2b1b0 was a codeword, then so was b5b4b3b2b1b0b6. In terms of polynomials, this says that if b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 is a code-polynomial then so is b5x6+b4x5+b3x4+b2x3+b1x2+b0x+b6. This corresponds to just multiplying the polynomial by x since (b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0)x = b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x = b5x6+b4x5+b3x4+b2x3+b1x2+b0x+b6 since x7 = 1 (mod x7+1). So saying a code is cyclic is the same as saying that for every code-polynomial p(x), xp(x) is also a code-polynomial.
That the code was linear means that if b6b5b4b3b2b1b0 and c6c5c4c3c2c1c0 are both codewords, and ai = bi + ci for i = 0,1,...,6, then a6a5a4a3a2a1a0 is also a codeword. In terms of polynomials, this means that if b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 and c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0 are both code-polynomials, then a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0 is a code-polynomial where ai = bi + ci for i = 0,1,...,6. This just means that if p(x) and q(x) are code-polynomials, then so is p(x) + q(x).
Now consider a code that is both cyclic and linear, like the Hamming code. In this case if p(x) is a code-polynomial, then so is xp(x), and hence also x2p(x), x3p(x), and so on. Since the code is also linear, we can add these code-polynomials to conclude x2p(x) + p(x) = (x2+1)p(x) is also a code-polynomial. In fact, if p(x) is a code-polynomial, then a(x)p(x) is a code-polynomial for any polynomial a(x) (not necessarily a code-polynomial). So the collection of all code-polynomials of any linear cyclic code of length n is a set I of elements of Z2[x]/(xn + 1) such that if p(x) Î I, then a(x)p(x) Î I for every a(x) and if p(x),q(x) Î I, then p(x) + q(x) Î I. Such a set I is called an ideal of the ring Z2[x]/(xn + 1) and plays an important role in the theory of rings. We will now look at how to find such ideals, and hence how to find linear cyclic codes.
Suppose I is an ideal in Z2[x]/(xn + 1), i.e. I is a set of code-polynomials of a linear cyclic code. Let g(x) be the non-zero polynomial of smallest degree in I. We then have the following.
Theorem: Every element of I is of the form a(x)g(x) for some polynomial a(x).
Proof: Let p(x) Î I, then we can write p(x) = q(x)g(x) + r(x) for some polynomials q(x) and r(x) with deg(r(x)) < deg(g(x)). Moving q(x)g(x) to the other side of the equation (and remembering that in Z2 addition and subtraction are the same) we get r(x) = p(x) +q(x)g(x). But since g(x) Î I, so is q(x)g(x) and since p(x) Î I as well, so is p(x) + q(x)g(x), hence r(x) Î I. But deg(r(x)) < deg(g(x)) and g(x) was selected to be the non-zero polynomial in I of smallest degree. So r(x) must be zero, and p(x) = q(x)g(x).
Theorem: g(x) divides xn + 1.
Proof: We can write xn+1 = q(x)g(x) + r(x) for some polynomials q(x) and r(x) with deg(r(x)) < deg(g(x)). As in the previous proof, we can rewrite this as r(x) = xn+1 + q(x)g(x). But now r(x) = q(x)g(x) (mod xn+1), so r(x) Î I. But as before, g(x) was selected to be the non-zero polynomial of I of smallest degree, so since deg(r(x)) < deg(g(x)), we must have r(x) = 0 and q(x)g(x) = xn + 1.
This now tells us how to build a linear cyclic code. Fix a length n, say n = 17. Then we want to work with polynomials in Z2[x]/(x17 + 1). Next pick a generator g(x) that divides x17 + 1, which is easier if you first factor x17 + 1 = (1+x) (1+x+x2+x4+x6+x7+x8) (1+x3+x4+x5+x8). Say we pick g(x) = 1+x3+x4+x5+x8. This generator has degree 8, so we will work with 9 = 17 - 8 data bits. Put the nine data bits into polynomial form d(x) = d8x8 + ... + d0. Encode the data-polynomial into a code-polynomial by computing d(x)g(x). If our data-polynomial is x8+x5+x2+1 (which represents the data bits 100100101), then we compute d(x)g(x) = x16+x12+x11+x9+x8+x7+x6+x5+x4+x3+x2+1 (which represents the codeword 10001101111111101). We now transmit the codeword. When we receive a word, we convert it back to polynomial form to get w(x). Next we divide w(x) divide by g(x) to get w(x) = q(x)g(x) + r(x). If no errors have occurred, then r(x) = 0 and q(x)=d(x) and we have recovered the original data bits. Now suppose an error occurs and we receive the word 10011101111111101. In this case we have w(x) = x16+x13+x12+x11+x9+x8+x7+x6+x5+x4+x3+x2+1 = (x8+x)( 1+x3+x4+x5+x8) + (x7+x3+x2+x+1). The remainder is x7+x3+x2+x+1 rather than 0, which tells us that an error has been made. To fix the error, we assume first that only a single error has been made. If an error is made in the jth position, then we will receive w(x) = d(x)g(x) + xj. So w(x) = xj (mod g(x)) and all we have to do is find j so xj = x7+x3+x2+x+1 (mod g(x)). There are several shortcuts you can take here, but the most straightforward approach is just to compute all the remainders of xj (mod 1+x3+x4+x5+x8). The first few are very quick ( x0 = 1 (mod g(x)), x1 = x (mod g(x)), ... x7 = x7 (mod g(x)) ) and then things get a little more complicated ( x8 = x5+x4+x3+1 (mod g(x)) ) until we eventually find x13 = x7+x3+x2+x+1, so the error occurred in the 13th bit. We correct this bit to get 10001101111111101, which we then decode to find the original data bits 100100101.
We now have a general procedure for building linear cyclic codes. But we haven’t proved that the code we’ve built will actually be able to correct any single error (and there is one more condition we will need to add to the mix before that will be true). We haven’t started looking at how we could correct more than one error at a time. We haven’t worried about finding the most efficient coding scheme. All of these questions will lead us deeper into the study of polynomial rings.