ROM (Read-Only Memory) in Verilog - Time & Space Complexity

Time Complexity: ROM (Read-Only Memory) in Verilog

O(1)

Understanding Time Complexity

We want to understand how the time to read data from a ROM changes as the size of the memory grows.

How does the number of steps needed to get data change when the ROM size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module rom(
  input wire [3:0] addr,
  output reg [7:0] data
);
  always @(*) begin
    case(addr)
      4'd0: data = 8'hA1;
      4'd1: data = 8'hB2;
      4'd2: data = 8'hC3;
      // ... more addresses ...
      default: data = 8'h00;
    endcase
  end
endmodule

This code models a ROM that outputs a fixed 8-bit value based on a 4-bit address input.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The case statement checks the input address against stored values.
• How many times: Each read checks the address once; no loops or repeated traversals happen during a single read.

How Execution Grows With Input

Reading from ROM is like looking up a value in a fixed list by address.

Input Size (n)	Approx. Operations
10	1 check per read
100	1 check per read
1000	1 check per read

Pattern observation: The number of steps to read data stays the same no matter how big the ROM is.

Final Time Complexity

Time Complexity: O(1)

This means reading data from ROM takes the same amount of time regardless of how many entries it has.

Common Mistake

[X] Wrong: "Reading from ROM takes longer if the ROM has more data because it checks each entry one by one."

[OK] Correct: ROM uses the address directly to get data instantly, not by searching through all entries.

Interview Connect

Knowing that ROM reads are constant time helps you understand hardware design and how memory access works efficiently.

Self-Check

"What if the ROM was implemented using a loop to search for the address instead of a direct case statement? How would the time complexity change?"

Practice

1. What is the primary purpose of a ROM (Read-Only Memory) in Verilog?

easy

A. To store fixed data that cannot be changed during simulation or operation

B. To store data that can be written and read dynamically

C. To perform arithmetic operations

D. To generate clock signals

Solution

1. Step 1: Understand ROM functionality

   ROM is designed to hold data that is fixed and cannot be modified during operation.

2. Step 2: Compare with other memory types

   Unlike RAM, ROM data is read-only and does not support writing during runtime.

3. Final Answer:

   To store fixed data that cannot be changed during simulation or operation -> Option A

4. Quick Check:

   ROM = fixed data storage [OK]

Hint: ROM stores fixed data only, no writes allowed [OK]

Common Mistakes:

• Confusing ROM with RAM (read-write memory)
• Thinking ROM can perform operations
• Assuming ROM generates signals

2. Which of the following is the correct way to declare a ROM using an array and initial block in Verilog?

easy

A. integer rom_mem; always @(posedge clk) rom_mem = 8'hAA;

B. wire [7:0] rom_mem [0:3]; always @(posedge clk) rom_mem[0] <= 8'hAA;

C. reg [7:0] rom_mem; initial rom_mem = 8'hAA;

D. reg [7:0] rom_mem [0:3]; initial begin rom_mem[0] = 8'hAA; rom_mem[1] = 8'hBB; rom_mem[2] = 8'hCC; rom_mem[3] = 8'hDD; end

Solution

1. Step 1: Identify correct ROM declaration

   ROM is declared as a reg array with an initial block to assign fixed values.

2. Step 2: Check each option

   reg [7:0] rom_mem [0:3]; initial begin rom_mem[0] = 8'hAA; rom_mem[1] = 8'hBB; rom_mem[2] = 8'hCC; rom_mem[3] = 8'hDD; end uses reg array and initial block correctly. wire [7:0] rom_mem [0:3]; always @(posedge clk) rom_mem[0] <= 8'hAA; uses wire and always block incorrectly. Options C and D do not declare arrays properly.

3. Final Answer:

   reg [7:0] rom_mem [0:3]; initial begin rom_mem[0] = 8'hAA; rom_mem[1] = 8'hBB; rom_mem[2] = 8'hCC; rom_mem[3] = 8'hDD; end -> Option D

4. Quick Check:

   ROM array + initial block = reg [7:0] rom_mem [0:3]; initial begin rom_mem[0] = 8'hAA; rom_mem[1] = 8'hBB; rom_mem[2] = 8'hCC; rom_mem[3] = 8'hDD; end [OK]

Hint: Use reg array with initial block for ROM data [OK]

Common Mistakes:

• Using wire instead of reg for ROM array
• Assigning inside always block for ROM
• Not using an array for multiple ROM entries

3. Given the following Verilog ROM code, what is the output value of data_out when addr = 2'b10?

module rom_example(input [1:0] addr, output reg [7:0] data_out);
  always @(*) begin
    case(addr)
      2'b00: data_out = 8'h1A;
      2'b01: data_out = 8'h2B;
      2'b10: data_out = 8'h3C;
      2'b11: data_out = 8'h4D;
      default: data_out = 8'h00;
    endcase
  end
endmodule

medium

A. 8'h4D

B. 8'h1A

C. 8'h3C

D. 8'h00

