Binary Gray-Code

Synopsis:

  Gray-Code is a different way of counting. It is very different from most other formats, in that the value represented by a particular digit in a particular column can only be interpreted in association with other digits. This is very different from base 10, or even base 2, where the value of a number is the sum of the values generated independently by each digit in each column. For this reason (and another mentioned later), Gray-Code may be best left for computer interpretation, where algorithms may be run to determine the value. (Simple algorithms are given, below, for converting between Binary-Reflected Gray-Code and conventional Binary numbers. Different forms of Gray-Code require different algorithms.)

  Gray-Codes have an advantage over other number formats when the number is being transmitted over a serial interface as its bits are being updated; or where the bits are being transmitted in parallel where the rise- and fall-time of all outputs and inputs are not absolutely identical, and a data-valid bit is not implemented for any of a variety of reasons; or where the bits are being read in a serial fashion. When counting with a Gray-Code, there is no point at which several bits change. Indeed the salient point about Gray-Codes is: As the value is incremented, or decremented, only one bit changes at a time; The uncertainty in a received value is never greater than the possible change in the value, during the time of transmission. This makes Gray-Codes ideal for transmission of pseudo-analogue data such as gauge readings and indications of position.

The Niche for Gray-Code

  If a decimal number being transmitted is changing from 154 to 156 then the Least Significant Bit (LSB) will be blurred – but one will still see the value is somewhere between 150 and 159. However if there is the same ±1 change about 160 – then only the Most Significant Bit (MSB) of 149 and 151 is invariant, and readable with confidence; and so, one can only be sure the value is between 100 and 199! If the change is from 499 to 601 – then the whole value is uncertain, other than to say it is the range of 100 to 999. Alternatively, if the number is transmitted only once, and the change happens, between the transition of the first and second digit – or the value is read only once, and it changes similarly as it is being read – the value received could be a grossly errored. To continue with the latest example, the number received might be ‘699,’ or ‘401’!

  Similar problems exist with conventional binary data. Gray-Codes, by their nature, have no such problems. Although there are several types of Gray-Codes, each with their own rules of generation, the salient feature of changing only one digit at a time remains. The remainder of this article concentrates on the Binary-Reflected Gray-Code format. In Binary-Reflected Gray-Code the error in reading what starts to be a value of 14, and changes to 15, could – at worst – be the 17; Similarly 24±1 could be read as 22: But nowhere would the error be greater. For comparison, if a binary value of 15 were to change to 16, as it was (serially) transmitted [or read without a data-valid strobe] – the received value could be zero or 31!

Simple rules for the formation of Binary-Reflected Gray-Code:

  (You may also want to consult the Counting in Gray-Code section, further down.)

Basic Rule:

  Zero is represented by all bits being zero. Only one bit changes each time 1 is added or subtracted.

Rule Governing the Lowest Bit:

  The lowest bit toggles state the first and every second time 1 is added. That is: Whenever the number increments to an odd value (or decrements to an even value) – The LSB toggles state. (The next rule controls which bit changes on the counts between; when the number increments to an even value.) Thus the state of the LSB, as the count increments from zero (or any other integral multiple of four), is: 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, ….

Rule Governing the Higher Bits:

  All except the lowest bit are formed by this rule that is based on the bit one lower than the one in question. (For simplicity, this rule is written to apply to incrementing by one.) The bit toggles state half way between the 0-1 and 1-0 toggles of the bit one lower. Thus, each bit toggles state at half the frequency of the next bit lower, and changes (on counting up) only when that bit is high (i.e.: is set; is 1; etc.). This fills in half the gaps left by the toggling of the lower bits; and leaves gaps (in the middle of their string of zeros), to be filled by the toggling of higher bits.

Example:

  The following displays a 5-bit grey code counting according to the above rules.
   Blue (   ) table borders highlight the bits that differ between adjacent values.
   Green (   ) borders highlight the ends of the MSB row, whereat there would be change on roll-over.

NOTES:

• If the table were to be extrapolated to six or more bits, then the green (   ) highlights at the left and right ends of the MSB row belong at the ends of the new MSB row; and there would be no bit-state change where the green highlights are at present.
  • Briefly: On adding each row, the existing pattern is reflected about its right end, and the new row is: ‘0’ under the original; ‘1’ under the reflection.
• As with conventional binary numbers, ignoring the state of lower order bits does not delete vital data; it only reduces the precision by (2n) where n = number of bits not processed.
  • [By this formula, if zero bits are ignored, the precision is 20 = 1, or ±0.5, exactly the result we get from rounding.]
