VHDL - CORDIC Verfahren

Transcrição

Outline
Motivation und Geschichte des CORDIC-Verfahrens
CORDIC-Verfahren
Der verallgemeinerte CORDIC
VHDL - CORDIC Verfahren
Marc Reichenbach und Michael Schmidt
Informatik 3 / Rechnerarchitektur
Universität Erlangen Nürnberg
04/12
1 / 30
Outline
CORDIC-Verfahren
Gliederung
CORDIC-Verfahren
2 / 30
Outline
CORDIC-Verfahren
Motivation
• oft “Standardfunktionen” benötigt
• meistens nur mit hohem Aufwand zu berechnen
• spezielle iterative Algorithmen ohne Verwendung von
Multiplikationen
• dadurch Einsparung von Chipfläche
3 / 30
Outline
CORDIC-Verfahren
Standardfunktionen
• Sinus
• Cosinus
• Tangens
• Exponentialfunktion
• Logarithmusfunktion
• Arcus- und Areafunktionen
• Quadratwurzel
• Multiplikation, Division
4 / 30
Outline
CORDIC-Verfahren
Einsparung von Chipfläche
• Multiplikationen sehr zeitintensiv
• Multiplikationswerke sehr groß
• Technologien damals
• LSI, MSI, SSI: Anzahl der Transistoren begrenzt
• Technologien heute
• Verwendung schneller Multiplizierer
• Einsatz in platzkritischen Technologien wie FPGA
• Einsatz bei massiv parallelen Architekturen
5 / 30
Outline
CORDIC-Verfahren
Alternative Technologien
• Lookup-Tabellen
• viel Platzverbrauch
• für jede Funktionen eine eigene notwendig
• Interpolation zwischen den Werten
• BKM (Bit) Algorithmen
• iterative shift-and-add Algorithmus
• nur für Logarithmus- und Expotentialfunktionen geeignet
• Taylorreihe
• Beispiel Sinus an a = 0: sin(x) = x +
x3
3!
+
x5
5!
+
x7
7!
+
x9
9!
• ... benötigt auch Multiplikationen
6 / 30
Outline
CORDIC-Verfahren
CORDIC Entwicklung
• CORDIC-Verfahren von Volder (1959) und Walther (1971)
entwickelt
• Konvergenzverfahren auf Basis von Koordinatentransformation
• Verfahren benötigt nur einfache Operationen
• Addition (RCA)
• Schiebeoperationen (Multiplexer)
• Abfragen (Multiplexer)
• Tabellenzugriff (ROM, Counter)
• alle “Standardfunktionen” damit umsetzbar
7 / 30
Outline
CORDIC-Verfahren
CORDIC - Veröffentlichungen und Einsatz
• Volder 1959: The CORDIC Trigonometric Computing
Technique. sin, cos, arctan, sqrt
• CORDIC - coordinate rotation digital computing
• Walther 1971: A unified algorithm for elementary functions.
sinh, cosh, e, ln, div
• Einsatz in den ersten Generationen der HP Taschenrechner
• CORDIC-Prozessor als ASIC in Roboter-Steuergung:
Timmermann et al.: A CMOS floating-point vector-arithmetic
unit
8 / 30
Outline
CORDIC-Verfahren
Prinzip des CORDIC-Verfahren
• Berechnung Sinus bzw. Cosinus wird auf
Koordinatentransformationen zurückgeführt
• Drehung eines Vektors (x0 , y0 ) um einen Winkel Θ in einen
Vektor (xn , yn )
• mathematisch durch Multiplikation mit sog. Rotationsmatrix
durchführbar
(xn,yn)
Θ
xn
cos Θ − sin Θ
x
=
· 0
yn
sin Θ cos Θ
y0
(x0,y0)
9 / 30
Outline
CORDIC-Verfahren
CORDIC - Sinus und Kosinus
• durch Drehung des Vektors (1, 0) um Θ ist sin Θ und cos Θ
berechenbar
cos Θ − sin Θ
1
xn
=
·
sin Θ cos Θ
0
yn
sin Θ
(xn,yn)
Θ
cos Θ
(1,0)
10 / 30
Outline
CORDIC-Verfahren
CORDIC - Umformung in den Tangenz
• durch mathematische Umformung nur noch Abhänigkeit von
einer Winkelfuntion tan Θ
• wichtig um Multiplikationen durch Schiebeoperationen nach
rechts zu ersetzen
• Drehung um den Winkel Θ wird nun durch Folge von
Drehungen um Teilwinkel αi realisiert
xn
x
cos Θ − sin Θ
=
· 0
yn
sin Θ cos Θ
y0
1
1 + tan2 Θ
1
xn
1
− tan Θ
x
=√
·
· 0
2
yn
tan
Θ
1
y0
1 + tan Θ
cos Θ = √
11 / 30
Outline
CORDIC-Verfahren
CORDIC - Einführung Teilwinkel
• Teilwinkel αi sind bereits vorab definiert
• Teilwinkel so gewählt, dass der gewünschte Winkel Θ als
Linearkombination der Teilwinkel αi darstellbar ist
Θ=
n−1
X
σi · αi
σi ∈ {−1, 1}
i=0
• d.h., der Winkel Θ wird durch eine alternierende
Approximation angenährt
• bedeutet, dass man vor- und zurückdreht
• ist man bei einer Teildrehung zu weit gegangen, d.h. über den
Winkel Θ hinaus, so muss man im nächsten Schritt wieder
zurückdrehen
• die Drehrichtung wird durch den Parameter σi gesteuert
12 / 30
Outline
CORDIC-Verfahren
CORDIC - Linearkombination der Teilwinkel
• zur Steuerung des Vorzeichens bzw. der Drehrichtung wird
Hilfsvariable zi eingeführt
• z0 wird mit dem gewünschten Drehwinkel Θ initialisiert
α1+α2+α3
Θ
α1+α2
α1
α1+α2
+α3-α4
(xn,yn)
α3
α2
α4
Θ
z0 = Θ
zi+1 = zi − σi · αi
α1
(1,0)
(
1
zi ≥ 0
σi =
−1 zi < 0
13 / 30
Outline
CORDIC-Verfahren
CORDIC - Eliminierung der Multiplikationen
Mathematischer Ausdruck einer Teildrehung:
1
xi+1
1
=p
·
2
yi+1
σ
tan
αi
i
1 + tan αi
x
−σi tan αi
· i
yi
1
Eliminierung der Multiplikationen:
• wesentliche Idee hinter dem Verfahren
• ersetze Multiplikationen durch Schiebeoperationen
tan αi = 2−i
i = 0...n − 1
14 / 30
Outline
CORDIC-Verfahren
CORDIC - Iteration ohne Multiplikation
Teildrehung um αi
1
xi+1
= ki ·
yi+1
σi 2−i
−σi 2−i
x
· i
yi
1
1
1
ki = p
=√
1 + 2−2i
1 + tan2 αi
• da es sich bei den Teilwinkeln αi um bekannte Werte handelt,
können die ki vorab zusammengefasst werden
15 / 30
Outline
CORDIC-Verfahren
CORDIC - Iterationsformeln
Iterationsformeln
xi+1 = xi − σi · 2−i · yi
yi+1 = yi + σi · 2−i · xi
zi+1 = zi − σi · arctan 2−i
Faktor k
k=
n−1
Y
i=0
1
√
1 + 2−2i
16 / 30
Outline
CORDIC-Verfahren
CORDIC - Initialwerte
Lösung des Systems von Differenzengleichungen ist
xn = x0 cos z0 − y0 sin z0
yn = y0 cos z0 + x0 sin z0
Durch geeignete Wahl der Initialwerte ist damit Sinus und Cosinus
berechenbar
x0 = 1 ∧ y0 = 0 −→ xn = cos z0 ∧ y0 = sin z0
Achtung: Um den Wert k zu klein!
k=
n−1
Y
i=0
√
1
1 + 2−2i
17 / 30
Outline
CORDIC-Verfahren
CORDIC - Initialwert k
Multiplikation nicht notwendig, wenn Startwert gut gewählt
x00 = x0 · k = k
y00 = y0 · k = 0
(xn,yn)
k · (xn,yn)
k · (1,0) (1,0)
18 / 30
Outline
CORDIC-Verfahren
CORDIC - Vektormodus
• eben gezeigtes Verfahren verfolgte Strategie die z-Komponente
gegen 0 streben zu lassen
• dies wird Rotationsmodus genannt
• es gibt aber auch die Möglichkeit, mit der zweiten Variable yi
gegen 0 zu kovergieren
(x0, y0)
Θ
(xn, 0)
x0
cos Θ = q
x02 + y02
y0
sin Θ = q
x02 + y02
→ tan Θ =
y0
x0
(x02 + y02)1/2 = xn
19 / 30
Outline
CORDIC-Verfahren
CORDIC - Funktionalität des Vektormodus
• diese Strategie wird Vektormodus genannt
• graphisch gesehen kann dann auf der x-Achse die Länge des
Vektors (x0 , y0 ) abgelesen werden
• werden gleichzeitig in der dritten Komponente alle z alle
Teilwinkel aufsummiert, erhält zn den Winkel identisch mit
arctan(y0 /x0 )
• Iterationsformeln identisch wie beim Rotationsmodus
• zur Bestimmung des Vorzeichens σi muss nun die Variable yi
abgefragt werden
20 / 30
Outline
CORDIC-Verfahren
CORDIC - wichtige Formeln des Vektormodus
Zusammenfassung in Formeln
Länge eines Vektors / Wurzel:
xn =
q
x02 + y02
Winkel eines Vektors / arctan:
zn = z0 + Θ = z0 + arctan(y0 /x0 )
Vorzeichen für die Iterationen:
(
−1, yi ≥ 0
σi =
1,
yi < 0
21 / 30
Outline
CORDIC-Verfahren
CORDIC - Erweiterung zum allgemeinen CORDIC
• bisher gezeigten Iterationsformeln erlauben die Berechnung
• der Wurzelfunktion
• des Arkustangens
• der trigonometrischen Funktionen
• Walther erweiterte 1971 das von Volder für zyklische
Koordinatensysteme entwickelte Verfahren auf
• lineare und
• hyperbolische Koordinatensysteme
22 / 30
Outline
CORDIC-Verfahren
CORDIC - Norm eines Vektors
p
x2 + m · y2
x
p
x2 + y2
p
x2 − y2
m=1
m=0
m=-1
zyklisches KOS
lineares KOS
hyperbolisches KOS
23 / 30
Outline
CORDIC-Verfahren
CORDIC - Veralgemeinerte Rotationsmatrix
"
1 √
1
xi+1
=p
·
√
tan(αi m)
yi+1
1 + tan2 (αi m) σi √m
√
√ # −σi m tan(αi m) xi
·
yi
1
m = −1
m=1
m=0
↓
↓
zyklisch
1
σi tan αi
−σi tan αi
1
tan αi = 2−i
↓
hyperbolisch
linear
1
σi αi
0
1
αi = 2−i
1
σi tanh αi
−σi tanh αi
1
tanh αi = 2−i
24 / 30
Outline
CORDIC-Verfahren
CORDIC - Verallgemeinerte Iterationsformeln
Iterationsformeln
xi+1 = xi − mσi · 2−F (i) · yi
yi+1 = yi + σi · 2−F (i) · xi


i
wenn m = 0 ∨ m = 1



1, 2, 3, 4, 4, 5, 6, . . . ,
F (i) =

13, 13, 14, 15, . . . ,



40, 40, 41, . . .
wenn m = −1
25 / 30
Outline
CORDIC-Verfahren
CORDIC - Die Funktion F (i)
• Zahlen 4, 13, 40, k, 3k + 1 treten im hyperbolischen Fall
doppelt auf
• Grund ist Konvergenz
• für die Einhaltung der Konvergenz muss für verschiedene
Teilwinkel αi gelten
αi −
n−1
X
αi < ∆α
j=i+1
• d.h., jeder Teilwinkel einer Iteration kann durch alle folgenden
Teilwinkel bis auf einen Restfehler kompensiert werden
26 / 30
Outline
CORDIC-Verfahren
CORDIC - Konvergenz der Teilwinkel
• Restfehler des Gesamtverfahrens ist durch den Teilwinkel der
letzten Iteration definiert
• damit Kompensation möglich ist, muss Nachfolgewinkel
mindestens die Hälfte des Vorhergehenden betragen
1
αi+1 ≥ αi
2
• für zirkulares und lineares Koordinatensystem erfüllt
• für hyperbolisches nicht: eine Winkeldrehung muss an
bestimmten Fällen eventuell wieder vollständig rückgängig
gemacht werden
27 / 30
Outline
CORDIC-Verfahren
CORDIC - Übersicht
Betriebsart
Rotationsmodus
zn → 0
m
1
0
-1
Vektormodus
yn → 0
1
0
-1
Funktion
xn = x0 cos z0 − y0 sin z0
yn = y0 cos z0 + x0 sin z0
xn = x0
yn = y0 + z0 x0
xn = x0 cosh z0 + y0 sinh z0
yn = yq
0 cosh z0 + x0 sinh z0
xn
zn
xn
zn
= (x02 + y02 )
= z0 + arctan(y0 /x0 )
= x0
= zq
0 + y0 /x0
xn = x02 − y02
zn = z0 + Atanh(y0 /x0 )
28 / 30
Outline
CORDIC-Verfahren
CORDIC - Berechenbare Funktionen
z
e = cosh z + sinh z
√
q
z = (z + 41 )2 − (z − 14 )2
e −z = cosh z − sinh z tan z =
ln z = 2Atanh( z−1
z+1 )
sin z
cos z
tanh z =
sinh z
cosh z
29 / 30
Outline
CORDIC-Verfahren
CORDIC - Architektur
xi+1 = xi − mσi · 2−F (i) · yi
yi+1 = yi + σi · 2−F (i) · xi
xi
yi
zi
2-F(i)
Shift
+/xi+1
mσi
αi
Shift
σi
+/-
+/-
yi+1
zi+1
σi
30 / 30

VHDL - CORDIC Verfahren

Transcrição

Documentos relacionados

Übung 10

Strahlensätze und Trigonometrie am rechtwinkligen Dreieck

Übungsblatt 1

Kap. 12

Physik I Musterlösung für die Prüfung Sommer 2011 Aufgabe 1

Grundwissen 9. Klasse - Leibniz

Übungsblatt 4

Lösungsvorschlag zu Blatt 10

Umwandlung elektrischer Energie mit Leistungselektronik WS 2014

Hotels in Oberkirch