Digital Logic Design — Boolean Algebra, Logic Gates, Combinational Circuits

Unit 1: Number Systems

Decimal, Binary, Octal, Hexadecimal

| System | Base | Digits | |---|---|---| | Decimal | 10 | 0-9 | | Binary | 2 | 0, 1 | | Octal | 8 | 0-7 | | Hexadecimal | 16 | 0-9, A-F |

Binary to Decimal: Multiply each bit by 2^position

• 1011₂ = 1×8 + 0×4 + 1×2 + 1×1 = 11₁₀

Decimal to Binary: Divide by 2, collect remainders bottom to top

• 13 → 13/2=6R1, 6/2=3R0, 3/2=1R1, 1/2=0R1 → 1101₂

Hex to Binary: Each hex digit = 4 binary bits

• A = 1010, F = 1111, 2 = 0010

Binary Arithmetic

Addition: 1+1 = 10 (write 0, carry 1)
Subtraction using 2's complement:
  2's complement = 1's complement + 1
  1's complement = flip all bits
  A - B = A + (2's complement of B)

---

Unit 2: Boolean Algebra

Basic Laws:

| Law | AND form | OR form | |---|---|---| | Identity | A · 1 = A | A + 0 = A | | Null | A · 0 = 0 | A + 1 = 1 | | Idempotent | A · A = A | A + A = A | | Complement | A · A' = 0 | A + A' = 1 | | Involution | (A')' = A | — |

De Morgan's Theorems (Very Important!):

• (A · B)' = A' + B'
• (A + B)' = A' · B'

Simplify using Boolean algebra:

F = AB + AB' = A(B + B') = A·1 = A
F = A + AB = A(1 + B) = A·1 = A   (Absorption Law)

---

Unit 3: Logic Gates

| Gate | Symbol | Operation | Truth Table | |---|---|---|---| | AND | · | Output=1 only if ALL inputs=1 | 0·0=0, 0·1=0, 1·1=1 | | OR | + | Output=1 if ANY input=1 | 0+0=0, 0+1=1, 1+1=1 | | NOT | ' or ¬ | Inverts input | 0'=1, 1'=0 | | NAND | | AND followed by NOT | Universal gate | | NOR | | OR followed by NOT | Universal gate | | XOR | ⊕ | Output=1 if inputs are DIFFERENT | 0⊕0=0, 0⊕1=1, 1⊕1=0 | | XNOR | ⊙ | Output=1 if inputs are SAME | Complement of XOR |

Universal Gates: NAND and NOR can implement any Boolean function.

---

Unit 4: Karnaugh Map (K-Map)

K-Map minimizes Boolean expressions visually by grouping 1s.

Rules for Grouping:

• Groups must be powers of 2: 1, 2, 4, 8
• Groups must be rectangular
• Groups should be as large as possible
• Cells wrap around (edges are adjacent)
• Each 1 must be covered; 1s can be in multiple groups

2-variable K-Map:

    B'  B
A'  | 0 | 1 |
A   | 2 | 3 |

4-variable K-Map (standard arrangement):

        CD
AB    00  01  11  10
00  |  0 | 1 | 3 | 2 |
01  |  4 | 5 | 7 | 6 |
11  | 12 |13 |15 |14 |
10  |  8 | 9 |11 |10 |

Reading simplified expression:

• Group of 4 in a row → variable eliminated for that group
• Mark variables that change across group as eliminated
• Write remaining variables (non-changing) as AND terms

---

Unit 5: Combinational Circuits

Half Adder

• Adds two 1-bit numbers
• Sum = A XOR B
• Carry = A AND B

Full Adder

• Adds three bits (A, B, Cin)
• Sum = A XOR B XOR Cin
• Carry = AB + BCin + ACin

Multiplexer (MUX)

• 2^n to 1 selector
• n select lines choose 1 of 2^n inputs
• Used for data selection, implementing Boolean functions

Decoder

• n inputs → 2^n outputs
• Exactly one output active at a time
• Used in memory addressing, 7-segment display

Encoder

• 2^n inputs → n outputs
• Converts active input to binary code

---

Unit 6: Sequential Circuits and Flip-Flops

Sequential circuits have memory — output depends on current input AND previous state.

SR Flip-Flop (Set-Reset)

| S | R | Q (next) | |---|---|---| | 0 | 0 | Q (no change) | | 0 | 1 | 0 (reset) | | 1 | 0 | 1 (set) | | 1 | 1 | INVALID |

D Flip-Flop (Data)

• Q(next) = D
• On clock edge, output = input
• Eliminates invalid state of SR

JK Flip-Flop

• Combines SR with toggle
• J=K=1 → toggles (Q' → Q)
• Most versatile flip-flop

T Flip-Flop (Toggle)

• T=0 → no change; T=1 → toggles
• Used in counters

Registers and Counters

• Register: Group of flip-flops storing multiple bits
• Counter: Sequential circuit that counts clock pulses
  • Ripple (Asynchronous): simple but slow
  • Synchronous: all FFs clocked together; faster

---

Solved PYQ Questions

Q1 (2023): Minimize F = Σm(0,1,2,5,6,7) using K-Map Group 1s cleverly → F = A'B' + AB + B'C'... (draw K-map for visual solving)

Q2 (2023): Convert (156)₁₀ to binary, octal, and hex 156/2 = 78R0, 78/2=39R0, 39/2=19R1, 19/2=9R1, 9/2=4R1, 4/2=2R0, 2/2=1R0, 1/2=0R1 Binary: 10011100₂ → Octal: 234₈ → Hex: 9C₁₆

Q3 (2022): Implement XOR using only NAND gates A XOR B = (A NAND (A NAND B)) NAND (B NAND (A NAND B)) Uses 4 NAND gates total.

---

Quick Revision Checklist

• Number conversions: decimal↔binary↔octal↔hex
• De Morgan's theorems (both forms)
• Universal gates: NAND and NOR
• XOR: output 1 when inputs different; XNOR: output 1 when inputs same
• K-Map: groups must be powers of 2, largest possible
• Half adder vs Full adder formulas
• 4 flip-flop types and their truth tables
• Synchronous vs Asynchronous counters