Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-02-06T07:50:06.475Z Has data issue: false hasContentIssue false

7 - Linear systems

Published online by Cambridge University Press:  03 May 2010

Ryan Kastner ,
Anup Hosangadi  and
Farzan Fallah
Ryan Kastner
Affiliation:
University of California, San Diego
Anup Hosangadi
Affiliation:
University of California, Santa Barbara
Farzan Fallah
Affiliation:
Stanford University, California
Get access

Summary

Chapter overview

This chapter provides a thorough discussion of the issues surrounding the optimization of linear systems. Section 7.2 describes fundamental properties, and presents a list of common linear transforms. Then, Section 7.3 formalizes the problem. Sections 7.4 and 7.5 introduce two important cases of linear system optimization, namely single- and multiple-constant multiplication. While the algorithms to solve these problems are important, they do not fully take advantage of the solution space; thus, they may lead to inferior results. Section 7.6 describes the relationship of these two problems to the linear system optimization problem and provides an overview of techniques used to optimize linear systems. Section 7.7 presents a transformation from a linear system into a set of polynomial expressions. The algorithms presented later in the chapter use this transformation during optimization. Section 7.8 describes an algorithm for optimizing expressions for synthesis using two-operand adders. The results in Section 7.9 describe the synthesis of high-speed FIR filters using this two-operand optimization along with other common techniques for FIR filter synthesis. Then, Section 7.10 focuses on more complex architectures, in particular, those using three-operand adders, and shows how CSAs can speed up the calculation of linear systems. Section 7.11 discusses how to consider timing constraints by modifying the previously presented optimization techniques. Specifically, the section describes ideas for performing delay aware optimization.

