# Low-Cost Design of an FIR Filter by Using a Coefficient Mapping Method

Authors: Ming-Chih Chen; Hong-Yi Wu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This work presents a novel coefficient mapping method to reduce the
area cost of the finite impulse response (FIR) filter design, especially for optimizing
its coefficients. Being capable of reducing the area cost and improving the filter performance,
the proposed mapping method consists of four steps: quantization of coefficients,
import of parameters, constitution of prime coefficients with parameters, and constitution
of residual coefficients with prime coefficients. Effectiveness of the proposed coefficient
mapping method is verified by selecting the 48-tap filter of IS-95 code division multiple
access (CDMA) standard as the benchmark. Experimental results indicate that the proposed
design with canonical signed digit (CSD) coefficients can operate at 86 MHz with an area of
241,813 um2, leading to a throughput rate of 1,382 Mbps. Its ratio of throughput/area is 5,715 Kbps/um2,
yielding a higher performance than that of previous designs. In summary, the proposed design reduces 5.7%
of the total filter area, shortens 25.7% of the critical path delay, and improves 14.8% of the throughput/area
by a value over that of the best design reported before.


---

## Body

## 1. Introduction

Digital signal processing applications are common in home entertainment systems, television sets, high-fidelity audio equipment, and information systems. The digital filter is an important component in mathematical operations on a sampled, discrete-time signal to enhance the certainty of a signal. The digital filter is characterized by its transfer function. Two digital filters are infinite impulse response (IIR) and finite impulse response (FIR) filters. The IIR filter consists of a transfer function with feedback mode, and the FIR filter consists of the function with nonfeedback mode. Commonly found in image processing, audio processing, and wireless communications, FIR filter applications are characterized by a linear phase, arbitrary magnitude, and relatively easy implementation. The filter hardware consists of adders, subtractors, shifters, and registers. Many related works [1–9] attempt to reduce the number of these required components in filter implementation, especially for the optimization of coefficients’ realization. Experimental results demonstrate that the proposed coefficient mapping method performs better than previous designs in terms of area ratio.The rest of this paper is organized as follows. Section2 briefly describes previous researches for filter optimization. Section 3 then describes the coefficient mapping method. Next, Section 4 summarizes the experimental results and compares them with those of other previous designs. Conclusions are finally drawn in Section 5, along with recommendations for future research.


## 2. Background

### 2.1. Digital FIR Filter

Digital filters generally vary in coefficients, based on their specifications. The design of coefficients in a filter can be divided into four portions: coefficient selection, coefficient identification, searching algorithm, and coefficient quantization.(1) Coefficient Selection. Typically determined by a set of filter specifications, coefficient selection must consider the number of taps, bit width, and filter complexity. According to the different complexities of coefficients, different algorithms are used to find the common subexpressions (CSs) and eliminate them for obtaining the best area reduction.(2) Coefficient Identification. Coefficients must be encoded to determine the area cost of a filter and the frequency of extracting common subexpressions. In coefficient encoding, the common expression is binary encoding. However, this encoding method causes more 1’s signals in data expression and more calculations in hardware implementation. Hence, optimizing more coefficients [10, 11] involves using the canonic signed digit (CSD) expression to eliminate many 1’s signals and using less common subexpressions.(3) Searching Algorithm. The searching algorithm can find more common subexpressions to reduce the area cost of filter. Although many works [1–9, 12, 13] have attempted to find as many common subexpressions as possible, a more complex algorithm may not yield a higher performance, especially in coefficients with a low complexity.(4) Coefficient Quantization. Coefficient quantization is an effective means of reducing the number of logic gates while implementing a filter. When the coefficients are quantized for implementation, the commonly used rounding method causes a deviation in the time and frequency responses of the implemented filter from the ideal response. Sensitivity of the filter response is of priority concern when quantizing the coefficients.


### 2.2. Optimization of the FIR Filter

