Digital Design / Module 2: Combinational building blocks
11. Barrel shifters and glitches
Know why combinational outputs can pulse before settling.
See it move
Barrel shifters
A barrel shifter moves a word by any amount in one cycle. It would be costly to build a giant mux for each output bit, so we use stages. Each stage shifts by a power of two, or passes the word through, according to one bit of the shift amount. An 8-bit shifter has three stages: shift by 1, 2 and 4. A shift of 5 means stages 1 and 3 are active. That gives log2(N) levels of muxes, with N muxes in each.
Shifting left by k multiplies by 2^k. Logical right shift fills with zeros, whereas arithmetic right shift copies the sign bit, so it divides a signed value by 2^k, rounding towards negative infinity.
Why outputs glitch
Paths through a circuit have different delays, so while inputs change the output may briefly show wrong values. A static hazard is a brief pulse when the output should stay constant. A dynamic hazard is several transitions when it should change just once.
Take F = AB + A'C with B = C = 1. F should be 1 whatever A does. But when A falls, AB turns off immediately, whereas A'C needs an extra inverter delay to turn on. For a moment both terms are 0, and F dips.
Why this usually doesn't matter
A flop samples only at the clock edge. If timing is met, all glitches have died away before the edge, and synchronous design relies on exactly this. The glitch still costs some power, however, since it charges and discharges capacitance.
When it matters a lot
Never use combinational logic as a clock or an asynchronous reset. Any glitch there is seen as a real edge, with immediate effect. Likewise, signals crossing into another should come straight from a flop.
Common mistake
Adding consensus terms to "fix" glitches in ordinary synchronous logic. The synthesis tool may remove them anyway, and they aren't needed. Fix the structure: register the signal before it goes anywhere sensitive.
One more to try
Key ideas
- A barrel shifter uses log2(N) mux stages.
- Unequal path delays cause static and dynamic hazards.
- Registers hide glitches, provided timing is met; never clock from raw combinational logic.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
assign y = a >>> n;
Why it failed
>> always fills with zeros, so the sign bit is lost and a negative value turns positive. >>> on a signed value copies the sign bit into the new positions, which keeps the division correct.
Interview questions
coreWhy not use combinational output as a clock?
Glitches create false edges, and the path is hard to time.
basicIn an 8-bit barrel shifter with stages for shifts of 1, 2 and 4, which stages are active for a shift of 6?
6 is binary 110, so the shift-by-2 and shift-by-4 stages are active and the shift-by-1 stage passes the word through. Each stage is controlled by one bit of the shift amount, and the shifts add up.
basicWhat does shifting an unsigned value left by 3 do arithmetically, and when does it go wrong?
It multiplies by 2^3 = 8, because each bit moves to a position worth eight times as much. It goes wrong when 1s are shifted out of the top, which is unsigned overflow; for example, 8-bit 40 << 3 should be 320 but wraps to 64. Size the result wider when the product must be kept.
coreHow many 2:1 muxes and stages does a 32-bit barrel shifter need?
It needs log2(32) = 5 stages, shifting by 1, 2, 4, 8 and 16. Each stage has one 2:1 mux per bit, so 5 × 32 = 160 muxes. The delay is five mux levels whatever the shift amount.
coreWhat do u >>> 2 and s >>> 2 give for these two registers?
reg [7:0] u = 8'hF0; reg signed [7:0] s = 8'shF0; // u >>> 2 ? s >>> 2 ?
u >>> 2 gives 8'h3C and s >>> 2 gives 8'hFC. The arithmetic shift operator only copies the sign bit when the operand is signed; on an unsigned operand it acts as a logical shift and fills with zeros. The operator alone does not make a shift arithmetic.
coreA signed 8-bit register holds -7. What is -7 >>> 1, and is that the same as -7 / 2 in Verilog?
-7 >>> 1 gives -4, because an arithmetic right shift rounds towards negative infinity. Verilog's -7 / 2 gives -3, because integer division truncates towards zero. Swapping a divide for a shift on signed data therefore changes results for negative odd values.
coreF = AB + A'C with B = C = 1. Explain the glitch when A falls from 1 to 0, and how a consensus term would remove it.
F should stay 1. When A falls, AB turns off at once, but A'C must wait for the inverter on A, so for a moment both terms are 0 and F dips: a static-1 hazard. The consensus term BC is 1 throughout and holds F high. In synchronous logic this usually does not matter, since the flop samples after everything settles, but the dip still burns power.
advancedHow does this code rotate an 8-bit value left by a variable amount?
wire [7:0] x;
wire [2:0] amt;
wire [15:0] t = {x, x} << amt;
wire [7:0] rot = t[15:8];Concatenating x with itself gives a 16-bit word where shifting left by amt moves amt bits from the lower copy into the upper byte. The upper byte is then x with its top amt bits wrapped round to the bottom, which is a rotate left. For x = 1001_0110 and amt = 3 it gives 1011_0100. It works for every amt from 0 to 7, with no special case for 0.
advancedThis counter is meant to count 0 to 9. What is wrong with it?
wire clr_n = ~(cnt == 4'd9); always @(posedge clk or negedge clr_n) if (!clr_n) cnt <= 4'd0; else cnt <= cnt + 4'd1;
The clear comes from combinational decode of cnt and drives an asynchronous reset, so the moment cnt reaches 9 it is cleared again. 9 never lasts a whole cycle, and the counter actually cycles through 0 to 8. Worse, a decode of several changing bits can glitch on other transitions and fire a false reset. Use a synchronous clear: cnt <= (cnt == 4'd9) ? 4'd0 : cnt + 4'd1;.