liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Low Power and Low Complexity Shift-and-Add Based Computations
Linköping University, Department of Electrical Engineering, Electronics System. Linköping University, The Institute of Technology.
2008 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

The main issue in this thesis is to minimize the energy consumption per operation for the arithmetic parts of DSP circuits, such as digital filters. More specific, the focus is on single- and multiple-constant multiplications, which are realized using shift-and-add based computations. The possibilities to reduce the complexity, i.e., the chip area, and the energy consumption are investigated. Both serial and parallel arithmetic are considered. The main difference, which is of interest here, is that shift operations in serial arithmetic require flip-flops, while shifts can be hardwired in parallel arithmetic.The possible ways to connect a given number of adders is limited. Thus, for single-constant multiplication, the number of shift-and-add structures is finite. We show that it is possible to save both adders and shifts compared to traditional multipliers. Two algorithms for multiple-constant multiplication using serial arithmetic are proposed. For both algorithms, the total complexity is decreased compared to one of the best-known algorithms designed for parallel arithmetic. Furthermore, the impact of the digit-size, i.e., the number of bits to be processed in parallel, is studied for FIR filters implemented using serial arithmetic. Case studies indicate that the minimum energy consumption per sample is often obtained for a digit-size of around four bits.The energy consumption is proportional to the switching activity, i.e., the average number of transitions between the two logic levels per clock cycle. To achieve low power designs, it is necessary to develop accurate high-level models that can be used to estimate the switching activity. A method for computing the switching activity in bit-serial constant multipliers is proposed.For parallel arithmetic, a detailed complexity model for constant multiplication is introduced. The model counts the required number of full and half adder cells. It is shown that the complexity can be significantly reduced by considering the interconnection between the adders. A main factor for energy consumption in constant multipliers is the adder depth, i.e., the number of cascaded adders. The reason for this is that the switching activity will increase when glitches are propagated to subsequent adders. We propose an algorithm, where all multiplier coefficients are guaranteed to be realized at the theoretically lowest depth possible. Implementation examples show that the energy consumption is significantly reduced using this algorithm compared to solutions with fewer word level adders.For most applications, the input data are correlated since real world signals are processed. A data dependent switching activity model is derived for ripple-carry adders. Furthermore, a switching activity model for the single adder multiplier is proposed. This is a good starting point for accurate modeling of shift-and-add based computations using more adders.Finally, a method to rewrite an arbitrary function as a sum of weighted bit-products is presented. It is shown that for many elementary functions, a majority of the bit-products can be neglected while still maintaining reasonable high accuracy, since the weights are significantly smaller than the allowed error. The function approximation algorithms can be implemented using a low complexity architecture, which can easily be pipelined to an arbitrary degree for increased throughput.

Place, publisher, year, edition, pages
Linköping University: Linköping University Electronic Press , 2008. , 268 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1201
Keyword [en]
FIR filters, Function approximation, Digital circuits, Computer arithmetic, Constant multiplication, Addition, Low power, Switching activity estimation
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering
URN: urn:nbn:se:liu:diva-12576ISBN: 978-91-7393-836-5OAI: diva2:1733
Public defence
2008-10-03, Visionen, Hus B, Campus Valla, Linköping University, Linköping, 13:15 (English)
Available from: 2008-09-17 Created: 2008-09-15 Last updated: 2015-03-11Bibliographically approved

Open Access in DiVA

fulltext(1904 kB)3008 downloads
File information
File name FULLTEXT02.pdfFile size 1904 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(53 kB)82 downloads
File information
File name COVER02.pdfFile size 53 kBChecksum SHA-512
Type coverMimetype application/pdf

Search in DiVA

By author/editor
Johansson, Kenny
By organisation
Electronics SystemThe Institute of Technology
Other Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 3008 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 3609 hits
ReferencesLink to record
Permanent link

Direct link