3
$\begingroup$

I found what I believe is a valid solution to the following assignment problem but the answer is bothering me.

Let $$H_0(z) = 1+2z^{-1}+3z^{-2}+2z^{-3}+z^{-4}\quad\textrm{and}\quad H_1(z)=H_0(-z).$$

Find causal FIR filters $F_0(z)$ and $F_1(z)$ such that $\hat{x}(n)$ agrees with $x(n)$ except for a possible delay and (nonzero) scale factor.

enter image description here

So I came up with the following causal FIR filters for $F_0(z)$ and $F_1(z)$

\begin{align} F_0(z) &= \frac{1}{4}\left(2-5z^{-1}+4z^{-2}-2z^{-3}\right) \\ F_1(z) &= \frac{1}{4}\left(2+5z^{-1}+4z^{-2}+2z^{-3}\right) \end{align}

Lets see what happens when I plug them in... First let's determine the transfer function for the system

\begin{equation} \hat{X}(z) = X(z)H_0(z)F_0(z) + X(z)H_1(z)F_1(z) \end{equation}

then

\begin{equation} \frac{\hat{X}(z)}{X(z)} = H_0(z)F_0(z) + H_1(z)F_1(z) \end{equation}

Plugging in my answer for $F_0(z)$ and $F_1(z)$ I get

\begin{equation} \frac{\hat{X}(z)}{X(z)} = 1 \end{equation}

But does this make sense? Shouldn't there always be some delay when I filter? I always thought the best I would be able to do would be linear phase distortion when all of my filters are causal. $F_0$ and $F_1$ are causal right? They are a linear combination of delayed inputs so I don't see how they wouldn't be causal. Any help pointing out where I may have made a mistake would be appreciated. Or is it reasonable to have causal FIR filters composed such that the output has zero phase distortion?

Edit: Thanks to Teague's answer I think I understand now. Also I verified using simulink that the output does indeed match the input. Here's the simulation.

enter image description here

Edit 2: From Mr. Lyons' request I'm posting the method I used to solve the problem.

Disclaimer: The problem gave a hint that I should consider polyphase representations but I couldn't figure out how to get a solution using a polyphase approach so I did it a different way. If anyone has an answer for how to solve this using polyphase I will post a new question so you can answer it.

The question asks to find FIR filters $F_0(z)$ and $F_1(z)$ so the first thing I did was assume that FIR filters existed and I thought it was reasonable to think they were no higher order than $H_0(z)$ and $H_1(z)$. I let

\begin{equation} F_k(z) = \sum_{m=0}^{4}{b_{km}z^{-m}}, \hspace{10pt} k=0,1 \end{equation}

and solve for the 10 coefficients $b_{00}, b_{01}, ... b_{04}, b_{10}, b_{11}, ..., b_{14}$

Then plugging $F_0(z)$ and $F_1(z)$ into the transfer function

\begin{align} \frac{\hat{X}(z)}{X(z)} & = H_0(z)F_0(z) + H_1(z)F_1(z) \\ & = (b_{00} + b_{10}) + (2b_{00} + b_{01} - 2b_{10} + b_{11})z^{-1} + ... + (b_{04} + b_{14})z^{-8} \end{align}

I want to find the coefficients that result in only a delay and scale. I figured there was no reason mathematically that I couldn't solve for $\hat{X}(z)/X(z)=1$. So I set up the following matrix to zero all the delays except $z^{0}$.

\begin{equation} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & -2 & 1 & 0 & 0 & 0 \\ 3 & 2 & 1 & 0 & 0 & 3 & -2 & 1 & 0 & 0 \\ 2 & 3 & 2 & 1 & 0 & -2 & 3 & -2 & 1 & 0 \\ 1 & 2 & 3 & 2 & 1 & 1 & -2 & 3 & -2 & 1 \\ 0 & 1 & 2 & 3 & 2 & 0 & 1 & -2 & 3 & -2 \\ 0 & 0 & 1 & 2 & 3 & 0 & 0 & 1 & -2 & 3 \\ 0 & 0 & 0 & 1 & 2 & 0 & 0 & 0 & 1 & -2 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} b_{00} \\ b_{01} \\ b_{02} \\ b_{03} \\ b_{04} \\ b_{10} \\ b_{11} \\ b_{12} \\ b_{13} \\ b_{14} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{bmatrix} \end{equation}

The matrix is a 9x10 rank 9, meaning it is under constrained. Because of this I can arbitrarily add a 10th equation. Because I thought it would be nice if $F_0(z) = F_1(-z)$ I added a constraint that $b_{02} = b_{12} \rightarrow b_{02} - b_{12} = 0$. Adding this to the bottom of the matrix I get

