Barrel shifters

3.3.11 · Hardware › Combinational Circuits

A barrel shifter ek combinational circuit hai jo ek data word ko ek hi clock cycle mein kisi bhi number of bit positions se shift (ya rotate) karta hai — sirf multiplexers use karke — koi clocking nahi, koi iteration nahi.

Processors SHL R1, 5 ya floating-point normalisation, address scaling, aur multiply/divide-by-powers-of-2 jaise instructions har cycle execute karte hain. Ek multi-cycle shifter pipeline ko stall kar deta. Hum chahte hain ek single-cycle, purely combinational device.

WHAT is it, precisely?

HOW is it structured?

Key insight: shift amount ko bits mein decompose karo.

$S = \sum_{i = 0}^{k - 1} s_{i} 2^{i}, k = lo g_{2} n$

Stage $i$ bit $s_{i}$ se control hota hai.
Agar $s_{i} = 1$ , toh stage $i$ apna input $2^{i}$ se shift karta hai; agar $s_{i} = 0$ , toh data ko unchanged pass karta hai.
Saare $k$ stages cascade karo → total shift $= \sum s_{i} 2^{i} = S$ . ✅

Deriving the multiplexer equation from scratch

Stage $i$ consider karo, jo $s_{i} = 1$ hone par left mein $2^{i}$ se shift karta hai (0s se fill karta hai). Stage input $A = a_{n - 1} \dots a_{0}$ aur output $B = b_{n - 1} \dots b_{0}$ maano.

"Left shift by $2^{i}$ " ka matlab kya hai? Output bit $j$ , input bit $j - 2^{i}$ leta hai: $b_{j} = a_{j - 2^{i}} (and b_{j} = 0 if j - 2^{i} < 0)$

Jab $s_{i} = 0$ , pass through karo: $b_{j} = a_{j}$ .

Dono cases ko $s_{i}$ se select hone wale 2:1 mux ke saath combine karo:

For a rotate, jo bits end se bahar girti hain woh 0 se replace hone ki jagah wrap around ho jaati hain: $b_{j} = \overline{s_{i}} a_{j} + s_{i} a_{(j - 2^{i}) mod n}$

Counting the hardware (the 80/20 that matters)

Number of stages $=== lo g_{2} n ==$ .
Har stage mein $n$ muxes hote hain (har output bit ke liye ek).
Total muxes $=== n lo g_{2} n ==$ .
Propagation delay $=== lo g_{2} n == \times (delay of one 2:1 mux)$ — sirf logarithmically badhta hai, isliye yeh fast hai.

Worked Example 1 — Shift left by 13 on an 8… wait, 16-bit word

$n = 16$ lo, toh $k = lo g_{2} 16 = 4$ stages (shift by 1, 2, 4, 8). Shift amount $S = 13$ .

Step 1 — $S$ ko binary mein likho. $13 = 110 1_{2}$ , toh $s_{3} s_{2} s_{1} s_{0} = 1101$ . Kyun? Control bits shift amount ke binary digits HAIN.

Step 2 — matching stages ko ON karo.

$s_{0} = 1$ → shift by $2^{0} = 1$
$s_{1} = 0$ → pass through
$s_{2} = 1$ → shift by $2^{2} = 4$
$s_{3} = 1$ → shift by $2^{3} = 8$

Step 3 — total shift $= 1 + 4 + 8 = 13$ . ✅ Yeh step kyun? Confirm karta hai ki sum-of-powers decomposition requested shift ke barabar hai.

Input ke saath trace karo A = 0000 0000 0000 0001 (value 1):

After stage 0 (shift 1): ...0010
Stage 1 (pass): ...0010
Stage 2 (shift 4): ...0010 0000
Stage 3 (shift 8): 0010 0000 0000 0000 = $2^{13} = 8192$ . ✅ ( $1 \times 2^{13}$ .)

Worked Example 2 — Rotate right by 3 on a 4-bit word

