Design of Efficient Graph Based Algorithm With Modified Carry save Adder

International Journal of Mechanical Engineering

© 2014 by SSRG - IJME Journal

Volume 1 Issue 1

Year of Publication : 2014

Authors : Mr.M.Sivakumar, Mr.R.Seshadri, Dr.S.Ramakrishnan

10.14445/23488360/IJME-V1I1P102

How to Cite?

Mr.M.Sivakumar, Mr.R.Seshadri, Dr.S.Ramakrishnan, "Design of Efficient Graph Based Algorithm With Modified Carry save Adder," SSRG International Journal of Mechanical Engineering, vol. 1,  no. 1, pp. 6-11, 2014. Crossref, https://doi.org/10.14445/23488360/IJME-V1I1P102

Abstract:

In the field of digital signal processing, many well-organized algorithms and architectures are introduced for the design of low complexity bit parallel multiple constant multiplication (MCM) operation which take over the complica-tion of many digital signal processing systems. Little courtesy has been given to the digit serial MCM intention. In this paper we discourse the difficulty of optimizing the gate level delay in digit serial MCM designs by modifying the carry save adder and implementing it to the graph based (GB) algorithm. Here delay and power can be highly reduced albeit at the cost of an increased area. Experimental effects show the capability of the proposed optimization algorithms and of the digit-serial MCM architectures in the design of digit-serial MCM operations and finite impulse response filters. The proposed method reduces the delay to achieve higher speed than the existing method.

Keywords:

Graph based (GB) algorithm, modified carry save adder (MCSA), finite impulse response (FIR) filters, gate-level delay optimization, multiple constant multiplications.

References:

[1]    A. Dempster and M. Macleod, “Use of minimum-adder multiplier blocks in FIR digital filters,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 42, no. 9, pp. 569–577, Sep. 1995.
[2]    C. Wallace, “A suggestion for a fast multiplier,” IEEE Trans. Electron. Compute., vol. 13, no. 1, pp. 14–17, Feb. 1964.
[3]    H. Nguyen and A. Chatterjee, “Number-splitting with shift-and-add decomposition for power and hardware optimization in linear DSP synthesis,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 8, no. 4, pp. 419–424, Aug. 2000.
[4]    I.-C. Park and H.-J. Kang, “Digital filter synthesis based on minimal signed digit representation,” in Proc. DAC, 2001.
[5]    K. Parhi, “A systematic approach for design of digit-serial signal processing architectures,” IEEE Trans. Circuits Syst., vol. 38, no. 4, pp. 358–375, Apr. 1991.
[6]    L. Aksoy, E. Costa, P. Flores, and J. Monteiro, “Optimization of area in digital FIR filters using gate-level metrics,” in Proc. DAC, 2007, pp. 420–423.
[7]    L. Aksoy, E. Costa, P. Flores, and J. Monteiro, “Exact and approximate algorithms for the optimization of area and delay in multiple constant multiplications,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 27, no. 6, pp. 1013–1026, Jun. 2008.
[8]    L. Aksoy, E. Gunes, and P. Flores, “Search algorithms for the multiple constant multiplications problem: Exact and approximate,” J. Microprocess. Microsyst., vol. 34, no. 5, pp. 151–162, Aug. 2010.
[9]    L. Aksoy, C. Lazzari, E. Costa, P. Flores, and J. Monteiro, “Efficient shift-adds design of digit-serial multiple constant multiplications,” in Proc. Great Lakes Symp. VLSI, 2011, pp. 61–66.
[10]    M. Ercegovac and T. Lang, Digital Arithmetic. San Mateo, CA: Morgan Kaufmann, 2003.
[11]    P. Barth, “A Davis-Putnam based enumeration algorithm for linear pseudo-Boolean optimization,” Max-Planck-Institut für Informatik, Saarbrücken, Germany, Tech. Rep. MPI-I-95-2-003, 1995.
[12]    P. Flores, J. Monteiro, and E. Costa, “An exact algorithm for the maximal sharing of partial terms in multiple constant multiplications,” in Proc. Int. Conf. Comput.-Aided Design, Nov. 2005, pp. 13–16.
[13]    R. Hartley, “Subexpression sharing in filters using canonic signed digit multipliers,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 43, no. 10, pp. 677–688, Oct. 1996.
[14]    T. Larrabee, “Test pattern generation using Boolean satisfiability,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 11, no. 1, pp. 4–15, Jan. 1992.
[15]    Y.-H. Ho, C.-U. Lei, H.-K. Kwan, and N. Wong, “Global optimization of common subexpressions for multiplierless synthesis of multiple constant multiplications,” in Proc. ASPDAC, 2008, pp. 119–124.
[16]    Levent aksoy, Cristiano lazzari, “Design of digit-serial FIR filters: Algorithm, Architectures, and a CAD tool,” IEEE Trans. On very large scale integration (VLSI) systems, vol.21. No.3,march 2013.