Gray-Code

The Gray code is a continuous code, in which adjacent code words differ only in a single dual digit. The Hamming distance of all neighboring code words is therefore the first result, the maximum possible reading errors is reduced in quantization of an analog signal to a code. It serves as a coding method for robust transmission of digital over analog signal paths sizes. The code is named after the physicist Frank Gray, who in 1953 was granted a patent on this process.

Most of the Gray code is designed as a binary code, but may also be used for multi-level transmission routes.

  • 3.1 problem with binary code signals
  • 3.2 solution with Gray code
  • 3.3 Karnaugh - Veitch - Diagram

Generation of binary code

Logical Operators

The following points show how to get a Gray - coded binary step by step from a binary-coded decimal ( binary code):

  • X1: binary number in binary code
  • X2: Right shift the binary number by 1 bit
  • X3: Modulo -2 addition ( XOR operation ) of X1 and X2; this is the desired number in the Gray code.

The same as the pseudo code:

  • Binary code X1 → Gray Code: X3 = (X1 XOR X2)

Generator matrix

Since the Gray code is a linear code, it can be generated with a generator matrix. A binary word of length can be regarded as a vector -dimensional vector space. Let now a row vector, then allows the encoding of the word in the code word represented as follows:

The decoding is done with the multiplication of the inverse of. This has the following form:

The vector space can be represented graphically with hypercubes.

Generating as a Gray counter

One can also directly program a Gray - code counter in hardware ( for example in the HDL). For this purpose, it is useful to use an auxiliary register which toggles with each clock cycle.

Qh [n 1 ] =! Qh [n ]

This combinatorics is quite clear:

Q0 [ n 1] =! (Q0 [n ] ^ Qh [n])

Q1 [n 1] = Q 1 [n ] ^ (Q0 [n] and Q h [n])

Q2 [n 1] = Q 2 [n ] ^ (Q1 [n ] &! Q0 [ n] and Q h [n])

Q3 [n 1] = Q 3 [n ] ^ (Q2 [n ] &! Q1 [n ] &! Q0 [ n] and Q h [n])

...

Qk -1 [n 1] = Q k -1 [n ] ^ ( Qk -2 [n ] &! Qk -3 [n] & ... &! Q1 [n ] &! Q0 [n ] & Qh [ n])

Qk [n 1] = Q k [n ] ^ (? Qk -1 [n ] &! Qk -2 [n] & ... &! Q1 [n ] &! Q0 [ n] and Q h [n])

^: = Exclusive OR / XOR / non-equivalence! : = Inverter / NOT / negation &: = And / AND / Conjunction

Importance

The starting point for this code is the following problem: On several wires of an electrical data line data to be transmitted in parallel, constantly (not abruptly ) change, such as signals from a temperature sensor or a rotary encoder. Theoretically, the bits change at exactly the same time a new value on each affected line, both at the input of the line and at the output. In fact, however, the bits do not change at the same time on the line. This can have several causes: scattering components, run times, unbalance, etc. This leads to unwanted intermediate states:

00 01 11 10 3-bit Gray - code: 000 001 011 010 110 111 101 100 4-bit Gray - code: 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 5-bit Gray - code: 00000 00001 00011 00010 00110 00111 00101 00100 01100 01101 01111 01110 01010 01011 01001 01000 11000 11001 11011 11010 11110 11111 11101 11100 10100 10101 10111 10110 10010 10011 10001 10000 6-bit Gray - code: 000000 000001 000011 000010 000110 000111 000101 000100 001100 001101 001111 001110 001010 001011 001001 001000 011000 011001 011011 011010 011110 011111 011101 011100 010100 010101 010111 010110 010010 010011 010001 010000 110000 110001 110011 110010 110110 110111 110101 110100 111100 111101 111111 111110 111010 111011 111001 111000 101000 101001 101011 101010 101110 101111 101101 101100 100100 100101 100111 100110 100010 100011 100001 100000 Problem with binary code signals

While the theoretical signal in the order

  • { 0000 }, { 0001 }, { 0010 }, { 0011 }, { 0100 }, { 0101 }, { 0110 }, { 0111 }, etc.

Is sent, at the output side briefly other signal states:

  • { 0000 }, { 0001 }, { 0000 }, { 0010 }, { 0011 }, { 0100 }, { 0101 }, { 0111 }, { 0110 }, { 0111 }, etc.

Solution with Gray code

To avoid this, the control signal states are sent in a sequence by means of a Gray code where only one bit is always the same:

  • Dispatches sequence: { 0000 } {0001 } { 0011 } { 0010 } { 0110 } { 0111 } { 0101 } { 0100 }, etc.
  • Incoming sequence: { 0000 }, { 0001 }, { 0011 }, { 0010 }, { 0110 }, { 0111 }, { 0101 }, { 0100 }, etc.

So here at the output of the same sequence as the input.

Karnaugh - Veitch - Diagram

In the Karnaugh - Veitch -diagram recognizes the Gray code - there are several possible sequences - the fact that transitions occur only between ( horizontally or vertically ) adjacent fields.

The code is also suitable for cyclic applications such as the disk as shown below, since the zero change only one place also in the transition from the highest number.

