Gray code: Difference between revisions

Revision as of 09:20, 29 February 2024

Revision as of 09:22, 29 February 2024

Line 35:

[[George R. 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 the least significant bit follows a repetitive pattern of 12 on, 12 off {{nowrap|( … {{mono|0101010111001100}} … );}} the next digit a pattern of 24 on, 24 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]]