# Efficient parallelized polyphase decimation FIR filter

I am struggling to derive a parallelized polyphase decimation FIR filter structure. I wonder if anyone can point me to some references?

Normally a polyphase decimation FIR filter's decimation factor (denoted $$M$$) equal to number of decomposed shorter filters (denoted $$K$$). When $$K=M$$ the solution is a typical polyphase FIR decimator. But in my case, I wish to do a efficient parallelized polyphase structure, and $$K > M$$ .

Assume you do a polyphase decomposition into $$M$$ shorter filters, because that's really the best you can do in exploiting the decimation properties of your system.

Your $$M$$ shorter filters are just that: FIR filters.

You can then go ahead and take these filters and decompose it into $$c=\left\lfloor\frac KM\right\rfloor$$ filters each.

That way, you get $$cM$$ parallelly computable filters, $$K-M < cM \le K$$, where $$cM=K$$ exactly when your $$K$$ is an integer multiple of $$M$$.

Note that I'd be rather surprised if you could get a huuuge performance boost out of this, assuming this is about computation on say a general-purpose CPU. The memory / cache bandwidth (and CPU cycles) occupied by deinterleaving or dealing with non-contiguous samples can kill performance rather quickly.

What I've seen is that people instead go and implement their $$M$$ shorter filters (which still might be massive!) as FFT-based fast convolution filters. Some FFT implementations (FFTw, specifically) allow you to multi-thread your FFT.

If you're not writing software for machines that prefer linear memory accesses, but, say, FPGA gateware, things look different. Often, significant gains come from exploiting symmetry of filter coefficients, or zero-taps in Nyquist-M filters; make sure your restructuring doesn't break these advantages!