Namespaces
Variants
Actions

Difference between revisions of "Gray code"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g1102001.png" /> denote the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g1102002.png" /> binary strings of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g1102003.png" />. A Gray code of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g1102005.png" /> is a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g1102006.png" /> of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g1102007.png" /> in which every successive pair (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g1102008.png" />) of bitstrings differs by one bit in some position; the bits in all other positions agree. A cyclic Gray code is one in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g1102009.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020010.png" /> also differ by one bit. These bitstrings can also be thought of as the characteristic vectors of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020011.png" />. The hypercube of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020013.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020015.png" />-cube) is the [[Graph|graph]] whose vertex set is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020016.png" /> and whose edge set consists of those pairs of vertices that differ by one bit. Thus, a Gray code is a Hamilton path (cf. [[Graph circuit|Graph circuit]]) on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020017.png" />-cube and a cyclic Gray code is a Hamilton cycle (cf. [[Graph circuit|Graph circuit]]) on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020018.png" />-cube.
+
<!--
 +
g1102001.png
 +
$#A+1 = 48 n = 0
 +
$#C+1 = 48 : ~/encyclopedia/old_files/data/G110/G.1100200 Gray code
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
Let  $  {\mathcal B} _ {n} $
 +
denote the set of all $  N = 2  ^ {n} $
 +
binary strings of length $  n $.  
 +
A Gray code of order $  n $
 +
is a sequence $  B _ {0} \dots B _ {N - 1 }  $
 +
of elements of $  {\mathcal B} _ {n} $
 +
in which every successive pair ( $  B _ {i} , B _ {i + 1 }  $)  
 +
of bitstrings differs by one bit in some position; the bits in all other positions agree. A cyclic Gray code is one in which $  B _ {0} $
 +
and $  B _ {N - 1 }  $
 +
also differ by one bit. These bitstrings can also be thought of as the characteristic vectors of subsets of $  \{ 1 \dots n \} $.  
 +
The hypercube of order $  n $(
 +
or $  n $-
 +
cube) is the [[Graph|graph]] whose vertex set is $  {\mathcal B} _ {n} $
 +
and whose edge set consists of those pairs of vertices that differ by one bit. Thus, a Gray code is a Hamilton path (cf. [[Graph circuit|Graph circuit]]) on the $  n $-
 +
cube and a cyclic Gray code is a Hamilton cycle (cf. [[Graph circuit|Graph circuit]]) on the $  n $-
 +
cube.
  
 
===Origins and uses.===
 
===Origins and uses.===
The term  "Gray code"  comes from F. Gray, who worked as an engineer at Bell Laboratories, and who, in 1953, obtained US patent 2,632,058 for  "pulse code communication" . The patent contained a construction which has come be known as the binary reflected Gray code (BRG code), after the recursive construction rule given below for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020019.png" />.
+
The term  "Gray code"  comes from F. Gray, who worked as an engineer at Bell Laboratories, and who, in 1953, obtained US patent 2,632,058 for  "pulse code communication" . The patent contained a construction which has come be known as the binary reflected Gray code (BRG code), after the recursive construction rule given below for $  n > 0 $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020020.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
$$ \tag{a1 }
 +
{\mathcal C} ( n ) = {\mathcal C} ( n - 1 ) \cdot 0 \circ {\overline{ {{\mathcal C} ( n - 1 ) }}\; } \cdot 1 .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020021.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020022.png" />, the empty string. There are three operations. The dot operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020023.png" />, for a list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020024.png" />, gives the list consisting of every string in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020025.png" /> appended with the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020026.png" />. The concatenation operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020027.png" /> gives the list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020028.png" /> followed by the list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020029.png" />. By <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020030.png" /> one denotes the reversal of the list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020031.png" />. Thus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020034.png" />.
+
If $  n = 0 $,  
 +
then $  {\mathcal C} ( n ) = \varepsilon $,  
 +
the empty string. There are three operations. The dot operation $  {\mathcal L} \cdot x $,  
 +
for a list $  {\mathcal L} $,  
 +
