Editing Gray code (section)

== History and practical application ==

=== Mathematical puzzles ===

Reflected binary codes were applied to mathematical puzzles before they became known to engineers.

The binary-reflected Gray code represents the underlying scheme of the classical [[Chinese rings puzzle]], a sequential mechanical puzzle mechanism described by the French Louis Gros in 1872.<ref name="Gros_1872"/><ref name="Knuth_2014"/>

It can serve as a solution guide for the [[Towers of Hanoi]] problem, based on a game by the French [[Édouard Lucas]] in 1883.<ref name="Lucas_1883"/><ref name="Parville_1883"/><ref name="Allardice-Fraser_1883"/><ref name="Lucas_1892"/> Similarly, the so-called Towers of Bucharest and Towers of Klagenfurt game configurations yield [[#n-ary|ternary and pentary]] Gray codes.<ref name="Herter-Rote_2016"/>

[[Martin Gardner]] wrote a popular account of the Gray code in his August 1972 [[List of Martin Gardner Mathematical Games columns|"Mathematical Games" column]] in ''[[Scientific American]]''.<ref name="Gardner_1972"/>

The code also forms a [[Hamiltonian cycle]] on a [[hypercube]], where each bit is seen as one dimension.

=== Telegraphy codes ===

{{anchor|Baudot|Excess-1 Gray}}When the French engineer [[Émile Baudot]] changed from using a 6-unit (6-bit) code to 5-unit code for his [[printing telegraph]] system, in 1875<ref name="Zeman-Fischer_1877"/> or 1876,<ref name="Froehlich-Kent_1991"/><ref name="Fischer_2000"/> he ordered the alphabetic characters on his print wheel using a reflected binary code, and assigned the codes using only three of the bits to vowels. With vowels and consonants sorted in their alphabetical order,<ref name="Rothen_1884"/><ref name="Pendry_1920"/><ref name="MacMillan_2010"/> and other symbols appropriately placed, the 5-bit character code has been recognized as a reflected binary code.<ref name="Knuth_2014"/> This code became known as [[Baudot code]]<ref name="ITU_1909"/> and, with minor changes, was eventually adopted as [[International Telegraph Alphabet No.&nbsp;1]] (ITA1, CCITT-1) in 1932.<ref name="ITU_1933_FR"/><ref name="ITU_1933_EN"/><ref name="MacMillan_2010"/> 
 
{{anchor|Schäffler telegraph|Schäffler code}}About the same time, the German-Austrian {{ill|Otto Schäffler|de|Theodor Heinrich Otto Schäffler}}<ref name="Zemanek_1979"/> demonstrated another printing telegraph in Vienna using a 5-bit reflected binary code for the same purpose, in 1874.<ref name="Zemanek_1976"/><ref name="Knuth_2014"/>

=== Analog-to-digital signal conversion ===

[[Frank Gray (researcher)|Frank Gray]], 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]]-based apparatus. Filed in 1947, the method and apparatus were granted a patent in 1953,<ref name="Gray_1947"/> and the name of Gray stuck to the codes. The "[[Pulse-code modulation#History|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.<ref name="Goodall_1951"/>

