2
$\begingroup$

I came across an interesting question from Strang & Nguyen$^\color{magenta}{\dagger}$ where it asks to design a $3$-point (or 4-point) high-pass filter with better performance than the $2$-point moving difference filter, which have the impulse response $$ h(n) = 0.5\delta(n) - 0.5\delta(n-1)$$

Please see the question below.


Invent a highpass filter $K$ with three or four taps (coefficients) that is better than the moving difference $H_1$: the goal is $$ | K (\omega) | < | H_1 (\omega) | \quad \text{ for } 0 < | \omega | < \frac{\pi}{2}$$ and $$ | H_1 (\omega) | < | K (\omega) | < 1 \quad \text{ for } \frac{\pi}{2} < | \omega| < \pi.$$


I found a 4-point solution here, however I could not find a 3-point solution. I am also interested in the methodology of finding the solution.


$\color{magenta}{\dagger}$ Gilbert Strang, Truong Nguyen, Wavelets and Filter Banks, Wellesley-Cambridge Press, Wellesley, 1997.

$\endgroup$
1
  • 1
    $\begingroup$ Interesting follow-up question could be whether there exists a 3 coefficient sparse FIR filter that meets the requirements. $\endgroup$
    – jpa
    Dec 24, 2023 at 17:31

4 Answers 4

4
$\begingroup$

Cannot be done as written, at least not with a real impulse response and the requirements as stated.

Let's call the 3 coefficients for the impulse response $[k_0,k_1,k_2]$ We assume that "3 points" implies that $k_0 \neq 0$ and $k_2 \neq 0$, otherwise it would be 2-point or 1-point solution

From the requirements it follows directly that

$$K(0) = 0 \tag{1}$$ $$K(\pi) = 1 \tag{2}$$ $$|K(\pi/2)| = \sqrt{0.5} \tag3 $$

We can derive the following equations from the z-Transform $H(\omega) = k_0 + e^{-j\omega}k_1 + e^{-2j\omega}k_2$

$$K(0) = k_0+k_1+k_2 = 0 \tag{4}$$ $$K(\pi) = k_0-k_1+k_2 = 1 \tag{5}$$ $$|K(\pi/2)| = |k_0-j\cdot k_1-k_2| = \sqrt{0.5} \tag{6}$$

From equations (4) and (5) we get $$k_0+k_2 = -k_1 \tag{7}$$ $$k_0+k_2 = 1 + k_1 \tag{8} $$

We can solve for $k_1$ as

$$k_1 = -0.5 \tag{9}$$

And from equation (1) we get

$$k_0 -.5 + k_2 = 0 \rightarrow k_2 = 0.5-k_0 \tag{10}$$

We can pop this into equation (3) $$|2\cdot k_0 - .5 -j0.5| = \sqrt{0.5}\tag{11}$$

Assuming a real impulse response, the absolute value of the imaginary part is 0.5. In order for the magnitude of the complex expression to be $\sqrt{0.5}$, the absolute value of the real part also has to be 0.5. We get

$$ 2\cdot k_0 - .5 = .5 \tag{12} $$

or $$ 2\cdot k_0 - .5 = -.5 \tag{13} $$

There are two solutions: from eq (12) we would get $k_{0,12} = 0.5$ and $k_{2,12} = 0 $. From eq (13) we get $k_{0,13} = 0$ and $k_{2,13} = 0.5$

Both solutions turn out to be "2-point" solutions: the original high pass and the original highpass delayed and phase flipped.

$\endgroup$
5
  • $\begingroup$ I wish you put more steps in there for Eqs. 4, 5, and 6. I think $k_2$ needs a minus sign somewhere. No? $\endgroup$ Dec 24, 2023 at 19:15
  • 1
    $\begingroup$ @robertbristow-johnson: good point, it looks like I made a sign error in eq(6). I'll rework it. $\endgroup$
    – Hilmar
    Dec 25, 2023 at 21:56
  • $\begingroup$ I might be wrong. I was just looking at it. I haven't put pen to paper. $\endgroup$ Dec 25, 2023 at 22:44
  • $\begingroup$ @robertbristow-johnson. You were right, I did two sign flips, that are hopefully fixed now. They more or less compensated each other, so the result is the same (and that's why I didn't see it in the first place :-) $\endgroup$
    – Hilmar
    Dec 26, 2023 at 14:00
  • $\begingroup$ The thing that clued me in was that $k_0$ and $k_2$ where always added with scaling of 1. They may as well be the same variable. $\endgroup$ Dec 26, 2023 at 16:58
2
$\begingroup$

I think Hilmar's answer is the "correct" one to select (although to clarify the requirements cannot be met with any 2 coefficients real or complex). This post is to demonstrate why the attempted solution with complex coefficients does not work when all relevant frequencies are included.

