Make a correct filter meet its depth budget, and change nothing else

The 8-tap filter you start from is correct: it matches a golden model on every one of 2088 checks. It is also too slow. Yosys measures its longest path at 48 logic levels, and the budget for this project is 43. Your job is to change its structure until it fits, with the same output values, at a latency you state.

The finished block below is the reference solution: the transposed form. It needs no extra cycle of latency, which the obvious fix, a pipeline register, does.

Read the chain from left to right; a partial sum moves one register per clock and picks up one product at each adder.

• One sample, eight multipliers: the newest sample goes to every coefficient at once. Nothing waits in a delay line.

• The registers sit inside the sum: s7 holds c7 times a sample from one clock ago, s6 adds c6 times the next sample, and so on. By the time a sum reaches y it holds c0·x(t) + c1·x(t−1) + ... + c7·x(t−7), the same sum as the direct form.

• Every register-to-register path is one multiply and one add (the highlighted column), however many taps the filter has.

The spec

1. Function: y(t) = c[0]·x(t) + c[1]·x(t−1) + ... + c[7]·x(t−7), exact, with no rounding or saturation. 19 bits hold the widest sum: 8 × (−128 × −128) = 131072. Width growth shows how that width is found.

2. Latency: the number of rising edges from the edge that takes x(t) to the edge that shows y(t). The starting RTL has latency 1. A solution may change it, but must state it.

3. Reset clears every register, so the first outputs are those of an all-zero history.

4. Coefficients change only under reset.

5. Depth: the longest path, measured with the command below, is at most 43 levels.

The budget uses the assumption of the depth story: 0.05 ns per generic level, including wire (an assumption for this exercise, not a library figure), 0.4 ns clock-to-Q and 0.2 ns setup. A 2.75 ns clock leaves 2.15 ns, which is 43 levels.

Before you start

• Cutting logic depth: a timing-closure story: how ltp -noff measures depth, and why restructuring comes before registers.

• RTL patterns for timing: restructurings that cost no latency.

• Pipelined MAC: multiply-accumulate stages and their latency.

• Width growth: sizing products and sums so nothing overflows.

The starting point

The direct form keeps the last eight samples in a delay line and sums all eight products in one cycle. The whole module is in the Testbench listing; its heart is one loop:

1
2
3
4
5

// snippet: the sum in fir_direct
always_comb begin
  acc = '0;
  for (int k = 0; k < 8; k++) acc = acc + d[k] * $signed(coef[8*k +: 8]);
end

Measured with the flow of the depth story:

$ yosys -p "read_verilog -sv fir_direct.sv; synth -flatten -noabc -top fir_direct; abc -g AND,OR,XOR,MUX; opt_clean; stat; ltp -noff"
...
  created 0 $alu and 1 $macc cells.
...
     4474 cells
...
       83   $_DFF_PN0_
...
Longest topological path in fir_direct (length=48):
    0: \coef [43]
...
   48: \acc [18] (via $abc$8636$auto$blifparse.cc:397:parse_blif$13019)
   ff: \y [18] (via $auto$ff.cc:337:slice$536)

• length=48 is five levels over the budget: −0.25 ns of slack at the assumed 0.05 ns per level.

• The path starts at \coef [43], bit 3 of c5, and ends at \y [18], the sign bit of the output: a multiply, the sum of eight products and the carry of a 19-bit add, all in one cycle.

• created 0 $alu and 1 $macc cells says Yosys has already merged all eight multiplies and seven adds into one multiply-accumulate block, built as an adder tree. The chain written in the loop is not the chain in the netlist.

That last line closes the first idea you might try. Rewriting the loop as a balanced tree of adds, as the depth story did for its compares, gives the same single block and 48 levels again. The tool already balanced the sum; what is left is the multiply and the final 19-bit add. For scale, a lone 19-bit adder between two registers measures 36 levels in this flow, so any design that finishes a full-width add in one cycle cannot go much below that.

Done when

The direct-form run is slow: ltp on its 4474-cell flat netlist takes a few minutes. The other versions finish in about a second.

Reference solution: the transposed form

The direct form moves samples through registers and sums them at the end. The transposed form moves the sums instead. Each new sample is registered once in x_q and multiplied by every coefficient; each partial sum moves one register towards y, collecting one product per step.

1
2
3
4
5
6
7
8
9

