# Gray code

A Gray code is an ordering of the \( 2^{n} \) n-bit [binary numbers](https://www.edgepedia.org/binary-number) in which successive entries differ in exactly one bit position.<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup> The best-known instance is the binary reflected Gray code (BRGC), named after Frank Gray, a researcher at Bell Telephone Laboratories who patented its use in pulse code communication as U.S. Patent 2,632,058, filed 13 November 1947 and issued 17 March 1953.<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup><sup> • </sup><sup>[2](https://patents.google.com/patent/US2632058A/en)</sup> The single-bit-change property makes the code valuable wherever a value is read while it may be changing: rotary encoders, analog-to-digital converters, and counters that cross between asynchronous clock domains.<sup>[3](https://www.ia.omron.com/support/faq/answer/34/faq00941/)</sup>

| Key fact | Detail |
|---|---|
| Definition | An ordering of \( 2^{n} \) binary numbers such that only one bit changes from one entry to the next; codes for 4 or more bits are not unique, even allowing permutation or inversion of bits<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup> |
| Naming | Named for Frank Gray of Bell Telephone Laboratories; U.S. Patent 2,632,058 "Pulse Code Communication", filed 13 November 1947, issued 17 March 1953<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup><sup> • </sup><sup>[2](https://patents.google.com/patent/US2632058A/en)</sup> |
| Earlier use | A Gray code was used in a telegraph demonstrated by French engineer Émile Baudot in 1878<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup> |
| Binary-to-Gray conversion | \( g = b \oplus (b \gg 1) \); the inverse is a prefix XOR computable in logarithmic parallel time<sup>[4](https://aggregate.ee.engr.uky.edu/MAGIC/)</sup> |
| Graph interpretation | An n-bit Gray code corresponds to a Hamiltonian cycle on an n-dimensional hypercube<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup> |
| Main applications | Absolute rotary encoders, flash ADC metastability reduction, asynchronous clock-domain crossing, and Karnaugh map labeling<sup>[3](https://www.ia.omron.com/support/faq/answer/34/faq00941/)</sup><sup> • </sup><sup>[5](https://www.analog.com/en/resources/technical-articles/2022/07/16/07/24/understanding-flash-adcs.html)</sup><sup> • </sup><sup>[6](https://docs.amd.com/r/en-US/ug574-ultrascale-clb/Asynchronous-Clock-Domain-Crossing)</sup> |

## The single-bit property

In ordinary binary counting, a carry can flip many bits at once: moving from 3 to 4 changes 011 to 100, three bits at a stroke.<sup>[7](https://www.ituonline.com/tech-definitions/what-is-gray-code/)</sup> If a reader samples the bits while several are in transition, it can catch a mixture of old and new values and produce a number far from either. With a Gray code only one bit is ever in doubt, so a reading taken at any instant is either the old value or the new one, never a third value.<sup>[8](https://control.com/technical-articles/an-introduction-to-gray-code-for-encoders)</sup> According to the NIST Dictionary of Algorithms and Data Structures, this matters for mechanical encoders: under an ordinary binary code as many as n bits may flip between successive values, so small misalignments among the sensing elements can yield drastically wrong readings.<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup>

## The binary reflected Gray code

The construction that carries Gray's name is recursive. Writing \( \mathcal{C}(n) \) for the n-bit list, the rule is

\[ \mathcal{C}(n) = \mathcal{C}(n-1) \cdot 0 \; \circ \; \overline{\mathcal{C}(n-1)} \cdot 1, \]

where the dot appends a bit to every string, the circle concatenates two lists, and the overbar reverses the list; \( \mathcal{C}(0) \) is the empty string.<sup>[9](https://encyclopediaofmath.org/index.php?title=Gray_code)</sup> This gives \( \mathcal{C}(1) = 0, 1 \), \( \mathcal{C}(2) = 00, 10, 11, 01 \), and \( \mathcal{C}(3) = 000, 100, 110, 010, 011, 111, 101, 001 \).<sup>[9](https://encyclopediaofmath.org/index.php?title=Gray_code)</sup>

Conversion between the two representations is cheap. The Kth Gray code word is \( K \oplus (K \gg 1) \), where \( \oplus \) is bitwise exclusive-or.<sup>[4](https://aggregate.ee.engr.uky.edu/MAGIC/)</sup> Going back from Gray to binary is a linear sequence of XORs, equivalent to a parallel prefix XOR; for 32-bit values it takes five shift-and-XOR steps (shifts of 16, 8, 4, 2, and 1).<sup>[4](https://aggregate.ee.engr.uky.edu/MAGIC/)</sup> Polynomial-time algorithms exist for conversion between binary numbers and certain Gray codes generally.<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup>

The code is not weighted: unlike binary, a bit's column does not carry an implicit place value, so a Gray word read as a binary number has no direct arithmetic meaning.<sup>[10](https://www.allaboutcircuits.com/technical-articles/gray-code-basics/)</sup> A controller that receives Gray-coded position data converts it to binary before doing arithmetic.<sup>[8](https://control.com/technical-articles/an-introduction-to-gray-code-for-encoders)</sup>

## History

The single-bit-change idea predates Gray's patent. A Gray code was used in a telegraph demonstrated by the French engineer [Émile Baudot](https://www.edgepedia.org/emile-baudot) in 1878, and Baudot had patented his rapid telegraph in 1874.<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup><sup> • </sup><sup>[11](https://baudotsystems.co/blog/what-the-telegraph-knew/)</sup> Gray's 1947 patent application addressed pulse code transmission, in which the instantaneous amplitudes of a message are sampled and each sample is translated into a group of on-or-off pulses.<sup>[2](https://patents.google.com/patent/US2632058A/en)</sup> The patent's stated object was to reduce coding errors: with a conventional binary coding mask, a small wander of the electron beam from one aperture row to the row above or below could produce a coding error far greater than the beam deflection error, whereas the rearranged code keeps the error never greater than the deflection error.<sup>[2](https://patents.google.com/patent/US2632058A/en)</sup> The patent also claimed simpler mask manufacture, since the least-significant-column apertures could be made twice as large as in a binary mask.<sup>[2](https://patents.google.com/patent/US2632058A/en)</sup>

## Applications

**Rotary encoders.** In an absolute encoder, a disk patterned with light and dark marks is read by a row of 8 to 10 sensors, and the controller must read them all at once to get position.<sup>[8](https://control.com/technical-articles/an-introduction-to-gray-code-for-encoders)</sup> If the disk pattern followed plain binary, several sensors could transition together and a staggered read could return a value half old and half new, interpreted as motion to a distant position; with Gray code the controller can only read the value just before or just after the single bit change.<sup>[8](https://control.com/technical-articles/an-introduction-to-gray-code-for-encoders)</sup> Encoder manufacturer Omron summarizes the advantage the same way: because only one bit changes, no read-timing strobe is needed and the code reads steadily compared with binary or BCD.<sup>[3](https://www.ia.omron.com/support/faq/answer/34/faq00941/)</sup> Quadrature encoders, the two-channel incremental type common on knobs, are themselves a 2-bit Gray code, which is why a genuine quadrature output never switches both channels at the same instant.<sup>[12](https://industrialmonitordirect.com/blogs/knowledgebase/troubleshooting-incremental-encoder-quadrature-signal-errors)</sup>

**Analog-to-digital conversion.** In flash ADCs, comparator outputs can be ambiguous, a condition called metastability; Gray-code encoding, which allows only 1 bit in the output to change at a time, can greatly improve metastability.<sup>[5](https://www.analog.com/en/resources/technical-articles/2022/07/16/07/24/understanding-flash-adcs.html)</sup> Later patents built encoders that are additionally immune to bubble errors, in which spurious comparator patterns pass through the encoder.<sup>[13](https://patents.google.com/patent/US6388602B1/en)</sup>

**Clock domain crossing.** When a counter must be read by logic running on a different, asynchronous clock, each bit of a multi-bit bus is subject to metastable capture. Gray-coding the counter means the destination domain, sampling through register synchronizers, can only see the old or the new count, never a mixture; for general multi-bit buses, which lack this structure, the recommended practice is an independent-clock (dual-clock) FIFO.<sup>[6](https://docs.amd.com/r/en-US/ug574-ultrascale-clb/Asynchronous-Clock-Domain-Crossing)</sup>

**Karnaugh maps.** A Karnaugh map arranges a truth table as a grid whose rows and columns are labeled in Gray-code order, so that any two adjacent cells, including cells across the left-right and top-bottom wraparound, differ in exactly one input variable; this adjacency is what lets equal product terms be grouped and simplified visually.<sup>[14](https://ocw.mit.edu/courses/6-004-computation-structures-spring-2017/pages/c4/c4s1/)</sup><sup> • </sup><sup>[15](https://university.kurz.fyi/computer-science/computer/digital-logic-computer-organization/karnaugh-maps-and-boolean-simplification)</sup>

## Variants and generalizations

Gray codes for 4 or more bits are not unique, even allowing for permutation or inversion of bits.<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup> A full n-bit cyclic code has \( 2^{n} \) entries, but an application may need fewer; a patented method generates cyclic codes with \( 2k \) entries for any \( 2^{n-1} < 2k < 2^{n} \) by selecting \( k \) ordered entries from each half of the full reflected code.<sup>[16](https://patents.google.com/patent/US6970113B1/en)</sup>

The idea extends beyond bitstrings. A combinatorial Gray code, a term introduced in 1980, is a listing of a class of combinatorial objects, each appearing exactly once, in which consecutive objects differ by a small prespecified change; such listings are known for bitstrings, combinations, permutations, partitions, triangulations, and graph-defined objects such as spanning trees and perfect matchings.<sup>[17](https://www.combinatorics.org/ojs/index.php/eljc/article/view/ds26)</sup> In graph theory, an n-bit Gray code corresponds to a [Hamiltonian cycle](https://www.edgepedia.org/hamiltonian-cycle) on the n-dimensional hypercube, and snake-in-the-box and coil-in-the-box codes are Gray-code-related structures studied for single-bit error detection.<sup>[1](https://xlinux.nist.gov/dads/HTML/graycode.html)</sup><sup> • </sup><sup>[10](https://www.allaboutcircuits.com/technical-articles/gray-code-basics/)</sup> Gray coding of data buses has also been applied to reduce switching noise and crosstalk in network-on-chip interconnects.<sup>[18](https://technav.ieee.org/topic/reflective-binary-codes/)</sup>

## References

1. [Gray code, NIST Dictionary of Algorithms and Data Structures](https://xlinux.nist.gov/dads/HTML/graycode.html)
2. [Frank Gray, "Pulse Code Communication", U.S. Patent 2,632,058, Google Patents](https://patents.google.com/patent/US2632058A/en)
3. [FAQ00941: What is the feature of the Gray code?, OMRON Industrial Automation](https://www.ia.omron.com/support/faq/answer/34/faq00941/)
4. [The Aggregate Magic Algorithms, University of Kentucky](https://aggregate.ee.engr.uky.edu/MAGIC/)
5. [Understanding Flash ADCs, Analog Devices](https://www.analog.com/en/resources/technical-articles/2022/07/16/07/24/understanding-flash-adcs.html)
6. [Asynchronous Clock Domain Crossing, UG574, AMD](https://docs.amd.com/r/en-US/ug574-ultrascale-clb/Asynchronous-Clock-Domain-Crossing)
7. [What Is Gray Code?, ITU Online IT Training](https://www.ituonline.com/tech-definitions/what-is-gray-code/)
8. [An Introduction to Gray Code for Encoders, control.com Technical Articles](https://control.com/technical-articles/an-introduction-to-gray-code-for-encoders)
9. [Gray code, Encyclopedia of Mathematics](https://encyclopediaofmath.org/index.php?title=Gray_code)
10. [Gray Code Basics, All About Circuits Technical Articles](https://www.allaboutcircuits.com/technical-articles/gray-code-basics/)
11. [What the telegraph knew, Baudot Systems](https://baudotsystems.co/blog/what-the-telegraph-knew/)
12. [Fix Incremental Encoder A/B Channel Simultaneous Edge Errors, Industrial Monitor Direct](https://industrialmonitordirect.com/blogs/knowledgebase/troubleshooting-incremental-encoder-quadrature-signal-errors)
13. [US6388602B1: Bubble and meta-stability error immune gray-code encoder, Google Patents](https://patents.google.com/patent/US6388602B1/en)
14. [Computation Structures, Lecture 4.1 annotated slides, MIT OpenCourseWare](https://ocw.mit.edu/courses/6-004-computation-structures-spring-2017/pages/c4/c4s1/)
15. [Karnaugh Maps and Boolean Simplification, Digital Logic & Computer Organization](https://university.kurz.fyi/computer-science/computer/digital-logic-computer-organization/karnaugh-maps-and-boolean-simplification)
16. [US6970113B1: Method for generation of even numbered reduced Gray codes, Google Patents](https://patents.google.com/patent/US6970113B1/en)
17. [Torsten Mütze (2023). Combinatorial Gray Codes — an Updated Survey. The Electronic Journal of Combinatorics, Dynamic Survey DS26.](https://www.combinatorics.org/ojs/index.php/eljc/article/view/ds26)
18. [Reflective binary codes, IEEE Technology Navigator](https://technav.ieee.org/topic/reflective-binary-codes/)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Arithmetic and number systems › Computational arithmetic › Redundant and modular computer number systems*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license