Digital Design Interview Q&A
Flip-Flops, Latches, FSM Encoding, FIFOs & Verilog Fundamentals
For digital circuits, the Newton-Raphson algorithm is the most common iterative method. It converges quickly and maps well to hardware.
Algorithm:
// Initialize guess (e.g., high half of input)
// Iterate 3-4 times for 32-bit precision:
x_next = (x + (A / x)) / 2
// Final Step: Floor adjustment
if ((x * x) > A) x = x - 1;
Verilog Implementation (Simplified 32-bit):
module sqrt_newton (
input wire clk,
input wire rst_n,
input wire start,
input wire [31:0] a,
output reg [31:0] result,
output reg done
);
reg [31:0] x;
reg [31:0] a_reg;
reg [2:0] iter;
wire [31:0] a_div_x = (x != 0) ? (a_reg / x) : 32'd0;
wire [31:0] nr_step = (x + a_div_x) >> 1;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
x <= 0; a_reg <= 0; iter <= 0;
result <= 0; done <= 0;
end else begin
done <= 0;
if (start) begin
a_reg <= a;
x <= a[31:16]; // Initial guess
iter <= 0;
end else if (iter < 3) begin
x <= nr_step;
iter <= iter + 1;
end else begin
result <= (x * x > a_reg) ? (x - 1) : x;
done <= 1;
iter <= 0;
end
end
end
endmodule
- LUT: Best for small bit-widths (e.g., 8-bit input). Fast (1 cycle) but area grows exponentially.
- Digit-by-Digit: Restoring method. Similar to hand calculation. No multiplier needed, but slower (N/2 cycles).
| Feature | D-Flip-Flop | T-Flip-Flop |
|---|---|---|
| Operation | Data at D input is transferred to Q on the active clock edge. | If T=0, Q remains same. If T=1, Q toggles to complement. |
| Equation | $Q_{next} = D$ | $Q_{next} = T \oplus Q_{current}$ |
| Usage | General purpose registers, FSMs. | Counters (binary ripple counters), frequency dividers. |
- Master Latch: Active when Clock is Low (or High, depending on design). It samples the D input.
- Slave Latch: Active when Clock is High (or Low). It takes the output of the Master latch as its input.
- Inverter: Placed between them to ensure they are active at opposite times.
When the clock transitions, the Master becomes transparent, and the Slave becomes transparent, transferring the data.
FIFO depth is determined by the difference in data rates between the source (writer) and destination (reader) and the maximum burst duration.
Formula:
Depth ≥ (Ratewriter - Ratereader) × Max\_Burst\_Time
Example:
- Writer Clock: 100 MHz (1 data/cycle)
- Reader Clock: 50 MHz (1 data/cycle)
- Max Burst: 100 cycles of writer clock
Calculation:
- Time for 100 cycles @ 100MHz = 1 ns
- In 1 ns, Reader @ 50MHz reads: $50M \times 1ns = 50$ words.
- Writer writes: $100M \times 1ns = 100$ words.
- Overflow Risk = $100 - 50 = 50$ words.
- Input S sets the output High.
- Input R resets the output Low.
- When both S and R are Low (inactive), the output holds its previous state.
To make a D-Latch, add an enable input and logic to prevent S and R from being active simultaneously.
| Feature | Blocking (=) | Non-Blocking (<=) |
|---|---|---|
| Execution | Statement is executed immediately. Next statement waits. | All statements are evaluated first, then assigned at the end of the time step. |
| Usage | Combinational Logic (always @(*)) |
Sequential Logic (always @(posedge clk)) |
| Example | a = b; c = a; // c gets new b |
a <= b; c <= a; // c gets OLD b |
| Feature | Combinational | Sequential |
|---|---|---|
| Memory | No memory. Output depends only on current inputs. | Has memory (Flip-Flops/Latches). Output depends on current inputs AND previous state. |
| Clock | Asynchronous (usually not clocked directly). | Synchronous (clocked) or Asynchronous. |
| Examples | Mux, Adder, Decoder, LUT. | Counters, Registers, FSMs, RAM. |
Glitch (Hazard): A short, unwanted pulse (High or Low) at the output of combinational logic caused by different path delays through logic gates.
Why it's fatal:
- If a glitch occurs on a control signal (like Reset, Enable, or Write), it can cause the circuit to enter an unintended state.
- In asynchronous circuits, glitches can cause oscillation or race conditions.
Solutions:
- One-Hot Encoding: Reduces combinational logic complexity, reducing glitch potential.
- Proper FSM Design: Ensure valid states are one-hot or use a "safe" default state for invalid states.
- Filtering: Use a synchronizer or a short RC filter (analog) for critical control signals.
- Timing Analysis: Ensure setup/hold times are met so glitches don't propagate into Flip-Flops.
| Feature | Latch | Flip-Flop |
|---|---|---|
| Trigger | Level Sensitive (e.g., when CLK=1). | Edge Triggered (e.g., on Posedge CLK). |
| Behavior | Output follows input as long as CLK is active. Multiple changes possible in one high period. | Output changes only at the precise edge. Stable output during rest of cycle. |
| Design | Simpler, but prone to "latch transparency" issues. | More robust for synchronous design. Preferred in modern ASICs. |
| Feature | Binary Encoding | One-Hot Encoding |
|---|---|---|
| Bit Width | $\log_2(N)$ bits for N states. | N bits for N states. |
| Example (4 States) | 00, 01, 10, 11 | 0001, 0010, 0100, 1000 |
| Logic Complexity | More combinational logic for decoding states. | Simpler logic (just shift registers). Easier to route. |
| Speed | Can be slower due to complex next-state logic. | Faster for high-frequency designs. |
- High Frequency / Large FSMs: Use One-Hot. It reduces critical path length.
- Small FSMs / Area Critical: Use Binary. It uses fewer Flip-Flops.
- Glitch Resistance: One-Hot is generally more glitch-tolerant if implemented correctly.
No comments:
Post a Comment