// snippet: the body of fir_transposed
for (genvar k = 0; k < 8; k++) begin : g_p
  assign p[k] = x_q * $signed(coef[8*k +: 8]);
end
...
x_q  <= x;
s[7] <= 19'(p[7]);
for (int k = 1; k < 7; k++) s[k] <= s[k+1] + 19'(p[k]);
y    <= s[1] + 19'(p[0]);

1. `x_q` registers the input, so every path starts at a flop, as in the direct form.

2. c0 sits at the output end. The newest sample must meet c0 in the same clock it reaches y, and c7 at the far end, seven registers earlier. Get this order backwards and the filter runs its coefficients in reverse (see the second check-yourself question).

3. Latency is still 1. x(t) enters x_q on edge t, and y(t) appears on edge t + 1, the same as the starting RTL. Nothing downstream has to change.

4. Every sum is 19 bits wide and sign-extended from the 16-bit product with a size cast, so no partial sum can overflow.

The same measurement:

Longest topological path in fir_transposed (length=38):
    0: \coef [33]
...
   38: $auto$maccmap.cc:240:synth$348.Y [18] (via $abc$9802$auto$blifparse.cc:397:parse_blif$13172)
   ff: \s[4] [18] (via $auto$ff.cc:337:slice$638)

The worst path is now one tap: bit 1 of c4, through its multiplier and its adder, into s[4]. Yosys built eight small multiply-accumulate blocks, one per tap, instead of one large one.

Gates are cells minus flops. The transposed form meets the budget with five levels to spare and costs 72 flops, because a 19-bit partial sum is wider than the 8-bit sample it replaces in the delay line. The pipelined tree, also in the listing, registers the eight products and then sums them in two stages. It meets the budget too, but adds two cycles of latency and 164 flops. Both sit within three levels of the 36-level floor of a single 19-bit add.

The test

The bench drives all three versions with the same samples and checks each one against a golden model written in plain integers, at that version's latency.

• Six coefficient sets: a ramp c0 = 1 to c7 = 8 (not symmetric, so the order of the taps shows); every c = −128 (the widest sum); a symmetric low-pass; and three random sets. Each set is loaded under reset.

• Per set: an impulse, a step to +127, a step to −128, alternating full-scale samples, then 300 random samples.

• The impulse is the sharpest check. With the ramp, the output after an impulse reads 1, 2, ..., 8, so a tap in the wrong place or the wrong cycle shows up as a wrong number at a known cycle.

$ iverilog -g2012 -Wall -o sim.out fir_direct.sv fir_transposed.sv fir_tree.sv tb_fir.sv
$ vvp -n sim.out
PASS: 6264 output checks over 6 coefficient sets; direct and transposed at latency 1, tree at latency 3

Common mistakes

The pipelined tree registers both halves of the sum. A tempting shortcut is to register only the half you think is critical:

1
2
3
4
5

// bad-example: the second half of the tree is not registered
assign q1 = 18'(p_q[4]) + 18'(p_q[5]) + 18'(p_q[6]) + 18'(p_q[7]);
...
q_q[0] <= 18'(p_q[0]) + 18'(p_q[1]) + 18'(p_q[2]) + 18'(p_q[3]);
y <= 19'(q_q[0]) + 19'(q1);

It synthesises to 42 levels with 229 flops: inside the budget and 18 flops cheaper than the reference tree. The bench rejects it at once:

FAIL tree: set 0 cycle 6: y=9 want 4
FAIL tree: set 0 cycle 7: y=6 want 5
FAIL tree: set 0 cycle 8: y=7 want 6
FAIL tree: set 0 cycle 9: y=8 want 7
FATAL: tb_fir.sv:57: FAIL: 1895 of 6264 checks

Taps 4 to 7 now reach y one cycle sooner than taps 0 to 3. The impulse response reads 1, 2, 3, 9, 6, 7, 8: c4 = 5 lands on top of c3 = 4, and the filter has become seven samples long. A random-only test would show a wrong value too, but not why; the impulse with distinct coefficients names the taps that moved.

Stretch goals

1. Fold symmetric coefficients. For a linear-phase filter, c[k] = c[7−k]: add x(t−k) and x(t−7+k) first (9 bits), then multiply once, so four multipliers do the work of eight. Measure levels, flops and gates against the table above, and keep an asymmetric test for the unfolded version. See Pipelined MAC.

2. Break the 36-level floor. Split each 19-bit add into a low and a high half with a registered carry between them, as step 4 of the depth story did for its accumulator, and align the halves at the output. State the new latency.

