3.9 Frequency sampling design method for fir filters

Given a desired frequency response, the frequency sampling design method designs a filter with a frequency response exactly equal to the desired response at a particular set of frequencies ${}_k$ .

or $$H_d=Wh$$ So

Important special case

What if the frequencies are equally spaced between $0$ and $2\pi$ , i.e. ${}_k=\frac{2\pi k}{M}+$

Then $$H_d({}_k)=\sum_{n=0}^{M-1} h(n)e^{-(i\frac{2\pi kn}{M})}e^{-(in)}=\sum_{n=0}^{M-1} h(n)e^{-(in)}e^{-(i\frac{2\pi kn}{M})}=\text{DFT!}$$ so $$h(n)e^{-(in)}=\frac{1}{M}\sum_{k=0}^{M-1} H_d({}_k)e^{i\frac{2\pi nk}{M}}$$ or $$h(n)=\frac{e^{in}}{M}\sum_{k=0}^{M-1} H_d({}_k)e^{i\frac{2\pi nk}{M}}=e^{in}\mathrm{IDFT}(H_d({}_k))$$

Important special case #2

$h(n)$ symmetric, linear phase, and has real coefficients. Since $h(n)=h(M-n)$ , there are only $\frac{M}{2}$ degrees of freedom, and only $\frac{M}{2}$ linear equations are required.

Removing linear phase from both sides yields $$A({}_k)=\begin{cases}2\sum_{n=0}^{\frac{M}{2}-1} h(n)\cos ({}_k(\frac{M-1}{2}-n)) & \text{if $\text{M even}$}\\ 2\sum_{n=0}^{M-\frac{3}{2}} h(n)\cos ({}_k(\frac{M-1}{2}-n))+h(\frac{M-1}{2}) & \text{if $\text{M odd}$}\end{cases}$$ Due to symmetry of response for real coefficients, only $\frac{M}{2}$ ${}_k$ on $\in \left[0 , \pi \right)$ need be specified, with the frequencies $-{}_k$ thereby being implicitly defined also. Thus we have $\frac{M}{2}$ real-valued simultaneous linear equations to solve for $h(n)$ .

Special case 2a

$h(n)$ symmetric, odd length, linear phase, real coefficients, and ${}_k$ equally spaced: $\forall k, 0\le k\le M-1\colon {}_k=\frac{n\pi k}{M}$

To yield real coefficients, $A()$ mus be symmetric $$(A()=A(-))\implies (A(k)=A(M-k))$$

Simlar equations exist for even lengths, anti-symmetric, and $=\frac{1}{2}$ filter forms.

Comments on frequency-sampled design

This method is simple conceptually and very efficient for equally spaced samples, since $h(n)$ can be computed using the IDFT.

$H()$ for a frequency sampled design goes exactly through the sample points, but it may be very far off from the desired response for $\neq {}_k$ . This is the main problem with frequency sampled design.

Possible solution to this problem: specify more frequency samples than degrees of freedom, and minimize the total errorin the frequency response at all of these samples.

Extended frequency sample design

For the samples $H({}_k)$ where $0\le k\le M-1$ and $N> M$ , find $h(n)$ , where $0\le n\le M-1$ minimizing $(H_d({}_k)-H({}_k))$

For $()$∞ l norm, this becomes a linear programming problem (standard packages availble!)

Here we will consider the $(, l)$ norm.

To minimize the $(, l)$ norm; that is, $\sum_{n=0}^{N-1} \left|H_d({}_k)-H({}_k)\right|$ , we have an overdetermined set of linear equations: $$\begin{pmatrix}e^{-(i{}_0\times 0)} & & e^{-(i{}_0(M-1))}\\ & & \\ e^{-(i{}_{N-1}\times 0)} & & e^{-(i{}_{N-1}(M-1))}\\ \end{pmatrix}h=\begin{pmatrix}{H}_d({}_0)\\ H_d({}_1)\\ \\ H_d({}_{N-1})\\ \end{pmatrix}$$ or $$Wh=H_d$$

The minimum error norm solution is well known to be $h=\overline{W}W^{(-1)}\overline{W}{H}_d$ ; $\overline{W}W^{(-1)}\overline{W}$ is well known as the pseudo-inverse matrix.