Memory as Logic: ROM Lookup Tables and ROM Sequencers
Use a ROM as a truth table, and build a state machine whose behaviour is a table of words.
You Will Be Able To
- Read a ROM as the truth table of its address bits.
- Size a ROM for a function of n inputs and m outputs.
- Build a state machine from a ROM and a state register.
- Fill the words of a ROM sequencer from a state table.
- Lesson
- G8.6
- Time
- 30 min
- Runs on
- Your browser
- Check
- 4 questions
A detector should flag every 1 0 1 in a bit stream, and matches may overlap. On 1 0 1 0 1 it flagged only the first one. The logic was a ROM, and one word of it was wrong.
state is the state after the edge, and hit is 1 after a match.- Cycle 2
The input has been 1, 0, 1.
hitis 1. But the state goes back to 0, so the last 1 is forgotten. - Cycle 4
The input has been 1, 0, 1 again, sharing its first 1 with the last match. The detector is in state 1 and says nothing.
Measured on Icarus Verilog: the example of this lesson as it ships, edges 1 to 10.
A ROM Is a Truth Table
A ROM with n address bits has 2n words. Read the address bits as inputs and the word as outputs. The ROM is then the truth table of any function of those inputs.
This ROM has 8 words of 2 bits: a full adder. Set the inputs, and the lit word line is the address. Its two stored bits are the carry and the sum.
Edit a cell of the table, and the ROM stores another function. The decoder does not change. Only the stored bits do.
| Address bits | Words | Yosys cells for 4-bit words |
|---|---|---|
| 4 | 16 | 21 |
| 6 | 64 | 93 |
| 8 | 256 | 349 |
Measured with Yosys on ROMs with seeded, irregular contents. Yosys turns the table into minimized gates, so the counts depend on the contents. A ROM array would grow by exactly four times.
Inside the ROM: A Decoder and an OR Plane
A ROM is two layers of logic. A decoder turns the address into one row line per word. Each output bit is then an OR of the rows where that bit is 1.
- I/O
- Control / FSM
- Datapath
- Data
- Decode
The decoder raises one row line, the minterm of the address. It is the AND plane of the ROM, and it is fixed.
- OR plane
Each output column has a dot on every row where it holds a 1. Only the dots change from one ROM to another.
- Read
The column is 1 if the raised row has a dot in it. So each output is a sum of minterms: the canonical form of its truth table.
Read the diagram as text
- Address: n bits
- Decoder: one row line per word
- OR plane: a dot where a word holds a 1
- Word: m bits
- Address → Decoder: address
- Decoder → OR plane: one row is 1
- OR plane → Word: each column ORs its dots
A large ROM splits the decoder into rows and columns, as the SRAM of G8.3 does. The PLA of G13 makes both planes programmable.
So a ROM array never simplifies. It stores every minterm, even when a short formula exists. That is why it is cheap to change and costly to grow.
A State Machine in a ROM
Put a register around a ROM, and you have a state machine. The address is the state and the inputs. The word holds the next state and the outputs.
addr is the word this edge loaded: {old state, in}. state and hit are the values after the edge.- Cycle 0
State 0 with input 1 is address 1. Its word sends the machine to state 1: seen 1.
- Cycle 1
State 1 with input 0 is address 2. The machine moves to state 2: seen 1 0.
- Cycle 2
Address 5 is state 2 with input 1: a match. Its word is 01_1: next state 1 and hit = 1.
- Cycle 4
The last 1 of the first match started the second one. Address 5 again: a second hit.
- Cycle 7
A third match after 1 1 0 1. The run counts 3 matches.
Measured on Icarus Verilog: the example with rom[5] fixed, edges 1 to 10.
| Address | State | in | Word | Meaning |
|---|---|---|---|---|
| 0 | 0 | 0 | 00_0 | stay in 0 |
| 1 | 0 | 1 | 01_0 | seen 1 |
| 2 | 1 | 0 | 10_0 | seen 1 0 |
| 3 | 1 | 1 | 01_0 | still seen 1 |
| 4 | 2 | 0 | 00_0 | start again |
| 5 | 2 | 1 | 01_1 | match, and seen 1 |
The ROM of the fixed detector. Words 6 and 7 belong to state 3, which is never reached.
- I/O
- Storage
- Data
- Control
- Address
The state and the inputs together form the address.
- Word
One field of the word is the next state. The rest are the outputs.
- Edge
At the clock edge the register loads the next state, and a new address is formed.
Read the diagram as text
- Inputs: low address bits
- ROM: the state table
- State register: loads at the clock edge
- Outputs: the other word bits
- State register → ROM: state: high address bits
- Inputs → ROM: inputs
- ROM → State register: next state
- ROM → Outputs: outputs
The hardware never changes. A new table gives a new machine. This is the idea behind a microprogrammed controller.
A match goes back to state 0
rom[5] = 3'b00_1;
Icarus: 2 matches. The match at edge 5 is missed.
A match goes to state 1
rom[5] = 3'b01_1;
Icarus: 3 matches. Overlapping matches are found.
Asked in interviews
How can a memory implement logic?
Use the inputs as the address and store the truth table as the words. Each output bit is a column of the table. Any function of the address bits fits, however irregular.
When is a ROM a poor choice?
When there are many inputs. Each input doubles the number of words. A wide, regular function such as an adder is far smaller as logic.
What is a ROM-based state machine?
A state register and a ROM. The address is the state plus the inputs, and each word holds the next state and the outputs. Changing the table changes the machine without new logic.
Try It
The input is 1 0 1 0 1 1 0 1 0 0. It holds three 1 0 1 patterns, and the first two share a 1.
Line e3 shows hit=1, but state=0. The ROM sent the machine back to the start, so the 1 at edge 3 is forgotten.
At edge 5 the input has been 1, 0, 1 again, but hit stays 0. The run ends with 2 matches.
Fix the word rom[5]: its next state must be 1, so the word is 3'b01_1. Run again: line e3 shows state=1, line e5 shows hit=1, and the run ends with 3 matches.
Synthesize the design to measure its cells and inspect the mapped gates.
e1 in=1 addr=1 state=1 hit=0 e2 in=0 addr=2 state=2 hit=0 e3 in=1 addr=5 state=0 hit=1 e4 in=0 addr=0 state=0 hit=0 e5 in=1 addr=1 state=1 hit=0 e6 in=1 addr=3 state=1 hit=0 e7 in=0 addr=2 state=2 hit=0 e8 in=1 addr=5 state=0 hit=1 e9 in=0 addr=0 state=0 hit=0 e10 in=0 addr=0 state=0 hit=0 2 matchesOriginal design · 10 cells · 3 flip-flops · 0 latches · 2 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
// tb.sv: the bench (read-only). It feeds 1 0 1 0 1 1 0 1 0 0 and prints one line per clock edge.
`timescale 1ns/1ps
module tb;
logic clk = 0, rst = 1, in = 0;
wire hit;
int hits = 0;
logic [2:0] a;
logic [9:0] stream = 10'b0010110101; // read from bit 0 up: 1 0 1 0 1 1 0 1 0 0
rom_fsm dut (.clk(clk), .rst(rst), .in(in), .hit(hit));
always #5 clk = ~clk;
initial begin
@(posedge clk); #1 rst = 0;
for (int k = 0; k < 10; k++) begin
in = stream[k];
#1 a = {dut.state, in}; // the ROM address this edge loads
@(posedge clk); #1;
$display("e%0d in=%b addr=%0d state=%0d hit=%b", k + 1, in, a, dut.state, hit);
hits += hit;
end
$display("%0d matches", hits);
$finish(0);
end
endmodule
Check Yourself
Common Mistakes
Wrong Write one ROM word of the state table wrong.
The machine follows its table blindly. With rom[5] sending a match back to state 0, the lab counts 2 matches, not 3.
Fix Check each word against the state table: next state first, then the output bits.
rom[5] = 3'b00_1;rom[5] = 3'b01_1;Wrong Build the address in a different bit order from the table.
Every lookup reads the wrong row. In the spot item, rom[{in, state}] finds the wrong number of matches.
Fix Write the address order once, in a comment beside the table, and build the address in exactly that order.
Wrong Leave the inputs out of the address.
Each state then has one word, so the next state cannot depend on the input.
Fix The address is the state and every input that the next state or the outputs depend on.
Wrong Use a ROM for a function of many inputs.
Each input bit doubles the words: Yosys builds 21 cells for a 16-word ROM and 349 cells for a 256-word one.
Fix Use a ROM when the inputs are few and the function is irregular. Use logic for wide, regular functions.
Remember
- A ROM is a truth table: the address bits are the inputs and the word bits the outputs.
- n address bits give 2n words, so a ROM suits few inputs and irregular functions.
- Inside, a ROM is a fixed decoder and an OR plane of stored dots.
- A ROM plus a state register is a state machine: the address is {state, inputs}, the word is {next state, outputs}.
- Build the address in exactly the order the table was written for.