Code Gray

The reflected binary code or Gray code, named after researcher Frank Gray, is a binary numbering system in which two consecutive numbers differ by only one of its digits.

The Gray code was originally designed to prevent illegal signals (false signals or misrepresentation) from electromechanical switches, and is currently used to facilitate error correction in communications systems, such as some cable television systems. cable and digital terrestrial television.

000
001
011
010
110
111
101
100

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
Dorotheergasse
1011
1001
1000

Code Gray

Bell Laboratories researcher Frank Gray invented the term reflected binary code when he patented it in 1947, remarking that it "had no recognized name yet". He created the name based on the fact that the code "can be constructed from conventional binary code by a sort of "reflective process"".

The code was later called "Gray" by other researchers. Two patents in 1953 gave an alternative name "Gray's code" for "reflected binary code"; one of them also refers to the code as "minimum error code" (minimum error code) and as "cyclic permutation code" (cyclic permutation code).

History and practical applications

Reflected binary code was applied to mathematical puzzles before being used for engineering. The French engineer Émile Baudot gave an application to the Gray code in 1878 in telegraphy, work for which he was awarded the Legion of Honor.

The Gray code is sometimes incorrectly attributed to Elisha Gray (in Principles of Pulse Code Modulation, K. W. Cattermole, for example).

Until the first half of the 1940s, digital logic circuits were made with vacuum tubes and electromechanical devices. The counters required very high input powers and generated noise spikes when several bits changed simultaneously. With this in mind, Frank Gray devised a method for converting analog signals to groups of reflected binary code using an apparatus designed with vacuum tubes, thus ensuring that any transition would vary by only one bit.

Currently, the Gray code is used as part of the design algorithm for Karnaugh maps, which are, in turn, used as a "design tool" in the implementation of combinational circuits and sequential circuits. The validity of the Gray code is due to the fact that an efficient digital design will require simpler and faster transitions between logical states (0 or 1), which is why it persists in its use, despite the fact that noise and power problems have been resolved. reduced with the technology of solid state of the integrated circuits.

Using the Gray code it is also possible to solve the problem of the Towers of Hanoi. You can even form a Hamiltonian cycle or a hypercube, in which each bit can be seen as a dimension.

Due to the Hamming distance properties of the Gray code, it is sometimes used in genetic algorithms.

Motivation

Old computers indicated positions by opening and closing switches. Using three switches as inputs using Base 2, these two positions would be one after the other:

001
011
100
101

The problem with base 2 binary code is that with mechanical switches, it's really hard to get all the switches to toggle at the same time. In the transition of the two states shown above, three switches change places. In the time that the switches are flipping, spurious information outputs can occur. If the mentioned outputs feed a sequential circuit, the system will probably present a data entry error.

The gray code solves this problem by changing only one digit at a time, so there is no such problem:

Decimal Gray Binario
0 000 000
1 001 001
2 011 010
3 010 011
4 110 100
5 111 101
6 101 110
7 100 111

Keep in mind that to convert from binary to Gray the values that must be added in base 2 take the following values 1+1=0, 0+0=0, 1+0=1 and 0+1= 1; this operation vertically as shown in the following example:

Dorotheergasse
1010----
1111

Note that from 7 it could go to 0 with a single switch change (the most significant one goes to zero). This is the property called "cyclic" from Gray's code.

Conversions

Base 2 to Gray

To convert a binary number (in Base 2) to Gray code, simply XOR it with the same number shifted one bit to the right, regardless of the carry.

Example: 1010 (Base 2) to gray

Dorotheergasse
1010----
1111

Other examples 0111(Base 2) to gray:

0111
0111----
0100

1101010001
110101010001-...
101111001

Gray to Base 2

We define a vector ${displaystyle g}$ containing the digits in gray and another vector ${displaystyle b}$ to contain digits in Base 2

• ${displaystyle g_{0}}$ is the digit found at the left end of the representation in gray code

• ${displaystyle b_{0}}$ is the highest weight digit and is at the left end on the representation at Base 2

Then it turns out: ${displaystyle b_{n+1}={g_{n+1}}oplus {b_{n}}}}$ except that ${displaystyle b_{0}=g_{0}}}$which can be summarized as:

ExampleWith the number ${displaystyle g=1001}$ Gray code.

The first thing is to say: ${displaystyle b_{0}=g_{0}}}$So for this case: ${displaystyle b_{0}=1}$. Then following with the algorithm: ${displaystyle b_{n+1}={g_{n+1}}oplus {b_{n}}}}$ Turns out:
${displaystyle b_{0}=g_{0}=1}$
${displaystyle b_{1}={g_{1}}oplus {b_{o}=0oplus 1=1}$
${displaystyle b_{2}={g_{2}}oplus {b_{1}=0oplus 1=1}$
${displaystyle b_{3}={g_{3}}oplus {b_{2}=1oplus 1=0}$

This results ${displaystyle b=1110}$