Una forma de calcular los logaritmos de base 2

Calcular logaritmos es una operación bastante común en el procesamiento de señales digitales. Más a menudo, tal vez, solo se deben considerar las convoluciones (multiplicación con acumulación) y las amplitudes con fases. Como regla general, para calcular los logaritmos en un FPGA, el algoritmo CORDIC se usa en una versión hiperbólica, que requiere solo tablas y operaciones aritméticas simples. Sin embargo, esto no siempre es conveniente, especialmente si el proyecto es grande, el cristal es pequeño y comienzan los bailes con la optimización. Fue con tal situación que tuve que enfrentar un día. Ambos puertos del bloque RAM (Cyclone IV) ya funcionaban bien, sin dejar ventanas libres. No quería usar otro bloque para CORDIC hiperbólico. Pero había un multiplicador, para el cual se obtuvo una ventana libre decente en el diagrama de tiempo. Después de pensar un día, compuse el siguiente algoritmo, en el que las tablas no se usan, pero hay multiplicación, más exactamente cuadratura. Y dado que la cuadratura del circuito es más simple que el caso general de la multiplicación, quizás este algoritmo sea de interés para chips especializados, aunque, por supuesto, no hay diferencia para FPGA. Más detalles debajo del corte.

Al explicar qué es qué, es más fácil para los números reales. Comencemos con ellos. Pasamos a la implementación de enteros más tarde.

Que haya un número X. Encuentra el número Y tal que $$$X = 2 ^ Y$.
También suponemos que X se encuentra en el rango de 1 a 2. Esto no limita demasiado la generalidad, ya que X siempre se puede transferir a este intervalo por multiplicación o división por una potencia de dos. Para Y, esto significará sumar o restar un número entero, lo cual es fácil. Entonces X se encuentra en el intervalo de 1 a 2. Entonces Y se ubicará en el intervalo de 0 a 1. Escribimos Y como una fracción binaria infinita:

$$

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

Las probabilidades $$${b_i}$en este registro no hay más que solo bits de la representación binaria del número Y. Además, como Y es menor que 1, es obvio que $$${b_0}$= 0.

Cuadremos nuestra primera ecuación: $$$X ^ 2 = 2 ^ {2Y}$y como antes, escribimos la representación binaria de 2Y . Obviamente

$$

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

Es decir pedacitos $$${b_i}$permaneció igual, solo los poderes de dos se movieron. Murciélago $$${b_0}$no está presente en la vista porque es igual a cero.

Son posibles dos casos:

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

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

En el primer caso, tomamos como el nuevo valor de X $$$X ^ 2/2$en el segundo $$$X ^ 2$.

Como resultado, la tarea se redujo a la primera. La nueva X nuevamente se encuentra en el rango de 1 a 2, la nueva Y de 0 a 1. Pero aprendimos un poco del resultado. Tomando los mismos pasos en el futuro, podemos obtener tantos bits de Y como sea posible.

Veamos cómo funciona en un programa en 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; } 

Calculamos el logaritmo con una precisión de 16 bits y lo comparamos con lo que ofrece la biblioteca matemática. El programa trajo:

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

El resultado coincidió con la biblioteca con una precisión del 0,003%, lo que muestra la eficiencia de nuestro algoritmo.

Pasemos a una implementación entera.

Deje que los números binarios sin signo de N bits representen el intervalo [0, 1]. Por conveniencia, consideramos el número de unidad $$$2 ^ N$pero no $$$2 ^ N-1$y, en consecuencia, un número de deuce $$$2 ^ {N + 1}$. Escribiremos un programa a imagen y semejanza del anterior, pero trabajando con enteros:

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

Después de haber jugado en un programa con diferentes profundidades de bits (DIG), precisión de cálculo (N_BITS) y argumentos de logaritmo (w), vemos que todo se calcula correctamente. En particular, con los parámetros especificados en esta fuente, el programa produce:

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

Ahora todo está listo para implementar una pieza de hierro en veril, haciendo exactamente lo mismo que la función myLog en C. Las variables syu en nuestra función pueden imprimirse en un bucle y compararse con lo que produce el simulador verilog. La correspondencia de estas variables con la implementación de hierro es muy transparente y comprensible. u es un registro de trabajo que toma nuevos valores de X durante las iteraciones. s es un registro de desplazamiento en el que se acumula el resultado. La interfaz de nuestro módulo se verá así:

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

El bus de entrada se adopta 18 bits, respectivamente, el ancho de los multiplicadores en el ciclón IV. Los números en nuestro módulo deberían venir normalizados. Es decir con bit alto igual a uno. En mi proyecto, esto se hizo automáticamente. Pero en cuyo caso implementar el normalizador, creo que nadie será difícil. La precisión de los cálculos se establece mediante el parámetro nbits, por defecto igual a 16. El módulo cuenta un bit por ciclo, y para 16 ciclos calcula el logaritmo con una precisión de 16 bits. Si necesita más rápido con la misma precisión o más precisamente con la misma velocidad, espero que nadie tenga muchas dificultades para dividir el módulo en varios dispositivos y canalizarlos.


Ejecute la prueba con este 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 

Al ejecutar la prueba, vemos la salida final del simulador: valor = 27819, resultado = 9ba5. Verilog dio lo mismo que C. El diagrama de tiempos aquí es bastante trivial y no es de particular interés. Por lo tanto, no lo traigo.


Asegúrese de que coincidan poco a poco. En total, la implementación en un verilo repite el modelo C hasta un poco. Este es el resultado que debe lograrse implementando algoritmos en el hardware.

Eso es probablemente todo. Espero que alguien encuentre útil esta experiencia.