UART receiver module in Verilog - Time & Space Complexity

Time Complexity: UART receiver module

O(n)

Understanding Time Complexity

We want to understand how the time it takes for a UART receiver to process data changes as the input size changes.

Specifically, how does the number of operations grow when receiving more bits?

Scenario Under Consideration

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

module uart_rx(
  input wire clk,
  input wire rx,
  output reg [7:0] data_out,
  output reg data_ready
);
  reg [3:0] bit_count = 0;
  reg [7:0] shift_reg = 0;

  always @(posedge clk) begin
    if (bit_count < 8) begin
      shift_reg <= {shift_reg[6:0], rx};
      bit_count <= bit_count + 1;
    end else begin
      data_out <= shift_reg;
      data_ready <= 1;
      bit_count <= 0;
    end
  end
endmodule

This code receives 8 bits serially, shifting them into a register, then signals data ready.

Identify Repeating Operations

Look for repeated actions in the code.

• Primary operation: Shifting in one bit per clock cycle inside the always block.
• How many times: Exactly 8 times for each byte received.

How Execution Grows With Input

Each byte requires 8 clock cycles to receive all bits.

Input Size (bytes)	Approx. Operations (bit shifts)
1	8
10	80
100	800

Pattern observation: The operations grow linearly with the number of bytes received.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The UART receiver processes all bits instantly in one clock cycle."

[OK] Correct: The receiver must handle each bit one at a time, so it takes multiple cycles proportional to bits.

Interview Connect

Understanding how hardware modules like UART receivers scale with input size helps you reason about real embedded system performance.

Self-Check

"What if the UART receiver was designed to receive 16 bits instead of 8? How would the time complexity change?"

Practice

1. What is the primary role of a UART receiver module in digital communication?

easy

A. To read serial bits and convert them into bytes

B. To generate clock signals for data transmission

C. To encode parallel data into serial format

D. To amplify the input signal strength

Solution

1. Step 1: Understand UART receiver function

   A UART receiver reads incoming serial bits one by one.

2. Step 2: Conversion to bytes

   It collects these bits and converts them into a byte for further processing.

3. Final Answer:

   To read serial bits and convert them into bytes -> Option A

4. Quick Check:

   UART receiver = serial bits to bytes [OK]

Hint: Remember UART receiver converts serial bits to bytes [OK]

Common Mistakes:

• Confusing receiver with transmitter
• Thinking it generates clock signals
• Assuming it amplifies signals

2. Which of the following is the correct Verilog syntax to declare a 8-bit output register named data_out in a UART receiver module?

easy

A. output reg [7:0] data_out;

B. reg output [7:0] data_out;

C. output [7:0] reg data_out;

D. reg [7:0] output data_out;

Solution

1. Step 1: Identify correct order for output register declaration

   In Verilog, the correct order is 'output reg [width] name;'.

2. Step 2: Check each option

   Only output reg [7:0] data_out; follows this syntax correctly.

3. Final Answer:

   output reg [7:0] data_out; -> Option A

4. Quick Check:

   output reg declaration syntax = output reg [7:0] data_out; [OK]

Hint: Use 'output reg [width] name;' for output registers [OK]

Common Mistakes:

• Placing 'reg' after 'output'
• Swapping 'output' and 'reg' keywords
• Omitting bit width

3. Given the following Verilog snippet inside a UART receiver module:

always @(posedge clk) begin
  if (start_bit_detected) begin
    bit_count <= 0;
    data_reg <= 0;
  end else if (bit_sample_enable) begin
    data_reg <= {serial_in, data_reg[7:1]};
    bit_count <= bit_count + 1;
  end
end

What will be the value of data_reg after 3 samples if serial_in was 1, 0, then 1 in consecutive samples?

medium

A. 00000101 (binary)

B. 10100000 (binary)

C. 00000011 (binary)

D. 11100000 (binary)

Solution

1. Step 1: Understand bit shifting in data_reg

   Each sample shifts data_reg right by 1 and inserts serial_in at MSB.

2. Step 2: Calculate data_reg after each sample

   Initial data_reg=00000000
   Sample 1 (serial_in=1): data_reg=10000000
   Sample 2 (serial_in=0): data_reg=01000000
   Sample 3 (serial_in=1): data_reg=10100000
   Thus, after 3 samples, data_reg = 10100000 (binary)

3. Final Answer:

   10100000 (binary) -> Option B

4. Quick Check:

   Shift right + insert serial_in MSB = 10100000 [OK]

Hint: Track bit shifts and insertions stepwise [OK]

Common Mistakes:

• Confusing MSB and LSB positions
• Assuming left shift instead of right
• Ignoring initial zero value

4. In a UART receiver module, the following code snippet causes the received data to be incorrect:

always @(posedge clk) begin
  if (start_bit_detected) begin
    bit_count <= 0;
    data_reg <= 0;
  end else if (bit_sample_enable) begin
    data_reg <= {data_reg[6:0], serial_in};
    bit_count <= bit_count + 1;
  end
end

What is the likely error in this code?

medium

A. bit_count is not incremented correctly

B. The start bit is not being detected properly

C. Bits are shifted left instead of right, causing wrong bit order

D. serial_in is not sampled at the correct clock edge

Solution

1. Step 1: Analyze bit shifting direction

   The code shifts data_reg left by 1 bit and inserts serial_in at LSB.

2. Step 2: Understand UART bit order

   UART typically receives LSB first, so bits should be shifted right with serial_in at MSB to maintain correct order.

3. Final Answer:

   Bits are shifted left instead of right, causing wrong bit order -> Option C

4. Quick Check:

   Incorrect shift direction = Bits are shifted left instead of right, causing wrong bit order [OK]

Hint: UART bits usually shift right; check shift direction [OK]

Common Mistakes:

• Mixing up left and right shifts
• Ignoring bit order in UART protocol
• Assuming start bit detection error

5. You want to design a UART receiver module that sets a data_ready flag only after receiving all 8 data bits and the stop bit. Which approach correctly implements this behavior?

hard

A. Set data_ready when bit_count == 8 (only data bits)

B. Set data_ready immediately after detecting the start bit

C. Set data_ready after receiving 7 data bits only

D. Set data_ready when bit_count == 9 (8 data bits + 1 stop bit)

Solution

1. Step 1: Understand UART frame structure

   A UART frame has 1 start bit, 8 data bits, and 1 stop bit.

2. Step 2: Determine when data is fully received

   Data is ready only after all 8 data bits and the stop bit are received, so bit_count should reach 9.

3. Final Answer:

   Set data_ready when bit_count == 9 (8 data bits + 1 stop bit) -> Option D

4. Quick Check:

   Data ready after 9 bits = Set data_ready when bit_count == 9 (8 data bits + 1 stop bit) [OK]

Hint: Wait for all bits including stop bit before setting data_ready [OK]

Common Mistakes:

• Setting data_ready too early
• Ignoring stop bit in count
• Confusing start bit with data bits