EE1D2 Lecture 3 — Memory Systems & Programmable Logic
📚 Core Concepts
1. Memory System Design
When building a large memory system from smaller modules, you need to think in two directions:
- Width expansion (parallel modules): To increase word size, place modules in parallel. If each module gives 4-bit words and you need 16-bit words, you need 4 modules in parallel.
- Depth expansion (series/decoder): To increase the number of addressable words, use a decoder to select between groups of parallel modules.
Address lines formula:
Total words = (words per module) × (number of module groups)
Number of address lines = log₂(total words)
2. ROM (Read-Only Memory) in Logic Circuits
A ROM can act as a lookup table — given address inputs (A1, A0), it outputs stored data bits (D0, D1, D2). These outputs can then feed into a multiplexer (MUX) to implement combinational logic functions.
How to read a ROM truth table:
| A1 | A0 | D0 | D1 | D2 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Each row is a minterm. D0, D1, D2 tell you the stored value for that address.
ROM + MUX circuit: A MUX uses the ROM outputs as data inputs and external signals as select lines. The output F is formed by selecting one of D0–D2 based on the select signals (e.g., C and D).
MUX output formula: F = D0·S1'·S0' + D1·S1'·S0 + D2·S1·S0' + (input)·S1·S0
Where S1 and S0 are the MUX select lines.
3. DEMUX + ROM Circuits
A DEMUX (demultiplexer) routes a single input to one of several outputs based on select lines. When chained with a ROM, the pattern is:
- DEMUX routes the input signal to one of several address lines of the ROM.
- The ROM maps these to output data bits.
- Those data bits feed into logic gates or are OR-ed to produce the final output F.
4. PLA (Programmable Logic Array)
A PLA implements a sum of products (SOP) expression. It consists of:
- An AND plane — forms product terms (minterms or implicants)
- An OR plane — combines products into outputs
How to read a PLA diagram:
- Each row of crosses (×) in the AND plane represents one product term. A cross on an uncomplemented line = true variable; on a complemented line = complemented variable.
- Each × in the OR plane means that product term feeds into the output.
Simplification method:
- Read off all product terms from the AND plane.
- Write the full SOP expression.
- Simplify using a Karnaugh map (K-map).
5. PAL (Programmable Array Logic)
A PAL is similar to a PLA but the OR plane is fixed. PALs can include D flip-flops to implement finite state machines (FSMs).
- The current state (Y1, Y0) feeds back into the AND plane.
- The input (X) also feeds into the AND plane.
- The next state is determined by evaluating the AND-OR logic and clocking the flip-flops.
To find the next state: Substitute current Y1, Y0, and X values into the Boolean expressions for D1 and D0.
6. FPGA (Field-Programmable Gate Array)
An FPGA implements logic using Look-Up Tables (LUTs) and MUXes with programmable connections. In an FSM context:
- MUX select lines connect to state outputs (Y1, Y0) and inputs (X).
- Programmed LUT values determine which MUX inputs are active.
- D flip-flops store the current state and update on the clock edge.
To analyse an FPGA FSM: Identify which MUX inputs are connected (1s vs 0s), derive D1 and D0 expressions, then evaluate for the given state and all possible input values.
🛠️ How to Solve the Exercises
Memory sizing problems (Q1, Q2)
Step 1: Determine how many modules you need in parallel for the desired word width.
Parallel modules = target word size ÷ module word size
Step 2: Determine how many groups you need for the desired depth.
Groups = target word count ÷ module word count
Step 3: Total modules = parallel × groups
Step 4: For address lines, compute log₂(total word count).
ROM + MUX problems (Q3)
Step 1: Express each ROM output (D0, D1, D2) as a Boolean function of the address inputs (A1, A0). Read off directly from the truth table.
Step 2: Identify the MUX select lines. What signals connect to S1 and S0?
Step 3: Write the full MUX output expression:
F = D0·S1'·S0' + D1·S1'·S0 + D2·S1·S0' + D3·S1·S0
Step 4: Substitute your D expressions and simplify (use Boolean algebra or K-map).
DEMUX + ROM problems (Q4)
Step 1: Trace the DEMUX — which output activates under which combination of select signals?
Step 2: Use the activated DEMUX output as the ROM address. Look up the corresponding ROM data outputs.
Step 3: Combine D0 and D1 through the output logic (e.g., OR gate) to get F.
Step 4: Simplify the resulting Boolean expression.
PLA problems (Q5, Q6)
Step 1: Read each AND gate row from the diagram to extract product terms. Work column by column — a mark on a true line means the variable appears uncomplemented; on a complement line means complemented.
Step 2: Write the unsimplified SOP:
F = (term1) + (term2) + ...
Step 3: Plot the minterms on a K-map and group them to find the minimal SOP.
PAL / FSM problems (Q7)
Step 1: From the PAL diagram, derive the Boolean expressions for D1 and D0 (next-state logic).
Step 2: Substitute the given current state (Y1, Y0) and input (X) into those expressions.
Step 3: The resulting (D1, D0) values are the next state after the clock edge.
FPGA / FSM problems (Q8)
Step 1: Identify MUX select connections. Note which state/input signals go to S0 and S1 of each MUX.
Step 2: Read the LUT values programmed into the MUX inputs (the 0s and 1s on each data line).
Step 3: Write D1 and D0 as Boolean expressions using the MUX formula:
F = I0·S1'·S0' + I1·S1'·S0 + I2·S1·S0' + I3·S1·S0
Step 4: Evaluate for the current state and both possible values of X (since X is unknown), giving two possible next states.
📝 Exercises
Question 1
A large memory system for words of 16 bits is assembled using a decoder and 256 memory modules of 1024 words × 4 bits. How many address lines does this system have?
- a) 14
- b) 16 ✓
- c) 18
- d) 20
Solution:
- 4 modules in parallel → 16-bit words
- Total word count = 1024 × (256 ÷ 4) = 1024 × 64 = 65,536 = 2¹⁶
- → 16 address lines
Question 2
A memory system needs 8192 words × 32 bits. Available modules: 256 words × 8 bits. How many modules are needed?
- a) 1024
- b) 512
- c) 128 ✓
- d) 256
Solution:
- Parallel modules for 32-bit words: 32 ÷ 8 = 4
- Groups for depth: 8192 ÷ 256 = 32
- Total = 4 × 32 = 128 modules
Question 3
A ROM (truth table below) drives a 4-to-1 MUX. The MUX select lines are C (S1) and D (S0). What is the simplified Boolean expression for F?
| A1 | A0 | D0 | D1 | D2 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
With A = A1, B = A0 as circuit inputs:
- a) F = CD + ABD + AB'C + A'BC
- b) F = ABC + A'BD' + AB'C'D' ✓
- c) F = ABC + ACD' + ACD' + A'BC'D'
- d) F = A'BC' + ABD + AB'C'D'
Solution:
D0 = B
D1 = AB
D2 = A'B + AB'
F = D0·C'D' + D1·C'D + D2·CD' + C·CD
= BC'D' + ABC'D + (A'B + AB')CD' + C²D
= BC'D' + ABC'D + A'BCD' + AB'CD' + 0
Simplify → F = ABC + A'BD' + AB'C'D'
Question 4
A DEMUX routes input Z to ROM address lines. ROM truth table:
| A1 | A0 | D1 | D0 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Select lines: S1 = X, S0 = Y. F = D1 OR D0. What is the simplified expression?
- a) F = X'Z + YZ ✓
- b) F = XYZ
- c) F = X'Z
- d) F = X'Y'Z + X'YZ'
Solution:
A1 = X'Y'Z + X'YZ = X'Z
A0 = XYZ
D1 = A0 = XYZ
D0 = A1 = X'Z
F = D1 + D0 = XYZ + X'Z = X'Z + YZ
Question 5
A PLA implements F = A'BD + BC' + BCD + AB'C'. What is the simplified form?
- a) F = AB' + A'B + BD + AC'
- b) F = A'B' + CD' + AB'C
- c) F = AB' + A'B + AD + AC'
- d) F = BC' + AC' + BD ✓
Solution:
Plot minterms of A'BD + BC' + BCD + AB'C' onto a 4-variable K-map → group to get:
F = BC' + AC' + BD
Question 6
A PLA implements F = A'D' + A'BD + AB'D'. What is the simplified form?
- a) F = A'B'C' + B'CD
- b) F = A'B + B'D' ✓
- c) F = A'B + B'D' + A'C'
- d) F = A'B + B'D' + A'B'C'
Solution:
Plot A'D' + A'BD + AB'D' onto a K-map → minimal grouping gives:
F = A'B + B'D'
Question 7
A PAL FSM is in state Y1 Y0 = 1 0 with input X = 0. What is the next state?
- a) Y1 Y0 = 0 0
- b) Y1 Y0 = 0 1
- c) Y1 Y0 = 1 0
- d) Y1 Y0 = 1 1 ✓
Solution:
From the PAL diagram (reading the AND plane), with Y1=1, Y0=0, X=0, evaluate D1 and D0:
Next state = Y1 Y0 = 1 1
Question 8
An FPGA FSM has two MUXes. Top MUX: S1 = Y0, S0 = Y1. Bottom MUX: S1 = Y1, S0 = X. Currently Y1 Y0 = 1 1. What are the possible next states?
- a) Y1 Y0 = 1 0 or Y1 Y0 = 1 1 ✓
- b) Y1 Y0 = 0 0 or Y1 Y0 = 1 0
- c) Y1 Y0 = 1 1 or Y1 Y0 = 0 1
- d) Y1 Y0 = 1 0 or Y1 Y0 = 0 1
Solution:
D1 = Y0·Y1 + Y0'·Y1' = XNOR(Y0, Y1)
D0 = Y1·X' + Y1'·X = XOR(Y1, X)
At Y1=1, Y0=1:
D1 = 1·1 + 0·0 = 1 (always 1 regardless of X)
D0 = 1·X' + 0·X = X'
If X=0: next state = Y1 Y0 = 1 1
If X=1: next state = Y1 Y0 = 1 0
Possible next states: 1 0 or 1 1
EE1D2 Lecture 3 — Memory Systems, ROM/PLA/PAL/FPGA Logic