gives the list consisting of every string in $  {\mathcal L} $
 +
appended with the symbol $  x $.  
 +
The concatenation operation $  {\mathcal L} _ {1} \circ {\mathcal L} _ {2} $
 +
gives the list $  {\mathcal L} _ {1} $
 +
followed by the list $  {\mathcal L} _ {2} $.  
 +
By $  {\overline {\mathcal L} \; } $
 +
one denotes the reversal of the list $  {\mathcal L} $.  
 +
Thus $  {\mathcal C} ( 1 ) = 0,1 $,
 +
$  {\mathcal C} ( 2 ) = 00, 10, 11, 01 $
 +
and $  {\mathcal C} ( 3 ) = 000, 100, 110, 010, 011,111, 101, 001 $.
  
There is a simple relation between the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020035.png" />th binary string (counting from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020036.png" />) in the BRG code, call it <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020037.png" />, and the binary representation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020038.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020039.png" />,
+
There is a simple relation between the $  r $
 +
th binary string (counting from 0 $)  
 +
in the BRG code, call it $  g _ {n} \dots g _ {1} $,  
 +
and the binary representation of $  r = ( b _ {n - 1 }  \dots b _ {0} ) _ {2} $.  
 +
For $  i = 1 \dots n $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020040.png" /></td> </tr></table>
+
$$
 +
b _ {i - 1 }  = b _ {i} \oplus g _ {i}  \textrm{ and  }  g _ {i} = b _ {i - 1 }  \oplus b _ {i} ,
 +
$$
  
where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020041.png" /> is the exclusive-or operation.
+
where the $  \oplus $
 +
is the exclusive-or operation.
  
 
===Connections and variations.===
 
===Connections and variations.===
The BRG code can be used in solving the Chinese rings puzzle and the towers of Hanoi puzzle, both of which predate Gray's patent [[#References|[a1]]]. In practice, variants of the BRG code are often required. Uniform Gray codes refer to those that have, at least approximately, the same number of bit changes occurring in each position. A monotone Gray code has the property that all strings with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020042.png" /> ones appear before any with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020043.png" /> ones [[#References|[a6]]].
+
The BRG code can be used in solving the Chinese rings puzzle and the towers of Hanoi puzzle, both of which predate Gray's patent [[#References|[a1]]]. In practice, variants of the BRG code are often required. Uniform Gray codes refer to those that have, at least approximately, the same number of bit changes occurring in each position. A monotone Gray code has the property that all strings with $  k $
 +
ones appear before any with $  k + 2 $
 +
