algorithm - ¿Cómo obtener una raíz cuadrada para una entrada de 32 bits solo en un ciclo de reloj?

integer verilog

Question

Quiero diseñar un módulo sintetizable en Verilog que tomará solo un ciclo para calcular la raíz cuadrada de una entrada dada de 32 bits.

Answer 1

Hay conversión a un logaritmo, reducir a la mitad y volver a convertir.
Para tener una idea de cómo implementar el registro "combinatorio" y el antilog , consulte el artículo EDN de Michael Dunn que muestra el codificador de prioridad, la palanca de cambios de barril y la tabla de búsqueda, con tres variantes de registro en System Verilog para descarga.
(El codificador de prioridad, la palanca de cambio de barril y la tabla de búsqueda parecen prometedores para "one-step-Babylonian / Heron / Newton / -Raphson. Pero eso probablemente todavía necesitaría una tabla de búsqueda de 128K por 9 bits).

Si bien no presenta "verilog",
Tole Sutikno: "Un algoritmo de raíz cuadrada optimizado para implementación en hardware FPGA" muestra una implementación combinatoria de un algoritmo modificado (binario) dígito por dígito.

Answer 2

La forma habitual de hacer esto en hardware es usar un CORDIC . Una implementación general permite el cálculo de una variedad de funciones trascendentales (cos / sin / tan) y ... raíces cuadradas dependiendo de cómo inicialice y opere el CORDIC.

Es un algoritmo iterativo, por lo que para hacerlo en un solo ciclo, desenrollaría el bucle en tantas iteraciones como necesite para la precisión deseada y encadene las instancias.

Específicamente, si operó el CORDIC en modo de vectorización, inicialícelo con [x, 0] y gire a 45 grados, la salida final [x '', y''] será una constante multiplicativa de distancia. es decir, sqrt (x) = x ''* sqrt (2) * K

Answer 3

Tengo el código aquí está

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

always@(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

Answer 4

[Editar1] código reparado

Recientemente descubrí que los resultados estaban apagados, incluso si las pruebas determinan que todo estaba bien, así que profundicé más y descubrí que tenía un error tonto en mi ecuación y debido a conflictos de nombres con mi entorno pgm, las pruebas obtuvieron falsos positivos, así que lo pasé por alto antes. Ahora funciona en todos los casos como debería.

Lo mejor que puedo pensar (excepto aproximación o LUT grande) es la búsqueda binaria sin multiplicación, aquí el 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;
    }
//---------------------------------------------------------------------------

La búsqueda binaria estándar sqrt(xx) está configurando bits de x de MSB a LSB para que el resultado de x*x <= xx . Afortunadamente, podemos evitar la multiplicación simplemente reescribiendo la cosa como multiplicador incremental ... en cada iteración, el resultado x*x se puede usar así:

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

Donde x0 es el valor de x de la última iteración y x1 es el valor real. El m es el peso del bit procesado real. (2*m) y (m*m) son constantes y se pueden usar como LUT y bit-shift, por lo que no es necesario multiplicar. Solo se necesita adición. Lamentablemente, la iteración está vinculada a la computación secuencial que prohíbe la paralelización, por lo que el resultado es 16T en el mejor de los casos.

En el código, a0 representa la última x*x y a1 representa la x*x iterada real

Como puede ver, el sqrt se realiza en 16 x (BitShiftLeft,BitShiftRight,OR,Plus,Compare) donde el desplazamiento de bits y LUT se pueden cablear.

Si tiene puertas súper rápidas para esto en comparación con el resto, puede multiplicar el reloj de entrada por 16 y usarlo como sincronización interna para el módulo SQRT . Algo similar a los viejos tiempos cuando había un reloj MC como división del reloj de la CPU de origen en las antiguas CPU / MCU Intel ... De esta manera, puede obtener el tiempo 1T (o el múltiplo depende de la relación de multiplicación).