RTL Design Patterns · Chapter 5 · Arithmetic & Datapath Patterns
Shifters & Barrel Shifters
Datapaths often have to slide bits sideways by an amount not known until run time, to normalize a mantissa, scale a DSP sample, align a byte field, or rotate a word. Shifting one place at a time is a sequential machine that can take many cycles and stall the pipeline. A barrel shifter does it in a single combinational cycle, and it is not new arithmetic but a familiar pattern: a tree of multiplexers steered by the shift amount, with log2(N) stages where each stage either passes the data through or shifts it by a power of two. On top of that sit the three shift flavours, logical fill-zero, arithmetic sign-extend, and rotate, plus the classic bug of right-shifting signed data logically, which drops zeros where the sign bit belonged. Built and self-check-verified in SystemVerilog, Verilog, and VHDL.
Intermediate14 min readRTL Design PatternsBarrel ShifterArithmetic ShiftRotateMux TreeDatapath
Chapter 5 · Section 5.3 · Arithmetic & Datapath Patterns
1. The Engineering Problem
You are building the shift unit of an ALU, and the shift amount is not a constant — it arrives in a register every cycle. One instruction asks to shift data_in left by 3; the next, left by 17; the next, an arithmetic right shift by 5 on a signed value; the next, a rotate by 11. The amount, the direction, and the flavour of shift all change instruction to instruction, and the result must be ready this cycle because the next pipeline stage is already waiting on it.
The obvious first idea is a loop: a small state machine that shifts data_in one place, checks whether it has shifted enough, and repeats. It is correct, and it is a disaster — a shift by 31 takes 31 cycles, the ALU stalls, and a "shift" instruction is suddenly the slowest thing in the machine. Worse, the latency depends on the operand, so the pipeline timing is data-dependent. No real datapath shifts like this. The requirement is uncompromising: shift or rotate data_in by a run-time-variable shamt, in one combinational cycle, for any amount from 0 to N-1.
The structure that meets that requirement is the barrel shifter, and the reason it belongs in this chapter is that it is not new arithmetic — it is a composition of multiplexers (§1.1). And riding on top of it is the same signedness question that haunted the adder (§5.1) and the comparator: when you shift right, do you fill the vacated top bits with zeros (a logical shift) or with copies of the sign bit (an arithmetic shift)? For unsigned data, zeros are right. For signed data, filling zeros destroys the sign — -8 >> 1 should be -4, but a logical shift turns it into a huge positive number. Which fill you use is a signedness decision, exactly like which overflow flag you read on the adder, and getting it wrong is silent until real negative data flows through.
// The amount is a RUN-TIME value, not a constant — a register, every cycle:
wire [4:0] shamt; // 0..31, changes each instruction
wire [31:0] data_in;
wire [1:0] mode; // 00 logical, 01 arithmetic, 10 rotate
// NAIVE — shift one place, N times: up to 31 cycles, data-dependent latency:
// for (i=0;i<shamt;i=i+1) acc = acc >> 1; // sequential, stalls the pipe
// RIGHT — a BARREL SHIFTER: log2(32)=5 mux-tree stages do ANY shift in ONE
// combinational cycle. Stage k shifts by 2^k if shamt[k] is set, else passes.
// And the RIGHT-shift fill bit is a SIGNEDNESS decision:
// logical >> fills 0 (correct for UNSIGNED)
// arithmetic >>> fills sign (correct for SIGNED — -8 >> 1 == -4)2. Mental Model
3. Pattern Anatomy
The shifter family is one structure — a log2(N)-stage mux tree — read along three axes: how the amount enters, which direction/flavour fills the vacated bits, and whether the shift is variable or constant.
The log2(N)-stage mux tree (the structure a variable shift synthesizes to). Number the stages 0 .. log2(N)-1. Stage k looks at bit k of shamt. If shamt[k] is 1, the stage shifts its input by 2^k places; if it is 0, the stage passes its input straight through. Because shamt = sum over k of shamt[k] * 2^k, chaining the stages composes their shifts into exactly shamt. Each stage is a rank of N 2:1 muxes: mux i chooses between "keep bit i" (no shift) and "take the bit 2^k places away" (shift), under the common select shamt[k]. So a 32-bit barrel shifter is 5 ranks of 32 muxes — 160 2:1 muxes — and its delay is the 5-deep mux chain, i.e. ~log2(N), not ~N. That logarithmic depth is the whole point: it is what makes a variable shift a one-cycle operation instead of an N-cycle loop.
Direction and fill — the four flavours differ only in the vacated bits. Every stage shifts data one way and must supply something for the bits that open up. That "something" is the only difference between the flavours:
- Logical left (
<<). Shift toward the MSB; the vacated low bits fill with 0. Bits shifted past the MSB are dropped. - Logical right (
>>). Shift toward the LSB; the vacated high bits fill with 0. This is correct for unsigned data — a logical right shift bykis an unsigned divide by2^k. - Arithmetic right (
>>>). Shift toward the LSB; the vacated high bits fill with copies of the sign bit (data_in[N-1]). This is correct for signed data — an arithmetic right shift bykis a signed divide-by-2^kthat rounds toward negative infinity, and it preserves the sign. (Arithmetic left shift is identical to logical left; the fill is always 0 at the bottom.) - Rotate. No bits are lost; bits that fall off one end wrap around to the other. A rotate-left by
kon an N-bit word is{data_in[N-1-k:0], data_in[N-1:N-k]}— the vacated bits fill with the bits that fell off. Rotate is not a shift-plus-fill; it is a shift where the "fill" is the data itself.
Variable vs constant — where the logic actually is. This distinction decides whether you pay for the tree at all:
- Constant shift —
shamtis a compile-time constant (data_in << 3). There is no logic: shifting by a constant is just wiring bitito biti-3and tying three low bits to 0. The synthesis tool builds zero gates. A constant shift is free. - Variable shift —
shamtis a signal. Now the tool must build the full log2(N)-stage mux tree, because at elaboration time it cannot know the amount and must be able to produce all of them. This is the barrel shifter, and it has real area (log2(N)·N muxes) and real delay (log2(N) mux depth). Confusing the two — assuming a variable shift is as cheap as a constant one — is the resource mistake of §6.
The shift-amount width, and shifting by ≥ N. shamt needs log2(N) bits to name every legal amount 0 .. N-1. If shamt is wider than that, it can request a shift by ≥ N, which for a logical shift means "everything falls off — result is 0 (or all-sign-bits for arithmetic right)". A correct design either constrains shamt to log2(N) bits (so ≥ N is unrepresentable) or defines the ≥ N behaviour deliberately; leaving it to a truncated index is the off-by-width bug.
The barrel-shifter family — one log2(N)-stage mux tree, four fills, steered by shamt
data flowThe whole anatomy reduces to four decisions you make on every shifter: is the amount variable (build the tree) or constant (free wiring); which direction; which fill — zero (logical), sign (arithmetic), or wrap (rotate); and how many bits shamt needs so it cannot silently request a shift by more than N-1. Get the fill wrong on signed right shifts and the datapath is correct in a positive-only simulation and wrong the moment a negative value flows through.
4. Real RTL Implementation
This is the core of the page. We build two patterns — (a) a WIDTH-generic barrel shifter with a mode selecting logical / arithmetic / rotate and a run-time-variable shamt, built explicitly as a log2(N)-stage mux tree; and (b) the arithmetic-vs-logical right-shift signedness bug (buggy vs fixed) — and each is shown in SystemVerilog, Verilog, and VHDL, with an RTL block and a self-checking testbench. The idea is identical across all three; only the syntax for the sign-fill and the shift operators differs, and seeing them side by side is what fixes the logical-vs-arithmetic reasoning in your head.
One discipline runs through every block: the mux-tree stages are explicit, so you can see the log2(N) structure a variable shift becomes; and the right-shift fill is chosen by mode — zero for logical, the sign bit for arithmetic, the wrapped bits for rotate — never left to a default operator. In SystemVerilog and Verilog that means a generate/for loop over the log2(N) stages with a per-stage fill; in VHDL it means numeric_std shift_left/shift_right/rotate_left on the correctly-typed signed/unsigned value.
4a. WIDTH-generic barrel shifter — the log2(N) mux tree, three ways
Start with the workhorse: one module that shifts left or right, logical or arithmetic, or rotates, by a run-time shamt, for any WIDTH. Rather than write data_in >> shamt and let the tool infer the tree invisibly, we build the log2(N) stages explicitly, so the mux-tree structure — and the per-stage fill — is on the page. Each stage either shifts by its power of two or passes through, selected by one bit of shamt; the fill fed into the shifted input is what encodes logical vs arithmetic vs rotate.
module barrel_shifter #(
parameter int WIDTH = 32,
localparam int SHW = $clog2(WIDTH) // shamt names 0..WIDTH-1
)(
input logic [WIDTH-1:0] data_in,
input logic [SHW-1:0] shamt, // RUN-TIME variable amount
input logic dir, // 0 = left, 1 = right
input logic [1:0] mode, // 00 logical, 01 arithmetic, 10 rotate
output logic [WIDTH-1:0] data_out
);
// The fill bit for a RIGHT shift is the whole lesson: logical fills 0,
// arithmetic fills the SIGN bit (data_in[MSB]). Rotate ignores the fill —
// it re-injects the bits that fell off, so no data is ever lost.
logic sign_fill;
assign sign_fill = (mode == 2'b01) ? data_in[WIDTH-1] : 1'b0;
// Build log2(WIDTH) stages. Stage k shifts by 2^k when shamt[k] is set,
// else passes through. Each stage is a row of 2:1 muxes; chaining them
// composes the shifts into exactly `shamt`, so ANY amount takes one cycle.
logic [WIDTH-1:0] stage [SHW+1]; // stage[0]=input ... stage[SHW]=output
assign stage[0] = data_in;
genvar k;
generate
for (k = 0; k < SHW; k++) begin : g_stage
localparam int SH = (1 << k); // this stage shifts by 2^k
always_comb begin
if (!shamt[k])
stage[k+1] = stage[k]; // bit not set -> pass through
else if (mode == 2'b10) // ROTATE: wrap, direction-aware
stage[k+1] = dir ? {stage[k][SH-1:0], stage[k][WIDTH-1:SH]} // rot right
: {stage[k][WIDTH-1-SH:0], stage[k][WIDTH-1:WIDTH-SH]}; // rot left
else if (dir) // RIGHT logical/arithmetic: fill top
stage[k+1] = {{SH{sign_fill}}, stage[k][WIDTH-1:SH]};
else // LEFT: fill low bits with 0
stage[k+1] = {stage[k][WIDTH-1-SH:0], {SH{1'b0}}};
end
end
endgenerate
assign data_out = stage[SHW];
endmoduleTwo lines carry the lesson. sign_fill = (mode==arith) ? data_in[MSB] : 0 is the entire logical-vs-arithmetic decision, isolated to one signal. And building stage[k+1] from stage[k] under shamt[k] is the mux tree — the tool synthesizes exactly SHW ranks of WIDTH muxes, delay ~log2(WIDTH), no matter what shamt is at run time. The testbench sweeps every shift amount 0..WIDTH-1 for each mode and direction, checks against a reference model, and — critically — drives negative data_in for the arithmetic-right case so the sign-fill is actually exercised.
module barrel_shifter_tb;
localparam int WIDTH = 32;
localparam int SHW = $clog2(WIDTH);
logic [WIDTH-1:0] data_in, data_out;
logic [SHW-1:0] shamt;
logic dir;
logic [1:0] mode;
int errors = 0;
barrel_shifter #(.WIDTH(WIDTH)) dut
(.data_in(data_in), .shamt(shamt), .dir(dir), .mode(mode), .data_out(data_out));
function automatic logic [WIDTH-1:0] ref_model
(logic [WIDTH-1:0] d, int s, logic rt, logic [1:0] m);
if (m == 2'b10) // ROTATE (wrap)
return rt ? ((d >> s) | (d << (WIDTH - s))) // rotate right
: ((d << s) | (d >> (WIDTH - s))); // rotate left
else if (!rt) return d << s; // LEFT logical
else if (m == 2'b01) return $signed(d) >>> s; // RIGHT arithmetic (sign-extend)
else return d >> s; // RIGHT logical (fill 0)
endfunction
initial begin
// Use a value with the MSB set so arithmetic vs logical actually DIFFER.
data_in = 32'hF3A5_0F0F; // negative as signed
for (int m = 0; m < 3; m++) begin
for (int r = 0; r < 2; r++) begin
for (int s = 0; s < WIDTH; s++) begin // EXHAUSTIVE over shamt
mode = m[1:0]; dir = r[0]; shamt = s[SHW-1:0];
#1;
assert (data_out === ref_model(data_in, s, r[0], m[1:0]))
else begin
$error("mode=%b dir=%b s=%0d out=%h exp=%h",
mode, dir, s, data_out, ref_model(data_in, s, r[0], m[1:0]));
errors++;
end
end
end
end
// Directed sign-fill corner: arithmetic right of a small negative.
data_in = -32'sd8; mode = 2'b01; dir = 1'b1; shamt = 5'd1; #1; // -8 >>> 1 == -4
assert ($signed(data_out) === -32'sd4)
else begin $error("arith -8>>>1 = %0d exp=-4", $signed(data_out)); errors++; end
if (errors == 0) $display("PASS: barrel_shifter correct for all shamt/mode/dir");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleThe Verilog form is identical in intent — only wire/reg typing, $signed casts, and the generate idiom differ. The explicit log2(N) stages and the sign_fill mux are line-for-line the same idea; the arithmetic right shift in the reference model uses Verilog's >>> on a $signed operand.
module barrel_shifter #(
parameter WIDTH = 32,
parameter SHW = 5 // = clog2(WIDTH); set by instantiator
)(
input wire [WIDTH-1:0] data_in,
input wire [SHW-1:0] shamt, // run-time variable amount
input wire dir, // 0 = left, 1 = right
input wire [1:0] mode, // 00 logical, 01 arithmetic, 10 rotate
output wire [WIDTH-1:0] data_out
);
// Right-shift fill: 0 for logical, the SIGN bit for arithmetic.
wire sign_fill = (mode == 2'b01) ? data_in[WIDTH-1] : 1'b0;
// log2(WIDTH) stages chained; stage k shifts by 2^k under shamt[k].
wire [WIDTH-1:0] stage [0:SHW];
assign stage[0] = data_in;
genvar k;
generate
for (k = 0; k < SHW; k = k + 1) begin : g_stage
localparam SH = (1 << k); // this stage's shift = 2^k
// shamt[k]==0 -> pass; rotate -> wrap; right -> fill sign/0; left -> fill 0.
assign stage[k+1] =
(!shamt[k]) ? stage[k] :
(mode == 2'b10) ? (dir ? {stage[k][SH-1:0], stage[k][WIDTH-1:SH]}
: {stage[k][WIDTH-1-SH:0], stage[k][WIDTH-1:WIDTH-SH]}) :
(dir) ? {{SH{sign_fill}}, stage[k][WIDTH-1:SH]}
: {stage[k][WIDTH-1-SH:0], {SH{1'b0}}};
end
endgenerate
assign data_out = stage[SHW];
endmodule module barrel_shifter_tb;
parameter WIDTH = 32;
parameter SHW = 5;
reg [WIDTH-1:0] data_in;
reg [SHW-1:0] shamt;
reg dir;
reg [1:0] mode;
wire [WIDTH-1:0] data_out;
reg [WIDTH-1:0] exp;
integer m, r, s, errors;
barrel_shifter #(.WIDTH(WIDTH), .SHW(SHW)) dut
(.data_in(data_in), .shamt(shamt), .dir(dir), .mode(mode), .data_out(data_out));
// Reference model as a function of the current inputs.
function [WIDTH-1:0] ref_model;
input [WIDTH-1:0] d; input integer sh; input rt; input [1:0] md;
begin
if (md == 2'b10)
ref_model = rt ? ((d >> sh) | (d << (WIDTH - sh))) // rotate right
: ((d << sh) | (d >> (WIDTH - sh))); // rotate left
else if (!rt) ref_model = d << sh; // left logical
else if (md == 2'b01) ref_model = $signed(d) >>> sh; // right arithmetic
else ref_model = d >> sh; // right logical
end
endfunction
initial begin
errors = 0;
data_in = 32'hF3A5_0F0F; // MSB set: signed negative
for (m = 0; m < 3; m = m + 1)
for (r = 0; r < 2; r = r + 1)
for (s = 0; s < WIDTH; s = s + 1) begin // EXHAUSTIVE over shamt
mode = m[1:0]; dir = r[0]; shamt = s[SHW-1:0];
#1;
exp = ref_model(data_in, s, r[0], m[1:0]);
if (data_out !== exp) begin
$display("FAIL: mode=%b dir=%b s=%0d out=%h exp=%h",
mode, dir, s, data_out, exp);
errors = errors + 1;
end
end
// Directed: -8 arithmetic-right by 1 must be -4, not a huge positive.
data_in = -32'sd8; mode = 2'b01; dir = 1'b1; shamt = 5'd1; #1;
if ($signed(data_out) !== -32'sd4) begin
$display("FAIL: arith -8>>>1 = %0d exp=-4", $signed(data_out));
errors = errors + 1;
end
if (errors == 0) $display("PASS: barrel_shifter correct for all shamt/mode/dir");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleVHDL makes the signedness the most explicit of the three, because numeric_std forces you to name signed vs unsigned before you can shift. shift_left/shift_right on an unsigned value fill with 0 (logical); shift_right on a signed value sign-extends (arithmetic); rotate_left/rotate_right wrap. So the mode literally chooses the type you cast to — the arithmetic-vs-logical decision is impossible to make by accident.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity barrel_shifter is
generic ( WIDTH : positive := 32 );
port (
data_in : in std_logic_vector(WIDTH-1 downto 0);
shamt : in std_logic_vector(natural(ceil(log2(real(WIDTH))))-1 downto 0);
dir : in std_logic; -- '0' left, '1' right
mode : in std_logic_vector(1 downto 0); -- 00 logical, 01 arith, 10 rotate
data_out : out std_logic_vector(WIDTH-1 downto 0)
);
end entity;
architecture rtl of barrel_shifter is
begin
process (all)
variable n : natural;
begin
n := to_integer(unsigned(shamt)); -- the variable amount
if mode = "10" then -- ROTATE (wrap, no data lost)
if dir = '0' then
data_out <= std_logic_vector(rotate_left (unsigned(data_in), n));
else
data_out <= std_logic_vector(rotate_right(unsigned(data_in), n));
end if;
elsif dir = '0' then -- LEFT (fill 0 at bottom)
data_out <= std_logic_vector(shift_left (unsigned(data_in), n));
elsif mode = "01" then -- RIGHT ARITHMETIC: cast SIGNED
data_out <= std_logic_vector(shift_right(signed(data_in), n)); -- sign-extends
else -- RIGHT LOGICAL: cast UNSIGNED
data_out <= std_logic_vector(shift_right(unsigned(data_in), n)); -- fills 0
end if;
end process;
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity barrel_shifter_tb is
end entity;
architecture sim of barrel_shifter_tb is
constant WIDTH : positive := 32;
constant SHW : positive := 5; -- = clog2(WIDTH)
signal data_in, data_out : std_logic_vector(WIDTH-1 downto 0);
signal shamt : std_logic_vector(SHW-1 downto 0);
signal dir : std_logic;
signal mode : std_logic_vector(1 downto 0);
-- Reference model mirrors the DUT with independent numeric_std calls.
function ref_model(d : std_logic_vector; n : natural;
rt : std_logic; md : std_logic_vector) return std_logic_vector is
begin
if md = "10" then
if rt = '0' then return std_logic_vector(rotate_left (unsigned(d), n));
else return std_logic_vector(rotate_right(unsigned(d), n)); end if;
elsif rt = '0' then return std_logic_vector(shift_left (unsigned(d), n));
elsif md = "01" then return std_logic_vector(shift_right(signed(d), n));
else return std_logic_vector(shift_right(unsigned(d), n)); end if;
end function;
begin
dut : entity work.barrel_shifter generic map (WIDTH => WIDTH)
port map (data_in => data_in, shamt => shamt, dir => dir, mode => mode, data_out => data_out);
stim : process
begin
data_in <= x"F3A50F0F"; -- MSB set: negative as signed
for m in 0 to 2 loop
for r in 0 to 1 loop
for s in 0 to WIDTH-1 loop -- EXHAUSTIVE over shamt
mode <= std_logic_vector(to_unsigned(m, 2));
dir <= '1' when r = 1 else '0';
shamt <= std_logic_vector(to_unsigned(s, SHW));
wait for 1 ns;
assert data_out = ref_model(data_in, s,
'1' when r = 1 else '0',
std_logic_vector(to_unsigned(m, 2)))
report "barrel_shifter mismatch" severity error;
end loop;
end loop;
end loop;
-- Directed: -8 arithmetic-right by 1 must sign-extend to -4.
data_in <= std_logic_vector(to_signed(-8, WIDTH));
mode <= "01"; dir <= '1'; shamt <= std_logic_vector(to_unsigned(1, SHW));
wait for 1 ns;
assert to_integer(signed(data_out)) = -4
report "arith -8 >> 1 did not sign-extend to -4" severity error;
report "barrel_shifter self-check complete" severity note;
wait;
end process;
end architecture;4b. The arithmetic-vs-logical right-shift bug — buggy vs fixed, in all three HDLs
Now the signature failure, shown as buggy vs fixed RTL in each language, then dramatized narratively in §7. The setting is a signed scaling path: a DSP block divides a signed value by 2^k by right-shifting it. The correct operation is an arithmetic right shift, which sign-extends and preserves the value's sign. The bug uses a logical right shift (>>), which fills the vacated top bits with 0 — so for a negative input it produces a large positive number instead of the (negative) scaled result. It is silent on positive-only stimulus and wrong the moment a negative sample flows through.
// BUGGY: divides a SIGNED value by 2^k using a LOGICAL right shift. For a
// negative input the vacated top bits fill with 0, so -8 >> 1 becomes
// a huge POSITIVE number instead of -4. Passes positive-only tests.
module scale_shift_bad #(parameter int WIDTH = 16) (
input logic signed [WIDTH-1:0] data_in,
input logic [3:0] k, // divide by 2^k
output logic signed [WIDTH-1:0] data_out
);
// `>>` is the LOGICAL shift: it fills 0 at the top even on a signed operand,
// so it destroys the sign — the wrong shift for signed data.
assign data_out = data_in >> k; // WRONG: logical, not arithmetic
endmodule
// FIXED: use the ARITHMETIC right shift `>>>` on a signed operand, which
// sign-extends: the vacated top bits copy the sign bit, so -8 >>> 1 = -4.
module scale_shift_good #(parameter int WIDTH = 16) (
input logic signed [WIDTH-1:0] data_in,
input logic [3:0] k,
output logic signed [WIDTH-1:0] data_out
);
// `>>>` on a SIGNED operand fills with the sign bit — the signed divide by 2^k.
assign data_out = data_in >>> k; // RIGHT: arithmetic, sign-preserving
endmodule module scale_shift_tb;
localparam int WIDTH = 16;
logic signed [WIDTH-1:0] data_in, data_out, exp;
logic [3:0] k;
int errors = 0;
// Bind to scale_shift_good to PASS; to _bad to watch negatives corrupt.
scale_shift_good #(.WIDTH(WIDTH)) dut (.data_in(data_in), .k(k), .data_out(data_out));
task check;
input signed [WIDTH-1:0] d; input [3:0] sh;
begin
data_in = d; k = sh;
#1;
// Reference: signed divide-by-2^k, floor toward -inf, == arithmetic shift.
exp = $signed(d) >>> sh;
assert (data_out === exp)
else begin $error("d=%0d k=%0d out=%0d exp=%0d", d, sh, data_out, exp); errors++; end
end
endtask
initial begin
check(16'sd64, 4'd2); check(16'sd100, 4'd3); // POSITIVE: bug is invisible here
check(-16'sd8, 4'd1); check(-16'sd4, 4'd1); // NEGATIVE: buggy >> gives huge +ve
check(-16'sd64, 4'd2); check(-16'sd1, 4'd1); // -1 >>> anything stays -1
check(-16'sd256,4'd4); check(-16'sd15, 4'd2); // floor-toward-neg-inf cases
if (errors == 0) $display("PASS: scale_shift is arithmetic (sign-preserving)");
else $display("FAIL: %0d mismatches (logical >> used on signed data?)", errors);
$finish;
end
endmoduleThe Verilog buggy/fixed pair is the same story. The bug is data_in >> k on signed data (logical fill); the fix is data_in >>> k with the operand declared signed so >>> sign-extends. Driving negative inputs — where logical and arithmetic diverge — is what surfaces it; positive-only stimulus never will.
// BUGGY: signed scaling done with a LOGICAL right shift. `>>` fills 0 at the
// top, so a negative input becomes a large positive result.
module scale_shift_bad #(parameter WIDTH = 16) (
input wire signed [WIDTH-1:0] data_in,
input wire [3:0] k,
output wire signed [WIDTH-1:0] data_out
);
assign data_out = data_in >> k; // WRONG: logical shift on signed data
endmodule
// FIXED: `>>>` on a signed operand is the ARITHMETIC shift — it sign-extends,
// so the sign is preserved and -8 >>> 1 == -4.
module scale_shift_good #(parameter WIDTH = 16) (
input wire signed [WIDTH-1:0] data_in,
input wire [3:0] k,
output wire signed [WIDTH-1:0] data_out
);
assign data_out = data_in >>> k; // RIGHT: arithmetic, operand is signed
endmodule module scale_shift_tb;
parameter WIDTH = 16;
reg signed [WIDTH-1:0] data_in;
reg [3:0] k;
wire signed [WIDTH-1:0] data_out;
reg signed [WIDTH-1:0] exp;
integer errors;
// Bind to _good to PASS; to _bad to observe negatives becoming huge positives.
scale_shift_good #(.WIDTH(WIDTH)) dut (.data_in(data_in), .k(k), .data_out(data_out));
task check;
input signed [WIDTH-1:0] d; input [3:0] sh;
begin
data_in = d; k = sh;
#1;
exp = $signed(d) >>> sh; // arithmetic reference
if (data_out !== exp) begin
$display("FAIL: d=%0d k=%0d out=%0d exp=%0d", d, sh, data_out, exp);
errors = errors + 1;
end
end
endtask
initial begin
errors = 0;
check(16'sd64, 4'd2); check(16'sd100, 4'd3); // POSITIVE: bug invisible
check(-16'sd8, 4'd1); check(-16'sd4, 4'd1); // NEGATIVE: exposes it
check(-16'sd64, 4'd2); check(-16'sd1, 4'd1); // -1 stays -1
check(-16'sd256,4'd4); check(-16'sd15, 4'd2); // floor toward -inf
if (errors == 0) $display("PASS: scale_shift is arithmetic (sign-preserving)");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleIn VHDL the mistake wears its cause on its sleeve: the buggy version casts to unsigned before shifting (a logical shift that fills 0), the fixed version casts to signed (an arithmetic shift that sign-extends). Because numeric_std forces you to name the interpretation, the wrong-fill bug looks deliberate in review — which is exactly why it is caught faster in VHDL.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
-- BUGGY: scales a SIGNED value by casting to UNSIGNED before shift_right, so the
-- fill is 0 (logical). A negative input becomes a large positive result.
entity scale_shift_bad is
generic ( WIDTH : positive := 16 );
port (
data_in : in std_logic_vector(WIDTH-1 downto 0);
k : in natural range 0 to WIDTH-1;
data_out : out std_logic_vector(WIDTH-1 downto 0)
);
end entity;
architecture rtl of scale_shift_bad is
begin
-- unsigned shift_right fills 0 at the top — WRONG for signed data.
data_out <= std_logic_vector(shift_right(unsigned(data_in), k));
end architecture;
-- FIXED: cast to SIGNED so shift_right sign-extends — the arithmetic divide by 2^k.
entity scale_shift_good is
generic ( WIDTH : positive := 16 );
port (
data_in : in std_logic_vector(WIDTH-1 downto 0);
k : in natural range 0 to WIDTH-1;
data_out : out std_logic_vector(WIDTH-1 downto 0)
);
end entity;
architecture rtl of scale_shift_good is
begin
-- signed shift_right copies the sign bit into the vacated top bits.
data_out <= std_logic_vector(shift_right(signed(data_in), k));
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity scale_shift_tb is
end entity;
architecture sim of scale_shift_tb is
constant WIDTH : positive := 16;
signal data_in, data_out : std_logic_vector(WIDTH-1 downto 0);
signal k : natural range 0 to WIDTH-1;
procedure check(signal di : out std_logic_vector; signal kk : out natural;
signal dout : in std_logic_vector;
d : integer; sh : natural) is
variable expv : integer;
begin
di <= std_logic_vector(to_signed(d, WIDTH));
kk <= sh;
wait for 1 ns;
-- Arithmetic reference: signed floor-divide by 2^sh.
expv := to_integer(shift_right(to_signed(d, WIDTH), sh));
assert to_integer(signed(dout)) = expv
report "scale_shift mismatch: not arithmetic (sign lost?)" severity error;
end procedure;
begin
-- Bind to scale_shift_good to PASS; to _bad to observe negatives corrupt.
dut : entity work.scale_shift_good generic map (WIDTH => WIDTH)
port map (data_in => data_in, k => k, data_out => data_out);
stim : process
begin
check(data_in, k, data_out, 64, 2); check(data_in, k, data_out, 100, 3); -- positive
check(data_in, k, data_out, -8, 1); check(data_in, k, data_out, -4, 1); -- NEGATIVE
check(data_in, k, data_out, -64, 2); check(data_in, k, data_out, -1, 1); -- -1 stays -1
check(data_in, k, data_out,-256, 4); check(data_in, k, data_out, -15, 2); -- floor -inf
report "scale_shift self-check complete" severity note;
wait;
end process;
end architecture;Across all three languages the lesson is one sentence: a right shift on signed data must sign-extend — >>> / $signed in SystemVerilog and Verilog, shift_right(signed(...)) in VHDL — because a logical >> fills 0 where the sign bit belonged and turns a negative into a huge positive.
5. Verification Strategy
A shifter is combinational, and its correctness is a function you can check against a reference model — and because the legal shift amounts are only 0 .. WIDTH-1, you can check them exhaustively rather than sample. The single invariant that captures a correct shifter is:
For every shift amount
0 .. WIDTH-1and every mode,data_outequals the reference shift/rotate ofdata_in— with the arithmetic right shift sign-extending (so it agrees on NEGATIVE inputs), the logical right shift filling 0, and the rotate losing no bits.
Everything below is that invariant made checkable, and it maps directly onto the §4 testbenches.
- Exhaustive
shamtsweep per mode/direction (self-checking). Loopshamtover allWIDTHlegal values for eachmode(logical/arithmetic/rotate) and eachdir, and assertdata_out === referenceevery time. Becauseshamthas onlyWIDTHlegal values, this is complete, not sampled — the §4a testbenches do exactly this with a reference-model function: SVassert (data_out === ref_model(...)), Verilogif (data_out !== exp) $display("FAIL"), VHDLassert data_out = ref_model(...) report ... severity error. - Verify the arithmetic right shift on NEGATIVE operands. This is the point of the page, so it is the point of verification: the logical and arithmetic right shifts agree on positive data and disagree on negatives, so a positive-only sweep cannot tell them apart. The reference for the arithmetic case must itself sign-extend (
$signed(d) >>> s, orshift_right(signed(d), s)), and the stimulus must include values with the MSB set — the §4 testbenches seeddata_inwith a negative value and add a directed-8 >>> 1 == -4check. A testbench that only drives positive data contains the bug in its own coverage. - Verify rotate wraps and loses no bits. The rotate invariant is that the multiset of bits is preserved — nothing falls off. Check
rotateagainst(d >> s) | (d << (N-s))(right) /(d << s) | (d >> (N-s))(left), and add the cornerrotate by 0(identity) androtate by N(also identity, ifshamtcan reach it) — a rotate that drops bits instead of wrapping fails these. - Boundary shift amounts, including
0and≥ WIDTH. Driveshamt = 0(must be the identity — a common off-by-one is a stage that shifts when it should pass), the maximumWIDTH-1, and — ifshamtis wider thanlog2(WIDTH)— a value≥ WIDTH, confirming the defined behaviour (all-zeros for logical, all-sign for arithmetic, or a constrained index). This surfaces the shift-amount-width bug of §6. - Parameter-generic verification (
WIDTH = 8, 16, 32). A parameterized shifter must be verified generic, not assumed generic. Re-run the exhaustive sweep at severalWIDTHs; the number of stages islog2(WIDTH), so a form that passes atWIDTH=32can still be wrong atWIDTH=8if a stage count or a slice bound was hardcoded. Width-genericity is a property you prove, not assume. - Expected waveform. Because the shifter has no clock, "correct" on a waveform is immediate: as
shamtsteps0 → 1 → 2 → …,data_outtracks the correspondingly-shifteddata_incombinationally within the propagation delay. The visual signature of the §7 bug is an arithmetic right shift whose top bits go to 0 on a negative input (the value jumps positive) instead of filling with 1s — a mismatch you see the instant a negative operand appears.
6. Common Mistakes
Logical shift where an arithmetic shift was meant (the signedness trap). The signature bug of this page. >> (logical) fills the vacated top bits with 0; >>> (arithmetic, on a signed operand) fills them with the sign bit. On signed data a logical right shift is arithmetically wrong: -8 >> 1 should be -4 but a logical shift produces a large positive number, because it clears the sign bit instead of extending it. This is the exact signedness trap of the adder (§5.1) and comparator (§1.5) reappearing on the shifter: the fill on a right shift is a signedness decision — sign-extend signed data, zero-fill unsigned data. It is silent on positive-only stimulus and wrong the moment negatives flow through. (Full post-mortem in §7; buggy-vs-fixed RTL for all three HDLs in §4b.)
Off-by-one or wrong direction in the shift amount. A stage that shifts when shamt's bit is 0 (or vice-versa) gives a shift off by that power of two; a left/right direction bit inverted gives the mirror-image result. The classic tell is that shamt = 0 is not the identity — a correct shifter must pass data_in through unchanged when the amount is zero. Always test the shamt = 0 corner explicitly; it catches the whole class.
Treating a variable shift as free wiring. A constant shift (data_in << 3) is zero logic — just relabelled wires. A variable shift, where shamt is a signal, must build the whole log2(N)-stage mux tree, because the tool must be able to produce every amount. Assuming a variable shift is as cheap as a constant one underestimates a 32-bit barrel shifter by 160 muxes and a 5-deep mux delay. When a variable shift lands on a critical path, that log2(N) depth is real — it is not "free like a shift."
Confusing rotate with shift. A shift loses the bits that fall off one end and fills the vacated end (with 0 or sign); a rotate wraps — the bits that fall off one end re-enter the other, and no bits are lost. Using a shift where a rotate was intended (or vice-versa) silently drops or duplicates data. Rotate is {data[N-1-k:0], data[N-1:N-k]}, not data << k; verification must check that the rotated result's bits are a wrap, not a fill.
Shift-amount width — shifting by ≥ N. shamt needs exactly log2(N) bits to name amounts 0 .. N-1. If it is wider, it can request a shift by ≥ N, whose meaning ("everything falls off") must be defined on purpose — a logical shift by ≥ N is all-zeros, an arithmetic right shift by ≥ N is all-sign-bits. Feeding a too-wide shamt into a shifter whose stages only cover log2(N) bits either truncates the amount silently or produces an undefined result. Constrain shamt to log2(N) bits, or handle the ≥ N case explicitly.
7. DebugLab
The scaling path that flipped negatives positive — a logical shift used where arithmetic was meant
The engineering lesson: a right shift on signed data must sign-extend, not zero-fill — logical (>>) and arithmetic (>>>) right shifts agree on positive data and disagree on negatives, so the wrong choice is invisible until real negative data flows through. The tell is sign-dependent corruption: if a scaling or divide-by-power-of-two path is correct on positive operands and flips negatives into large positives, suspect a logical shift used where an arithmetic one was meant. Two habits make it impossible, and they are identical across SystemVerilog, Verilog, and VHDL: choose the shift by the data's signedness — arithmetic (>>> on a signed operand, shift_right(signed(...))) for signed data, logical (>>, shift_right(unsigned(...))) for unsigned data — never by which operator you typed first, and in verification, drive negative inputs and check against a signed reference so the -8 >>> 1 == -4 case (where logical and arithmetic diverge) is actually exercised.
8. Interview Q&A
9. Exercises
Design and reasoning exercises — no syntax drills. Each rehearses the "it's a mux tree" and "which fill do I mean?" habits.
Exercise 1 — Trace the mux tree
For an 8-bit barrel shifter (3 stages, shifting by 1/2/4), trace data_in = 8'b1010_1100 shifted left by shamt = 5. Show the intermediate value after each of the three stages, stating for each whether the stage shifts or passes (from the bits of 5 = 3'b101) and by how much. Confirm the final result equals data_in << 5 with zeros filled at the bottom. Then repeat for a logical right shift by 5 (fill 0 at the top) and a rotate right by 5 (wrap), and note which bits survive in each.
Exercise 2 — Predict the two right shifts
For an 8-bit signed value data_in = 8'hF0 (i.e. -16), give the result of (a) a logical right shift by 2 (>>) and (b) an arithmetic right shift by 2 (>>>), both as an 8-bit pattern and as a signed decimal. Explain why they differ, which one is the correct "divide by 4" for signed data, and what the two results would be if data_in were instead 8'h30 (+48) — and why the two shifts agree in that case. Then state the single stimulus property a testbench must have to tell the two shifts apart.
Exercise 3 — Cost the shifter
You must add a shift unit to a 32-bit ALU. Case (a): the shift amount is a constant baked into each instruction's decode. Case (b): the shift amount is a register value, variable each cycle. For each case, state how much logic the shifter costs (in gates/muxes and in delay), and explain the difference. Then, for case (b), give two architectural options if the resulting log2(N)-deep mux tree lands on the critical path, and name the cost each introduces (latency or area).
Exercise 4 — Build a funnel shifter on paper
A funnel (or rotate-through) shifter takes a 2N-bit input {high, low} and a shift amount, and outputs the N-bit window that starts shamt bits into the concatenation — it generalizes shift and rotate. Describe how you would build it from the same log2(N)-stage mux-tree idea, what the "fill" becomes (hint: it is supplied by the other half of the 2N-bit input), and how you would obtain (a) a logical left shift, (b) a logical right shift, and (c) a rotate as special cases of the funnel by choosing what to feed into high and low.
10. Related Tutorials
Continue in RTL Design Patterns (sibling and forward links unlock as they ship):
- Saturation & Rounding — Chapter 5; the arithmetic right shift is the divide-by-
2^ka fixed-point datapath rounds and saturates around — the signed fill from this page feeds directly into rounding. - ALU Construction — Chapter 5; this barrel shifter is the shift unit of the ALU, sharing the result mux with the arithmetic and logic units.
- Datapath / Control Split — Chapter 5; the shifter is pure datapath, and the mode/direction/
shamtare the control signals an FSM or decoder drives into it.
In-track dependencies (patterns this one builds on):
- Multiplexers (2:1, N:1, one-hot) — Chapter 1.1; a barrel shifter is a tree of these 2:1 muxes — each stage is a rank of muxes selected by one bit of
shamt. - Adders & Subtractors — Chapter 5.1; the same signedness trap — carry-out vs signed overflow there, logical vs arithmetic shift here — and both are decided by the data's declared signedness.
- Multipliers — Chapter 5.2; a shift-by-a-constant is how partial products are aligned, and a multiply by a power of two is a left shift.
- Comparators — Chapter 1.5; the earliest appearance of the signed-vs-unsigned decision that this page's arithmetic-vs-logical shift repeats.
- Encoding & Conversions — Chapter 5; two's-complement and sign-extension are exactly the fill an arithmetic right shift replicates.
Backward / method:
- The RTL Design Mindset — Chapter 0.2; the Interface → State → Datapath → Control → Verification lenses this page applied to the shifter (pure datapath; the shift mode is control).
- What Is an RTL Design Pattern? — Chapter 0.1; why the shifter earns the name "pattern" — a recurring need, a reusable form (the mux tree), a synthesis reality (log2(N) muxes), and a signature failure (logical vs arithmetic).
Verilog v1 prerequisites (the grammar this pattern transcribes into):
- Shift Operators — the
<<,>>, and>>>operators this pattern builds the barrel shifter from, and where logical vs arithmetic lives. - Physical Data Types (signed/unsigned) — the declared signedness that decides whether a right shift should fill 0 or the sign bit.
- Arithmetic Operators — the divide-by-
2^kthat an arithmetic right shift implements, and the multiply-by-2^ka left shift implements. - Bitwise Operators — the concatenation, replication, and OR used to build the per-stage fill and the rotate wrap.
11. Summary
- A barrel shifter is a mux tree, not a loop. Any shift by
shamtis the sum of the powers of two whose bits are set, so you buildlog2(N)stages — stagekshifts by2^kor passes through under bitkofshamt— each a rank of 2:1 muxes (§1.1). The shifts compose to exactlyshamt, so any amount0..N-1happens in one combinational cycle, delay~log2(N), instead of the N-cycle "shift one place, N times" loop. - The four flavours are one tree with a different fill. Logical left fills 0 at the bottom; logical right fills 0 at the top; arithmetic right fills copies of the sign bit at the top (the signed divide-by-
2^kthat preserves sign); rotate fills with the bits that fell off the other end (no data lost). The structure is identical — only the vacated-bit source changes. - A variable shift builds the tree; a constant shift is free.
data_in << 3(constant) is relabelled wires, zero logic. A variable shift, whereshamtis a signal, must build the full log2(N)-stage mux tree — real area (log2(N)·Nmuxes) and real delay. Do not cost a variable shift as if it were a constant one. - Logical vs arithmetic on a right shift is a SIGNEDNESS decision.
>>(logical) fills 0;>>>(arithmetic, on a signed operand) sign-extends. They agree on positive data and disagree on negatives —-8 >> 1gives a huge positive,-8 >>> 1gives-4. Right-shifting signed data with a logical shift silently corrupts every negative value (§7); it is the Chapter-5 signedness trap again. Choose the shift that matches the data's signedness. - Verify exhaustively, on negatives, generic in width. Sweep
shamtover all0..N-1for each mode/direction and checkdata_outagainst a reference; drive negative inputs so the arithmetic shift's sign-extension is actually exercised (the-8 >>> 1 == -4corner); test rotate-wraps,shamt = 0identity, and the≥ Namount; re-run parameter-generic acrossWIDTH = 8, 16, 32. Self-checking testbenches shown here in SystemVerilog, Verilog, and VHDL.