Single-port RAM design in Verilog - Time & Space Complexity

Time Complexity: Single-port RAM design

O(1)

Understanding Time Complexity

When designing a single-port RAM in Verilog, it is important to understand how the time to access memory changes as the size of the memory grows.

We want to know how the number of operations changes when we increase the memory size.

Scenario Under Consideration

Analyze the time complexity of the following single-port RAM code snippet.

module single_port_ram (
  input wire clk,
  input wire we,
  input wire [7:0] addr,
  input wire [7:0] data_in,
  output reg [7:0] data_out
);
  reg [7:0] ram [0:255];

  always @(posedge clk) begin
    if (we) ram[addr] <= data_in;
    data_out <= ram[addr];
  end
endmodule

This code models a memory with 256 locations, each 8 bits wide, accessed through a single port for reading or writing.

Identify Repeating Operations

In this design, the main operation is accessing the memory array at a given address.

• Primary operation: Reading or writing one memory location per clock cycle.
• How many times: Once per clock cycle, regardless of memory size.

How Execution Grows With Input

Accessing memory happens in a fixed time each cycle, no matter how big the memory is.

Input Size (memory locations)	Approx. Operations per access
10	1
100	1
1000	1

Pattern observation: The time to read or write one location stays the same even if the memory size grows.

Final Time Complexity

Time Complexity: O(1)

This means each memory access takes a constant amount of time, no matter how large the memory is.

Common Mistake

[X] Wrong: "Accessing larger memory takes more time because there are more locations to check."

[OK] Correct: Memory hardware uses direct addressing, so it jumps straight to the location without checking others, keeping access time constant.

Interview Connect

Understanding that single-port RAM access time is constant helps you explain hardware efficiency clearly and confidently in interviews.

Self-Check

"What if we changed the design to a multi-port RAM allowing simultaneous accesses? How would the time complexity change?"

Practice

1. What is the main characteristic of a single-port RAM in Verilog?

easy

A. It stores data without any clock or control signals.

B. It can read and write data simultaneously on separate ports.

C. It uses one address line for both reading and writing operations.

D. It requires two clocks for read and write operations.

Solution

1. Step 1: Understand single-port RAM basics

   Single-port RAM has only one address line used for both reading and writing data.

2. Step 2: Compare with other RAM types

   Unlike dual-port RAM, it cannot perform read and write simultaneously on different ports.

3. Final Answer:

   It uses one address line for both reading and writing operations. -> Option C

4. Quick Check:

   Single-port RAM = one address line for read/write [OK]

Hint: Single-port RAM uses one address for both read and write [OK]

Common Mistakes:

• Thinking it can read and write at the same time
• Assuming it needs two clocks
• Believing it works without a clock

2. Which of the following is the correct Verilog syntax to declare a 256x8 single-port RAM memory array?

easy

A. wire [7:0] mem [255:0];

B. memory [7:0] mem [0:255];

C. reg mem [7:0] [0:255];

D. reg [7:0] mem [0:255];

Solution

1. Step 1: Understand Verilog memory declaration

   Memory arrays are declared as reg [width-1:0] name [address_range]; for RAM.

2. Step 2: Check each option

   reg [7:0] mem [0:255]; correctly declares 256 locations (0 to 255) each 8 bits wide. wire [7:0] mem [255:0]; uses wire which is incorrect for RAM storage. reg mem [7:0] [0:255]; reverses dimensions. memory [7:0] mem [0:255]; uses invalid keyword.

3. Final Answer:

   reg [7:0] mem [0:255]; -> Option D

4. Quick Check:

   RAM declaration = reg [7:0] mem [0:255] [OK]

Hint: Use reg with [width-1:0] and address range [OK]

Common Mistakes:

• Using wire instead of reg for RAM
• Swapping width and address range
• Using invalid keywords like memory

3. Given the following Verilog code snippet for a single-port RAM, what is the value of data_out after the clock edge if we = 1, addr = 3, and data_in = 8'hAA?

reg [7:0] mem [0:7];
always @(posedge clk) begin
  if (we) mem[addr] <= data_in;
  data_out <= mem[addr];
