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

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

    [Edit1] código reparado

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

    Lo mejor que puedo pensar (excepto la aproximación o LUT grande) es la búsqueda binaria sin multiplicación, aquí código de 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, de modo que el resultado de x*x < = xx . Afortunadamente, podemos evitar la multiplicación simplemente reescribiendo la cosa como un multiplicador creciente ... en cada iteración, el resultado anterior de x*x puede usarse 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. Los (2*m) y (m*m) son constantes y se pueden usar como LUT y bit-shift, por lo que no es necesario multiplicarlos. Solo se necesita una adición. Lamentablemente, la iteración está obligada a un cómputo 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 el último x*x y a1 representa iterado real x*x

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

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

    Tengo el código aquí es

      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 

    La forma habitual de hacerlo 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 inicialices y operes el CORDIC.

    Es un algoritmo iterativo, por lo tanto, para hacerlo en un solo ciclo, debe desenrollar el ciclo en tantas iteraciones como necesite para la precisión deseada y encadenar las instancias juntas.

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

    Hay conversión a logaritmo, reducción a la mitad y conversión de vuelta.
    Para obtener una idea de cómo implementar registro “combinatorio” y antilogaritmo , consulte el artículo de EDN de Michael Dunn que muestra el codificador de prioridad, la palanca de cambio 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 cambios de barril y la tabla de búsqueda parecen prometedores para “babilónico de un solo paso / Heron / Newton / -Raphson. Pero eso probablemente aún 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 la implementación en hardware FPGA” muestra una implementación combinatoria de un algoritmo de dígito por dígito modificado (binario).