Digital Revolution (Part III) - Error Correction Codes

4. Codes and geometry

Many tools have been developed to find specific families of error correcting codes. These tools include ideas from sphere packing, group theory, and geometry. To get an appreciation of the discussion that follows, try to construct for yourself the largest number of binary sequences of length 7 than has the property that every pair of the sequences has Hamming distance 3.

As an example of using geometric ideas to construct error correction codes, consider the diagram below, which represents a finite geometry of exactly 7 points and 7 lines with three points on every line. In this geometry two points determine a unique line but every pair of lines has a point in common. Such a geometry is known as a projective geometry.
 

 

It is now possible to construct a matrix of zeros and ones that represent this plane by thinking of the columns of the matrix as representing the points, and the rows of the matrix as representing the lines. For a particular row, the entry in a column is a 1 if that point is on the line which the row represents and a 0 otherwise. For example for L₁, we would get the entries:
 

This is because this line contains the points P₁, P₂, and P₄ and, thus, there are 1's in columns one, two, and four. Continuing in this way for the other 6 lines we get the following 7x7 array of zeros and ones.

 

You can check that the Hamming distance between any pair of these rows treated as a binary string is at least 3. Thus, we can think of these 7 rows as being the code words of a binary error correction code which will correct, as explained above, up to one error per code word. Can one add additional binary strings of length 7 to the strings above and still keep the distance between the strings at least three? The answer is yes. What we can do is create a new string from each string (row of the matrix) above by changing the ones in the row to zeros and the zeros in the row to ones. We now have 14 sequences of binary digits of length 7 where each of the pairs of sequences has Hamming distance at least three. Finally, we can add the two additional strings 0000000 and 1111111 and maintain this property. Thus, we have the remarkably large collection of binary strings (16 strings), each pair of which has distance at least three. Thus, we have a 16 codeword code which will correct 1 error. Although this is not the way that Hamming constructed the code that Shannon mentions in his very early paper on information theory, it is isomorphic to that code. There can be no larger collection of code words for a code with code words of length 7 that corrects one error. Using other finite projective (no parallel lines) and finite affine planes (unique parallels), one can construct other error correcting codes. The symmetric combinatorial structure of these geometries (same number of lines through a point; same number of points on a line) are what make it possible for the associated matrices of the geometries to have nice properties as codewords.

1. Introduction
2. Basic ideas
3. The channel concept
4. Codes and geometry
5. Theory and practice of codes
6. Error correction technologies
7. References