Digital Logic — BIT Exam

// (39)₁₀ in BCD: encode each digit separately
3 → 0011,   9 → 1001
BCD = 0011 1001

// BCD Addition Rule: If sum of a digit group > 9, add 0110 (6)
  0111  (7)
+ 0110  (6)
──────
  1101  ← 13 in binary, but 13 > 9 in BCD context!
+ 0110  ← Add 6 correction factor
──────
1 0011  ← 1 (carry) | 0011 (3) → BCD of 13 ✓

// Rule: MSB stays the same. Each subsequent bit = XOR of adjacent binary bits
Binary:     1  0  1  1
           ↓  ↓  ↓  ↓
MSB:        1              ← copy as is
1 XOR 0:      1
0 XOR 1:         1
1 XOR 1:            0

Gray Code: 1  1  1  0

// Gray to Binary (reverse): MSB same, each bit = XOR with previous gray bit
Gray:   1  1  1  0
Binary: 1
1 XOR 1 = 0
0 XOR 1 = 1
1 XOR 0 = 1
Binary: 1  0  1  1 ← back to original ✓

// NOT using NAND: connect both inputs together
NOT(A) = NAND(A, A)    // Single NAND gate, both inputs = A

// AND using NAND: NAND then NOT the result
AND(A,B) = NAND[NAND(A,B), NAND(A,B)]   // 2 NAND gates

// OR using NAND: invert both inputs then NAND
OR(A,B)  = NAND[NAND(A,A), NAND(B,B)]   // 3 NAND gates

// NOR using NAND: build OR then invert
NOR(A,B) = NAND[OR(A,B), OR(A,B)]       // 4 NAND gates total

// Same logic applies for NOR as Universal Gate:
NOT(A) = NOR(A, A)
OR(A,B) = NOR[NOR(A,B), NOR(A,B)]
AND(A,B) = NOR[NOR(A,A), NOR(B,B)]

// First Theorem: "Break the bar, change the operator"
̄(A·B) = Ā + B̄
// NOT(AND) = OR of NOTs → NAND = NOT-AND

// Second Theorem:
̄(A+B) = Ā · B̄
// NOT(OR) = AND of NOTs → NOR = NOT-OR

// Extended De Morgan: works for any number of variables
̄(A·B·C) = Ā + B̄ + C̄
̄(A+B+C) = Ā · B̄ · C̄

// Simplification Example:
F = ̄(A·B) + ̄(A+C)
  = (Ā+B̄)  + (Ā·C̄)    ← apply De Morgan to each term
  = Ā + B̄ + Ā·C̄        ← expand
  = Ā(1+C̄) + B̄          ← factor out Ā
  = Ā·1 + B̄             ← (1+C̄) = 1 by Null Law
  = Ā + B̄               ← final simplified form

// SOP (Sum of Products) = Minterm form
// Take rows where output F = 1, AND the variables, then OR all terms
// If variable = 1 in that row → use A, if 0 → use Ā

// Truth Table: F = Σm(1,2,3) [minterms where F=1]
Row: A B | F
     0 0 | 0
     0 1 | 1  → Ā·B
     1 0 | 1  → A·B̄
     1 1 | 1  → A·B

F (SOP) = Ā·B + A·B̄ + A·B

// POS (Product of Sums) = Maxterm form
// Take rows where output F = 0, OR the variables, then AND all terms
// If variable = 0 in that row → use A, if 1 → use Ā

Row: 0 0 → (A+B)     ← complement of 0,0
F (POS) = (A+B)

         B=0   B=1
         ─────────────
A=0  |   m₀  |   m₁  |
A=1  |   m₂  |   m₃  |

// Example: F = Σm(0,1,3) → F=1 at m₀, m₁, m₃

         B=0   B=1
         ─────────────
A=0  |   1   |   1   |   ← Group 1: pair m₀,m₁ (top row, B varies → Ā)
A=1  |   0   |   1   |   ← Group 2: pair m₁,m₃ (right column, A varies → B)

Groups:
  Group 1 (m₀,m₁): A=0 constant, B varies → term = Ā
  Group 2 (m₁,m₃): B=1 constant, A varies → term = B

F = Ā + B

// 3-var: rows = C, columns = AB in Gray Code order

        AB=00  AB=01  AB=11  AB=10
        ──────────────────────────
C=0  |   m₀  |  m₂  |  m₆  |  m₄  |
C=1  |   m₁  |  m₃  |  m₇  |  m₅  |

// Example: F = Σm(0,1,2,3,4)
        AB=00  AB=01  AB=11  AB=10
C=0  |   1   |   1  |   0  |   1  |
C=1  |   1   |   1  |   0  |   0  |

// Group 1 (Octet impossible): m₀,m₁,m₂,m₃ form a Quad → AB=00,01 both rows
//   A=0 constant → term = Ā
// Group 2: m₀,m₄ (first and last column) — wrap around!
//   C=0, B=0 constant → term = C̄·B̄

