Essays/Gray Code

Gray code encodes integers as boolean lists so that code words for adjacent numbers differ by 1 bit. For example, the 4-bit encodings of 7 and 8 are:

0 1 0 0
1 1 0 0

The 2^n Gray codes of length n can be computed as follows:

   G=: 3 : '(0&,. , 1&,.@|.)^:y i.1 0'

   G&.> 2 3 4
┌───┬─────┬───────┐
│0 0│0 0 0│0 0 0 0│
│0 1│0 0 1│0 0 0 1│
│1 1│0 1 1│0 0 1 1│
│1 0│0 1 0│0 0 1 0│
│   │1 1 0│0 1 1 0│
│   │1 1 1│0 1 1 1│
│   │1 0 1│0 1 0 1│
│   │1 0 0│0 1 0 0│
│   │     │1 1 0 0│
│   │     │1 1 0 1│
│   │     │1 1 1 1│
│   │     │1 1 1 0│
│   │     │1 0 1 0│
│   │     │1 0 1 1│
│   │     │1 0 0 1│
│   │     │1 0 0 0│
└───┴─────┴───────┘

Gray codes and the binary representations are closely related: The binary representations of n bits can be computed similarly, and one can be transformed into the other readily:

   B=: 3 : '(0&,. , 1&,.)^:y i.1 0'

   (B ; G) 3
┌─────┬─────┐
│0 0 0│0 0 0│
│0 0 1│0 0 1│
│0 1 0│0 1 1│
│0 1 1│0 1 0│
│1 0 0│1 1 0│
│1 0 1│1 1 1│
│1 1 0│1 0 1│
│1 1 1│1 0 0│
└─────┴─────┘

   (B 3) -: ~:/\"1 G 3
1
   (G 3) -: ~:/\^:_1"1 B 3
1

B can also be expressed as #:@i.@(2&^)

   (B -: #:@i.@(2&^)) 8
1

B and G are related in self-similar manner:

'dot;title B i. G'plot (B i. G) 10

Comparatively, binary base spectra of G and B look like this:

   viewmat (|:G 8);'G 8'
   viewmat (|:B 8);'B 8'

---

See also

MathWorld

---

Contributed by Roger Hui, with further contributions by Oleg Kobchenko.