Essays/Gray Code
< Essays
Jump to navigation
Jump to search
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
Contributed by Roger Hui, with further contributions by Oleg Kobchenko.