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
Low-Complexity Multiplierless Constant Rotators Based on Combined Coefficient Selection and Shift-and-Add Implementation (CCSSI)
Linköping University, Department of Electrical Engineering, Computer Engineering. Linköping University, The Institute of Technology.
Linköping University, Department of Electrical Engineering, Electronics System. Linköping University, The Institute of Technology.
Linköping University, Department of Electrical Engineering, Computer Engineering. Linköping University, The Institute of Technology.ORCID iD: 0000-0003-3470-3911
2014 (English)In: IEEE Transactions on Circuits and Systems Part 1: Regular Papers, ISSN 1549-8328, E-ISSN 1558-0806, Vol. 61, no 7, 2002-2012 p.Article in journal (Refereed) Published
Abstract [en]

This paper presents a new approach to design multiplierless constant rotators. The approach is based on a combined coefficient selection and shift-and-add implementation (CCSSI) for the design of the rotators. First, complete freedom is given to the selection of the coefficients, i.e., no constraints to the coefficients are set in advance and all the alternatives are taken into account. Second, the shift-and-add implementation uses advanced single constant multiplication (SCM) and multiple constant multiplication (MCM) techniques that lead to low-complexity multiplierless implementations. Third, the design of the rotators is done by a joint optimization of the coefficient selection and shift-and-add implementation. As a result, the CCSSI provides an extended design space that offers a larger number of alternatives with respect to previous works. Furthermore, the design space is explored in a simple and efficient way. The proposed approach has wide applications in numerous hardware scenarios. This includes rotations by single or multiple angles, rotators in single or multiple branches, and different scaling of the outputs. Experimental results for various scenarios are provided. In all of them, the proposed approach achieves significant improvements with respect to state of the art.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE) , 2014. Vol. 61, no 7, 2002-2012 p.
Keyword [en]
Adder minimization; combined coefficient selection and shift-and-add implementation (CCSSI); complex multiplier; fast Fourier transform; multiple constant multiplication (MCM); rotation; shift-and-add
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:liu:diva-109385DOI: 10.1109/TCSI.2014.2304664ISI: 000339045500010OAI: oai:DiVA.org:liu-109385DiVA: diva2:738039
Available from: 2014-08-15 Created: 2014-08-15 Last updated: 2017-12-05Bibliographically approved
In thesis
1. Optimization of Rotations in FFTs
Open this publication in new window or tab >>Optimization of Rotations in FFTs
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The aims of this thesis are to reduce the complexity and increasethe accuracy of rotations carried out inthe fast Fourier transform (FFT) at algorithmic and arithmetic level.In FFT algorithms, rotations appear after every hardware stage, which are alsoreferred to as twiddle factor multiplications.

At algorithmic level, the focus is on the development and analysisof FFT algorithms. With this goal, a new approach based on binary tree decompositionis proposed. It uses the Cooley Tukey algorithm to generate a large number ofFFT algorithms. These FFT algorithms have identical butterfly operations and data flow but differ inthe value of the rotations. Along with this, a technique for computing the indices of the twiddle factors based on the binary tree representation has been proposed. We have analyzed thealgorithms in terms of switching activity, coefficient memory size, number of non-trivial multiplicationsand round-off noise. These parameters have impact on the power consumption, area, and accuracy of the architecture.Furthermore, we have analyzed some specific cases in more detail for subsets of the generated algorithms.

At arithmetic level, the focus is on the hardware implementation of the rotations.These can be implemented using a complex multiplier,the CORDIC algorithm, and constant multiplications. Architectures based on the CORDIC and constant multiplication use shift and add operations, whereas the complex multiplication generally uses four real multiplications and two adders.The sine and cosine coefficients of the rotation angles fora complex multiplier are normally stored in a memory.The implementation of the coefficient memory is analyzed and the best possible approaches are analyzed.Furthermore, a number of twiddle factor multiplication architectures based on constant multiplications is investigated and proposed. In the first approach, the number of twiddle factor coefficients is reduced by trigonometric identities. By considering the addition aware quantization method, the accuracy and adder count of the coefficients are improved. A second architecture based on scaling the rotations such that they no longer have unity gain is proposed. This results in twiddle factor multipliers with even lower complexity and/or higher accuracy compared to the first proposed architecture.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2012. 49 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1423
Keyword
Discrete Fourier transform, Fast Fourier transform, twiddle factor multiplication
National Category
Signal Processing
Identifiers
urn:nbn:se:liu:diva-74702 (URN)978-91-7519-973-3 (ISBN)
Public defence
2012-03-01, Visionen, B-huset, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2012-02-07 Created: 2012-02-05 Last updated: 2017-06-12Bibliographically approved

Open Access in DiVA

fulltext(5830 kB)380 downloads
File information
File name FULLTEXT01.pdfFile size 5830 kBChecksum SHA-512
e755cecf39484f2fd5f097a6a397e65b182f5c7a8e84b0eacff3249ab3022237f52855a9b1efd9704af3a35c896e2f94bb6ae7f8deea7f1cd1b2681101bb3c16
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Garrido Gálvez, MarioQureshi, FahadGustafsson, Oscar
By organisation
Computer EngineeringThe Institute of TechnologyElectronics System
In the same journal
IEEE Transactions on Circuits and Systems Part 1: Regular Papers
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 380 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 1050 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