• As with conventional binary numbers: Using five bits one can count from zero to 31.
• Unlike conventional [five-digit] binary numbers, the value 11111 is not the maximum value (31), but is 21 – approximately two thirds of the maximum value.
  • Similarly, where there are more (or fewer) bits used, all ‘1’s is approximately two thirds of the maximum value.
• The pattern exhibited by the state of the bits, excluding the state of the highest bit, is mirrored around the half-value point.
  • In the example, compare 15 & 16, 14 & 17, 13 & 18, … 0 & 31, wherein the only difference in each pair is the state of the highest bit.)
• The maximum value which can be represented (as limited by the number of bits being used), produces a bit-pattern that will wrap to zero on the toggling of the MSB.
  • (The highest value possible, with any number of digits, is “1 0 0…0 0”.)
• Since each increment of value is performed by toggling of exactly one bit: The number of bits which are set alternates between even and odd on every count.
  • Since zero is represented by all zeros, the parity of the number of bits which are set is the same as the parity of the value represented.

Observations:

• The lowest bit changes state, every second count.
• Each bit, except the highest [and lowest], is ON, and OFF for twice as long as the bit one lower than it; and changes state mid-way through the ON period of that bit, one lower.
• The highest two bits (but no other pair) count in quadrature.

Algorithms to Convert between Binary-Reflected Gray-Code and Conventional Binary:

To convert from Gray-Code to Binary:

  Start at the MSB, and then work towards the LSB.

• MSB: Copy the bit.
• Other Bits (commencing from the one below MSB, and progressing to the LSB):
  • If the bit solved for in the previous step is reset (zero, low, etc.):
  • Then the value of this output bit is the same as the bit being processed;
  • Else: Invert it.

To convert from Binary to Gray-Code:

  This conversion may be done in either direction.

• MSB: Copy the bit.
• Other Bits (which may be processed in any order):
  • If, in the input word, the bit above the bit being processed is reset (zero, low, etc.):
  • Then the value of the output bit is the same as the bit being processed;
  • Else: Invert it.

Math Functions in Gray-Code:

  Recall that the forte of Gray-Code lies in its transmissibility, not in its processability. It is designed for being incremented and decremented, and the rules for that are relatively simple. The rules for doubling a value are relatively simple, and are given below; but for most other processing of values, one is probably best off converting to a conventional number system (using the algorithm above), and using the conventional algorithms to perform the math (and then converting back, if re-transmission is needed).

  Whereas ‘Add One,’ in binary can be reduced to one simple rule (• Start at the LSB, and toggle the state of every bit, proceeding until a ‘RESET-to-SET’ transition is made; At which point one is done) – In Gray-Code one operates on the the lowest bit which has an even number of SET bits at, and to the left of, its position. Thus:

• Evaluate the number of bits which are SET – to determine if one is incrementing an even number to an odd number, or incrementing an odd number to an even number.
  • If there is an EVEN number of bits set; To Increment an even number:
    • FLIP the state of the LSB; End of routine.
  • If there is an ODD number of bits set; To Increment an odd number:
    • Move LEFT to operate on the bit immediately above the lowest bit which is set,
    • Flip that bit; End of routine.

  To subtract one:

• To subtract one from an ODD number: Toggle the state of the LSB.
• To subtract one from an EVEN number: Skip to the bit above the least significant one which is set – and toggle its state.

Multiplying in Binary-Reflected Gray-Code:

  Whereas ‘Multiply by 2,’ in binary, is a simple Bit-Shift-Left – In Gray-Code:

• For EVEN numbers (numbers with an even number of bits set) – the same rule applies;
• For ODD numbers – Bit-Shift-Left, and SET the LSB [so that the number just created has an EVEN number of bits set, and is therefore an even number].

  An alternative wording to the above is:

• Bit-Shift-Left;
• If the number of Set bits is not even: SET the LSB.

And thus, to divide by two – provided the number has an even number of bits set:

• Discard the lowest bit, and Bit-Shift-Right.

Adding in Binary-Reflected Gray-Code:

  Whereas adding, in binary, is just like adding in base 10 (with the need to carry being very much more prevalent) – in Gray-Code (as was stated above), maybe one should not try it, except as:

• Iterate the following until what is to be added is reduced to zero:
  • Add one to the result, and subtract one from what is still to be added.

Copyright

This material is Copyright (© 1999, through 2013), Robert W. C. Stevens. Reproduction, with this copyright notice intact, is permitted – but sharing the URL would save a tree, and probably make more sense.