# FIR to FIR Model Reduction with Linear Group Delay in Passband by SDP Optimization

Authors: Haijiang Hu; Shaojing Song; Fengdeng Zhang
Journal: Journal of Electrical and Computer Engineering
 (2020)

---

## Abstract

Filter model reduction is an important optimization method in digital signal processing. A method of FIR to FIR model reduction using SDP optimization is proposed in this paper. At first, we use SDP to design an original FIR filter. Then we name a generalK-order FIR digital filter H1z−1 with coefficient values equal to the first K + 1 filter coefficient values of H0z−1. Finally, we design a new general K-order FIR digital filter H2z−1 connected in parallel with H1z−1 using SDP optimization. The experiment results show this method has good performance on the magnitude error and the linear phase in passband. Therefore, this method can be used in the field of digital signal processing.


---

## Body

## 1. Introduction

Filter model reduction is an important optimization method in digital signal processing. An FIR filter with the high order has better performance than another FIR filter with the low order. However, when the order is higher, the design of FIR filter is more complex while the implementation of FIR filter is more difficult. Therefore, when the performance requirement is not very rigorous, we use the method of FIR model reduction to design an FIR filter with the lower order instead of another FIR filter with the higher order. In the process of filter design, the convex programming (CP) have already been a hot research for recent years, such as semidefinite programming (SDP) and second-order cone programming (SOCP) [1]. In this paper, we present a method of FIR to FIR model reduction using SDP optimization. The experiment results show this method has good performance on the magnitude error and the linear phase in passband. Therefore, this method can be used in the field of digital signal processing.Many scientists study model reduction filter design and propose many different methods in recent years. An important recent result is that the filter minimization problem—given a filter, find the smallest equivalent filter-is NP-hard [2]. Reference [3] propose a comparative study based on combined special projections and important frequency-weighted model order reduction algorithms to compute optimal approximants for full-order digital filter. In Reference [4], two different algorithms for approximating FIR by IIR filters are treated: truncation of the balanced model and the Hankel-norm optimal approximation. Cain et al. [5] extends the use of the balanced model truncation and Hankel-norm optimal approximation to permit close approximation of complex FIR prototypes by IIR filters. Saberifar et al. [6] considers automatic reduction of combinatorial filters to a given size, even if that reduction necessitates changes to the filter’s behavior. Agrawal et al. [7] proposes an efficient technique for optimal design of IIR filter with minimum passband error, minimum stopband error, high stopband attenuation, and also free from limit cycle effect using cuckoo search algorithm. Yu and Xiong [8] studies an H∞ model reduction problem for interval frequency negative imaginary systems. Ramesh et al. [9] propose that the higher-order discrete systems are approximated into the lower-order discrete systems with the help of proposed model order reduction technique. This order reduction includes cross multiplication of polynomials process and using the Genetic Algorithm at the tail end of approximation process. Cain et al. [5] extends the use of the balanced model truncation and Hankel-norm optimal approximation to permit close approximation of complex FIR prototypes by IIR filters. Aldhaheri [10] presents a numerically efficient technique for the design of reduced-order IIR digital filters. Deng et al. [11] studies the design of linear phase IIR filters via optimal Hankel-norm approximation. Adamou-Mitiche and Mitiche [12] uses the special projections of frequency-weighted model order reduction algorithms, based on the gradient flow without frequency weighted, the frequency-weighted balanced truncation, and the gradient flow with frequency weighted, respectively. Reference [13] proposes a new Hankel-norm approach to the robust receding horizon FIR filter design in discrete-time state space under intensive external disturbances. In contrast to the above methods, our proposed method has simple process and good performance. Therefore, this method is easy to apply in the model reduction filter design.


## 2. Principle

In our design, we use the following method to realize the FIR to FIR model reduction.


### 2.1. Basic SDP Optimization for FIR Design

