Gray code: Difference between revisions

{{task}}[[wp: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 [[wp:Karnaugh map|Karnaugh maps]] in order from left to right or top to bottom.

 

 

 

Encoding (MSB is bit 0, b is binary, g is Gray code):

<pre>if b[i-1] = 1

g[i] = not b[i]

else

g[i] = b[i]</pre>

Or:

<pre>g = b xor (b logically right shifted 1 time)</pre>

Decoding (MSB is bit 0, b is binary, g is Gray code):

<pre>b[0] = g[0]

 

;Reference

* [http://www.wisc-online.com/Objects/ViewObject.aspx?ID=IAU8307 Converting Between Gray and Binary Codes]. It includes step-by-step animations.

 

=={{header|Ada}}==

use Ada.Text_IO, Interfaces;

 

New_Line;

end loop;

Check compactness of assembly code generated by GNAT :http://pastebin.com/qtNjeQk9<br>

0: 2#0# => 2#0# => 0

1: 2#1# => 2#1# => 1

31: 2#11111# => 2#10000# => 31</pre>

 

{{works with|BBC BASIC for Windows}}

PRINT " Decimal Binary Gray Decoded"

DEF FNgraydecode(G%) : LOCAL B%

REPEAT B% EOR= G% : G% = G% >>> 1 : UNTIL G% = 0

 

=={{header|bc}}==

This language has no bitwise logic. We must repeat, with each bit, the exclusive-or calculation. This solution uses <tt>h % 2</tt> and <tt>i % 2</tt> to grab the low bits, and repeats <tt>if (h % 2 != i % 2)</tt> to check if the exclusive-or is one. Our encoding and decoding functions are identical except that <tt>h</tt> always comes from the decoded integer.

 

 

/* encode Gray code */

"

}

 

00001 => 00001 => 00001

00010 => 00011 => 00010

11110 => 10001 => 11110

11111 => 10000 => 11111</pre>

 

=={{header|C}}==

{{trans|Tcl}}

}

 

int gray_decode(int n) {

Demonstration code:

 

/* Simple bool formatter, only good on range 0..31 */

}

return 0;

<pre>

0 : 00000 => 00000 => 00000 : 0

</pre>

 

 

public class Gray {

}

}

<pre>

Number Binary Gray Decoded

</pre>

 

 

}

 

 

}

 

void main() {

}

 

 

 

}

 

}

 

 

}

 

void main() {

 

: [""];

}

 

void main() {

 

=={{header|Delphi}}==

{{trans|DWScript}}

 

{$APPTYPE CONSOLE}

Writeln(Format(' %2d %s %s %s %2d', [i, IntToBin(i, 5), IntToBin(g, 5), IntToBin(d, 5), d]));

end;

 

=={{header|DWScript}}==

 

begin

Result := v xor (v shr 1);

PrintLn(Format(' %2d %s %s %s %2d',

[i, IntToBin(i, 5), IntToBin(g, 5), IntToBin(d, 5), d]));

 

=={{header|Erlang}}==

{{trans|Euphoria}}

-export([encode/1, decode/1]).

 

decode(0,N) -> N;

decode(G,N) -> decode(G bsr 1, G bxor N).

 

Demonstration code:

 

test_encode(N) ->

test_encode(I, N) when I < N -> test_encode(I), test_encode(I+1, N).

 

 

<pre>

0 : 00000 : 00000 : 00000 : 0

 

=={{header|Euphoria}}==

return xor_bits(n,floor(n/2))

end function

j = gray_decode(j)

printf(1,"%05d\n",dcb(j))

 

<pre>00000 => 00000 => 00000

00001 => 00001 => 00001

11110 => 10001 => 11110

11111 => 10000 => 11111</pre>

 

=={{header|Forth}}==

 

: gray> ( n -- n )

begin

2dup 2/ xor

until

: test

32 0 do

gray> 5 .r

loop

 

=={{header|Fortran}}==

IMPLICIT NONE

INTEGER IGRAY,I,J,K

10 CONTINUE

S(1:L-K)=''

 

<pre> 0 : 00000 => 00000 => 00000 : 0

30 : 11110 => 10001 => 11110 : 30

31 : 11111 => 10000 => 11111 : 31</pre>

=={{header|Go}}==

{{trans|Euphoria}}

Binary reflected, as described in the task. Reading down through the solutions, the Euphoria decode algorithm caught my eye as being concise and easy to read.

 

import "fmt"

fmt.Printf(" %2d %05b %05b %05b %2d\n", b, b, g, d, d)

}

<pre>

decimal binary gray decoded

=={{header|Groovy}}==

Solution:

i ^ (i >>> 1)

}

def h = grayDecode(code >>> 1)

return (h << 1) + ((code ^ h) & 1)

 

Test:

def remainder = i

def bin = []

it, iB[4],iB[3],iB[2],iB[1],iB[0], cB[4],cB[3],cB[2],cB[1],cB[0], decode)

println()

 

Results:

====== ====== ========= ======

0 00000 00000 0

 

=={{header|Haskell}}==

 

 

 

 

 

 

 

 

 

 

=={{header|J}}==

<code>G2B</code> is an invertible function which will translate Gray code to Binary:

 

 

Thus <code>G2B inv</code> will translate binary to Gray code.

Required example:

 

G2B=: ~:/\&.|:

(,: ,.@".&.>) 'n';'#:n';'G2B inv#:n';'#.G2B G2B inv#:n'

|30|1 1 1 1 0|1 0 0 0 1 |30 |

|31|1 1 1 1 1|1 0 0 0 0 |31 |

 

=={{header|Java}}==

{{trans|C}}

public static long grayEncode(long n){

}

public static long grayDecode(long n) {

}

public static void main(String[] args){

System.out.print(Integer.toBinaryString(i) + "\t");

System.out.println(grayDecode(grayEncode(i)));

}

}

}

 

 

 

end

 

 

 

 

 

=={{header|Logo}}==

{{trans|Euphoria}}

output bitxor :number lshift :number -1

end

]

output :value

 

Demonstration code, including formatters:

while [(count :str) < :width] [

make "str word :pad :str

print (sentence (format :num 2) ": (binary :num 5) ": (binary :gray 5) ":

(binary :decoded 5) ": (format :decoded 2)) ]

 

<pre> 0 : 00000 : 00000 : 00000 : 0

1 : 00001 : 00001 : 00001 : 1

31 : 11111 : 10000 : 11111 : 31

</pre>

 

=={{header|Lua}}==

{{trans|Euphoria}}

This code uses the [http://bitop.luajit.org/index.html Lua BitOp] module. Designed to be a module named <tt>gray.lua</tt>.

 

local bit = require('bit')

end

 

 

Demonstration code:

local gray = require 'gray'

 

to_bit_string(i,5), to_bit_string(g, 5),

to_bit_string(gd,5), gd))

 

<pre>

 

31 : 11111 => 10000 => 11111 : 31

</pre>