Tricky Problem: Converting Binary 1101 to Gray Code and Back

Apply the binary-to-Gray and Gray-to-binary XOR conversion procedures correctly in each direction, recognizing that they are structurally different algorithms and not the same formula simply run in reverse.

Convert binary 1101 to Gray code. Then convert the result back to binary.

Why This Problem Is Tricky

Binary-to-Gray and Gray-to-binary both use XOR, and both process bits from most significant to least significant, which makes them look like the same operation performed in two directions. They are not: binary-to-Gray computes each Gray bit by XOR-ing two ADJACENT bits of the ORIGINAL binary number (every XOR uses only source bits, computed independently of each other), while Gray-to-binary must CASCADE — each binary bit is computed by XOR-ing the current Gray bit with the PREVIOUSLY COMPUTED binary bit, so each step depends on the result of the step before it, not on the raw Gray bits alone. Applying the non-cascading binary-to-Gray recipe when trying to reverse the conversion is a very common and easy-to-miss error.

Step-by-Step Worked Solution

Binary to convert: B3 B2 B1 B0 = 1 1 0 1.

Binary-to-Gray rule: G3 = B3 (the MSB is copied unchanged); for each lower bit, Gi = B(i+1) XOR Bi, using only the ORIGINAL binary bits. G3 = B3 = 1. G2 = B3 XOR B2 = 1 XOR 1 = 0. G1 = B2 XOR B1 = 1 XOR 0 = 1. G0 = B1 XOR B0 = 0 XOR 1 = 1. Result: Gray = 1011.

Gray-to-binary rule (converting 1011 back): B3 = G3 (the MSB is copied unchanged); for each lower bit, Bi = B(i+1) XOR Gi, using the PREVIOUSLY COMPUTED binary bit (cascading), not another raw Gray bit. B3 = G3 = 1. B2 = B3 XOR G2 = 1 XOR 0 = 1. B1 = B2 XOR G1 = 1 XOR 1 = 0. B0 = B1 XOR G0 = 0 XOR 1 = 1. Result: Binary = 1101 — exactly the original value, confirming the round trip is correct.

Why the Obvious Wrong Answer Is Wrong

A common mistake when converting Gray back to binary is to reuse the binary-to-Gray-style formula, computing each binary bit as Bi = G(i+1) XOR Gi (using only the given Gray bits, with no cascading through the binary result). For example, this wrong approach would compute B1 = G2 XOR G1 = 0 XOR 1 = 1, which disagrees with the correct cascading result of B1 = B2 XOR G1 = 1 XOR 1 = 0. The two formulas agree only for the MSB and can silently diverge for lower bits whenever the running binary value differs from simply using the raw Gray bits directly — which is exactly what happened here. The correct Gray-to-binary algorithm MUST propagate the previously solved binary bit forward into each subsequent XOR; it is not the same operation as binary-to-Gray run with the roles of B and G swapped.

The Two Conversion Rules

In binary-to-Gray, every XOR input comes from the ORIGINAL binary number. In Gray-to-binary, one XOR input is the RESULT of the previous step, not a raw Gray bit — this cascading dependency is the part most often forgotten.

Binary -> Gray (non-cascading, uses only original binary bits):
  G(n-1) = B(n-1)
  Gi     = B(i+1) xor Bi     for i = n-2 down to 0

Gray -> Binary (cascading, uses the previously computed binary bit):
  B(n-1) = G(n-1)
  Bi     = B(i+1) xor Gi     for i = n-2 down to 0

Code Examples

The forward conversion uses only the original binary bits at every step (no cascading), while the reverse conversion explicitly reuses each just-computed binary bit (B3, then B2, then B1) as an input to the next XOR, which is the structural difference between the two algorithms. Expected result: Gray = 1011; Binary (round trip) = 1101

Gray code of 1101 is 1011; converting 1011 back gives 1101.

Binary -> Gray:
  B: 1   1   0   1
  G3 = B3          = 1
  G2 = B3 xor B2   = 1 xor 1 = 0
  G1 = B2 xor B1   = 1 xor 0 = 1
  G0 = B1 xor B0   = 0 xor 1 = 1
  Gray = 1011

Gray -> Binary (cascading):
  G: 1   0   1   1
  B3 = G3          = 1
  B2 = B3 xor G2   = 1 xor 0 = 1
  B1 = B2 xor G1   = 1 xor 1 = 0
  B0 = B1 xor G0   = 0 xor 1 = 1
  Binary = 1101   (matches the original -- round trip confirmed)

Binary<->Gray Conversion Data Flow

Binary -> Gray (each XOR uses only original B bits, no cascade):
  B: 1   1   0   1
      \ / \ / \ /
       X   X   X      (X = xor)
  G: 1   0   1   1     (G3=B3 copied directly)

Gray -> Binary (cascades through the computed B bits):
  G: 1   0   1   1
  B: 1 ->X-> 1 ->X-> 0 ->X-> 1     (each B feeds forward into the next xor)

Why Getting the Direction Right Matters

Gray code is used in rotary encoders and FIFO pointer comparisons specifically because only one bit changes between any two adjacent values, which prevents false intermediate readings during a transition. Firmware that converts an encoder's Gray-coded position back to binary using the wrong (non-cascading) formula will silently produce incorrect position readings for some rotation angles — a subtle bug that is very hard to catch without working through a concrete example like this one.

Computing Gray-to-binary bit B1 as G2 xor G1 (non-cascading) = 1

Computing B1 as B2 xor G1 (cascading from the already-computed B2) = 0

The Gray-to-binary conversion is not the binary-to-Gray formula run with B and G swapped. It must cascade: each binary bit's XOR uses the PREVIOUSLY COMPUTED binary bit, not a second raw Gray bit. Using G2 xor G1 instead of B2 xor G1 gives the wrong answer whenever the cascaded binary value differs from a raw Gray bit, exactly as it does here (1 vs. the correct 0).

What is the Gray code equivalent of binary 1101? A. 1011 B. 1111 C. 0110 D. 1101

A. 1011 — G3=B3=1; G2=B3 xor B2=1 xor 1=0; G1=B2 xor B1=1 xor 0=1; G0=B1 xor B0=0 xor 1=1. Gray = 1011. Converting 1011 back to binary using the cascading rule reproduces 1101, confirming correctness.

When converting Gray code back to binary, each binary bit (other than the MSB) is computed by XOR-ing the corresponding Gray bit with what? A. The next Gray bit B. The previous (more significant) Gray bit C. The previously computed binary bit (one position more significant) D. The original binary number's MSB only

C. The previously computed binary bit (one position more significant) — Gray-to-binary conversion cascades: Bi = B(i+1) xor Gi, where B(i+1) is the binary bit already computed in the previous (more significant) step, not a raw Gray bit. This cascading dependency is what distinguishes Gray-to-binary from the non-cascading binary-to-Gray formula, and forgetting it is the most common source of conversion errors.

Convert binary 1010 to Gray code, then convert the result back to binary to verify the round trip.

Binary->Gray: G3=1; G2=1 xor 0=1; G1=0 xor 1=1; G0=1 xor 0=1. Gray=1111. Gray->Binary: B3=1; B2=1 xor 1=0; B1=0 xor 1=1; B0=1 xor 1=0. Binary=1010, matching the original.

Use the non-cascading rule for binary-to-Gray, and the cascading rule for Gray-to-binary.