Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Computational and Implementation Complexity of Polynomial Evaluation Schemes
Linköping University, Department of Electrical Engineering, Electronics System. Linköping University, The Institute of Technology.
Linköping University, Department of Electrical Engineering, Electronics System. Linköping University, The Institute of Technology.ORCID iD: 0000-0003-3470-3911
2011 (English)In: Proceedings of NORCHIP, 2011 Date:14-15 Nov. 2011, IEEE conference proceedings, 2011, 1-6 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this work, we consider the computational complexity of different polynomial evaluation schemes. By considering the number of operations of different types, critical path, pipelining complexity, and latency after pipelining, high-level comparisons are obtained. These can then be used to short list suitable candidates for an implementation given the specifications. Not only multiplications are considered, but they are divided into data-data multiplications, squarers, and data-coefficient multiplications, as the latter can be optimized depending on implementation architecture and application.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2011. 1-6 p.
Keyword [en]
Adders, Computer architecture, Delay, Filtering algorithms, ISO, Pipeline processing, Polynomials
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-73935DOI: 10.1109/NORCHP.2011.6126735ISBN: 978-1-4577-0515-1 (print)ISBN: 978-1-4577-0514-4 (print)OAI: oai:DiVA.org:liu-73935DiVA: diva2:478816
Conference
NORCHIP 2011. The Nordic Microelectronics event, 29th Norchip Conference 14-15 November 2011, Lund, Sweden
Available from: 2012-01-17 Created: 2012-01-17 Last updated: 2015-03-11Bibliographically approved
In thesis
1. On the Implementation of Integer and Non-Integer Sampling Rate Conversion
Open this publication in new window or tab >>On the Implementation of Integer and Non-Integer Sampling Rate Conversion
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The main focus in this thesis is on the aspects related to the implementation of integer and non-integer sampling rate conversion (SRC). SRC is used in many communication and signal processing applications where two signals or systems having different sampling rates need to be interconnected. There are two basic approaches to deal with this problem. The first is to convert the signal to analog and then re-sample it at the desired rate. In the second approach, digital signal processing techniques are utilized to compute values of the new samples from the existing ones. The former approach is hardly used since the latter one introduces less noise and distortion. However, the implementation complexity for the second approach varies for different types of conversion factors. In this work, the second approach for SRC is considered and its implementation details are explored. The conversion factor in general can be an integer, a ratio of two integers, or an irrational number. The SRC by an irrational numbers is impractical and is generally stated for the completeness. They are usually approximated by some rational factor.

The performance of decimators and interpolators is mainly determined by the filters, which are there to suppress aliasing effects or removing unwanted images. There are many approaches for the implementation of decimation and interpolation filters, and cascaded integrator comb (CIC) filters are one of them. CIC filters are most commonly used in the case of integer sampling rate conversions and often preferred due to their simplicity, hardware efficiency, and relatively good anti-aliasing (anti-imaging) characteristics for the first (last) stage of a decimation (interpolation). The multiplierless nature, which generally yields to low power consumption, makes CIC filters well suited for performing conversion at higher rate. Since these filters operate at the maximum sampling frequency, therefore, are critical with respect to power consumption. It is therefore necessary to have an accurate and efficient ways and approaches that could be utilized to estimate the power consumption and the important factors that are contributing to it. Switching activity is one such factor. To have a high-level estimate of dynamic power consumption, switching activity equations in CIC filters are derived, which may then be used to have an estimate of the dynamic power consumption. The modeling of leakage power is also included, which is an important parameter to consider since the input sampling rate may differ several orders of magnitude. These power estimates at higher level can then be used as a feed-back while exploring multiple alternatives.

Sampling rate conversion is a typical example where it is required to determine the values between existing samples. The computation of a value between existing samples can alternatively be regarded as delaying the underlying signal by a fractional sampling period. The fractional-delay filters are used in this context to provide a fractional-delay adjustable to any desired value and are therefore suitable for both integer and non-integer factors. The structure that is used in the efficient implementation of a fractional-delay filter is know as Farrow structure or its modifications. The main advantage of the Farrow structure lies in the fact that it consists of fixed finite-impulse response (FIR) filters and there is only one adjustable fractional-delay parameter, used to evaluate a polynomial with the filter outputs as coefficients. This characteristic of the Farrow structure makes it a very attractive structure for the implementation. In the considered fixed-point implementation of the Farrow structure, closed-form expressions for suitable word lengths are derived based on scaling and round-off noise. Since multipliers share major portion of the total power consumption, a matrix-vector multiple constant multiplication approach is proposed to improve the multiplierless implementation of FIR sub-filters.

The implementation of the polynomial part of the Farrow structure is investigated by considering the computational complexity of different polynomial evaluation schemes. By considering the number of operations of different types, critical path, pipelining complexity, and latency after pipelining, high-level comparisons are obtained and used to short list the suitable candidates. Most of these evaluation schemes require the explicit computation of higher order power terms. In the parallel evaluation of powers, redundancy in computations is removed by exploiting any possible sharing at word level and also at bit level. As a part of this, since exponents are additive under multiplication, an ILP formulation for the minimum addition sequence problem is proposed.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2012. 65 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1420
National Category
Signal Processing
Identifiers
urn:nbn:se:liu:diva-73722 (URN)978-91-7519-980-1 (ISBN)
Public defence
2012-02-09, Visionen, B-building, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2012-01-17 Created: 2012-01-12 Last updated: 2015-03-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Abbas, MuhammadGustafsson, Oscar
By organisation
Electronics SystemThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 904 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf