Single-port RAM in VHDL - Time & Space Complexity

Time Complexity: Single-port RAM in VHDL

O(1)

Understanding Time Complexity

When working with single-port RAM in VHDL, it is important to understand how the time to access memory changes as the memory size grows.

We want to know how the number of steps to read or write data changes when the memory gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity single_port_ram is
  port(
    clk : in std_logic;
    addr : in unsigned(7 downto 0);
    data_in : in std_logic_vector(7 downto 0);
    data_out : out std_logic_vector(7 downto 0);
    we : in std_logic
  );
end entity single_port_ram;

architecture rtl of single_port_ram is
  type ram_type is array (0 to 255) of std_logic_vector(7 downto 0);
  signal ram : ram_type := (others => (others => '0'));
begin
  process(clk) is
  begin
    if rising_edge(clk) then
      if we = '1' then
        ram(to_integer(addr)) <= data_in;
      end if;
      data_out <= ram(to_integer(addr));
    end if;
  end process;
end architecture rtl;

This code defines a single-port RAM with 256 memory locations. On each clock, it writes data if enabled and always reads data from the given address.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing the RAM array at the given address.
• How many times: Once per clock cycle for read and possibly once for write.

How Execution Grows With Input

Each read or write accesses one memory location directly by address, no loops or repeated steps over the memory size.

Input Size (n)	Approx. Operations
256	1 access per clock
512	1 access per clock
1024	1 access per clock

Pattern observation: The number of steps stays the same no matter how big the memory is because each access is direct.

Final Time Complexity

Time Complexity: O(1)

This means the time to read or write data does not grow as the memory size increases; it stays constant.

Common Mistake

[X] Wrong: "Accessing memory takes longer as the memory size grows because it has to check many locations."

[OK] Correct: In single-port RAM, the address directly points to the location, so the access time stays the same regardless of size.

Interview Connect

Understanding how memory access time behaves helps you explain hardware design choices clearly and shows you grasp how hardware handles data efficiently.

Self-Check

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

Practice

1. What is the main function of a single-port RAM in VHDL?

easy

A. Generate clock signals

B. Store data using one address and one data line

C. Perform arithmetic operations

D. Control input/output pins

Solution

1. Step 1: Understand the role of single-port RAM

   Single-port RAM is designed to store data at a specific address with one data input and output line.

2. Step 2: Identify the correct function

   It does not perform arithmetic, generate clocks, or control pins; it only stores and retrieves data.

3. Final Answer:

   Store data using one address and one data line -> Option B

4. Quick Check:

   Single-port RAM = Data storage [OK]

Hint: Single-port RAM stores data at one address line [OK]

Common Mistakes:

• Confusing RAM with arithmetic units
• Thinking RAM generates clocks
• Assuming RAM controls I/O pins

2. Which VHDL statement correctly declares a single-port RAM with 16 locations of 8-bit width?

easy

A. signal ram : std_logic_vector(7 downto 0) array (0 to 15);

B. signal ram : std_logic_vector(15 downto 0)(7 downto 0);

C. type ram_type is array (0 to 15) of std_logic_vector(7 downto 0);\nsignal ram : ram_type;

D. type ram_type is array (7 downto 0) of std_logic_vector(0 to 15);\nsignal ram : ram_type;

Solution

1. Step 1: Understand array declaration syntax

   In VHDL, RAM is declared as an array of std_logic_vector with address range and data width.

2. Step 2: Check each option

   type ram_type is array (0 to 15) of std_logic_vector(7 downto 0);\nsignal ram : ram_type; correctly declares an array from 0 to 15 with 8-bit vectors. Others have incorrect syntax or order.

3. Final Answer:

   type ram_type is array (0 to 15) of std_logic_vector(7 downto 0); signal ram : ram_type; -> Option C

4. Quick Check:

   Correct array declaration = type ram_type is array (0 to 15) of std_logic_vector(7 downto 0);\nsignal ram : ram_type; [OK]

Hint: Use 'array (0 to N) of std_logic_vector(width downto 0)' [OK]

Common Mistakes:

• Reversing array and vector ranges
• Using incorrect syntax for array of vectors
• Declaring signal without type

3. Given this VHDL process for single-port RAM:

process(clk) begin
  if rising_edge(clk) then
    if we = '1' then
      ram(to_integer(unsigned(addr))) <= data_in;
    end if;
    data_out <= ram(to_integer(unsigned(addr)));
  end if;
end process;

What happens when we is '1' and addr is 3?

medium

A. Data at address 3 is updated but data_out shows old data

B. Data at address 3 is not updated but data_out shows old data

C. Data at address 3 is updated with data_in and data_out shows new data

D. No change occurs in RAM or output

Solution

1. Step 1: Analyze write operation timing

   On rising clock edge, if write enable (we) is '1', RAM at address is updated with data_in.

2. Step 2: Analyze read operation timing

   Data_out is assigned from RAM at address after write, but read happens before write completes, so old data is output.

3. Final Answer:

   Data at address 3 is updated but data_out shows old data -> Option A

4. Quick Check:

   Write updates RAM, read outputs old data [OK]

Hint: Write updates RAM, read outputs previous data same cycle [OK]

Common Mistakes:

• Assuming read shows new data immediately
• Confusing write enable effect
• Ignoring clock edge timing

4. Identify the error in this single-port RAM process:

process(clk) begin
  if clk'event and clk = '1' then
    if we = '1' then
      ram(addr) <= data_in;
    end if;
    data_out <= ram(addr);
  end if;
end process;

medium

A. Using clk'event and clk = '1' instead of rising_edge(clk)

B. No error, code is correct

C. Assigning data_out inside clocked process

D. Missing conversion from std_logic_vector to integer for addr

Solution

1. Step 1: Check clock edge detection

   Using clk'event and clk = '1' is valid but less recommended than rising_edge(clk).

2. Step 2: Check address usage

   Address 'addr' is likely std_logic_vector and must be converted to integer for RAM indexing.

3. Final Answer:

   Missing conversion from std_logic_vector to integer for addr -> Option D

4. Quick Check:

   Address must be integer index [OK]

Hint: Convert std_logic_vector addr to integer for RAM indexing [OK]

Common Mistakes:

• Using std_logic_vector directly as index
• Ignoring recommended rising_edge(clk)
• Thinking data_out can't be assigned in process

5. How would you modify a single-port RAM VHDL design to asynchronously clear all memory contents to zero on a reset signal?

hard

A. Add an asynchronous reset in the process that sets all RAM locations to zero

B. Use a synchronous reset that clears only the current address data

C. Add a separate process that writes zeros to RAM on reset clock edge

D. Reset signal cannot clear RAM contents in VHDL

Solution

1. Step 1: Understand asynchronous reset effect

   An asynchronous reset triggers immediately, allowing clearing all RAM locations regardless of clock.

2. Step 2: Implement reset logic

   Inside the clocked process, add a condition for reset that loops through all RAM addresses and sets them to zero.

3. Final Answer:

   Add an asynchronous reset in the process that sets all RAM locations to zero -> Option A

4. Quick Check:

   Async reset clears entire RAM [OK]

Hint: Use async reset to zero all RAM locations immediately [OK]

Common Mistakes:

• Clearing only one address on reset
• Using synchronous reset for full RAM clear
• Believing reset can't clear RAM