einfache Division mit Atmega AVR?

[wolli_bolli]

Hallo,
//alles Folgende bezieht sich auf einen assemblerprogrammierten
//Atmega 324P
Ich möchte meinen Roboter mit einer Art Tacho ausstatten, der die Geschwindigkeit ermittelt:

Dazu sind an den Rädern Impulssensoren angebracht (3 Impulse/Umdrehung). Die Zeitdauer zwischen zwei Impulsen wird mit einem Hardwaretimer exakt gemessen. Um nun die Geschwindigkeit zu erhalten muss man bekanntermaßen folgende Formel anwenden:


Geschwindigkeit = zurückgelegter Weg / dafür benötigte Zeit


Der Weg ist in meinem Fall kostant, die Zeit ändert sich. Um die Aufgabe mit Mikrocontroller (in meinem Fall: Atmega324P) zu lösen, verwendet man in der Regel Routinen, die prinzipiell das schriftliche, dezimale Dividieren nachbilden und relativ viel Zeit (einige 50 Taktzyklen) benötigen.
Ich habe mir gedacht, dass man solche Aufgaben eigentlich schneller lösen können müsste, wenn man die Division in eine Multiplikation umwandelt und die mit dem Hardwaremultiplizierer des Controllers durchführt:


Ergebnis = Divident * (1/Divisor)


Allerdings hat man das Problem nur verlagert, da man vorher den Reziprokwert des Divisors bilden muss (1/Divisor).
Ich könnte mir aber vorstellen, das dies auf binärer Ebene durch einfache Bitmanipulationen machen kann (analog funktioniert es ja schließlich auch bei Addition/Subtraktion).

Meine Frage an euch:
Funkioniert das so? Oder kann man auf anderem Wege die Division beschleunigen?
Ich hab auch schon eine ganze Weile mit Papier und Bleistift überlegt und auch im Internet nachgesehen habe aber nichts passendes gefunden. (vielleicht steh ich aber einfach nur auf dem Schlauch)

Vielen Dank für sämtliche Bemühungen
Gruß,
wolli_bolli

PS.: Ich möchte das ganze in Assembler programmieren.

[rideyourstyle]

Rechnen und Assembler ist eine "gute" sache ;-)

