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