Eine Möglichkeit zur Berechnung von Logarithmen zur Basis 2

Das Berechnen von Logarithmen ist eine ziemlich häufige Operation in der digitalen Signalverarbeitung. Häufiger sollten vielleicht nur Windungen (Multiplikation mit Akkumulation) und Amplituden mit Phasen berücksichtigt werden. Zur Berechnung der Logarithmen auf einem FPGA wird in der Regel der CORDIC-Algorithmus in einer hyperbolischen Version verwendet, die nur Tabellen und einfache arithmetische Operationen erfordert. Dies ist jedoch nicht immer praktisch, insbesondere wenn das Projekt groß ist, der Kristall klein ist und Tänze mit Optimierung beginnen. In einer solchen Situation musste ich mich eines Tages stellen. Beide Ports des RAM-Blocks (Cyclone IV) arbeiteten bereits fest und ließen keine freien Fenster übrig. Ich wollte keinen anderen Block für hyperbolisches CORDIC verwenden. Es gab jedoch einen Multiplikator, für den im Zeitdiagramm ein anständiges freies Fenster erhalten wurde. Nachdem ich einen Tag nachgedacht hatte, komponierte ich den folgenden Algorithmus, in dem Tabellen nicht verwendet werden, aber es gibt eine Multiplikation, genauer gesagt eine Quadrierung. Und da das Quadrieren von Schaltkreisen einfacher ist als der allgemeine Fall der Multiplikation, ist dieser Algorithmus möglicherweise für spezialisierte Chips von Interesse, obwohl es für FPGA natürlich keinen Unterschied gibt. Weitere Details unter dem Schnitt.

Erklären, was was ist, ist für reelle Zahlen einfacher. Beginnen wir mit ihnen. Wir fahren später mit der Ganzzahlimplementierung fort.

Es gebe eine Zahl X. Finden Sie die Zahl Y so, dass $$$X = 2 ^ Y$.
Wir nehmen auch an, dass X im Bereich von 1 bis 2 liegt. Dies schränkt die Allgemeinheit nicht zu sehr ein, da X immer durch Multiplikation oder Division mit einer Zweierpotenz in dieses Intervall übertragen werden kann. Für Y bedeutet dies, dass eine ganze Zahl addiert oder subtrahiert wird, was einfach ist. X liegt also im Intervall von 1 bis 2. Dann liegt Y im Intervall von 0 bis 1. Wir schreiben Y als unendlichen binären Bruch:

$$

$$Y = {b_0} 2 ^ 0 + {b_1} 2 ^ {- 1} + ... + {b_n} 2 ^ {- n} + ...$$

Chancen $$${b_i}$In diesem Datensatz gibt es nichts weiter als nur Bits der binären Darstellung der Zahl Y. Da Y kleiner als 1 ist, ist es außerdem offensichtlich, dass $$${b_0}$= 0.

Quadrieren wir unsere erste Gleichung: $$$X ^ 2 = 2 ^ {2Y}$und wie zuvor schreiben wir die binäre Darstellung von 2Y . Offensichtlich

$$

$$2Y = {b_1} 2 ^ 0 + {b_2} 2 ^ {- 1} + ... + {b_n} 2 ^ {- (n-1)} + ...$$

Das heißt, Bits $$${b_i}$blieb gleich, nur die Kräfte von zwei bewegten sich. Fledermaus $$${b_0}$nicht in der Ansicht vorhanden, da es gleich Null ist.

Zwei Fälle sind möglich:

1) $$$X ^ 2> 2$, 2Y> 1, $$${b_1} = 1$

2) $$$X ^ 2 <2$, 2Y <1, $$${b_1} = 0$

Im ersten Fall nehmen wir als neuen Wert von X. $$$X ^ 2/2$in der zweiten - $$$X ^ 2$.

Infolgedessen wurde die Aufgabe auf die erstere reduziert. Das neue X liegt wieder im Bereich von 1 bis 2, das neue Y von 0 bis 1. Aber wir haben ein bisschen vom Ergebnis gelernt. Wenn wir in Zukunft die gleichen Schritte unternehmen, können wir so viele Y- Bits wie möglich erhalten.

Mal sehen, wie es in einem C-Programm funktioniert:

#include <stdio.h> #include <math.h> int main() { double w=1.4; double s=0.0; double a=0.5; double u=w; for(int i=0; i<16; i++) { u=u*u; if(u>2) { u=u/2; s+=a; } a*=0.5; } w=log2(w); double err=100*abs(2*(sw)/(s+w)); printf("res=%f, log=%f, err=%f%c\n",s,w,err,'%'); return 0; } 

Wir haben den Logarithmus mit einer Genauigkeit von 16 Bit berechnet und mit dem verglichen, was die mathematische Bibliothek liefert. Das Programm brachte:

