G4.9.1 Barrel Shifter from Mux Stages

MediumImplementIcarus Verilog + Yosys · serverReview the topic

Build a 16-bit right rotator from four mux stages that rotate by 1, 2, 4 and 8 places, and expose each stage.

Hardware context: A cipher round that rotates a word by a key-dependent amount, and a sensor filter that scales signed samples. Build a four-stage 16-bit barrel rotator with every stage visible.

A cipher block rotates a 16-bit word right by a key-dependent amount in every round. The design review asks for a barrel shifter. It has four stages, each a row of 2:1 muxes, so the timing is the same for every amount.

This is an Implement problem. Write rotr16. Stage k rotates its input right by 2^k places when bit k of n is 1, and passes it otherwise. The stages come in the order 1, 2, 4, 8. Drive s1, s2 and s4 with the words after the first three stages, and y with the last.

The check applies one word and one amount per case and records all four outputs. The check also synthesizes the module on the site's flow and rejects any latch.

Signals in the Timeline

SignalWidthRole
script20input of each check
Full specification
The module (keep the name and the ports)
module rotr16 (
  input  logic [15:0] x,
  input  logic [3:0]  n,         // rotate right by 0 to 15 places
  output logic [15:0] s1,        // after the stage that rotates by 1 when n[0] = 1
  output logic [15:0] s2,        // after the stage that rotates by 2 when n[1] = 1
  output logic [15:0] s4,        // after the stage that rotates by 4 when n[2] = 1
  output logic [15:0] y          // after the stage that rotates by 8 when n[3] = 1
);
  // your design
endmodule
OutputRule
s1x rotated right by n[0] places.
s2s1 rotated right by 2·n[1] places.
s4s2 rotated right by 4·n[2] places.
ys4 rotated right by 8·n[3] places; so y is x rotated right by n.

The result fields are s1_step0, s2_step0, s4_step0 and y_step0, in hex.

Examples

Example 1

Rotate by 1
Input
x=0001 n=1
Output
s1_step0 = 0x8000, s2_step0 = 0x8000, s4_step0 = 0x8000, y_step0 = 0x8000

Only the first stage acts: the 1 in bit 0 wraps around to bit 15, and the later stages pass 8000 on.

Example 2

Rotate by 5 = 1 + 4
Input
x=8421 n=5
Output
s1_step0 = 0xc210, s2_step0 = 0xc210, s4_step0 = 0xc21, y_step0 = 0xc21

The 1-place and the 4-place stages act; the 2-place and 8-place stages pass their input on unchanged.

Example 3

Rotate by 15
Input
x=8000 n=15
Output
s1_step0 = 0x4000, s2_step0 = 0x1000, s4_step0 = 0x100, y_step0 = 0x1

All four stages act: 1 + 2 + 4 + 8 = 15 places right, the same as one place left.

Constraints and Contract

  • Inputs are known 0/1 values. Each case holds its inputs for one nanosecond and samples the outputs at its end.
  • Keep the module name and the ports. The design is combinational.

Hints

Hint 1

A rotate right by k places is a concatenation. The low k bits go to the top, and the other bits slide down.

Hint 2

Each stage is one conditional: if its bit of n is 1, rotate by its amount; else pass the word.

Hint 3

Chain the stages: the 2-place stage starts from s1, the 4-place stage from s2, and the last from s4.

What the grader checks: Sixteen directed cases, one per amount, and twelve seeded ones apply a word and an amount. All four stage outputs are compared with a model written in JavaScript. The synthesis check rejects a latch.

The submitted design must synthesize with 0 latches and no combinational loop. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.

28 checks on Icarus Verilog + Yosys · server. 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 3 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

Rotate by 1

Input
x=0001 n=1
Expected output
s1_step0 = 0x8000, s2_step0 = 0x8000, s4_step0 = 0x8000, y_step0 = 0x8000

Only the first stage acts: the 1 in bit 0 wraps around to bit 15, and the later stages pass 8000 on.

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

Icarus Verilog + Yosys · server