In our design,H0ω is a FIR filter with N-order. H0ω is stated as follows:(1)H0e−jω=∑n=0Nhne−jnω,where N is the order of filter.H
0
ω is also stated as follows:(2)H0ω=∑n=0Nhne−jnω=hTcω−jsω.We defineFx=diagDω1,Dω2,…,DωM, where M is the number of sampling points, and(3)Dω=δα1ωα2ωα1ω10α2ω01≥0.InDω,(4)α1ω=hTWωcω−WωHrω,α2ω=hTWωsω−WωHiω,where Wω is the weight function, Hrω and Hiω are the real part and the imaginary part of transfer function in the ideal filter. And we can obtain(5)Dω=100000000δ+0Wωcos0ωWωsin0ωWωcos0ω00Wωsin0ω00h0+⋯+0WωcosNωWωsinNωWωcosNω00WωsinNω00hN+0−WωHrωWωHiω−WωHrω10WωHiω01,and(6)Dω=D1ωδ+D2ωh0+⋯+DN+2ωhN+D0ω.Therefore, for SDP optimization,(7)F0=D0ω1⋯0⋮⋱⋮0⋯D0ωM,F1=D1ω1⋯0⋮⋱⋮0⋯D1ωM,⋮FN+2=DN+2ω1⋯0⋮⋱⋮0⋯DN+2ωM,where M is the number of sampling points.We also can defineFF and c as follows: FF=F1F2⋯FN+2 and c=10⋯0T. epsi is an presetting threshold value and a constant. After setting F0, FF, c, and epsi, we can get the result from output xs by SDP method. After all parameters are obtained, we use SeDuMi [14] for Matlab to optimize this problem. The SDP function in SeDuMi is defined as follows:function [xs, Fs, fs, k] = projective_sdp(c, FF, F0, epsi)Title: projective algorithm for homogenized SDP problems.Description: implements the projective algorithm.It finds a vectorx thatminimizesc′ ∗ xsubject to:F(x) ≥ 0whereF(x) = x(1) ∗ F1 + x(2) ∗ F2 + ⋯ + x(n) ∗ Fn + F0 is positive semidefinite.Input:c: p-dimensional cost vectorFF: m × m ∗ p matrix of the form FF=F1F2⋯FpF0: m × m constant matrix constraint F(x) ≥ 0epsi: tolerance for the gap between f(xk) and its lower boundOutput:xs: solution for the decision variablesfs: value of the objective function at x = xsFs: constraint matrix F(x) at x = xsk: number of iterations at convergence


### 2.2. FIR Model Reduction by SDP

At first, we name a generalK-order FIR digital filter H1z−1 with coefficient values equal to the first K + 1 filter coefficient values of H0z−1. K is a positive integer, which is not less than N/2. Then, we design a new general K-order FIR digital filter H2z−1 connected in parallel with H1z−1 using SDP optimization.This step can be described that the objective is to designH2z−1 to minimize both the magnitude difference and group delay difference between H1z−1+H2z−1 and H0z−1. Therefore, the objective function is stated as follows:(8)Hobjω=h1+h2Tcω−jsω,where h1 is constant vector and h2 is optimizing objective.F
x
=
diag
D
ω
1
,
D
ω
2
,
…
,
D
ω
M, where M is number of sampling points, and(9)Dω=δα1ωα2ωα1ω10α2ω01≥0.InDω,(10)α1ω=h1+h2TWωcω−WωHrω,α2ω=h1+h2TWωsω−WωHiω,where Wω is the weight function and Hrω and Hiω are the real part and the imaginary part of transfer function in the ideal filter. And we can obtain(11)Dω=100000000δ+0Wωcos0ωWωsin0ωWωcos0ω00Wωsin0ω00h10+⋯+0WωcosKωWωsinKωWωcosKω00WωsinKω00h1K+0Wωcos0ωWωsin0ωWωcos0ω00Wωsin0ω00h20+⋯+0WωcosKωWωsinKωWωcosKω00WωsinKω00h2K+0−WωHrωWωHiω−WωHrω10WωHiω01.and(12)Dω=D1ωδ+D2ωh0+⋯+DK+2ωhK+D0ω.The following analysis is same to basic SDP optimization.After obtainingH2z−1, we calculate H1z−1+H2z−1 as the new FIR filter, and compare the performance between H0z−1 and H1z−1+H2z−1.


## 2.1. Basic SDP Optimization for FIR Design

In our design,H0ω is a FIR filter with N-order. H0ω is stated as follows:(1)H0e−jω=∑n=0Nhne−jnω,where N is the order of filter.H
0
ω is also stated as follows:(2)H0ω=∑n=0Nhne−jnω=hTcω−jsω.We defineFx=diagDω1,Dω2,…,DωM, where M is the number of sampling points, and(3)Dω=δα1ωα2ωα1ω10α2ω01≥0.InDω,(4)α1ω=hTWωcω−WωHrω,α2ω=hTWωsω−WωHiω,where Wω is the weight function, Hrω and Hiω are the real part and the imaginary part of transfer function in the ideal filter. And we can obtain(5)Dω=100000000δ+0Wωcos0ωWωsin0ωWωcos0ω00Wωsin0ω00h0+⋯+0WωcosNωWωsinNωWωcosNω00WωsinNω00hN+0−WωHrωWωHiω−WωHrω10WωHiω01,and(6)Dω=D1ωδ+D2ωh0+⋯+DN+2ωhN+D0ω.Therefore, for SDP optimization,(7)F0=D0ω1⋯0⋮⋱⋮0⋯D0ωM,F1=D1ω1⋯0⋮⋱⋮0⋯D1ωM,⋮FN+2=DN+2ω1⋯0⋮⋱⋮0⋯DN+2ωM,where M is the number of sampling points.We also can defineFF and c as follows: FF=F1F2⋯FN+2 and c=10⋯0T. epsi is an presetting threshold value and a constant. After setting F0, FF, c, and epsi, we can get the result from output xs by SDP method. After all parameters are obtained, we use SeDuMi [14] for Matlab to optimize this problem. The SDP function in SeDuMi is defined as follows:function [xs, Fs, fs, k] = projective_sdp(c, FF, F0, epsi)Title: projective algorithm for homogenized SDP problems.Description: implements the projective algorithm.It finds a vectorx thatminimizesc′ ∗ xsubject to:F(x) ≥ 0whereF(x) = x(1) ∗ F1 + x(2) ∗ F2 + ⋯ + x(n) ∗ Fn + F0 is positive semidefinite.Input:c: p-dimensional cost vectorFF: m × m ∗ p matrix of the form FF=F1F2⋯FpF0: m × m constant matrix constraint F(x) ≥ 0epsi: tolerance for the gap between f(xk) and its lower boundOutput:xs: solution for the decision variablesfs: value of the objective function at x = xsFs: constraint matrix F(x) at x = xsk: number of iterations at convergence


