SPI controller implementation in Verilog - Time & Space Complexity

Time Complexity: SPI controller implementation

O(n)

Understanding Time Complexity

We want to understand how the time it takes for an SPI controller to run grows as the amount of data changes.

How does the controller's work increase when we send more bits?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module spi_controller(
  input clk,
  input rst,
  input start,
  input [7:0] data_in,
  output reg mosi,
  output reg sclk,
  output reg done
);
  reg [3:0] bit_cnt;
  reg [7:0] shift_reg;

  always @(posedge clk or posedge rst) begin
    if (rst) begin
      bit_cnt <= 0;
      done <= 0;
      sclk <= 0;
    end else if (start) begin
      shift_reg <= data_in;
      bit_cnt <= 8;
      done <= 0;
    end else if (bit_cnt > 0) begin
      sclk <= ~sclk;
      if (sclk) begin
        mosi <= shift_reg[7];
        shift_reg <= shift_reg << 1;
        bit_cnt <= bit_cnt - 1;
      end
      if (bit_cnt == 1) done <= 1;
    end
  end
endmodule

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sending each bit by shifting and toggling the clock.
• How many times: 8 times for 8 bits (bit_cnt counts down from 8 to 0).

How Execution Grows With Input

Each bit requires a fixed number of clock toggles and shifts to send.

Input Size (bits)	Approx. Operations
10	About 10 bit sends, each with clock toggles and shifts
100	About 100 bit sends, more clock toggles and shifts
1000	About 1000 bit sends, many clock toggles and shifts

Pattern observation: The work grows directly with the number of bits to send.

Final Time Complexity

Time Complexity: O(n)

This means the time to send data grows linearly 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 controller sends bits one after another, so more bits mean more steps and more time.

Interview Connect

Understanding how hardware controllers like SPI handle data bit by bit helps you explain timing and performance in real devices.

Self-Check

"What if we changed the data width from 8 bits to 16 bits? How would the time complexity change?"

Practice

1. What is the main role of the cs (chip select) signal in an SPI controller?

easy

A. To enable communication with the specific SPI device

B. To provide the clock signal for data transfer

C. To send data from master to slave

D. To receive data from the slave device

Solution

1. Step 1: Understand the function of cs in SPI

   The cs signal is used to select which SPI device the master wants to communicate with by enabling it.

2. Step 2: Differentiate cs from other signals

   The clock signal is sclk, data sent from master is mosi, and data received is miso. So cs is not for clock or data transfer but device selection.

3. Final Answer:

   To enable communication with the specific SPI device -> Option A

4. Quick Check:

   cs = device enable [OK]

Hint: Remember: cs selects device, sclk clocks data [OK]

Common Mistakes:

• Confusing cs with clock signal
• Thinking cs sends or receives data
• Mixing up mosi and miso signals

2. Which of the following is the correct Verilog syntax to declare a 8-bit register named shift_reg?

easy

A. reg shift_reg:8;

B. reg shift_reg[7:0];

C. wire [7:0] shift_reg;

D. reg [7:0] shift_reg;

Solution

1. Step 1: Recall Verilog register declaration syntax

   Registers are declared with reg [width-1:0] name; format. For 8 bits, it is [7:0].

2. Step 2: Check each option

   reg [7:0] shift_reg; uses correct syntax. reg shift_reg[7:0]; reverses the range and name. wire [7:0] shift_reg; uses wire, not reg. reg shift_reg:8; uses invalid colon syntax.

3. Final Answer:

   reg [7:0] shift_reg; -> Option D

4. Quick Check:

   reg [7:0] name; = correct reg declaration [OK]

Hint: Use reg [7:0] name; for 8-bit registers [OK]

Common Mistakes:

• Using wire instead of reg for storage
• Incorrect bit range syntax
• Misplacing brackets around name

3. Given this snippet of an SPI controller shift register update inside a clocked always block:

always @(posedge sclk) begin
  if (cs == 0) begin
    shift_reg <= {shift_reg[6:0], miso};
  end
end

What does this code do on each rising edge of sclk when cs is low?

medium

A. Loads miso into the MSB of shift_reg without shifting

B. Shifts shift_reg right by 1 and inserts miso at MSB

C. Shifts shift_reg left by 1 and inserts miso at LSB

D. Clears shift_reg to zero

Solution

