My course on error correcting codes has now finished. I think most of it went fairly well, but I’m not satisfied with the way I treated linear codes. I think I spent too much time on results requiring only basic linear algebra, and not enough time on the more interesting results that really are part of coding theory—in particular: how to encode and decode with linear codes, and how to construct linear codes with good error correcting properties.
For instance, I spent several lectures defining generator and parity check matrices and using them to show that if is a linear binary code of length , then has dimension if and only if can be defined by a system of independent linear equations (which may be recorded in a parity check matrix). Next year I plan to just state this result and give examples, and not, as this year, to give a matrix based proof; this proof probably did not appeal to the stronger students—who should be shown the elegant proof using bilinear forms and the rank-nullity theorem—while, predictably, the weaker students just got lost.
Anyway, the purpose of this post is to show that it is possible for someone who is familiar with linear algebra and the first isomorphism theorem, but knows only the basic definitions of coding theory, to discover the rather elegant Hamming code of length 7.
Let and let be the row vector of length which has a in position and in all other positions. Suppose that is a one-error correcting linear binary code. If we transmit the codeword and a single error occurs in transmission, so that we receive for some , then since is one-error correcting, must be strictly nearer to (in the Hamming distance) than to any other codeword. It follows that if then , except when and . Since is linear, and its cosets are all mutually disjoint. (Standard array decoding motivates this observation quite nicely.)
How can we design so that it has this property? By the result from linear algebra mentioned above, if has dimension then there is a matrix such that
Now the critical observation is that the cosets and are equal if and only if . This can easily be shown directly; alternatively, it follows at once from first isomorphism theorem for the map . Since is the -th row of , it follows that is one-error correcting if and only the rows of are distinct and non-zero. (The non-zero condition ensures that for any .)
There are binary words of length and cosets of that must distinguish. Hence we must have . The most efficient choice is therefore to take and where , and to take for the -matrix which has all non-zero binary words of length as its rows. Provided that , the resulting code is a -error correcting code of length and dimension .
For example, if then we take
to get the code defined by the parity check equations , . So in this case is the binary repetition code of length .
If then we expect to get a code of dimension . Taking
we get the code
This is the Hamming -code. One advantage of this construction is that it makes clear an easy decoding algorithm: if is received, then decode as where is the -th row of . It is also clear how to generalize the construction to get perfect one-error correcting codes over larger fields.