Gray 1000 → binary, 4-bit — Gray code
edge casethe last codeword, one bit from the first
Answer
1111
Why this example is worth doing
A single leading 1 decodes to fifteen — the _last_ entry of the four-bit sequence, not the midpoint, which is the intuition trap this entry exists to spring. It follows from the reflection construction: the upper half is the lower half mirrored, so the largest index sits at the top of the mirrored block and carries the smallest-looking codeword. Because 1000 and 0000 differ in one bit, the sequence closes into a cycle, which is what makes Gray code usable on a rotating shaft.
Try your own input in the Gray code. Convert binary to reflected Gray code and back, and build the sequence by reflection.
How the answer is reached
Gray code 1000 to binary
Copy the most significant bit, then XOR each Gray bit with the binary bit already produced above it. This direction is inherently sequential.
| bit i | g_i | b_(i+1) | b_i = b_(i+1) XOR g_i |
|---|---|---|---|
| 3 | 1 | - (the MSB is copied) | 1 |
| 2 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 |
Gray1000
binary1111
equivalentlyb_i = parity of g_(n-1) ... g_i
This is the binary reflected Gray code. It is one Gray code among many: any single-bit-change ordering of the codewords is a Gray code, and other constructions give different tables.
Source: Frank Gray, US Patent 2,632,058, "Pulse Code Communication" (filed 1947, granted 1953)