1. Step 1: Analyze the shift operation

   The code concatenates shift_reg[6:0] (bits 6 down to 0) with miso at the right side, effectively shifting left by 1 bit and inserting miso at the least significant bit (LSB).

2. Step 2: Confirm behavior when cs is low

   The shift happens only when cs == 0, which means the device is selected and data is being received bit by bit.

3. Final Answer:

   Shifts shift_reg left by 1 and inserts miso at LSB -> Option C

4. Quick Check:

   shift_reg <= {shift_reg[6:0], miso} = left shift + miso LSB [OK]

Hint: Concatenation {a,b} puts b at LSB, shifting left [OK]

Common Mistakes:

• Thinking it shifts right instead of left
• Confusing MSB and LSB positions
• Ignoring the condition on cs signal

4. Consider this Verilog snippet for SPI clock generation:

always @(posedge clk) begin
  if (cs == 0) begin
    sclk <= ~sclk;
  end else begin
    sclk <= 0;
  end
end

What is the main problem with this code?

medium

A. It toggles sclk on every clk edge, causing sclk frequency to be half of clk only when cs is low

B. It does not reset sclk properly when cs is high

C. It causes sclk to toggle asynchronously to clk

D. It will cause a synthesis error due to missing sensitivity list

Solution

1. Step 1: Understand clock toggling logic

   The code toggles sclk on every rising edge of clk if cs is low, effectively dividing the clock frequency by 2 during active communication.

2. Step 2: Identify the problem

   This behavior is expected for SPI clock generation. The code also resets sclk to 0 when cs is high, which is correct. There is no asynchronous toggling or sensitivity list issue.

3. Final Answer:

   It toggles sclk on every clk edge, causing sclk frequency to be half of clk only when cs is low -> Option A

4. Quick Check:

   sclk toggles at half clk frequency when cs=0 [OK]

Hint: Toggling sclk halves clk frequency during cs low [OK]

Common Mistakes:

• Thinking sclk toggles asynchronously
• Expecting sclk to run continuously
• Confusing sensitivity list with always block usage

5. You want to implement an SPI controller that sends 8 bits from a register tx_data over mosi and receives 8 bits into rx_data from miso. Which approach correctly handles the bit counting and shifting in Verilog?

hard

A. Use an 8-bit counter that decrements on each sclk falling edge when cs is high, shift tx_data right to output MSB on mosi, and shift in miso into rx_data.

B. Use a 3-bit counter that increments on each sclk rising edge when cs is low, shift tx_data left to output MSB on mosi, and shift in miso into rx_data.

C. Use a 4-bit counter that increments on each clk rising edge regardless of cs, shift tx_data right to output LSB on mosi, and ignore miso.

D. Use a 3-bit counter that resets only when cs is high, shift tx_data left to output LSB on mosi, and shift in miso into rx_data.

Solution

1. Step 1: Determine counter size and control

   For 8 bits, a 3-bit counter (0 to 7) is enough. It should increment on sclk rising edge only when cs is low (active communication).

2. Step 2: Understand shifting direction and data lines

   SPI usually sends MSB first, so shifting tx_data left outputs MSB on mosi. Incoming bits from miso are shifted into rx_data.

3. Step 3: Evaluate options

   Use a 3-bit counter that increments on each sclk rising edge when cs is low, shift tx_data left to output MSB on mosi, and shift in miso into rx_data. matches correct counter size, control, and shifting direction. Use a 4-bit counter that increments on each clk rising edge regardless of cs, shift tx_data right to output LSB on mosi, and ignore miso. uses wrong counter size and ignores miso. Use an 8-bit counter that decrements on each sclk falling edge when cs is high, shift tx_data right to output MSB on mosi, and shift in miso into rx_data. uses wrong edge and counter behavior. Use a 3-bit counter that resets only when cs is high, shift tx_data left to output LSB on mosi, and shift in miso into rx_data. incorrectly outputs LSB first and counter reset logic.

4. Final Answer:

   Use a 3-bit counter that increments on each sclk rising edge when cs is low, shift tx_data left to output MSB on mosi, and shift in miso into rx_data. -> Option B

5. Quick Check:

   3-bit counter + sclk rising + MSB first shift = correct SPI send/receive [OK]

Hint: Count 8 bits with 3-bit counter, shift MSB first [OK]

Common Mistakes:

• Using wrong counter size or clock edge
• Shifting in wrong direction for MSB first
• Ignoring chip select signal during counting