FIR Filter Design using Multiple Constant Multiplication (MCM) Method with Modified Ripple Carry Adder

FIR Filter Design using Multiple Constant Multiplication (MCM) Method with Modified Ripple Carry Adder

M. Manoj,

ECE Department,

Sri Manakula Vinayagar Engineering College, Puducherry, India.

R. Imtiaz,

Assistant Professor, ECE Department,

Sri Manakula Vinayagar Engineering College, Puducherry, India

AbstractFIR filters are used in digital signal processing. These filters are used as filtering unit for fixed and reconfigurable applications. This work proposes a multiple constant multiplication (MCM) method to reduce the area delay product (ADP) of the FIR filters that are used for fixed applications. The existing work comprises ripple carry adders that are used in adder unit, which consumes more area and delay. In order to overcome the drawbacks of existing work, the proposed work is designed which is based on modified ripple carry adders that are used in adder unit. The simulation is done using VHDL in Xilinx ISE 12.1.The parameters such as area, power and delay are compared with the existing MCM method.

Index TermsFinite Impulse Response (FIR)-Reconfigurable- Multiple Constant Multiplication (MCM)-adders

1. INTRODUCTION

   Digital filters plays major role in DSP, due to its advance performance is one of the key reasons that DSP has become so popular. Filters are used for two process, signal separation

   extracting common parts among the constants represented in canonic signed digit (CSD) . There are three different kinds of common subexpressions horizontal, vertical and oblique. Due to the computational complexity and the fact that linear phase FIR filters are symmetrical, the search for redundant computations in multiplier block is normally connected to horizontal common subexpressions. This paper proposes a combination of horizontal and vertical CSE. We have presented an improved horizontal and vertical CSE which is able to reduce the number of adders.

2. COMPUTATIONAL ANALYSIS AND MATHEMATICAL FORMULATION OF BLOCK

   TRANSPOSE FORM FIR FILTER

   The output of N length FIR filter can be computed using the relation

   1

   and signal restoration. Signal separation is needed when a signal have distorted with interference, noise, or other signals. Signal restoration is used when a signal has been distorted in some way. Digital filters can be implemented in two ways, by convolution (also called finite impulse response or FIR) and by recursion (also called infinite impulse response or IIR). Filters carried out by convolution have good performance

   than filters used in recursion, but execute much more slowly

   where,

   () = (). ( )

   =0

   y(n)-Filter output

   h (i)- Filter coefficient x(n)-Input

   (1)

   as the multiplicand has a limited number of values. From this reason, it is attractive to carry out the multiplication by using shifts and adds. The shifts can be realized by using hard- wired shifters and hence they are essentially free. Furthermore, we can reduce the area of adder by introducing common sub expression elimination CSE techniques. The CSE tackles the multiple constant multiplication (MCM) problem by minimizing the number of additions through

   The computation of (1) can be expressed by the recurrence relation

   Y(z) = [z1(··· (z1(z1h(N 1) + h(N 2))+ h(N 3))··· + h(1)) + h(0)]X(z) (2)

   The general block diagram of FIR filter is shown in figure 1

   Fig.1. Block Diagram of Finite Impulse response (FIR) Filter

