The reflected binary code, also known as Gray code after Frank Gray
Frank Gray (researcher)
Frank Gray was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic, and is remembered for the Gray code....
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
where two successive values differ in only one bit. It is a non-weighted code.
The reflected binary code was originally designed to prevent spurious output from electromechanical switch
Switch
In electronics, a switch is an electrical component that can break an electrical circuit, interrupting the current or diverting it from one conductor to another....
es. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television
Digital terrestrial television
Digital terrestrial television is the technological evolution of broadcast television and advance from analog television, which broadcasts land-based signals...
Data Over Cable Service Interface Specification is an international telecommunications standard that permits the addition of high-speed data transfer to an existing cable TV system...
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
Frank Gray was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic, and is remembered for the Gray code....
introduced the term reflected binary code in his 1947 patent application, remarking that the code had "as yet no recognized name". He derived the name from the fact that it "may be built up from the conventional binary code by a sort of reflection process".
The code was later named after Gray by others who used it. Two different 1953 patent applications give "Gray code" as an alternative name for the "reflected binary code"; one of those also lists "minimum error code" and "cyclic permutation code" among the names. A 1954 patent application refers to "the Bell Telephone Gray code".
Motivation
Many devices indicate position by closing and opening switches. If that device uses natural binary codes
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
, these two positions would be right next to each other:
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
is that, with real (mechanical) switches, it is very unlikely that switches will change states exactly in synchrony. In the transition between the two states shown above, all three switches change state. In the brief period while all are changing, the switches will read some spurious position. Even without keybounce, the transition might look like 011 — 001 — 101 — 100. When the switches appear to be in position 001, the observer cannot tell if that is the "real" position 001, or a transitional state between two other positions. If the output feeds into a sequential
Sequential logic
In digital circuit theory, sequential logic is a type of logic circuit whose output depends not only on the present input but also on the history of the input. This is in contrast to combinational logic, whose output is a function of, and only of, the present input...
In digital circuit theory, combinational logic is a type of digital logic which is implemented by boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the...
) then the sequential system may store a false value.
The reflected binary code solves this problem by changing only one switch at a time, so there is never any ambiguity of position,
Notice that state 7 can roll over to state 0 with only one switch change. This is called the "cyclic" property of a Gray code. A good way to remember Gray coding is by being aware that the least significant bit follows a repetitive pattern of 2. That is 11, 00, 11 etc. and the second digit follows a pattern of fours.
More formally, a Gray code is a code assigning to each of a contiguous set of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s, or to each member of a circular list, a word of symbols such that each two adjacent code words differ by one symbol. These codes are also known as single-distance codes, reflecting the Hamming distance
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
of 1 between adjacent codes. There can be more than one Gray code for a given word length, but the term was first applied to a particular binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
code for the non-negative integers, the binary-reflected Gray code, or BRGC, the three-bit version of which is shown above.
History and practical application
Reflected binary codes were applied to mathematical puzzles before they became known to engineers. The French engineer Émile Baudot
Émile Baudot
Jean-Maurice-Émile Baudot , French telegraph engineer and inventor of the first means of digital communication Baudot code, was one of the pioneers of telecommunications...
Telegraphy is the long-distance transmission of messages via some form of signalling technology. Telegraphy requires messages to be converted to a code which is known to both sender and receiver...
The Legion of Honour, or in full the National Order of the Legion of Honour is a French order established by Napoleon Bonaparte, First Consul of the Consulat which succeeded to the First Republic, on 19 May 1802...
medal for his work. The Gray code is sometimes attributed, incorrectly, to Elisha Gray
Elisha Gray
Elisha Gray was an American electrical engineer who co-founded the Western Electric Manufacturing Company...
(in Principles of Pulse Code Modulation, K. W. Cattermole, for example).
Frank Gray was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic, and is remembered for the Gray code....
, who became famous for inventing the signaling method that came to be used for compatible color television, invented a method to convert analog signals to reflected binary code groups using vacuum tube
Vacuum tube
In electronics, a vacuum tube, electron tube , or thermionic valve , reduced to simply "tube" or "valve" in everyday parlance, is a device that relies on the flow of electric current through a vacuum...
-based apparatus. The method and apparatus were patented in 1953 and the name of Gray stuck to the codes. The "PCM tube" apparatus that Gray patented was made by Raymond W. Sears of Bell Labs, working with Gray and William M. Goodall, who credited Gray for the idea of the reflected binary code.
The use of his eponymous codes that Gray was most interested in was to minimize the effect of error in the conversion of analog signals to digital; his codes are still used today for this purpose, and others.
Position encoders
Gray codes are used in position encoders (linear encoder
Linear encoder
A linear encoder is a sensor, transducer or readhead paired with a scale that encodes position. The sensor reads the scale in order to convert the encoded position into an analog or digital signal, which can then be decoded into position by a digital readout or motion controller.The encoder can be...
A rotary encoder, also called a shaft encoder, is an electro-mechanical device that converts the angular position or motion of a shaft or axle to an analog or digital code. The output of incremental encoders provides information about the motion of the shaft which is typically further processed...
s), in preference to straightforward binary encoding. This avoids the possibility that, when several bits change in the binary representation of an angle, a misread will result from some of the bits changing before others. Originally, the code pattern was electrically conductive, supported (in a rotary encoder) by an insulating disk. Each track had its own stationary metal spring contact; one more contact made the connection to the pattern. That common contact was connected by the pattern to whichever of the track contacts were resting on the conductive pattern. However, sliding contacts wear out and need maintenance, which favors optical encoders.
Regardless of the care in aligning the contacts, and accuracy of the pattern, a natural-binary code would have errors at specific disk positions, because it is impossible to make all bits change at exactly the same time as the disk rotates. The same is true of an optical encoder; transitions between opaque and transparent cannot be made to happen simultaneously for certain exact positions. Rotary encoders benefit from the cyclic nature of Gray codes, because consecutive positions of the sequence differ by only one bit.
Towers of Hanoi
The binary-reflected Gray code can also be used to serve as a solution guide for the Towers of Hanoi problem
Tower of Hanoi
The Tower of Hanoi or Towers of Hanoi, also called the Tower of Brahma or Towers of Brahma, is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod...
, as well as the classical Chinese rings puzzle, a sequential mechanical puzzle mechanism. It also forms a Hamiltonian cycle on a hypercube
Hypercube
In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
properties of Gray codes, they are sometimes used in genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s. They are very useful in this field, since mutations in the code allow for mostly incremental changes, but occasionally a single bit-change can cause a big leap and lead to new properties.
Error correction
In modern digital communications, Gray codes play an important role in error correction. For example, in a digital modulation scheme such as QAM
Quadrature amplitude modulation
Quadrature amplitude modulation is both an analog and a digital modulation scheme. It conveys two analog message signals, or two digital bit streams, by changing the amplitudes of two carrier waves, using the amplitude-shift keying digital modulation scheme or amplitude modulation analog...
In digital communications, symbol rate is the number of symbol changes made to the transmission medium per second using a digitally modulated signal or a line code. The Symbol rate is measured in baud or symbols/second. In the case of a line code, the symbol rate is the pulse rate in pulses/second...
A constellation diagram is a representation of a signal modulated by a digital modulation scheme such as quadrature amplitude modulation or phase-shift keying. It displays the signal as a two-dimensional scatter diagram in the complex plane at symbol sampling instants...
is arranged so that the bit patterns conveyed by adjacent constellation points differ by only one bit. By combining this with forward error correction
Forward error correction
In telecommunication, information theory, and coding theory, forward error correction or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels....
capable of correcting single-bit errors, it is possible for a receiver
Receiver (radio)
A radio receiver converts signals from a radio antenna to a usable form. It uses electronic filters to separate a wanted radio frequency signal from all other signals, the electronic amplifier increases the level suitable for further processing, and finally recovers the desired information through...
to correct any transmission errors that cause a constellation point to deviate into the area of an adjacent point. This makes the transmission system less susceptible to noise
Noise
In common use, the word noise means any unwanted sound. In both analog and digital electronics, noise is random unwanted perturbation to a wanted signal; it is called noise as a generalisation of the acoustic noise heard when listening to a weak radio transmission with significant electrical noise...
.
Communication between clock domains
Digital logic designers use Gray codes extensively for passing multi-bit count information between synchronous logic that operates at different clock frequencies. The logic is considered operating in different "clock domains". It is fundamental to the design of large chips that operate with many different clocking frequencies.
Gray code counters and arithmetic
A typical use of Gray code counters is building a FIFO (first-in, first-out) data buffer that has read and write ports that exist in different clock domains. The input and output counters inside such a dual-port FIFO are often stored using Gray code to prevent invalid transient states from being captured when the count crosses clock domains.
The updated read and write pointers need to be passed between clock domains when they change, to be able to track FIFO empty and full status in each domain. Each bit of the pointers is sampled non-deterministically for this clock domain transfer. So for each bit, either the old value or the new value is propagated. Therefore, if more than one bit in the multi-bit pointer is changing at the sampling point, a "wrong" binary value (neither new nor old) can be propagated. By guaranteeing only one bit can be changing, Gray codes guarantee that the only possible sampled values are the new or old multi-bit value. Typically Gray codes of power-of-two length are used.
Sometimes digital buses in electronic systems are used to convey quantities that can only increase or decrease by one at a time, for example the output of an event counter which is being passed between clock domains or to a digital-to-analog converter. The advantage of Gray codes in these applications is that differences in the propagation delays of the many wires that represent the bits of the code cannot cause the received value to go through states that are out of the Gray code sequence. This is similar to the advantage of Gray codes in the construction of mechanical encoders, however the source of the Gray code is an electronic counter in this case. The counter itself must count in Gray code, or if the counter runs in binary then the output value from the counter must be reclocked after it has been converted to Gray code, because when a value is converted from binary to Gray code, it is possible that differences in the arrival times of the binary data bits into the binary-to-Gray conversion circuit will mean that the code could go briefly through states that are wildly out of sequence. Adding a clocked register after the circuit that converts the count value to Gray code may introduce a clock cycle of latency, so counting directly in Gray code may be advantageous. A Gray code counter was patented in 1962 , and there have been many others since. In recent times a Gray code counter can be implemented as a state machine in Verilog
Verilog
In the semiconductor and electronic design industry, Verilog is a hardware description language used to model electronic systems. Verilog HDL, not to be confused with VHDL , is most commonly used in the design, verification, and implementation of digital logic chips at the register-transfer level...
. In order to produce the next count value, it is necessary to have some combinational logic that will increment the current count value that is stored in Gray code. Probably the most obvious way to increment a Gray code number is to convert it into ordinary binary code, add one to it with a standard binary adder, and then convert the result back to Gray code. This approach was discussed in a paper in 1996 and then subsequently patented by someone else in 1998 . Other methods of counting in Gray code are discussed in a report by R. W. Doran, including taking the output from the first latches of the master-slave flip flops in a binary ripple counter.
Perhaps the most common electronic counter with the "only one bit changes at a time" property is the Johnson counter.
Constructing an n-bit Gray code
The binary-reflected Gray code list for n bits can be generated recursively
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
from the list for n−1 bits by reflecting the list (i.e. listing the entries in reverse order), concatenating the original list with the reversed list, prefixing the entries in the original list with a binary 0, and then prefixing the entries in the reflected list with a binary 1. For example, generating the n = 3 list from the n = 2 list:
2-bit list:
00, 01, 11, 10
Reflected:
10, 11, 01, 00
Prefix old entries with 0:
000, 001, 011, 010,
Prefix new entries with 1:
110, 111, 101, 100
Concatenated:
000, 001, 011, 010,
110, 111, 101, 100
The one-bit Gray code is G1 = (0, 1). This can be thought of as built recursively as above from a zero-bit Gray code G0 = { Λ } consisting of a single entry of zero length. This iterative process of generating Gn+1 from Gn makes the following properties of the standard reflecting code clear:
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
of the numbers 0, ... , 2n−1. (Each number appears exactly once in the list.)
Gn is embedded as the first half of Gn+1.
Therefore the coding is stable, in the sense that once a binary number appears in Gn it appears in the same position in all longer lists; so it makes sense to talk about the reflective Gray code value of a number: G(m) = the m-th reflecting Gray code, counting from 0.
Each entry in Gn differs by only one bit from the previous entry. (The Hamming distance is 1.)
The last entry in Gn differs by only one bit from the first entry. (The code is cyclic.)
These characteristics suggest a simple and fast method of translating a binary value into the corresponding Gray code. Each bit is inverted if the next higher bit of the input value is set to one. This can be performed in parallel by a bit-shift and exclusive-or operation if they are available: the nth Gray code is obtained by computing
A similar method can be used to perform the reverse translation, but the computation of each bit depends on the computed value of the next higher bit so it cannot be performed in parallel. Assuming is the th gray-coded bit ( being the most significant bit), and is the th binary-coded bit ( being the most-significant bit), the reverse translation can be given recursively: , and . Alternatively, decoding a Gray code into a binary number can be described as a prefix sum
Prefix sum
In computer science, the prefix sum, or scan, of a sequence of numbers is a second sequence of numbers , the sums of prefixes of the input sequence:-Parallel algorithm:A prefix sum can be calculated in parallel by the following steps....
of the bits in the Gray code, where each individual summation operation in the prefix sum is performed modulo two.
To construct the binary-reflected Gray code iteratively, start with the code 0, and at step i find the bit position of the least significant '1' in the binary representation of i - flip the bit at that position in the previous code to get the next code. The bit positions start 0, 1, 0, 2, 0, 1, 0, 3, ... .
Converting to and from Gray code
/*
The purpose of this function is to convert an unsigned
binary number to reflected binary Gray code.
unsigned short binaryToGray(unsigned short num)
{
return (num>>1) ^ num;
}
/*
The purpose of this function is to convert a reflected binary
Gray code number to a binary number.
unsigned short grayToBinary(unsigned short num)
{
unsigned short temp = num ^ (num>>8);
temp ^= (temp>>4);
temp ^= (temp>>2);
temp ^= (temp>>1);
return temp;
}
Special types of Gray codes
In practice, a "Gray code" almost always refers to a binary-reflected Gray code (BRGC).
However, mathematicians have discovered other kinds of Gray codes.
Like BRGCs, each consists of a lists of words, where each word differs from the next in only one digit (each word has a Hamming distance
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
of 1 from the next word).
n-ary Gray code
There are many specialized types of Gray codes other than the binary-reflected Gray code. One such type of Gray code is the n-ary Gray code, also known as a non-Boolean Gray code.
As the name implies, this type of Gray code uses non-Boolean values in its encodings.
Ternary is an adjective meaning "composed of three items". It can refer to:* Ternary complex, a complex formed by the interaction of three molecules* Ternary compound, a type of chemical compound...
) Gray code would use the values {0, 1, 2}.
The (n, k)-Gray code is the n-ary Gray code with k digits.
The sequence of elements in the (3, 2)-Gray code is: {00, 01, 02, 12, 10, 11, 21, 22, 20}.
The (n, k)-Gray code may be constructed recursively, as the BRGC, or may be constructed iteratively
Iteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
to iteratively generate the (N, k)-Gray code is presented (in C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
):
// parameters: value, base, digits
// Convert a value to a graycode with the given base and digits. Iterating
// through a sequence of values would result in a sequence of graycodes in
// which only one digit changes at a time.
int baseN[digits]; // Stores the ordinary base-N number, one digit per entry
int gray[digits]; // Stores the base-N graycode number
int i; // The loop variable
// Put the normal baseN number into the baseN array. For base 10, 109
// would be stored as [9,0,1]
int tempvalue = value;
for(i = 0; i < digits; i++) {
baseN[i] = tempvalue % base;
tempvalue /= base;
}
// Convert the normal baseN number into the graycode equivalent. Note that
// the loop starts at the most significant digit and goes down.
int shift = 0;
for(i = digits - 1; i >= 0; i--) {
// The gray digit gets shifted down equal to the sum of the higher
// digits.
gray[i] = (baseN[i] - shift) % base;
shift += gray[i] - base; // - base to prevent negative in mod operation
}
// EXAMPLES
// input: value = 1899, base = 10, digits = 4
// output: baseN[] = [9,9,8,1], gray[] = [0,1,7,1]
// input: value = 1900, base = 10, digits = 4
// output: baseN[] = [0,0,9,1], gray[] = [0,1,8,1]
There are other graycode algorithms for (n,k)-Gray codes. It is important to note that the (n,k)-Gray codes produced by the above algorithm is always cyclical; some algorithms, such as that by Guan, lack this property when k is odd. On the other hand, while only one digit at a time changes with this method, it can change by wrapping (looping from n-1 to 0). In Guan's algorithm, the count alternately rises and falls, so that the numeric difference between two graycode digits is always one.
Gray codes are not uniquely defined, because a permutation of the columns of such a code is a Gray code too. The above procedure produces a code in which the lower the significance of a digit, the more often it changes, making it similar to normal counting methods.
Balanced Gray code
Although the binary reflected Gray code is useful in many scenarios, it is not
optimal in certain cases because of a lack of "uniformity". In balanced Gray codes, we seek to make the
number of changes in each coordinate position as close as possible. To make this
more precise, let G be a R-ary complete Gray cycle having transition
sequence ; the transition counts (spectrum) of are the
collection of integers defined by
We say that a Gray code is uniform or uniformly balanced if
its transition counts are all equal, in which case we have
for all k. Clearly, when , such codes exist only if n is a power of
2. Otherwise, if n does not divide evenly, the best we can do is to
construct well-balanced codes where every transition count is either or . Gray codes can also be
exponentially balanced if all of their transition counts are adjacent
powers of two, and such codes exist for every power of two.
We will now show a construction for well-balanced binary Gray codes which allows us
to generate a n-digit balanced Gray code for every n. The main principle is
to inductively construct a -digit Gray code given an n-digit Gray
code G in such a way that the balanced property is preserved. To do this, we
consider partitions of into an even number L of
non-empty blocks of the form
where , and (mod ). This partition
induces a -digit Gray code given by
If we define the transition multiplicities to be the number of times the digit in position i
changes between consecutive blocks in a partition, then for the -digit
Gray code induced by this partition the transition spectrum is
The delicate part of this construction is to find an adequate partitioning of a
balanced n-digit Gray code such that the code induced by it remains balanced.
Uniform codes can be found when and ,
and this construction can be extended to the R-ary case as well.
Monotonic Gray codes
Monotonic codes are useful in the theory of interconnection networks, especially for
minimizing dilation for linear arrays of processors.
If we define the weight of a binary string to be the number of 1's in
the string, then although we clearly cannot have a Gray code with strictly
increasing weight, we may want to approximate this by having the code run
through two adjacent weights before reaching the next one.
We can formalize the concept of monotone Gray codes as follows: consider the
partition of the hypercube into levels of vertices
that have equal weight, i.e.
for . These levels satisfy . Let be the subgraph of induced by , and let be the edges in . A monotonic Gray code is then a Hamiltonian
path in such that whenever comes before in the path, then .
An elegant construction of monotonic n-digit Gray codes for any n is based on the idea of recursively building subpaths of length having edges in . We define , whenever or , and
otherwise. Here, is a suitably defined permutation and refers
to the path P with its coordinates permuted by . These paths give rise to
two monotonic n-digit Gray codes and given by
The choice of which ensures that these codes are indeed Gray codes turns
out to be . The first few values of are
shown in the table below.
Subpaths in the Savage-Winkler algorithm
j = 0
j = 1
j = 2
j = 3
n = 1
0, 1
n = 2
00, 01
10, 11
n = 3
000, 001
100, 110, 010, 011
101, 111
n = 4
0000, 0001
1000, 1100, 0100, 0110, 0010, 0011
1010, 1011, 1001, 1101, 0101, 0111
1110, 1111
These monotonic Gray codes can be efficiently implemented in such a way that
each subsequent element can be generated in O(n) time. The algorithm is
most easily described using coroutines.
Monotonic codes have an interesting connection to the Lovász conjecture
Lovász conjecture
In graph theory, the Lovász conjecture is a classical problem on Hamiltonian paths in graphs. It says:The original article of Lovász stated the result in the opposite, butthis version became standard...
In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...
contains a Hamiltonian
path. The "middle-level" subgraph is vertex-transitive
Vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...
(that is,
its automorphism group is transitive, so that each vertex has the same "local
environment"" and cannot be differentiated from the others, since we can relabel
the coordinates as well as the binary digits to obtain an automorphism
Automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms of an object forms a group, called the automorphism...
) and the
problem of finding a Hamiltonian path in this subgraph is called the
"middle-levels problem", which can provide insights into the more general
conjecture. The question has been answered affirmatively for , and
the preceding construction for monotonic codes ensures a Hamiltonian path of length
at least 0.839N where N is the number of vertices in the middle-level
subgraph.
Beckett–Gray code
Another type of Gray code, the Beckett–Gray code, is named for Irish playwright Samuel Beckett
Samuel Beckett
Samuel Barclay Beckett was an Irish avant-garde novelist, playwright, theatre director, and poet. He wrote both in English and French. His work offers a bleak, tragicomic outlook on human nature, often coupled with black comedy and gallows humour.Beckett is widely regarded as among the most...
Symmetry generally conveys two primary meanings. The first is an imprecise sense of harmonious or aesthetically pleasing proportionality and balance; such that it reflects beauty or perfection...
Samuel Beckett’s Quad was written in 1981 and first appeared in print in 1984 where the work is described as “[a] piece for four players, light and percussion” and has also been called a “ballet for four people.” It resembles something the shape-theatre ensemble Mummenschanz might have conceived,...
" features four actors and is divided into sixteen time periods. Each period ends with one of the four actors entering or leaving the stage. The play begins with an empty stage, and Beckett wanted each subset of actors to appear on stage exactly once. Clearly the set of actors currently on stage can be represented by a 4-bit binary Gray code. Beckett, however, placed an additional restriction on the script: he wished the actors to enter and exit so that the actor who had been on stage the longest would always be the one to exit. The actors could then be represented by a first in, first out
FIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
queue, so that (of the actors onstage) the actor being dequeued is always the one who was enqueued first. Beckett was unable to find a Beckett–Gray code for his play, and indeed, an exhaustive listing of all possible sequences reveals that no such code exists for n = 4. It is known today that such codes do exist for n = 2, 5, 6, 7, and 8, and do not exist for n = 3 or 4. An example of an 8-bit Beckett–Gray code can be found in Knuth's Art of Computer Programming. According to Sawada and Wong, the search space for n = 6 can be explored in 15 hours, and more than 9,500 solutions for the case n = 7 have been found.
The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it gets to a new corner, the previous corner and all of...
codes, or snakes, are the sequences of nodes of induced path
Induced path
In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the...
s in an n-dimensional hypercube graph, and coil-in-the-box codes, or coils, are the sequences of nodes of induced cycles
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
in a hypercube. Viewed as Gray codes, these sequences have the property of being able to detect any single-bit coding error. Codes of this type were first described by W. H. Kautz in the late 1950s; since then, there has been much research on finding the code with the largest possible number of codewords for a given hypercube dimension.
Single-track Gray code
Yet another kind of Gray code is the single-track Gray code (STGC) developed by N. B. Spedding (NZ Patent 264738 - October 28, 1994)
and refined by Hiltgen, Paterson and Brandestini in "Single-track Gray codes" (1996). The STGC is a cyclical list of P unique binary encodings of length n such that two consecutive words differ in exactly one position, and when the list is examined as a P x n matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
, each column is a cyclic shift of the first column.
A rotary encoder, also called a shaft encoder, is an electro-mechanical device that converts the angular position or motion of a shaft or axle to an analog or digital code. The output of incremental encoders provides information about the motion of the shaft which is typically further processed...
s, where a number of tracks are being sensed by contacts, resulting for each in an output of 0 or 1. To reduce noise due to different contacts not switching at exactly the same moment in time, one preferably sets up the tracks so that the data output by the contacts are in Gray code. To get high angular accuracy, one needs lots of contacts; in order to achieve at least 1 degree accuracy, one needs at least 360 distinct positions per revolution, which requires a minimum of 9 bits of data, and thus the same number of contacts.
If all contacts are placed at the same angular position, then 9 tracks are needed to get a standard BRGC with at least 1 degree accuracy. However, if the manufacturer moves a contact to a different angular position (but at the same distance from the center shaft), then the corresponding "ring pattern" needs to be rotated the same angle to give the same output. If the most significant bit (the inner ring in Figure 1) is rotated enough, it exactly matches the next ring out. Since both rings are then identical, the inner ring can be cut out, and the sensor for that ring moved to the remaining, identical ring (but offset at that angle from the other sensor on that ring).
Those 2 sensors on a single ring make a quadrature encoder.
That reduces the number of tracks for a "1 degree resolution" angular encoder to 8 tracks.
Reducing the number of tracks still further can't be done with BRGC.
For many years, Torsten Sillke and other mathematicians believed that it was impossible to encode position on a single track such that consecutive positions differed at only a single sensor, except for the 2-sensor, 1-track quadrature encoder.
So for applications where 8 tracks were too bulky, people used single-track incremental encoders (quadrature encoders) or 2-track "quadrature encoder + reference notch" encoders.
N. B. Spedding, however, registered a patent in 1994 with several examples showing that it was possible. Hiltgen and Paterson published a paper in 2001 exhibiting a single-track gray code with exactly 360 angular positions, constructed using 9 sensors, the same number as a BRGC with the same resolution. (It would be impossible to discriminate that many positions with any fewer sensors.)
An STGC for P = 30 and n = 5 is reproduced here:
10000
10100
11100
11110
11010
11000
01000
01010
01110
01111
01101
01100
00100
00101
00111
10111
10110
00110
00010
10010
10011
11011
01011
00011
00001
01001
11001
11101
10101
10001
Note that each column is a cyclic shift of the first column, and from any row to the next row only one bit changes.
The single-track nature (like a code chain) is useful in the fabrication of these wheels (compared to BRGC), as only one track is needed, thus reducing their cost and size.
The Gray code nature is useful (compared to chain code
Chain code
A chain code is a lossless compression algorithm for monochrome images. The basic principle of chain codes is to separately encode each connected component, or "blot", in the image. For each such region, a point on the boundary is selected and its coordinates are transmitted...
In combinatorial mathematics, a k-ary De Bruijn sequence B of order n, named after the Dutch mathematician Nicolaas Govert de Bruijn, is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in A appears as a sequence of consecutive characters exactly...
s), as only one sensor will change at any one time, so the uncertainty during a transition between two discrete states will only be plus or minus one unit of angular measurement the device is capable of resolving.
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
In combinatorial mathematics, a k-ary De Bruijn sequence B of order n, named after the Dutch mathematician Nicolaas Govert de Bruijn, is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in A appears as a sequence of consecutive characters exactly...
Gillham code is a digital code using an eleven-wire interface that is used to transmit uncorrected barometric altitude between an encoding altimeter or analog air data computer and a transponder...
Steinhaus–Johnson–Trotter algorithm, an algorithm that generates Gray codes for the factorial number system
The Wolfram Demonstrations Project is hosted by Wolfram Research, whose stated goal is to bring computational exploration to the widest possible audience. It consists of an organized, open-source collection of small interactive programs called Demonstrations, which are meant to visually and...
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
A chain code is a lossless compression algorithm for monochrome images. The basic principle of chain codes is to separately encode each connected component, or "blot", in the image. For each such region, a point on the boundary is selected and its coordinates are transmitted...
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
s are all useful in finding one's absolute position on a single-track rotary encoder (or other position sensor).
Bell Labs
The use of his eponymous codes that Gray was most interested in was to minimize the effect of error in the conversion of analog signals to digital; his codes are still used today for this purpose, and others..svg.png)
Gray codes are used in position encoders (linear encoder
The binary-reflected Gray code list for n bits can be generated recursively
is the 
th gray-coded bit (
being the most significant bit), and 
is the 
th binary-coded bit (
being the most-significant bit), the reverse translation can be given recursively: 
, and 
. Alternatively, decoding a Gray code into a binary number can be described as a prefix sum
; the transition counts (spectrum) of 
are the
, such codes exist only if n is a power of
evenly, the best we can do is to
or 
. Gray codes can also be
-digit Gray code 
given an n-digit Gray
into an even number L of
, and 
(mod 
). This partition
-digit Gray code given by
to be the number of times the digit in position i
-digit
is
and 
,
into levels of vertices
. These levels satisfy 
. Let
be the subgraph of 
induced by 
, and let
be the edges in 
. A monotonic Gray code is then a Hamiltonian
such that whenever 
comes before
in the path, then 
.
of length 
having edges in 
. We define
, 
whenever 
or 
, and
is a suitably defined permutation and 
refers
. These paths give rise to
and 
given by
which ensures that these codes are indeed Gray codes turns
. The first few values of 
are
is vertex-transitive
, and
