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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
On Generating Complex Numbers for FFT and NCO Using the CORDIC Algorithm
Linköping University, Department of Electrical Engineering. (Computer Engineering)
2008 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesisAlternative title
Att generera komplexa tal för FFT och NCO med CORDIC-algoritmen (Swedish)
Abstract [en]

This report has been compiled to document the thesis work carried out by Anton Andersson for Coresonic AB. The task was to develop an accelerator that could generate complex numbers suitable for fast fourier transforms (FFT) and tuning the phase of complex signals (NCO). Of many ways to achieve this, the CORDIC algorithm was chosen. It is very well suited since the basic implementation allows rotation of 2D-vectors using only shift and add operations. Error bounds and proof of convergence are derived carefully The accelerator was implemented in VHDL in such a way that all critical parameters were easy to change. Performance measures were extracted by simulating realistic test cases and then compare the output with reference data precomputed with high precision. Hardware costs were estimated by synthesizing a set of different configurations. Utilizing graphs of performance versus cost makes it possible to choose an optimal configuration. Maximum errors were extracted from simulations and seemed rather large for some configurations. The maximum error distribution was then plotted in histograms revealing that the typical error is often much smaller than the largest one. Even after trouble-shooting, the errors still seem to be somewhat larger than what other implementations of CORDIC achieve. However, precision was concluded to be sufficient for targeted applications.

Abstract [sv]

Den här rapporten dokumenterar det examensarbete som utförts av AntonAndersson för Coresonic AB. Uppgiften bestod i att utveckla enaccelerator som kan generera komplexa tal som är lämpliga att använda försnabba fouriertransformer (FFT) och till fasvridning av komplexasignaler (NCO). Det finns en mängd sätt att göra detta men valet föllpå en algoritm kallad CORDIC. Den är mycket lämplig då den kan rotera2D-vektorer godtycklig vinkel med enkla operationer som bitskift ochaddition. Felgränser och konvergens härleds noggrannt. Acceleratorn implementerades i språket VHDL med målet att kritiskaparametrar enkelt skall kunna förändras. Därefter simuleradesmodellen i realistiska testfall och resulteten jämfördes medreferensdata som förberäknats med mycket hög precision. Dessutomsyntetiserades en mängd olika konfigurationer så att prestanda enkeltkan viktas mot kostnad.Ur de koefficienter som erhölls genom simuleringar beräknades detstörsta erhållna felet för en mängd olika konfigurationer. Felenverkade till en början onormalt stora vilket krävde vidareundersökning. Samtliga fel från en konfiguration ritades ihistogramform, vilket visade att det typiska felet oftast varbetydligt mindre än det största. Även efter felsökning verkar acceleratorngenerera tal med något större fel än andra implementationer avCORDIC. Precisionen anses dock vara tillräcklig för avsedda applikationer.

Place, publisher, year, edition, pages
2008. , 55 p.
Keyword [en]
FFT, NCO, CORDIC algorithm, CORDIC convergence, CORDIC error analysis
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-15556ISRN: LITH-ISY-EX--08/4197--SEOAI: oai:DiVA.org:liu-15556DiVA: diva2:127535
Subject / course
Computer Engineering
Presentation
2008-11-14, Glashuset, B-huset, Campus Valla, Linköpings universitet, Linköping, 14:30 (English)
Uppsok
Technology
Supervisors
Examiners
Available from: 2008-12-09 Created: 2008-11-17 Last updated: 2012-04-24Bibliographically approved

Open Access in DiVA

fulltext(696 kB)929 downloads
File information
File name FULLTEXT01.pdfFile size 696 kBChecksum SHA-512
1305c068aa1a48d4c021466ff289edc891bfb43995f275d50ebb276668693a597a46db6af83bac1baaecddcd97b8b6d1508fb4f560a9ac306a16ce262ed3b0d9
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Andersson, Anton
By organisation
Department of Electrical Engineering
Engineering and Technology

Search outside of DiVA

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

urn-nbn

Altmetric score

urn-nbn
Total: 1056 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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