Der Denkanstoss in Richtung Multiplikation ist gut. Hast du einmal daran gedacht, dass du die Konstante Weg hoch minus 1 machen würdest! Dieser Wert ändert sich nicht. Dafür hast du dann eine Kommazahl. :-( Also müsstest du je nach gewünschter Genauigkeit beide Werte mit einem bestimmten Wert multiplizieren (einfachhalber ein Vielfaches von 2 -> rol, ror)
Oder so ähnlich...

[wolli_bolli]

Ich habe auch schon daran gedacht, einfach den Reziprokwert des Weges zu bilden. Wenn ich den dann aber mit der Zeit multipliziere kommt als Ergebnis der Reziprokwert der Geschwindigkeit heraus, da ich dann letztendlich Zeit durch Weg teile. Ich brauche aber den "echten" Wert der Geschwindigkeit (und nicht den reziproken). Insofern komme ich um eine Division durch die sich ändernde Zeit nicht herum.

Gruß wolli_bolli

[rideyourstyle]

Ach ja stimmt. Irgendwie war mir klar, aber während dem schreiben sind mit Zweifel gkommen. Darum schrieb ich auch: Oder so ähnlich...
Leider habe ich mit Assembler nur die Addtion und Subratkion gebraucht. Ich wollte mir einmal eine Sammlung von Rechenmakros schreiben, die dann je nach Anwedung direkt includiert werden können!

[Gock]

Durch geschickte Wahl der Konstanten, des TimerPrescalers, des µCTaktes SOWIE der möglich messbaren Zeitspanne ist es möglich, die Division in eine Subtraktion zu überführen.
Geschickt heißt, alle benutzten Werte müssen 8Bit breit sein und der gesamten GeschwBereich abdecken und dabei die Geschw in einer geeigneten Einheit darstellen.
Beispiel:
v_min = 255 TimerWerte entsprechen 1cm/s
v_max = 1 TimerWert entspricht 255cm/s
255 und 1 sind die 8Bit TimerWerte der Messung.
Dann entspricht:
v = 255-TimerWert der aktuellen Geschwindigkeit in cm/s.
Bei zB TimerWert = 64 --> 255-63 = 192cm/s
oder TimerWert = 196 --> 255-196 = 59 cm/s
Letztendlich müsstest Du in diesem Beispiel dafür sorgen, dass 255 Timerzählung der min Geschw entsprechen und das kann recht viel sein. Eventuell wird ein Softwareteiler notwendig, der den TimerPrescaler zusätzlich teilt. Aber das alles hängt von den genauen Bedingungen ab.

Wenn Du keinen Softwareteiler benutzen willst, kannst Du einen anderen Timer dazu verwenden, die minimale Auflösung darzustellen, in dem Du dessen CompareMatches während der Zeitmessung zählst und anschließend umrechnest. Damit ist es möglich genauer zu messen, weil Du am Ende Anzahl der CompMatches hast UND den letzten TimerWert des 2. Zählers. Aber das bringt Dir nichts hinsichtlich Rechenzeit.
Gruß

[SprinterSB]

50 Takte ist ja nicht die Welt...

Du hast ja nichma geschrieben, um welche Division es geht. 32/32 oder 8/8 Bits???

Bei 8/8 und konstantem Dividend ging ne Tabelle wenns schnell gehen muss, braucht aber natürlich Platz.

Als Referenz für ne DIV/MODULO-Implementierung ist avr-gcc ganz gut, da kann man nachschauen wie es dort gemacht ist, ist vielleicht schneller?

Hier mal ein Link an die Quelle der libgcc.S, hoffe mal der Link geht. Ist kommentierter GNU avr-asm:

http://gcc.gnu.org/viewcvs/trunk/gcc/config/avr/libgcc.S?revision=133966&view=markup

Da gibts Division+Modulo for 32 bit (si), 16 Bit (hi) und 8 Bit (qi), signed und unsigned. Die 8-Bit unsigned Version heisst zB udivmodqi4, die signed 16-Bit Version divmodhi4 etc.

[wolli_bolli]

@SprinterSB: es geht um eine 16bit/16bit Division (Wegkonstante ~ 5200, Zeit 1...2048 ergibt Weg in cm/s), meine bisherige Divisionsroutine ähnelt dem avr-gcc Code.

@Gock: deine Möglichkeit scheint genial, ist aber ungenau, da sie die Geschwindigkeit als lineare Funktion der Zeit annimmt, in Wirklichkeit ist der Graph der Zeit - Geschwindigkeitsfunktion aber keine Gerade sondern eine Hyperbel. Durch geschickte Bereichswahl und eventuelle Vorfaktoren (Multiplizieren geht ja sehr einfach und schnell) kann man die Abweichung aber gering halten. Werde mal morgen früh durchrechnen ob das für mein Problem genau genug ist.

Außerdem könnte es sein, dass man, wenn man für die Zeitmessung ein Compare Match Interrupt im CTC-Modus verwendet durch kontinuierliches Senken des Vergleichswertes die Hyperbel der Funktion quasi zu einer Gerade "strecken" kann. Dann könnte man mit höherer Genauigkeit Gocks Formel anwenden. Auch dazu werd ich mir mal Gedanken machen.

Gruß wolli_bolli

[wkrug]

Guck mal http://www.avr-asm-tutorial.net/avr_de/rechnen/division.html#div8bin
die Routine kannst Du für deine 16 Bit einfach erweitern.

[Gock]

Hyperbel???
Du meinst, Deine Geschwindigkeit ändert sich hyperbolisch??? Das ist aber eine merkwürdige Geschwindigkeit! Vielleicht meinst Du "nichtlinear".
Das macht aber dann keinen Unterschied zu Deiner Variante mit der Division, denn da nimmst Du sie auch linear an und bildest den Mittelwert über dieselbe Periode wie ich.
Sollte sich die Änderung der Geschwindigkeit (also die Beschleunigung) innerhalb des Messintervalls so stark ändern, dann ist das bereits ein Problem der Hardware -> zu geringe Auflösung der Encoder.
Solche Probleme sollte man nicht unbedingt versuchen zu korrigieren, wenn man nur 50 Takte zur Verfügung hat.
Allerdings habe ich im Nachhinein festgestellt, dass Du mehrere 50 Takte meintest. Bei 16Bit Operationen sind die dann natürlich auch notwendig.
Der GCC Link von Sprinter ist echt gut, wenn auch etwas unübersichtlich auf den ersten Blick.
Mit dem Link von wkrug kann ich nicht so viel anfangen, weil da kein Code zu finden ist.
Wenn es nicht 32Bit sein müssen kann ich nur die optimierten Routinen von Atmel selbst empfehlen. Es gibt sie Code- und Speed-Optimized, sie funktionieren sicher und es sind jeweils Code und Taktverbrauch angegeben.
Gruß

PS: Danke, ich finde meine Methode auch genial... ;-)
O:)

[wolli_bolli]

Ich würde schon sagen, dass sich die Geschwindigkeit hyperbolisch ändert, schließlich geht die Geschwindigkeit gegen unendlich, wenn die Zeit gegen null geht. Um die Geschwindigkeit gegen Null gehen zu lassen, muss prinzipiell eine unendliche Zeit vergehen. Das sind genau die Eigenschaften einer Hyperbel und nicht die einer Gerade, wenn ich mich nicht irre, was aber durchaus sein kann.
Wie dem auch sei, ich habe jetzt ersteinmal die mit dem Kopf durch die Wand Methode angewandt und mir von Excel eine Tabelle mit 2000 16-bit Werten berechnen lassen und das ganze im Flash des Controllers abgespeichert. Somit wird nicht mehr dividiert sondern einfach nachgeschaut. Da ich sowieso erst ca. 2,5 KByte von meinen 32 KByte Speicher mit Programm gefüllt hab, stört der relativ große Speicherhunger der Tabelle vorerst nicht.
Dennoch nochmal danke für eure Hilfe
Gruß
wolli_bolli

