Uma maneira de calcular logaritmos da base 2

Computar logaritmos é uma operação bastante comum no processamento de sinais digitais. Mais frequentemente, talvez, apenas convoluções (multiplicação com acumulação) e amplitudes com fases devam ser consideradas. Como regra, para calcular os logaritmos em um FPGA, o algoritmo CORDIC é usado em uma versão hiperbólica, exigindo apenas tabelas e operações aritméticas simples. No entanto, isso nem sempre é conveniente, especialmente se o projeto é grande, o cristal é pequeno e a dança com otimização começa. Foi com tal situação que tive que enfrentar um dia. As duas portas do bloco de RAM (Cyclone IV) já estavam funcionando bem, sem deixar janelas livres. Eu não queria usar outro bloco para o CORDIC hiperbólico. Mas havia um multiplicador, para o qual uma janela livre decente foi obtida no diagrama de tempo. Depois de pensar um dia, compus o seguinte algoritmo, no qual tabelas não são usadas, mas há multiplicação, mais precisamente ao quadrado. E como o quadrado do circuito é mais simples que o caso geral de multiplicação, talvez esse algoritmo seja do interesse de chips especializados, embora, é claro, não haja diferença para o FPGA. Mais detalhes sob o corte.

Explicando o que é o quê, é mais fácil para números reais. Vamos começar com eles. Prosseguimos para a implementação inteira mais tarde.

Que haja um número X. Encontre o número Y tal que $$$X = 2 ^ Y$ .
Também assumimos que X está no intervalo de 1 a 2. Isso não limita demais a generalidade, pois X sempre pode ser transferido para esse intervalo por multiplicação ou divisão por uma potência de dois. Para Y, isso significa adicionar ou subtrair um número inteiro, o que é fácil. Então X fica no intervalo de 1 a 2. Então Y fica no intervalo de 0 a 1. Escrevemos Y como uma fração binária infinita:

$$

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

Odds $$${b_i}$ nesse registro, não há nada além de bits da representação binária do número Y. Além disso, como Y é menor que 1, é óbvio que $$${b_0}$ = 0.

Vamos quadrar nossa primeira equação: $$$X ^ 2 = 2 ^ {2A}$ e, como antes, escrevemos a representação binária de 2Y . Obviamente,

$$

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

I.e. bits $$${b_i}$ permaneceu o mesmo, apenas os poderes de dois se moveram. Morcego $$${b_0}$ não está presente na visualização porque é igual a zero.

Dois casos são possíveis:

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

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

No primeiro caso, tomamos como o novo valor de X $$$X ^ 2/2$ no segundo - $$$X ^ 2$ .

Como resultado, a tarefa foi reduzida para a primeira. O novo X novamente está no intervalo de 1 a 2, o novo Y de 0 a 1. Mas aprendemos um pouco do resultado. Seguindo os mesmos passos no futuro, podemos obter o máximo de Y possível.

Vamos ver como isso funciona em um programa 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 o logaritmo com uma precisão de 16 bits e comparamos com o que a biblioteca matemática fornece. O programa trouxe:

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

O resultado coincidiu com a biblioteca com uma precisão de 0,003%, o que mostra a eficiência do nosso algoritmo.

Vamos passar para uma implementação inteira.

Deixe que os números não assinados binários de N bits representem o intervalo [0, 1]. Por conveniência, consideramos o número da unidade $$$2 ^ N$ mas não $$$2 ^ N-1$ e, consequentemente, um número empate $$$2 ^ {N + 1}$ . Escreveremos um programa à imagem e semelhança do anterior, mas trabalhando com números inteiros:

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

Tendo reproduzido em um programa com diferentes profundidades de bits (DIG), precisão de cálculo (N_BITS) e argumentos de logaritmo (w), vemos que tudo é calculado corretamente. Em particular, com os parâmetros especificados nesta fonte, o programa produz:

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

Agora tudo está pronto para implementar um pedaço de ferro no veril, fazendo exatamente a mesma coisa que a função myLog em C. As variáveis s e u em nossa função podem ser impressas em um loop e comparadas com o que o simulador de verilog produz. A correspondência dessas variáveis ​​para a implementação do ferro é muito transparente e compreensível. u é um registro de trabalho que recebe novos valores de X durante as iterações. s é um registro de turno no qual o resultado é acumulado. A interface do nosso módulo ficará assim:

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

O barramento de entrada é adotado em 18 bits, respectivamente, a largura dos multiplicadores no Ciclone IV. Os números em nosso módulo devem ser normalizados. I.e. com bit alto igual a um. No meu projeto, isso foi feito automaticamente. Mas, nesse caso, para implementar o normalizador, acho que ninguém será difícil. A precisão dos cálculos é definida pelo parâmetro nbits, por padrão igual a 16. O módulo conta um bit por ciclo e, por 16 ciclos, calcula o logaritmo com uma precisão de 16 bits. Se você precisar mais rápido com a mesma precisão ou mais precisamente com a mesma velocidade, espero que ninguém tenha muita dificuldade em dividir o módulo em vários dispositivos e pipelining.


Execute o teste com 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 

Executando o teste, vemos a saída final do simulador - valor = 27819, resultado = 9ba5. Verilog deu a mesma coisa que C. O diagrama de tempo aqui é bastante trivial e não é de particular interesse. Portanto, eu não trago.


Certifique-se de que correspondam pouco a pouco. No total, a implementação em um verilo repete até um pouco o modelo C. Esse é o resultado que deve ser alcançado com a implementação de algoritmos no hardware.

Provavelmente é tudo. Espero que alguém ache útil essa minha experiência.