Computer Architecture - Visual Exam Notes
Digital Logic and System Basics
Lecture 1: Fundamentals of Digital Logic
History of Logic Gates
Vacuum Tubes (1904-1950s): Bulky, high power consumption, prone to failure
ENIAC (1945): Used ~18,000 vacuum tubes
Transistors (1947-Present): Smaller, reliable, energy-efficient
Integrated Circuits (1960s onward): Multiple transistors on single chip
Boolean Algebra Basics
Developed by George Boole in 1847
Uses only two values: 1 (True/High/ON) and 0 (False/Low/OFF)
Foundation of all digital electronics
Basic Logic Gates
[11]
NOT Gate (Inverter)
Function: Y = A' or Ā
Operation: Inverts input (0→1, 1→0)
Truth Table:
A Y
0 1
1 0
AND Gate
Function: Y = A.B (or A∧B)
Operation: Output is 1 only when both inputs are 1
Truth Table:
A B Y
0 0 0
0 1 0
1 0 0
1 1 1
OR Gate
Function: Y = A+B (or A∨B)
Operation: Output is 1 when at least one input is 1
Truth Table:
A B Y
0 0 0
0 1 1
1 0 1
1 1 1
NAND Gate (Universal Gate)
Function: Y = (A.B)' = A̅ .B̅
Operation: NOT AND - output is 0 only when both inputs are 1
Truth Table:
A B Y
0 0 1
0 1 1
1 0 1
1 1 0
NOR Gate (Universal Gate)
Function: Y = (A+B)' = A̅ +B̅
Operation: NOT OR - output is 1 only when both inputs are 0
Truth Table:
A B Y
0 0 1
0 1 0
1 0 0
A B Y
1 1 0
Lecture 2: Advanced Logic Gates and Laws
De Morgan's Laws
[17]
1. First Law: A̅ +B̅ = A̅ .B̅
"Complement of sum equals product of complements"
2. Second Law: A̅ .B̅ = A̅ +B̅
"Complement of product equals sum of complements"
Derived Gates
XOR Gate (Exclusive OR)
Function: Y = A⊕B = A'B + AB'
Operation: Output is 1 when inputs are different
Truth Table:
A B Y
0 0 0
0 1 1
1 0 1
1 1 0
XNOR Gate (Exclusive NOR)
Function: Y = (A⊕B)' = AB + A'B'
Operation: Output is 1 when inputs are same
Truth Table:
A B Y
0 0 1
0 1 0
1 0 0
1 1 1
Universal Gates Implementation
[16]
NAND and NOR are called universal gates
Any Boolean function can be implemented using only NAND or only NOR gates
Using NAND Gates:
NOT: A → A NAND A = A'
AND: A,B → (A NAND B) NAND (A NAND B) = A.B
OR: A,B → (A NAND A) NAND (B NAND B) = A+B
Using NOR Gates:
NOT: A → A NOR A = A'
OR: A,B → (A NOR B) NOR (A NOR B) = A+B
AND: A,B → (A NOR A) NOR (B NOR B) = A.B
Lecture 3: Boolean Algebra Laws
Fundamental Laws
1. Commutative Laws
Addition: A + B = B + A
Multiplication: A.B = B.A
2. Associative Laws
Addition: A + (B + C) = (A + B) + C
Multiplication: A.(B.C) = (A.B).C
3. Distributive Laws
A.(B + C) = A.B + A.C
A + (B.C) = (A + B).(A + C)
4. Identity Laws
A+0=A
A.1 = A
A+1=1
A.0 = 0
5. Complement Laws
A + A' = 1
A.A' = 0
6. Idempotent Laws
A+A=A
A.A = A
7. Absorption Laws
A + A.B = A
A.(A + B) = A
A + A'.B = A + B
A.(A' + B) = A.B
Lecture 4: Combinational Circuits
Circuit Types
Combinational Circuits
Output depends only on present inputs
No memory required
Faster than sequential circuits
Examples: Adders, Multiplexers, Encoders
Sequential Circuits
Output depends on present inputs and previous outputs
Memory required
Slower than combinational circuits
Examples: Flip-flops, Counters, Registers
Half Adder
[12]
Purpose: Adds two single bits
Inputs: A, B
Outputs: Sum (S), Carry (C)
Equations:
Sum = A ⊕ B
Carry = A.B
Truth Table:
A B Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Full Adder
[13]
Purpose: Adds two bits plus carry from previous stage
Inputs: A, B, Cin (Carry in)
Outputs: Sum (S), Cout (Carry out)
Equations:
Sum = (A ⊕ B) ⊕ Cin
Cout = A.B + (A ⊕ B).Cin
Truth Table:
A B Cin Sum 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
Lecture 5: Subtractors and Data Selectors
Half Subtractor
Purpose: Subtracts one bit from another
Inputs: A (minuend), B (subtrahend)
Outputs: Difference (D), Borrow (B)
Equations:
Difference = A ⊕ B
Borrow = A'.B
Truth Table:
A B Diff Borrow
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
Full Subtractor
Purpose: Subtracts two bits with borrow from previous stage
Inputs: A, B, Bin (Borrow in)
Outputs: Difference (D), Bout (Borrow out)
Equations:
Difference = (A ⊕ B) ⊕ Bin
Bout = Bin.(A ⊕ B)' + A'.B
4-bit Parallel Adder (Ripple Carry Adder)
Structure: Chain of full adders
Carry propagation: Cout of one stage → Cin of next stage
Example: Adding 1010 + 0101 = 1111
Multiplexer (MUX)
[14]
Function: Data selector - routes one of many inputs to single output
Structure: 2ⁿ inputs, n select lines, 1 output
Types: 2:1, 4:1, 8:1, 16:1
4:1 Multiplexer
Inputs: I₀, I₁, I₂, I₃
Select lines: S₁, S₀
Output: Y = S₁'S₀'I₀ + S₁'S₀I₁ + S₁S₀'I₂ + S₁S₀I₃
Demultiplexer (DEMUX)
Function: Data distributor - routes single input to one of many outputs
Structure: 1 input, n select lines, 2ⁿ outputs
Also known as: Data distributor
Lecture 6: Encoders, Decoders, and Comparators
Encoder
Function: Converts 2ⁿ input lines to n output lines
Applications:
Octal to Binary
Decimal to Binary
Hexadecimal to Binary
8:3 Encoder (Octal to Binary)
Inputs: I₀ to I₇ (8 lines)
Outputs: Y₂, Y₁, Y₀ (3 lines)
Example: Input I₅ active → Output 101 (binary for 5)
Decoder
[15]
Function: Converts n input lines to 2ⁿ output lines
Applications:
Binary to Decimal
Binary to Octal
Binary to Hexadecimal
3:8 Decoder (Binary to Octal)
Inputs: B₂, B₁, B₀ (3 lines)
Outputs: Y₀ to Y₇ (8 lines)
Example: Input 011 → Y₃ active (output line 3)
Comparators
1-bit Comparator
Inputs: A, B
Outputs: A>B, A=B, A<B
Equations:
A < B = A'.B
A = B = (A ⊕ B)'
A > B = A.B'
2-bit Comparator
Inputs: A₁A₀, B₁B₀
Outputs: A>B, A=B, A<B
Equations:
A > B = A₁B₁' + (A₁ ⊕ B₁)'A₀B₀'
A = B = (A₁ ⊕ B₁)'(A₀ ⊕ B₀)'
A < B = A₁'B₁ + (A₁ ⊕ B₁)'A₀'B₀
Important Formulas for Exams
Gate Equations
NOT: Y = A'
AND: Y = A.B
OR: Y = A + B
NAND: Y = (A.B)'
NOR: Y = (A + B)'
XOR: Y = A ⊕ B = A'B + AB'
XNOR: Y = (A ⊕ B)' = AB + A'B'
De Morgan's Laws
(A + B)' = A'.B'
(A.B)' = A' + B'
Boolean Identities
A+0=A
A+1=1
A.0 = 0
A.1 = A
A+A=A
A.A = A
A + A' = 1
A.A' = 0
Adder/Subtractor Equations
Half Adder: Sum = A⊕B, Carry = A.B
Full Adder: Sum = (A⊕B)⊕Cin, Cout = AB + (A⊕B)Cin
Half Subtractor: Diff = A⊕B, Borrow = A'.B
Full Subtractor: Diff = (A⊕B)⊕Bin, Bout = Bin(A⊕B)' + A'.B
Visual Learning Tips
1. Logic Gate Symbols: Remember the standard IEEE symbols for quick recognition
2. Truth Tables: Practice drawing complete truth tables for complex circuits
3. Circuit Analysis: Trace signals step-by-step through each gate
4. Boolean Simplification: Use visual methods like Karnaugh maps
5. Universal Implementation: Practice converting circuits using only NAND/NOR
6. Combinational Design: Start with truth table, derive Boolean expression, then circuit
7. Data Path Tracing: Follow data flow in multiplexers and decoders
8. Comparison Logic: Visualize bit-by-bit comparison in comparator circuits
Exam Tips
1. Truth Tables: Always verify your Boolean equations with truth tables
2. Circuit Analysis: Trace signals through gates step by step
3. Boolean Simplification: Use laws systematically
4. Universal Gates: Remember NAND and NOR can implement any function
5. Combinational vs Sequential: Know the key differences
6. Multiplexer/Demultiplexer: Understand the relationship (inverse functions)
7. Encoder/Decoder: Remember the input-output line relationships
8. Comparators: Focus on the three possible outcomes for any comparison
Good Luck with Your Exams!