Even with complex coefficients the requirement can not be met completely: with complex coefficients the frequency range must extend from $-\pi/2$ to $+\pi/2$ since the positive and negative frequencies will no longer be related as they are with real coefficients and the requirements are specified for both positive and negative frequencies given the $|\omega|$ in the formulation.

Using the OP's answer as an example, with $z_1=20e^{-j1.25\pi}$ and $z_0=1$ we would get the following plot when we review the full spectrum, compared to the original differencer:

$$K(z) = A(1- 20e^{-j1.25\pi}z)(1-z^{-1}) = A(1 - 20e^{-j1.25\pi}z^{-1} + 20e^{-j1.25\pi}z^{-2})$$

Where the scaling $A$ is determined by setting $|K(z)|=1$ when $z = -1$.

$$H(z) = 0.5 - 0.5z^{-1}$$

magnitude response

$\endgroup$
5
  • $\begingroup$ Dan, should the x axis label be rad/samples? $\endgroup$
    – Jdip
    Dec 23, 2023 at 13:16
  • $\begingroup$ Unfortunately, the requirements are not met here. $\endgroup$ Dec 23, 2023 at 13:44
  • $\begingroup$ I think one way is to use frequency sampling of the desired response. Any ideas how to do it for 3 points? $\endgroup$ Dec 23, 2023 at 13:48
  • $\begingroup$ How are the requirements not met here? $\endgroup$
    – Jdip
    Dec 23, 2023 at 14:41
  • $\begingroup$ My prior answer did not meet the requirements (I had reversed the plot). I deleted that replacing it with the explanation above why a complex solution also won't work. $\endgroup$ Dec 24, 2023 at 13:52
2
$\begingroup$

In this answer I give an alternative proof that a filter with $3$ taps cannot outperform the solution with two taps for the given design specifications.

A solution

$$H_3(e^{j\omega})=h_0+h_1e^{-j\omega}+h_2e^{-2j\omega}\tag{1}$$

with three (real-valued) taps must satisfy the constraints at DC and at Nyquist:

$$H_3(1)=0,\qquad H_3(-1)=1\tag{2}$$

leading to the equations

\begin{align*} h_0+h_1+h_2 &= 0\\ h_0-h_1+h_2 &= 1 \tag{3} \end{align*}

These equations leave one degree of freedom for the design of the filter with three taps:

$$H_3(e^{j\omega})=\frac12-h_2-\frac12 e^{-j\omega}+h_2e^{-2j\omega}\tag{4}$$

With the frequency response of the two-tap filter

$$H_2(e^{j\omega})=\frac12\left(1-e^{-j\omega}\right)=je^{-j\omega/2}\sin\omega/2\tag{5}$$

the frequency response of the three-tap filter $(4)$ can be written as

\begin{align*} H_3(e^{j\omega}) &= H_2(e^{j\omega})-h_2\left(1-e^{-2j\omega}\right)\\ &= H_2(e^{j\omega}) - 2je^{-j\omega}h_2\sin\omega \tag{6} \end{align*}

Its squared magnitude is

\begin{align*} \big|H_3(e^{j\omega})\big|^2 &= \big|H_2(e^{j\omega})\big|^2 - 2\textrm{Re}\left\{H_2(e^{j\omega})2(-j)e^{j\omega}h_2\sin\omega\right\} + 4h_2^2\sin^2\omega \\ & = \big|H_2(e^{j\omega})\big|^2 - 4h_2\textrm{Re}\left\{e^{j\omega/2}\sin\omega\sin\omega/2\right\} + 4h_2^2\sin^2\omega \\ &= \big|H_2(e^{j\omega})\big|^2 - 4h_2\cos\omega/2\sin\omega/2\sin\omega+ 4h_2^2\sin^2\omega \\ &= \big|H_2(e^{j\omega})\big|^2 - 2h_2\sin^2\omega+ 4h_2^2\sin^2\omega \\ &= \big|H_2(e^{j\omega})\big|^2 + 2h_2(2h_2-1)\sin^2\omega\tag{7} \end{align*}

We can see from $(7)$ that the difference term on the right-hand side is either positive or negative for all $\omega$, depending on the value of $h_2$, but it cannot change sign. However, for $H_3(e^{j\omega})$ to be superior to $H_2(e^{j\omega})$, its magnitude would need to be smaller than $|H_2(e^{j\omega})|$ for $0<\omega <\pi/2$, and it would need to be greater than $|H_2(e^{j\omega})|$ for $\pi/2<\omega<\pi$. But for this to be the case, the difference term in $(7)$ would need to change sign. This shows that it is impossible for a three-tap filter to satisfy the specifications better than a two-tap filter. It takes at least four taps to improve on the two-tap solution (see this question).

