68. Interview patterns

coreWhat do interviewers look for?

Clear thinking and hardware intuition, not only the final answer.

basicIs this a correct power-of-two test for an 8-bit x?

assign is_pow2 = ((x & (x - 8'd1)) == 8'd0);

Almost. A power of two has exactly one bit set, so subtracting 1 clears it and sets the bits below, and x & (x - 1) is zero. But for x = 0, x - 1 is all ones and 0 & anything is 0, so the test also says 0 is a power of two. Over all 256 values it says yes 9 times, while there are only 8 powers of two. Add a check that x is not zero.

basicYou are asked to detect the pattern 101 in a serial stream. The input is 1, 0, 1, 0, 1. How many matches should be reported, and what should you ask first?

It depends on whether matches may overlap. If they may, the last 1 of the first match also starts the second, so there are 2 matches. If they may not, the detector restarts after a match, and there is only 1. Both are valid designs, so ask about overlap, reset behaviour and input timing before drawing the state machine.

coreBits arrive one per clock, MSB first. This FSM keeps the remainder of the number so far divided by 3. Feed it 1, 1, 1, 1: when does div go high?

always @(posedge clk or negedge rst_n)
  if (!rst_n) r <= 2'd0;
  else case (r)
    2'd0:    r <= bit_in ? 2'd1 : 2'd0;
    2'd1:    r <= bit_in ? 2'd0 : 2'd2;
    default: r <= bit_in ? 2'd2 : 2'd1;
  endcase
assign div = (r == 2'd0);

Shifting in a bit doubles the number and adds the bit, so the new remainder is (2r + bit) mod 3, which gives the six transitions in the case. The numbers are 1, 3, 7 and 15, with remainders 1, 0, 1, 0. So div is high after the second bit (3) and after the fourth (15). The FSM needs only three states, however long the stream is.

coreA burst of 120 words is written at 250 MHz, one per cycle. The reader takes one word per cycle at 100 MHz. What is the minimum FIFO depth?

The burst lasts 120 x 4 ns = 480 ns. In that time the reader takes 480 / 10 = 48 words. So 120 - 48 = 72 words must be stored. Say that this assumes the reader starts at once and the bursts are separated enough to drain, and add margin for clock alignment and, in an async FIFO, synchronizer delay.

coreWhat hardware does this population count become, and how would you make it faster?

always @(*) begin
  n = 4'd0;
  for (i = 0; i < 8; i = i + 1)
    n = n + x[i];
end

The loop is unrolled by synthesis into a chain of eight additions, each adding one bit to the running total, so the delay grows with the number of bits. It is functionally correct for all 256 inputs. A faster version adds bits in a tree, pairs first, then pairs of pairs, so the depth grows with the log of the width. Synthesis may restructure some of this, but describing the tree makes the intent clear.

coreYou design a rising-edge detector that compares the input with last cycle's value. What assumption should you state, and what changes if it does not hold?

The detector assumes the input is synchronous to your clock. If it comes from another clock domain, it can change between edges, so the output pulse could be shorter than a cycle or the flops could go metastable. In that case, put a two-flop synchronizer in front and detect the edge on its output, which adds two cycles of latency. Saying this out loud, along with your reset assumptions, is part of the answer.

advancedDescribe a glitch-free clock multiplexer for two unrelated clocks.

Each clock gets an enable path: the select, combined with the other path's disabled state, goes through two flops clocked on the falling edge of that path's own clock, and the output gates that clock. Switching works as break-before-make: the active clock's enable drops on its own falling edge, which is fed back to the other path, and only then does the new clock's enable rise on its own falling edge. Changing enables while each clock is low means no shortened pulse can appear at the output, and the two flops per path handle the asynchronous select. A plain mux switching at an arbitrary moment can produce a runt pulse that clocks some flops and not others.

advancedA path has clock-to-Q 0.2 ns, maximum logic 3.1 ns, minimum logic 0.05 ns, setup 0.15 ns and hold 0.1 ns. The capture clock arrives 0.25 ns later than the launch clock. What is the highest clock frequency, and is hold met?

For setup, a later capture clock adds time: period >= 0.2 + 3.1 + 0.15 - 0.25 = 3.2 ns, so fmax is 1 / 3.2 ns = 312.5 MHz. For hold, the fastest data arrives at 0.2 + 0.05 = 0.25 ns, but it must not change until 0.1 + 0.25 = 0.35 ns, so hold fails by 0.1 ns. The same skew that helped setup hurt hold, and the hold failure does not depend on frequency. The fix is to add delay on the short path.