Consider numbers represented in 4-bit gray code. Let h3h2h1h0 be the gray code…
2006
Consider numbers represented in 4-bit gray code. Let h3h2h1h0 be the gray code representation of a number n and let g3g2g1g0 be the gray code of (n + 1) (modulo 16) value of the number. Which one of the following functions is correct?
- A.
g0(h3,h2,h1,h0) = ∑ (1,2,3,6,10,13,14,15)
- B.
g1(h3,h2,h1,h0) = ∑ (4,9,10,11,12,13,14,15)
- C.
g2(h3,h2,h1,h0) = ∑ (2,4,5,6,7,12,13,15)
- D.
g3(h3,h2,h1,h0) = ∑ (0,1,6,7,10,11,12,13)
Attempted by 348 students.
Show answer & explanation
Correct answer: C
Answer: The function g2(h3,h2,h1,h0) = Σ(2,4,5,6,7,12,13,15) is correct.
Derivation:
Compute Gray codes: Gray(n) = n xor (n >> 1). For n = 0..15 the Gray sequence (decimal) is: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8].
For each n compute g = Gray(n+1). Map h = Gray(n) to g = Gray(n+1). The mapping (h -> g) in decimal is: 0→1, 1→3, 2→6, 3→2, 4→12, 5→4, 6→7, 7→5, 8→0, 9→8, 10→11, 11→9, 12→13, 13→15, 14→10, 15→14.
Extract g2 (the 4's place bit) from each g: g2 = 1 exactly for h = 2, 4, 5, 6, 7, 12, 13, 15.
Therefore g2(h3,h2,h1,h0) = Σ(2,4,5,6,7,12,13,15), which matches the stated function.