Change search
ReferencesLink to record
Permanent link

Direct link
Alternatives for Low-Complexity Complex Rotators
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.
Linköping University, Department of Electrical Engineering, Electronics System. Linköping University, The Institute of Technology.ORCID iD: 0000-0003-3470-3911
2010 (English)In: Proceedings of the 17th IEEE International Conference on Electronics, Circuits, and Systems, (ICECS 2010), Athens, Dec-12-15, 2010, IEEE , 2010, 17-20 p.Conference paper (Refereed)
Abstract [en]

Complex rotations find use in common transforms such as the Discrete Cosine Transform (DCT) and the Discrete Fourier Transform (DFT). In this work we consider low-complexity realization of constant angle rotators based on shifts, adders, and subtracters. The results show that redundant CORDIC and scaled constant multiplication are providing the best results, depending on which angle is considered. It is also shown that the precision can vary several bits using the same number of adders and subtracters, and, hence, the correct choice of rotator architecture is crucial for a low-complexity realization.

Place, publisher, year, edition, pages
IEEE , 2010. 17-20 p.
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-65909DOI: 10.1109/ICECS.2010.5724443OAI: oai:DiVA.org:liu-65909DiVA: diva2:400287
Conference
The 17th IEEE International Conference on Electronics, Circuits, and Systems, (ICECS 2010), Athens, Dec-12-15, 2010
Note
©2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. Fahad Qureshi, Mario Garrido and Oscar Gustafsson, Alternatives for Low-Complexity Complex Rotators, 2010, The 17th IEEE International Conference on Electronics, Circuits, and Systems, (ICECS 2010), Athens, Dec-12-15, 2010. Available from: 2011-03-07 Created: 2011-02-25 Last updated: 2015-03-11Bibliographically 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: 2015-03-11Bibliographically approved

Open Access in DiVA

fulltext(159 kB)448 downloads
File information
File name FULLTEXT02.pdfFile size 159 kBChecksum SHA-512
fd3259e36a977c934506a1158c32dff71352f5dec8ae6cedd3c5d8bc319abff87eb2a6ee926ec27b941c7a042bf8c9dd1f37c039bbd49a13ca7d3f12792a6df0
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Qureshi, FahadGustafsson, Oscar
By organisation
Electronics SystemThe Institute of Technology
Engineering and Technology

Search outside of DiVA

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

Altmetric score

Total: 268 hits
ReferencesLink to record
Permanent link

Direct link