$n = 4$ , $k = 2$ stages. Rotate-right amount $S = 3 = 1 1_{2}$ , toh $s_{1} s_{0} = 11$ : pehle 1 se rotate phir 2 se.

Input $A = 1000$ (bit 3 set).

Rotate right by 1 → 0100 Kyun? $b_{j} = a_{(j + 1) mod 4}$ ; jo bit neeche se bahar jaati hai woh upar wrap ho jaati hai.
Rotate right by 2 → 0001 Kyun? Mod-wrap dobara $2^{1} = 2$ se apply karna.

Total rotate-right by 3 of 1000 = 0001. Seedha check karo: 1000 ko right 3 rotate karna = 0001. ✅

Common Mistakes

Active Recall

Recall Q: Sirf

$lo g_{2} n$ stages kyun? Kyunki shift amount (0… $n - 1$ ) ek $lo g_{2} n$ -bit binary number hai; har bit ek aisa stage select karta hai jo us power of two se shift karta hai, aur unka sum koi bhi amount reproduce kar deta hai.

Recall Q: Left-shift stage

$i$ ke liye per-bit mux equation likho. $b_{j} = \overline{s_{i}} a_{j} + s_{i} a_{j - 2^{i}}$ (with $a_{< 0} = 0$ ).

Recall Q:

$n = 32$ ke liye mux count aur delay? Muxes $= n lo g_{2} n = 32 \times 5 = 160$ ; delay $= 5$ mux delays.

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho tum ek shelf par kitabon ki row ko kisi bhi number of spaces se move karna chahte ho, lekin tumhe sirf 1, 2, 4, ya 8 ke jumps mein push karne ki permission hai. Unhe 13 spaces move karne ke liye, tum 8 ka jump karte ho, phir 4 ka, phir 1 ka (total 13!). Har jump ek alag "helper" hai jise tum ON ya OFF kar sakte ho. Sirf 4 helpers se tum kitabon ko 0 se 15 tak kisi bhi amount se ek saath slide kar sakte ho, ek ek space nudge karne ki jagah. Yahi barrel shifter hai — ON/OFF sliders ka ek stack, har power of two ke liye ek.

Connections

Multiplexers — fundamental building block (2:1 mux per bit).
Binary Number Representation — shift amount ka powers of two mein decomposition.
Combinational Circuits — koi clock nahi, purely input-driven.
Shift and Rotate Operations — ALU operations jo yeh implement karta hai.
Logarithmic Delay Structures — carry-lookahead / prefix networks jaisa hi $lo g n$ idea.
Floating Point Normalization — fast shifters ka ek major real user.

What is a barrel shifter?

Ek combinational circuit jo ek word ko ek cycle mein kisi bhi amount se shift/rotate karta hai cascaded mux stages use karke, jahan har stage ek power of two se shift karta hai.

How many stages does an n-bit barrel shifter have?

lo g_{2} n

stages.

How many 2:1 muxes total?

n lo g_{2} n

What is the propagation delay in terms of mux delays?

lo g_{2} n

mux delays (logarithmic).

Per-bit equation of a left-shift stage i?

b_{j} = \overline{s_{i}} a_{j} + s_{i} a_{j - 2^{i}}

How wide is the shift-amount control input?

⌈ lo g_{2} n ⌉

bits.

Which stages are active to shift by 13?

8, 4, 1 wale stages (kyunki

13 = 110 1_{2}

Difference between shift and rotate stage inputs?

Shift khaali hue bits ko 0 se fill karta hai; rotate unhe wrap around karta hai (

(j - 2^{i}) mod n

Why powers of two per stage instead of 1 each?

Koi bhi amount distinct powers of two ka sum hai, isliye

lo g_{2} n

layers saare amounts cover kar leti hain.

Rotate-right-by-3 of 1000 (4-bit)?

0001.

The Core Idea

WHY do we need it?