Error Detection

[Written by Sam Rebelsky. Based loosely on a problem by Emily Moore.]

As you may know, values in the computer are represented in as a sequence of binary (0/1) digits. Unfortunately, when values are transmitted, some digits may be flipped randomly. How do computers detect these errors? There are a number of ways. In general, we assume that at most one error is made in a string (that is, at most one digit is flipped from 0 to 1 or from 1 to 0).

Develop a set of three length-three strings of 0's and 1's such that it is impossible to convert one member of the set to another by flipping only one digit. For example, you shouldn't have both 010 and 011 in your set, since we can covert between the two by flipping one digit.

Is it possible to find a set of four length-three strings that have the same characteristics? Why or why not?

What is the biggest set of non-interconvertable length-four strings you can create?

[Front Door] [Problems] [Resolutions] [Essays] [Resources] [Miscellaneous]

Warning! This site is under development.

Source text last modified Tue May 5 08:49:55 1998.

This page generated on Thu May 7 14:25:06 1998 by SiteWeaver.

Contact our webmaster at