Clock domain crossing awareness in Verilog - Time & Space Complexity

Time Complexity: Clock domain crossing awareness

O(n)

Understanding Time Complexity

When working with clock domain crossing in Verilog, it is important to understand how the timing and synchronization steps affect the overall execution time.

We want to see how the operations needed to safely transfer signals between different clocks grow as the design scales.

Scenario Under Consideration

Analyze the time complexity of the following Verilog code snippet handling clock domain crossing.

module cdc_sync (
  input wire clk_dst,
  input wire async_signal,
  output reg sync_signal
);
  reg sync_ff1, sync_ff2;

  always @(posedge clk_dst) begin
    sync_ff1 <= async_signal;
    sync_ff2 <= sync_ff1;
    sync_signal <= sync_ff2;
  end
endmodule
    

This code synchronizes an asynchronous signal into the destination clock domain using two flip-flops.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The always block triggered on each rising edge of the destination clock.
• How many times: It runs once every clock cycle of the destination clock, repeating indefinitely.

How Execution Grows With Input

Each clock cycle, the synchronization steps happen once, regardless of signal complexity.

Input Size (n)	Approx. Operations
10 cycles	10 synchronization steps
100 cycles	100 synchronization steps
1000 cycles	1000 synchronization steps

Pattern observation: The number of operations grows linearly with the number of clock cycles, but the synchronization logic itself does not grow with signal complexity.

Final Time Complexity

Time Complexity: O(n)

This means the synchronization steps happen once per clock cycle, so the total work grows linearly with time.

Common Mistake

[X] Wrong: "Adding more flip-flops in the synchronizer will increase the time complexity exponentially."

[OK] Correct: Each flip-flop adds a fixed delay per cycle, but the operations still happen sequentially once per clock cycle, so complexity grows linearly, not exponentially.

Interview Connect

Understanding how clock domain crossing synchronization scales helps you design reliable hardware and explain timing behavior clearly in real projects.

Self-Check

"What if we added a handshake protocol instead of simple flip-flop synchronization? How would the time complexity change?"

Practice

1. What is the main purpose of using a synchronizer in clock domain crossing?

easy

A. To safely transfer signals between different clock domains

B. To increase the clock frequency

C. To reduce power consumption

D. To generate a new clock signal

Solution

1. Step 1: Understand clock domain crossing

   Signals crossing from one clock domain to another can cause timing errors if not handled properly.

2. Step 2: Role of synchronizers

   Synchronizers, typically two flip-flops in series, help avoid metastability by safely transferring signals between different clock domains.

3. Final Answer:

   To safely transfer signals between different clock domains -> Option A

4. Quick Check:

   Synchronizer = Safe signal transfer [OK]

Hint: Synchronizers prevent timing errors between clocks [OK]

Common Mistakes:

• Thinking synchronizers increase clock speed
• Confusing synchronizers with power-saving methods
• Assuming synchronizers generate clocks

2. Which Verilog code snippet correctly implements a 2-flip-flop synchronizer for a single-bit signal async_signal crossing into clk domain?

easy

A. reg sync_0, sync_1; always @(posedge clk) begin sync_1 <= async_signal; sync_0 <= sync_1; end

B. reg sync_0, sync_1; always @(posedge clk) begin sync_0 <= async_signal; sync_1 <= sync_0; end

C. reg sync_0, sync_1; always @(posedge async_signal) begin sync_0 <= clk; sync_1 <= sync_0; end

D. reg sync_0, sync_1; always @(negedge clk) begin sync_0 <= async_signal; sync_1 <= sync_0; end

Solution

1. Step 1: Identify correct clock edge and signal assignment

   The synchronizer must sample the asynchronous signal on the positive edge of the destination clock (clk), so posedge clk is correct.

2. Step 2: Check flip-flop chaining order

   The first flip-flop captures async_signal, the second captures the output of the first. This is correctly done as sync_0 <= async_signal; then sync_1 <= sync_0;.

