SPI master controller in VHDL - Time & Space Complexity

Time Complexity: SPI master controller

O(n)

Understanding Time Complexity

We want to understand how the time needed to run an SPI master controller changes as the amount of data to send grows.

Specifically, how does the controller's work increase when sending more bits?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

process(clk)
  variable bit_count : integer := 0;
begin
  if rising_edge(clk) then
    if start = '1' then
      bit_count := 0;
      sclk <= '0';
    elsif bit_count < 8 then
      sclk <= not sclk;
      if sclk = '1' then
        mosi <= data(bit_count);
        bit_count := bit_count + 1;
      end if;
    end if;
  end if;
end process;

This code sends 8 bits one by one over SPI by toggling the clock and shifting out bits.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sending each bit by toggling the clock and outputting one bit on MOSI.
• How many times: The loop runs 8 times, once per bit to send.

How Execution Grows With Input

Each bit requires a fixed number of clock toggles and output steps.

Input Size (bits)	Approx. Operations
8	About 16 clock cycles and bit outputs
16	About 32 clock cycles and bit outputs
32	About 64 clock cycles and bit outputs

Pattern observation: The work grows directly with the number of bits to send. Double the bits, double the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to send data grows in a straight line with the number of bits.

Common Mistake

[X] Wrong: "The SPI controller sends all bits at once, so time does not grow with data size."

[OK] Correct: The SPI sends bits one after another, so more bits mean more clock cycles and more time.

Interview Connect

Understanding how hardware controllers like SPI scale with data size helps you explain timing and performance in embedded systems clearly and confidently.

Self-Check

"What if we changed the SPI to send 2 bits per clock cycle? How would the time complexity change?"

Practice

1. What is the primary role of the SPI master controller in VHDL designs?

easy

A. To convert SPI signals into parallel data only

B. To act as a slave device responding to SPI commands

C. To generate random data for SPI devices

D. To control the clock, chip select, and data lines for SPI communication

Solution

1. Step 1: Understand SPI roles

   The SPI master controls communication timing and signals like clock and chip select.

2. Step 2: Identify controller function

   The master sends and receives data by managing these lines, unlike a slave which only responds.

3. Final Answer:

   To control the clock, chip select, and data lines for SPI communication -> Option D

4. Quick Check:

   SPI master controls clock, chip select, data lines [OK]

Hint: Master controls clock and chip select lines [OK]

Common Mistakes:

• Confusing master with slave device
• Thinking master only sends data without control
• Assuming master generates random data

2. Which VHDL statement correctly declares a 8-bit shift register signal for SPI data?

easy

A. signal shift_reg : integer range 0 to 255;

B. signal shift_reg : std_logic_vector(7 downto 0);

C. signal shift_reg : std_logic;

D. signal shift_reg : bit_vector(0 to 7);

Solution

1. Step 1: Identify correct data type for shift register

   Shift registers for SPI data use std_logic_vector for bit-wise operations.

2. Step 2: Check syntax and range

   std_logic_vector(7 downto 0) correctly defines 8 bits from MSB to LSB.

3. Final Answer:

   signal shift_reg : std_logic_vector(7 downto 0); -> Option B

4. Quick Check:

   Use std_logic_vector(7 downto 0) for 8-bit register [OK]

Hint: Use std_logic_vector with downto for bit vectors [OK]

Common Mistakes:

• Using integer instead of bit vector
• Using bit_vector which is less common
• Declaring single bit instead of vector

3. Given this VHDL process snippet for SPI clock generation:

process(clk)
begin
  if rising_edge(clk) then
    if clk_div = 1 then
      spi_clk <= not spi_clk;
      clk_div <= 0;
    else
      clk_div <= clk_div + 1;
    end if;
  end if;
end process;

What is the frequency relationship between spi_clk and clk?

medium

A. spi_clk frequency equals clk frequency

B. spi_clk frequency is double clk frequency

C. spi_clk frequency is half of clk frequency

D. spi_clk frequency is unrelated to clk frequency

Solution

1. Step 1: Analyze clock division logic

   clk_div toggles spi_clk every 2 rising edges of clk, flipping spi_clk once per two clk cycles.

2. Step 2: Determine frequency ratio

   Since spi_clk toggles every 2 clk cycles, its frequency is half of clk frequency.

3. Final Answer:

   spi_clk frequency is half of clk frequency -> Option C

4. Quick Check:

   spi_clk toggles every 2 clk cycles = half frequency [OK]

Hint: Toggle output every 2 input cycles halves frequency [OK]

Common Mistakes:

• Assuming frequencies are equal
• Thinking frequency doubles
• Ignoring clk_div counter effect

4. Identify the error in this SPI master controller state machine snippet:

type state_type is (IDLE, LOAD, TRANSFER);
signal state : state_type := IDLE;

process(clk)
begin
  if rising_edge(clk) then
    case state is
      when IDLE =>
        if start = '1' then
          state <= LOAD;
        end if;
      when LOAD =>
        state <= TRANSFER;
      when TRANSFER =>
        if bit_count = 8 then
          state <= IDLE;
        end if;
    end case;
  end if;
end process;

medium

A. bit_count is not reset, causing TRANSFER to never end

B. Missing default case in state machine

C. start signal is not checked in TRANSFER state

D. State transitions are missing LOAD to IDLE path

Solution

1. Step 1: Check state transitions and counters

   TRANSFER state depends on bit_count reaching 8 to return to IDLE.

2. Step 2: Identify missing reset of bit_count

   If bit_count is never reset to 0, it may never reach 8, so TRANSFER state loops indefinitely.

3. Final Answer:

   bit_count is not reset, causing TRANSFER to never end -> Option A

4. Quick Check:

   bit_count reset missing = infinite TRANSFER [OK]

Hint: Always reset counters to avoid infinite states [OK]

Common Mistakes:

• Ignoring counter reset logic
• Expecting default case is mandatory
• Confusing start signal usage

5. You want to extend an SPI master controller to support variable data widths (4 to 16 bits). Which VHDL approach best handles this requirement?

hard

A. Use a generic parameter for data width and adjust shift register size accordingly

B. Hardcode shift register to 16 bits and ignore unused bits

C. Create separate modules for each data width and select at compile time

D. Use integer counters only without shift registers

Solution

1. Step 1: Understand variable data width needs

   Supporting 4 to 16 bits requires flexible register size and control logic.

2. Step 2: Use generics for flexibility

   Generics allow parameterizing data width at compile time, adjusting shift register size dynamically.

3. Step 3: Evaluate other options

   Hardcoding wastes resources; separate modules increase complexity; counters alone can't shift data.

4. Final Answer:

   Use a generic parameter for data width and adjust shift register size accordingly -> Option A

5. Quick Check:

   Generics enable flexible data width in VHDL [OK]

Hint: Use generics to set data width flexibly [OK]

Common Mistakes:

• Hardcoding fixed sizes wastes resources
• Creating many modules complicates design
• Ignoring shift register role in data transfer