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

Time Complexity: JK flip-flop behavior

O(1)

Understanding Time Complexity

We want to understand how the time it takes for a JK flip-flop to update its output changes as we use it in a circuit.

Specifically, how does the JK flip-flop's behavior affect the number of steps needed when the input changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module jk_flip_flop(
  input wire clk,
  input wire j,
  input wire k,
  output reg q
);

  always @(posedge clk) begin
    case ({j, k})
      2'b00: q <= q;       // No change
      2'b01: q <= 0;       // Reset
      2'b10: q <= 1;       // Set
      2'b11: q <= ~q;      // Toggle
    endcase
  end
endmodule

This code models a JK flip-flop that updates its output q on the rising edge of the clock based on inputs j and k.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The flip-flop updates its output once every clock cycle.
• How many times: Exactly one update per clock rising edge, no loops or recursion inside.

How Execution Grows With Input

The JK flip-flop updates its output in a fixed number of steps each clock cycle, regardless of input size.

Input Size (n)	Approx. Operations
10	10 updates (one per clock)
100	100 updates
1000	1000 updates

Pattern observation: The number of operations grows linearly with the number of clock cycles, but each update is constant time.

Final Time Complexity

Time Complexity: O(1)

This means each JK flip-flop update takes a constant amount of time, no matter what the inputs are.

Common Mistake

[X] Wrong: "The JK flip-flop takes longer to update if inputs change a lot or if the circuit is bigger."

[OK] Correct: Each JK flip-flop update happens in a fixed step triggered by the clock edge, independent of input changes or circuit size.

Interview Connect

Understanding that hardware elements like JK flip-flops operate in fixed time steps helps you reason about timing and delays in digital circuits confidently.

Self-Check

"What if the JK flip-flop was part of a chain of flip-flops updating in sequence? How would the overall time complexity change?"

Practice

1. What is the output behavior of a JK flip-flop when both inputs J and K are 0?

easy

A. The output toggles its state.

B. The output resets to 0.

C. The output sets to 1.

D. The output holds its previous state.

Solution

1. Step 1: Understand JK flip-flop input conditions

   When both J and K are 0, the flip-flop does not change its output.

2. Step 2: Recall JK flip-flop behavior for J=0 and K=0

   The output remains the same as the previous state, meaning it holds its value.

3. Final Answer:

   The output holds its previous state. -> Option D

4. Quick Check:

   J=0, K=0 means hold state [OK]

Hint: J=0 and K=0 means no change, output holds [OK]

Common Mistakes:

• Confusing hold with reset or set
• Thinking output toggles when inputs are zero
• Assuming output always resets on zero inputs

2. Which of the following is the correct Verilog sensitivity list for a JK flip-flop triggered on the rising edge of clock clk?

easy

A. always @(posedge clk or posedge reset)

B. always @(posedge clk)

C. always @(clk)

D. always @(negedge clk)

Solution

1. Step 1: Identify clock edge triggering

   JK flip-flops are usually triggered on the rising edge of the clock signal.

2. Step 2: Choose correct sensitivity list syntax

   In Verilog, rising edge is specified by posedge clk, so always @(posedge clk) is correct.

3. Final Answer:

   always @(posedge clk) -> Option B

4. Quick Check:

   Rising edge trigger = posedge clk [OK]

Hint: posedge clk means rising edge trigger [OK]

Common Mistakes:

• Using negedge instead of posedge
• Missing edge keyword in sensitivity list
• Including unrelated signals without reason

3. Given the following Verilog code snippet for a JK flip-flop, what will be the output q after the clock rising edge if j=1, k=0, and previous q=0?

always @(posedge clk) begin
  case ({j,k})
    2'b00: q <= q;
    2'b01: q <= 0;
    2'b10: q <= 1;
    2'b11: q <= ~q;
  endcase
end

medium

A. 1

B. Toggle previous q

C. 0

D. No change

Solution

1. Step 1: Identify input combination and previous output

   Inputs are j=1, k=0, previous q=0.

2. Step 2: Match input to case statement

   For {j,k} = 2'b10, the code sets q to 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   J=1, K=0 sets q=1 [OK]

Hint: J=1 and K=0 sets output to 1 [OK]

Common Mistakes:

• Confusing toggle with set
• Ignoring previous q value
• Misreading case statement

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

always @(posedge clk) begin
  if (j == 1 && k == 1)
    q <= q;
  else if (j == 1)
    q <= 1;
  else if (k == 1)
    q <= 0;
end

medium

A. Missing sensitivity to reset signal.

B. Incorrect use of non-blocking assignment '<='.

C. The toggle condition is incorrect; it should invert q, not hold it.

D. The if-else structure is missing an else case for j=0 and k=0.

Solution

1. Step 1: Analyze toggle condition for j=1 and k=1

   The code holds q when both j and k are 1, but JK flip-flop should toggle q in this case.

2. Step 2: Verify other conditions and assignments

   Other conditions set or reset q correctly, but toggle logic is wrong.

3. Final Answer:

   The toggle condition is incorrect; it should invert q, not hold it. -> Option C

4. Quick Check:

   J=1 and K=1 toggles q, not holds [OK]

Hint: J=K=1 means toggle output, not hold [OK]

Common Mistakes:

• Assuming hold on J=K=1 instead of toggle
• Ignoring toggle logic in JK flip-flop
• Confusing blocking and non-blocking assignments

5. You want to design a JK flip-flop in Verilog that asynchronously resets q to 0 when reset is high, otherwise behaves normally on the rising edge of clk. Which code snippet correctly implements this behavior?

hard

A. always @(posedge clk or posedge reset) begin\n if (reset) q <= 0;\n else case ({j,k})\n 2'b00: q <= q;\n 2'b01: q <= 0;\n 2'b10: q <= 1;\n 2'b11: q <= ~q;\n endcase\nend

B. always @(posedge clk) begin\n if (reset) q <= 0;\n else case ({j,k})\n 2'b00: q <= q;\n 2'b01: q <= 0;\n 2'b10: q <= 1;\n 2'b11: q <= ~q;\n endcase\nend

C. always @(posedge reset or posedge clk) begin\n if (reset) q <= 1;\n else case ({j,k})\n 2'b00: q <= q;\n 2'b01: q <= 0;\n 2'b10: q <= 1;\n 2'b11: q <= ~q;\n endcase\nend

D. always @(posedge clk or negedge reset) begin\n if (!reset) q <= 0;\n else case ({j,k})\n 2'b00: q <= q;\n 2'b01: q <= 0;\n 2'b10: q <= 1;\n 2'b11: q <= ~q;\n endcase\nend

Solution

1. Step 1: Identify asynchronous reset sensitivity

   The reset is asynchronous, so it must be in the sensitivity list with posedge reset.

2. Step 2: Check reset behavior and JK logic

   When reset is high, q is set to 0 immediately. Otherwise, JK flip-flop behavior is implemented correctly with case statement.

3. Final Answer:

   Code with sensitivity list @(posedge clk or posedge reset) and reset logic first. -> Option A

4. Quick Check:

   Asynchronous reset uses posedge reset in sensitivity list [OK]

Hint: Async reset needs posedge reset in sensitivity list [OK]

Common Mistakes:

• Placing reset only inside clock edge sensitivity
• Setting q to 1 on reset instead of 0
• Using negedge reset incorrectly for active-high reset