# A Novel Design of Sparse FIR Multiple Notch Filters with Tunable Notch Frequencies

Authors: Wei Xu; Anyu Li; Boya Shi; Jiaxiang Zhao
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

We focus on the design of finite impulse response (FIR) multiple notch filters. To reduce the computational complexity and hardware implementation complexity, a novel algorithm is developed based on the mixture of the tuning of notch frequencies and the sparsity of filter coefficients. The proposed design procedure can be carried out as follow: first, since sparse FIR filters have lower implementation complexity than full filters, a sparse linear phase FIR single notch filter with the given rejection bandwidth and passband attenuation is designed. Second, a tuning procedure is applied to the computed sparse filter to produce the desired sparse linear phase FIR multiple notch filter. When the notch frequencies are varied, the same tuning procedure can be employed to render the new multiple notch filter instead of designing the filter from scratch. The effectiveness of the proposed algorithm is demonstrated through three design examples.


---

## Body

## 1. Introduction

The multiple notch filters, which can highly attenuate some frequency components in the input signal while leaving the others relatively unchanged, are widely used in many applications. Important examples include radar systems, control and instrumentation systems, communications systems, medical applications, biomedical engineering, and indoor localization [1, 2].Various methods [3–8] have been reported to design FIR multiple notch filters. In general, the multiple notch filters derived from these algorithms are not sparse. Compared with full FIR filters, sparse filters can significantly reduce the implementation complexity in the hardware. In [9], we proposed an iterative reweighed OMP algorithm to compute sparse notch filters. However, when the notch frequencies are varied, it requires one to design the whole filter from scratch, hence increasing the computational complexity of this scheme.Recently, in [10–12], a number of algorithms are proposed to design FIR filters based on LMS minimization or Monte Carlo methods. The disadvantage of these approaches is the suboptimality in terms of the filter length related to its selectivity. Another disadvantage is that the attenuation at the notch frequency changes during the adaptation process; therefore, a strong attenuation of the disturbing signal at the notch frequency is not guaranteed. Moreover, the actual value of the attenuation at notch frequency is caused by the adaptation process.In this brief, the design problems of sparse FIR multiple notch filters with tunable notch frequencies are studied. To reduce the computational complexity and the hardware complexity, a novel algorithm is developed based on the mixture of the tuning of notch frequencies and the sparsity of filter coefficients. The sparse FIR multiple notch filters can significantly reduce the number of the adders and multipliers used in the hardware implementation. However, the design of FIR sparse filter always involves iterative procedures and numerical optimization, which results in a high computational complexity for the practice system. The tuning of notch frequencies is a useful operation for the design of FIR multiple notch filter. In the case of variable notch frequencies, the same tuning process is implemented to obtain the new multiple notch filter instead of designing the filter from scratch. Therefore, the tuning feature can significantly reduce the computational complexity. We demonstrate the effectiveness of this approach through three design examples.


## 2. Problem Formulation

Given the design parameters of linear phase FIR multiple notch filter, which include a set of the notch frequenciesω¯ii=1r, rejection bandwidth Δω, and passbands attenuation α, the given notch frequencies ω¯ii=1r satisfying ω¯i<ω¯i+1 for 1≤i≤r are allowed to be nonuniformly distributed in the set [0,π]. The ideal multiple notch filter amplitude response Hdω satisfies(1)Hdω=0ω∈Ω01ω∈Ω1,where Ω0 and Ω1 are, respectively, defined as(2)Ω0=ω∣ω-ω¯i≤Δω2,1≤i≤r,Ω1=0,π-Ω0.To simplify the presentation, we focus on the design of Type-I linear phase FIR filterHejω=e-jMωH0ω; that is, the filter order N=2M is even and hm=hN-m for all 0≤m≤N. For other types of filter, our design method presented in this letter is feasible. For the case of Type-I filter, the zero-phase amplitude response H0ω can be expressed as(3)H0ω=hM+2∑m=1MhM-mcos⁡mω,with M=N/2.


## 3. The Proposed Sparse Linear Phase FIR Multiple Notch Filter Design

