Barrel shifters and staged multiplexers

Prerequisites: MUXes^{iMultiplexer A combinational circuit that connects one of several inputs to the output according to a select signal. Specify how select bits map to input numbers. Learn more}, logical and arithmetic shifts, and combinational propagation delay^{iPropagation delay The time from an input change until the output settles to the correct value. Logical equivalence and timing behavior are separate properties. Learn more}.

Turn variable shifting into selection among fixed connections

A shift register^{iRegister A circuit that stores multiple bits of state. The synchronous registers in this course store their specified inputs at a clock edge. Learn more} moving one bit at a time uses one clock per shift. A barrel shifter takes a shift amount and computes the result along one combinational path. Bits do not move repeatedly over time; selected wiring connects the desired input positions to outputs.

For a 16-bit value shifted by 0–15 positions, $s=s_0+2s_1+4s_2+8s_3$. Put four stages in series, shifting by 1, 2, 4 and 8. Each MUX chooses either pass-through or its fixed shift.

For example, 11 is binary 1011, selecting shifts by 1, 2 and 8 and bypassing 4. Logical right shifting $X=0xD2A5$ gives intermediates 0x6952, 0x1A54, 0x1A54 and 0x001A. These are four combinational-stage values, not four clock-cycle values.

There are four groups of 16 MUXes: 64 one-bit 2:1 selection points before wiring and constant-propagation optimization. For $W=2^K$, the selection structure scales with $W\log_2W$ and depth with $\log_2W$. Even a separate W:1 MUX drawn for each output can synthesize into a tree, so RTL line count does not establish area or frequency.

Below, 0xD2A5 shifts logically right by 11. Each bit of amount 1011 selects a combinational stage. The diagram does not represent execution over four clocks.

Use a right shifter to implement left shifts too

Reverse the input bit order, logically shift right by s, then reverse the result: this is logical left shift. The symmetry allows sharing the four stages. Input/output direction MUXes add cost beyond the 64 points; fixed bit reversal itself is wiring.

Arithmetic right shift fills vacant high bits with the original input's sign bit. Left shifts fill with zeros even in arithmetic mode. In two's complement^{iTwo's complement A representation of signed integers using fixed-width bit patterns. The n-bit range is −2^(n−1) through 2^(n−1)−1. Learn more}, arithmetic and logical left shifts move bits identically and do not automatically check signed overflow.

Shift-amount range is part of the circuit contract too. The example accepts 0–31 through five-bit shamt. For amounts at least 16, logical and left shifts yield 0; arithmetic right shift yields 16 copies of the sign bit. Using only shamt's low four bits would misinterpret a shift by 16 as a shift by 0.

module barrel16 (
  input  wire [15:0] x,
  input  wire [4:0] shamt,
  input  wire left,
  input  wire arithmetic,
  output wire [15:0] y
);
  wire fill;
  wire [15:0] stage [0:4];
  assign fill = (!left) && arithmetic && x[15];

  for (genvar i = 0; i < 16; i++) begin : direction
    assign stage[0][i] = left ? x[15-i] : x[i];
    assign y[i] = shamt[4] ? fill :
                  (left ? stage[4][15-i] : stage[4][i]);
  end

  for (genvar k = 0; k < 4; k++) begin : shift_stage
    localparam int D = 1 << k;
    assign stage[k+1] = shamt[k]
      ? {{D{fill}}, stage[k][15:D]}
      : stage[k];
  end
endmodule

The generate variable k is constant during circuit construction; it does not describe a device that executes a loop four times at runtime. Fixed part-selects and replication lengths create four fixed wiring patterns and MUX stages. fill stays constant across stages, so selecting several stages preserves consistent sign extension.

This RTL explicitly supplies sign fill, implementing arithmetic shift even for unsigned^{iUnsigned A rule for interpreting a bit pattern as a nonnegative integer. The n-bit range is 0 through 2^n−1 and may differ from the signed interpretation of the same bits. Learn more} vectors. A compact operator version requires a signed left operand and >>> for arithmetic right shift. Merely writing >>>, or making the original variable of a part-select signed, is insufficient. Concatenations and some selections can lose signed interpretation; first convert to a signed value of the intended width. See AMD's Verilog-expression documentation for synthesis-supported operators.

Treat delay separately from information loss

The four combinational stages also incur direction/range-selection and wiring delays. If timing is insufficient, insert registers, but delay the remaining shift amount and direction controls by the same clocks as data. Output latency^{iLatency The time or number of cycles from accepting an input to producing its corresponding output. It differs from throughput, the amount processed per unit time. Learn more} then changes; the interface is no longer that of a simple combinational module.

Shifting cannot recover discarded information. For unsigned left shift, any discarded upper 1 means range overflow. Signed overflow also depends on the original sign and discarded bits. This module outputs no such flags. Arithmetic right shift of a negative value rounds division by $2^s$ downward: shifting $-3$ by one gives $-2$, unlike integer division toward zero, which gives $-1$.