Type
Chapter
Information
Arithmetic Optimization Techniques for Hardware and Software Design , pp. 126 - 181
Publisher: Cambridge University Press
Print publication year: 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Schneider, P. J. and Eberly, D. H., Geometric Tools for Computer Graphics, New York, NY: Elsevier Science Inc.
Tolimieri, R., An, M., and Lu, C., Algorithms for Discrete Fourier Transforms and Convolution. New York, NY: Springer, 1997.CrossRefGoogle Scholar
Beauchamp, K., Applications of Walsh and Related Functions. New York, NY: Academic Press, 1984.Google Scholar
Bergland, G. D., A fast Fourier transform algorithm for real-valued series, Communications of the ACM, 11(10), 703–10, 1968.CrossRefGoogle Scholar
Bracewell, R. N., Discrete Hartley transform, Journal of the Optical Society of America, 73(12), 1832–5, 1983.CrossRefGoogle Scholar
Rao, K. R. and Yip, P., Discrete Cosine Transform: Algorithms, Advantages, Applications. New York, NY: Academic Press Professional, Inc., 1990.CrossRefGoogle Scholar
Martucci, S. A., Symmetric convolution and the discrete sine and cosine transforms, IEEE Transactions on Signal Processing, 42(5), 1038–51, 1994.CrossRefGoogle Scholar
Henrique, S. M., Signal Processing with Lapped Transforms. Norwood, MA: Artech House, Inc., 1992.Google Scholar
Rabiner, L. R. and Gold, B., Theory and Application of Digital Signal Processing, Englewood Cliffs, NJ: Prentice-Hall, Inc., 1975.Google Scholar
Vetterli, M. and Kovačević, J., Wavelets and Subband Coding. Upper Sadde River, NJ: Prentice-Hall, Inc., 1995.Google Scholar
JPEG Standard (JPEG ISO/IEC 10918–1 ITU-T Recommendation T.81). http://www.itu.int/rec/T-REC-T.81/en
Richardson, I. E. G., H.264 and MPEG-4 Video Compression, John Wiley and Sons, 2003.
Cappello, P. and Steiglitz, K., Some complexity issues in digital signal processing, IEEE Transactions on Acoustics, Speech and Signal Processing, 32(5) 1037–41, 1984.CrossRefGoogle Scholar
Knuth, D. E., The Art of Computer Programming, Vol. 2, Seminumerical Algorithms. Reading, MA: Addison Wesly, 1997.Google Scholar
Huapeng, W. and Hasan, M. A., Closed-form expression for the average weight of signed-digit representations, IEEE Transactions on Computers, 48(8), 848–51, 1999.CrossRefGoogle Scholar
,Synopsys Datasheet, Design Compiler Ultra-Design Compiler® at its Best, http://www.synopsys.com
,TSMC Design Document, TSMC 90 nm Technology Platform, http://www.tsmc.com
Dempster, A. G. and Macleod, M. D., Constant integer multiplication using minimum adders, IEE Proceedings on Circuits, Devices and Systems, 141(5), 407–13, 1994.CrossRefGoogle Scholar
Gustafsson, O., Dempster, A. G., and Wanhammar, L., Extended results for minimum-adder constant integer multipliers, IEEE International Symposium on Circuits and Systems, 2002, Vol. 1, pp. I-73–I-76. Washington, DC: IEEE Computer Society, 2002.Google Scholar
Voronenko, Y. and Puschel, M., Multiplierless multiple constant multiplication, ACM Transactions on Algorithms, 3(2), 11, 2007.CrossRefGoogle Scholar
Ercegovac, M. D. and Lang, T., Digital Arithmetic. San Francisco, CA: Morgan Kaufmann Publishers, 2004.Google Scholar
Coleman, J. O., Cascaded coefficient number systems lead to FIR filters of striking computational efficiency, International IEEE Conference in Electronics, Circuits and Systems, 2001. Washington, DC: IEEE Computer Society, 2001.Google Scholar
Muchnick, S. S., Advanced Compiler Design and Implementation, San Francisco, CA:Morgan Kaufmann Publishers, 1997.Google Scholar
Briggs, P., Cooper, K. D., and Simpson, L. T., Value numbering, Software – Practice and Experience, 27(6), 701–24, 1997.3.0.CO;2-0>CrossRefGoogle Scholar
Sethi, R. and Ullman, J. D., The generation of optimal code for arithmetic expressions, Journal of the ACM, 17(4), 715–28, 1970.CrossRefGoogle Scholar
McKeeman, W. M., Peephole optimization, Communications of the ACM, 8(7), 443–4, 1965.CrossRefGoogle Scholar
Tanenbaum, A. S., Straven, H., and Stevenson, J. W., Using peephole optimization on intermediate code, ACM Transactions on Programming Languages & Systems, 4(1), 21–36, 1982.CrossRefGoogle Scholar
Fischer, C. N. and LeBlanc, R. J. Jr., Crafting a Compiler, Menlo Park, CA: Benjamin/Cummings, 1991.Google Scholar
Briggs, P. and Cooper, K. D., Effective partial redundancy elimination, Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, 1994, pp. 159–70. New York, NY: ACM, 1994.CrossRefGoogle Scholar
Aho, A. V., Johnson, S. C., and Ullman, J. D., Code generation for expressions with common subexpressions, Journal of The ACM, 24(1), 146–60, 1977.CrossRefGoogle Scholar
Potkonjak, M., Srivastava, M. B., and Chandrakasan, A. P., Multiple constant multiplications: efficient and versatile framework and algorithms for exploring common subexpression elimination, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 15(2), 151–65, 1996.CrossRefGoogle Scholar
Mehendale, M., Sherlekar, S. D., and Venkatesh, G., Synthesis of multiplier-less FIR filters with minimum number of additions, International Conference on Computer-Aided Design, San Jose, 1995, pp. 668–71. Washington, DC: IEEE Computer Society, 1995.Google Scholar
Hartley, R. I., Subexpression sharing in filters using canonic signed digit multipliers, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 43(10) 677–88, 1996.CrossRefGoogle Scholar
Pasko, R., Schaumont, P., Derudder, V., Vernalde, V., and Durackova, D., A new algorithm for elimination of common subexpressions, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 18(1), 58–68, 1999.CrossRefGoogle Scholar
Park, I.-C. and Kang, H.-J., Digital filter synthesis based on an algorithm to generate all minimal signed digit representations, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 21, 1525–9, 2002.CrossRefGoogle Scholar
Dempster, A. G. and Macleod, M. D., Using all signed-digit representations to design single integer multipliers using subexpression elimination, IEEE Symposium on Circuits and Systems, Vancouver, 2004. Washington, DC: IEEE Computer Society, 2004.Google Scholar
Garey, M. R. and Johnson, D. S., Computers and Intractability: a Guide to the Theory of NP-completeness, San Francisco, CA: W. H. Freeman, 1979.Google Scholar
Bull, D. R. and Horrocks, D. H., Primitive operator digital filters, IEE Proceedings on Circuits, Devices and Systems, 138(3), 401–12, 1991.CrossRefGoogle Scholar
Dempster, A. G. and Macleod, M. D., Use of minimum-adder multiplier blocks in FIR digital filters, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 42(9), 569–77, 1995.CrossRefGoogle Scholar
Bernstein, R. L., Multiplication by integer constants, Software – Practice and Experience, 16(7), 641–52, 1986.CrossRefGoogle Scholar
Zimmermann, R. and Tran, D. Q., Optimized synthesis of sum-of-products, Asilomar Conference on Signals, Systems and Computers, Pacific Grove, 2003. Washington, DC: IEEE Computer Society, 2003.Google Scholar
Chatterjee, A., Roy, R. K., and d'Abreu, M. A., Greedy hardware optimization for linear digital systems using number splitting and repeated factorization, IEEE Transaction on Very Large Scale Integrated Systems, 1, 423–31, 1993.CrossRefGoogle Scholar
Nguyen, H. T. and Chatterjee, A., Number-splitting with shift-and-add decomposition for power and hardware optimization in linear DSP synthesis, IEEE Transactions on Very Large Scale Integrated Systems, 15(2), 419–24, 2000.CrossRefGoogle Scholar
Huy, N. and Chatterjee, A., OPTIMUS: a new program for OPTIMizing linear circuits with number-splitting and shift-and-add decompositions, Conference on Advanced Research in VLSI, Chapel Hill, 1995, pp. 258–71. Washington, DC: IEEE Computer Society, 1995.Google Scholar
Malvar, H. S., Hallapuro, A., Karczewicz, M. and Kerofsky, L., Low-complexity transform and quantization in H.264/AVC, IEEE Transactions on Circuits and Systems for Video Technology, 13(7), 598–603, 2003.CrossRefGoogle Scholar
Wiegand, T., Sullivan, G. J., Bjontegaard, G.et al., Overview of the H.264/AVC video coding standard, IEEE Transactions on Circuits and Systems for Video Technology, 13(7), 560–76, 2003.CrossRefGoogle Scholar
Brayton, R. K., Sangiovanni-Vincentelli, A. L., McMullen, C. T., and Hachtel, G. D., Logic Minimization Algorithms for VLSI Synthesis. Norwell, MA: Kluwer Academic Publishers, 1984.CrossRefGoogle Scholar
Vasudevamurthy, J. and Rajski, J., A method for concurrent decomposition and factorization of Boolean expressions, Proceedings of the IEEE International Conference on Computer-Aided Design, Santa Clara, 1990, pp. 510–13. Washington DC: IEEE Computer Society, 1990.Google Scholar
http://www.xilinx.com/ipcenter/catalog/logicore/docs/ram_shift.pdf
Xilinx Inc., Virtex II Platform FPGA Handbook, 2000.
Xilinx Inc., Virtex-4 Handbook, 2004.
Weste, N. and Harris, D., CMOS VLSI Design – A Circuits and Systems Perspective, 3rd edn. Boston, MA: Addison Wesley Publishing Company, 2004.Google Scholar
Park, I.-C. and Kang, H.-J., Digital filter synthesis based on an algorithm to generate all minimal signed digit representations, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21, 1525–9, (2002).CrossRefGoogle Scholar
Um, J., Kim, T., and Liu, C. L., A fine-grained arithmetic optimization technique for high-performance low-power data path synthesis, Proceedings of the 37th Design Automation Conference (DAC), pp. 98–103. New York, NY: ACM, 2000.CrossRefGoogle Scholar
Micheli, G. D., Synthesis and optimization of digital circuits, first edition, Boston, MA: McGraw-Hill Higher Education, 1994.Google Scholar
Um, J. and Kim, T., Layout-aware synthesis of arithmetic circuits, Proceedings of the 39th Design Automation Conference (DAC) pp. 207–12. New York, NY: ACM, 2002.Google Scholar
Dempster, A. G. and Macleod, M. D., Use of minimum-adder multiplier blocks in FIR digital filters, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 42, 569–77, 1995.CrossRefGoogle Scholar
Noll, T. G., Carry-save arithmetic for high-speed digital signal processing, Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 982–6. Washington, DC: IEEE, 1990.CrossRefGoogle Scholar
Gustaffson, O., Dempster, A. G., and Walhammar, L., Extended results for minimum-adder constant integer multipliers, Proceedings of the IEEE International Symposium on Circuits and Systems, 2002, Vol. 1, I-73–I-76. Washington, DC: IEEE, 2002.Google Scholar
SMPTE 421M, VC-1 Compressed Video Bitstream Format and Decoding Process. http://www.smpte.org

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • Linear systems
  • Ryan Kastner, University of California, San Diego, Anup Hosangadi, University of California, Santa Barbara, Farzan Fallah, Stanford University, California
  • Book: Arithmetic Optimization Techniques for Hardware and Software Design
  • Online publication: 03 May 2010
  • Chapter DOI: https://doi.org/10.1017/CBO9780511712180.008
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • Linear systems
  • Ryan Kastner, University of California, San Diego, Anup Hosangadi, University of California, Santa Barbara, Farzan Fallah, Stanford University, California
  • Book: Arithmetic Optimization Techniques for Hardware and Software Design
  • Online publication: 03 May 2010
  • Chapter DOI: https://doi.org/10.1017/CBO9780511712180.008
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • Linear systems
  • Ryan Kastner, University of California, San Diego, Anup Hosangadi, University of California, Santa Barbara, Farzan Fallah, Stanford University, California
  • Book: Arithmetic Optimization Techniques for Hardware and Software Design
  • Online publication: 03 May 2010
  • Chapter DOI: https://doi.org/10.1017/CBO9780511712180.008
Available formats
×