Digital Electronics · lesson 9

Multipliers and Barrel Shifters

Array multiplication built from adders, and barrel shifters that shift or rotate by any amount in one pass using a chain of 2-to-1 muxes.

14 min read · Free, no login

Multiplication as repeated, shifted addition

Binary multiplication by hand uses exactly the long-multiplication method taught for decimal numbers: multiply the multiplicand by each bit of the multiplier in turn, shift each result left according to that bit's position, and add all the shifted results together. The only simplification binary brings is that each bit of the multiplier is either 0 or 1, so "multiply by this bit" is either "copy the multiplicand" or "write all zeros" – there is no digit-by-digit multiplication table to consult, only a decision and a shift. Each of these shifted, bit-gated copies of the multiplicand is called a partial product, and an array multiplier is a circuit built to generate and add all of them.

Worked example: 5 × 3

Let us multiply A = 0101 (5) by B = 0011 (3). Each partial product is A ANDed bit-by-bit with one bit of B, then shifted left by that bit's position:

  • PP0 = A · B0 = 0101 · 1 = 0101, shifted by 0 → 00101
  • PP1 = A · B1 = 0101 · 1 = 0101, shifted by 1 → 01010
  • PP2 = A · B2 = 0101 · 0 = 0000, shifted by 2 → 00000
  • PP3 = A · B3 = 0101 · 0 = 0000, shifted by 3 → 00000

Adding the four shifted rows: 00101 + 01010 + 00000 + 00000 = 01111, which is decimal 15 – correctly 5 × 3. Only two of the four partial products are actually nonzero here because B's top two bits are 0, but a general multiplier circuit cannot know that in advance and has to generate every row.

0 1 0 1 A = 5 0 0 1 1 × B = 3 0 0 1 0 1 PP0 (B0=1, shift 0) 0 1 0 1 0 PP1 (B1=1, shift 1) 0 0 0 0 0 PP2 (B2=0) 0 0 0 0 0 PP3 (B3=0) 0 1 1 1 1 Sum = 15
Each partial product is A gated by one bit of B, shifted left by that bit's position; summing all of them gives the product.

An array multiplier builds this directly in hardware: one row of AND gates per bit of B to form each partial product, and a grid of full adders to sum the shifted rows, with the carry from each full adder feeding into the adder diagonally below it. For n-bit operands this needs roughly n2 AND gates and n(n−1) full adders – it trades a large amount of hardware for a multiplication that completes in a bounded number of adder delays, rather than iterating one row at a time the way a simple sequential multiplier would.

Barrel shifters

A different but related problem is shifting – or rotating – a word by some number of bit positions given at run time. Shifting one bit position with a single mux stage is straightforward; shifting by an arbitrary amount using one mux per possible shift amount would need a number of muxes that grows linearly with the word width, which gets expensive fast. A barrel shifter instead shifts by any amount in log2(n) stages, by shifting in powers of two: an 8-bit barrel shifter has one stage that optionally shifts by 4, one that optionally shifts by 2, and one that optionally shifts by 1, and any shift amount from 0 to 7 is reached by choosing some combination of those three stages – exactly the way any number from 0 to 7 is a sum of a subset of 4, 2 and 1 in binary.

Input Shift by 4 sel S2 Shift by 2 sel S1 Shift by 1 sel S0 Output
Three stages, each either passing the word through unchanged or shifting it by its fixed power-of-two amount, combine to produce any shift from 0 to 7 in a fixed, small number of mux delays.

Each stage is built from one 2-to-1 mux per output bit: one mux input is the unshifted data from the previous stage, the other is that same data pre-wired shifted by the stage's fixed amount, and the stage's select bit (one bit of the overall shift amount) chooses between them. For a shift amount of, say, 5 (binary 101), the barrel shifter enables the "shift by 4" and "shift by 1" stages and bypasses "shift by 2," since 4+1=5. Because every stage is a fixed, pre-wired shift rather than a general one, and all three stages exist in hardware simultaneously, the total delay through the whole barrel shifter is only the delay of log2(n) muxes, regardless of which shift amount was requested – a flat, predictable cost that a sequential "shift one position at a time, k times" circuit cannot match once k gets large. A rotator is the same structure with wraparound wiring instead of zero-fill at the stage boundaries, which is why barrel shifters are usually described as supporting both shifts and rotates with no extra hardware cost.

Key takeaways

  • Binary multiplication generates one partial product per multiplier bit – the multiplicand, shifted and gated by that bit – then sums all the shifted rows.
  • An array multiplier builds this directly as a grid of AND gates and full adders, trading hardware for a bounded multiplication delay instead of iterating a row at a time.
  • A barrel shifter shifts by any amount in log2(n) mux stages, each stage optionally applying a fixed power-of-two shift.
  • The requested shift amount's bits directly select which stages are active, the same way any number is a sum of powers of two.
  • A rotator is a barrel shifter with wraparound wiring instead of zero-fill, at no extra hardware cost.