[[File:US02632058 Gray.png|thumb|upright=1.2|center|Part of front page of Gray's patent, showing PCM tube (10) with reflected binary code in plate (15)]]

Gray was most interested in using the codes to minimize errors in converting analog signals to digital; his codes are still used today for this purpose.

=== Position encoders ===

[[File:Encoder Disc (3-Bit).svg|thumb|[[Rotary encoder]] for angle-measuring devices marked in 3-bit binary-reflected Gray code (BRGC)]] 
[[File:Gray code rotary encoder 13-track opened.jpg|thumb|A Gray code absolute rotary encoder with 13 tracks. Housing, interrupter disk, and light source are in the top; sensing element and support components are in the bottom.]]

Gray codes are used in linear and rotary position encoders ([[absolute encoder]]s and [[quadrature encoder]]s) in preference to weighted binary encoding. This avoids the possibility that, when multiple bits change in the binary representation of a position, a misread will result from some of the bits changing before others.

For example, some rotary encoders provide a disk which has an electrically conductive Gray code pattern on concentric rings (tracks). Each track has a stationary metal spring contact that provides electrical contact to the conductive code pattern. Together, these contacts produce output signals in the form of a Gray code. Other encoders employ non-contact mechanisms based on optical or magnetic sensors to produce the Gray code output signals.

Regardless of the mechanism or precision of a moving encoder, position measurement error can occur at specific positions (at code boundaries) because the code may be changing at the exact moment it is read (sampled). A binary output code could cause significant position measurement errors because it is impossible to make all bits change at exactly the same time. If, at the moment the position is sampled, some bits have changed and others have not, the sampled position will be incorrect. In the case of absolute encoders, the indicated position may be far away from the actual position and, in the case of incremental encoders, this can corrupt position tracking.

In contrast, the Gray code used by position encoders ensures that the codes for any two consecutive positions will differ by only one bit and, consequently, only one bit can change at a time. In this case, the maximum position error will be small, indicating a position adjacent to the actual position.

=== Genetic algorithms ===

Due to the [[Hamming distance]] properties of Gray codes, they are sometimes used in [[genetic algorithm]]s.<ref name="Goldberg_1989"/> 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.

=== Boolean circuit minimization ===

Gray codes are also used in labelling the axes of [[Karnaugh map]]s since 1953<ref name="Karnaugh_1953"/><ref name="Wakerly_1994"/><ref name="Brown_2012"/> as well as in [[Händler circle graph]]s since 1958,<ref name="Händler_1958"/><ref name="Steinbuch-Wagner_1967"/><ref name="ISER_1"/><ref name="ISER_2"/> both graphical methods for [[logic circuit minimization]].

=== Error correction ===

In modern [[digital communications]], 1D- and 2D-Gray codes play an important role in error prevention before applying an [[error correction]]. For example, in a [[digital modulation]] scheme such as [[quadrature amplitude modulation|QAM]] where data is typically transmitted in [[symbol rate|symbols]] of 4 bits or more, the signal's [[constellation diagram]] is arranged so that the bit patterns conveyed by adjacent constellation points differ by only one bit. By combining this with [[forward error correction]] capable of correcting single-bit errors, it is possible for a [[Receiver (radio)|receiver]] 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]].
<gallery heights="120" mode="packed" style="text-align:left">
 QPSK Gray Coded.svg|Codes 4-PSK
 8PSK Gray Coded.svg|Codes 8-PSK
 16QAM Gray Coded.svg|Codes 16-QAM
</gallery>

=== Communication between clock domains ===
{{Main article|Clock domain crossing}}

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.

=== Cycling through states with minimal effort ===

If a system has to cycle sequentially through all possible combinations of on-off states of some set of controls, and the changes of the controls require non-trivial expense (e.g. time, wear, human work), a Gray code minimizes the number of setting changes to just one change for each combination of states. An example would be testing a piping system for all combinations of settings of its manually operated valves.

A [[balanced Gray code]] can be constructed,<ref name="Bhat-Savage_1996"/> that flips every bit equally often. Since bit-flips are evenly distributed, this is optimal in the following way: balanced Gray codes minimize the maximal count of bit-flips for each digit.

==== Gray code counters and arithmetic ====
[[George R. Stibitz]] utilized a reflected binary code in a binary pulse counting device in 1941 already.<ref name="Stibitz_1941"/><ref name="Winder_1959"/><ref name="Knuth_2014"/>

A typical use of Gray code counters is building a [[FIFO (computing and electronics)|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.<ref name="Donohue_2003"/> 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,<ref group="nb" name="NB_Arithmetic_conversion"/> 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.<ref name="Hulst_1957"/>

To produce the next count value in a Gray-code counter, it is necessary to have some combinational logic that will increment the current count value that is stored. One way to increment a Gray code number is to convert it into ordinary binary code,<ref name="Powell_1968"/> add one to it with a standard binary adder, and then convert the result back to Gray code.<ref name="Mehta-Owens-Irwin_1996"/> Other methods of counting in Gray code are discussed in a report by [[Robert W. Doran]], including taking the output from the first latches of the master-slave flip flops in a binary ripple counter.<ref name="Doran_2007"/>

==== Gray code addressing<span class="anchor" id="Shifted Gray encoding"></span> ====

As the execution of [[program code]] typically causes an instruction memory access pattern of locally consecutive addresses, [[bus encoding]]s using Gray code addressing instead of binary addressing can reduce the number of state changes of the address bits significantly, thereby reducing the [[CPU power consumption]] in some low-power designs.<ref name="Su-Tsui-Despain_1994"/><ref name="Guo-Parameswaran_2010"/>