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).
Encoding (MSB is bit 0, b is binary, g is Gray code):
if b[i-1] = 1 g[i] = ~b[i] else g[i] = b[i]
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]
D
<lang d>import std.stdio, std.conv ;
T enGray(T)(T n) { return n ^ (n >>> 1) ; } T deGray(T)(T n) {
if(n == 0) return 0 ;
enum T MSB = to!T(1) << (T.sizeof*8 - 1) ;
bool bitSet(T m, uint pos) { return (m & ( MSB >>> pos)) != 0 ; }
// bit pos count from MSB/left
auto posFromMSB = 0 ;
while( !bitSet(n, posFromMSB) )
posFromMSB++ ;
auto res = ( MSB >>> posFromMSB ) ;
foreach(bitPos;posFromMSB + 1 .. T.sizeof*8)
if(bitSet(n, bitPos) != bitSet(res, bitPos - 1))
res += ( MSB >>> bitPos ) ;
return res ;
}
void main() {
writeln("num bits encoded decoded") ;
foreach(i; 0..32) {
auto encoded = enGray(i) ;
writefln("%2d: %5b => %5b : %2d", i, i, encoded, deGray(encoded)) ;
}
}</lang> Output:
num bits encoded decoded 0: 0 => 0 : 0 1: 1 => 1 : 1 2: 10 => 11 : 2 3: 11 => 10 : 3 4: 100 => 110 : 4 5: 101 => 111 : 5 6: 110 => 101 : 6 7: 111 => 100 : 7 8: 1000 => 1100 : 8 9: 1001 => 1101 : 9 10: 1010 => 1111 : 10 11: 1011 => 1110 : 11 12: 1100 => 1010 : 12 13: 1101 => 1011 : 13 14: 1110 => 1001 : 14 15: 1111 => 1000 : 15 16: 10000 => 11000 : 16 17: 10001 => 11001 : 17 18: 10010 => 11011 : 18 19: 10011 => 11010 : 19 20: 10100 => 11110 : 20 21: 10101 => 11111 : 21 22: 10110 => 11101 : 22 23: 10111 => 11100 : 23 24: 11000 => 10100 : 24 25: 11001 => 10101 : 25 26: 11010 => 10111 : 26 27: 11011 => 10110 : 27 28: 11100 => 10010 : 28 29: 11101 => 10011 : 29 30: 11110 => 10001 : 30 31: 11111 => 10000 : 31
This version uses a compile time generated translation table, if maximum bit width of the numbers is a constant. The encoding table is generated recursively, then the decode table is calculated and appended. <lang d>import std.stdio, std.conv, std.algorithm ;
T[] Gray(int N : 1, T)() { return [to!T(0), 1] ; }
T[] Gray(int N, T)() { // recursively generate gray encoding mapping table
assert(N <= T.sizeof*8, "N exceed number of bit of T") ;
enum T M = to!T(2)^^(N-1) ;
T[] g = Gray!(N - 1, T);
foreach(i;0..M)
g ~= M + g[M - i - 1] ;
return g ;
}
T[][] GrayDict(int N, T)() {
T[][] dict = [Gray!(N, T), [0]] ;
foreach(i ; 1..dict[0].length) // append inversed gray encoding mapping
dict[1] ~= countUntil(dict[0], i) ;
return dict ;
}
enum { Encode = 0 , Decode = 1 } ;
T gray(int N, T)(T n, int Mode = Encode) {
enum Dict = GrayDict!(N, T) ; // generated at compile time return Dict[Mode][n] ;
}
void main() {
foreach(i; 0..32) {
auto encoded = gray!(5)(i, Encode) ;
auto decoded = gray!(5)(encoded, Decode) ;
writefln("%2d: %5b => %5b : %2d", i, i, encoded, decoded) ;
} // checked correct ouput
}</lang>
J
G n (from j:Essays/Gray Code) computes the table of all n-bit Gray code values.
<lang j>G=:3 :'(0&,. , 1&,.@|.)^:y i.1 0'</lang>
Example:
<lang j> G 3 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0</lang>
m Gfn derives an invertible function which finds the m-bit Gray code value for a given argument.
<lang j>Gfn=:1 :'{&(G m)'</lang>
Examples:
<lang j> 5 Gfn 8 0 1 1 0 0
5 Gfns inv 5 Gfns i.8
0 1 2 3 4 5 6 7</lang>
(F inv derives a function which is the inverse of F, if F is an invertible function.)
And, finally:
<lang j> Gray=:G 5
n=:i.#Gray binary=:#:n decoded=:5 Gfn inv 5 Gfn n (,: ,.@".&.>) ;:'n binary Gray decoded'
+--+---------+---------+-------+ |n |binary |Gray |decoded| +--+---------+---------+-------+ | 0|0 0 0 0 0|0 0 0 0 0| 0 | | 1|0 0 0 0 1|0 0 0 0 1| 1 | | 2|0 0 0 1 0|0 0 0 1 1| 2 | | 3|0 0 0 1 1|0 0 0 1 0| 3 | | 4|0 0 1 0 0|0 0 1 1 0| 4 | | 5|0 0 1 0 1|0 0 1 1 1| 5 | | 6|0 0 1 1 0|0 0 1 0 1| 6 | | 7|0 0 1 1 1|0 0 1 0 0| 7 | | 8|0 1 0 0 0|0 1 1 0 0| 8 | | 9|0 1 0 0 1|0 1 1 0 1| 9 | |10|0 1 0 1 0|0 1 1 1 1|10 | |11|0 1 0 1 1|0 1 1 1 0|11 | |12|0 1 1 0 0|0 1 0 1 0|12 | |13|0 1 1 0 1|0 1 0 1 1|13 | |14|0 1 1 1 0|0 1 0 0 1|14 | |15|0 1 1 1 1|0 1 0 0 0|15 | |16|1 0 0 0 0|1 1 0 0 0|16 | |17|1 0 0 0 1|1 1 0 0 1|17 | |18|1 0 0 1 0|1 1 0 1 1|18 | |19|1 0 0 1 1|1 1 0 1 0|19 | |20|1 0 1 0 0|1 1 1 1 0|20 | |21|1 0 1 0 1|1 1 1 1 1|21 | |22|1 0 1 1 0|1 1 1 0 1|22 | |23|1 0 1 1 1|1 1 1 0 0|23 | |24|1 1 0 0 0|1 0 1 0 0|24 | |25|1 1 0 0 1|1 0 1 0 1|25 | |26|1 1 0 1 0|1 0 1 1 1|26 | |27|1 1 0 1 1|1 0 1 1 0|27 | |28|1 1 1 0 0|1 0 0 1 0|28 | |29|1 1 1 0 1|1 0 0 1 1|29 | |30|1 1 1 1 0|1 0 0 0 1|30 | |31|1 1 1 1 1|1 0 0 0 0|31 | +--+---------+---------+-------+</lang>
Also, for reference, here is the algorithm mentioned in the task description:
<lang j>B2G=: ({.,2 ~:/\ ])"1</lang>
Example use:
<lang j> B2G #:i.4 0 0 0 1 1 1 1 0</lang>
Java
This example encodes using shifts, bitwise operations, and summing into the result. It decodes using Strings. <lang java>public class Gray { public static long grayEncode(long n){ long result = 0; for(int exp = 0; n > 0; n /= 2, exp++){ long nextHighestBit = (n >> 1) & 1; if(nextHighestBit == 1){ result += ((n & 1) == 0) ? (1 << exp) : 0; //flip the bit }else{ result += (n & 1) * (1 << exp); //"n & 1" is "this bit", don't flip it } } return result; }
public static long grayDecode(long n){ String nBits = Long.toBinaryString(n); String result = nBits.substring(0, 1); for(int i = 1; i < nBits.length(); i++){ //bin[i] = gray[i] ^ bin[i-1]
//XOR with characters result += nBits.charAt(i) != result.charAt(i - 1) ? "1" : "0"; } return Long.valueOf(result, 2); }
public static void main(String[] args){ System.out.println("i\tBinary\tGray\tDecoded"); for(int i = 0; i < 32;i++){ System.out.print(i +"\t"); System.out.print(Integer.toBinaryString(i) + "\t"); System.out.print(Long.toBinaryString(grayEncode(i))+ "\t"); System.out.println(grayDecode(grayEncode(i))); } } }</lang> Output:
i Binary Gray Decoded 0 0 0 0 1 1 1 1 2 10 11 2 3 11 10 3 4 100 110 4 5 101 111 5 6 110 101 6 7 111 100 7 8 1000 1100 8 9 1001 1101 9 10 1010 1111 10 11 1011 1110 11 12 1100 1010 12 13 1101 1011 13 14 1110 1001 14 15 1111 1000 15 16 10000 11000 16 17 10001 11001 17 18 10010 11011 18 19 10011 11010 19 20 10100 11110 20 21 10101 11111 21 22 10110 11101 22 23 10111 11100 23 24 11000 10100 24 25 11001 10101 25 26 11010 10111 26 27 11011 10110 27 28 11100 10010 28 29 11101 10011 29 30 11110 10001 30 31 11111 10000 31
PicoLisp
<lang PicoLisp>(de grayEncode (N)
(bin (x| N (>> 1 N))) )
(de grayDecode (G)
(bin
(pack
(let X 0
(mapcar
'((C) (setq X (x| X (format C))))
(chop G) ) ) ) ) )</lang>
Test: <lang PicoLisp>(prinl " Binary Gray Decoded") (for I (range 0 31)
(let G (grayEncode I)
(tab (4 9 9 9) I (bin I) G (grayDecode G)) ) )</lang>
Output:
Binary Gray Decoded 0 0 0 0 1 1 1 1 2 10 11 2 3 11 10 3 4 100 110 4 5 101 111 5 6 110 101 6 7 111 100 7 8 1000 1100 8 9 1001 1101 9 10 1010 1111 10 11 1011 1110 11 12 1100 1010 12 13 1101 1011 13 14 1110 1001 14 15 1111 1000 15 16 10000 11000 16 17 10001 11001 17 18 10010 11011 18 19 10011 11010 19 20 10100 11110 20 21 10101 11111 21 22 10110 11101 22 23 10111 11100 23 24 11000 10100 24 25 11001 10101 25 26 11010 10111 26 27 11011 10110 27 28 11100 10010 28 29 11101 10011 29 30 11110 10001 30 31 11111 10000 31
Ruby
Integer#from_gray has recursion so it can use each bit of the answer to compute the next bit.
<lang ruby>class Integer
# Converts a normal integer to a Gray code. def to_gray raise Math::DomainError, "integer is negative" if self < 0 self ^ (self >> 1) end
# Converts a Gray code to a normal integer.
def from_gray
raise Math::DomainError, "integer is negative" if self < 0
recurse = proc do |i|
next 0 if i == 0
o = recurse[i >> 1] << 1
o + (i & 1 ^ o[1])
end
recurse[self]
end
end
(0..31).each do |number|
encoded = number.to_gray
decoded = encoded.from_gray
printf("%2d: %5b => %5b => %5b: %2d\n",
number, number, encoded, decoded, decoded)
end</lang>