Gray code

Gray code is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Gray code is a form of binary encoding where transitions between consecutive numbers differ by only one bit. This is a useful encoding for reducing hardware data hazards with values that change rapidly and/or connect to slower hardware as inputs. It is also useful for generating inputs for Karnaugh maps in order from left to right or top to bottom.

Create functions to encode a number to and decode a number from Gray code. Display the normal binary representations, Gray code representations, and decoded Gray code values for all 5-bit binary numbers (0-31 inclusive, leading 0's not necessary).

Encoding (MSB is bit 0, b is binary, g is Gray code):

if b[i-1] = 1
   g[i] = ~b[i]
else
   g[i] = b[i]

Decoding (MSB is bit 0, b is binary, g is Gray code):

b[0] = g[0]

for other bits:
b[i] = g[i] xor b[i-1]

J

G n (from j:Essays/Gray Code) computes the table of all n-bit Gray code values.

<lang j>G=:3 :'(0&,. , 1&,.@|.)^:y i.1 0'</lang>

Example:

<lang j> G 3 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0</lang>

m Gfn derives an invertible function which finds the m-bit Gray code value for a given argument.

<lang j>Gfn=:1 :'{&(G m)'</lang>

Examples:

<lang j> 5 Gfn 8 0 1 1 0 0

  5 Gfns inv 5 Gfns i.8

0 1 2 3 4 5 6 7</lang>

(F inv derives a function which is the inverse of F, if F is an invertible function.)

And, finally:

<lang j> Gray=:G 5

  n=:i.#Gray
  binary=:#:n
  decoded=:5 Gfn inv 5 Gfn n
  (,: ,.@".&.>) ;:'n binary Gray decoded'

+--+---------+---------+-------+ |n |binary |Gray |decoded| +--+---------+---------+-------+ | 0|0 0 0 0 0|0 0 0 0 0| 0 | | 1|0 0 0 0 1|0 0 0 0 1| 1 | | 2|0 0 0 1 0|0 0 0 1 1| 2 | | 3|0 0 0 1 1|0 0 0 1 0| 3 | | 4|0 0 1 0 0|0 0 1 1 0| 4 | | 5|0 0 1 0 1|0 0 1 1 1| 5 | | 6|0 0 1 1 0|0 0 1 0 1| 6 | | 7|0 0 1 1 1|0 0 1 0 0| 7 | | 8|0 1 0 0 0|0 1 1 0 0| 8 | | 9|0 1 0 0 1|0 1 1 0 1| 9 | |10|0 1 0 1 0|0 1 1 1 1|10 | |11|0 1 0 1 1|0 1 1 1 0|11 | |12|0 1 1 0 0|0 1 0 1 0|12 | |13|0 1 1 0 1|0 1 0 1 1|13 | |14|0 1 1 1 0|0 1 0 0 1|14 | |15|0 1 1 1 1|0 1 0 0 0|15 | |16|1 0 0 0 0|1 1 0 0 0|16 | |17|1 0 0 0 1|1 1 0 0 1|17 | |18|1 0 0 1 0|1 1 0 1 1|18 | |19|1 0 0 1 1|1 1 0 1 0|19 | |20|1 0 1 0 0|1 1 1 1 0|20 | |21|1 0 1 0 1|1 1 1 1 1|21 | |22|1 0 1 1 0|1 1 1 0 1|22 | |23|1 0 1 1 1|1 1 1 0 0|23 | |24|1 1 0 0 0|1 0 1 0 0|24 | |25|1 1 0 0 1|1 0 1 0 1|25 | |26|1 1 0 1 0|1 0 1 1 1|26 | |27|1 1 0 1 1|1 0 1 1 0|27 | |28|1 1 1 0 0|1 0 0 1 0|28 | |29|1 1 1 0 1|1 0 0 1 1|29 | |30|1 1 1 1 0|1 0 0 0 1|30 | |31|1 1 1 1 1|1 0 0 0 0|31 | +--+---------+---------+-------+</lang>

Java

This example encodes using shifts, bitwise operations, and summing into the result. It decodes using Strings. <lang java>public class Gray { public static long grayEncode(long n){ long result = 0; for(int exp = 0; n > 0; n /= 2, exp++){ long nextHighestBit = (n >> 1) & 1; if(nextHighestBit == 1){ result += ((n & 1) == 0) ? (1 << exp) : 0; //flip the bit }else{ result += (n & 1) * (1 << exp); //"n & 1" is "this bit", don't flip it } } return result; }

public static long grayDecode(long n){ String nBits = Long.toBinaryString(n); String result = nBits.substring(0, 1); for(int i = 1; i < nBits.length(); i++){ //bin[i] = gray[i] ^ bin[i-1]

//XOR with characters result += nBits.charAt(i) != result.charAt(i - 1) ? "1" : "0"; } return Long.valueOf(result, 2); }

public static void main(String[] args){ System.out.println("i\tBinary\tGray\tDecoded"); for(int i = 0; i < 32;i++){ System.out.print(i +"\t"); System.out.print(Integer.toBinaryString(i) + "\t"); System.out.print(Long.toBinaryString(grayEncode(i))+ "\t"); System.out.println(grayDecode(grayEncode(i))); } } }</lang> Output:

i	Binary	Gray	Decoded
0	0	0	0
1	1	1	1
2	10	11	2
3	11	10	3
4	100	110	4
5	101	111	5
6	110	101	6
7	111	100	7
8	1000	1100	8
9	1001	1101	9
10	1010	1111	10
11	1011	1110	11
12	1100	1010	12
13	1101	1011	13
14	1110	1001	14
15	1111	1000	15
16	10000	11000	16
17	10001	11001	17
18	10010	11011	18
19	10011	11010	19
20	10100	11110	20
21	10101	11111	21
22	10110	11101	22
23	10111	11100	23
24	11000	10100	24
25	11001	10101	25
26	11010	10111	26
27	11011	10110	27
28	11100	10010	28
29	11101	10011	29
30	11110	10001	30
31	11111	10000	31

PicoLisp

<lang PicoLisp>(de grayEncode (N)

  (bin (x| N (>> 1 N))) )

(de grayDecode (G)

  (bin
     (pack
        (let X 0
           (mapcar
              '((C) (setq X (x| X (format C))))
              (chop G) ) ) ) ) )</lang>

Test: <lang PicoLisp>(prinl " Binary Gray Decoded") (for I (range 0 31)

  (let G (grayEncode I)
     (tab (4 9 9 9) I (bin I) G (grayDecode G)) ) )</lang>

Output:

       Binary     Gray  Decoded
   0        0        0        0
   1        1        1        1
   2       10       11        2
   3       11       10        3
   4      100      110        4
   5      101      111        5
   6      110      101        6
   7      111      100        7
   8     1000     1100        8
   9     1001     1101        9
  10     1010     1111       10
  11     1011     1110       11
  12     1100     1010       12
  13     1101     1011       13
  14     1110     1001       14
  15     1111     1000       15
  16    10000    11000       16
  17    10001    11001       17
  18    10010    11011       18
  19    10011    11010       19
  20    10100    11110       20
  21    10101    11111       21
  22    10110    11101       22
  23    10111    11100       23
  24    11000    10100       24
  25    11001    10101       25
  26    11010    10111       26
  27    11011    10110       27
  28    11100    10010       28
  29    11101    10011       29
  30    11110    10001       30
  31    11111    10000       31