UART transmitter module in Verilog - Time & Space Complexity

Time Complexity: UART transmitter module

O(n)

Understanding Time Complexity

We want to understand how the time to send data grows in a UART transmitter module.

How does the number of steps change as the data size or baud rate changes?

Scenario Under Consideration

Analyze the time complexity of the following UART transmitter code snippet.

module uart_tx(
  input wire clk,
  input wire tx_start,
  input wire [7:0] tx_data,
  output reg tx,
  output reg tx_busy
);
  reg [3:0] bit_index;
  reg [9:0] shift_reg;

  always @(posedge clk) begin
    if (tx_start & ~tx_busy) begin
      shift_reg <= {1'b1, tx_data, 1'b0};
      bit_index <= 0;
      tx_busy <= 1;
    end else if (tx_busy) begin
      tx <= shift_reg[0];
      shift_reg <= shift_reg >> 1;
      bit_index <= bit_index + 1;
      if (bit_index == 9) tx_busy <= 0;
    end
  end
endmodule

This code sends 8 data bits plus start and stop bits serially, one bit per clock cycle.

Identify Repeating Operations

Look for repeated actions in the code.

• Primary operation: Sending each bit one by one in a shift register.
• How many times: 10 times per data byte (1 start bit + 8 data bits + 1 stop bit).

How Execution Grows With Input

The time to send one byte is fixed at 10 bits, so it does not grow with data size.

Input Size (bytes)	Approx. Operations (bit sends)
1	10
10	100
100	1000

Pattern observation: The total steps grow linearly with the number of bytes sent.

Final Time Complexity

Time Complexity: O(n)

This means the time to send data grows directly in proportion to the number of bytes.

Common Mistake

[X] Wrong: "Sending one byte takes constant time regardless of bits."

[OK] Correct: Each byte requires sending 10 bits, so time depends on bits per byte, not just the byte count.

Interview Connect

Understanding how hardware modules like UART scale with input size helps you explain timing and performance clearly in real projects.

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 purpose of a UART transmitter module in Verilog?

easy

A. To send data bit by bit with start and stop bits

B. To receive data from a serial line

C. To generate a clock signal

D. To store data in memory

Solution

1. Step 1: Understand UART transmitter function

   A UART transmitter sends data serially, one bit at a time, adding start and stop bits to frame the data.

2. Step 2: Compare options with UART role

   Only To send data bit by bit with start and stop bits describes sending data bit by bit with start and stop bits, which matches UART transmitter behavior.

3. Final Answer:

   To send data bit by bit with start and stop bits -> Option A

4. Quick Check:

   UART transmitter = sends framed serial data [OK]

Hint: UART transmitter sends framed bits serially [OK]

Common Mistakes:

• Confusing transmitter with receiver
• Thinking UART generates clock
• Assuming it stores data

2. Which of the following is the correct Verilog syntax to declare a 1-bit output named tx in a UART transmitter module?

easy

A. output [7:0] tx;

B. input wire tx;

C. output reg tx;

D. wire tx; output;

Solution

1. Step 1: Identify output declaration for 1-bit signal

   In Verilog, a 1-bit output that can change inside always blocks is declared as output reg tx;.

2. Step 2: Check other options

   input wire tx; declares input, not output. output [7:0] tx; declares 8 bits, not 1. wire tx; output; is invalid syntax.

3. Final Answer:

   output reg tx; -> Option C

4. Quick Check:

   1-bit output reg = output reg tx; [OK]

Hint: Use 'output reg' for 1-bit output driven in always block [OK]

Common Mistakes:

• Using input instead of output
• Declaring wrong bit width
• Incorrect syntax order

3. Given this simplified UART transmitter snippet, what will be the value of tx after sending the start bit?

reg tx = 1;
reg [3:0] bit_count = 0;
always @(posedge clk) begin
  if (bit_count == 0) tx <= 0; // start bit
  else tx <= 1; // stop bit or idle
  bit_count <= bit_count + 1;
end

medium

A. 0

B. 1

C. Undefined

D. Remains unchanged

Solution

1. Step 1: Analyze bit_count and tx assignment

   When bit_count is 0, tx is set to 0 (start bit).

2. Step 2: Determine tx value after start bit

   At the first clock edge, bit_count is 0, so tx becomes 0.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Start bit = 0 on tx line [OK]

Hint: Start bit always drives tx low (0) [OK]

Common Mistakes:

• Assuming tx stays 1 initially
• Confusing bit_count values
• Ignoring synchronous assignment

4. Identify the error in this UART transmitter code snippet:

always @(posedge clk) begin
  if (start) begin
    tx <= 0; // start bit
    busy <= 1;
  end else if (bit_count == 8) begin
    tx <= 1; // stop bit
    busy <= 0;
  end
  bit_count <= bit_count + 1;
end

medium

A. tx is never set to 0

B. bit_count increments even when not transmitting

C. busy signal is never set

D. Missing reset for bit_count

Solution

1. Step 1: Check bit_count increment logic

   bit_count increments every clock cycle regardless of start or transmission state.

2. Step 2: Understand impact on transmission

   This causes bit_count to increase even when not transmitting, which is incorrect behavior.

3. Final Answer:

   bit_count increments even when not transmitting -> Option B

4. Quick Check:

   bit_count should increment only during transmission [OK]

Hint: Increment counters only when transmitting [OK]

Common Mistakes:

• Incrementing counters unconditionally
• Not resetting bit_count properly
• Ignoring busy signal control

5. You want to modify a UART transmitter module to send 9 data bits instead of 8. Which changes are necessary?

• Adjust bit counter width
• Change stop bit timing
• Modify data register size
• Update start bit logic

Which combination is correct?

hard

A. Adjust bit counter width and modify data register size only

B. Update start bit logic only

C. Change stop bit timing and update start bit logic only

D. Adjust bit counter width, modify data register size, and change stop bit timing

Solution

1. Step 1: Adjust bit counter and data register

   To send 9 bits, the bit counter must count to 9 and the data register must hold 9 bits.

2. Step 2: Change stop bit timing

   Stop bit timing depends on total bits sent; sending 9 bits changes timing, so it must be updated.

3. Step 3: Evaluate start bit logic

   Start bit logic remains the same because it always signals the start of transmission.

4. Final Answer:

   Adjust bit counter width, modify data register size, and change stop bit timing -> Option D

5. Quick Check:

   9-bit data needs counter, register, and timing updates [OK]

Hint: Update counter, register size, and timing for extra bits [OK]

Common Mistakes:

• Forgetting to change counter width
• Ignoring stop bit timing
• Changing start bit logic unnecessarily