UART transmitter and receiver in VHDL - Time & Space Complexity

Time Complexity: UART transmitter and receiver

O(n)

Understanding Time Complexity

We want to understand how the time it takes for a UART transmitter and receiver to work changes as the amount of data changes.

Specifically, how does the time grow when sending or receiving more bits?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

process(clk)
begin
  if rising_edge(clk) then
    if tx_start = '1' then
      if bit_count < 8 then
        tx_data_out <= tx_data_in(bit_count);
        bit_count <= bit_count + 1;
      else
        tx_busy <= '0';
      end if;
    end if;
  end if;
end process;
    

This code sends 8 bits one by one on each clock cycle when transmission starts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sending or receiving each bit in sequence.
• How many times: 8 times per byte (for 8 bits).

How Execution Grows With Input

Each byte requires sending 8 bits one after another, so time grows with the number of bytes.

Input Size (bytes)	Approx. Operations (bit sends)
10	80
100	800
1000	8000

Pattern observation: Time grows linearly with the number of bytes because each byte has a fixed number of bits to send.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

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

[OK] Correct: Each bit is sent one after another, so the total time depends on all bits, not just the byte as a whole.

Interview Connect

Understanding how UART timing scales helps you explain hardware communication delays clearly and confidently.

Self-Check

"What if we changed the bit count from 8 to 16? How would the time complexity change?"

Practice

1. What is the main role of the UART transmitter in a communication system?

easy

A. To send data bits serially with start and stop bits

B. To receive data bits and convert them to parallel form

C. To amplify the signal strength for transmission

D. To encrypt data before sending

Solution

1. Step 1: Understand UART transmitter function

   The UART transmitter converts parallel data into serial form and adds start and stop bits for synchronization.

2. Step 2: Differentiate transmitter from receiver roles

   The receiver listens and converts serial data back to parallel, so amplification or encryption is not the transmitter's main role.

3. Final Answer:

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

4. Quick Check:

   Transmitter sends serial data = A [OK]

Hint: Remember: transmitter sends serial bits with start/stop [OK]

Common Mistakes:

• Confusing transmitter with receiver
• Thinking transmitter encrypts data
• Assuming transmitter amplifies signals

2. Which of the following is the correct VHDL port declaration for a UART receiver input line named rx?

easy

A. rx : out std_logic;

B. rx : inout std_logic_vector(7 downto 0);

C. rx : in std_logic;

D. rx : buffer std_logic_vector(7 downto 0);

Solution

1. Step 1: Identify direction of UART receiver input

   The receiver reads data from the input line, so the port direction must be 'in'.

2. Step 2: Check data type for single UART line

   UART input is a single bit line, so type is std_logic, not a vector.

3. Final Answer:

   rx : in std_logic; -> Option C

4. Quick Check:

   Receiver input is 'in std_logic' = C [OK]

Hint: Input lines use 'in std_logic' for single UART signals [OK]

Common Mistakes:

• Using 'out' instead of 'in' for receiver input
• Using std_logic_vector for single bit line
• Using 'buffer' or 'inout' incorrectly

3. Given this VHDL snippet for a UART transmitter process, what is the value of tx_line after sending the start bit?

process(clk)
begin
  if rising_edge(clk) then
    if state = IDLE then
      tx_line <= '1';
    elsif state = START_BIT then
      tx_line <= '0';
    end if;
  end if;
end process;

medium

A. '1'

B. '0'

C. 'Z'

D. 'X'

Solution

1. Step 1: Analyze process behavior at START_BIT state

   When state equals START_BIT, the code sets tx_line to '0', representing the start bit.

2. Step 2: Confirm output value after start bit

   Since the start bit is '0', tx_line will be '0' during START_BIT state.

3. Final Answer:

   '0' -> Option B

4. Quick Check:

   Start bit = '0' on tx_line = B [OK]

Hint: Start bit in UART is always '0' on tx_line [OK]

Common Mistakes:

• Confusing start bit with idle line '1'
• Assuming 'Z' or 'X' values appear
• Ignoring state conditions

4. Identify the error in this UART receiver process snippet:

process(clk)
begin
  if rising_edge(clk) then
    if rx = '0' then
      data <= rx_data & rx;
    end if;
  end if;
end process;

medium

A. Missing reset condition for data register

B. Concatenation order is incorrect for data assembly

C. rx signal should be '1' to detect start bit

D. Process sensitivity list is incomplete

Solution

1. Step 1: Check process for reset handling

   The process lacks a reset condition to clear or initialize 'data', which is essential for reliable UART reception.

2. Step 2: Validate other parts

   Concatenation order and rx = '0' for start bit detection are correct; sensitivity list with clk is standard.

3. Final Answer:

   Missing reset condition for data register -> Option A

4. Quick Check:

   Reset needed to clear data = A [OK]

Hint: Always include reset in UART receiver process [OK]

Common Mistakes:

• Ignoring reset causes data corruption
• Thinking start bit is '1'
• Misunderstanding concatenation order

5. You want to design a UART transmitter in VHDL that sends 8-bit data with 1 start bit, 1 stop bit, and no parity. Which sequence correctly represents the bits sent on the tx line for data byte "10110011"?

hard

A. Start bit '0', data bits MSB first '10110011', stop bit '1'

B. Start bit '1', data bits MSB first '10110011', stop bit '0'

C. Start bit '0', data bits LSB first '11001101', stop bit '0'

D. Start bit '0', data bits LSB first '11001101', stop bit '1'

Solution

1. Step 1: Recall UART bit order and framing

   UART sends a start bit '0', then data bits least significant bit (LSB) first, then stop bit '1'.

2. Step 2: Convert data byte to LSB first sequence

   Data '10110011' MSB to LSB is bits 7 to 0. LSB first means sending '11001101'.

3. Step 3: Confirm start and stop bits

   Start bit is '0', stop bit is '1' as per UART standard.

4. Final Answer:

   Start bit '0', data bits LSB first '11001101', stop bit '1' -> Option D

5. Quick Check:

   UART sends start '0', LSB first, stop '1' = D [OK]

Hint: UART sends LSB first with start '0' and stop '1' bits [OK]

Common Mistakes:

• Sending MSB first instead of LSB first
• Using wrong stop bit value
• Confusing start bit as '1'