Concatenation and replication in Verilog - Time & Space Complexity

Time Complexity: Concatenation and replication

O(n)

Understanding Time Complexity

We want to see how the time to run Verilog code changes when using concatenation and replication.

How does the number of operations grow as we increase the size of the data being combined?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module concat_replication(input [3:0] a, input [3:0] b, output reg [15:0] out);
  always @(*) begin
    out = {4{a}};       // replicate 'a' 4 times
    out = {a, b, a, b}; // concatenate 'a' and 'b' twice
  end
endmodule
    

This code replicates a 4-bit input 4 times and concatenates two 4-bit inputs multiple times to form a 16-bit output.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Replication repeats the input bits multiple times; concatenation joins multiple inputs side by side.
• How many times: Replication repeats 4 times; concatenation combines 4 parts once.

How Execution Grows With Input

As the input size grows, the number of bits to replicate or concatenate grows too.

Input Size (bits)	Approx. Operations
4	4 (replications) x 4 bits = 16 bit operations
8	4 x 8 = 32 bit operations
16	4 x 16 = 64 bit operations

Pattern observation: The operations grow linearly with the input size multiplied by the replication count.

Final Time Complexity

Time Complexity: O(n)

This means the time to replicate or concatenate grows directly in proportion to the input size.

Common Mistake

[X] Wrong: "Concatenation or replication happens instantly, no matter the input size."

[OK] Correct: Each bit must be copied or joined, so larger inputs take more steps, not zero time.

Interview Connect

Understanding how data size affects operations like concatenation helps you reason about hardware design efficiency and timing.

Self-Check

"What if we increased the replication count from 4 to n? How would the time complexity change?"

Practice

1. What does the Verilog expression {4{1'b0}} produce?

easy

A. A 4-bit vector with all bits set to 0

B. A 1-bit vector with value 4

C. A syntax error due to incorrect replication

D. A 4-bit vector with all bits set to 1

Solution

1. Step 1: Understand replication syntax

   The expression {4{1'b0}} means repeat the bit 0 four times.

2. Step 2: Construct the resulting vector

   Repeating 1'b0 four times creates a 4-bit vector: 0000.

3. Final Answer:

   A 4-bit vector with all bits set to 0 -> Option A

4. Quick Check:

   Replication repeats bits = 0000 [OK]

Hint: Replication repeats bits exactly as many times as the number [OK]

Common Mistakes:

• Confusing replication with concatenation
• Thinking it produces a single bit with value equal to the number
• Assuming it creates all ones instead of zeros

2. Which of the following is the correct syntax to concatenate a 3-bit vector a and a 2-bit vector b in Verilog?

easy

A. [a, b]

B. (a + b)

C. {a, b}

D. {a + b}

Solution

1. Step 1: Recall concatenation syntax

   Concatenation in Verilog uses curly braces with commas between signals.

2. Step 2: Identify correct syntax

   The correct way to join vectors a and b side by side is {a, b}.

3. Final Answer:

   {a, b} -> Option C

4. Quick Check:

   Concatenation uses braces and commas = {a, b} [OK]

Hint: Use curly braces with commas for concatenation [OK]

Common Mistakes:

• Using parentheses instead of braces
• Using plus sign inside braces incorrectly
• Using square brackets which are invalid here

3. What is the 8-bit value of the following Verilog expression?
{2{2'b10}, 4'b0011}

medium

A. 10101011

B. 10100011

C. 10100000

D. 10010011

Solution

1. Step 1: Evaluate the replication part

   2'b10 is 2 bits: 10. Replicated twice: 10 10.

2. Step 2: Concatenate with 4'b0011

   Concatenate 10 10 (4 bits) with 0011 (4 bits) to get 10100011.

3. Final Answer:

   10101011 -> Option A

4. Quick Check:

   Replication + concatenation = 10101011 [OK]

Hint: Replicate first, then concatenate signals [OK]

Common Mistakes:

• Miscounting bits after replication
• Concatenating in wrong order
• Confusing binary digits during replication

4. Identify the error in this Verilog code snippet:

wire [7:0] out;
assign out = {3{2'b11}, 3'b101};

medium

A. Replication count must be a variable, not a constant

B. Concatenation operands have mismatched bit widths causing size mismatch

C. Replication syntax is incorrect, missing parentheses

D. No error, code is correct

Solution

1. Step 1: Calculate bits from replication

   3{2'b11} replicates 2 bits three times = 6 bits total.

2. Step 2: Calculate bits from concatenation

   Concatenating 6 bits with 3 bits (3'b101) gives 9 bits total, but out is 8 bits wide.

3. Step 3: Identify size mismatch error

   The assigned value is 9 bits, but out expects 8 bits, causing a size mismatch error.

4. Final Answer:

   Concatenation operands have mismatched bit widths causing size mismatch -> Option B

5. Quick Check:

   Bit width mismatch in concatenation = error [OK]

Hint: Check total bits match target width in concatenation [OK]

Common Mistakes:

• Ignoring bit width mismatch warnings
• Assuming replication count must be variable
• Thinking replication syntax needs parentheses

5. You want to create a 12-bit signal sig by repeating a 3-bit pattern 3'b101 four times using the replication operator. Which Verilog expression correctly does this?

hard

A. assign sig = {4(3'b101)};

B. assign sig = {3'b101, 3'b101, 3'b101, 3'b101};

C. assign sig = {3'b101 * 4};

D. assign sig = {4{3'b101}};

Solution

1. Step 1: Understand replication for repeating patterns

   Using {4{3'b101}} repeats the 3-bit pattern four times, producing 12 bits.

2. Step 2: Compare with other options

   Manual concatenation assign sig = {3'b101, 3'b101, 3'b101, 3'b101}; repeats explicitly but doesn't use the replication operator; assign sig = {3'b101 * 4}; is invalid syntax; assign sig = {4(3'b101)}; is incorrect syntax.

3. Final Answer:

   assign sig = {4{3'b101}}; -> Option D

4. Quick Check:

   Replication repeats pattern cleanly = assign sig = {4{3'b101}}; [OK]

Hint: Use replication braces {count{pattern}} for repeated signals [OK]

Common Mistakes:

• Using multiplication instead of replication
• Writing replication without braces
• Manually concatenating repeated patterns instead of replicating