Barrel Shifter
Shifting by a variable amount in O(log n) delays.
Problem
How do you shift a value by a variable number of positions in one clock cycle, not one position per cycle?
How it works
A barrel shifter decomposes the shift amount into powers of 2 and uses log₂(n) stages of multiplexers. Each stage conditionally shifts by 2k positions based on bit k of the shift amount.
For an 8-bit barrel shifter with shift amount S[2:0]:
• Stage 0 (S[0]): each bit has a 2:1 MUX choosing between its current position and the position shifted by 1.
• Stage 1 (S[1]): each bit has a 2:1 MUX choosing between its current position and the position shifted by 2.
• Stage 2 (S[2]): each bit has a 2:1 MUX choosing between its current position and the position shifted by 4.
The shift amount 5 = 101₂ activates stages 0 and 2, shifting by 1 then by 4, for a total shift of 5. Total delay: log₂(n) MUX delays, regardless of the shift amount.
Area: n × log₂(n) multiplexers. For 32-bit: 32 × 5 = 160 MUXes.
For an 8-bit barrel shifter with shift amount S[2:0]:
• Stage 0 (S[0]): each bit has a 2:1 MUX choosing between its current position and the position shifted by 1.
• Stage 1 (S[1]): each bit has a 2:1 MUX choosing between its current position and the position shifted by 2.
• Stage 2 (S[2]): each bit has a 2:1 MUX choosing between its current position and the position shifted by 4.
The shift amount 5 = 101₂ activates stages 0 and 2, shifting by 1 then by 4, for a total shift of 5. Total delay: log₂(n) MUX delays, regardless of the shift amount.
Area: n × log₂(n) multiplexers. For 32-bit: 32 × 5 = 160 MUXes.
Key insightBy decomposing the shift into power-of-2 stages, a barrel shifter achieves any shift amount in O(log n) time instead of O(n).