T flip-flop behavior in Verilog - Time & Space Complexity

Time Complexity: T flip-flop behavior

O(n)

Understanding Time Complexity

We want to understand how the time it takes for a T flip-flop to update changes as inputs change.

How does the number of operations grow when the input toggles repeatedly?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module t_flip_flop(
  input wire clk,
  input wire t,
  output reg q
);
  always @(posedge clk) begin
    if (t) q <= ~q;
  end
endmodule

This code models a T flip-flop that toggles its output on each clock rising edge if the input t is high.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The flip-flop toggles output on every clock rising edge when t is 1.
• How many times: This happens once per clock cycle, repeating as many times as clock cycles occur.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10 clock cycles	10 toggles if t=1 each cycle
100 clock cycles	100 toggles if t=1 each cycle
1000 clock cycles	1000 toggles if t=1 each cycle

Pattern observation: The number of toggles grows linearly with the number of clock cycles when t stays high.

Final Time Complexity

Time Complexity: O(n)

This means the number of toggles grows directly in proportion to the number of clock cycles.

Common Mistake

[X] Wrong: "The flip-flop toggles multiple times within one clock cycle."

[OK] Correct: The flip-flop only changes state once per clock rising edge, so toggling happens at most once per cycle.

Interview Connect

Understanding how hardware elements like flip-flops behave over time helps you reason about timing and performance in digital designs.

Self-Check

"What if the input 't' changes randomly every clock cycle? How would the time complexity of toggling change?"

Practice

1. What happens to the output Q of a T flip-flop when the input T is 1 at the rising edge of the clock?

easy

A. The output Q toggles (changes from 0 to 1 or 1 to 0).

B. The output Q resets to 0.

C. The output Q stays the same.

D. The output Q sets to 1.

Solution

1. Step 1: Understand T flip-flop behavior

   A T flip-flop toggles its output Q when T is 1 at the clock's rising edge.

2. Step 2: Apply the toggle rule

   Since T is 1, Q changes from 0 to 1 or 1 to 0.

3. Final Answer:

   The output Q toggles (changes from 0 to 1 or 1 to 0). -> Option A

4. Quick Check:

   T=1 causes toggle = A [OK]

Hint: Remember: T=1 toggles output Q on clock edge [OK]

Common Mistakes:

• Thinking output resets when T=1
• Assuming output stays the same always
• Confusing T flip-flop with D flip-flop

2. Which of the following is the correct Verilog sensitivity list for a T flip-flop with asynchronous reset rst and clock clk?

easy

A. always @(posedge clk or posedge rst)

B. always @(negedge clk or negedge rst)

C. always @(clk or rst)

D. always @(posedge rst or negedge clk)

Solution

1. Step 1: Identify asynchronous reset and clock edge

   Asynchronous reset triggers on positive edge of rst, clock triggers on positive edge of clk.

2. Step 2: Write sensitivity list accordingly

   Sensitivity list must include posedge clk and posedge rst for asynchronous reset.

3. Final Answer:

   always @(posedge clk or posedge rst) -> Option A

4. Quick Check:

   Async reset and posedge clock = A [OK]

Hint: Async reset uses posedge or negedge in sensitivity list [OK]

Common Mistakes:

• Using level-sensitive instead of edge-sensitive triggers
• Mixing posedge and negedge incorrectly
• Omitting reset from sensitivity list

3. Given the following Verilog code for a T flip-flop, what is the value of Q after two rising edges of clk if T=1 and rst=0 initially?

module t_ff(input clk, rst, T, output reg Q);
  always @(posedge clk or posedge rst) begin
    if (rst) Q <= 0;
    else if (T) Q <= ~Q;
  end
endmodule

medium

A. Q toggles once, so final Q = ~initial Q

B. Q toggles twice, so final Q = initial Q

C. Q resets to 0 after two clocks

D. Q remains unchanged

Solution

1. Step 1: Analyze behavior on each clock edge

   At each rising edge, since T=1 and rst=0, Q toggles.

2. Step 2: Calculate after two toggles

   Two toggles mean Q changes twice, returning to its initial value.

3. Final Answer:

   Q toggles twice, so final Q = initial Q -> Option B

4. Quick Check:

   Two toggles return Q to initial = B [OK]

Hint: Even toggles return Q to start value [OK]

Common Mistakes:

• Assuming Q toggles only once after two clocks
• Forgetting reset is zero so no reset occurs
• Confusing toggle with set or reset

4. Identify the error in this Verilog T flip-flop code snippet:

always @(posedge clk or posedge rst) begin
  if (rst == 1'b1)
    Q = 0;
  else if (T == 1'b1)
    Q = ~Q;
end

medium

A. No initial value assigned to Q

B. Missing sensitivity to negedge clk

C. Using blocking assignments = instead of non-blocking <= inside always block

D. Incorrect reset condition syntax

Solution

1. Step 1: Check assignment types in sequential always block

   Sequential logic inside always @(posedge clk ...) must use non-blocking assignments <=.

2. Step 2: Identify the error

   The code uses blocking assignments =, which can cause simulation mismatches.

3. Final Answer:

   Using blocking assignments = instead of non-blocking <= inside always block -> Option C

4. Quick Check:

   Sequential logic needs non-blocking <= = D [OK]

Hint: Use <= for sequential logic inside always @(posedge clk) [OK]

Common Mistakes:

• Using blocking = instead of non-blocking <=
• Adding negedge clk unnecessarily
• Miswriting reset condition syntax

5. You want to design a frequency divider by 4 using T flip-flops in Verilog. How many T flip-flops connected in series are needed, and what should be the input T for each flip-flop to achieve this?

hard

A. 1 T flip-flop with T toggling every 4 clock cycles

B. 4 T flip-flops, each with T=0 to hold state

C. 3 T flip-flops, each with T=1 to toggle on every clock edge

D. 2 T flip-flops, each with T=1 to toggle on every clock edge

Solution

1. Step 1: Calculate number of flip-flops for divide by 4

   Divide by 4 requires 2^n = 4, so n = 2 flip-flops. A chain of 2 toggling flip-flops achieves frequency divide by 4.

2. Step 2: Consider toggle input for frequency division

   Each T flip-flop must toggle (T=1) on its clock input. The first flip-flop toggles on main clock, the next toggles on previous flip-flop output.

3. Step 3: Confirm the configuration

   2 T flip-flops chained with T=1 for each achieves divide-by-4.

4. Final Answer:

   2 T flip-flops, each with T=1 to toggle on every clock edge -> Option D

5. Quick Check:

   Divide by 4 needs 2 toggling T flip-flops = C [OK]

Hint: Divide by 2^n needs n T flip-flops toggling [OK]

Common Mistakes:

• Using wrong number of flip-flops for division
• Setting T=0 so flip-flops don't toggle
• Confusing divide by 4 with divide by 8