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

Ln+1=Ln⋅(1+dn⋅2−n)
En+1=En−ln⁡(1+dn⋅2−n)

mit L,E∈ℂ und dn∈{−1,0,1,−i,i,1−i,1+i,−1−i,−1+i}. Die neun Fälle für dn ergeben sich aus zwei unabhängigen Fallunterscheidungen für Real- und Imaginärteil:

Re⁡{dn}∈{−1,0,1}
Im⁡{dn}∈{−1,0,1}.

Für die komplexe Multiplikation aus der Iterationsvorschrift

Ln+1=Ln⋅(1+dn⋅2−n)=Ln+Ln⋅dn⋅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 dn. 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 dn 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:

Re⁡{dn}={−1falls Re⁡{2nEn}<−12−0falls −12≤Re⁡{2nEn}≤−14+1falls −14<Re⁡{2nEn}
Im⁡{dn}={−1falls Im⁡{2nEn}<−34−0falls −34≤Im⁡{2nEn}≤−34+1falls −34<Im⁡{2nEn}

In einer realen Implementierung wird E nach jedem Iterationsschritt um ein Bit nach links geschoben, so dass in der Fallunterscheidung mit Re⁡{En} statt mit Re⁡{2nEn} gearbeitet werden kann. Die Einträge der Logarithmentabelle sind passend dazu ebenfalls nach links verschoben, d. h. Zeile n der Tabelle enthält 2nln⁡(1+dn⋅2−n) für alle neun Fälle von dn.

L-Mode

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

Re⁡{dn}={+1falls Re⁡{ϵn}<−12−0falls −12≤Re⁡{ϵn}≤−12−1falls −12<Re⁡{ϵn}
Im⁡{dn}={+1falls Im⁡{ϵn}<−12−0falls −12≤Im⁡{ϵn}≤−12−1falls −12<Im⁡{ϵn}

Auch hier wird in einer realen Implementierung ϵn+1 direkt aus ϵn berechnet, ohne den Umweg über Ln und Ln+1. Dabei wird L nach der Initialisierung überhaupt nicht mehr benötigt, sondern nur noch ϵ→0 iteriert.