1 ! Copyright (c) 2012 Anonymous
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: arrays kernel math math.parser prettyprint ranges sequences ;
4 IN: rosetta-code.gray-code
6 ! http://rosettacode.org/wiki/Gray_code
8 ! Gray code is a form of binary encoding where transitions
9 ! between consecutive numbers differ by only one bit. This is a
10 ! useful encoding for reducing hardware data hazards with values
11 ! that change rapidly and/or connect to slower hardware as inputs.
12 ! It is also useful for generating inputs for Karnaugh maps in
13 ! order from left to right or top to bottom.
15 ! Create functions to encode a number to and decode a number
16 ! from Gray code. Display the normal binary representations, Gray
17 ! code representations, and decoded Gray code values for all 5-bit
18 ! binary numbers (0-31 inclusive, leading 0's not necessary).
20 ! There are many possible Gray codes. The following encodes what
21 ! is called "binary reflected Gray code."
23 ! Encoding (MSB is bit 0, b is binary, g is Gray code):
30 ! g = b xor (b logically right shifted 1 time)
32 ! Decoding (MSB is bit 0, b is binary, g is Gray code):
34 ! b[i] = g[i] xor b[i-1]
36 : gray-encode ( n -- n' ) dup -1 shift bitxor ;
38 :: gray-decode ( n! -- n' )
40 [ n -1 shift dup n! 0 = not ] [
45 : gray-code-main ( -- )
47 dup [ >bin ] [ gray-encode ] bi
48 [ >bin ] [ gray-decode ] bi 4array .