[SprinterSB]

@SprinterSB: es geht um eine 16bit/16bit Division (Wegkonstante ~ 5200, Zeit 1...2048 ergibt Weg in cm/s), meine bisherige Divisionsroutine ähnelt dem avr-gcc Code.


Mit 50 Ticks für 16/16 sind das ca. 3 Ticks/Bit. wo willst Du da was verbessern? Zeig doch mal den Code. Tricks sind immer drin.

[Gock]

...schließlich geht die Geschwindigkeit gegen unendlich, wenn die Zeit gegen null geht. Um die Geschwindigkeit gegen Null gehen zu lassen, muss prinzipiell eine unendliche Zeit vergehen.
Mit Grenzwerten kannst Du das Problem nicht lösen, weil wir uns hier im "quantisierten Raum" Raum bewegen. Wenn Du <1 oder >254 Zählerwerte misst, dann bist Du im nicht definierten Gebiet aber noch lange nicht im Grenzwert. Diese Fälle musst Du natürlich abfangen, indem Du ausschließt, dass sie zutreffen. Sollten sie durch einen Fehler zutreffen, müssen sie per Software abgefangen werden. In jeden Fall ist die Methode absolut linear.
Einen LookUpTable bei 16 Bit zu benutzen wird in keinem Fall zu einem "optimierten" Ergebnis führen, weil Du dann einen "Sortieralgorithmus" brauchst. Diese haben neben relativ hoher Rechenleistung den weiteren Nachteil, dass Du nie genau weißt, wie viele Takte im jeweiligen Fall benötigt werden.
"Schnell" ist was anderes und genau ohnehin, wenn Du bei 16Bit nur 2000 Werte nutzt...
Aber Du kannst es ja versuchen. Da wir die genauen Parameter nicht kennen (erlaubte Takte...) wird es langsam schwer einen weiteren guten Rat zu geben...
Viel Spass

...hat da etwa wer was gelöscht???....

[wolli_bolli]

@Sprinter: Ich habe nicht von 50 Taktzyklen sondern von einigen 50 Taktzyklen gesprochen.
@Gock: Das mit der Wertetabelle funktioniert bestens, da die Wertetabelle (2500 16bit Werte=>ca. 5kByte) im Flash ab einer bestimmten Adresse anfängt und sich dann kontinuierlich fortsetzt (von der geringsten Overflowanzahl bis zur höchsten). Jeder Wert ist genau einer Anzahl von Timeroverflows zugeordnet. Somit muss ich nur den Tabellenbeginn in den Z-Pointer laden, dann die doppelte Anzahl der Timer-overflows dazuzählen(wg. 16 bit) und den 16 bit Geschwindigkeitswert mit lpm auslesen. Ich sehe daher keinen Bedarf für einen komplizierten Sortieralgorithmus, da die Werte schon "gebrauchsfertig" im Flash liegen. Damit habe ich zu jedem für meinen Roboter sinnvollen Wert Timerwert den passenden Geschwindigkeitswert (Bereich: ca.9-0.2 km/h). Kleinere Werte werden als 0,00 km/h angezeigt, größere können aus hardwaregründen nicht entstehen, dennoch wird dann sicherheitshalber der Geschwindigkeitswert auf 0xFFFF gesetzt, dass man den Fehler feststellen kann. Der ganze Auslesemechanismus braucht geschätzte 15 Taktzyklen und funktioniert wunderbar.

Gruß Wolli_bolli

[Gock]

Ja ok, damit hast Du die ungültigen Fälle abgefangen, und einen Sortieralgorithmus umgangen, wenn auch 5kB für verbraucht.
Mit 16Bit hat das dann zwar nichts mehr zu tun, wenn Du nur 2500Werte speicherst, aber Du hast von vornherein nicht alle Vorrausetzungen genau genannt, sodass wir das hier nicht beurteilen können.
Ich denke trotzdem, dass Du keine 5kB bräuchtest.
Aber manchmal ist man einfach glücklich damit, dass es funktioniert... ;-)
Viel Spass dabei.
Gruß

[wolli_bolli]

Vorerst passt das so, evt. werde ich mich irgendwann später nochmal damit befassen (z.B. wenn mir der Flashspeicher ausgeht und ich zu geizig bin einen Atmega 624 zu besorgen).
Außerdem möchte ich mich nochmal bei euch für eure Bemühungen bedanken.
Gruß Wolli