Einfache Division in VHDL und ASM

Einfache Division einer Variablen durch eine Konstante mittels mehrfacher bzw. zyklischer Addition des verschobenen Vektors.

von J.S.

Die hier beschriebene Methode eignet sich zur Umsetzung in Controllern, die nicht in C programmierbar sind, bzw. nicht über Multiplikation oder Division verfügen, sowie für FPGAs und PLDs, in denen keine Multiplizierer zur Verfügung stehen, oder genutzt werden sollen.

Methode 1

Eine Division kann bekanntermassen grundsätzlich durch eine inverse Multiplikation erzeugt werden, indem man mit dem Reziprokwert multipliziert und dabei stillschweigend um einen definierten Wert hochskaliert. Z.B. lässt sich der Wert 567 leicht durch 81,3 teilen, indem man für das Ergebnis zusätzlich 8 Bits an Auflösung zulässt. Der Korrekturwert ergäbe sich dann zu (256/81,3 = 3). Eine Multiplikation mit 3 ergäbe einen vergleichweise grossen Fehler. Dieser lässt sich bei Hinzunahme von 16 Stellen auf gut 0,1% senken, da 56536/81,3 = 806,100.

Diese Multiplikation wird in Controllern und FPGAs in der Regel durch Coprozessoren / integrierte Multiplier durchgeführt, wobei in FPGAs die Möglichkeit besteht, es per constraint in eine parallele Addition zu überführen, bei der verschobene Kopieren der Vektoren je nach Notwendigkeit addiert werden.

Um Addierer zu sparen lässt sich das jedoch auf iterativ / sequentiell behandeln:

Methode 2

Jede Ganzzahldivision lässt sich durch eine fortgesetzte Addition von binär geteilten = verschobenen Kopien des Ursprungsvektors darstellen. Z.B. erreicht man eine Dividion durch 3, in dem man 1/4, 1/16, 1/64 etc. des Vektors addiert. Durch das fortwährende Schieben ist eine theoretisch unendliche Auflösung gegeben, da der Endvektor jeweils mitwächst und nicht von vorn herein statisch festgelegt ist. Damit besteht grundsätzlich die Möglichkeit, dynamisch genuu zu rechen, bzw die Genauigkeit den aktuellen Erfodernissen in Echtzeit anzupassen, z.B. beim Finden von Lösungen, bei denen das Erreichen einer gewissen Genauigkeit ein Abbruchkriterim darstellt.

Beispiel

Die unbekannte Zahl (hier 157) soll durch 3 diviert werden. Die Iteration erfolgt so, dass jeweils immer der um 2 Stellen nach rechts verschobene Vektor der Zahl selbst zu laufenden Summe hinzu addiert wird. Nach 7 Iterationen ergibt sich hier ein Vektor mit 20 Bit Auflösung im Format 8.12.

1 0 0 1 1 1 0 1

   1 0 0 1 1 1 0 1                     = 1/4 x
       1 0 0 1 1 1 0 1                 = 1/16 x
           1 0 0 1 1 1 0 1
               1 0 0 1 1 1 0 1
                   1 0 0 1 1 1 0 1
                       1 0 0 1 1 1 0 1

0 0 1 1 0 1 0 0_0 1 0 1 0 0 1 0_0 0 0 1 = x/3

= 52 + 82/256 + 1/256/16 = 52,32

Eine Division durch 7 lässt sich mit nur 4 Vektoren (1/8 + 1/64 + 1/512 + 1/4096) auf 0,1% genau durchführen. Für weitere Divisionen mit 9,11,13,17 .. etc lässt sich eine Tabelle mit Excel oder MATLAB erzeugen.

Links

• Konstante