AVR-CORDIC

AVR-Arithmetik mit dem CORDIC-Algorithmus

Der Cordic-Algorithmus bietet eine ganze Reihe mathematischer Funktionen. Er wird seit den ersten Taschenrechnern bis zu den mathematischen Befehlen der Pentium-Prozessoren oder in FPGAs verwendet.

Hier soll nur die praktische Anwendung in Mikrocontrollern der AVR-Reihe besprochen werden. Er arbeitet iterativ, ähnlich der sukzessiven Approximation in Analog-Digital-Wandlern. Es werden nur Additionen und Schiebeoperationen benötigt.

Es gibt sechs verschiedene CORDIC-Versionen, die für unterschiedliche mathematische Funktionen benutzt werden:

"circular", "linear", "hyperbolic", und diese jeweils "vectoring" oder "rotation".

circular vectoring

Kartesische --> Polarkoordinaten, arcsin, arccos, arctan, arccot

circular rotation

Polare --> Kartesische Koordinaten, sin, cos, tan, cot

Der CORDIC kann so auch als Alternative zum DDS Sinusgenerator verwendet werden. Er braucht keine Tabelle, daher ist eine höhere Amplitudenauflösung von z. B. 16 Bit möglich. Es entsteht gleichzeitig eine Sinus- und Cosinusschwingung.

linear vectoring

Division y/x

linear rotation

Multiplikation y*x

hyperbolic vectoring

arsinh, arcosh, artanh, arcoth, ln, log10, Quadratwurzel

hyperbolic rotation

sinh, cosh, tanh, coth, e-Funktion

Die avrfix - Festkommabibliothek

Entstand im Rahmen einer Baccalaureus-Arbeit an der TU Wien und ist auf Sourceforge frei verfügbar. Sie bietet neben den Grundrechenarten und einigen Hilfsroutinen zur Rundung und Überlaufbehandlung vor allem zwei CORDIC - Routinen, siehe Handbuch avrlib.pdf Seite 126:

• "CORDICCK" circular
• "CORDICHK" hyperbolic

der lineare Modus ist nicht vorhanden.

Mit dem Parameter "mode" wird die Transformationsrichtung übergeben:

• mode = 0 entspricht rotation
• mode = 1 entspricht vectoring

Mit dem Parameter "iterations" wird einer von zwei möglichen 32-Bit Festkomma-Datentypen ausgewählt:

• _Akkum hat 1 Vorzeichenbit, 15 Vorkomma- und 16 Nachkommabits, iterations=16
• _lAkkum hat 1 Vorzeichenbit, 7 Vorkomma- und 24 Nachkommabits, iterations=24

Sinus/Cosinusgenerator

Die iterative Näherung der Sinus und Cosinusfunktion folgt diesem Programmablauf, ähnlich der Darstellung im DDJ-Artikel von Mike Pashea, siehe Literaturangaben: Konvergenzbereich:: -1.7433 < angle < 1.7433 (pi/2 = 1,57075) Eingangsvariable "angle" und "iterations", Ergebnis "cos" und "sin"

cos = 1/1,6468
sin = 0
for i=0 to iterations
  cos_tmp = cos
  sin_tmp = sin
  if (angle > 0)
    cos = cos - sin_tmp*2^(-i)
    sin = sin + cos_tmp*2^(-i)
    angle = angle - arctan(2^(-i))
  else
    cos = cos + sin_tmp*2^(-i)
    sin = sin - cos_tmp*2^(-i)
    angle = angle + arctan(2^(-i))
  endif
next i

Mit OpenOffice-Calc berechnet sehen die ersten neun Iterationen wie im Bild gezeigt aus - Größere Version als PDF. Die "if(angle>0)"-Verzweigung wurde durch die Signum-Funktion "VORZEICHEN(angle)" ersetzt. Winkel in 64 Stufen von -Pi/2 bis +Pi/2, obere Diagrammreihe Sin und Cos (angle), unten als x/y-Diagramm, das muß einen Halbkreis ergeben.

In den meisten 8-Bit-Controllern fehlt ein sogenannter Barrel-Shift-Befehl für die "*2^(-i)"-Berechnung. Das ist eine arithmetische (vorzeichenrichtige) Rechtsverschiebung um eine wählbare Anzahl Stellen. In AVR-Assembler ausgedrückt: asr Highbyte, ror Lowbyte(s), asr ... Man kann sich mit Multiplikationen oder einem indirekten Sprung ijmp in eine "asr - ror - asr - ror..."-Folge behelfen, elegant ist beides nicht.

CORDIC im Diskussionsforum

• "echter" double mit AVR-GCC
• Cordic-Algorithmus, FPGA
• CORDIC-Core Xilinx
• Mischung mit sin/cos in VHDL
• Genauigkeitsproblem, FFT im FPGA
• Wurzel mit Cordic auf Spartan3E
• sin/cos mit Cordic-Algorithmus in AVR-Assembler

Bücher & Artikel

• DSP with FPGAs U.Meyer-Baese Kap.2.8 ISBN 3-540-21119-5 Anhang des Buchs als PDF, Literaturverzeichnis, Verilog-Files und Register
• Vladimir Baykov, Problems of Elementary Functions Evaluation Based on Digit by Digit (CORDIC) Technique, PhD thesis, Leningrad State Univ. of Electrical Eng., 1972
• Schmid, Hermann, Decimal computation. New York, Wiley, 1974
• V.D.Baykov,V.B.Smolov, Hardware implementation of elementary functions in computers, Leningrad State University, 1975, 96p.
• Vladimir D. Baykov, Vladimir B. Smolov: Special-purpose processors: iterative algorithms and structures. Radio & svjaz, Moscow 1985, 288 pages.
• Implementing Cordic Algorithms by Pitts Jarvis, DDJ Oktober 01, 1990
• The CORDIC Method for Faster sin and cos Calculations by Michael Bertrand, DDJ November 01, 1992
• Microcontrollers & CORDIC Methods by Michael Pashea, DDJ September 01, 2000
• Implementing Matrix Inversions in Fixed-point Hardware by Ramon Uribe and Tom Cesear, DDJ Oktober 12, 2006
• Software Implementation of Trigonometric Functions Using CORDIC Algorithm by Christober Rayappan, DDJ Dezember 19, 2006

Siehe auch

Sinus- und Cosinus-Berechnung mittels

• CORDIC
• Linearer Interpolation

Weblinks

• Wikipedia zu Cordic, dort weitere Links
• Historisches, u.a. Originalliteratur ab 1959 als PDF
• avrfix Festkommabibliothek für AVR in C und Downloadseite
• CORDIC sin/cos in C und Z80-Assembler
• schnelle Division mit CORDIC in PIC-Assembler
• CORDIC-C-Routinen aus Dr.Dobbs Journal 1990 und hier Converted to ANSI-C
• Cordic sin/cos und kart./polar auf Basic-Stamp
• CORDIC-Arcustangens für Lego/Renesas H8
• Xilinx Cordic IP-Block mit ausführlicher Beschreibung
• Alle Cordic-Algorithmen in C für Taschenrechner hp35 [1972]