3. MCM-Based Implementation of FIR Filter

   In FIR filter, the multiplication operation is performed between one common variable and many constants (the coefficients) and known as the multiple constant multiplication (MCM). The algorithms that are introduced before is to implement this MCM for an efficient FIR filter design can be categorized in two main groups: 1) graph based algorithms and 2) common sub-expression elimination (CSE) algorithms. Most of these graph based or CSE algorithms presented earlier are used to obtain efficient FIR filter architecture by running the algorithms on a particular set of coefficients for some time on a highly efficient computing platform.We discuss the derivation of MCM units for transpose form block FIR filter, and the design of proposed structure for fixed filters. For fixed-coefficient implementation, The general block diagram for MCM is given in figure 2.The proposed MCM structure is shown in figure

   Fig.2. Block Diagram of Multiple Constant Multiplications

   The multiplications are required to be mapped to the MCM units for a low-complexity realization. In the following, we show that the proposed formulation for MCM-based implementation of block FIR filter makes use of the symmetry in input matrix to perform horizontal and vertical common subexpression elimination and to minimize the number of shift-add operations in the MCM blocks. To illustrate the computation for L = 4 and N = 16. The input matrix contains six-input samples {x(4k), x(4k 1), x(4k 2), x(4k 3), x(4k 4), x(4k 5), x(4k 6)}, and multiplied with several constant coefficients, as shown in Table I. As shown in Table I, MCM can be used for both horizontal and vertical direction of the coefficient matrix. The sample x(4k3) appears in four rows or four columns of the following whereas x(4k) appears in only one row or one column.Therefore, all the four rows of coefficient matrix are

   involved in the MCM for the x(4k 3), whereas only the first row of coefficients are involved in the MCM for x(4k). For larger values of N or the smaller block sizes, the row size of the coefficient matrix is larger that results in larger MCM size across all the samples, which results into larger saving in computational complexity.

   Input sample	Coefficient Group
   X(4k)	{h(0),h(4),h(8),h(12)}
   X(4k-1)	{h(0),h(4),h(8),h(12)} {h(1),h(5),h(9),h(13)}
   X(4k-2)	{h(0),h(4),h(8),h(12)}
   	{h(1),h(5),h(9),h(13)}
   	{h(2),h(6),h(10),h(14)}
   X(4k-3)	{h(0),h(4),h(8),h(12)}
   	{h(1),h(5),h(9),h(13)}
   	{h(2),h(6),h(10),h(14)}
   	{h(3),h(7),h(11),h(15)}
   X(4k-4)	{h(1),h(5),h(9),h(13)}
   	{h(2),h(6),h(10),h(14)}
   	{h(3),h(7),h(11),h(15)}
   X(4k-5)	{h(2),h(6),h(10),h(14)} {h(3),h(7),h(11),h(15)}
   X(4k-6)	{h(3),h(7),h(11),h(15)}

   Table 1.Input Samples used for multiplication

4. PROPOSED MCM METHOD

   The proposed MCM-based structure for FIR filters for block size L = 4 is shown in Fig. 3 for the purpose of illustration. The MCM-based structure (shown in Fig. 3) involves six MCM blocks corresponding to six input samples. Each MCM block computes the necessary product terms as shown in Table I. The subexpressions of the MCM blocks are shift computed in the adder network to obtain the inner-product output (rl,m), for 0 l L 1 and 0 m (N/L) 1 corresponding to the matrix product of (14). The inner- product values are finally added in the PAU of to obtain a block of filter output.

   Fig 3.Proposed MCM structure

   1. Coefficient Storage Unit

      The Coefficient storage Unit consists of Read Only Memory (ROM) for storing the Fixed Coefficient Constants with Counter. The Counte architecture is used for to get the value from the ROM Memory.

   2. Register Unit

   The Register Unit consists of adders to add the given inputs; the Block diagram of Register unit is as shown in the figure.

   Fig.4: Block Diagram of Register Unit

   Fig.5:.Block Diagram of Inner Product Unit:

   The input which is given from the register unit is multiplied along with the coefficients inorder to get the output og the filter.The multiplication along with the addition is performed in the inner product unit which is shown in figure5 .Each inner product unit comprises of inner product cell which is shown in figure 6

   Fig.6. Block diagram of Inner Product Cell Unit

   Each IPU is comprised of L Inner Product (IP) cells shown in figure 6, where each IP cell involves L multipliers and (L1) adders. The Register Unit involves (L 1) registers of B-bit width. The Pipeline Adder Unit involves L (M1) adders and the same number of registers, where each register has a width of (B+B-), B+, and B- respectively, being the bit width of input sample and filter coefficients. Therefore, the proposed structure involves LN multipliers, L (N 1) adders, and [B (N

   1) + B (N L)] (flip flops) FFs; and processes L samples in every cycle where the duration of cycle period T = [TM + TA

   + TFA (log2 L)].We do not find a multiplier-based direct- form block Finite Impulse Response (FIR) structure on RFIR in the literature. However, direct-form multiplier-based block FIR structure can be derived from the block formulation Finite Impulse Response (FIR) .We have derived the direct- form block Finite Impulse Response (FIR) structure, and estimated its hardware and time complexities for comparison purpose.

   C .Modified Ripple carry adder

   The Proposed system is consists of Adder architecture in the Pipeline adder unit with carry look ahead generator adder architecture and with modified Ripple carry adder. The analysis is performed between these two architectures and we find out the Area, Delay and Power of Field Programmable Gate Array(FPGA) spartan-3E is used and their values for the corresponding Field Programmable Gate Array(FPGA) can be Determined and tabulated in table-II. Software used for simulation and synthesis is Xilinx ISE 12.1 respectively in this project.

   Fig.7. Block diagram of Modified Ripple carry adder architecture used in adder unit

   	Slices	LUT	Delay (ns)	Power (W)
   Existing System	120	152	2.353	0.328
   Proposed System	131	163	2.202	0.270

   Table II Comparison of area, power and delay

   Existing MCM method

   Proposed MCM method

   Existing MCM method

   Proposed MCM method

   2.4

   2.35

   2.3

   2.25

   2.2

   2.15

   2.1

   2.4

   2.35

   2.3

   2.25

   2.2

   2.15

   2.1

   Fig.11. Comparison chart of Delay values for Existing and Proposed system architectures

   Fig.8. Output screenshot showing the Delay values for the proposed system architecture

   0.4

   0.35

   0.3

   0.25

   0.2

   0.15

   0.1

   0.05

   0

   Existing MCM method Proposed MCM method

   Fig.12. Graph Showing the Results for Power values for Existing and Proposed system architectures

   Fig 9.Comparison for power

   180

   160

   140

   120

   100

   80

   60

   40

   20

   0

   Existing MCM method

   Proposed MCM method

   180

   160

   140

   120

   100

   80

   60

   40

   20

   0

   Existing MCM method

   Proposed MCM method

   Slices LUT

   Slices LUT

   Fig .10. Comparison chart of area for existing and proposed work

   1. Advantages

      • Low power

      • Less delay

   2. Applications

      • Filtering unit

      • Radar

      • Microcontroller

