# 3-point highpass filter

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)$$

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.

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

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.

• I wish you put more steps in there for Eqs. 4, 5, and 6. I think $k_2$ needs a minus sign somewhere. No? Commented Dec 24, 2023 at 19:15
• @robertbristow-johnson: good point, it looks like I made a sign error in eq(6). I'll rework it. Commented Dec 25, 2023 at 21:56
• I might be wrong. I was just looking at it. I haven't put pen to paper. Commented Dec 25, 2023 at 22:44
• @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 :-) Commented Dec 26, 2023 at 14:00
• 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. Commented Dec 26, 2023 at 16:58

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}$$

• Dan, should the x axis label be rad/samples?
– Jdip
Commented Dec 23, 2023 at 13:16
• Unfortunately, the requirements are not met here. Commented Dec 23, 2023 at 13:44
• I think one way is to use frequency sampling of the desired response. Any ideas how to do it for 3 points? Commented Dec 23, 2023 at 13:48
• How are the requirements not met here?
– Jdip
Commented Dec 23, 2023 at 14:41
• 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. Commented Dec 24, 2023 at 13:52

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}$$

\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).

• Very nice! Happy holidays Matt Commented Dec 24, 2023 at 22:39
• @DanBoschen: Thanks Dan, same to you! Commented Dec 25, 2023 at 8:40
• @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 ? Commented Dec 25, 2023 at 18:06
• @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. Commented Dec 25, 2023 at 18:23

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);


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.

• 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. Commented Dec 23, 2023 at 15:01
• 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. Commented Dec 24, 2023 at 9:43
• 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. Commented Dec 24, 2023 at 13:49
• @SamiAl-Dalahmah: As already pointed out by Dan, you forgot the negative frequencies. Hence your filter doesn't meet the requirements Commented Dec 24, 2023 at 14:17
• @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. Commented Dec 24, 2023 at 16:18