Suche schnelle Implementation von ATN2 (evtl. CORDIC)

[Che Guevara]

Hi,

ich bin schon länger auf der Suche nach einem Algorithmus, welcher schnell den ATN2 berechnen kann. Dabei bin ich auf viele verschiedene Seiten gestoßen, u.a. die hier: http://www.mikrocontroller.net/attachment/90736/cordic.pdf
Der Algo soll angeblich den Winkel als 16Bit Variable ausgeben, also &h0000 entspricht 0° und &hffff entspricht 360°.
Wenn ich aber die Ergebnisse mit denen der normalen ATN2 Funktion vergleiche, kommt nur Schwachsinn raus! Ich verwende die gleichen Parameter für beide Funktionen und rechne das Ergebnis der normalen Funktion in Grad um.
Hat jemand sowas schonmal gemacht oder kann mir helfen? Ich brauche keine Vorgefertigte Lösung, aber eine Starthilfe wäre nicht schlecht :D
Eine LookupTabelle kann ich leider aus Platzgründen nicht verwenden. Diese ist zwar für kleine Werte von X/Y noch ausreichend genau, aber irgendwann ist die Abweichung einfach zu groß.
Das Ganze soll in einem ATXMega32A4 (@32MHz) laufen und sollte höchstens 500Takte beanspruchen, wobei das schon die oberste Grenze ist. Die normale ATN2 Funktion benötigt über 3000 Takte, das macht ca. 100µs und ist zu lange.

Gruß & Vielen Dank
Chris

[for_ro]

Hallo Chris,
schau doch mal hier (http://www.mcselec.com/index2.php?option=com_forum&Itemid=59&page=viewtopic&t=11180&start=0&postdays=0&postorder=asc&highlight=) bei MCS.

[Che Guevara]

Hi,

danke für den Tipp, ich schau mir die Codes gerade an! Wenn ich was funktionsfähiges finde, poste ich es hier.

Gruß
Chris

[Che Guevara]

Also ich hab die Codes nun ausprobiert, musste aber leider feststellen, dass da wohl irgendetwas nicht ganz stimmt. Teilweise bekomme ich immer nur 54° als Ausgabe, obwohl der reale ATN2 weit über 100° liegt... Die ASM-Implementation gefällt mir aber eigentlich sehr gut! Damit brauche ich zwar immer noch ca. 1500 Takte für eine Berechnung, das ist aber immerhin schonmal die Hälfte von ATN2.
Aber ich bin der Meinung, DAS MUSS DOCH SCHNELLER GEHEN?!
Also experimentiere ich jetzt mal mit einer Tabelle und evtl. Interpolation oder linearer Annäherung für größere Werte, um schneller zu sein. Wenn da jemand Ahnung hat, kann er sich gerne melden :D

Gruß
Chris

[malthy]

Hallo!

Ich habe nur mal schnell den Code, den User "laborratte" auf der zweiten Seite gepostet hat (http://www.mcselec.com/index2.php?option=com_forum&Itemid=59&page=download&id=2465) (Link s. o.) im Simulator laufen lassen. Bei mir stimmen alle Erbenisse - hätte ehrlich gesagt auch nichts anderes erwartet. Denk daran, dass die Ausgaben "hochskaliert" sind um die gewünschte Genauigkeiten in einem Integer unterzubringen. Der Atan2 liefert bei dieser Implementierung übrigens auch Grad und nicht wie meistens (auch in Bascom) Einheiten von pi (Radiant). Du musst also noch umrechnen (angleInDegrees = (180/pi) * angleInRadians).

Gruß
Malte

[Che Guevara]

Hi,

also ich hab den selben Code verwendet und wenn bei mir z.b. Y 28000 ist und X 5, dann stimmts einfach nichtmehr...
Dass es hochskaliert ist und die Ausgabe in Winkel ist, ist mir bewusst! Bei kleinen Eingaben stimmts ja auch.
Aber mir dauerts sowieso zu lange, deswegen mach ich mir jetzt selbst was ;)

Gruß
Chris

[malthy]

wenn bei mir z.b. Y 28000 ist und X 5, dann stimmts einfach nichtmehr...

Okay, mag sein. Aber dir ist schon klar, dass das einem Dreieck entspricht dessen Gegenkathete 5 mm lang ist während die Ankathete 28 m lang ist? Also kann sein dass das in deiner Anwendung korrekt ist, in den meisten Fällen wird man vermutlich nicht auf so extreme Wertepaare kommen (behaupte ich mal ganz selbstbewusst ;-)).

Wenn du magst, schreib doch mal von deinem eigenen Ansatz, das Thema finde ich grundsätzlich interessant!

Gruß
Malte

[Che Guevara]

Hi,

ja mir ist bewusst, dass die Differenz der Werte gewaltig ist, aber genau das brauche ich auch! Ich brauche die ATN2 Funktion zum einen für ein 3-Achs-ACC, wo solche Werte durchaus realistisch sind. Außerdem hab ich noch einen 3-Achs-Kompass, wo auch wieder solche Werte vorkommen.
Ja, sehr gerne berichte ich davon ;)
Mein erster Ansatz ist es, eine kleine Tabelle von ca. 100-200 Werten anzulegen, für die kleinen Werte von X/Y, da hier die größte Steigung auftritt. Für alle Werte von X/Y, die nicht mehr in der Tabelle vorhanden sind, wird die Steigung klein sein und man kann annähernd genau eine Gerade für bestimmte Bereiche anlegen (also eine Art Interpolation).
Leider brauche ich bei dieser Methode wieder eine Division. Aber darum komme ich wohl leider nicht drumrum...
Was hältst du den von der Idee?

Gruß
Chris

[malthy]

Sobald du eine Division drin hast, wird's auf einem AVR vermutlich wieder problematisch mit deinen Zeit-Constraints. Die Idee beim Cordic-Algo ist ja gerade ohne Multiplikation und Division auszukommen. Ich glaube du müsstest ebenso einen Ansatz finden der ohne Division auskommt. Außerdem hast du ja offenbar schon auch relativ hohe Ansprüche an die Genauigkeit. Ich überblick das jetzt eherlich gesagt nicht so ganz, aber wenn du ein Verhältnis von 28000:5 bei deinen Beschleunigungswerten hast (bzw haben kannst), muss dein Sensor ja schon recht genau sein (gute 12 bit zumindest wenn ich jetzt nicht auf die Schnelle zu einfach denke). Deswegen bin ich insgesamt (sehr) skeptisch. Es ist ja nicht so, dass sich nicht schon relativ kluge Leute daran versucht hätten ...

[Che Guevara]

Hi,

ja, die Division ist der störende Faktor! Aber bei meiner Lösung benötige ich nur eine Division, die als Integer nur um die 300 Takte braucht. Das ist zwar immer noch relativ lange, aber der Rest besteht dann ausschließlich aus Tabelle lesen und ein paar Additionen / Subtraktionen. Der Nachteil beim Cordic ist eben, dass er bei einer Tiefe von z.b. 10 schon 96 Shifts benötigt, dadurch wirds dann doch wieder relativ langsam!
Man muss eben einen Kompromiss zwischen Geschwindigkeit und Genauigkeit und Platzverbrauch eingehen, immer abgestimmt auf den Verwendungszweck. Mein ACC ist ein MPU6000, der 16Bit Auflösung hat. Das gute daran ist eben, wenn der Wert von X/Y z.b. zwischen 4 & 10 liegt, kann man diese kleine Strecke linearisieren, genauso wie die anderen Strecken, z.b. zwischen 10 & 20, 20 & 50, 50 & 100 , usw..... Du verstehst? :D

Gruß
Chris