In this section, a novel design method is presented to produce the sparse FIR multiple notch filter. The procedure of computing the linear phase FIR multiple notch filter starts with the estimation of the initial orderN of the filter Fejω through(4)N=maxi∈1,…,rNi.From [13, eq. (20)], Ni is computed as(5)Ni=max⁡N^ωp1i,ΔF,δp,δs,N^ωp2i,ΔF,δp,δs,where ΔF=Δω/2 and the function N^· is determined by [13, eq. (15)]. The arguments of N^· can be computed as(6)ωp1i=ω¯i-ΔF2,ωp2i=1-ω¯i-ΔF2,δp=δs=1-α1+α.The following design procedure is mainly comprised of two stages: in the first stage, a sparse linear phase FIR single notch filterFejω with the given rejection bandwidth and passband attenuation is designed as a fixed sparse filter. In the next stage, a tuning process is carried out to compute the desired multiple notch filter with the given notch frequencies based on the filter Fejω.


### 3.1. Sparse Linear Phase FIR Single Notch Filter Design

In this section, a sparse linear phase FIR single notch filterFejω of order N with the notch frequency ω¯1=0 is designed. Let Fejω=e-jMωF0ω represent the single notch filter, as shown in Figure 1; the real-valued amplitude response F0ω satisfies(7)F0ω=0,ω=0,0<F0ω<1-δF,0<ω<Δω2,F0ω-1<δF,Δω2≤ω≤π.Figure 1
The illustration for the amplitude response of the desired sparse single notch filter.The passband rippleδF of the single notch filter Fejω and the attenuation in the passbands α are related through(8)δF=1-α2r1+α.Equation (8) is a conservative choice of δF which ensures the multiple notch filter yielded from this choice to satisfy the design specifications. In most cases, δF can be chosen between 1-α/2r1+α and 1-α/1+α.The design of the sparse single notch filterFejω can be formulated as(9a)minff0(9b)s.t.cωf-1≤δF,ω∈Δω2,π,(9c)cωf=0,ω=0,where we have(10)cω=1cos⁡ω⋯cos⁡mω⋯cos⁡Mω,f=fM2fM-1⋯2fm⋯2f0T,with 0≤m≤M.To compute a solution of problem (9a), (9b), and (9c), we follow the standard discretization procedure as presented in [14] and replace the continuous parameter ω by L samples (where L≫1 is a large positive integer) uniformly distributed in the frequency set [Δω/2,π]. Thus, the discretization and normalized formulation of problem (9a), (9b), and (9c) is given by(11a)minff0(11b)s.t.Af-1L×1≤δF·1L×1,(11c)11×Lf=0,where we have(12)A=cω1cω2⋮cωl⋮cωL=1cos⁡ω1⋯cos⁡Mω11cos⁡ω2⋯cos⁡Mω2⋮⋮⋱⋮1cos⁡ωl⋯cos⁡Mωl⋮⋮⋱⋮1cos⁡ωL⋯cos⁡MωL,with ωl∈Δω/2,π and 1≤l≤L.It is known that this optimization problem is in general NP-hard due to the existence ofl0-norm in its objective function. To tackle this problem, a great deal of effort has been made to develop efficient algorithms. In this paper, we can employ one of these sparse filter algorithms, for example, linear programming [15], iterative second-order cone programming (ISOCP) [16], iterative reweighted l1 (IRL1) [17], and iterative reweighted OMP (IROMP) schemes [9], to attain the desired sparse FIR single notch filter.


### 3.2. The Design of the Desired Linear Phase FIR Multiple Notch Filter

In this section, a tuning process is implemented to derive the desired FIR multiple notch filter based onFejω of the previous stage.For the given notch frequencies setω¯ii=1r, the multiple notch filter Hejω can be given as(13)Hejω=e-jMω∑i=1rF0ω+ω¯i+F0ω-ω¯i.According to the Fourier transform theory, the impulse responsehn of Hejω can be obtained as(14)hn=∑i=1rfncos⁡nω¯i,where 0≤n≤N.Compute the attenuationα^ in the passbands of the linear phase FIR multiple notch filter Hejω as(15)α^=min⁡H0ωmax⁡H0ω,ω∈Ω1.Ifα^≤α, then the computed filter hnn=0N is a sparse solution for the given specifications. Otherwise, the following linear program optimization is run to minimize the attenuation in the passbands of the obtained filter:(16a)minh,μμ(16b)s.t.Bh-1L×1≤δ+μ·1L×1,(16c)cω¯ih=0,i=1,2,…,r,(16d)hn=0,n∈Z,where Z represents the set of indices at which h(n)=0 based on (14) and matrix B can be written as(17)B=cω1′cω2′⋮cωl′⋮cωL′,ωl′∈Ω1.If the optimal objective value μ of (16a), (16b), (16c), and (16d) is negative, that is, μ≤0, the obtained filter h is a sparse solution for the given specifications. Otherwise, the sparsity pattern Z is infeasible to the given specifications of the multiple notch filter; then the largest element is eliminated from Z and the linear program (16a), (16b), (16c), and (16d) is solved with the new set Z until μ≤0.When the notch frequencies are changed, the same tuning process is implemented to yield the new multiple notch filter instead of designing the filter from scratch. Figure2 outlines the main steps of the proposed algorithm.Figure 2
Flowchart of the proposed design algorithm.


