Gray Codes: Coding Binary Strings

[From the notes of Herb Wilf, transcribed by Emily Moore. Modified and extended by Sam Rebelsky.]

It is possible to apply Gray code techniques to "strings" of characters as well as sets. Consider the set of strings of length three in which all the characters in the string are 0 or 1. These are typically called binary strings. (Binary means "two-valued".)

B3: { 000, 001, 010, 011, 100, 101, 110, 111 }

The order in which they are listed here is called their natural order. If you think of these as binary numbers with place values from right to left of 1, 2, and 4, then the order is the order of their values 0, 1, 2, 3, 4, 5, 6, 7. For example, 111 is 4 + 2 + 1 = 7 and 010 is 0 + 2 + 0 = 2.

A Gray code order of these strings is a listing of the strings so that two strings next to each other differ only in one position. For instance, if we start with 000 the next string listed must have a single 1.

A. Find a listing of all eight strings in Gray code order.

B. Is there more than one such listing? If so, how many listings are there?

C. Find a listing of all sixteen length-four binary strings in Gray code order.

D. Can you generalize the pattern?


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

Warning! This site is under development.

Source text last modified Tue May 5 09:13:23 1998.

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

Contact our webmaster at rebelsky@math.grin.edu