MATH STINGER #1

          by Dr. Joel C. Fowler
          Assistant Professor of Mathematics

     In communications, information to be transmitted is often
encoded as strings of zeros and ones.  For example, if the words
"yes" and "no" are to be transmitted, they could be encoded as: 
                       "yes" = 1
                       "no"  = 0.
     The difficulty with this code is that, if any distortion
occurs, a transmitted 1 could easily be changed to a received 0
or vice versa.  One method used to reduce this problem is to use
codewords with built in redundancy.  For example, the following
would be a better code:
                        "yes" = 111
                        "no"  = 000.
     If an error occurs in a single position it can now be
corrected.  If the message 001 is received, for example, it is
likely to have come from a transmitted message of 000.  If 011 is
received it can be decoded as 111.  Of course, if more than one
digit is altered a decoding error will be made.  The chances of
this happening, however, are much smaller than for the "yes" = 1,
"no" = 0 code first given.
     A more sophisticated code can communicate more than just
"yes" and "no" by using more codewords.  For example, the
following code has four codewords and is able to correct any
single digit error:
                         "north" = 00000
                         "south" = 11100
                         "east"  = 00111
                         "west"  = 11011.
     Notice that the ability of a code to correct any single
digit error is due to its having the property that every pair of
codewords differ in at least three positions.  When this
condition is satisfied any one digit change in a codeword
produces a string that is closer to that codeword than any other
codeword.  The error can then be corrected.  For example, a one
digit change in the codeword for "east", 00111, could produce
10111, 01111, 00011, 00101, or 00110 depending on which position
is altered.  Note that each of these is still nearer to 00111
than any other codeword, and hence could be successfully decoded. 
It would take a two digit change in 00111 to produce a word
nearer to some other codeword.  This is true for each codeword
and is a result of the fact that every pair of codewords differ
in at least three positions.  You should check that the above
code satisfies this property.  
     The puzzle for this issue is to find a collection of eight
codewords, each having six digits, that will correct any single
digit error.  In other words, you must find a collection of eight
length six strings of zeros and ones with the property that every
pair differ in at least three positions.
     After you have found them you may wonder if it is possible
to find more than eight codewords with this property (still of
length six).  The answer is no, but the reason is too lengthy to
give here.
     A second (and more difficult) puzzle is to find as many
codewords of length seven as possible that correct one error.  If
you wish to work on this, you should know that there are more
than twelve.
    Stinger #2  Math Stingers Main Page