I was learning about digital filter structures and there I came to know that parallel implementation of IIR filters speeds up the process and I understand that.But what I am not convinced of is that parallel implementation of FIR filters doesn't speed up the process. I want to know the importance of parallel structures in FIR filters.
EDIT: I understand that if I have a digital IIR filter whose transfer function is $H(z)$ then its parallel realization would be
$$H(z) = \sum_{i}{H_{i}(z)}$$
where each $H_{i}(z)$ is no more complicated than bi-quadratic. So at the most we require two delay elements for each parallel part. So if order of $H(z)$ is 10 then ignoring time required for multiplication, the minimum processing time is twice of the sampling period not ten times of that.
Now my question is what happens in case of digital FIR filters ?
-
$\begingroup$ "speed up the process": What process? $\endgroup$– Marcus MüllerCommented Jan 1, 2017 at 20:41
-
$\begingroup$ Sorry, I am talking about time of processing. $\endgroup$– No SoundCommented Jan 1, 2017 at 20:43
-
$\begingroup$ I understood that, but what is "time" of processing? Are we talking about latency in e.g. an FPGA implementation with a dedicated multiplier per tap, or throughput in a software implementation on a PC? $\endgroup$– Marcus MüllerCommented Jan 1, 2017 at 21:02
-
1$\begingroup$ hm with your edit: how is that implementation faster than a sequential implementation of the same IIR, on a sequential computer? Biquads are very popular in hardware DSP implementations, but CPUs generally work on one value at a time, so, there's no possibility for parallelism at this level; with multicore CPUs, where you could actually calculate multiple $H_i$ at once, the synchronization overhead is so significant that it simply doesn't pay to decompose $H$ into biquads – you could decompose a 20000-tap IIR into e.g. four smaller IIRs and gain from multiple cores,… $\endgroup$– Marcus MüllerCommented Jan 1, 2017 at 21:50
-
1$\begingroup$ …, so I have the slight feeling that you're confusing concepts of hardware and structural and software parallelism; I might be wrong, however! Can you refer to the source of the claim "parallel IIRs are faster on general-purpose CPUs"? $\endgroup$– Marcus MüllerCommented Jan 1, 2017 at 21:51
1 Answer
As already pointed out in the comments, it's a misunderstanding that the parallel structure of IIR filters "speeds up the process". The reason for breaking up the transfer function into second-order (and first-order) blocks is to increase numerical stability, especially for fixed-point implementations. The low-order filter sections can be arranged in a cascade structure - i.e., effectively factoring the transfer function -, or in a parallel structure, which corresponds to a partial fraction expansion of the transfer function.
Note that if we don't take quantization effects into account, the direct implementation of the total transfer function, the cascade structure, and the parallel structure give exactly the same output signal. There is no difference in delay, as you seem to believe. Even though in the direct implementation you have a longer delay line, you don't need to wait till the input signal has traveled through the delay line, because the delay line is tapped. So the first non-zero input sample can directly produce a non-zero output sample.
Let's now come to your question about FIR filters. The transfer function of a causal $N^{th}$-order FIR filter with impulse response $h[n]$, $n=0,1,\ldots,N$ is given by
$$\begin{align}H(z)&=\frac{h[0]z^N+h[1]z^{N-1}+\ldots +h[N]}{z^N}\\&=h[0]+h[1]z^{-1}+\ldots +h[N]z^{-N}\end{align}\tag{1}$$
where the second line of Eq. $(1)$ is (trivially) a partial fraction expansion. That means that the "parallel structure" of an FIR filter simply equals a direct form implementation. In other words, there is no distinct parallel structure implementation of an FIR filter.
-
$\begingroup$ Thanks @MattL ! And yes I misunderstood that the parallel structure of IIR filters "speeds up the process". Now I think that the line, "So if order of H(z) is 10 then ignoring time required for multiplication, the minimum processing time is twice of the sampling period not ten times of that", in my question is wrong. $\endgroup$– No SoundCommented Jan 3, 2017 at 16:13