Combinational multipliers — Hinglish notes

3.3.12 · Hardware › Combinational Circuits

WHY hume ek combinational multiplier ki zaroorat hai?

WHAT hai ek partial product?

AND kyun? Do single bits ko multiply karna: $1 \times 1 = 1$ , baaki sab $0$ . Woh truth table bilkul AND gate hai. Isliye $a_{i} \cdot b_{j} = a_{i} \land b_{j}$ .

HOW scratch se product formula derive karein

Har number ko positional binary mein likho: $A = \sum_{i = 0}^{n - 1} a_{i} 2^{i}, B = \sum_{j = 0}^{m - 1} b_{j} 2^{j}$

Multiply karo aur distributive law use karo:

= \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}\,}$$ > - **Har term** $a_i b_j$ ek AND gate hai. > - Exponent $2^{i+j}$ batata hai **kaun sa column** hai jisme bit land karegi — matlab kitna shift karna hai. > - Ek hi column mein terms ko sum karna **full adders** se hota hai (jo sum + carry produce karte hain). **Ye sab kyun hai?** Ye kehta hai: saare $n\times m$ AND products banao, har ek ko column $i+j$ mein rakh do, aur carry propagation ke saath columns add karo. Ye *literally* wahi circuit hai. **Output width:** sabse bada possible product hai $(2^n-1)(2^m-1) < 2^{n+m}$, isliye $P$ ko zyada se zyada $==n+m==$ bits chahiye. ![[3.3.12-Combinational-multipliers.png]] --- ## Array multiplier structure > [!definition] Array multiplier > Ek regular 2-D grid: row $j$ AND gates se $PP_j$ banati hai aur ise (shifted) running sum mein add karti hai jo row $j-1$ se aa rahi hoti hai, ==full adders== ki ek row use karke. Carries rows ke andar aur unke aaro-paar ripple karte hain. $2\times 2$ example ke liye, $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$ (add karne ko kuch nahi → sirf AND) - $P_1 = a_1b_0 \oplus a_0b_1$, carry $c_1 = a_1b_0 \wedge a_0b_1$ (ek **half adder**) - $P_2 = a_1b_1 \oplus c_1$, carry $c_2$ - $P_3 = a_1b_1 \wedge c_1$ **Yahan half adders kyun?** Column $2^1$ mein exactly do bits add karni hain aur koi incoming carry nahi hai → half adder. Deeper columns mein carry bhi aati hai → full adders. --- ## Worked example 1 — $3 \times 2$ compute karo $A = 11_2 = 3$, $B = 10_2 = 2$. 1. $PP_0$ ($b_0=0$): saare bits $=0$. **Kyun?** $0$ ke saath AND karne par kuch bhi $0$ ho jaata hai. 2. $PP_1$ ($b_1=1$): $a_0b_1=1,\ a_1b_1=1 \Rightarrow 11$, left by 1 shift → $110_2$. 3. Sum: $000 + 110 = 110_2 = 6$. ✓ **Kyun correct?** $3\times2 = 6$, aur $110_2=6$. ## Worked example 2 — $3 \times 3$ compute karo (sab AND = 1) $a_1a_0 = 11$, $b_1b_0=11$, toh har $a_ib_j = 1$. - $P_0 = a_0b_0 = 1$ - Column $2^1$: $a_1b_0 + a_0b_1 = 1+1$. **Carry kyun?** $1+1=10_2$, toh $P_1=0$, $c_1=1$. - Column $2^2$: $a_1b_1 + c_1 = 1 + 1 = 10_2$, toh $P_2=0$, $c_2=1$. - Column $2^3$: $c_2 = 1$, toh $P_3=1$. - Product $= 1001_2 = 9$. ✓ ($3\times3=9$.) **Ye step (carries) kyun?** Har column sirf ek bit hold kar sakta hai; excess "overflow" ho jaati hai carry ke roop mein agle higher weight column mein, bilkul decimal carrying ki tarah. ## Worked example 3 — width sanity check, $15\times15$ (4-bit) Max value $=225 = 11100001_2$, jo $8$ bits $= n+m = 4+4$ hai. **Kyun?** Ye $n+m$ bound confirm karta hai: $225 < 256 = 2^8$. ✓ --- ## Delay & cost (80/20 essentials) > [!formula] Array multiplier ripple delay > Worst-case delay $\propto$ array ke through path. Ek $n\times n$ array multiplier ke liye carry roughly $2n$ adder stages se ripple karta hai: > $$t_{\text{delay}} \approx \mathcal{O}(n)$$ > Gate count (AND + adders) $\approx \mathcal{O}(n^2)$. **$\mathcal{O}(n)$ delay kyun?** Sabse lambi signal path grid ke diagonal ko cross karti hai aur phir bottom carry chain ko — dono ki length $\sim n$ hai. > [!intuition] Faster multipliers kyun exist karte hain > $\mathcal{O}(n)$ ko beat karne ke liye, partial products ko **carry-save adders** ke saath group karo (carries defer karo) aur **Wallace/Dadda tree** se sum karo, jo $\mathcal{O}(\log n)$ depth deta hai. Array multiplier sabse simple, sabse regular baseline hai. --- ## Common mistakes > [!mistake] "Partial products banane ke liye XOR gates use karo." > **Kyun sahi lagta hai:** addition mein XOR use hota hai (sum bit), toh students har jagah XOR dhundhte hain. > **Fix:** Ek partial product bit *banana* do bits ki **multiplication** hai → ==AND==. XOR baad mein appear hota hai, adders ke andar jo partial products ko **sum** karte hain. Multiply = AND, add = XOR (+carry). > [!mistake] "Product width wider operand ki width ke barabar hoti hai." > **Kyun sahi lagta hai:** addition mein result sirf $\sim n+1$ bits hota hai, toh log assume karte hain ki multiplication bhi similar hai. > **Fix:** Multiplication *magnitude* badhata hai. $n$-bit × $m$-bit ko $==n+m==$ bits chahiye, kyunki $2^{n-1}\cdot2^{m-1}=2^{n+m-2}$ already ek high bit set karta hai. > [!mistake] "Har partial product ko shift karna bhool jaana." > **Kyun sahi lagta hai:** saare partial products identical lagte hain ($A$ ki copies), toh beginners unhe aligned add kar dete hain. > **Fix:** $PP_j$ ka weight $2^j$ hai — ise summing se pehle **$j$ columns left shift** karna zaroori hai (master formula mein $2^{i+j}$). --- > [!recall]- Feynman: 12-saal ke bacche ko explain karo > Tum jaante ho na kaafi bade numbers ko paper par multiply kaise karte hain? Tum top number ko har bottom digit se multiply karte ho, ek row ek time, har row ko ek step left slide karte ho, phir saari rows add kar dete ho. Ek binary multiplier wahi karta hai, lekin digits sirf 0 aur 1 hoti hain. Toh "ek digit se multiply karna" bahut simple hai: agar digit 1 hai, number copy karo; agar 0 hai, zeros likho. Ye "copy ya zero" trick tiny AND switches se hoti hai, aur "rows add karne" wala part chote adder blocks se hota hai. Jab 1+1 hota hai tum 0 likhte ho aur agli column mein 1 carry karte ho — bilkul normal jaise. Machine saari rows ek saath karta hai, toh answer bas appear ho jaata hai. > [!mnemonic] > **"AND makes it, ADD stacks it, SHIFT places it, CARRY paces it."** > AND = partial products, ADD = full adders, SHIFT = $2^{i+j}$ weight, CARRY = column overflow. --- ## #flashcards/hardware Single partial-product bit $a_i b_j$ kaun sa gate banata hai? ::: Ek AND gate (single-bit multiply = AND). $A,B$ ke product ka master formula kya hai? ::: $P=\sum_{i,j}(a_i\wedge b_j)\,2^{i+j}$. Ek $n$-bit × $m$-bit product ko kitne bits chahiye? ::: $n+m$ bits (kyunki product $<2^{n+m}$). Partial product $PP_j$ ko left mein $j$ kyun shift karte hain? ::: Kyunki ye positional expansion mein $2^j$ se weighted hoti hai. Array mein partial products ko kya sum karta hai? ::: Full adders ki rows (aur half adders jahan koi carry nahi aati). $n\times n$ array multiplier ki worst-case delay? ::: $\mathcal{O}(n)$ array ke aaro-paar carry ripple ki wajah se. Array multiplier ka gate/area cost order? ::: $\mathcal{O}(n^2)$ (AND-per-pair plus per-cell adder). Kaun sa structure $\mathcal{O}(\log n)$ depth achieve karta hai? ::: Carry-save / Wallace (ya Dadda) adder tree. Multiplication mein bits-ka-multiply kaun se gate se map karta hai, aur bits-ka-add kaun se gate se? ::: Multiply→AND; add→XOR (with carry). $2\times2$ mein, column $2^1$ full adder ki jagah half adder kyun hai? ::: Ismein do bits hain aur koi incoming carry nahi hai. --- ## Connections - [[Full Adder]] aur [[Half Adder]] — summing cells - [[AND Gate]] — partial products banata hai - [[Ripple Carry Adder]] — carry chain jo speed limit karti hai - [[Carry Save Adder]] / [[Wallace Tree]] — faster summation - [[Binary Number System]] — positional weights $2^i$ - [[Booth's Algorithm]] — signed numbers ke liye partial products kam karna - [[Combinational Circuits]] — parent topic (koi memory/clock nahi) ## 🖼️ 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] ```