The equation of FIR filter can be expressed as (1), and its transferred function can also be expressed as (2):
(1)y(n)=∑k=0N-1h(k)x(n-k),(2)H(z)=∑n=0N-1h(n)z-n.Parametern in (1) and (2) is expressed as the number of taps. This parameter is related to the output of a filter system and its frequency responses. Two implementation methods used for a filter are direct and cascade architectures. Here, the direct architecture is of priority concern, especially for enhancing the frequency responses of a filter with all zeros. The direct architecture can also be divided into direct and transposed forms. The direct form consists mainly of multipliers, adders, and registers. Figure 1 shows the architecture of the direct form. An n-tap filter with a direct form requires n copies of a multiplier, n-1 copies of an adder, and n copies of a register.Figure 1
Filter architecture of a direct form.Coefficientsh(0)–h(k) can be expressed as binary numbers. The binary expressions for the coefficients can be found with the common subexpressions (CSs) between them. In previous researches [1–9], there are three common subexpression elimination (CSE) methods including horizontal, vertical, and mixed searching methods. The method in [1] uses CSD expressions [2] for the coefficients and uses horizontal searching algorithm to find the CSs including (1,0,1), (1,0,-1), (1,0,0,1), and (1,0,0,-1). This method first optimizes the CS with the highest appearance until no CS can be extracted. In [3, 7], this method also uses CSD expressions, yet uses vertical search to find the CSs, including (1,-1) and (-1,1). By modifying the vertical searching method in [8], the method in [4] first uses horizontal search to extract the CSs including (1,0,1), (1,0,-1), (1,0,0,1) and (1,0,0,-1), which is expressed in CSD format. Thereafter, this method performs a vertical search to extract the CSs, including (1,0,1) and (-1,0,1).In addition to using two horizontal methods and one vertical searching method to extract the CSs, the method in [5] also uses a multiplier-adder block (MAB) and structure adder (SA) to construct the CSs and their residues. Besides finding two CSs with the same appearances, the method in [6] extracts the CS with a smaller bit width. A previous work [8] developed two methods for extracting the CSs in CSD format. The first method analyzes the CSs with 3-, 4-, and 5-bit by performing the statistics of their appearances. The second method searches the coefficients up to down and extracts the CSs between them by using vertical search. The method in [9] proposes a rule in which the depth of logic gates cannot be increased by performing the horizontal search in the same way as in [4] and the vertical search in the same way as in [8].Following implementation of the above searching methods, the CSs can be extracted and the same CSs can be used for calculation only once. Calculation times of the filter are reduced due to the extractions. These searching methods can also reduce the required number of adders and subtractors. To verify the different searching methods, the 48-tap filter of IS-95 CDMA is selected as the benchmark.


## 2.1. Digital FIR Filter

Digital filters generally vary in coefficients, based on their specifications. The design of coefficients in a filter can be divided into four portions: coefficient selection, coefficient identification, searching algorithm, and coefficient quantization.(1) Coefficient Selection. Typically determined by a set of filter specifications, coefficient selection must consider the number of taps, bit width, and filter complexity. According to the different complexities of coefficients, different algorithms are used to find the common subexpressions (CSs) and eliminate them for obtaining the best area reduction.(2) Coefficient Identification. Coefficients must be encoded to determine the area cost of a filter and the frequency of extracting common subexpressions. In coefficient encoding, the common expression is binary encoding. However, this encoding method causes more 1’s signals in data expression and more calculations in hardware implementation. Hence, optimizing more coefficients [10, 11] involves using the canonic signed digit (CSD) expression to eliminate many 1’s signals and using less common subexpressions.(3) Searching Algorithm. The searching algorithm can find more common subexpressions to reduce the area cost of filter. Although many works [1–9, 12, 13] have attempted to find as many common subexpressions as possible, a more complex algorithm may not yield a higher performance, especially in coefficients with a low complexity.(4) Coefficient Quantization. Coefficient quantization is an effective means of reducing the number of logic gates while implementing a filter. When the coefficients are quantized for implementation, the commonly used rounding method causes a deviation in the time and frequency responses of the implemented filter from the ideal response. Sensitivity of the filter response is of priority concern when quantizing the coefficients.


