VLSI Interview Questions and Answers – Part 4

A Mealy FSM’s output depends on both the current state and the current inputs. We need states to represent the amount of money deposited so far.

• States: S_0 (0c), S_5 (5c), S_10 (10c)
• Inputs: `in_nickel`, `in_dime`
• Outputs: `dispense_pencil`, `return_change`

module vending_machine (
    input  logic clk, reset,
    input  logic in_nickel, in_dime,
    output logic dispense_pencil, return_change
);
    typedef enum logic [1:0] { S_0, S_5, S_10 } state_t;
    state_t current_state, next_state;

    // State Register
    always_ff @(posedge clk or posedge reset) begin
        if (reset) current_state <= S_0;
        else       current_state <= next_state;
    end

    // Next State and Output Logic
    always_comb begin
        // Default outputs
        dispense_pencil = 1'b0;
        return_change = 1'b0;
        next_state = current_state; // Hold state by default

        case (current_state)
            S_0: begin
                if (in_nickel) next_state = S_5;
                else if (in_dime)   next_state = S_10;
            end
            S_5: begin
                if (in_nickel) next_state = S_10;
                else if (in_dime) begin
                    next_state = S_0;
                    dispense_pencil = 1'b1;
                end
            end
            S_10: begin
                if (in_nickel) begin
                    next_state = S_0;
                    dispense_pencil = 1'b1;
                end
                else if (in_dime) begin
                    next_state = S_0;
                    dispense_pencil = 1'b1;
                    return_change = 1'b1; // 10c + 10c = 20c. Return 5c.
                end
            end
        endcase
    end
endmodule
            

We can use a state machine that saturates. Let's define three states: `EQUAL`, `MORE_01`, and `MORE_10`. This approach uses a fixed number of states and is a more literal interpretation of an FSM solution.

module transition_fsm (
    input  logic clk, reset,
    input  logic data_in,
    output logic more_01_trans,
    output logic more_10_trans
);
    typedef enum {EQUAL, MORE_01, MORE_10} state_t;
    state_t current_state, next_state;
    logic data_prev;

    // Detect transitions
    wire is_01_trans = (data_prev == 1'b0) && (data_in == 1'b1);
    wire is_10_trans = (data_prev == 1'b1) && (data_in == 1'b0);

    // State register and previous data register
    always_ff @(posedge clk or posedge reset) begin
        if (reset) begin
            current_state <= EQUAL;
            data_prev <= 1'b0;
        end else begin
            current_state <= next_state;
            data_prev <= data_in;
        end
    end

    // Next state logic
    always_comb begin
        next_state = current_state;
        case (current_state)
            EQUAL: begin
                if (is_01_trans) next_state = MORE_01;
                else if (is_10_trans) next_state = MORE_10;
            end
            MORE_01: begin
                if (is_10_trans) next_state = EQUAL;
            end
            MORE_10: begin
                if (is_01_trans) next_state = EQUAL;
            end
        endcase
    end

    // Output logic
    assign more_01_trans = (current_state == MORE_01);
    assign more_10_trans = (current_state == MORE_10);
endmodule
            

This is a classic FSM problem. We can determine if a number is divisible by 5 by tracking the remainder after division by 5. Let the number seen so far be `N`. When a new bit `b` arrives, the new number is `2*N + b`.

The new remainder is `(2*N + b) mod 5`. We can design states based on the current remainder (`N mod 5`). The output is high only when a transition leads to state S0 (remainder 0).

This requires a combination of a priority encoder and a state machine to iterate through the bits.

1. When `in_vld` is asserted, latch the `Data_in` into an internal register, let's call it `data_reg`.
2. In each subsequent cycle, feed `data_reg` into a priority encoder to find the index of the lowest-set bit.
3. Output this index and assert `out_vld`.
4. To find the *next* set bit in the next cycle, clear the bit that was just found from `data_reg`. A common trick for this is `data_reg <= data_reg & (data_reg - 1)`. This clears the LSB '1'.
5. Repeat until `data_reg` becomes zero, at which point `out_vld` is de-asserted.