The value of a 1 at the position in the Gray code number system (where n is counted from 1, so ... 31, 15, 7, 3, 1). The individual ones, as opposed to normal binary system, is not added, but subtracted from the right. Example: 111Gray = 7 - ( 3 - 1 ) = 5 or 1111Gray = 15 - ( 7 - (3 - 1)) = 10 points, of which 0 are omitted here, for example: 101Gray = 7 - 1 = 6

In the generation of a Gray code, the procedure is symmetrical.

Because different adjacent values ​​in only one digit, the Gray code is placed to detect errors in serial processes.

Hypercube

Figure 1 shows the hypercube for 3 variables and Figure 2 the same cube with associated coordinate system. The node ( vertex or circles ) on the Hyper- unit cube correspond to a line in the Gray code. The transitions ( the vicinity of the lines) are represented by the edges of the cube. While hiking on the edge produces a Gray code.

On each edge changes exactly 1 bit. Of the Gray code is so much neighborhoods, such as dice has edges. The possible paths can be traversed on 6 different ways from the hypercube in Figure 1. Thus a maximum of 6 ways to generate a 3-bit Gray code, the conditions of the Gray code satisfies (Table and Figure 3). Apart from that the Gray code is cyclical and the start point may therefore be at a different line. Because of its simple recursive generation specification of the binary reflected Gray code is usually ( binary- reflected Gray code) specified (column " e" - second to last column in the table). There is a whole class of Gray codes for a specific bit length. There is an n- bit Gray code exactly as much variations as there are Hamilton cycles on an n- dimensional hypercube.

Since the shown here Gray code is cyclical, the code in the column c), d ) and f) in the table was shifted to a position upwardly ( as compared to the Table above), so that each of the three zeros in the last row of the table are. Thus it is evident that it is the Gray code in column a) is only a mirror-image reversal of column b). Same column c), the inversion of column D), while column E) is the inversion of column F). There are three undirected Hamilton cycles in the three-dimensional hypercube, which here only in a different direction (directed Hamilton cycle ) were shown. To better illustrate the code tables for the 6 variants of the 3-bit Gray codes are shown again here. Wherein the variant E represents the binary reflected Gray code, which is usually meant when the gray code is mentioned. The 6 versions can also be obtained by permutation of the three columns of the code table. It follows that n for n bit! Versions out there. So for 3 Bit 3! = 6 versions of the 3-bit Gray code ..

The 4-bit Gray code can be read from the hypercube in Figure 4. For 4-bit, there are 4! = 24 different Gray codes.

Applications

One application is to determine the absolute position of a disk or strip, which is marked with black and white bars which are scanned with light barriers or other sensors. This position is then used for angular or rotational speed measurement.

A further application is the fringe projection. There, a sequence of patterns of parallel stripes is projected onto an object. The number of the strips is Gray -coded and can be calculated by a camera for observing each pixel.

Another application is the asynchronous reading of data. For example, the gray code is used to read the error-free counter readings in correlators. Even in the worst case, if it is read in a single tilting bits, the result is always correct because tipping over a bit is not defined and it also makes up only a difference of ± 1. This type of reading requires no synchronization and very little CPU time.

Other possible applications include wind direction meter or water level gauge, picture of car article in elevators.

The reflected Gray code has a close relationship to the problem of the Towers of Hanoi, and he also describes the approach of the Great Rings.

Example

The decimal number corresponding to the Gray code. The decoded into its decimal representation then follows the rule. When a plurality of ones found in a Gray code number, they will be subtracted from each other: The Gray code is decoded as follows.

General procedure: In a conversion is critical, at which position are the ones. Position has an influence on the calculation. If we look at the number 100, then the fuel is at position 3 (from right to left). The factor for the one you get by considering that decimal can be stored in binary form in a maximum of 3-bit number. In 3-bit binary code, the number 7 (111 ) can be stored for a maximum. Suppose now a larger binary number that works virtually the same way. Binary number: 11010 (1 at position 5,4 and 2). 5-bit binary number: max. 31 4-bit binary number: max. 15 bit binary number 2: max. 3

Calculation:

Count back a Gray code

For I: = numBits - 1 downto 0 do / / every single bit from last to first      = Add Value or ( / / the result of each calculated bits to the overall result: Value        ((( 1 shl (I 1) ), and Value ) shr 1) / / location of the bit in the result above        xor / / xor with        ( (1 shl I) and Gray code) / / the current position of the code                         ); history

Even before the term Gray code was introduced, there was already mathematical puzzle games, in which the principle was applied. Only later did the code found the attention of engineers. By 1878 turned Otto Schaeffler, the Vienna- telegraphs and telephones produced and improved, the reflected Gray code. The Frenchman Jean -Maurice -Émile Baudot used Gray codes in 1887 for electric telegraphy. He received the award of the French Legion of Honour for his work.

However, names factor was Frank Gray, a researcher at Bell Laboratories, who rediscovered the code until 1946 for his purposes. Under the title Pulse Code Communications filed a patent for a Gray encoding electron tube was issued March 17, 1953, U.S. patent number 2,632,058.

278138
de