## 2.2. Optimization of the FIR Filter

The equation of FIR filter can be expressed as (1), and its transferred function can also be expressed as (2):
(1)y(n)=∑k=0N-1h(k)x(n-k),(2)H(z)=∑n=0N-1h(n)z-n.Parametern in (1) and (2) is expressed as the number of taps. This parameter is related to the output of a filter system and its frequency responses. Two implementation methods used for a filter are direct and cascade architectures. Here, the direct architecture is of priority concern, especially for enhancing the frequency responses of a filter with all zeros. The direct architecture can also be divided into direct and transposed forms. The direct form consists mainly of multipliers, adders, and registers. Figure 1 shows the architecture of the direct form. An n-tap filter with a direct form requires n copies of a multiplier, n-1 copies of an adder, and n copies of a register.Figure 1
Filter architecture of a direct form.Coefficientsh(0)–h(k) can be expressed as binary numbers. The binary expressions for the coefficients can be found with the common subexpressions (CSs) between them. In previous researches [1–9], there are three common subexpression elimination (CSE) methods including horizontal, vertical, and mixed searching methods. The method in [1] uses CSD expressions [2] for the coefficients and uses horizontal searching algorithm to find the CSs including (1,0,1), (1,0,-1), (1,0,0,1), and (1,0,0,-1). This method first optimizes the CS with the highest appearance until no CS can be extracted. In [3, 7], this method also uses CSD expressions, yet uses vertical search to find the CSs, including (1,-1) and (-1,1). By modifying the vertical searching method in [8], the method in [4] first uses horizontal search to extract the CSs including (1,0,1), (1,0,-1), (1,0,0,1) and (1,0,0,-1), which is expressed in CSD format. Thereafter, this method performs a vertical search to extract the CSs, including (1,0,1) and (-1,0,1).In addition to using two horizontal methods and one vertical searching method to extract the CSs, the method in [5] also uses a multiplier-adder block (MAB) and structure adder (SA) to construct the CSs and their residues. Besides finding two CSs with the same appearances, the method in [6] extracts the CS with a smaller bit width. A previous work [8] developed two methods for extracting the CSs in CSD format. The first method analyzes the CSs with 3-, 4-, and 5-bit by performing the statistics of their appearances. The second method searches the coefficients up to down and extracts the CSs between them by using vertical search. The method in [9] proposes a rule in which the depth of logic gates cannot be increased by performing the horizontal search in the same way as in [4] and the vertical search in the same way as in [8].Following implementation of the above searching methods, the CSs can be extracted and the same CSs can be used for calculation only once. Calculation times of the filter are reduced due to the extractions. These searching methods can also reduce the required number of adders and subtractors. To verify the different searching methods, the 48-tap filter of IS-95 CDMA is selected as the benchmark.


## 3. Proposed Coefficient Mapping Method