5. CONCLUSION

From the Results Tabulated in Table-II it shows that even though the Adder architectures are changed, the MCM Method of FIR Filter architecture is having Low Power and Less Delay. The conclusion is incurred from the results.

AUTHOR

M.Manoj completed his B.Tech in Electronics and Communication Engineering from Krishnasamy College of Engineering and Technology, Cuddalore in 2013. He is now pursuing his Master of Technology (M.Tech) in VLSI & Embedded Systems at Sri Manakula Vinayagar Engineering College, Puducherry, India.

ACKNOWLEDGMENT

I would like to thank Mr. R. Imtiaz, Assistant professor ECE department, SMVEC for guiding me throughout the project. He has given me technical support and helped me to finish the project successfully.

REFERENCES

1. Kumar Mohanty and Pramod K. Meher., High Performance FIR Filter Architecture for Fixed and Reconfigurable Applications in IEEE Trans.on VLSI , vol PP

   ,issue 99, April 2015.

2. Mr.K.Anandan and N.S.Yogaananth., VLSI Implementation of Reconfigurable Low Power Fir Filter Architecture in International Journal of Innovative Research in Computer and Communication Engineering, vol.2, issue 1, pp 3514-3520, March 2014.

3. Miodrag potkonjak, Mani.B.S. and Anantha.P.C.,Multiple constant multiplications efficient and versatile framework and algorithms for exploring common subexpression elimination IEEE Trans. Computer Aided-Design of Integrated Circuits and Systems, VOL.15,NO.2, pp 151-165, 1996.

4. Yuen H.A.H., Chi U.L., Hing-K.K.,Ngai Wong, Global optimization of common subexpressions for multiplierless synthesis of multiple constant multiplications IEEE Explore,pp.119-124, 2008.

5. Levent Aksoy, Eduardo.D.Costa, Paulo Flores, José Monteiro., Exact and approximate algorithms for the optimization of area and delay in multiple constant multiplications IEEE Transactions on Computer-Aided Design of Integrated Circuits And Systems, Vol. 27, No. 6, pp. 1013-1026, 2008

6. .R. Hartley, Subexpression sharing in filters using canonic signed digit multipliers, IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 43, no. 10,pp. 677688, Oct. 1996.

7. I.-C. Park and H.-J. Kang, Digital filter synthesis based on minimal signed digit representation, in Proc. DAC, pp. 468 473, 2001.

8. Dempster, M. Macleod, Use of minimum-adder multiplier blocks in FIR digital filters, IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 42, no. 9, pp. 569577, Sep. 1995.

9. Kenny Johansson, Oscar Gustafsson, Andrew G. D., and Lars Wanhammar, Algorithm to reduce the number of shifts and additions in multiplier blocks using serial arithmetic IEEE MELECON, pp. 197-200, 2004.

10. Levent Aksoy,Cristiano Lazzari, Eduardo Costa,Paulo Flores, José Monteiro., Efficient shift-adds design of digit-serial multiple constant multiplications GLSVLSI11,2011.