Gray code

From Computer History Wiki
Jump to: navigation, search

A Gray code (named after their inventor) is a coding system in which 'neighbour' codes only differ in one bit. In a classic binary code, many transitions from one value to the next involve multi-bit changes; e.g. going from 3 (011) to 4 (100) involves changes in all three bits.

As an example, here is the simplest three-bit Gray code (note that the transition from value 07, counting up and wrapping around to 00, also changes only one bit):

Value Code
00 000
01 001
02 011
03 010
04 110
05 111
06 101
07 100

Gray codes are sometimes called 'reflected' codes, since the values in one half of the code table are (except for the high bit) a mirrored reversal of those in the other half (e.g. above, the code for 04 is a reflection of that for 03, 05 for 02, etc).

The multiple bit changing behaviour of a classic binary code can be an issue when one is used, for example, in a state machine: when using a counter to hold the state, if the binary-coded state is fed into combinatorial circuitry, the output bits do not all change at the exact same instant. So (to give a concrete instance), the counter output might very briefly display 7 (111) in the process of going from 3 (011) to 4 (100). The combinatorial circuity might therefore produce glitches on its output during the brief period when a false intermediate outputs are present.

Gray codes have other uses too, though - for example in transmission codings.