\begin{equation} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & -2 & 1 & 0 & 0 & 0 \\ 3 & 2 & 1 & 0 & 0 & 3 & -2 & 1 & 0 & 0 \\ 2 & 3 & 2 & 1 & 0 & -2 & 3 & -2 & 1 & 0 \\ 1 & 2 & 3 & 2 & 1 & 1 & -2 & 3 & -2 & 1 \\ 0 & 1 & 2 & 3 & 2 & 0 & 1 & -2 & 3 & -2 \\ 0 & 0 & 1 & 2 & 3 & 0 & 0 & 1 & -2 & 3 \\ 0 & 0 & 0 & 1 & 2 & 0 & 0 & 0 & 1 & -2 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} b_{00} \\ b_{01} \\ b_{02} \\ b_{03} \\ b_{04} \\ b_{10} \\ b_{11} \\ b_{12} \\ b_{13} \\ b_{14} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{bmatrix} \end{equation}

Which makes the matrix a 10x10 rank 10. Inverting and solving I found the solutions for $F_0(z)$ and $F_1(z)$ given above.

Interestingly the final constraint is pretty arbitrary as long is it isn't linearly dependent on the other 9 rows. I can make it pretty much anything. For example, if I want the coefficients to sum to 0 then I could make the last row of the matrix all $1$s which yields a different solution than the one I showed above, that is...

\begin{align} F_0(z) & = \frac{1}{8} (7 - 16z^{-1} + 17z^{-2} - 10z^{-3} + 3z^{-4}) \\ F_1(z) & = \frac{1}{8} (1 + 4z^{-1} - 1z^{-2} - 2z^{-3} - 3z^{-4}) \end{align}

Again if anyone knows the polyphase way to do this problem I am curious. Let me know in the comments and I'll post the question.

$\endgroup$
  • $\begingroup$ A quick comment regarding the polyphase representation. The constraint you were given ( H1(z) = H0(-z) ), suggests you are designing a QMF bank. I don't know your background, but this filter bank essentially takes an input signal and separates it into two signals: a low frequency content signal, and a high frequency content signal. By doing this, each subsignal has half the bandwidth of the original inputted signal. You can thus downsample and not lose any information. This sets you up for a position to implement polyphase filtering. I would suggest posting the question for a better response. $\endgroup$ – Izzo Oct 4 '16 at 15:53
  • $\begingroup$ @Teague I posted the question at dsp.stackexchange.com/questions/34646/… $\endgroup$ – jodag Oct 7 '16 at 2:15
4
$\begingroup$

Your work is correct.

First just think about how causal digital filters produce an output as a function of the current and previous inputs. Right?

Now think about the case where a 'filter' only produces an output as a function of the current input (i.e. not influenced by the previous inputs). We don't typically classify these as filters, instead we generally call these 'gain blocks'.

That's essentially what you've created. Your individual transfer functions are causal, and individually their outputs depend on the current and previous outputs. However when combined, they act as a single gain block with a gain of 1.

I understand where you're coming from though where you think there should be some kind of delay and you are correct. In an actual digital system, it would take time to produce the output after doing the intermediate calculations (e.g. what if you had one billion gain blocks in a row? How would this happen instantaneously?).

The best way to think about this is if you were to implement it on a DSP chip. In this realm, you are working with two different clocks: the system update rate and the processor clock. Say you want to operate a digital filter at 1kHz. It is likely that your processor will be operating at a clock rate in the MHz (i.e. not at 1kHz). So what takes multiple steps within the processor (i.e. takes multiple clock ticks) appears to happen instantaneously with regard to the 1kHz filter update rate.

Make sense?

$\endgroup$
  • $\begingroup$ Thank you that makes sense now. So basically it's no longer a filter but a unity gain block! $\endgroup$ – jodag Oct 3 '16 at 0:48
3
$\begingroup$

@jodag, you have not implemented any kind of filter. You implemented a top-path system in parallel with a bottom-path system. In the diagram below the impulse response of the top-path is shown with blue dots. The impulse response of the bottom-path is shown with red asterisks.

enter image description here

The combined parallel system's impulse response is the sum of the impulse responses of the two paths, which in your case is a single unity-valued sample at time index n = 0. As Teague said, you've implemented a single gain block with a gain of 1. Your parallel system has no input/output time delay. By the way, how did you determine $F_0(z)$ based on $H_0(z)$? Thanks.

$\endgroup$
  • $\begingroup$ Thanks for the answer, looking at the impulse response plot this makes a lot of sense. BTW I added the derivation of $F_0(z)$ and $F_1(z)$ to my question. It's probably an over complicated approach but it worked for me :) $\endgroup$ – jodag Oct 3 '16 at 22:58
  • $\begingroup$ @jodag, at the risk of having this comment of mine deleted by the Ruler's of this web site, I say "Thanks" for going to the trouble of posting your derivation. I look forward to studying it. $\endgroup$ – Richard Lyons Oct 4 '16 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.