algorithm - Como obter uma raiz quadrada para entrada de 32 bits em apenas um ciclo de clock?




integer verilog (3)

Eu tenho o código aqui, é

    module sqrt(
input[31:0]a,
output[15:0]out
    );
reg [31:0]temp;
reg[14:0]x;

[email protected](a)
begin
if(a<257)x=4;
if(a>256 && a<65537)x=80;
if(a>65536 && a<16777217)x=1000;
if(a>16777216 && a<=4294967295)x=20000;
temp=(x+(a/x))/2;
temp=(temp+(a/temp))/2;
temp=(temp+(a/temp))/2;
temp=(temp+(a/temp))/2;
temp=(temp+(a/temp))/2;
temp=(temp+(a/temp))/2;
temp=(temp+(a/temp))/2;
end

assign out=temp;
endmodule

Eu quero projetar um módulo sintetizável em Verilog que levará apenas um ciclo no cálculo da raiz quadrada da entrada dada de 32 bits.


Há conversão para um logaritmo, metade e conversão de volta.
Para uma idéia de como implementar log combinatório e antilog , consulte o artigo de EDN de Michael Dunn mostrando o codificador de prioridade, barril e tabela de consulta, com três variantes de log no System Verilog para download .
(O codificador de prioridade, barril shifter e lookup table parece promissor para "one-step-Babylonian / Heron / Newton / -Raphson. Mas isso provavelmente ainda precisaria de uma tabela de consulta de 128K por 9 bits.)

Embora não apresentando "verilog",
Tole Sutikno: "Um Algoritmo de Raiz Quadrada Otimizado para Implementação em Hardware FPGA" mostra uma implementação combinatória de um algoritmo de dígito por dígito modificado (binário).


[Edit1] código reparado

Recentemente descobri os resultados, mesmo que os testes determinassem que tudo estava OK, então eu investiguei mais e descobri que eu tinha um bug bobo na minha equação e devido a conflitos de nome com o meu ambiente pgm, os testes obtiveram falsos positivos, então eu ignorei isso antes. Agora funciona em todos os casos como deveria.

A melhor coisa que posso pensar (exceto aproximação ou LUT grande) é a busca binária sem multiplicação, aqui código C ++ :

//---------------------------------------------------------------------------
WORD u32_sqrt(DWORD xx) // 16 T
    {
    DWORD x,m,a0,a1,i;
    const DWORD lut[16]=
        {
        //     m*m
        0x40000000,
        0x10000000,
        0x04000000,
        0x01000000,
        0x00400000,
        0x00100000,
        0x00040000,
        0x00010000,
        0x00004000,
        0x00001000,
        0x00000400,
        0x00000100,
        0x00000040,
        0x00000010,
        0x00000004,
        0x00000001,
        };
    for (x=0,a0=0,m=0x8000,i=0;m;m>>=1,i++)
        {
        a1=a0+lut[i]+(x<<(16-i));
        if (a1<=xx) { a0=a1; x|=m; }
        }
    return x;
    }
//---------------------------------------------------------------------------

A pesquisa binária padrão sqrt(xx) está configurando bits de x de MSB para LSB, de modo que o resultado de x*x <= xx . Felizmente podemos evitar a multiplicação simplesmente reescrevendo a coisa como incrementando o multiplicador ... em cada iteração o resultado x*x mais antigo pode ser usado assim:

x1 = x0+m
x1*x1 = (x0+m)*(x0+m) = (x0*x0) + (2*m*x0) + (m*m)

Onde x0 é o valor de x da última iteração e x1 é o valor real. O m é o peso do bit processado real. Os (2*m) e (m*m) são constantes e podem ser usados ​​como LUT e bit-shift, então não há necessidade de multiplicar. Apenas a adição é necessária. Infelizmente, a iteração está fadada ao cálculo seqüencial e proíbe a paralelização, de modo que o resultado é, no máximo, 16T .

No código a0 representa o último x*x e a1 representa o iterado real x*x

Como você pode ver, o sqrt é feito em 16 x (BitShiftLeft,BitShiftRight,OR,Plus,Compare) onde o bit shift e o LUT podem ser conectados.

Se você tem portas super rápidas para isso em comparação com o resto, você pode multiplicar o clock de entrada por 16 e usá-lo como temporização interna para o módulo SQRT . Algo parecido com os velhos tempos, quando havia o relógio MC como a divisão do clock da CPU na CPU antiga da Intel / MCU s ... Desta forma, você pode obter 1T tempo (ou vários deles depende da taxa de multiplicação).





sqrt