Ring counter in Verilog - Time & Space Complexity

Time Complexity: Ring counter

O(1)

Understanding Time Complexity

Let's see how the time it takes to run a ring counter changes as we increase its size.

We want to know how the number of steps grows when the ring counter gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module ring_counter(
  input clk,
  input reset,
  output reg [3:0] q
);
  always @(posedge clk or posedge reset) begin
    if (reset)
      q <= 4'b0001;
    else
      q <= {q[0], q[3:1]};
  end
endmodule

This code creates a 4-bit ring counter that shifts a single '1' around the bits on each clock pulse.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The bit shift operation that moves the '1' around the register.
• How many times: This happens once every clock cycle, repeating indefinitely.

How Execution Grows With Input

Each clock cycle, the ring counter shifts bits once, no matter how many bits it has.

Input Size (n bits)	Approx. Operations per cycle
4	1 shift operation
8	1 shift operation
16	1 shift operation

Pattern observation: The number of operations per clock cycle stays the same even if the ring counter size grows.

Final Time Complexity

Time Complexity: O(1)

This means the time to update the ring counter does not grow as the number of bits increases.

Common Mistake

[X] Wrong: "The time to shift bits grows with the number of bits in the ring counter."

[OK] Correct: In hardware, the shift happens in parallel, so it takes the same time regardless of size.

Interview Connect

Understanding how hardware operations scale helps you explain efficient designs clearly and confidently.

Self-Check

"What if the ring counter was implemented using a for-loop to shift bits sequentially? How would the time complexity change?"

Practice

1.

What is the main function of a ring counter in Verilog?

easy

A. It generates random numbers for testing.

B. It counts the number of clock pulses in binary.

C. It stores multiple bits of data simultaneously.

D. It circulates a single '1' bit through a register chain.

Solution

1. Step 1: Understand ring counter behavior

   A ring counter moves a single '1' bit around a group of bits in a loop, unlike a binary counter which counts in binary.

2. Step 2: Identify the correct function

   The main function is to circulate one '1' bit through the register chain, which matches It circulates a single '1' bit through a register chain..

3. Final Answer:

   It circulates a single '1' bit through a register chain. -> Option D

4. Quick Check:

   Ring counter = single '1' bit circulation [OK]

Hint: Ring counter moves one '1' bit around registers [OK]

Common Mistakes:

• Confusing ring counter with binary counter
• Thinking it stores multiple bits set to '1'
• Assuming it generates random values

2.

Which of the following is the correct way to declare a 4-bit ring counter register in Verilog?

?

easy

A. reg [3:0] ring_counter; // 4-bit register

B. wire [4:0] ring_counter; // 5-bit wire

C. reg ring_counter[3:0]; // 4 separate registers

D. integer ring_counter; // integer type

Solution

1. Step 1: Understand register declaration syntax

   In Verilog, a 4-bit register is declared as reg [3:0] name; where bits are indexed from 3 down to 0.

2. Step 2: Check each option

   reg [3:0] ring_counter; // 4-bit register correctly declares a 4-bit register. wire [4:0] ring_counter; // 5-bit wire uses wire and 5 bits, which is incorrect. reg ring_counter[3:0]; // 4 separate registers declares an array of 4 registers, not a 4-bit register. integer ring_counter; // integer type declares an integer, not a bit vector.

3. Final Answer:

   reg [3:0] ring_counter; // 4-bit register -> Option A

4. Quick Check:

   4-bit register = reg [3:0] [OK]

Hint: Use reg [3:0] for 4-bit registers in Verilog [OK]

Common Mistakes:

• Using wire instead of reg for storage
• Confusing array of registers with bit vector
• Using integer for bit-level operations

3.

Consider the following Verilog code snippet for a 4-bit ring counter:

module ring_counter(clk, reset, q);
  input clk, reset;
  output reg [3:0] q;
  always @(posedge clk or posedge reset) begin
    if (reset)
      q <= 4'b0001;
    else
      q <= {q[2:0], q[3]};
  end
endmodule

What will be the value of q after 3 clock cycles following a reset?

medium

