Gray code: Difference between revisions

Revision as of 02:13, 10 March 2025

Revision as of 02:17, 10 March 2025

Line 32:

[[File:Reflected binary Gray 2632058.png|thumb|Gray's patent introduces the term "reflected binary code"]]

In principle, there can be more than one such code for a given word length, but the term Gray code was first applied to a particular [[binary numeral system|binary]] code for non-negative integers, the ''binary-reflected Gray code'', or '''BRGC'''. [[Bell Labs]] researcher

[[George R. &nbsp;Stibitz]] described such a code in a 1941 patent application, granted in 1943.<ref name="Stibitz_1941"/><ref name="Winder_1959"/><ref name="Knuth_2014"/> [[Frank Gray (researcher)|Frank Gray]] introduced the term ''reflected binary code'' in his 1947 patent application, remarking that the code had "as yet no recognized name".<ref name="Gray_1947"/> He derived the name from the fact that it "may be built up from the conventional binary code by a sort of reflection process".

In the standard encoding of the Gray Code the least significant bit follows a repetitive pattern of 2 on, 2 off {{nowrap|(... {{mono|11001100}} ...);}} the next digit a pattern of 4 on, 4 off; the ''i''-th least significant bit a pattern of 2^''i'' on 2^''i'' off. The most significant digit is an exception to this: for an ''n''-bit Gray code, the most significant digit follows the pattern 2^''n''-1 on, 2^''n''-1 off, which is the same (cyclic) sequence of values as for the second-most significant digit, but shifted forwards 2^''n''-2 places. The four-bit version of this is shown below:

[[File:Gray_code_tesseract.svg|thumb|Visualized as a traversal of [[Vertex (graph theory)|vertices]] of a [[tesseract]]]]

[[File:Gray code number line arcs.svg|thumb|Gray code along the number line]]

In the standard encoding of the Gray Codecode the least significant bit follows a repetitive pattern of 2 &nbsp;on, 2 &nbsp;off {{nowrap|(... {{mono|11001100}} ...);}} the next digit a pattern of 4 &nbsp;on, 4 &nbsp;off; the ''i''-th least significant bit a pattern of 2^''i'' &nbsp;on 2^''i'' &nbsp;off. The most significant digit is an exception to this: for an ''n''-bit Gray code, the most significant digit follows the pattern 2^''n''-1−1 &nbsp;on, 2^''n''-1−1 &nbsp;off, which is the same (cyclic) sequence of values as for the second-most significant digit, but shifted forwards 2^''n''-2−2 places. The four-bit version of this is shown below:

{| class="wikitable sortable" style="text-align:center;"

|-

! Decimal !! Binary !! Gray

|-