Digital Logic Design
Number Systems, Logic Gates & Sequential Circuits
1. Number Systems
Base Conversion Fundamentals
Digital systems work with discrete values represented in different number bases. Understanding conversions between these systems is fundamental to computer engineering.
Common Number Bases
Binary (Base 2)
Digits: 0, 1
Used: Digital circuits, storage
Example: 1010β = 10ββ
Octal (Base 8)
Digits: 0-7
Used: Unix permissions
Example: 12β = 10ββ
Decimal (Base 10)
Digits: 0-9
Used: Human calculations
Example: 10ββ
Hexadecimal (Base 16)
Digits: 0-9, A-F
Used: Memory addresses, colors
Example: Aββ = 10ββ
Binary-Hex Quick Reference
Conversion Methods
Decimal to Binary
Repeated Division Method:
25 Γ· 2 = 12 remainder 1 (LSB)
12 Γ· 2 = 6 remainder 0
6 Γ· 2 = 3 remainder 0
3 Γ· 2 = 1 remainder 1
1 Γ· 2 = 0 remainder 1 (MSB)
Result: 25ββ = 11001β
2. Binary Arithmetic
Signed Number Representations
Sign-Magnitude
MSB is sign bit (0 = +, 1 = -)
Range (8-bit): -127 to +127
+5 = 00000101, -5 = 10000101
Problem: Two representations of zero
1's Complement
Negative: Invert all bits
Range (8-bit): -127 to +127
+5 = 00000101, -5 = 11111010
Problem: Still two zeros
2's Complement (Most Common)
Negative: Invert all bits + 1
Range (8-bit): -128 to +127
+5 = 00000101, -5 = 11111011
Advantage: Single zero, simpler arithmetic
Binary Coded Representations
BCD (Binary Coded Decimal)
Each decimal digit = 4 bits (0-9 only)
25ββ = 0010 0101 (BCD)
NOT same as 11001 (pure binary)
Gray Code
Only 1 bit changes between consecutive values
0: 000, 1: 001, 2: 011, 3: 010
4: 110, 5: 111, 6: 101, 7: 100
Floating Point (IEEE 754)
Single Precision (32-bit):
| Sign (1) | Exponent (8) | Mantissa (23) |
Value = (-1)^S Γ 1.M Γ 2^(E-127)
Bias: 127 (single), 1023 (double)
3. Logic Gates
Basic Gates
AND Gate
Y = A Β· B = AB
Output 1 only if ALL inputs are 1
0Β·0=0, 0Β·1=0
1Β·0=0, 1Β·1=1
OR Gate
Y = A + B
Output 1 if ANY input is 1
0+0=0, 0+1=1
1+0=1, 1+1=1
NOT Gate (Inverter)
Y = A' = Δ
Inverts the input
0' = 1
1' = 0
Universal Gates
NAND and NOR gates are called "universal" because any logic function can be implemented using only NAND gates or only NOR gates.
NAND Gate
Y = (AB)' = A' + B'
NOT-AND: Output 0 only if all inputs are 1
Implementations:
NOT: Connect inputs together
AND: NAND β NOT
OR: NOT inputs β NAND
NOR Gate
Y = (A+B)' = A' Β· B'
NOT-OR: Output 1 only if all inputs are 0
Implementations:
NOT: Connect inputs together
OR: NOR β NOT
AND: NOT inputs β NOR
XOR and XNOR Gates
XOR (Exclusive OR)
Y = A β B = A'B + AB'
Output 1 if inputs are DIFFERENT
Applications: Parity, adders, comparators
XNOR (Equivalence)
Y = (A β B)' = AB + A'B'
Output 1 if inputs are SAME
Applications: Equality comparator
4. Boolean Algebra
Fundamental Laws
Identity: A + 0 = A, A Β· 1 = A
Null: A + 1 = 1, A Β· 0 = 0
Idempotent: A + A = A, A Β· A = A
Complement: A + A' = 1, A Β· A' = 0
Double Negation: (A')' = A
Commutative: A + B = B + A, AB = BA
Associative: (A+B)+C = A+(B+C)
Distributive: A(B+C) = AB + AC
Absorption: A + AB = A, A(A+B) = A
Consensus: AB + A'C + BC = AB + A'C
De Morgan's Theorems
First Theorem:
(A Β· B)' = A' + B'
NOT of AND = OR of NOTs
Second Theorem:
(A + B)' = A' Β· B'
NOT of OR = AND of NOTs
General form: Break the bar, change the sign
Standard Forms
SOP (Sum of Products)
OR of AND terms (minterms)
F = AB'C + ABC + A'BC
Each minterm = 1 for one row of truth table
POS (Product of Sums)
AND of OR terms (maxterms)
F = (A+B+C)(A'+B+C)
Each maxterm = 0 for one row of truth table
Karnaugh Maps (K-Maps)
Visual method for simplifying Boolean expressions by grouping adjacent 1s.
Rules for grouping:
- Groups must be powers of 2 (1, 2, 4, 8, 16...)
- Groups must be rectangular
- Groups can wrap around edges
- Make groups as large as possible
- Every 1 must be in at least one group
- Fewer groups = simpler expression
Variables eliminated: Those that change within a group
5. Combinational Circuits
Adders
Half Adder
Adds two 1-bit numbers
Sum = A β B (XOR)
Carry = A Β· B (AND)
Full Adder
Adds two 1-bit numbers + carry in
Sum = A β B β Cin
Cout = AB + Cin(A β B)
Multiplexers & Demultiplexers
Multiplexer (MUX)
Data selector: Many inputs β 1 output
2βΏ inputs, n select lines, 1 output
Example: 4:1 MUX has 4 data inputs, 2 select lines
Demultiplexer (DEMUX)
Data distributor: 1 input β Many outputs
1 input, n select lines, 2βΏ outputs
Example: 1:4 DEMUX has 1 data input, 4 outputs
Encoders & Decoders
Encoder
2βΏ inputs β n outputs
Only one input active at a time
Priority encoder handles multiple active inputs
Decoder
n inputs β 2βΏ outputs
Only one output active for each input combination
Example: 3:8 decoder (3 inputs, 8 outputs)
Comparators
Compares two binary numbers and produces outputs:
- β’ A > B: Greater than output
- β’ A = B: Equal output (XNOR all bits, AND results)
- β’ A < B: Less than output
Example IC: 74LS85 (4-bit comparator)
6. Sequential Circuits
Latches vs Flip-Flops
Latches
Level-triggered (sensitive to input level)
Transparent when enabled
Flip-Flops
Edge-triggered (rising or falling edge)
Changes only on clock transition
Types of Flip-Flops
SR Flip-Flop
Set-Reset flip-flop
S=0, R=0: Hold (Q unchanged)
S=1, R=0: Set (Q=1)
S=0, R=1: Reset (Q=0)
S=1, R=1: Invalid (race condition)
D Flip-Flop
Data/Delay flip-flop
Q(next) = D
Output follows input on clock edge
No invalid state
Most common in practice
JK Flip-Flop
Most versatile flip-flop
J=0, K=0: Hold
J=1, K=0: Set
J=0, K=1: Reset
J=1, K=1: Toggle
T Flip-Flop
Toggle flip-flop
T=0: Hold (Q unchanged)
T=1: Toggle (Q changes)
Used in counters
Q(next) = T β Q
Flip-Flop Conversions
Excitation tables for converting between flip-flop types:
| Q | Q(next) | S R | J K | D | T |
|---|---|---|---|---|---|
| 0 | 0 | 0 X | 0 X | 0 | 0 |
| 0 | 1 | 1 0 | 1 X | 1 | 1 |
| 1 | 0 | 0 1 | X 1 | 0 | 1 |
| 1 | 1 | X 0 | X 0 | 1 | 0 |
X = Don't care (can be 0 or 1)
7. Counters & Registers
Counter Types
Asynchronous (Ripple)
- β’ Each FF triggered by previous FF output
- β’ Simple design, fewer components
- β’ Propagation delay accumulates
- β’ Not suitable for high-speed applications
Synchronous
- β’ All FFs triggered by same clock
- β’ No cumulative delay
- β’ More complex, more components
- β’ Preferred for high-speed applications
Common Counter Types
Binary Counter
Counts in binary sequence: 0000 β 0001 β 0010 β ...
n-bit counter: 0 to 2βΏ-1
Decade Counter (BCD)
Counts 0-9, then resets: 0000 β 0001 β ... β 1001 β 0000
MOD-10 counter
Ring Counter
Only one bit set at a time: 1000 β 0100 β 0010 β 0001
n flip-flops = n states (inefficient)
Johnson (Twisted Ring) Counter
Inverted output fed back: 0000 β 1000 β 1100 β 1110 β 1111 β 0111 β ...
n flip-flops = 2n states
Shift Registers
Types:
- β’ SISO (Serial In, Serial Out)
- β’ SIPO (Serial In, Parallel Out)
- β’ PISO (Parallel In, Serial Out)
- β’ PIPO (Parallel In, Parallel Out)
Applications:
- β’ Serial-to-parallel conversion
- β’ Parallel-to-serial conversion
- β’ Time delay (n clocks)
- β’ Ring counters
8. Key Takeaways for CpE Students
Essential Formulas & Concepts
Number Systems
- β’ 2's Complement = Invert + 1
- β’ Range (n-bit): -2^(n-1) to 2^(n-1)-1
- β’ IEEE 754: S|Exponent|Mantissa
Boolean Algebra
- β’ De Morgan: (AB)' = A'+B'
- β’ De Morgan: (A+B)' = A'B'
- β’ XOR: AβB = A'B + AB'
Combinational Circuits
- β’ Full Adder Sum = AβBβCin
- β’ MUX: 2βΏ inputs, n selects
- β’ Decoder: n inputs, 2βΏ outputs
Sequential Circuits
- β’ D FF: Q(next) = D
- β’ T FF: Q(next) = TβQ
- β’ n-bit counter: 2βΏ states
Common IC Numbers
74LS00: Quad NAND
74LS02: Quad NOR
74LS04: Hex NOT
74LS08: Quad AND
74LS32: Quad OR
74LS86: Quad XOR
74LS74: Dual D FF
74LS76: Dual JK FF
74LS90: Decade Counter