F = Ā + B̄·C̄

// Grouping elimination rule:
// Pair (2 cells)  → eliminates 1 variable
// Quad (4 cells)  → eliminates 2 variables
// Octet (8 cells) → eliminates 3 variables

// 4 variables A,B,C,D → rows = AB, columns = CD (Gray Code)

         CD=00  CD=01  CD=11  CD=10
         ─────────────────────────────────
AB=00 |   m₀  |   m₁  |   m₃  |   m₂  |
AB=01 |   m₄  |   m₅  |   m₇  |   m₆  |
AB=11 |  m₁₂  |  m₁₃  |  m₁₅  |  m₁₄  |
AB=10 |   m₈  |   m₉  |  m₁₁  |  m₁₀  |

// Corner grouping example: m₀,m₂,m₈,m₁₀ form a Quad (four corners!)
// B=0, D=0 constant → term = B̄·D̄

Sum   = A XOR B  =  A ⊕ B       // Use XOR gate
Carry = A AND B  =  A · B        // Use AND gate

// Hardware: 1 XOR gate + 1 AND gate = Half Adder
// Limitation: No Carry-in input — cannot chain multiple stages

Sum  = A ⊕ B ⊕ Cin
Cout = A·B + B·Cin + A·Cin
     = A·B + Cin·(A⊕B)          // Simplified form

// Full Adder can be built from 2 Half Adders + 1 OR gate:
HA1: S1 = A⊕B,       C1 = A·B
HA2: Sum = S1⊕Cin,   C2 = S1·Cin
Cout = C1 + C2

// 4:1 MUX with inputs I₀,I₁,I₂,I₃ and select lines S₁,S₀
Y = Ī₁·Ī₀·I₀ + Ī₁·S₀·I₁ + S₁·Ī₀·I₂ + S₁·S₀·I₃

// Selection truth table:
S₁ S₀  |  Output
─────────────────
 0  0  |   I₀
 0  1  |   I₁
 1  0  |   I₂
 1  1  |   I₃

// MUX as Universal Function Generator:
// Connect variables to select lines, 0/1 to data inputs
// Any function of n variables can be realized with a 2ⁿ:1 MUX

// State table format: Present State | Input | Next State | Output

Present State | Input X | Next State | Output Z
─────────────────────────────────────────────────
     S0       |    0    |    S0      |    0
     S0       |    1    |    S1      |    0
     S1       |    0    |    S0      |    0
     S1       |    1    |    S2      |    1
     S2       |    0    |    S0      |    1
     S2       |    1    |    S2      |    1

// Mealy Machine: Output depends on state AND input
// Moore Machine: Output depends ONLY on state (not input)

Q(next) = D    ← Output simply follows the input D at clock edge

// D FF eliminates the forbidden state by using D and D̄ directly
// Built from SR FF: S = D,  R = D̄ (they are always opposite)
// Primary use: data registers, memory cells, pipeline registers
// Also called "Delay FF" because output is delayed by one clock cycle

Q(next) = T ⊕ Q    ← XOR of T and current state

// Built from JK FF: J = K = T
// Primary use: counters, frequency dividers
// When T=1 permanently, FF toggles every clock cycle
// → output frequency = clock frequency / 2 (binary divide-by-2)

// n-bit counter cycles through 2ⁿ states
2-bit counter: Mod-4  → states: 00, 01, 10, 11
3-bit counter: Mod-8  → states: 000 to 111
4-bit counter: Mod-16 → states: 0000 to 1111

// To build a Mod-N counter where N is NOT a power of 2:
// Use enough FFs for the next higher power of 2, then reset when count = N
Mod-6  counter: use 3 FFs (Mod-8 base), reset at binary 6 (110)
Mod-10 counter: use 4 FFs (Mod-16 base), reset at binary 10 (1010)

// Ring Counter: n FFs → n states (0001, 0010, 0100, 1000 for 4-bit)
// Johnson Counter: n FFs → 2n states

// Formula: Total capacity = 2^(address lines) × data width

// Example 1: 12 address lines, 8 data lines
Memory locations = 2¹² = 4096 = 4K locations
Data width       = 8 bits = 1 byte
Total capacity   = 4K × 8 bits = 4 KB

// Example 2: How many address lines for 64KB memory with 8-bit data?
64KB = 64 × 1024 = 65536 locations = 2¹⁶
Address lines needed = 16

// Example 3: 16 address lines, 16-bit data bus
Locations = 2¹⁶ = 64K = 65536 locations
Word size = 16 bits = 2 bytes
Total     = 64K × 16 bits = 64K × 2 bytes = 128 KB

// Standard prefixes:
1 KB = 2¹⁰ = 1024 bytes
1 MB = 2²⁰ = 1,048,576 bytes
1 GB = 2³⁰ = 1,073,741,824 bytes