3.3.12Combinational Circuits
Combinational multipliers
1,922 words9 min readdifficulty · medium
WHY do we need a combinational multiplier?
WHAT is a partial product?
Why AND? Multiplying two single bits: , everything else . That truth table is exactly the AND gate. So .
HOW to derive the product formula from scratch
Write each number in positional binary:
Multiply and use the distributive law:
= \sum_{i=0}^{n-1}\sum_{j=0}^{m-1} (a_i b_j)\, 2^{\,i+j}$$ > [!formula] Master result > $$\boxed{\,P = \sum_{i,j} (a_i \wedge b_j)\, 2^{\,i+j}\,}$$ > - **Every term** $a_i b_j$ is one AND gate. > - The exponent $2^{i+j}$ tells you **which column** the bit lands in — i.e. how far to shift. > - Summing terms in the same column is done by **full adders** (which produce sum + carry). **Why is this everything?** It says: form all $n\times m$ AND products, place each in column $i+j$, and add columns with carry propagation. That is *literally* the circuit. **Output width:** the largest possible product is $(2^n-1)(2^m-1) < 2^{n+m}$, so $P$ needs at most $==n+m==$ bits. ![[3.3.12-Combinational-multipliers.png]] --- ## The array multiplier structure > [!definition] Array multiplier > A regular 2-D grid: row $j$ forms $PP_j$ with AND gates and adds it (shifted) to the running sum coming from row $j-1$, using a row of ==full adders==. Carries ripple within/across rows. For a $2\times 2$ example, $A=a_1a_0$, $B=b_1b_0$: | column weight | $2^0$ | $2^1$ | $2^2$ | $2^3$ | |---|---|---|---|---| | $PP_0$ ($b_0$) | $a_0b_0$ | $a_1b_0$ | | | | $PP_1$ ($b_1$) | | $a_0b_1$ | $a_1b_1$ | | - $P_0 = a_0 b_0$ (nothing to add → just the AND) - $P_1 = a_1b_0 \oplus a_0b_1$, carry $c_1 = a_1b_0 \wedge a_0b_1$ (a **half adder**) - $P_2 = a_1b_1 \oplus c_1$, carry $c_2$ - $P_3 = a_1b_1 \wedge c_1$ **Why half adders here?** Column $2^1$ has exactly two bits to add and no incoming carry → half adder. Deeper columns receive a carry too → full adders. --- ## Worked example 1 — compute $3 \times 2$ $A = 11_2 = 3$, $B = 10_2 = 2$. 1. $PP_0$ ($b_0=0$): all bits $=0$. **Why?** ANDing anything with $0$ gives $0$. 2. $PP_1$ ($b_1=1$): $a_0b_1=1,\ a_1b_1=1 \Rightarrow 11$, shifted left by 1 → $110_2$. 3. Sum: $000 + 110 = 110_2 = 6$. ✓ **Why correct?** $3\times2 = 6$, and $110_2=6$. ## Worked example 2 — compute $3 \times 3$ (all AND = 1) $a_1a_0 = 11$, $b_1b_0=11$, so every $a_ib_j = 1$. - $P_0 = a_0b_0 = 1$ - Column $2^1$: $a_1b_0 + a_0b_1 = 1+1$. **Why a carry?** $1+1=10_2$, so $P_1=0$, $c_1=1$. - Column $2^2$: $a_1b_1 + c_1 = 1 + 1 = 10_2$, so $P_2=0$, $c_2=1$. - Column $2^3$: $c_2 = 1$, so $P_3=1$. - Product $= 1001_2 = 9$. ✓ ($3\times3=9$.) **Why this step (the carries)?** Each column can hold only one bit; excess "overflows" as carry into the next-higher weight column, exactly like decimal carrying. ## Worked example 3 — width sanity check, $15\times15$ (4-bit) Max value $=225 = 11100001_2$, which is $8$ bits $= n+m = 4+4$. **Why?** Confirms the $n+m$ bound: $225 < 256 = 2^8$. ✓ --- ## Delay & cost (the 80/20 essentials) > [!formula] Array multiplier ripple delay > Worst-case delay $\propto$ path through the array. For an $n\times n$ array multiplier the carry ripples through roughly $2n$ adder stages: > $$t_{\text{delay}} \approx \mathcal{O}(n)$$ > Gate count (AND + adders) $\approx \mathcal{O}(n^2)$. **Why $\mathcal{O}(n)$ delay?** The longest signal path crosses the diagonal of the grid and then the bottom carry chain — both length $\sim n$. > [!intuition] Why faster multipliers exist > To beat $\mathcal{O}(n)$, group partial products with **carry-save adders** (defer carries) and sum with a **Wallace/Dadda tree**, giving $\mathcal{O}(\log n)$ depth. The array multiplier is the simplest, most regular baseline. --- ## Common mistakes > [!mistake] "Use XOR gates to form the partial products." > **Why it feels right:** addition uses XOR (sum bit), so students reach for XOR everywhere. > **The fix:** *Forming* a partial product bit is **multiplication** of two bits → ==AND==. XOR only appears later, inside the adders that **sum** the partial products. Multiply = AND, add = XOR (+carry). > [!mistake] "Product width equals the wider operand's width." > **Why it feels right:** in addition the result is only $\sim n+1$ bits, so people assume multiplication is similar. > **The fix:** Multiplication *grows* the magnitude. $n$-bit × $m$-bit needs $==n+m==$ bits, because $2^{n-1}\cdot2^{m-1}=2^{n+m-2}$ already sets a high bit. > [!mistake] "Forgetting to shift each partial product." > **Why it feels right:** all partial products look identical (copies of $A$), so beginners just add them aligned. > **The fix:** $PP_j$ is weighted by $2^j$ — it must be **shifted left by $j$ columns** before summing (the $2^{i+j}$ in the master formula). --- > [!recall]- Feynman: explain to a 12-year-old > You know how you multiply big numbers on paper? You multiply the top number by each bottom digit, one row at a time, slide each row one step to the left, then add all the rows. A binary multiplier does the same, but the digits are only 0 and 1. So each "multiply by a digit" is dead simple: if the digit is 1, copy the number; if it's 0, write zeros. The "copy or zero" trick is done by tiny AND switches, and the "add the rows" part is done by little adder blocks. When 1+1 happens you write 0 and carry a 1 to the next column — same as normal. The machine does all the rows at the same instant, so the answer just appears. > [!mnemonic] > **"AND makes it, ADD stacks it, SHIFT places it, CARRY paces it."** > AND = partial products, ADD = full adders, SHIFT = the $2^{i+j}$ weight, CARRY = column overflow. --- ## #flashcards/hardware Which gate forms a single partial-product bit $a_i b_j$? ::: An AND gate (single-bit multiply = AND). Master formula for the product of $A,B$? ::: $P=\sum_{i,j}(a_i\wedge b_j)\,2^{i+j}$. How many bits does an $n$-bit × $m$-bit product need? ::: $n+m$ bits (since product $<2^{n+m}$). Why must partial product $PP_j$ be shifted left by $j$? ::: Because it is weighted by $2^j$ in the positional expansion. What sums the partial products in the array? ::: Rows of full adders (and half adders where no carry enters). Worst-case delay of an $n\times n$ array multiplier? ::: $\mathcal{O}(n)$ due to carry ripple across the array. Gate/area cost order of an array multiplier? ::: $\mathcal{O}(n^2)$ (AND-per-pair plus per-cell adder). What structure achieves $\mathcal{O}(\log n)$ depth instead? ::: Carry-save / Wallace (or Dadda) adder tree. In multiplication, multiply-of-bits maps to which gate, and add-of-bits to which? ::: Multiply→AND; add→XOR (with carry). For $2\times2$, what makes column $2^1$ a half adder not full adder? ::: It has two bits and no incoming carry. --- ## Connections - [[Full Adder]] and [[Half Adder]] — the summing cells - [[AND Gate]] — forms partial products - [[Ripple Carry Adder]] — the carry chain that limits speed - [[Carry Save Adder]] / [[Wallace Tree]] — faster summation - [[Binary Number System]] — positional weights $2^i$ - [[Booth's Algorithm]] — reducing partial products for signed numbers - [[Combinational Circuits]] — parent topic (no memory/clock) ## 🖼️ Concept Map ```mermaid flowchart TD A[Multiply A times B] -->|positional expansion| B[Sum of ai 2^i times bj 2^j] B -->|distributive law| C[Master result P equals sum ai AND bj times 2^i+j] C -->|each term ai bj| D[AND gates form partial products] C -->|exponent 2^i+j| E[Column placement / shift] C -->|sum same column| F[Full adders] D -->|feed into| G[Array multiplier grid] F -->|carry propagation| G E -->|determines row shift| G G -->|combinational output| H[Product needs n+m bits] F -->|produce| I[Sum and carry] G -->|trades area for speed| J[Fast fixed-delay ALU multiply] ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Dekho, combinational multiplier basically wahi purani "long multiplication" hai jo hum school me karte the, bas binary me. Jab aap decimal me multiply karte ho, har digit ke liye ek partial product banate ho, use left me shift karte ho, aur sab ko add kar dete ho. Binary me ek zabardast simplification hoti hai: har digit sirf 0 ya 1 hai. To partial product ya to poora multiplicand hai (jab bit 1 hai) ya poora zero (jab bit 0 hai). Ye "copy ya zero" ka kaam ek simple ==AND gate== karti hai — kyunki bit-to-bit multiply ka truth table exactly AND jaisa hai. > > Formula khud derive kar lo: $A=\sum a_i 2^i$ aur $B=\sum b_j 2^j$. Inko multiply karo to $P=\sum_{i,j}(a_i\wedge b_j)2^{i+j}$ milta hai. Iska matlab — har jodi $a_i,b_j$ ke liye ek AND, aur us bit ko column number $(i+j)$ me daal do (yehi shift hai). Ek column me jab do ya zyada bits aa jaate hain, unko ==full adder== / half adder se add karte hain, aur $1+1$ hone par carry agle column me chala jaata hai — bilkul normal carry ki tarah. > > Do important baatein yaad rakho: (1) partial product banane me AND aata hai, add karne me XOR+carry — inhe mat mix karo. (2) $n$-bit × $m$-bit ka answer $n+m$ bits ka hota hai, kyunki multiplication magnitude badha deta hai. Speed ke liye: simple array multiplier ka delay $O(n)$ hota hai (carry ripple ke wajah se) aur gates $O(n^2)$. Agar aur fast chahiye to Wallace/Dadda tree use karke $O(\log n)$ depth le aate hain. Bas itna samajh gaye to poora topic clear hai. ![[audio/3.3.12-Combinational-multipliers.mp3]]