## 3.1. Sparse Linear Phase FIR Single Notch Filter Design

In this section, a sparse linear phase FIR single notch filterFejω of order N with the notch frequency ω¯1=0 is designed. Let Fejω=e-jMωF0ω represent the single notch filter, as shown in Figure 1; the real-valued amplitude response F0ω satisfies(7)F0ω=0,ω=0,0<F0ω<1-δF,0<ω<Δω2,F0ω-1<δF,Δω2≤ω≤π.Figure 1
The illustration for the amplitude response of the desired sparse single notch filter.The passband rippleδF of the single notch filter Fejω and the attenuation in the passbands α are related through(8)δF=1-α2r1+α.Equation (8) is a conservative choice of δF which ensures the multiple notch filter yielded from this choice to satisfy the design specifications. In most cases, δF can be chosen between 1-α/2r1+α and 1-α/1+α.The design of the sparse single notch filterFejω can be formulated as(9a)minff0(9b)s.t.cωf-1≤δF,ω∈Δω2,π,(9c)cωf=0,ω=0,where we have(10)cω=1cos⁡ω⋯cos⁡mω⋯cos⁡Mω,f=fM2fM-1⋯2fm⋯2f0T,with 0≤m≤M.To compute a solution of problem (9a), (9b), and (9c), we follow the standard discretization procedure as presented in [14] and replace the continuous parameter ω by L samples (where L≫1 is a large positive integer) uniformly distributed in the frequency set [Δω/2,π]. Thus, the discretization and normalized formulation of problem (9a), (9b), and (9c) is given by(11a)minff0(11b)s.t.Af-1L×1≤δF·1L×1,(11c)11×Lf=0,where we have(12)A=cω1cω2⋮cωl⋮cωL=1cos⁡ω1⋯cos⁡Mω11cos⁡ω2⋯cos⁡Mω2⋮⋮⋱⋮1cos⁡ωl⋯cos⁡Mωl⋮⋮⋱⋮1cos⁡ωL⋯cos⁡MωL,with ωl∈Δω/2,π and 1≤l≤L.It is known that this optimization problem is in general NP-hard due to the existence ofl0-norm in its objective function. To tackle this problem, a great deal of effort has been made to develop efficient algorithms. In this paper, we can employ one of these sparse filter algorithms, for example, linear programming [15], iterative second-order cone programming (ISOCP) [16], iterative reweighted l1 (IRL1) [17], and iterative reweighted OMP (IROMP) schemes [9], to attain the desired sparse FIR single notch filter.


## 3.2. The Design of the Desired Linear Phase FIR Multiple Notch Filter

In this section, a tuning process is implemented to derive the desired FIR multiple notch filter based onFejω of the previous stage.For the given notch frequencies setω¯ii=1r, the multiple notch filter Hejω can be given as(13)Hejω=e-jMω∑i=1rF0ω+ω¯i+F0ω-ω¯i.According to the Fourier transform theory, the impulse responsehn of Hejω can be obtained as(14)hn=∑i=1rfncos⁡nω¯i,where 0≤n≤N.Compute the attenuationα^ in the passbands of the linear phase FIR multiple notch filter Hejω as(15)α^=min⁡H0ωmax⁡H0ω,ω∈Ω1.Ifα^≤α, then the computed filter hnn=0N is a sparse solution for the given specifications. Otherwise, the following linear program optimization is run to minimize the attenuation in the passbands of the obtained filter:(16a)minh,μμ(16b)s.t.Bh-1L×1≤δ+μ·1L×1,(16c)cω¯ih=0,i=1,2,…,r,(16d)hn=0,n∈Z,where Z represents the set of indices at which h(n)=0 based on (14) and matrix B can be written as(17)B=cω1′cω2′⋮cωl′⋮cωL′,ωl′∈Ω1.If the optimal objective value μ of (16a), (16b), (16c), and (16d) is negative, that is, μ≤0, the obtained filter h is a sparse solution for the given specifications. Otherwise, the sparsity pattern Z is infeasible to the given specifications of the multiple notch filter; then the largest element is eliminated from Z and the linear program (16a), (16b), (16c), and (16d) is solved with the new set Z until μ≤0.When the notch frequencies are changed, the same tuning process is implemented to yield the new multiple notch filter instead of designing the filter from scratch. Figure2 outlines the main steps of the proposed algorithm.Figure 2
Flowchart of the proposed design algorithm.


