H8.1 Gray Pointer Conversion

EasyFixIcarus · browser samples / server checksReview the topic

Fix a Gray-code converter whose decoder runs the encoder formula a second time.

Hardware context: Gray-pointer asynchronous FIFO with a declared reset and synchronization model. Convert and check Gray-coded pointer values used for cross-domain visibility.

An asynchronous FIFO sends its pointers across clock domains in Gray code. From one count to the next, a Gray code changes exactly one bit. The receiving side turns the Gray value back into binary before it compares pointers.

The function gray_codec does both conversions for pointers of 2 to 8 bits. It encodes binary into Gray, and it decodes gray into binary. The two inputs are separate values, not one number in two forms.

A FIFO built on this function reported wrong fill levels. The encoded values are right, but many decoded values are not. The tests check both results for every value at every width from 2 to 8 bits.

Find the bug and fix it.

Signals in the Timeline

SignalWidthRole
binary8input of each check
gray8input of each check
pointer_bits4input of each check
Full specification
The function (keep its signature)
function automatic logic [79:0] gray_codec(input logic [7:0] binary, gray, input logic [3:0] pointer_bits);
Bits of the resultHolds
79:16Always 0.
15:8decoded_binary: the binary value of gray.
7:0encoded_gray: the Gray code of binary.
StepRule
MaskUse only the low pointer_bits bits of each input. Ignore the bits above them.
EncodeGray = b ^ (b >> 1). Each Gray bit is a binary bit XOR the bit above it.
DecodeBit i of the binary value is the XOR of the Gray bits from the top bit down to bit i.
Wrap bitThe top bit is the wrap bit of a FIFO pointer. It must survive both conversions.

A worked decode: Gray 0100 in 4 bits. The top bit is copied, giving 0. Then 0 ^ 1 = 1, 1 ^ 0 = 1 and 1 ^ 0 = 1. The binary value is 0111, which is 7.

Examples

Example 1

Encode 7 and Decode Gray 4
Input
binary = 7, gray = 4, pointer_bits = 4
Output
decoded_binary = 7, encoded_gray = 'b00000100

Binary 0111 encodes to Gray 0100. Gray 0100 decodes to binary 0111, which is 7. Running the encoder on 0100 would give 6 instead.

Example 2

The Wrap Bit Is Set
Input
binary = 8, gray = 12, pointer_bits = 4
Output
decoded_binary = 8, encoded_gray = 'b00001100

Binary 1000 is address 0 with the wrap bit set. It encodes to Gray 1100, which is 12. Gray 1100 decodes back to 1000, so the wrap bit survives.

Example 3

All 8 Bits in Use
Input
binary = 255, gray = 128, pointer_bits = 8
Output
decoded_binary = 255, encoded_gray = 'b10000000

Binary 11111111 encodes to Gray 10000000. Decoding 10000000 copies the top 1 into every lower bit, which gives 255.

Constraints and Contract

  • pointer_bits is 2 to 8. Bits of binary and gray above pointer_bits are ignored.
  • Keep the function name, the argument names and their widths.

Hints

Hint 1

Decoding must undo encoding. Encode 5 in 4 bits, then decode the result. Do you get 5 back?

Hint 2

Encoding looks at one neighbour per bit. Decoding cannot, because each binary bit depends on every Gray bit above it. It needs a running XOR from the top.

Hint 3

Look at the second line that sets decoded. It reruns the encoder on the raw input and also drops the mask. Keep the masked value and fold in copies shifted right by 1, 2 and 4.

What the grader checks: The tests check every value at every width from 2 to 8 bits, plus inputs with high bits to ignore. A correct conversion does not make a crossing safe. That also needs two flops and timing constraints.

513 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 8 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Encode 7 and Decode Gray 4

Input
binary = 7, gray = 4, pointer_bits = 4
Expected output
decoded_binary = 7, encoded_gray = 'b00000100

Binary 0111 encodes to Gray 0100. Gray 0100 decodes to binary 0111, which is 7. Running the encoder on 0100 would give 6 instead.

Run samples executes all 3 public checks. Check all tests runs 513 checks on the server.

Icarus · browser samples / server checks