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.

Allgemeines

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

Gegeben sei die Iterationsvorschrift

L_{n+1}=L_{n}\cdot (1+d_{n}\cdot 2^{-n})

E_{n+1}=E_{n}-\ln(1+d_{n}\cdot 2^{-n})

mit $L,E\in \mathbb {C}$ und $d_{n}\in \{-1,0,1,-i,i,1-i,1+i,-1-i,-1+i\}$ . Die neun Fälle für $d_{n}$ ergeben sich aus zwei unabhängigen Fallunterscheidungen für Real- und Imaginärteil:

\operatorname {Re} \{d_{n}\}\in \{-1,0,1\}

\operatorname {Im} \{d_{n}\}\in \{-1,0,1\}

.

Für die komplexe Multiplikation aus der Iterationsvorschrift

L_{n+1}=L_{n}\cdot (1+d_{n}\cdot 2^{-n})=L_{n}+L_{n}\cdot d_{n}\cdot 2^{-n}

sind die Operationen Addition, Fallunterscheidung und Bitshift ausreichend. Eine echte Multiplikation wird nicht benötigt. Die Iteration für $E$ 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 $d_{n}$ . 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

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

\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}}\leq &\operatorname {Re} \{2^{n}E_{n}\}\leq {\phantom {-}}{\frac {1}{4}}\\+1&{\text{falls }}{\phantom {-}}{\frac {1}{4}}<&\operatorname {Re} \{2^{n}E_{n}\}\\\end{cases}}

\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}}\leq &\operatorname {Im} \{2^{n}E_{n}\}\leq {\phantom {-}}{\frac {3}{4}}\\+1&{\text{falls }}{\phantom {-}}{\frac {3}{4}}<&\operatorname {Im} \{2^{n}E_{n}\}\\\end{cases}}

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

L-Mode

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

\operatorname {Re} \{d_{n}\}={\begin{cases}+1&{\text{falls }}&\operatorname {Re} \{\epsilon _{n}\}<-{\frac {1}{2}}\\{\phantom {-}}0&{\text{falls }}-{\frac {1}{2}}\leq &\operatorname {Re} \{\epsilon _{n}\}\leq {\phantom {-}}{\frac {1}{2}}\\-1&{\text{falls }}{\phantom {-}}{\frac {1}{2}}<&\operatorname {Re} \{\epsilon _{n}\}\\\end{cases}}

\operatorname {Im} \{d_{n}\}={\begin{cases}+1&{\text{falls }}&\operatorname {Im} \{\epsilon _{n}\}<-{\frac {1}{2}}\\{\phantom {-}}0&{\text{falls }}-{\frac {1}{2}}\leq &\operatorname {Im} \{\epsilon _{n}\}\leq {\phantom {-}}{\frac {1}{2}}\\-1&{\text{falls }}{\phantom {-}}{\frac {1}{2}}<&\operatorname {Im} \{\epsilon _{n}\}\\\end{cases}}

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

Literatur

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

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

Einzelnachweise

↑ 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.

[1] 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.