end

medium

A. 8'hAA

B. Previous value stored at mem[3]

C. 8'h00

D. Undefined (X)

Solution

1. Step 1: Analyze write and read order in always block

   The write happens first: if we=1, mem[3] is updated with 8'hAA. Then data_out is assigned mem[3].

2. Step 2: Understand non-blocking assignment timing

   Non-blocking assignments update after the always block finishes, so data_out reads the old value of mem[3] before write.

3. Final Answer:

   Previous value stored at mem[3] -> Option B

4. Quick Check:

   Non-blocking write then read = old value [OK]

Hint: Non-blocking writes update after reads in same clock [OK]

Common Mistakes:

• Assuming data_out immediately shows new data_in
• Confusing blocking and non-blocking assignments
• Ignoring timing of memory update

4. Identify the error in this single-port RAM Verilog code snippet:

reg [7:0] mem [0:15];
always @(posedge clk) begin
  if (we)
    mem[addr] = data_in;
  else
    data_out = mem[addr];
end

medium

A. Using blocking assignments (=) instead of non-blocking (<=) inside always block.

B. Memory size declaration is incorrect.

C. Missing reset signal for memory initialization.

D. Address width is not declared.

Solution

1. Step 1: Check assignment types in sequential always block

   Inside clocked always blocks, non-blocking assignments (<=) should be used to avoid race conditions.

2. Step 2: Verify other code parts

   Memory size and address width are not shown but not necessarily errors here. Reset is optional.

3. Final Answer:

   Using blocking assignments (=) instead of non-blocking (<=) inside always block. -> Option A

4. Quick Check:

   Use <= in clocked always blocks [OK]

Hint: Use <= for sequential logic inside always @(posedge clk) [OK]

Common Mistakes:

• Using = instead of <= in clocked blocks
• Assuming reset is mandatory
• Ignoring address width declaration

5. You want to design a single-port RAM in Verilog that supports synchronous write and asynchronous read. Which code snippet correctly implements this behavior?

hard

A. reg [7:0] mem [0:15];
always @(posedge clk) begin
if (we) mem[addr] <= data_in;
end
assign data_out = mem[addr];

B. reg [7:0] mem [0:15];
always @(posedge clk) begin
if (we) mem[addr] <= data_in;
data_out <= mem[addr];
end

C. reg [7:0] mem [0:15];
always @(addr or we or data_in) begin
if (we) mem[addr] = data_in;
end
assign data_out = mem[addr];

D. reg [7:0] mem [0:15];
always @(posedge clk) begin
if (we) mem[addr] = data_in;
end
always @(addr) begin
data_out = mem[addr];
end

Solution

1. Step 1: Understand synchronous write and asynchronous read

   Write happens on clock edge with write enable; read happens anytime from memory asynchronously.

2. Step 2: Analyze each code snippet

   reg [7:0] mem [0:15];
   always @(posedge clk) begin
     if (we) mem[addr] <= data_in;
   end
   assign data_out = mem[addr];

   uses clocked always block for write and continuous assignment for asynchronous read, which is correct.

   reg [7:0] mem [0:15];
   always @(posedge clk) begin
     if (we) mem[addr] <= data_in;
     data_out <= mem[addr];
   end

   reads synchronously.

   reg [7:0] mem [0:15];
   always @(addr or we or data_in) begin
     if (we) mem[addr] = data_in;
   end
   assign data_out = mem[addr];

   uses combinational always block for write, which is incorrect.

   reg [7:0] mem [0:15];
   always @(posedge clk) begin
     if (we) mem[addr] = data_in;
   end
   always @(addr) begin
     data_out = mem[addr];
   end

   uses blocking assignment in clocked block and asynchronous read in always block, which is not standard.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Synchronous write + async read = clocked write + assign read [OK]

Hint: Use clocked block for write, continuous assign for async read [OK]

Common Mistakes:

• Reading memory synchronously instead of asynchronously
• Using blocking assignments in clocked blocks
• Trying to write memory combinationally