res = 0,485413, log = 0,485427, err = 0,002931%

Das Ergebnis stimmte mit der Bibliothek mit einer Genauigkeit von 0,003% überein, was die Effizienz unseres Algorithmus zeigt.

Fahren wir mit einer ganzzahligen Implementierung fort.

Lassen Sie N-Bit-Binärzahlen ohne Vorzeichen das Intervall [0, 1] darstellen. Der Einfachheit halber berücksichtigen wir die Einheitennummer $$$2 ^ N$, und nicht $$$2 ^ N-1$und dementsprechend eine Zweizahl $$$2 ^ {N + 1}$. Wir werden ein Programm im Bild und in der Ähnlichkeit des vorherigen schreiben, aber mit ganzen Zahlen arbeiten:

 #include <stdio.h> #include <math.h> #define DIG 18 //  #define N_BITS 16 //    unsigned ONE=1<<(DIG-1); // unsigned TWO=ONE<<1; // unsigned SCALE=1<<(N_BITS+1); //  unsigned myLog(unsigned w) { unsigned s=0; unsigned long long u=w; for(int i=0; i<N_BITS+1; i++) { s<<=1; u=(u*u)>>(DIG-1); //    ! if(u&TWO) //      { u>>=1; s+=1; } printf("%X\n", (int)u); } return s; } int main() { double w=1.2345678; unsigned iw=(unsigned)(ONE*w); double dlog=log2(w); unsigned ilog=myLog(iw); unsigned test=(unsigned)(SCALE*dlog); int err=abs((int)(ilog-test)); printf("val=0x%X, res=0x%X, log=0x%X, err=%d\n",iw,ilog,test,err); return 0; } 

Nachdem wir in einem Programm mit unterschiedlichen Bittiefen (DIG), Berechnungsgenauigkeit (N_BITS) und Logarithmusargumenten (w) gespielt haben, sehen wir, dass alles korrekt berechnet wird. Insbesondere mit den in dieser Quelle angegebenen Parametern erzeugt das Programm:

val = 0x27819, res = 0x9BA5, log = 0x9BA6, err = 1

Jetzt ist alles bereit, um ein Stück Eisen auf Veril zu implementieren, und zwar genau so wie die myLog- Funktion in C. Die Variablen s und u in unserer Funktion können in einer Schleife gedruckt und mit dem verglichen werden, was der Verilog-Simulator erzeugt. Die Entsprechung dieser Variablen zur Eisenimplementierung ist sehr transparent und verständlich. u ist ein Arbeitsregister, das während der Iterationen neue Werte von X annimmt. s ist ein Schieberegister, in dem das Ergebnis akkumuliert wird. Die Schnittstelle unseres Moduls sieht folgendermaßen aus:

 module logarithm( input clk, // input wr, //   input[17:0] din, //   output[nbits-1:0] dout, //   output rdy //  ); parameter nbits=16; //  

Der Eingangsbus wird mit 18 Bit bzw. der Breite der Multiplikatoren im Zyklon IV übernommen. Die Zahlen auf unserem Modul sollten normalisiert sein. Das heißt, mit hohem Bit gleich eins. In meinem Projekt wurde dies automatisch durchgeführt. Aber in diesem Fall, um den Normalisierer zu implementieren, denke ich, dass niemand schwierig sein wird. Die Genauigkeit der Berechnungen wird durch den Parameter nbits festgelegt, der standardmäßig 16 beträgt. Das Modul zählt ein Bit pro Zyklus und berechnet für 16 Zyklen den Logarithmus mit einer Genauigkeit von 16 Bit. Wenn Sie schneller mit der gleichen Genauigkeit oder genauer mit der gleichen Geschwindigkeit benötigen, hoffe ich, dass niemand große Schwierigkeiten haben wird, das Modul in mehrere Geräte und Pipelining aufzuteilen.


Führen Sie den Test mit diesem Skript aus:

 #!/bin/sh rm -f *.vvp rm -f *.vcd iverilog -o testbench.vvp logarithm.v testbench.v vvp testbench.vvp gtkwave testbench.vcd testbench.gtkw 

Wenn wir den Test ausführen, sehen wir die endgültige Ausgabe des Simulators - Wert = 27819, Ergebnis = 9ba5. Verilog gab das Gleiche wie C. Das Zeitdiagramm hier ist ziemlich trivial und nicht von besonderem Interesse. Deshalb bringe ich es nicht.


Stellen Sie sicher, dass sie Stück für Stück übereinstimmen. Insgesamt wiederholt die Implementierung auf einem Verilo das C-Modell bis zu einem gewissen Grad. Dies ist das Ergebnis, das durch die Implementierung von Algorithmen in Hardware erzielt werden sollte.

Das ist wahrscheinlich alles. Ich hoffe, jemand wird dies meine Erfahrung nützlich finden.