Solution

1. Step 1: Locate the case for addr = 2'b10

   The case statement assigns data_out = 8'h3C when addr is 2'b10.

2. Step 2: Confirm output value

   Since addr matches 2'b10, data_out will be 8'h3C.

3. Final Answer:

   8'h3C -> Option C

4. Quick Check:

   addr 2'b10 -> data_out 8'h3C [OK]

Hint: Match addr in case to find data_out quickly [OK]

Common Mistakes:

• Choosing wrong case label
• Confusing hex values
• Ignoring default case

4. Identify the error in this ROM Verilog code snippet:

module rom_bug(input [1:0] addr, output reg [7:0] data_out);
  reg [7:0] rom_mem [0:3];
  initial begin
    rom_mem[0] = 8'hAA;
    rom_mem[1] = 8'hBB;
    rom_mem[2] = 8'hCC;
    rom_mem[3] = 8'hDD;
  end
  always @(*) begin
    data_out = rom_mem[addr];
  end
endmodule

medium

A. ROM array should be declared as wire, not reg

B. No error; code correctly implements ROM

C. Initial block cannot be used for ROM initialization

D. Using addr as index without conversion causes error

Solution

1. Step 1: Check ROM declaration and initialization

   ROM is declared as reg array and initialized in initial block, which is correct for simulation.

2. Step 2: Verify data output assignment

   Using addr as index to read rom_mem is valid and data_out is assigned in combinational always block.

3. Final Answer:

   No error; code correctly implements ROM -> Option B

4. Quick Check:

   ROM reg array + initial + combinational read = correct [OK]

Hint: ROM uses reg array + initial block + combinational read [OK]

Common Mistakes:

• Thinking initial block is illegal for ROM
• Confusing reg and wire for ROM arrays
• Assuming addr needs conversion

5. You want to implement a 4-word ROM in Verilog that outputs the square of the address value (0, 1, 4, 9). Which of the following code snippets correctly implements this ROM?

hard

A. always @(addr) begin case(addr) 2'b00: data_out=8'd0; 2'b01: data_out=8'd1; 2'b10: data_out=8'd4; 2'b11: data_out=8'd9; default: data_out=8'd0; endcase end

B. reg [7:0] rom [0:3]; initial begin rom[0]=8'd0; rom[1]=8'd1; rom[2]=8'd4; rom[3]=8'd9; end always data_out = rom[addr];

C. reg [7:0] rom [0:3]; assign rom[0]=0; assign rom[1]=1; assign rom[2]=4; assign rom[3]=9; assign data_out=rom[addr];

D. reg [7:0] rom [0:3]; always @(posedge clk) begin rom[0]<=0; rom[1]<=1; rom[2]<=4; rom[3]<=9; end assign data_out=rom[addr];

Solution

1. Step 1: Analyze each code snippet for ROM implementation

   reg [7:0] rom [0:3]; initial begin rom[0]=8'd0; rom[1]=8'd1; rom[2]=8'd4; rom[3]=8'd9; end always @(*) data_out = rom[addr]; lacks module and always block structure; data_out assignment is incomplete. always @(addr) begin case(addr) 2'b00: data_out=8'd0; 2'b01: data_out=8'd1; 2'b10: data_out=8'd4; 2'b11: data_out=8'd9; default: data_out=8'd0; endcase end uses a case statement to output fixed squares based on addr, which is a valid ROM implementation. reg [7:0] rom [0:3]; assign rom[0]=0; assign rom[1]=1; assign rom[2]=4; assign rom[3]=9; assign data_out=rom[addr]; tries to assign values to wire array elements, which is illegal. reg [7:0] rom [0:3]; always @(posedge clk) begin rom[0]<=0; rom[1]<=1; rom[2]<=4; rom[3]<=9; end assign data_out=rom[addr]; tries to assign ROM values inside a clocked always block, which is not suitable for ROM initialization.

2. Step 2: Confirm correct ROM behavior

   always @(addr) begin case(addr) 2'b00: data_out=8'd0; 2'b01: data_out=8'd1; 2'b10: data_out=8'd4; 2'b11: data_out=8'd9; default: data_out=8'd0; endcase end correctly outputs squares for each address using a combinational case statement, matching ROM behavior.

3. Final Answer:

   always @(addr) begin case(addr) 2'b00: data_out=8'd0; 2'b01: data_out=8'd1; 2'b10: data_out=8'd4; 2'b11: data_out=8'd9; default: data_out=8'd0; endcase end -> Option A

4. Quick Check:

   ROM as combinational case statement = always @(addr) begin case(addr) 2'b00: data_out=8'd0; 2'b01: data_out=8'd1; 2'b10: data_out=8'd4; 2'b11: data_out=8'd9; default: data_out=8'd0; endcase end [OK]

Hint: Use case statement for fixed ROM outputs [OK]

Common Mistakes:

• Assigning to wire arrays
• Initializing ROM inside clocked always block
• Not using combinational logic for ROM output