Is there any known way to compute the addition (and maybe the subtraction) of two Gray codes without having to convert the two Gray codes to regular binary, perform a binary addition then convert the result back to a Gray code? I managed to write increment and decrement functions, but the addition and subtraction seem even less documented and harder to write.
Here are the main observations used to construct the algorithm, assume that everything is a Gray code: 2 * n = (n << 1) ⊕ parity(n) If a is a power of 2 and a > b, then a ⊕ b = a + b. Consequently, i a is a power of 2 and a < b, then a ⊕ b = a - b.
For example, the representation of the decimal value "1" in binary would normally be " 001" and "2" would be " 010". In Gray code, these values are represented as " 001" and " 011". That way, incrementing a value from 1 to 2 requires only one bit to change, instead of two.
The most significant bit (MSB) of the Gray code is always equal to the MSB of the given Binary code. Other bits of the output Gray code can be obtained by XORing binary code bit at the index and previous index.
The purpose of Gray code is to encode binary numbers in such a way that the Hamming distance (number of bits on which the numbers differ) between any two consecutive numbers is always exactly one. This is accomplished by reordering the binary encoding so that any two consecutive numbers only differ by a single bit.
In this document under #6, there is an algorithm for serial Gray code addition (copied directly; note, that ⊕
is xor
):
procedure add (n: integer; A,B:word; PA,PB:bit;
var S:word; var PS:bit; var CE, CF:bit);
var i: integer; E, F, T: bit;
begin
E := PA; F := PB;
for i:= 0 to n-1 do begin {in parallel, using previous inputs}
S[i] := (E and F) ⊕ A[i] ⊕ B[i];
E := (E and (not F)) ⊕ A[i];
F := ((not E) and F) ⊕ B[i];
end;
CE := E; CF := F;
end;
This adds the Gray code words A and B to form the Gray code word S. The operand parities are PA and PB, the sum parity is PS. This propagates two carry bits internally, E and F, and produces two external carry bits CE and CF
Unfortunately, it doesn't state anything about subtraction, but I assume, when you can encode negative numbers, you can use addition for that.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With