CMOS Multipliers

Multiplication is one of the most computationally intensive operations in digital signal processing, cryptography, and processor arithmetic units. In CMOS VLSI, efficient multiplier architectures directly impact system throughput and power consumption. The two fundamental architectures studied in this context are the array multiplier and the Wallace tree multiplier, each offering different tradeoffs between speed, area, and design regularity.

Core Concept: How Digital Multiplication Works

Multiplying two n-bit numbers A and B in hardware involves generating n partial products and summing them to get a 2n-bit result. Each partial product is formed by ANDing each bit of A with a single bit of B and shifting appropriately. For a 4-bit multiplier, there are four partial product rows, each shifted one position to the left relative to the previous. The key design challenge is how to sum these partial products efficiently.

Array Multiplier

In an array multiplier, the partial products are summed row by row using a cascade of full adders arranged in a two-dimensional array. Each row of full adders adds one partial product row to the accumulated sum from the rows above it. The first row is simply the partial products themselves, and each subsequent row adds the next partial product using a row of full adders that also propagates carries to the next stage.

The main advantage of the array multiplier is its regular, systematic structure, which maps well onto standard cell CMOS layouts and makes physical design straightforward. The primary disadvantage is that the critical path passes through all (n-1) adder rows sequentially, giving a total delay of O(n). For a 32-bit multiplier, this means the carry must ripple through 31 adder rows, which is unacceptably slow for modern processors.

Wallace Tree Multiplier

The Wallace tree multiplier reduces the partial products in parallel using a tree of carry save adders (CSA). A carry save adder takes three inputs and produces two outputs (a sum and a carry vector) without propagating carry at all. This allows multiple operands to be combined in parallel at each level of the tree. At each level, groups of three partial product terms are reduced to two terms using CSA units. The number of terms to be added reduces by a factor of 3/2 at each level, so the number of levels is O(log_{3/2}(n)), which grows logarithmically with n.

After all levels of CSA reduction, only two vectors remain: a sum vector and a carry vector. These two vectors are then added using a single fast carry propagate adder (such as a carry lookahead adder or carry select adder) to produce the final product. The total delay is O(log n), which is significantly faster than the O(n) delay of the array multiplier for large bit widths.

Mathematical Expression

For n-bit by n-bit multiplication using a Wallace tree, the number of CSA levels required is approximately log_{3/2}(n). Each CSA level has a constant delay equal to one full adder delay. The final carry propagate adder adds another O(log n) delay if a carry lookahead adder is used. So the total delay is proportional to log n * t_CSA + log n * t_CPA. In contrast, the array multiplier total delay is (n-2) * t_FA_row + t_final_adder, which grows linearly with n.

Practical Understanding

Array multipliers are used in smaller bit-width applications or when design regularity is more important than raw speed, such as in simple microcontrollers or FPGAs with dedicated DSP blocks that use smaller multiplier widths. Wallace tree multipliers are the standard choice for high-performance multipliers in floating point units, digital signal processors, and graphics processing units where 16-bit, 32-bit, or 64-bit multiplication must complete within a single clock cycle at GHz frequencies.

The Dadda multiplier is a variant of the Wallace tree that reduces the number of full adders used by minimizing the reduction at each stage to the minimum necessary. It achieves the same O(log n) delay with slightly fewer hardware resources. In most practical implementations, the Dadda approach is preferred over pure Wallace due to better area efficiency.

Solved Numerical Example

Calculate the critical path delay for a 4-bit array multiplier and a 4-bit Wallace tree multiplier. Assume each full adder carry delay is 1 ns, each CSA stage delay is 1 ns, and the final carry propagate adder (CLA) in the Wallace tree has a delay of 2 ns.

Given:
n = 4 bits, t_FA = 1 ns per row (array), t_CSA = 1 ns per level, t_CPA = 2 ns

Why this formula applies:
Array: carry must propagate through (n-2) adder rows sequentially before final adder.
Wallace: CSA reduces partial products in parallel in log_{1.5}(n) levels, then one CPA.

Formula (Array Multiplier):
t_array = (n - 2) x t_FA_row + t_final_RCA
= (4 - 2) x 1 + (n x t_FA)
= 2 + 4 = 6 ns

Formula (Wallace Tree):
CSA levels needed for 4 partial products:
4 terms -> 3 CSA stages to reduce to 2 vectors ≈ ceil(log_{1.5}(4)) = 2 levels
t_wallace = 2 x t_CSA + t_CPA

Substitution:
t_array = (4-2) x 1 + 4 x 1 = 6 ns (including final RCA row)
t_wallace = 2 x 1 + 2 = 4 ns

Final Answer:
Array Multiplier delay = 6 ns
Wallace Tree delay = 4 ns
Speedup = (6 - 4)/6 = 33% faster for n=4 (much larger for higher n)

Exam Tip: GATE and university exams commonly ask you to identify which multiplier architecture has O(n) vs O(log n) delay. Array multiplier = O(n), Wallace tree = O(log n). Also remember that CSA does NOT propagate carry — it only reduces three inputs to two outputs (sum + carry vectors). The final carry propagation happens only once in the last adder stage.

Quick Revision

• Digital multiplication requires n partial products for two n-bit numbers, each formed by ANDing bits of A with one bit of B and shifting left by the bit position of B.
• Array multiplier: sums partial products row by row using full adders. Delay = O(n). Regular structure, easy layout. Suitable for small n or area-constrained designs.
• Wallace tree multiplier: reduces partial products in parallel using carry save adder (CSA) tree. Delay = O(log n). Higher speed, irregular wiring, used in high-performance FPUs and DSPs.
• CSA (carry save adder) adds three numbers and produces sum and carry vectors WITHOUT propagating carry. It is the key building block of the Wallace tree.
• After CSA reduction, two vectors remain (S and C). These are added once using a fast carry propagate adder (CLA or CLA-like) to get the final product.
• Dadda multiplier = optimized Wallace tree with fewer CSA units, same O(log n) delay.
• Exam trap: Do not say CSA propagates carry. It explicitly avoids carry propagation, which is the source of its speed advantage.