A. 4'b0100

B. 4'b1000

C. 4'b0010

D. 4'b0001

Solution

1. Step 1: Analyze initial reset value

   On reset, q is set to 4'b0001.

2. Step 2: Trace the bit rotation for 3 clock cycles

   Each clock cycle shifts bits left with wrap-around:
   Cycle 1: q = {q[2:0], q[3]} = {000,1} = 4'b0010
   Cycle 2: q = {010,0} = 4'b0100
   Cycle 3: q = {100,0} = 4'b1000

3. Final Answer:

   4'b1000 -> Option B

4. Quick Check:

   Rotate left 3 times from 0001 = 1000 [OK]

Hint: Rotate bits left each clock cycle after reset [OK]

Common Mistakes:

• Confusing bit order in rotation
• Forgetting wrap-around of MSB to LSB
• Misreading reset initial value

4.

Identify the error in this Verilog ring counter code snippet:

always @(posedge clk) begin
  if (reset)
    q <= 4'b0001;
  else
    q <= {q[3], q[2:0]};
end

medium

A. The register q is not declared as reg.

B. Reset condition should be asynchronous.

C. The concatenation order is incorrect for rotating bits.

D. The clock edge sensitivity list is missing reset.

Solution

1. Step 1: Understand the intended rotation

   The code intends to rotate bits left, but concatenation order is {q[3], q[2:0]}, which places MSB first, then lower bits, effectively no rotation.

2. Step 2: Identify correct rotation syntax

   Correct rotation left should be {q[2:0], q[3]} to move MSB to LSB position.

3. Final Answer:

   The concatenation order is incorrect for rotating bits. -> Option C

4. Quick Check:

   Rotation needs {q[2:0], q[3]} not {q[3], q[2:0]} [OK]

Hint: Check bit order in concatenation for rotation [OK]

Common Mistakes:

• Swapping bit order in concatenation
• Ignoring asynchronous reset requirement
• Forgetting to declare registers properly

5.

You want to design a 5-bit ring counter that starts with 5'b00001 on reset and rotates the '1' bit right on each clock cycle. Which of the following always block implementations correctly achieves this?

?

hard

A. always @(posedge clk or posedge reset) begin
if (reset)
q <= 5'b00001;
else
q <= {q[0], q[4:1]};
end

B. always @(posedge clk or posedge reset) begin
if (reset)
q <= 5'b00001;
else
q <= {q[3:0], q[4]};
end

C. always @(posedge clk or posedge reset) begin
if (reset)
q <= 5'b10000;
else
q <= {q[0], q[4:1]};
end

D. always @(posedge clk or posedge reset) begin
if (reset)
q <= 5'b00001;
else
q <= {q[1:0], q[4:2]};
end

Solution

1. Step 1: Understand right rotation of bits

   Right rotation moves the least significant bit (LSB) to the most significant bit (MSB) position, shifting others right.

2. Step 2: Check each option's rotation logic

   always @(posedge clk or posedge reset) begin if (reset) q <= 5'b00001; else q <= {q[0], q[4:1]}; end uses {q[0], q[4:1]} which places LSB at MSB and shifts others right, correct for right rotation.
   always @(posedge clk or posedge reset) begin if (reset) q <= 5'b00001; else q <= {q[3:0], q[4]}; end rotates left, incorrect.
   always @(posedge clk or posedge reset) begin if (reset) q <= 5'b10000; else q <= {q[0], q[4:1]}; end resets to 10000, not 00001.
   always @(posedge clk or posedge reset) begin if (reset) q <= 5'b00001; else q <= {q[1:0], q[4:2]}; end mixes bits incorrectly, not a proper rotation.

3. Final Answer:

   always @(posedge clk or posedge reset) begin if (reset) q <= 5'b00001; else q <= {q[0], q[4:1]}; end -> Option A

4. Quick Check:

   Right rotate = LSB to MSB, shift others right [OK]

Hint: Right rotate: LSB moves to MSB position [OK]

Common Mistakes:

• Confusing left and right rotation
• Incorrect reset value for starting bit
• Wrong bit slicing in concatenation