ANEW --GRAYCODE-- \ Wil Baden 2003-02-19
\ *******************************************************************
\ * *
\ * Wil Baden 2003-02-19 *
\ * *
\ * GRAYCODE *
\ * *
\ * A Graycode is a representation of numbers such that the codes *
\ * for a number and its successor differ by one bit. *
\ * *
\ *******************************************************************
There are many ways to define a Graycode, but the following is the
easiest and must common.
: Num>Gray ( n_1 -- n_2 )
dup 1 RSHIFT XOR ;
The inverse is:
: Gray>Num ( n_1 -- n_2 )
dup 1 RSHIFT XOR
dup 2 RSHIFT XOR
dup 4 RSHIFT XOR
dup 8 RSHIFT XOR
dup 16 RSHIFT XOR
( etcetera )
;
Here are the usual Graycodes for numbers 0 through 15.
0000 0110 1100 1010
0001 0111 1101 1011
0011 0101 1111 1001
0010 0100 1110 1000
Note that normal Graycodes reiterate for repeated sequences within a
power of 2, just like the numbers they represent.
0
1
00
01
11
10
000
001
011
010
110
111
101
100
If you take the same number of values from the beginning and end of a
sequence of a power of 2, the cycle will also repeat. Here three
numbers have been taken from the beginning and end of a normal
sequence of 16. This is one way that decimal integers have been
shown in past computers. The values are Graycodes for 3 through 12,
and are used for integers 0 through 9. This is "excess 3 Graycode".
0010 0110 0111 0101 0100 1100 1101 1111 1110 1010
Graycode can also be used to solve Tower of Hanoy and similar puzzles.
Tower of Hanoy is solved by moving the disk corresponding to the
changed bit one way in odd moves, and then the other way in even
moves.
\\ // \\ // \\ // \\ // \\ // \\ // \\ // \\