# Symmetric half-band FIR re-timing

I'm trying to get my head around an FPGA implementation of a half-band FIR filter. I'm trying to draw the block diagram to help with that. I've started with a 10th order example as so:

Due to the filter being a half-band, I can remove the zero taps:

The delays can then be grouped:

There is symmetry in the coefficients:

Folding the delay path to take advantage of the symmetry:

Now I want to re-time the filter to pipeline the adder chain. This is the part i'm unsure about. I've added the registers to the adder chain. Do I increase the left-to-right delay taps by 1 and decrease the right-to-left taps by 1? Or, due to removing the zero'd out taps do they have to increase and decrease by 2 (apart from around the centre tap which will increase/decrease by 1)?

Looking at an example in some course notes I have, this is what I thought would've have been the result of using the cut-set method:

You add a delay on the inbound path (left-to-right) and remove a delay from the folded delay path. This looks to be still a causal solution to me.

• I think you will have to add more detail on what exactly "retiming" and "pipelining" means in your case. I assume that the adders have some non-zero latency but I'm not sure. Commented Mar 22, 2022 at 12:06
• As this is being implemented in an FPGA, as the order of the filter gets larger, the adder chain along the bottom becomes the limiting factor as to how fast you can clock the filter. I'm trying to add pipelining to that chain by adding registers between the additions. I know you can do this using the cut-set method but i'm struggling to apply it on the folded structure i'm working with.
Commented Mar 22, 2022 at 12:50

The OP has updated the question with a possible solution and asks about causality and filter equivalence. Note first the transfer function for the intended linear phase filter with symmetric coefficients given as:

$$H(z) = w_0 + w_2z^{-2} + w_4z^{-4} + w_5z^{-5} + w_4z^{-6} +w_2z^{-8} + w_0z^{-10}$$

The third filter structure that the OP has given has a transfer function given as:

$$H(z) = w_0z^{-3} + w_2z^{-5} + w_4z^{-7} + w_5z^{-8} + w_4z^{-9} + w_2z^{-11} + w_0z^{-13}$$

Factoring out the additional 3 sample delay results in an otherwise perfect (and causal) match:

$$H(z) = z^{-3}(w_0 + w_2z^{-2} + w_4z^{-4} + w_5z^{-5} + w_4z^{-6} + w_2z^{-8} + w_0z^{-10})$$

Below are additional other suggestions for meeting timing from my earlier answer for comparison to the OP's good suggestion above.

Below is a retimed linear phase filter using a synchronous adder-tree:

An alternate approach would be to reverse the flow diagram (all branches become summing notes and summing nodes become branches, and signal flow is in reverse). This would result in a register at the output of each adder with a functionally equivalent filter and would look like the following:

Note that the first approach results in an additional delay while the second approach would be identical to the original.

• The FIR cores from AMD and Intel usually perform pre-adding to reduce the number of multipliers just like you did. And there's usually a pipelining delay of anywhere from 1 to 4 clock cycles. So your first solution is pretty close to what AMD and Intel do.
– Ben
Commented Mar 22, 2022 at 18:37
• @Ben thank you- what is your experience / opinion with the second option? I like that it doesn’t introduce additional delay (when we care) Commented Mar 22, 2022 at 18:54
• it doesn't introduce additional delay. That being said, It could be hard to meet timing closure. Remember adding pipelining delays to an FIR described by H(Z) is mathematically like multiplying H(z)*z^-N where N is the pipelining delay.
– Ben
Commented Mar 22, 2022 at 18:56
• @Ben but there are no accumulated delays— it could be 1000 taps yet it is one clock cycle per adder before it is retimed! Commented Mar 22, 2022 at 21:05
• Thanks @DanBoschen, I guess you are correct in that you do mostly have multiple clock cycles for the multiply summation in the reverse flow architecture. I'd probably avoid this approach in my FPGA designs just for keeping the timing constraints as straight forward as possible unless latency was a key factor in-which case the slightly more complicated timing constraints may be worth it.