W2.6.2 A Gray Pointer

EasyImplementIcarus · browser samples / server checksReview the topic

Build a position counter for a ring of N entries. Its bus code must change one bit per step, even when N is not a power of two.

Hardware context: Data bus encoder and decoder, and a ring pointer counter. Cut the toggles per transfer with bus-invert and Gray coding without losing a word.

A ring buffer of 10 entries sends its position across a long bus to another block. To save wire power, the bus code must change exactly one bit at every step. That includes the wrap from the last entry back to the first.

Plain Gray code does this for 16 entries. With 10 entries the wrap from 9 to 0 changes three bits. Write gray_ring: a binary position idx and a bus code that change together at each edge where inc is 1.

The tests run copies for rings of 10, 6 and 12 entries. Lesson W2.6 shows Gray code on full binary ranges; this ring is shorter.

Signals in the Timeline

SignalWidthRole
clk1stimulus, the same for every design
inc1stimulus, the same for every design
idx4stimulus, the same for every design
code4stimulus, the same for every design
Full specification
The module you write (keep the name, the parameters and the ports)
module gray_ring #(parameter int N = 10, parameter int W = 4) (
  input  logic         clk,
  input  logic         rst_n,      // asynchronous, active-low
  input  logic         inc,        // 1: step to the next position at this edge
  output logic [W-1:0] idx,        // the position, 0 to N-1, in binary
  output logic [W-1:0] code        // the value on the bus wires
);
  // your design
endmodule
OutputRule
idxRegister. 0 after reset. At a rising edge with inc = 1 it steps by one, and from N - 1 it wraps to 0. With inc = 0 it holds.
codeRegister. At an edge where idx steps, exactly one bit of code changes. At an edge where idx holds, code holds.
code (as a map)Each position has one code: whenever idx is k, code shows the same value. No two positions share a code.

N is even, from 4 to 2^W. The value of code after reset is your choice, as long as it is the code of position 0.

Each case resets one copy, then runs 64 rising edges with inc set before each one. After every edge the fixture checks idx against a model and counts the bits that code changed. It also records the code of each position. The result shows idx after the last edge and four pass flags. steps_ok means one bit per step and none when holding; map_ok means one code per position. distinct_ok means no shared codes, and idx_ok checks the position.

Examples

Example 1

Ten Entries, a Step at Every Edge
Input
N = 10, 64 steps in 64 edges (every edge)
Output
distinct_ok = yes, map_ok = yes, steps_ok = yes, idx_ok = yes, idx_after_edge_63 = 4

After 64 steps the position is 64 mod 10 = 4. Every step, including the six wraps from 9 to 0, must change one bit of code.

Example 2

Six Entries, a Step at Every Edge
Input
N = 6, 64 steps in 64 edges (every edge)
Output
distinct_ok = yes, map_ok = yes, steps_ok = yes, idx_ok = yes, idx_after_edge_63 = 4

A 3-bit code for 6 positions: 64 mod 6 = 4. Plain Gray code from 0 to 5 ends at 111, and 111 to 000 changes three bits.

Example 3

Ten Entries, Every Other Edge
Input
N = 10, 32 steps in 64 edges
Output
distinct_ok = yes, map_ok = yes, steps_ok = yes, idx_ok = yes, idx_after_edge_63 = 2

At the edges where inc is 0, idx and code must both hold. 32 steps leave idx at 2.

Constraints and Contract

  • inc is a known 0/1 value, set before each edge.
  • Keep the module name, the parameters N and W, and the ports.

Hints

Hint 1

Write out the 16 Gray codes of 4 bits in a column. Look at the codes of k and 15 - k. Which bits differ?

Hint 2

You need 10 consecutive codes from that column whose first and last differ in one bit. The symmetry from the first hint tells you where they are.

Hint 3

Map position idx to Gray code number idx + OFF, with one constant OFF that depends on N and W. Compute the next position first, then load both registers from it.

What the grader checks: Seven directed and nine seeded inc scripts run 64 edges each on rings of 10, 6 and 12 entries. So every case passes the wrap several times. The checks are properties of the code: one bit per step, one code per position, no shared codes. The position is checked against a model. Any correct code passes, not only the reference's.

16 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 2 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

Ten Entries, a Step at Every Edge

Input
N = 10, 64 steps in 64 edges (every edge)
Expected output
distinct_ok = yes, map_ok = yes, steps_ok = yes, idx_ok = yes, idx_after_edge_63 = 4

After 64 steps the position is 64 mod 10 = 4. Every step, including the six wraps from 9 to 0, must change one bit of code.

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

Icarus · browser samples / server checks