The mapping method divides the coefficients into two parts: primary coefficients and remaining coefficients. The parameters that are set up in the algorithm areQh and Qp. The constitution of coefficients has two steps: constitution of primary coefficients and calculation of multiple relations between the primary and remaining coefficients. The operation steps of the mapping method are described as follows.Step 1.
Normalize then-tap coefficients ci by multiplying 2m. The normalized results are hi=ci×2m, for 0≤i≤n-1.Step 2.
Separate normalized coefficientshi into two parts, H1 and H2:
(3)H1={hj},0≤j≤n2-1,H2={hk},n2≤k≤n-1.Step 3.
Quantizehj and hk based on Qh. Equations (4) and (5) show the relations between Qh, hj, and hk(4)hj=Qh(Sh,j)×Δhj,(5)hk=Qh(Sh,k)×Δhk.
Parameters Δhj and Δhk are the variances after performing the quantization. Let hj′=Qh(Sh,j) and let hk′=Qh(Sh,k). Equations (4) and (5) thus become the following equations separately:
(6)hj=hj′×Δhj,(7)hk=hk′×Δhk.Step 4.
Find a multiple valuepk,j that is between hk and hj, and find a multiple value pk,j′ that is between hk′ and hj′. The relations are shown as
(8)hk=pk,j×hj⟹pk,j=hkhj,(9)hk′=pk,j′×hj′⟹pk,j′=hk′h′j.Step 5.
Quantizepk,j′ based on Qp. Equation (10) shows the relation between Qp and pk,j′. Parameter Δpk,j denotes the variance after performing the quantization:
(10)pk,j′=Qp(Sp,k,j)×Δpk,j.
Letpk,j′′=Qp(Sp,k,j), and (11) shows the relation between pk,j′ and pk,j′′:
(11)pk,j′=pk,j′′×Δpk,j.Step 6.
Constitutehk′ and substitute (11) with (9). The relation between hk′, hj′, and pk,j′ becomes
(12)hk′=pk,j′′×hj′×Δpk,j.Step 7.
Revert the parametershj and hk by substituting (9) and (12) with (7). Equations (13) and (14) show the relations as follows:
(13)hj=Qh(Sh,j)×Δhj⟹hj=hj′×Δhj,(14)hk=Qh(Sh,j)×Qp(Sp,k,j)×Δpk,j×Δhk⟹hk=hj′×pk,j′′×Δpk,j×Δhk.Lethk′′=hj′×pk,j′′, and (14) is then modified to
(15)hk=hk′′×Δpk,j×Δhk.
According to the variance, the calculation error and correct rates can be expressed as
(16)ei={1-ΔifΔ≤1,Δ-1ifΔ>1,(17)ai=1-ei.
Substitute the variances of hk and hj into (16). The error rate ei can be obtained, for 0≤i≤n-1.For example, this work selects 18 coefficientsc0–c17 from 48-tap IS-95 CDMA to perform the mapping method. The coefficients are
(18)c0=-0.025299,c1=-0.034179,c2=-0.035766,c3=-0.016723,c4=0.021606,c5=0.064941,c6=0.091003,c7=0.081909,c8=0.037078,c9=-0.022003,c10=-0.060729,c11=-0.051177,c12=0.007873,c13=0.084381,c14=0.126861,c15=0.094543,c16=-0.012847,c17=-0.143463.Before performing the mapping method, this work first sets up two parameters in whichQh equals 32 and Qp equals 0.25 to reduce the hardware design complexity. After Steps 1, 2, 3, 4, 5, 6, and 7 of the proposed method are performed, Table 1 lists the generated hi values. Figure 2(a) shows the frequency responses, poles, and zeros distributions of the original filter. Figure 2(b) shows the behaviors of the filter with modified coefficients after applying the proposed mapping method. The behaviors in Figures 2(a) and 2(b) are approximately the same with each other.Table 1
New coefficients after performing the mapping method (Qh=32, Qp=0.25).
Group
Sign
Coefficient
Error rate (%)
h
j, hk (original coefficient)
h
j
′, hk′ (new coefficient)
H
1
c
0
−
829
832 (32×26)
0.36
c
1
−
1120
1120 (32×35)
0.00
c
2
−
1172
1184 (32×37)
1.01
c
3
−
548
544 (32×17)
0.74
c
4
+
708
704 (32×22)
0.57
c
5
+
2128
2144 (32×67)
0.75
c
6
+
2982
2976 (32×93)
0.20
c
7
+
2684
2688 (32×84)
0.15
c
8
+
1215
1216 (32×38)
0.08
H
2
c
9
−
721
832 (832×1)
13.3
c
10
−
1990
1960 (1120×1.75)
1.53
c
11
−
1677
1776 (1184×1.5)
5.57
c
12
+
258
272 (544×0.5)
5.15
c
13
+
2765
2816 (704×4)
1.81
c
14
+
4157
4288 (2144×2)
3.06
c
15
+
3098
2976 (2976×1)
4.10
c
16
−
421
672 (2688×0.25)
37.4
c
17
−
4560
4560 (1216×3.75)
3.09(a) Frequency responses, poles and zeros distributions of the original filter. (b) Frequency responses, poles and zeros distributions of the modified filter.
(a)
(b)


## 4. Experimental Results

For comparison, Table2 lists various 48-tap filter designs for IS-95 CDMA. These filters can generate 16-bit output data at one clock cycle. The table shows the architecture- and gate-level information of the filters. The area cost of the architecture-level includes how many adders, subtractors, and registers are used for implementation. Gate-level information includes the area cost, critical path delay, throughput, and throughput per area. In the architecture-level, analysis results indicate that the original filter with binary coefficients has the largest area cost among other designs. The design in [7] has the smallest summation for calculating the number of adders and subtractors. More than having the smallest area cost, the proposed design also achieves the highest throughput and ratio of throughput per area in the gate-level synthesis among other designs.Table 2
Performance comparison of various 48-tap filter designs for generating 16-bit outputs.
Methods
Info.
Architecture level
Gate level
Area no. of add., sub., and reg.
Area (um2)
Critical path delay (ns)
Throughput (Mbps)
Throughput/area (Kbps/um2)
Binary
(220, 0, 48)
300284
12.61
1268
4225
CSD
(88, 74, 48)
299622
12.08
1324
4421
Pasˇko et al. [1]
(76, 22, 48)
271357
15.08
1061
3910
Jang and Yang  [3]
(72, 70, 48)
295567
15.27
1047
3545
Vinod et al. [4]
(62, 34, 48)
274025
14.32
1117
4077
Choo et al. [5]
(67, 24, 48)
259104
14.18
1128
4355
Takahashi and Yokoyama [6]
(78, 22, 48)
273902
15.28
1047
3823
Mahesh and Vinod [7]
(88, 0, 48)
255450
15.58
1271
4979
Kato et al. [8]
(64, 26, 48)
264240
14.46
1106
4187
Vinod et al. [9]
(62, 34, 48)
260976
14.25
1122
4303
Our method with binary format
(66, 0, 48)
244547 (4.3%)
11.45 (26.5%)
1397 (9.9%)
5713 (14.7%)
Our method with CSD format
(23, 33, 48)
241813 (5.3%)
11.58 (25.7%)
1382 (8.7%)
5715 (14.8%)Table2 lists two filter designs: the coefficients expressed with binary and CSD formats. In the architecture-level, the proposed filter with CSD coefficients has the smallest summation for calculating the number of adders and subtractors. The proposed filter only requires a total of 56 adders and subtractors which are the smallest amounts among the previous designs. The best design is the method in [7], which has an area of 255,450 um2 and achieves a throughput/area of 4,979 Kbps/um2. The proposed design with CSD coefficients can operate at 86 MHz with an area of 241,813 um2, leading to a throughput rate of 1,382 Mbps. Its ratio of throughput/area is 5,715 Kbps/um2, which is the highest performance among the previous designs. In summary, the proposed design reduces 5.7% of the total filter area, shortens 25.7% of the critical path delay, and improves 14.8% of the throughput/area compared with the best design in [7].


## 5. Conclusions

This work has developed a novel filter design with coefficient mapping method. The proposed method can reduce the area cost by finding the primary coefficients and using them to construct the remaining coefficients. The proposed method can also use several coefficients and construct all of the filter coefficients. Experimental results demonstrate that the proposed design with binary or CSD coefficients can more significantly reduce the area cost and improve the ratio of throughput/area compared with previous designs. Implementation results further demonstrate that the proposed design has the highest throughput with the lowest area cost.



---

*Source: 495207-2013-11-18.xml*