BKM-Algorithmus

Der BKM-Algorithmus ist ein iterativer Algorithmus, mit dessen Hilfe sich die Logarithmus- und Exponentialfunktion effizient in digitalen Schaltungen berechnen lassen. Er wurde 1994 von J. C. Bajard, S. Kla und Jean-Michel Muller entwickelt, wovon sich auch die Bezeichnung ableitet.<ref>J. Bajard, S. Kla, Jean-Michel Muller: A new hardware algorithm for complex elementary functions. In: IEEE Transactions on Computers. Band 43, Nr. 8, 1994, ISSN 0018-9340, S. 955–963, doi:10.1109/12.295857. </ref>

Allgemeines[Bearbeiten]

Der BKM-Algorithmus ist wie CORDIC-Algorithmus ein so genannter Shift-and-add-Algorithmus, der auf bitweisen Verschiebungen und ganzzahligen Additionen in Addierwerken basiert. Divisionen werden ausschließlich mit negativen Potenzen von 2 durchgeführt, welche sich in digitalen Schaltungen direkt als bitweise Verschiebung implementieren lassen. Der Algorithmus kommt im Gegensatz zu dem CORDIC-Verfahren ohne Skalierungsfaktor aus und verwendet Logarithmentabellen anstelle der bei CORDIC notwendigen Arkustangens-Tabelle.

Die Berechnung eines Funktionswertes erfolgt in einem Iterationsverfahren mit einer Konvergenzrate von ungefähr einem Bit pro Durchlauf. Aufgrund dieses Umstands wird dieser Algorithmus manchmal auch als Bitalgorithmus bezeichnet.

Algorithmus[Bearbeiten]

Gegeben sei die Iterationsvorschrift

mit <math>L, E \in \C</math> und <math>d_n \in \{-1,0,1,-i,i,1-i,1+i,-1-i,-1+i\}</math>. Die neun Fälle für <math>d_n</math> ergeben sich aus zwei unabhängigen Fallunterscheidungen für Real- und Imaginärteil:

<math>\operatorname{Re}\{d_n\} \in \{-1,0,1\}</math>

<math>\operatorname{Im}\{d_n\} \in \{-1,0,1\}</math>.

Für die komplexe Multiplikation aus der Iterationsvorschrift

sind die Operationen Addition, Fallunterscheidung und Bitshift ausreichend. Eine echte Multiplikation wird nicht benötigt. Die Iteration für <math>E</math> benötigt einen Tabellen-Lookup für den Logarithmus und eine Subtraktion. Die Tabelle hat eine Zeile pro Iterationsschritt und neun komplexwertige Spalten für die neun möglichen Werte von <math>d_n</math>. Manche Spalten sind immer reell oder sind das komplex konjugierte einer anderen Spalte, so dass sich der real benötigte Speicherplatz erheblich reduzieren lässt.

E-Mode[Bearbeiten]

Zur Berechnung der komplexen Exponentialfunktion (E-Mode) ist <math>E</math> als Argument gegeben und <math>L</math> wird mit eins initialisiert. Die <math>d_n</math> werden in jedem Schritt so gewählt, dass <math>E</math> gegen null konvergiert. Wenn der Algorithmus endet, kann das Ergebnis in <math>L</math> abgelesen werden. Die Fallunterscheidung in jedem Schritt lautet:

<math>\operatorname{Re}\{d_n\} = \begin{cases}

  -1 &\text{falls } & \operatorname{Re}\{2^n E_n\} < -\frac{1}{2} \\
  \phantom{-}0 &\text{falls }-\frac{1}{2} \le & \operatorname{Re}\{2^n E_n\} \le \phantom{-}\frac{1}{4} \\
  +1 &\text{falls } \phantom{-}\frac{1}{4} < & \operatorname{Re}\{2^n E_n\} \\
\end{cases}</math>

<math>\operatorname{Im}\{d_n\} = \begin{cases}

  -1 &\text{falls } & \operatorname{Im}\{2^n E_n\} < -\frac{3}{4} \\
  \phantom{-}0 &\text{falls }-\frac{3}{4} \le & \operatorname{Im}\{2^n E_n\} \le \phantom{-}\frac{3}{4} \\
  +1 &\text{falls } \phantom{-}\frac{3}{4} < & \operatorname{Im}\{2^n E_n\} \\
\end{cases}</math>

In einer realen Implementierung wird <math>E</math> nach jedem Iterationsschritt um ein Bit nach links geschoben, so dass in der Fallunterscheidung mit <math>\operatorname{Re}\{E_n\}</math> statt mit <math>\operatorname{Re}\{2^n E_n\}</math> gearbeitet werden kann. Die Einträge der Logarithmentabelle sind passend dazu ebenfalls nach links verschoben, d.h. Zeile <math>n</math> der Tabelle enthält <math>2^n\ln(1+d_n \cdot 2^{-n})</math> für alle neun Fälle von <math>d_n</math>.

L-Mode[Bearbeiten]

Für den komplexen Logarithmus (L-Mode) wird umgekehrt vorgegangen. <math>L</math> ist als Argument gegeben und <math>E</math> wird mit null initialisiert. Die <math>d_n</math> werden in jedem Schritt so gewählt, dass <math>L</math> gegen eins konvergiert. Am Ende wird das Ergebnis in <math>E</math> abgelesen. Wir definieren den Fehler <math>\epsilon_n = 2^n(L_n-1)</math> und darauf die Fallunterscheidung:

<math>\operatorname{Re}\{d_n\} = \begin{cases}

  +1 &\text{falls } & \operatorname{Re}\{\epsilon_n\} < -\frac{1}{2} \\
  \phantom{-}0 &\text{falls }-\frac{1}{2} \le & \operatorname{Re}\{\epsilon_n\} \le \phantom{-}\frac{1}{2} \\
  -1 &\text{falls } \phantom{-}\frac{1}{2} < & \operatorname{Re}\{\epsilon_n\} \\
\end{cases}</math>

<math>\operatorname{Im}\{d_n\} = \begin{cases}

  +1 &\text{falls } & \operatorname{Im}\{\epsilon_n\} < -\frac{1}{2} \\
  \phantom{-}0 &\text{falls }-\frac{1}{2} \le & \operatorname{Im}\{\epsilon_n\} \le \phantom{-}\frac{1}{2} \\
  -1 &\text{falls } \phantom{-}\frac{1}{2} < & \operatorname{Im}\{\epsilon_n\} \\
\end{cases}</math>

Auch hier wird in einer realen Implementierung <math>\epsilon_{n+1}</math> direkt aus <math>\epsilon_n</math> berechnet, ohne den Umweg über <math>L_{n}</math> und <math>L_{n+1}</math>. Dabei wird <math>L</math> nach der Initialisierung überhaupt nicht mehr benötigt, sondern nur noch <math>\epsilon \to 0</math> iteriert.

Literatur[Bearbeiten]

Jean-Michel Muller: Elementary Functions. Algorithms and Implementation. 2. Auflage. Birkhäuser, Boston MA u. a. 2006, ISBN 0-8176-4372-9.
Günter Jorke, Bernhard Lampe, Norbert Wengel: Arithmetische Algorithmen der Mikrorechentechnik. 1. Auflage. VEB Verlag Technik, Berlin 1989, ISBN 3-341-00515-3, S. 280–282 (books.google.de – EAN: 9783341005156).

Weblinks[Bearbeiten]

BKM: A New Hardware Algorithm for Complex Elementary Functions. (PDF; 978 kB).

Einzelnachweise[Bearbeiten]