3. Check the slack yourself. Enter each version's levels × 0.05 ns as the logic delay in the slack calculator of Core equations and slack meaning with a 2.75 ns period, and confirm the slack column of the table above.

Project files

The complete listing below contains every file of this project, each starting at a // ---- file: <name> ---- line. Save each part under its name in one folder, then run the script.

run.sh

#!/bin/sh
set -e
iverilog -g2012 -Wall -o sim.out fir_direct.sv fir_transposed.sv fir_tree.sv tb_fir.sv
vvp -n sim.out
yosys -q -p "read_verilog -sv fir_direct.sv; synth -flatten -noabc -top fir_direct; abc -g AND,OR,XOR,MUX; opt_clean; stat; ltp -noff"   # optional: depth

Expected output: the line a correct design makes the simulation print at the end of its run.

PASS: 6264 output checks over 6 coefficient sets; direct and transposed at latency 1, tree at latency 3

Testbench

The three versions and the self-checking bench. Save each module in a file named after it (fir_direct.sv, fir_transposed.sv, fir_tree.sv, tb_fir.sv) to run the commands above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

// ---- file: fir_direct.sv ----
// Samples and coefficients are signed 8-bit; the output is signed 19-bit (never overflows).
module fir_direct (
  input  logic              clk, rst_n,
  input  logic signed [7:0] x,
  input  logic [8*8-1:0]    coef,          // c[k] = coef[8k +: 8], from a configuration register
  output logic signed [18:0] y
);
  logic signed [7:0] d [8];                // d[k] = x(t - k) after the edge that takes x(t)
  logic signed [18:0] acc;
  always_comb begin
    acc = '0;
    for (int k = 0; k < 8; k++) acc = acc + d[k] * $signed(coef[8*k +: 8]);
  end
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      for (int k = 0; k < 8; k++) d[k] <= '0;
      y <= '0;
    end else begin
      d[0] <= x;
      for (int k = 1; k < 8; k++) d[k] <= d[k-1];
      y <= acc;
    end
endmodule

// Transposed form: the sample goes to every multiplier at once and the partial sums move.
// ---- file: fir_transposed.sv ----
module fir_transposed (
  input  logic              clk, rst_n,
  input  logic signed [7:0] x,
  input  logic [8*8-1:0]    coef,
  output logic signed [18:0] y
);
  logic signed [7:0]  x_q;
  logic signed [18:0] s [1:7];             // s[k] holds the taps k to 7 of later outputs
  logic signed [15:0] p [8];
  for (genvar k = 0; k < 8; k++) begin : g_p
    assign p[k] = x_q * $signed(coef[8*k +: 8]);
  end
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      x_q <= '0; y <= '0;
      for (int k = 1; k < 8; k++) s[k] <= '0;
    end else begin
      x_q  <= x;
      s[7] <= 19'(p[7]);
      for (int k = 1; k < 7; k++) s[k] <= s[k+1] + 19'(p[k]);
      y    <= s[1] + 19'(p[0]);
    end
endmodule

// Pipelined tree: register the products, then a balanced adder tree with a register in the middle.
// ---- file: fir_tree.sv ----
module fir_tree (
  input  logic              clk, rst_n,
  input  logic signed [7:0] x,
  input  logic [8*8-1:0]    coef,
  output logic signed [18:0] y
);
  logic signed [7:0]  d [8];
  logic signed [15:0] p_q [8];
  logic signed [17:0] q_q [2];
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      for (int k = 0; k < 8; k++) begin d[k] <= '0; p_q[k] <= '0; end
      q_q[0] <= '0; q_q[1] <= '0; y <= '0;
    end else begin
      d[0] <= x;
      for (int k = 1; k < 8; k++) d[k] <= d[k-1];
      for (int k = 0; k < 8; k++) p_q[k] <= d[k] * $signed(coef[8*k +: 8]);
      q_q[0] <= 18'(p_q[0]) + 18'(p_q[1]) + 18'(p_q[2]) + 18'(p_q[3]);
      q_q[1] <= 18'(p_q[4]) + 18'(p_q[5]) + 18'(p_q[6]) + 18'(p_q[7]);
      y <= 19'(q_q[0]) + 19'(q_q[1]);
    end
endmodule

Related topics

• Cutting logic depth: a timing-closure story

• Pipelined MAC