## 4. Simulation

In this section, we confirm the effectiveness of our multiple notch filter design scheme through three examples.Example 1.
Let us design a multiple notch filter specified by a set of notch frequencies0.25π,0.49π,0.78π, α=-0.80 (passbands attenuation), and Δω=0.05π (the rejection bandwidths).By substituting the design specifications into [9, eq. (11)], we obtain the initial order N=174. In this simulation, we employ the IROMP scheme [9] to design the sparse single notch filter. As shown in Figure 3, the amplitude response of the multiple notch filter is derived by following steps in Figure 2. It is obvious that the specification is well satisfied. The nonzero tap weights of the multiple notch filter yielded from our design method are listed in Table 1. The filter order, number of nonzero taps, rejection bandwidth, passband attenuation, and attenuation at the notch frequency are listed in Table 2.Table 1
Nonzero coefficients of the designed filter in Example1.
Taps Nonzero tap weights 0 174 0.004722848554565 24 150 0.002007423266603 33 141 −0.004871513257007 38 136 −0.030966811403170 39 135 −0.022053492615673 40 134 0.014951595120278 41 133 −0.021767842979883 42 132 0.011692029570564 43 131 0.006950807646344 44 130 0.044114166070248 45 129 0.006311408033158 46 128 −0.062066578840798 47 127 −0.005818521570352 48 126 −0.002318412822056 49 125 0.005091217785500 50 124 0.020608511742342 51 123 −0.014404626498885 52 122 0.061394774774335 53 121 0.008629427173138 54 120 −0.072558769634137 55 119 −0.010787517932644 56 118 −0.022623175477306 57 117 0.030869196951431 58 116 0.009932536096148 59 115 −0.014074814764124 60 114 0.094137780017783 61 113 −0.004199271003407 62 112 −0.061953987746997 63 111 −0.047952288148680 64 110 −0.038531961471284 65 109 0.076026372592104 66 108 −0.015111106082247 67 107 0.000183867057454 68 106 0.099331267386019 69 105 −0.012255378374269 70 104 −0.028055658481912 71 103 −0.100962624763570 72 102 −0.038372777955426 73 101 0.098683027527897 74 100 −0.036089958346951 75 99 0.029655283702946 76 98 0.071889586307707 77 97 0.004739347900282 78 96 −0.002403828886942 79 95 −0.153598792283481 80 94 −0.019548891523249 81 93 0.089075079456139 82 92 −0.023403440116641 83 91 0.056274737680820 84 90 0.018813444978966 85 89 0.047899881207932 86 88 0.000409323536052 87  0.911070614139502Table 2
A list of filter order, rejection bandwidth, and attenuation of Examples1–3.
Example Filter order The number of nonzero tap weights Rejection bandwidth Passband attenuation Attenuation at the notch frequency 1 174 105 0.050π −0.7197 dB −247 dB 2 174 105 0.050π −0.5349 dB −259 dB 3 174 105 0.050π −0.7687 dB −264 dBFigure 3
The amplitude response of the filter yielded from our design method for Example1.Example 2.
We only change the notch frequencies from{0.25π,0.49π,0.78π} of Example 1 to {0.34π,0.43π,0.72π} but use the same rejection bandwidth and attenuation in the passbands.Since the same rejection bandwidth and attenuation in the passbands as Example1 are used, the sparse single notch filter Fejω of (11a), (11b), and (11c) with N=174 can be identical to the one computed in Example 1. Following the tuning procedure from (14) to (16a), (16b), (16c), and (16d), we compute the sparse multiple notch filter with this new set of the notch frequencies. Figure 4 shows the performance of the sparse multiple notch filter yielded from our scheme. The nonzero tap weights of the multiple notch filter yielded from our design method are listed in Table 3. The filter order, number of nonzero taps, rejection bandwidth, passband attenuation, and attenuation at the notch frequency are listed in Table 2.Table 3
Nonzero coefficients of the designed filter in Example2.
Taps Nonzero tap weights 0 174 −0.001484391069741 24 150 0.015053216345025 33 141 0.011203465180753 38 136 0.031930539223127 39 135 −0.011989478832635 40 134 −0.047916512343373 41 133 0.001724422497417 42 132 0.012946318823095 43 131 0.029367872190180 44 130 0.012950777492872 45 129 −0.058861258880195 46 128 −0.027161496236364 47 127 0.038124403599415 48 126 0.005580972074984 49 125 0.024077586822642 50 124 −0.013761958746995 51 123 −0.036380554634187 52 122 0.026803049613006 53 121 −0.001700050810428 54 120 −0.023056804511978 55 119 0.041926654928440 56 118 0.000428542187068 57 117 −0.005253841608839 58 116 −0.008896975496026 59 115 −0.071272465825430 60 114 0.037660569869951 61 113 0.085639588936268 62 112 −0.020291841316044 63 111 −0.035719226300918 64 110 −0.069237101344906 65 109 −0.019718488202998 66 108 0.128901758725893 67 107 0.025726032859600 68 106 −0.073722260607230 69 105 −0.025836288834871 70 104 −0.045891876538100 71 103 0.057310758857846 72 102 0.075489239705611 73 101 −0.063149359304339 74 100 −0.003347070890743 75 99 0.014446702737718 76 98 −0.058103382956618 77 97 0.032069195768895 78 96 0.000558233096476 79 95 0.006719715851877 80 94 0.084935075668951 81 93 −0.076509802170425 82 92 −0.097984593409281 83 91 0.043634372404206 84 90 0.040410785159360 85 89 0.089360899339001 86 88 −0.003266951955140 87  0.915171992267534Figure 4
The amplitude response of the filter yielded from our design method for Example2.Example 3.
Change the set of notch frequencies in Example1 to {0.25π,0.49π,0.61π,0.78π}, while α and Δω remain the same.Sinceα and Δω are kept constant, we start with the sparse single notch filter F(ejω) which is the same as that derived in Example 1 (N=174). The sparse multiple notch filter with this new notch frequencies is obtained through the tuning process from (14) to (16a), (16b), (16c), and (16d). Figure 5 illustrates the amplitude response of this filter. It is evident that the specification is satisfied. The nonzero tap weights of the multiple notch filter yielded from our design method are listed in Table 4. The filter order, number of nonzero taps, rejection bandwidth, passband attenuation, and attenuation at the notch frequency are listed in Table 2.Table 4
Nonzero coefficients of the designed filter in Example3.
Taps Nonzero tap weights 0 174 0.001163545765695 24 150 0.003165433288996 33 141 0.002091982284630 38 136 −0.047102411486321 39 135 −0.005481276840672 40 134 0.019772136963283 41 133 −0.043110955540852 42 132 0.020979982565140 43 131 0.015127277492607 44 130 0.022611789510971 45 129 0.010481611606251 46 128 −0.039298064713159 47 127 −0.024983870407359 48 126 −0.013239453713585 49 125 0.022935249461144 50 124 0.027344765658964 51 123 −0.037957131548364 52 122 0.075665876343805 53 121 0.024121474369378 54 120 −0.104718797612301 55 119 −0.014707635070068 56 118 0.016302396989146 57 117 0.011567221940061 58 116 −0.010934081396023 59 115 0.019926233327605 60 114 0.089656608769556 61 113 −0.041103476228622 62 112 −0.033265661189825 63 111 −0.026560471743885 64 110 −0.082576601043643 65 109 0.085379844129436 66 108 0.024951523169648 67 107 −0.038897009099235 68 106 0.088237797320545 69 105 0.036518046705842 70 104 −0.053707639239860 71 103 −0.134082248075127 72 102 0.007838779814640 73 101 0.104434475095505 74 100 −0.081493323669535 75 99 0.057503261219777 76 98 0.103032966355301 77 97 −0.046232816359952 78 96 −0.001798639004124 79 95 −0.100284039691277 80 94 −0.057999870693463 81 93 0.060896839992225 82 92 0.036785941586311 83 91 0.041803167312136 84 90 −0.030010449210885 85 89 0.094188919109719 86 88 0.018630470290357 87  0.882383969239141Figure 5
The amplitude response of the filter yielded from our design method for Example3.


## 5. Conclusion

In this paper, a novel approach has been presented for the design of sparse FIR multiple notch filters with tunable notch frequencies. To further improve the efficiency, the proposed algorithm is based on the mixture of the tuning of notch frequencies and the sparsity of filter coefficients. In the case of variable notch frequencies, the same tuning procedure can be used to render the new multiple notch filter instead of designing the filter from scratch. Therefore, the proposed algorithm can significantly reduce the computational complexity. Three examples are given to show the effectiveness of this approach.



---

*Source: 3490830-2018-05-08.xml*