⏳
Loading cheatsheet...
Boolean algebra, combinational and sequential circuits, minimization, and timing fundamentals.
| Base | Name | Digits | Prefix / Suffix | Example |
|---|---|---|---|---|
| 2 | Binary | 0, 1 | 0b / (2) | 1010.11 |
| 8 | Octal | 0–7 | 0o / (8) | 12.6 |
| 10 | Decimal | 0–9 | None / (10) | 10.75 |
| 16 | Hexadecimal | 0–9, A–F | 0x / (16) | A.F |
| Conversion | Method | Example |
|---|---|---|
| Decimal → Binary | Repeated division by 2 | 25 ÷ 2 = 12 R1, 12 ÷ 2 = 6 R0, 6 ÷ 2 = 3 R0, 3 ÷ 2 = 1 R1, 1 ÷ 2 = 0 R1 → 11001 |
| Binary → Decimal | Positional weighting (2^n) | 11001 = 1×16 + 1×8 + 0×4 + 0×2 + 1×1 = 25 |
| Decimal → Octal | Repeated division by 8 | 25 ÷ 8 = 3 R1, 3 ÷ 8 = 0 R3 → 31(8) |
| Octal → Binary | Replace each digit with 3 bits | 31(8) → 011 001 → 011001 |
| Decimal → Hex | Repeated division by 16 | 255 ÷ 16 = 15 R15 → FF(16) |
| Hex → Binary | Replace each digit with 4 bits | A3(16) → 1010 0011 |
| Binary → Hex | Group 4 bits from LSB | 10100011 → A3(16) |
| Binary → Octal | Group 3 bits from LSB | 101 000 11 → 043(8) (pad with 0) |
| Concept | Definition | Example (for 8-bit) |
|---|---|---|
| 1's Complement | Invert all bits | 25 = 00011001 → 1's = 11100110 |
| 2's Complement | 1's complement + 1 | 25 → 1's = 11100110 → 2's = 11100111 (−25) |
| Sign Bit | MSB: 0 = positive, 1 = negative | 01111111 = +127, 10000000 = −128 (2's) |
| Range (signed 8-bit) | −128 to +127 | 2's complement: −2^(n−1) to 2^(n−1)−1 |
| Range (unsigned 8-bit) | 0 to 255 | 0 to 2^n − 1 |
─── Binary Addition ───
1011 (11)
+ 0110 ( 6)
──────
10001 (17) ← carry propagates left
─── Binary Subtraction using 2's Complement ───
Subtract 6 from 11: 11 − 6 = 11 + (−6)
Step 1: Convert 6 to 2's complement (8-bit)
6 = 00000110
1's= 11111001
2's= 11111010 (this is −6)
Step 2: Add to the minuend
00001011 (+11)
+ 11111010 (−6)
──────────
100000101 → discard carry → 00000101 = 5 ✓
─── Binary Subtraction with Borrow (Direct) ───
1101 (13)
− 0110 ( 6)
──────
0111 ( 7)
─── Multiplication ───
1011 (11)
× 0101 ( 5)
──────
1011 (11 × 1)
0000 (11 × 0, shifted)
1011 (11 × 1, shifted)
──────
110111 (55)| Decimal | BCD Code |
|---|---|
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| 3 | 0011 |
| 4 | 0100 |
| 5 | 0101 |
| 6 | 0110 |
| 7 | 0111 |
| 8 | 1000 |
| 9 | 1001 |
Each decimal digit is represented by 4 bits. 12(10) → 0001 0010(BCD). Invalid BCD: 1010–1111 (use excess-3 or Gray for correction).
| Decimal | Binary | Gray Code |
|---|---|---|
| 0 | 0000 | 0000 |
| 1 | 0001 | 0001 |
| 2 | 0010 | 0011 |
| 3 | 0011 | 0010 |
| 4 | 0100 | 0110 |
| 5 | 0101 | 0111 |
| 6 | 0110 | 0101 |
| 7 | 0111 | 0100 |
| 8 | 1000 | 1100 |
| 9 | 1001 | 1101 |
Only 1 bit changes between consecutive values. Binary → Gray: MSB same, then XOR each pair.Gray → Binary: MSB same, then XOR with previous result bit.
| Law / Identity | AND Form | OR Form |
|---|---|---|
| Identity | A · 1 = A | A + 0 = A |
| Complement | A · A' = 0 | A + A' = 1 |
| Idempotent | A · A = A | A + A = A |
| Commutative | A · B = B · A | A + B = B + A |
| Associative | (A · B) · C = A · (B · C) | (A + B) + C = A + (B + C) |
| Distributive | A · (B + C) = A·B + A·C | A + (B · C) = (A+B)·(A+C) |
| Absorption | A + A·B = A | A · (A + B) = A |
| De Morgan's | (A · B)' = A' + B' | (A + B)' = A' · B' |
| Null Element | A · 0 = 0 | A + 1 = 1 |
| Involution | — | (A')' = A |
| Theorem | Expression |
|---|---|
| Consensus (SOP) | AB + A'C + BC = AB + A'C (BC is redundant) |
| Consensus (POS) | (A+B)(A'+C)(B+C) = (A+B)(A'+C) |
| Adjacency | AB + AB' = A (combine adjacent minterms) |
| XOR Identity | A ⊕ B = A'B + AB' |
| XNOR Identity | A ⊙ B = AB + A'B' |
| XOR Properties | A ⊕ A = 0, A ⊕ 1 = A', A ⊕ 0 = A |
| NAND = NOR | (A↑B)' = A'B' + A' + B' — NAND and NOR are duals |
| Minterm | A | B | C | Notation |
|---|---|---|---|---|
| m0 | 0 | 0 | 0 | A'B'C' |
| m1 | 0 | 0 | 1 | A'B'C |
| m2 | 0 | 1 | 0 | A'BC' |
| m3 | 0 | 1 | 1 | A'BC |
| m4 | 1 | 0 | 0 | AB'C' |
| m5 | 1 | 0 | 1 | AB'C |
| m6 | 1 | 1 | 0 | ABC' |
| m7 | 1 | 1 | 1 | ABC |
SOP = OR of AND terms. Canonical SOP: every term contains all variables.F = Σm(1,3,5,7) = A\'B\'C + A\'BC + AB\'C + ABC
| Maxterm | A | B | C | Notation |
|---|---|---|---|---|
| M0 | 0 | 0 | 0 | A + B + C |
| M1 | 0 | 0 | 1 | A + B + C' |
| M2 | 0 | 1 | 0 | A + B' + C |
| M3 | 0 | 1 | 1 | A + B' + C' |
| M4 | 1 | 0 | 0 | A' + B + C |
| M5 | 1 | 0 | 1 | A' + B + C' |
| M6 | 1 | 1 | 0 | A' + B' + C |
| M7 | 1 | 1 | 1 | A' + B' + C' |
POS = AND of OR terms. Canonical POS: every sum contains all variables.F = ΠM(0,2,4,6) = (A+B+C)(A+B\'+C)(A\'+B+C)(A\'+B\'+C)
Problem: Minimize F(A,B,C) = Σm(0,1,2,5,6,7) using a 3-variable K-map.
| B'C' | B'C | BC | BC' | |
|---|---|---|---|---|
| A' | 1 (m0) | 1 (m1) | 0 (m3) | 1 (m2) |
| A | 0 (m4) | 1 (m5) | 1 (m7) | 1 (m6) |
K-map Grouping:
BC
00 01 11 10
A'0 [ 1 1 0 1 ]
A1 [ 0 1 1 1 ]
Groups:
- Group 1: m0, m1, m5, m4 → B' (actually m4=0, so: m0+m1 → A'B')
- Group 1: m0, m1, m5, m4 → skip m4=0
- Group 1: m5, m7, m6 → A (covers m5, m7, m6 in bottom row + m4=0)
- Group 1: m0, m1, m5, m4 → skip m4=0
- Correct groups:
• m5, m7, m6 → A (bottom row without m4: m5+m6=m6+m7 → A·C' + A·C = A)
• m0, m1 → A'B' (top-left pair)
• m6, m2 → BC' (wrap-around vertical pair)
Optimized: F = A + A'B' + BC'Problem: Minimize F(A,B,C,D) = Σm(0,1,2,5,6,7,8,9,13,15)
| C'D' | C'D | CD | CD' | |
|---|---|---|---|---|
| A'B' | 1 | 1 | 0 | 1 |
| A'B | 0 | 1 | 1 | 1 |
| AB | 0 | 1 | 1 | 0 |
| AB' | 1 | 1 | 0 | 0 |
CD
00 01 11 10
00' [ 1 1 0 1 ] AB'C'D'=m8, AB'C'D=m9, AB'CD'=m10=0, AB'CD=m11=0
01' [ 0 1 1 1 ] A'BC'D'=m4=0, A'BC'D=m5, A'BCD=m7, A'BCD'=m6
11' [ 0 1 1 0 ] ABC'D'=m12=0, ABC'D=m13, ABCD=m15, ABCD'=m14=0
10' [ 1 1 0 0 ] AB'C'D'=m8, AB'C'D=m9
Groups (can wrap around edges!):
• m5, m7, m13, m15 → BD (column CD=01 and CD=11 → D stays, B=1)
• m0, m1, m8, m9 → B'C' (column CD=00 and CD=01 → C' stays, B'=1)
• m5, m7, m6 → A'B (row 01: A'B)
• m6, m7 → A'CD' (already covered)
Essential prime implicants:
1. BD (covers m5, m7, m13, m15)
2. B'C' (covers m0, m1, m8, m9)
3. A'BC' (covers m5, m6) — covers m6
Optimized: F = BD + B'C' + A'BC'X) can be used as 1 or 0 to form larger groups. SOP output uses groups of 1s; POS uses groups of 0s.| Gate | Symbol (Text) | Boolean Expression | Logic |
|---|---|---|---|
| AND | A & B | Y = A · B | 1 only if ALL inputs are 1 |
| OR | A | B | Y = A + B | 1 if ANY input is 1 |
| NOT | ~A | Y = A' | Inverts the input |
| NAND | !(A & B) | Y = (A · B)' | NOT of AND; 0 only if all inputs 1 |
| NOR | !(A | B) | Y = (A + B)' | NOT of OR; 1 only if all inputs 0 |
| XOR | A ^ B | Y = A'B + AB' | 1 if inputs are DIFFERENT |
| XNOR | !(A ^ B) | Y = AB + A'B' | 1 if inputs are SAME |
| A | B | AND | OR | NOT A | XOR | XNOR |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| A | B | NAND | NOR |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
NAND and NOR are universal gates — any logic function can be implemented using only NAND or only NOR gates.
| Function | NAND Implementation |
|---|---|
| NOT | Connect both inputs together: Y = (A · A)' = A' |
| AND | NAND → NOT: Y = ((A · B)')' = A · B |
| OR | De Morgan's: Y = (A' · B')' = A + B (NOT each input via NAND, then NAND) |
| XOR | 4 NAND gates: Y = ((A·(A·B)')' · (B·(A·B)')')' |
| NOR | OR via NAND → NOT: Y = ((A'·B')')' = (A+B)' |
| Function | NOR Implementation |
|---|---|
| NOT | Connect both inputs together: Y = (A + A)' = A' |
| OR | NOR → NOT: Y = ((A + B)')' = A + B |
| AND | De Morgan's: Y = (A' + B')' = A · B (NOT each input via NOR, then NOR) |
| XOR | 5 NOR gates: Y = ((A'+B)' + (A+B')')' |
| NAND | AND via NOR → NOT: Y = ((A'+B')')' = (A·B)' |
| Gate Equivalence | Expression | Alternative |
|---|---|---|
| NAND | (A·B)' | A' + B' (De Morgan's) |
| NOR | (A+B)' | A' · B' (De Morgan's) |
| XOR | A ⊕ B | A'B + AB' = (A+B)(A'B')' |
| XNOR | A ⊙ B | AB + A'B' = (A'+B)(A+B') |
| XOR (chain) | A ⊕ B ⊕ C | 1 if odd number of 1s (parity) |
| Buffer | Y = A | Two NOTs in series: Y = (A')' = A |
| Tri-state Buffer | Y = A if EN=1, Z if EN=0 | High-impedance output control |
| A | B | Sum (S) | Carry (C) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Equations: S = A ⊕ B, C = A · B
Adds two single bits. No carry-in. Cannot cascade for multi-bit addition.
| A | B | Cin | Sum (S) | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Equations: S = A ⊕ B ⊕ Cin, Cout = AB + Cin(A ⊕ B)
Two half adders OR one full adder = cascades for n-bit ripple carry adder.
| A | B | Diff (D) | Borrow (Bo) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
Equations: D = A ⊕ B, Bo = A\' · B
Subtracts two single bits. No borrow-in.
| A | B | Bin | Diff (D) | Bout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Equations: D = A ⊕ B ⊕ Bin, Bout = A\'B + Bin(A ⊕ B)\'
Can cascade for n-bit subtraction. Bout = 1 when A < B + Bin.
| Select (S) | Output (Y) |
|---|---|
| 0 | I0 |
| 1 | I1 |
2:1 MUX: Y = S\'·I0 + S·I1. Selects one of 2^n inputs using n select lines.
4:1 MUX: 2 select lines, Y = S1\'S0\'·I0 + S1\'S0·I1 + S1S0\'·I2 + S1S0·I3.
8:1 MUX: 3 select lines. Can implement ANY Boolean function with 3 variables.
16:1 MUX: 4 select lines. Uses two 8:1 MUXes + one 2:1 MUX as a tree.
| Select | I0 | I1 |
|---|---|---|
| 0 | Input | 0 |
| 1 | 0 | Input |
1:2 DEMUX: Routes input to one of 2^n outputs based on select lines.
Opposite of MUX. 1 input, 2^n outputs, n select lines.
1:4 DEMUX: 2 select lines. Input goes to exactly one output, others are 0.
A DEMUX with input permanently 1 acts as a Decoder.
| Input (Active) | D3 | D2 | D1 | D0 | Y1 | Y0 |
|---|---|---|---|---|---|---|
| D0 | 0 | 0 | 0 | 1 | 0 | 0 |
| D1 | 0 | 0 | 1 | 0 | 0 | 1 |
| D2 | 0 | 1 | 0 | 0 | 1 | 0 |
| D3 | 1 | 0 | 0 | 0 | 1 | 1 |
4:2 Priority Encoder: Higher-priority input overrides lower. If D3=1, output is 11 regardless of D0–D2.
Adds a Valid (V) output: V=1 if any input is active, V=0 if all zero.
| Input | A1 | A0 | D3 | D2 | D1 | D0 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 2 | 1 | 0 | 0 | 1 | 0 | 0 |
| 3 | 1 | 1 | 1 | 0 | 0 | 0 |
2:4 Decoder: n inputs → 2^n outputs (one-hot). Active-high: only one output is 1.
Active-low decoder (e.g., 74LS138): only one output is 0.
Can implement ANY function by OR-ing appropriate minterm outputs.
| A | B | A > B (G) | A = B (E) | A < B (L) |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
Equations: G = A·B\', E = A\'B\' + AB = A ⊙ B, L = A\'·B
n-bit comparator (e.g., 7485): Cascades from LSB to MSB with G, E, L inputs from previous stage. IC 7485 is a 4-bit magnitude comparator with cascading inputs.
─── Implementing Boolean Functions with MUX ───
Example: F(A, B, C) = Σm(1, 3, 5, 6)
Using 8:1 MUX with S2=A, S1=B, S0=C:
Connect D1=D3=D5=D6 = 1, others = 0
Using 4:1 MUX with S1=A, S0=B (C applied to data inputs):
When AB=00: F depends on C alone → F(0,0,C) = 0·C = 0 → I0 = 0
When AB=01: F depends on C alone → F(0,1,C) = C → I1 = C
When AB=10: F depends on C alone → F(1,0,C) = C → I2 = C
When AB=11: F depends on C alone → F(1,1,C) = C' → I3 = C'
Result: Y = 0·A'B' + C·A'B + C·AB' + C'·AB| S | R | Q(next) | Action |
|---|---|---|---|
| 0 | 0 | Q (prev) | No change (Hold) |
| 0 | 1 | 0 | Reset |
| 1 | 0 | 1 | Set |
| 1 | 1 | INVALID | Forbidden state! |
Characteristic Eq: Q(n+1) = S + R\'·Q(n), constraint: S·R = 0
Built with NOR gates (active-high SR) or NAND gates (active-low S\'R\').
| J | K | Q(next) | Action |
|---|---|---|---|
| 0 | 0 | Q (prev) | No change (Hold) |
| 0 | 1 | 0 | Reset |
| 1 | 0 | 1 | Set |
| 1 | 1 | Q' (prev) | Toggle |
Characteristic Eq: Q(n+1) = J·Q\'(n) + K\'·Q(n)
Removes the invalid state of SR-FF. When J=K=1, output toggles. Most versatile flip-flop.
| D | Q(next) | Action |
|---|---|---|
| 0 | 0 | Reset / Store 0 |
| 1 | 1 | Set / Store 1 |
Characteristic Eq: Q(n+1) = D
Data captured on clock edge (positive or negative triggered). Used in registers, shift registers, and memory cells. Eliminates the race-around condition present in JK-FF level-triggered designs.
| T | Q(next) | Action |
|---|---|---|
| 0 | Q (prev) | No change (Hold) |
| 1 | Q' (prev) | Toggle |
Characteristic Eq: Q(n+1) = T ⊕ Q(n)
Built from JK-FF by connecting J=K=T. Commonly used in counters and frequency dividers. Connect T permanently to 1 → output toggles every clock → frequency ÷ 2.
| Q(n) | Q(n+1) | SR inputs | JK inputs | D input | T input |
|---|---|---|---|---|---|
| 0 | 0 | S=0, R=× | J=0, K=× | D=0 | T=0 |
| 0 | 1 | S=1, R=0 | J=1, K=× | D=1 | T=1 |
| 1 | 0 | S=0, R=1 | J=×, K=1 | D=0 | T=1 |
| 1 | 1 | S=×, R=0 | J=×, K=0 | D=1 | T=0 |
Excitation tablestell you what inputs are needed to achieve a desired state transition. Used in counter and FSM design. × = don't care (either 0 or 1 works). JK flip-flop has the most don't cares, making it easiest for minimization.
| Register Type | Description | Flip-Flops | Application |
|---|---|---|---|
| Buffer Register | Parallel load, holds data | n D-FFs | Temporary data storage |
| Shift Register (SISO) | Serial in, serial out | n D-FFs | Delay lines, serial data |
| Shift Register (SIPO) | Serial in, parallel out | n D-FFs | Serial-to-parallel conversion |
| Shift Register (PISO) | Parallel in, serial out | n D-FFs + MUX | Parallel-to-serial conversion |
| Shift Register (PIPO) | Parallel in, parallel out | n D-FFs | Data transfer between buses |
| Universal Register | SISO + SIPO + PISO + PIPO | n D-FFs + MUXes | General-purpose register (74LS194) |
| Bidirectional | Shift left or right | n D-FFs + direction ctrl | Arithmetic operations |
| Counter Type | Clock | Speed | Glitches | Mod | Example |
|---|---|---|---|---|---|
| Asynchronous (Ripple) | Not common to all FFs | Slow (propagation delay) | Yes | 2^n | Ripple counter using T-FFs |
| Synchronous | Common to all FFs | Fast | No | 2^n or any | Synchronous up/down counter |
| Ring Counter | Synchronous | Fast | No | n | 4-bit: sequence 1000→0100→0010→0001 |
| Johnson (Twisted Ring) | Synchronous | Fast | No | 2n | 4-bit: 0000→1000→1100→1110→1111→0111→0011→0001 |
| Decade Counter | Synchronous/Async | Varies | Maybe | 10 | Counts 0→9 (BCD counter, IC 7490) |
| Up-Down Counter | Synchronous | Fast | No | 2^n | Control signal selects direction (IC 74193) |
─── Design a 3-bit Synchronous Up Counter using T-FFs ───
State sequence: 000 → 001 → 010 → 011 → 100 → 101 → 110 → 111 → 000
Step 1: State table with excitation table for T-FF
Q2 Q1 Q0 | Q2+ Q1+ Q0+ | T2 T1 T0
0 0 0 | 0 0 1 | 0 0 1
0 0 1 | 0 1 0 | 0 1 1
0 1 0 | 0 1 1 | 0 0 1
0 1 1 | 1 0 0 | 1 1 1
1 0 0 | 1 0 1 | 0 0 1
1 0 1 | 1 1 0 | 0 1 1
1 1 0 | 1 1 1 | 0 0 1
1 1 1 | 0 0 0 | 1 1 1
Step 2: K-map for each T input
T0 = 1 (always toggle LSB)
T1 = Q0 (toggle when Q0=1)
T2 = Q1·Q0 (toggle when both Q1 and Q0 = 1)
Result: Each bit toggles when ALL lower bits are 1.| Feature | Description |
|---|---|
| Output | Depends ONLY on present state |
| Output equation | Y = f(State only) |
| States | May need more states than Mealy |
| Output changes | Synchronized with clock edge |
| Glitches | No glitches (output tied to state FFs) |
| Model | State → Output (node label) |
─── Moore Machine Example: Detect "11" ───
States: S0 (reset), S1 (got 1), S2 (got 11 → output 1)
State | Input=0 | Input=1 | Output
S0 | S0 | S1 | 0
S1 | S0 | S2 | 0
S2 | S0 | S2 | 1
State diagram:
S0 --1--> S1 --1--> S2
^ | ^ |
| | | |
+--0----+ +--0----+
+--1----+---------+ (from S2 with input 0 → S0)
Sequence: 1,1 → S0→S1→S2 (output becomes 1)| Feature | Description |
|---|---|
| Output | Depends on present state AND input |
| Output equation | Y = f(State, Input) |
| States | Fewer states than Moore (typically) |
| Output changes | Can change asynchronously with input |
| Glitches | Possible glitches in combinational output |
| Model | Transition → Output (edge label) |
─── Mealy Machine Example: Detect "11" ───
States: S0 (reset), S1 (got 1)
State | Input=0 / Output | Input=1 / Output
S0 | S0 / 0 | S1 / 0
S1 | S0 / 0 | S1 / 1
State diagram:
S0 --1/0--> S1 --1/1--> S1
^ | |
| | |
+--0/0-----+ |
+--0/0-----------------+
Sequence: 1,1 → S0→S1→S1 (output 1 on second transition)| Aspect | Moore Machine | Mealy Machine |
|---|---|---|
| Output depends on | State only | State + Input |
| Number of states | More (output encoded in states) | Fewer |
| Output function | Y = f(State) | Y = f(State, Input) |
| Output timing | Clock synchronous | Can be asynchronous |
| Output glitches | None (registered output) | Possible combinational glitches |
| State encoding | Needs extra states for outputs | Fewer states suffice |
| Hardware | More flip-flops, less combinational | Fewer flip-flops, more combinational |
| Response time | One clock cycle delay | Immediate (same cycle as input change) |
Goal: Reduce the number of states to minimize hardware (flip-flops, combinational logic).
─── State Minimization Procedure ───
Step 1: Identify equivalent states
Two states are equivalent if, for every possible input:
1. They produce the same output
2. They transition to equivalent states (or the same state)
Step 2: Equivalence Table Method
• List all state pairs in a table
• Mark pairs with different outputs as "not equivalent"
• For remaining pairs, check if their next-state pairs are equivalent
• Repeat until no new pairs are marked
Example (Mealy machine):
State | x=0 / z | x=1 / z
A | B / 0 | C / 0
B | A / 0 | D / 1
C | D / 0 | A / 0
D | C / 0 | B / 1
Check pairs:
(A,B): x=0→B,A (same pair), x=1→C,D outputs differ? z: 0,1 → NOT EQUIV
(A,C): x=0→B,D outputs? 0,0 same; x=1→C,A (same pair), z:0,0 → EQUIV
(A,D): x=1→C,B outputs? 0,1 → NOT EQUIV
(B,C): x=0→A,D outputs? 0,0; x=1→D,A outputs? 1,0 → NOT EQUIV
(B,D): x=0→A,C outputs? 0,0; x=1→D,B (same pair), z:1,1 → EQUIV
(C,D): x=1→A,B outputs? 0,1 → NOT EQUIV
Equivalent pairs: (A,C) and (B,D)
Reduced: S0={A,C}, S1={B,D} → 4 states reduced to 2─── Design a Mealy FSM to detect the sequence "101" ───
Step 1: Define states
S0 = Initial / no useful sequence seen
S1 = Last input was '1'
S2 = Last two inputs were '10'
Step 2: State transition table (Mealy)
Present | Next (x=0) | Next (x=1) | Z (x=0) | Z (x=1)
State | State | State | |
S0 | S0 | S1 | 0 | 0
S1 | S2 | S1 | 0 | 0
S2 | S0 | S1 | 0 | 1 ← "101" detected!
Step 3: State assignment (binary encoding)
S0 = 00, S1 = 01, S2 = 10
Step 4: Excitation table (using D-FFs: Q1Q0)
Present | x=0: Q1+Q0+ Z | x=1: Q1+Q0+ Z
Q1 Q0 | |
0 0(S0)| 0 0 0 | 0 1 0
0 1(S1)| 1 0 0 | 0 1 0
1 0(S2)| 0 0 0 | 0 1 1
1 1(×) | × × × | × × ×
Step 5: Derive equations using K-maps
D1 = x'·Q0 (Q1 next)
D0 = x (Q0 next, independent of state!)
Z = x·Q1 (Output: 1 only when in S2 and input=1)
Circuit: 2 D-FFs, 1 AND gate for D1, 1 AND gate for Z
D0 connects directly to x!| Type | Full Form | Read/Write | Volatility | Erase Method | Use Case |
|---|---|---|---|---|---|
| ROM | Read Only Memory | Read only | Non-volatile | Cannot erase | Firmware, boot ROM, lookup tables |
| PROM | Programmable ROM | Read only (after programming) | Non-volatile | Cannot erase | Small production runs, custom firmware |
| EPROM | Erasable PROM | Read only (after programming) | Non-volatile | UV light (15–20 min) | Prototype development, reprogrammable firmware |
| EEPROM | Electrically Erasable PROM | Read/Write | Non-volatile | Electrical (byte-level) | BIOS settings, small config data |
| Flash | Flash EEPROM | Read/Write | Non-volatile | Electrical (block-level) | USB drives, SSDs, firmware updates |
| Feature | SRAM (Static) | DRAM (Dynamic) |
|---|---|---|
| Storage element | Flip-flop (6 transistors) | Capacitor (1T + 1C) |
| Refresh needed | No | Yes (every few ms) |
| Speed | Fast (~1–10 ns) | Slower (~50–100 ns) |
| Density | Low (less memory per chip) | High (more memory per chip) |
| Cost | Expensive | Cheaper |
| Power | Low (no refresh) | Higher (refresh consumes power) |
| Use case | Cache memory (L1, L2, L3) | Main memory (RAM) |
| Volatile | Yes | Yes |
| Example IC | Cache in CPU die | DDR4, DDR5 DIMMs |
| Level | Type | Speed | Size | Cost/Byte | Managed By |
|---|---|---|---|---|---|
| L1 | SRAM cache | ~1 ns | 32–64 KB | Highest | Hardware |
| L2 | SRAM cache | ~4 ns | 256 KB–1 MB | High | Hardware |
| L3 | SRAM cache | ~10 ns | 4–64 MB | Medium | Hardware |
| Main Memory | DRAM (DDR) | ~50–100 ns | 4–128 GB | Low | OS (MMU) |
| Secondary | SSD / NVMe | ~100 µs | 256 GB–4 TB | Very low | OS (File system) |
| Tertiary | HDD | ~10 ms | 1–20 TB | Lowest | OS (File system) |
Principle: As you go down the hierarchy, speed decreases, size increases, and cost per byte decreases. Cache exploits locality of reference: temporal (recently accessed data reused) and spatial (nearby data likely accessed).
| Technique | Address Fields | Tag Compare | Hit Rate | Conflict Misses | Hardware Complexity |
|---|---|---|---|---|---|
| Direct Mapping | Tag | Line | Word | 1 comparison | Low | High | Simple |
| Fully Associative | Tag | Word | N comparisons (parallel) | Highest | None | Complex (CAM needed) |
| Set-Associative | Tag | Set | Word | W comparisons (within set) | High | Low | Moderate |
─── Cache Mapping Calculations ───
Memory: 64 KB, Block size: 64 bytes, Cache: 4 KB
Number of blocks in memory = 64 KB / 64 B = 1024 blocks
Number of lines in cache = 4 KB / 64 B = 64 lines
─── Direct Mapping ───
Line offset = log₂(64) = 6 bits
Line number = log₂(64) = 6 bits
Tag = 16 - 6 - 6 = 4 bits
Mapping: Block i → Line (i mod 64)
─── 4-Way Set Associative ───
Sets = 64 / 4 = 16 sets
Word offset = 6 bits
Set index = log₂(16) = 4 bits
Tag = 16 - 6 - 4 = 6 bits
─── Fully Associative ───
Word offset = 6 bits
Tag = 16 - 6 = 10 bits
Any block can go in any line
─── Cache Performance ───
Hit Time = time to access cache
Miss Rate = 1 - Hit Rate
Miss Penalty = time to fetch from main memory
AMAT = Hit Time + Miss Rate × Miss Penalty| Term | Definition |
|---|---|
| Hit | Data found in cache |
| Miss | Data NOT found in cache; fetched from lower level |
| Hit Rate | Hits / (Hits + Misses) |
| Miss Rate | Misses / (Hits + Misses) = 1 − Hit Rate |
| Miss Penalty | Extra time to fetch data on a miss |
| AMAT | Average Memory Access Time = Hit Time + Miss Rate × Miss Penalty |
| Temporal Locality | Recently accessed data will likely be accessed again |
| Spatial Locality | Data near recently accessed data will likely be accessed |
| Replacement Policy | LRU (Least Recently Used), FIFO, LFU, Random |
| Write Policy | Write-through (update cache + memory) or Write-back (update cache only) |
Step 1: Draw the 4-variable K-map and place 1s at the given minterm positions.
Step 2: Identify the largest possible groups of power-of-2 adjacent 1s:
• Group m5, m7, m13, m15 (column BD) → term: BD
• Group m0, m1, m8, m9 (column B'C') → term: B'C'
• Group m6, m7 (row A'BC') → wait: m6=A'BCD', m7=A'BCD → A'BC
Actually, m4, m5, m6, m7 row gives A'B (covers m5, m6, m7).
• m5 and m7 covered by BD and A'B.
Step 3: Final minimized SOP: F = BD + B'C' + A'BC'
(3 terms, 5 literals vs. original 10 minterms — significant reduction.)
A universal gate can implement ANY Boolean function. To prove NAND is universal, we show it can implement NOT, AND, and OR:
NOT: Connect both inputs together: NAND(A, A) = (A · A)' = A'
AND: NAND followed by NOT: NAND(NAND(A,B), NAND(A,B)) = ((A·B)')' = A·B
OR: Using De Morgan's: A + B = (A'·B')'. First NOT each input via NAND, then NAND the results.
So: NAND(NAND(A,A), NAND(B,B)) = (A'·B')' = A + B
Since any Boolean function can be expressed in SOP form (using AND, OR, NOT), and NAND can create all three, NAND is a universal gate. The same logic applies to NOR using the dual of De Morgan's theorem.
Combinational Circuits: Output depends ONLY on present inputs. No memory elements. No clock required. Examples: adders, subtractors, MUX, DEMUX, encoder, decoder, comparator. Faster, simpler to design. Output changes immediately when input changes.
Sequential Circuits: Output depends on present inputs AND past state (memory). Contains flip-flops/latches as memory elements. Requires a clock signal. Examples: counters, shift registers, state machines (Moore/Mealy), frequency dividers. Slower due to clock and propagation delay. More complex to design due to state transitions and timing issues.
Moore Machine: Output depends ONLY on the current state. Each state has a fixed output. In the state diagram, output is written inside the state circle. Requires more states because output must be encoded in the state itself. Output is synchronized with the clock edge — no glitches. One clock cycle of latency between input and output change. Best for synchronous systems.
Mealy Machine: Output depends on BOTH the current state and current input. Output is written on the transition arrows. Fewer states needed since output is on transitions. Output can change as soon as input changes (potentially within the same clock cycle), but this can cause glitches if inputs change asynchronously. Best for reactive, input-driven systems. For the same functionality, a Mealy machine typically has one fewer state than its Moore equivalent.
Half Adder: Adds two 1-bit inputs (A, B). Produces Sum (A ⊕ B) and Carry (A · B). No carry-in input. Cannot be directly cascaded for multi-bit addition because there is no way to propagate a carry from a lower bit position. Used as a building block inside full adders.
Full Adder: Adds three 1-bit inputs (A, B, Cin). Produces Sum (A ⊕ B ⊕ Cin) and Carry-out (AB + Cin(A ⊕ B)). Has a carry-in from the previous lower bit. Can be cascaded to build n-bit adders (Ripple Carry Adder). A full adder is built from two half adders + one OR gate. For a 4-bit adder, you need 4 full adders. The carry-out of each stage becomes the carry-in of the next stage.