The original Gray code Let Z n 2 be the set of binary n -tuples. This may be identified with the vertices of the usual n -cube or with the set of all subsets of an n element set. The original Gray code gives an ordered list of Z n 2 with the property that successive values differ only in a single place. Concatenate these two lists by writing down the first followed by the second in reverse order. If the ordinary integer indexing of the bit sequence is used then a small change in reception, between 15 and 16, for instance, has a large impact on the bit string understood.
Gray codes enable a coding that minimizes the effect of such an error.
This is implemented through keeping track of the divisibility by 2 and of the step number. Then and . Thus from a given string in the Gray code and the rank one can compute the successor. There is a parsimonious implementation of this in the algorithm given in the appendix. Let be the original data supposed to be independent and identically distributed from an unknown distribution F on a space .