$\endgroup$
4
  • $\begingroup$ Very nice! Happy holidays Matt $\endgroup$ Dec 24, 2023 at 22:39
  • $\begingroup$ @DanBoschen: Thanks Dan, same to you! $\endgroup$
    – Matt L.
    Dec 25, 2023 at 8:40
  • $\begingroup$ @MattL. Thank you for your contribution. It is a very interesting point of view. In fact, I'm glad to have such informative discussion. Is it possible to add a third constraint at $H(\pi/2)=1/\sqrt(2)$ to meet the specifications. Moreover, what about having complex coefficients and how do we solve the unsymmetrical response as Dan pointed out ? $\endgroup$ Dec 25, 2023 at 18:06
  • 1
    $\begingroup$ @SamiAl-Dalahmah: The third constraint at $\pi/2$ is what Hilmar used in his answer. One can add it but it won't change the conclusion. Complex coefficients do not make much sense either because you want to approximate a symmetric response. Also, they won't solve the problem either. There simply is no 3-tap solution (real-valued or complex-valued) that outperforms the 2-tap solution. The optimum 3-tap solution has $h_2=0$, i.e., it is equivalent to the two-tap solution. $\endgroup$
    – Matt L.
    Dec 25, 2023 at 18:23
-1
$\begingroup$

As @Dan stated, to get a 3-point filter the transfer function has the from

$$K(z) = A(z-z_0)(z-z_1)$$

In order to satisfy the requirements, we set the first zero $z_0 = 1$ and makes sure that $K(1) = 0$, i.e. a good highpass filter. As for the second zero, I tried with real values but couldn't get a performance meeting the requirements. So I turned to a complex zero (there is no room for a conjugate) hence we end up with a complex impulse response. After trying many candidates, I got the zero $z_1 = 20 e^{-j 1.25\pi}$. I got other good candidates, which I included in the code below.

enter code here
 clc
 clearvars
 %% 2 points HPF
 hn = [0.5, -0.5];
 [Hmag, omega] = freqResponse(hn);

 %% 3 points HPF
 z0 = -1;
 z1 = 20*exp(-1j*pi*1.9);
 % z1 = 0.05*exp(-1j*pi*1.25);
 % z1 = 20*exp(1j*pi*0.75);

 kn3 = conv([1 z0], [1 z1]);
 Kz3 = freqResponse(kn3);

 close all
 plot(omega/pi, Hmag)
 grid on, hold on
 plot(omega/pi, Kz3)

 xlabel('\omega/ \pi')
 ylabel('| K(\omega) |')
 legend('2 points', '3 points', 'location','northwest')

 % Helper function
 function [Hmag, omega] = freqResponse(hn)
 % Compute the frequency response magnitude over [-pi, pi].

 N = 200;
 [Hz, w] = freqz(hn,1,N,'whole');
 Hmag = abs(Hz);
 omega = w - pi;
 Hmag = [Hmag(omega>=0)' Hmag(omega<0)'];
 Hmag= Hmag/max(Hmag);

2-point & 3-point HPF response.

EDIT: As per the discussion by the community members, the above suggested filter does not meet the requirements in the negative frequency part. Still this is the closest perform ance I could get using a 3-point filter, which has complex values and as such the frequency response is not symmetric. I updated the code and the figure as well.

$\endgroup$
6
  • 2
    $\begingroup$ However that doesn't meet it either since the requirements are for $|\omega|$ and you only plotted positive $\omega$. I think Hilmar has the right answer with great methodology. It's clear that one of the zeros MUST be at z=1, so then the other zero has to be real to have a symmetric response. My plot was backwards (I was misreading which was K and which was H) so deleted my bad answer. (Do freqz with parameter whole=True to see the response for all $\omega$ in the first Nyquist zone. $\endgroup$ Dec 23, 2023 at 15:01
  • $\begingroup$ I believe it does meet the requirements, since the 3-point HPF has greater response than the 2-point HPF in $\pi/2 < \omega <\pi$ and less than it in $0 < \omega < \pi/2$, as per the requirements. @Hilmar solution reduced to a 2-point HPF, which is not what is required. It seems that the 3-point HPF must have complex coefficients. $\endgroup$ Dec 24, 2023 at 9:43
  • $\begingroup$ the requirements are for $0 < |\omega| < \pi/2$. I'll add an answer to show the plot of what the complete frequency response looks like if that isn't clear. $\endgroup$ Dec 24, 2023 at 13:49
  • $\begingroup$ @SamiAl-Dalahmah: As already pointed out by Dan, you forgot the negative frequencies. Hence your filter doesn't meet the requirements $\endgroup$
    – Matt L.
    Dec 24, 2023 at 14:17
  • 2
    $\begingroup$ @SamiAl-Dalahmah: The answer is that there exists no 3-tap filter that outperforms the given two-tap solution according to the given specs. The optimal 3-tap filter has a third tap with value zero, i.e., it's identical to the two-tap solution. $\endgroup$
    – Matt L.
    Dec 24, 2023 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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