## 2.2. FIR Model Reduction by SDP

At first, we name a generalK-order FIR digital filter H1z−1 with coefficient values equal to the first K + 1 filter coefficient values of H0z−1. K is a positive integer, which is not less than N/2. Then, we design a new general K-order FIR digital filter H2z−1 connected in parallel with H1z−1 using SDP optimization.This step can be described that the objective is to designH2z−1 to minimize both the magnitude difference and group delay difference between H1z−1+H2z−1 and H0z−1. Therefore, the objective function is stated as follows:(8)Hobjω=h1+h2Tcω−jsω,where h1 is constant vector and h2 is optimizing objective.F
x
=
diag
D
ω
1
,
D
ω
2
,
…
,
D
ω
M, where M is number of sampling points, and(9)Dω=δα1ωα2ωα1ω10α2ω01≥0.InDω,(10)α1ω=h1+h2TWωcω−WωHrω,α2ω=h1+h2TWωsω−WωHiω,where Wω is the weight function and Hrω and Hiω are the real part and the imaginary part of transfer function in the ideal filter. And we can obtain(11)Dω=100000000δ+0Wωcos0ωWωsin0ωWωcos0ω00Wωsin0ω00h10+⋯+0WωcosKωWωsinKωWωcosKω00WωsinKω00h1K+0Wωcos0ωWωsin0ωWωcos0ω00Wωsin0ω00h20+⋯+0WωcosKωWωsinKωWωcosKω00WωsinKω00h2K+0−WωHrωWωHiω−WωHrω10WωHiω01.and(12)Dω=D1ωδ+D2ωh0+⋯+DK+2ωhK+D0ω.The following analysis is same to basic SDP optimization.After obtainingH2z−1, we calculate H1z−1+H2z−1 as the new FIR filter, and compare the performance between H0z−1 and H1z−1+H2z−1.


## 3. Experiments

In the following two examples, we use our method to implement the model reduction FIR design. In our design, the number of sampling pointM is 900, epsi is 0.1, and weight function Wω is(13)Wω=1,ωin passband,1.5,ωin stopband,0,ωin transition band,respectively. The first example is to design the low-pass model reduction FIR filter and the second example is to design the high-pass model reduction FIR filter.


### 3.1. Example 1

For the low pass filter example: original filter order = 40, model reduction filter order = 20,wp=0.3π,ws=0.6π, passband group delay = 9.2. This FIR filter is described as follows:(14)Hidealω=e−j9.2ω,ω≤0.3π,0,ω>0.6π.The design results of the second experiment are shown in Figures1 and 2. Figure 1 shows the result of original FIR filter with 40-order while Figure 2 shows the result of FIR filter with 20-order after model reduction. From Figures 1 and 2, we also can know the magnitude-frequency characteristic of model reduction FIR filter is similar to original FIR filter, while the group delay in passband of model reduction FIR filter is also the approximate linearization. Table 1 shows the passband error δp, the stopband error δs, and the group delay error δg of the original FIR filter and the model reduction FIR filter in experiment 1. From Table 1, we can see the performance on the passband error, the stopband error, and the group delay in passband in the model reduction FIR filter are similar to the performance of the original FIR filter. Therefore, our method is useful for FIR to FIR model reduction with linear group delay in passband.Figure 1
Performance of original FIR filter for example 1.Figure 2
Performance of model reduction FIR filter for example 1.Table 1
Performance comparison in example 1.
Design method
Performance
δ
p
δ
s
δ
g
H
0
0.00000517
0.00002981
0.00653796
H
1
0.09134123
0.16381954
1.19473802
H
1 + H2
0.00340258
0.00634723
0.03373886


### 3.2. Example 2