module serial_index_reporter (
    input  logic clk, reset,
    input  logic in_vld,
    input  logic [7:0] data_in,
    output logic out_vld,
    output logic [2:0] index
);
    logic [7:0] data_reg;

    always_ff @(posedge clk or posedge reset) begin
        if (reset) begin
            data_reg <= 8'b0;
        end else if (in_vld) begin
            data_reg <= data_in; // Latch new data
        end else if (out_vld) begin
            // Clear the LSB '1' to find the next one
            data_reg <= data_reg & (data_reg - 1);
        end
    end

    // Combinational logic for output
    assign out_vld = (data_reg != 8'b0);
    // Use a priority encoder to find the index of the LSB '1'
    assign index = $clog2(data_reg & -data_reg);

endmodule
            

A positive integer is a power of 2 if and only if its binary representation has exactly one bit set to '1'. There are two common ways to detect this:

Method 1: Population Count (Popcount)

Count the number of set bits in the vector. If the count is exactly 1, the number is a power of 2. This can be done with a tree of adders but is often less efficient.

Method 2: Bitwise Trick (More Efficient)

If a number `n` is a power of 2, then `n - 1` will have all the lower bits set to '1'. Therefore, for any power of 2, the bitwise AND of `n` and `n-1` will be zero. We must also handle the case of `n=0`, which is not a power of 2.

Logic Equation: is_power_of_2 = (n != 0) && ((n & (n-1)) == 0)

module power_of_2_detector (
    input  logic [7:0] n,
    output logic       is_power_of_2
);
    assign is_power_of_2 = (n != 8'b0) && ((n & (n - 1)) == 8'b0);
endmodule
            

The most direct way to implement this in hardware is with a tree of adders. For an N-bit vector, this will produce a `log2(N)`-bit sum.

Example for a 7-bit vector using full adders:

1. Layer 1: Group the 7 bits into two groups of 3 and one leftover. Use two 3-input full adders. Each full adder takes 3 bits and produces a 2-bit sum (Sum, Carry).
2. Layer 2: Add the results from Layer 1. This will involve adding the two 2-bit sums and the single leftover bit from the input. This can be done with more adders.
3. The final result will be the total count.

In Verilog, you can simply use the `+` operator in a loop, and the synthesis tool will create an efficient adder tree.

module pop_counter #(parameter WIDTH = 7) (
    input [WIDTH-1:0] data_in,
    output [$clog2(WIDTH):0] count
);
    always_comb begin
        count = '0;
        for (int i = 0; i < WIDTH; i++) begin
            count = count + data_in[i];
        end
    end
endmodule
            

This is a classic problem that can be solved elegantly using the properties of the XOR gate.

The key properties of XOR are:

• Self-inversing: `A ^ A = 0` (Any number XORed with itself is zero).
• Identity property: `A ^ 0 = A` (Any number XORed with zero is itself).
• Commutative & Associative: The order of operations doesn't matter.

Solution: If you XOR all the numbers in the array together, every number that appears twice will cancel itself out (`A ^ A = 0`). The final result of the cumulative XOR operation will be the one number that appeared only once, as it will be XORed with a final result of 0.

Hardware Implementation:

The circuit needs to iterate through the array and accumulate the XOR result.

1. A register (xor_accumulator), initialized to 0.
2. A counter to read each address of the memory/array.
3. An XOR gate whose inputs are the current value from the array and the current value of `xor_accumulator`. The output feeds back into the accumulator on the next clock cycle.

The algorithm for two's complement is: starting from the LSB, copy all bits up to and including the first '1'. After that, invert all subsequent bits.

This can be modeled with a simple two-state Mealy FSM:

• S0 (Copy State): The initial state. In this state, we have not yet seen a '1'. The output is the same as the input. If the input is 0, we stay in S0. If the input is 1, we also output 1 but transition to S1.
• S1 (Invert State): We have already seen the first '1'. In this state, we invert every subsequent input bit. We remain in S1 for all future inputs.

This problem further explores how assignment type (blocking/non-blocking) and statement order affect synthesis.

Module A (Blocking, Forward Order): q1=d; q2=q1; q=q2;

This will synthesize to a single flop where `q = d`. The assignments execute sequentially in the same timestep, so the value of `d` propagates instantly through `q1` and `q2` to `q`. The intermediate variables are optimized away. Result: One Flop.

Module B (Blocking, Reverse Order): q=q2; q2=q1; q1=d;

This is a classic example of a race condition and incorrect usage. `q` gets the old value of `q2`. Then `q2` gets the old value of `q1`. Finally, `q1` gets `d`. The logic does not form a clean shift register. Synthesis tools may produce unpredictable results or a single flop with complex feedback, but it will not be a three-stage shifter. This coding style should always be avoided for sequential logic. Result: Incorrect Logic.

Module C & D (Non-Blocking, Any Order):

q1<=d; q2<=q1; q<=q2; and q<=q2; q2<=q1; q1<=d;

For non-blocking assignments, the order of statements within the `always` block does not matter. In both cases, all right-hand sides are evaluated first using the values from before the clock edge. Then, all left-hand sides are updated simultaneously. Both modules correctly describe the behavior where `q1` gets `d`, `q2` gets the old `q1`, and `q` gets the old `q2`. Result: Both synthesize to a three-stage shift register. This demonstrates why non-blocking assignments are the standard for modeling sequential logic.

Neither is universally "better"; the choice depends entirely on the design requirements. Both have distinct advantages and disadvantages.

Conclusion: Use asynchronous resets for global, power-on reset conditions. Use synchronous resets for most internal logic to ensure robust, glitch-free, and predictable behavior.