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.

The Second Match Is MissedEach column is one clock edge. state is the state after the edge, and hit is 1 after a match.
0123456789clkinstate120120hitshould be a match
Scroll horizontally ↔
  1. Cycle 2

    The input has been 1, 0, 1. hit is 1. But the state goes back to 0, so the last 1 is forgotten.

  2. 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.

A Full Adder Stored in a ROM
abcincoutsum
000
001
010
011
100
101
110
111
  • cout = Σm(3, 5, 6, 7)
  • sum = Σm(1, 2, 4, 7)

Each output alone

  • cout = b & cin | a & cin | a & b
  • sum = ~a & ~b & cin | ~a & b & ~cin | a & ~b & ~cin | a & b & cin

7 terms · 18 literals

Shared product terms

  • cout = b & cin | a & cin | a & b
  • sum = ~a & ~b & cin | ~a & b & ~cin | a & ~b & ~cin | a & b & cin

7 distinct terms · 18 literals. No term helps more than one output here.

A ROM decodes every address: one word line per input combination (the AND plane is a full decoder), and the stored bits are the OR plane. 8 words × 2 bits; don't-cares are stored as 0.

AND and OR planesword 0word 1word 2word 3word 4word 5word 6word 7aa′bb′cincin′coutsumAND planeOR plane
  1. word 0
    a ○a′ ●b ○b′ ●cin ○cin′ ●
    cout ○sum ○
  2. word 1
    a ○a′ ●b ○b′ ●cin ●cin′ ○
    cout ○sum ●
  3. word 2
    a ○a′ ●b ●b′ ○cin ○cin′ ●
    cout ○sum ●
  4. word 3
    a ○a′ ●b ●b′ ○cin ●cin′ ○
    cout ●sum ○
  5. word 4
    a ●a′ ○b ○b′ ●cin ○cin′ ●
    cout ○sum ●
  6. word 5
    a ●a′ ○b ○b′ ●cin ●cin′ ○
    cout ●sum ○
  7. word 6
    a ●a′ ○b ●b′ ○cin ○cin′ ●
    cout ●sum ○
  8. word 7
    a ●a′ ○b ●b′ ○cin ●cin′ ○
    cout ●sum ●
Addressabcincoutsum
000000
100101
201001
301110
410001
510110
611010
711111

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 bitsWordsYosys cells for 4-bit words
41621
66493
8256349

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.

A ROM as a Decoder and an OR PlaneArrows show the path of one read. A dot in the OR plane means that word holds a 1 in that column.
  • I/O
  • Control / FSM
  • Datapath
  • Data
A ROM as a decoder and an OR planeArrows show the path of one read. A dot in the OR plane means that word holds a 1 in that column. io Address n bits control Decoder one row line per word datapath OR plane a dot where a wordholds a 1 io Word m bits addressone row is 1each column ORs itsdots
  1. io Addressn bits
    • address → Decoder
  2. control Decoderone row line per word
    • one row is 1 → OR plane
  3. datapath OR planea dot where a word holds a 1
    • each column ORs its dots → Word
  4. io Wordm bits
  1. Decode

    The decoder raises one row line, the minterm of the address. It is the AND plane of the ROM, and it is fixed.

  2. 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.

  3. 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.

The 101 Detector, with Its ROM FixedEach column is one clock edge. addr is the word this edge loaded: {old state, in}. state and hit are the values after the edge.
0123456789clkinaddr1252532524state121212120hit
Scroll horizontally ↔
  1. Cycle 0

    State 0 with input 1 is address 1. Its word sends the machine to state 1: seen 1.

  2. Cycle 1

    State 1 with input 0 is address 2. The machine moves to state 2: seen 1 0.

  3. Cycle 2

    Address 5 is state 2 with input 1: a match. Its word is 01_1: next state 1 and hit = 1.

  4. Cycle 4

    The last 1 of the first match started the second one. Address 5 again: a second hit.

  5. 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.

AddressStateinWordMeaning
00000_0stay in 0
10101_0seen 1
21010_0seen 1 0
31101_0still seen 1
42000_0start again
52101_1match, and seen 1

The ROM of the fixed detector. Words 6 and 7 belong to state 3, which is never reached.

The ROM Sequencer LoopArrows show what feeds what. The loop closes through the state register once per clock edge.
  • I/O
  • Storage
  • Data
  • Control
The ROM sequencer loopArrows show what feeds what. The loop closes through the state register once per clock edge. io Inputs low address bits storage ROM the state table storage State register loads at the clockedge io Outputs the other word bits state: high addressbitsinputsnext stateoutputs
  1. storage State registerloads at the clock edge
    • state: high address bits → ROM
  2. io Inputslow address bits
    • inputs → ROM
  3. storage ROMthe state table
    • next state → State register
    • outputs → Outputs
  4. io Outputsthe other word bits
  1. Address

    The state and the inputs together form the address.

  2. Word

    One field of the word is the next state. The rest are the outputs.

  3. 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
  1. 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.

  2. 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.

  3. 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.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: 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 matches

Original 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

Predict the outputThis ROM holds a 2-bit counter with an enable. What exact line does the program print?
module tb;
  logic [1:0] rom [8];                     // the word at {s, en} is the next value of s
  logic [1:0] s = 2'd0;
  logic [4:0] en = 5'b11011;               // used from bit 0 up
  initial begin
    for (int k = 0; k < 8; k++) rom[k] = k[0] ? 2'(k[2:1] + 1) : 2'(k[2:1]);
    for (int k = 0; k < 5; k++) s = rom[{s, en[k]}];
    $display("s=%0d", s);
  end
endmodule
Spot the bugEach option forms the ROM address of the detector. The input holds four overlapping 1 0 1 patterns. Which option gets the count wrong?
ConceptHow many words does a ROM need for a function of 6 inputs and 3 outputs?
ConceptWhy might a designer put a state machine in a ROM instead of in gates?

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.

Before
rom[5] = 3'b00_1;
After
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.

Practice

Report a problem with this page