3. Final Answer:

   reg sync_0, sync_1; always @(posedge clk) begin sync_0 <= async_signal; sync_1 <= sync_0; end -> Option B

4. Quick Check:

   Correct clock edge and flip-flop order = reg sync_0, sync_1; always @(posedge clk) begin sync_0 <= async_signal; sync_1 <= sync_0; end [OK]

Hint: Use posedge clk and chain flip-flops in order [OK]

Common Mistakes:

• Using negedge instead of posedge
• Swapping flip-flop assignments
• Triggering on async_signal edge

3. Given the following Verilog code snippet crossing a signal data_in from clk_a domain to clk_b domain using a 2-flip-flop synchronizer, what is the expected output of data_sync after several clock cycles?

reg sync_0, sync_1;
always @(posedge clk_b) begin
  sync_0 <= data_in;
  sync_1 <= sync_0;
end
assign data_sync = sync_1;

medium

A. The code will cause a synthesis error

B. data_sync will always match data_in immediately

C. data_sync will never change from initial value

D. data_sync will be a delayed and synchronized version of data_in

Solution

1. Step 1: Understand synchronizer behavior

   The 2-flip-flop synchronizer delays the asynchronous input by two clock cycles of clk_b and reduces metastability risk.

2. Step 2: Analyze output data_sync

   data_sync reflects data_in but delayed and synchronized to clk_b domain, not immediate.

3. Final Answer:

   data_sync will be a delayed and synchronized version of data_in -> Option D

4. Quick Check:

   Synchronizer output = delayed synchronized signal [OK]

Hint: Synchronizer delays and syncs signals, no immediate match [OK]

Common Mistakes:

• Expecting immediate signal match
• Assuming no delay in synchronization
• Thinking code causes synthesis error

4. Identify the problem in this Verilog code crossing a multi-bit signal data_bus[7:0] from clk_a to clk_b domain:

reg [7:0] sync_0, sync_1;
always @(posedge clk_b) begin
  sync_0 <= data_bus;
  sync_1 <= sync_0;
end

medium

A. The clock edge should be negedge instead of posedge

B. The code is correct and safe for multi-bit crossing

C. Multi-bit signals require handshake or FIFO, not simple flip-flop synchronizers

D. Missing reset signals causes metastability

Solution

1. Step 1: Recognize multi-bit signal crossing issues

   Multi-bit signals crossing clock domains can cause data corruption if bits change at different times.

2. Step 2: Understand proper methods for multi-bit crossing

   Simple flip-flop synchronizers are not safe for multi-bit buses; handshake protocols or FIFOs are needed.

3. Final Answer:

   Multi-bit signals require handshake or FIFO, not simple flip-flop synchronizers -> Option C

4. Quick Check:

   Multi-bit crossing needs handshake/FIFO [OK]

Hint: Use handshake or FIFO for multi-bit signals [OK]

Common Mistakes:

• Assuming flip-flops alone are safe for buses
• Changing clock edge without reason
• Ignoring metastability risks

5. You need to transfer a 16-bit data word from clk_fast domain to clk_slow domain safely. Which method best ensures data integrity and avoids metastability?

hard

A. Use a handshake protocol with data valid and acknowledge signals

B. Directly assign the data bus without synchronization

C. Use a 2-flip-flop synchronizer on each bit individually

D. Use asynchronous reset on the data bus

Solution

1. Step 1: Consider multi-bit data crossing challenges

   Transferring 16-bit data across clock domains risks partial updates and metastability if not handled properly.

2. Step 2: Evaluate synchronization methods

   Using handshake protocols with valid and acknowledge signals ensures complete and safe data transfer between different clock domains.

3. Final Answer:

   Use a handshake protocol with data valid and acknowledge signals -> Option A

4. Quick Check:

   Handshake ensures safe multi-bit crossing [OK]

Hint: Handshake protocols ensure safe multi-bit crossing [OK]

Common Mistakes:

• Trying to synchronize each bit separately
• Ignoring synchronization and assigning directly
• Relying on asynchronous reset for crossing