ones [[#References|[a6]]].
  
 
==Combinatorial Gray codes.==
 
==Combinatorial Gray codes.==
Line 21: Line 72:
  
 
===Combinations, partitions, permutations, and other objects.===
 
===Combinations, partitions, permutations, and other objects.===
Represent combinations (cf. [[Combination|Combination]]) by their characteristic vectors; i.e., the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020044.png" />-combinations of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020045.png" />-set are represented by those strings in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020046.png" /> that have exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020047.png" /> ones. For combinations, a rule analogous to (a1) may be given, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020048.png" />. The result is a Gray code in which each string differs from its predecessor by transposition of two bits:
+
Represent combinations (cf. [[Combination|Combination]]) by their characteristic vectors; i.e., the $  k $-
 +
combinations of an $  n $-
 +
set are represented by those strings in $  {\mathcal B} _ {n} $
 +
that have exactly $  k $
 +
ones. For combinations, a rule analogous to (a1) may be given, for $  0 < k < n $.  
 +
The result is a Gray code in which each string differs from its predecessor by transposition of two bits:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020049.png" /></td> </tr></table>
+
$$
 +
{\mathcal C} ( n,k ) = {\mathcal C} ( n - 1,k ) \cdot 0 \circ {\overline{ {{\mathcal C} ( n - 1,k - 1 ) }}\; } \cdot 1 .
 +
$$
  
 
This list gives rise to what is known as a revolving door algorithm; one element leaves the set and another element enters the set [[#References|[a2]]].
 
This list gives rise to what is known as a revolving door algorithm; one element leaves the set and another element enters the set [[#References|[a2]]].
  
For permutations (cf. [[Permutation|Permutation]]) a Gray code is known in which successive permutations differ only by transposition of two adjacent elements. It is a recursive construction in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020050.png" /> sweeps back and forth through the list of permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110200/g11020051.png" />. This Gray code is usually attributed to S.M. Johnson and H.F. Trotter [[#References|[a3]]], but was known much earlier by experts in campanology (which is the study of bells and bell ringing).
+
For permutations (cf. [[Permutation|Permutation]]) a Gray code is known in which successive permutations differ only by transposition of two adjacent elements. It is a recursive construction in which $  n $
 +
sweeps back and forth through the list of permutations of $  1 \dots n - 1 $.  
 +
This Gray code is usually attributed to S.M. Johnson and H.F. Trotter [[#References|[a3]]], but was known much earlier by experts in campanology (which is the study of bells and bell ringing).
  
 
A Gray code is known for the linear extensions of partially ordered sets in which each extension differs by one or two transpositions of adjacent poset elements [[#References|[a4]]].
 
A Gray code is known for the linear extensions of partially ordered sets in which each extension differs by one or two transpositions of adjacent poset elements [[#References|[a4]]].

Latest revision as of 19:42, 5 June 2020


Let $ {\mathcal B} _ {n} $ denote the set of all $ N = 2 ^ {n} $ binary strings of length $ n $. A Gray code of order $ n $ is a sequence $ B _ {0} \dots B _ {N - 1 } $ of elements of $ {\mathcal B} _ {n} $ in which every successive pair ( $ B _ {i} , B _ {i + 1 } $) of bitstrings differs by one bit in some position; the bits in all other positions agree. A cyclic Gray code is one in which $ B _ {0} $ and $ B _ {N - 1 } $ also differ by one bit. These bitstrings can also be thought of as the characteristic vectors of subsets of $ \{ 1 \dots n \} $. The hypercube of order $ n $( or $ n $- cube) is the graph whose vertex set is $ {\mathcal B} _ {n} $ and whose edge set consists of those pairs of vertices that differ by one bit. Thus, a Gray code is a Hamilton path (cf. Graph circuit) on the $ n $- cube and a cyclic Gray code is a Hamilton cycle (cf. Graph circuit) on the $ n $- cube.

Origins and uses.

The term "Gray code" comes from F. Gray, who worked as an engineer at Bell Laboratories, and who, in 1953, obtained US patent 2,632,058 for "pulse code communication" . The patent contained a construction which has come be known as the binary reflected Gray code (BRG code), after the recursive construction rule given below for $ n > 0 $.

$$ \tag{a1 } {\mathcal C} ( n ) = {\mathcal C} ( n - 1 ) \cdot 0 \circ {\overline{ {{\mathcal C} ( n - 1 ) }}\; } \cdot 1 . $$

If $ n = 0 $, then $ {\mathcal C} ( n ) = \varepsilon $, the empty string. There are three operations. The dot operation $ {\mathcal L} \cdot x $, for a list $ {\mathcal L} $, gives the list consisting of every string in $ {\mathcal L} $ appended with the symbol $ x $. The concatenation operation $ {\mathcal L} _ {1} \circ {\mathcal L} _ {2} $ gives the list $ {\mathcal L} _ {1} $ followed by the list $ {\mathcal L} _ {2} $. By $ {\overline {\mathcal L} \; } $ one denotes the reversal of the list $ {\mathcal L} $. Thus $ {\mathcal C} ( 1 ) = 0,1 $, $ {\mathcal C} ( 2 ) = 00, 10, 11, 01 $ and $ {\mathcal C} ( 3 ) = 000, 100, 110, 010, 011,111, 101, 001 $.

There is a simple relation between the $ r $ th binary string (counting from $ 0 $) in the BRG code, call it $ g _ {n} \dots g _ {1} $, and the binary representation of $ r = ( b _ {n - 1 } \dots b _ {0} ) _ {2} $. For $ i = 1 \dots n $,

$$ b _ {i - 1 } = b _ {i} \oplus g _ {i} \textrm{ and } g _ {i} = b _ {i - 1 } \oplus b _ {i} , $$

where the $ \oplus $ is the exclusive-or operation.

Connections and variations.

The BRG code can be used in solving the Chinese rings puzzle and the towers of Hanoi puzzle, both of which predate Gray's patent [a1]. In practice, variants of the BRG code are often required. Uniform Gray codes refer to those that have, at least approximately, the same number of bit changes occurring in each position. A monotone Gray code has the property that all strings with $ k $ ones appear before any with $ k + 2 $ ones [a6].

Combinatorial Gray codes.

The Gray code concept has been extended from subsets to many other types of combinatorial objects. The concept of a combinatorial Gray code is not precisely defined, but the two crucial ideas are that each object is listed exactly once and successive objects differ in some small prescribed way. Combinatorial Gray codes are useful because they often lead to efficient algorithms for generating (i.e., listing) the objects. Some of the more important combinatorial Gray codes are as follows.

Combinations, partitions, permutations, and other objects.

Represent combinations (cf. Combination) by their characteristic vectors; i.e., the $ k $- combinations of an $ n $- set are represented by those strings in $ {\mathcal B} _ {n} $ that have exactly $ k $ ones. For combinations, a rule analogous to (a1) may be given, for $ 0 < k < n $. The result is a Gray code in which each string differs from its predecessor by transposition of two bits:

$$ {\mathcal C} ( n,k ) = {\mathcal C} ( n - 1,k ) \cdot 0 \circ {\overline{ {{\mathcal C} ( n - 1,k - 1 ) }}\; } \cdot 1 . $$

This list gives rise to what is known as a revolving door algorithm; one element leaves the set and another element enters the set [a2].

For permutations (cf. Permutation) a Gray code is known in which successive permutations differ only by transposition of two adjacent elements. It is a recursive construction in which $ n $ sweeps back and forth through the list of permutations of $ 1 \dots n - 1 $. This Gray code is usually attributed to S.M. Johnson and H.F. Trotter [a3], but was known much earlier by experts in campanology (which is the study of bells and bell ringing).

A Gray code is known for the linear extensions of partially ordered sets in which each extension differs by one or two transpositions of adjacent poset elements [a4].

For set partitions, Gray codes are known in which successive partitions differ only by an element moving from some block to some other block. For numerical partitions, a Gray code is known in which successive partitions differ by one part increasing by one and another part decreasing by one [a5].

Many combinatorial Gray codes can be viewed as Hamilton cycles in vertex-transitive graphs, particularly Cayley graphs (cf. also Graph; Graph circuit) [a7]. The Gray code for permutations gives a Hamilton cycle on a Cayley graph known as the permutohedron.

References

[a1] F.G. Heath, "Origins of the binary code" Scientific Amer. , 227 (1972) pp. 76–83
[a2] A. Nijenhuis, H.S. Wilf, "Combinatorial algorithms" , Acad. Press (1978) (Edition: Second)
[a3] E.M. Reingold, J. Nievergelt, N. Deo, "Combinatorial algorithms: Theory and practice" , Prentice-Hall (1977)
[a4] G. Pruesse, F. Ruskey, "Generating linear extensions fast" SIAM J. Computing , 23 (1994) pp. 373–386
[a5] C.D. Savage, "Gray code sequences of partitions" J. Algorithms , 10 (1989) pp. 577–595
[a6] C.D. Savage, P. Winkler, "Monotone Gray codes and the middle two levels problem" J. Combinatorial Th. A , 70 (1995)
[a7] D. Witte, J.A. Gallian, "A survey: Hamiltonian cycles in Cayley graphs" Discrete Math. , 51 (1984) pp. 293–304
How to Cite This Entry:
Gray code. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Gray_code&oldid=47135
This article was adapted from an original article by F. Ruskey (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article