For a high pass filter example: original filter order = 40, model reduction filter order = 30,ws=0.4π,wp=0.7π, passband group delay = 21. This FIR filter is described as follows:(15)Hidealω=0,ω≤0.4π,e−j21ω,ω>0.7π.The design results of the third experiment are shown in Figures3 and 4. Figure 3 shows the result of original FIR filter with 40-order while Figure 4 shows the result of FIR filter with 30-order after model reduction. From Figures 3 and 4, we also can know the magnitude-frequency characteristic of model reduction FIR filter is similar to original FIR filter, while the group delay in passband of model reduction FIR filter is also the approximate linearization. Table 2 shows the passband error δp, the stopband error δs, and the group delay error δg of the original FIR filter and the model reduction FIR filter in experiment 2. From Table 2, we can see the performance on the passband error, the stopband error, and the group delay in passband in the model reduction FIR filter are similar to the performance of the original FIR filter. Therefore, in high pass FIR filter design, our method is also useful for FIR to FIR model reduction with linear group delay in passband.Figure 3
Performance of original FIR filter for example 2.Figure 4
Performance of model reduction FIR filter for example 2.Table 2
Performance comparison in example 2.
Design method
Performance
δ
p
δ
s
δ
g
H
0
0.00007143
0.00001533
0.00458099
H
1
0.00788919
0.00690130
0.07617960
H
1 + H2
0.00106166
0.00027860
0.01039840


## 3.1. Example 1

For the low pass filter example: original filter order = 40, model reduction filter order = 20,wp=0.3π,ws=0.6π, passband group delay = 9.2. This FIR filter is described as follows:(14)Hidealω=e−j9.2ω,ω≤0.3π,0,ω>0.6π.The design results of the second experiment are shown in Figures1 and 2. Figure 1 shows the result of original FIR filter with 40-order while Figure 2 shows the result of FIR filter with 20-order after model reduction. From Figures 1 and 2, we also can know the magnitude-frequency characteristic of model reduction FIR filter is similar to original FIR filter, while the group delay in passband of model reduction FIR filter is also the approximate linearization. Table 1 shows the passband error δp, the stopband error δs, and the group delay error δg of the original FIR filter and the model reduction FIR filter in experiment 1. From Table 1, we can see the performance on the passband error, the stopband error, and the group delay in passband in the model reduction FIR filter are similar to the performance of the original FIR filter. Therefore, our method is useful for FIR to FIR model reduction with linear group delay in passband.Figure 1
Performance of original FIR filter for example 1.Figure 2
Performance of model reduction FIR filter for example 1.Table 1
Performance comparison in example 1.
Design method
Performance
δ
p
δ
s
δ
g
H
0
0.00000517
0.00002981
0.00653796
H
1
0.09134123
0.16381954
1.19473802
H
1 + H2
0.00340258
0.00634723
0.03373886


## 3.2. Example 2

For a high pass filter example: original filter order = 40, model reduction filter order = 30,ws=0.4π,wp=0.7π, passband group delay = 21. This FIR filter is described as follows:(15)Hidealω=0,ω≤0.4π,e−j21ω,ω>0.7π.The design results of the third experiment are shown in Figures3 and 4. Figure 3 shows the result of original FIR filter with 40-order while Figure 4 shows the result of FIR filter with 30-order after model reduction. From Figures 3 and 4, we also can know the magnitude-frequency characteristic of model reduction FIR filter is similar to original FIR filter, while the group delay in passband of model reduction FIR filter is also the approximate linearization. Table 2 shows the passband error δp, the stopband error δs, and the group delay error δg of the original FIR filter and the model reduction FIR filter in experiment 2. From Table 2, we can see the performance on the passband error, the stopband error, and the group delay in passband in the model reduction FIR filter are similar to the performance of the original FIR filter. Therefore, in high pass FIR filter design, our method is also useful for FIR to FIR model reduction with linear group delay in passband.Figure 3
Performance of original FIR filter for example 2.Figure 4
Performance of model reduction FIR filter for example 2.Table 2
Performance comparison in example 2.
Design method
Performance
δ
p
δ
s
δ
g
H
0
0.00007143
0.00001533
0.00458099
H
1
0.00788919
0.00690130
0.07617960
H
1 + H2
0.00106166
0.00027860
0.01039840


## 4. Conclusion

In this paper, we use SDP to solve FIR to FIR model reduction design. At first, we name a generalK-order FIR digital filter H1z−1 with coefficient values equal to the first K + 1 filter coefficient values of H0z−1. Then we design a new general K-order FIR digital filter H2z−1 connected in parallel with H1z−1 using SDP optimization. The experiments testify this method has good performance on the passband error and group delay error in the passband. Therefore, this method is an efficient algorithm for FIR to FIR model reduction which can be used in the digital signal processing widely.



---

*Source: 4503706-2020-02-20.xml*