Noesis
3.3.13Combinational Circuits

ALU design fundamentals

1,917 words9 min readdifficulty · medium3 backlinks
🇮🇳 Yeh note Hinglish mein padho →

WHAT is an ALU?

The core insight: an ALU = arithmetic unit + logic unit, both fed to a selector.

F=MUX(S, arith(A,B), logic(A,B))F = \text{MUX}\big(S,\ \text{arith}(A,B),\ \text{logic}(A,B)\big)

HOW we build it — from first principles

Step 1: The 1-bit full adder (the heart of arithmetic)

Step 2: Add AND subtract with the SAME hardware

Step 3: The logic unit

Bitwise AND, OR, XOR, NOT are just gates applied to each bit pair in parallel — cheap and fast.

Step 4: Select with a MUX

All operation results exist simultaneously; the select lines drive a MUX so only one appears at FF. Adding a new operation = add its circuit + one more MUX input.

Figure — ALU design fundamentals

Status Flags (derive each one)

Worked Examples (4-bit ALU)

Common Mistakes

Active Recall

Recall Predict before revealing (Forecast-then-Verify)
  1. Why can one control bit turn an adder into a subtractor? → Because A−B=A+B‾+1A-B = A+\overline B+1; XOR BB with SsubS_{sub} and feed SsubS_{sub} as c0c_0.
  2. What makes overflow V=cn⊕cn−1V = c_n \oplus c_{n-1}? → Carry into vs out of sign bit disagree ⇒ sign corrupted.
  3. Where does the "selection" of operation happen? → A MUX driven by the select lines picks one parallel result.
Recall Feynman: explain to a 12-year-old

Imagine a calculator that already computed every answer — the plus answer, the minus answer, the "compare" answer — all at once, and lined them up. Then a little switch (the select lines) just points to the one drawer you asked for and hands you that answer. That's the ALU: do everything, then pick. Subtraction is a sneaky trick — flip all of B's bits and add one, and you've turned "add" into "subtract" without new machinery.

Flashcards

What is an ALU?
A combinational circuit doing arithmetic + logic on two n-bit inputs, selected by control lines, producing a result plus status flags (Z,C,N,V).
Why is the ALU purely combinational?
Its output depends only on current inputs A, B, S; it has no internal memory or clock — state lives in external registers.
Sum bit formula of a full adder?
si=ai⊕bi⊕cis_i = a_i \oplus b_i \oplus c_i (parity: 1 when an odd number of inputs is 1).
Carry-out formula of a full adder?
ci+1=aibi+ci(ai⊕bi)c_{i+1} = a_i b_i + c_i(a_i \oplus b_i) (generate OR propagate).
How does one control bit make an adder subtract?
XOR B with S_sub and set carry-in c0 = S_sub; then S_sub=1 gives A + ¬B + 1 = A − B.
Overflow (signed) flag formula?
V=cn⊕cn−1V = c_n \oplus c_{n-1}: carry into the sign bit differs from carry out of it.
Zero flag formula?
Z=Fn−1+⋯+F0‾Z = \overline{F_{n-1}+\dots+F_0} — NOR of all result bits (1 iff result is zero).
Difference between Carry and Overflow flags?
C = unsigned overflow (carry out of MSB); V = signed overflow (sign bit corrupted).
For a two's-complement subtractor, what does C=1 mean?
No borrow occurred (result non-negative); borrow = ¬C.
How is one of many operations selected in an ALU?
All ops compute in parallel; a multiplexer driven by the select lines routes the chosen result to F.

Connections

  • Full Adder — the arithmetic core of the ALU
  • Two's Complement — why A−B=A+B‾+1A-B=A+\overline B+1 works
  • Multiplexer — how the operation is selected
  • Carry Lookahead Adder — speeding up the addition path
  • Status Flags and Condition Codes — how flags drive branches
  • Ripple Carry Adder — the simplest add implementation
  • Datapath and Control Unit — where the ALU sits in a CPU

Concept Map

feed

feed

arith result

logic result

pick one

outputs

converts adder to A - B

derives

carry-out cn

contains

ALU Combinational Unit

Inputs A and B

Select lines S

Full Adder Chain

Logic Unit AND OR XOR NOT

Multiplexer

Result F

Status Flags

Sub control XOR + c0

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, ALU ka core idea bahut simple hai: CPU ko add, subtract, AND, OR, compare — sab karna padta hai, lekin har operation ke liye alag machine banane ki zaroorat nahi. Hum ek hi block banate hain jo saare operations parallel mein compute kar leta hai, aur phir ek MUX (multiplexer) select lines ki madad se sirf wahi answer bahar bhejta hai jo tumne manga. Yehi "compute everything, then pick one" trick ALU design ka dil hai.

Subtraction ka jugaad bahut mast hai. Two's complement mein A−B=A+B‾+1A - B = A + \overline{B} + 1. Matlab agar tum BB ke har bit ko ek control bit SsubS_{sub} ke saath XOR kar do, aur wahi SsubS_{sub} ko sabse pehle carry-in (c0c_0) bana do — to Ssub=0S_{sub}=0 pe pure addition hota hai aur Ssub=1S_{sub}=1 pe subtraction. Sirf ek control bit se adder ko subtractor bana diya, koi extra hardware nahi! Yeh 80/20 wala concept hai — isko samjhe to aadha chapter clear.

Flags bhi yaad rakhna zaroori hai: Z (result zero hai kya, NOR of all bits), C (carry out, unsigned overflow), N (MSB, negative sign), aur V (cn⊕cn−1c_n \oplus c_{n-1}, signed overflow). Sabse common galti — Carry aur Overflow ko same samajhna. Carry unsigned ke liye hai, Overflow signed ke liye. Aur ek aur baat: ALU khud purely combinational hai, uske andar koi memory ya clock nahi — output sirf current inputs pe depend karta hai. Yaad rakhna, memory registers mein hoti hai, ALU mein nahi.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 1,832 wordsD2Visual walkthroughThe derivation in pictures · 2,078 wordsD3Worked examplesEvery scenario covered · 3,267 wordsD4ExercisesGraded, full solutions · 2,366 wordsD5Question bankConcept traps, quick reveals · 1,238 words

Test yourself — Combinational Circuits

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Half adder and full adderHardware · 3.3.1Two's complement signed numbersHardware · 3.1.3Carry-lookahead adderHardware · 3.3.3Ripple-carry adderHardware · 3.3.2Single-cycle datapath designHardware · 5.2.1Multi-cycle datapathHardware · 5.2.2Classic 5-stage pipeline (IF - ID - EX - MEM - WB)Hardware · 5.2.3