-
Notifications
You must be signed in to change notification settings - Fork 76
/
gray_code.pi
74 lines (54 loc) · 1.72 KB
/
gray_code.pi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/*
Gray code in Picat.
From Rosetta Code:
http://rosettacode.org/wiki/Gray_code
"""
Gray code
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).
There are many possible Gray codes. The following encodes what is called "binary
reflected Gray code."
Encoding (MSB is bit 0, b is binary, g is Gray code):
if b[i-1] = 1
g[i] = not b[i]
else
g[i] = b[i]
Or:
g = b xor (b logically right shifted 1 time)
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]
"""
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import util.
import cp.
main => go.
go =>
foreach(I in 0..2**5-1)
G = gray_encode1(I),
E = gray_decode1(G),
println([I,I.to_binary_string(), G, G.to_binary_string(),E.to_binary_string(), E])
end,
nl,
N2=2**300,
G2=gray_encode1(N2),
E2=gray_decode1(G2),
println([N2,G2,E2,cond(N2==E2,same,not_same)]),
nl.
gray_encode1(N) = N ^ (N >> 1).
gray_decode1(N) = P =>
P = N,
N := N >> 1,
while (N != 0)
P := P ^ N,
N := N >> 1
end.