Une façon de calculer les logarithmes en base 2

Le calcul des logarithmes est une opération assez courante dans le traitement numérique du signal. Plus souvent, peut-être, seules les convolutions (multiplication avec accumulation) et les amplitudes avec phases doivent être prises en compte. En règle générale, pour calculer les logarithmes sur un FPGA, l'algorithme CORDIC est utilisé dans une version hyperbolique, ne nécessitant que des tables et des opérations arithmétiques simples. Cependant, ce n'est pas toujours pratique, surtout si le projet est grand, le cristal est petit et les danses avec optimisation commencent. C'est avec une telle situation que j'ai dû faire face un jour. Les deux ports du bloc RAM (Cyclone IV) fonctionnaient déjà étroitement, ne laissant aucune fenêtre libre. Je ne voulais pas utiliser un autre bloc pour CORDIC hyperbolique. Mais il y avait un multiplicateur, pour lequel une fenêtre libre décente a été obtenue dans le diagramme du temps. Après avoir réfléchi un jour, j'ai composé l'algorithme suivant, dans lequel les tableaux ne sont pas utilisés, mais il y a multiplication, plus précisément quadrature. Et comme la quadrature des circuits est plus simple que le cas général de la multiplication, cet algorithme est peut-être intéressant pour les puces spécialisées, bien qu'il n'y ait bien sûr aucune différence pour le FPGA. Plus de détails sous la coupe.

Expliquer ce qui est quoi, c'est plus facile pour les vrais nombres. Commençons par eux. Nous procédons à l'implémentation entière plus tard.

Soit un nombre X. Trouvez le nombre Y tel que $$$X = 2 ^ Y$ .
Nous supposons également que X est compris entre 1 et 2. Cela ne limite pas trop la généralité, car X peut toujours être transféré à cet intervalle par multiplication ou division par une puissance de deux. Pour Y, cela signifie ajouter ou soustraire un entier, ce qui est facile. Donc X se situe dans l'intervalle de 1 à 2. Alors Y se situera dans l'intervalle de 0 à 1. Nous écrivons Y comme une fraction binaire infinie:

$$

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

Cotes $$${b_i}$ dans cet enregistrement, il n'y a rien de plus que des bits de la représentation binaire du nombre Y. De plus, comme Y est inférieur à 1, il est évident que $$${b_0}$ = 0.

Équilibrons notre première équation: $$$X ^ 2 = 2 ^ {2Y}$ et comme précédemment, nous écrivons la représentation binaire de 2Y . De toute évidence,

$$

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

C'est-à-dire bits $$${b_i}$ est resté le même, seuls les pouvoirs de deux se sont déplacés. Bat $$${b_0}$ non présent dans la vue car il est égal à zéro.

Deux cas sont possibles:

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

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

Dans le premier cas, nous prenons comme nouvelle valeur de X $$$X ^ 2/2$ dans le second - $$$X ^ 2$ .

En conséquence, la tâche a été réduite à la première. Le nouveau X se situe à nouveau dans la plage de 1 à 2, le nouveau Y de 0 à 1. Mais nous avons appris un bit du résultat. En suivant les mêmes étapes à l'avenir, nous pouvons obtenir autant de bits de Y que possible.

Voyons comment cela fonctionne dans un programme C:

#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; } 

Nous avons calculé le logarithme avec une précision de 16 bits et comparé à ce que donne la bibliothèque mathématique. Le programme a apporté:

res = 0.485413, log = 0.485427, err = 0.002931%

Le résultat a coïncidé avec la bibliothèque avec une précision de 0,003%, ce qui montre l'efficacité de notre algorithme.

Passons à une implémentation entière.

Soit des nombres binaires non signés à N bits représentant l'intervalle [0, 1]. Pour plus de commodité, nous considérons le numéro d'unité $$$2 ^ N$ mais pas $$ , et en conséquence un numéro de deux $$$2 ^ {N + 1}$ . Nous allons écrire un programme à l'image et à la ressemblance du précédent, mais en travaillant avec des entiers:

 #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; } 

Après avoir joué dans un programme avec différentes profondeurs de bits (DIG), précision de calcul (N_BITS) et arguments de logarithme (w), nous voyons que tout est calculé correctement. En particulier, avec les paramètres spécifiés dans cette source, le programme produit:

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

Maintenant, tout est prêt à implémenter un morceau de fer sur Veril, faisant exactement la même chose que la fonction myLog en C. Les variables s et u de notre fonction peuvent être imprimées en boucle et comparées à ce que le simulateur Verilog produit. La correspondance de ces variables avec l'implémentation de fer est très transparente et compréhensible. u est un registre de travail qui prend de nouvelles valeurs de X pendant les itérations. s est un registre à décalage dans lequel le résultat est accumulé. L'interface de notre module ressemblera à ceci:

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

Le bus d'entrée est adopté sur 18 bits, respectivement, la largeur des multiplicateurs dans le Cyclone IV. Les chiffres sur notre module devraient être normalisés. C'est-à-dire avec un bit élevé égal à un. Dans mon projet, cela s'est fait automatiquement. Mais dans ce cas, pour mettre en œuvre le normalisateur, je pense que ce n'est difficile pour personne. La précision des calculs est définie par le paramètre nbits, par défaut égal à 16. Le module compte un bit par cycle et pendant 16 cycles, il calcule le logarithme avec une précision de 16 bits. Si vous avez besoin plus rapidement avec la même précision ou plus précisément avec la même vitesse, j'espère que personne n'aura beaucoup de difficulté à diviser le module en plusieurs appareils et pipelining.


Exécutez le test avec ce script:

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

En exécutant le test, nous voyons la sortie finale du simulateur - valeur = 27819, résultat = 9ba5. Verilog a donné la même chose que C. Le chronogramme ici est assez trivial et n'a pas d'intérêt particulier. Par conséquent, je ne l'apporte pas.


Assurez-vous qu'ils correspondent petit à petit. Au total, l'implémentation sur un verilo répète un peu le modèle C. C'est le résultat qui devrait être obtenu en implémentant des algorithmes dans le matériel.

C’est probablement tout. J'espère que quelqu'un trouvera cette expérience utile.