Cómo realizar una aproximación de valor pequeño para sqrt (x) en FPGA

Una rutina que he usado antes (no sé si es una "adecuada" o no) es un enfoque de dividir y vencer.

Empiezas con un valor superior e inferior arbitrario (digamos 5 y 0 respectivamente, la raíz cuadrada más alta y más baja que quieras encontrar) y encuentras el punto medio entre ellas. Cuadrar ese valor.

Si el valor cuadrado es mayor que su objetivo, establezca el valor superior para que sea su valor cuadrado. Si es más bajo, establece el valor más bajo.

Repita hasta que el valor cuadrado coincida con su valor de búsqueda, o haya ejecutado suficientes iteraciones para ser tan preciso como desee.

Aquí hay una pequeña versión que he juntado en perl:

#!/usr/bin/perl

my $val = shift;

my $max = 5;
my $min = 0;

my $iterations = 0;
my $maxiter = 40;

while(($max > $min) and ($iterations<$maxiter))
{
    $iterations++;
    my $diff = $min + ($max - $min) / 2;
    my $square = $diff * $diff;

    if($square == $val)
    {

        print "Square root found at $diff\n";
        print "$iterations iterations\n";
        exit(0);
    } else {
        if($square > $val)
        {
            $max = $diff;
        } else {
            $min = $diff;
        }
    }
}

my $diff = $min + ($max - $min) / 2;
print "Approximate square root after $iterations iterations: $diff\n";

Por supuesto, esto está usando un punto flotante, pero podría ser fácilmente adaptado a un punto fijo. Puede variar la precisión cambiando el límite de iteración. Cada iteración se vuelve un poco más precisa que la anterior.

por ejemplo: - encuentra la raíz cuadrada de 9:

Approximate square root after 40 iterations: 2.99999999999955
   - or - 
Approximate square root after 10 iterations: 3.00048828125
   - or - 
Approximate square root after 5 iterations: 3.046875

Si hubiera encontrado el valor 3, se habría detenido antes, claro.

Dale suficientes iteraciones y debería ser muy preciso:

./sqrt.pl 0.00284
Square root found at 0.0532916503778969
59 iterations

Aquí hay algunas ideas y rutinas del maestro trascendente ascendente / Guru Scott Dattalo aquí .
 Eso es, por supuesto, una broma, excepto la parte del gurú (¿Gurú?). Scott es excelente.

Discusión relevante.  2005 & PIC y algunos son C, pero pueden ser valiosos.

Scott again - 2003

¡¡¡Dos maestros !!!
 Dattallo & Golovchenko.
Una gama de métodos

No ha especificado lo que quiere decir con "valor pequeño" o "aproximación". Entonces, lo que voy a proponer podría no funcionar, pero aquí va.

Lo más fácil sería hacer una tabla de consulta. Esencialmente, una ROM donde el bus de direcciones es el número que desea que tenga una raíz cuadrada, y el resultado de los datos es el resultado. Con un solo BRAM, podría hacer un LUT de 9 bits, 8 bits fuera. Por supuesto, más BRAM te dará una mesa más grande.

(BRAM = El término Xilinx para una RAM de bloque, que también se puede usar como ROM. Otros FPGA tienen cosas similares)

Si desea más precisión de la que le proporcionará BRAM, podría hacer una interpolación lineal simple de dos entradas de LUT. Por ejemplo, digamos que desea una entrada de 12 bits, pero solo tiene BRAM para 10 bits. Toma los 10 bits principales de tu entrada y busca eso en la LUT. Agregue 1 a esos 10 bits y busque ese valor también. Luego, realiza una interpolación lineal simple entre los dos resultados, utilizando los 2 bits inferiores para indicar la proporción de un valor sobre el otro. Por supuesto, esto solo le dará una aproximación, pero creo que si hace los cálculos encontrará que podría ser lo suficientemente bueno.

Este método es el menos preciso con números de valor bajo, pero a medida que la entrada va a valores más altos, la precisión aumenta.

Una optimización del método anterior sería utilizar los BRAM como una ROM de doble puerto. De esta manera, puede leer dos valores sin aumentar el número de BRAM utilizados. Esto también le permitirá calcular un SQRT para cada ciclo de reloj, con algunos retrasos en la canalización.

Por cierto, ¡este método también funciona para SINE / COSINE!

Prueba el siguiente enfoque

• Si el número es negativo, maneje en consecuencia.
• Si el número es 0, devuelve 0.
• De lo contrario:
• normalice a un número en el rango [1/4, 1]: cuente cuántas veces k tiene que multiplicar su número por 4 ( x <<= 2 en C) hasta que esté dentro del rango anterior.
• utilice un enfoque arbitrario (aproximaciones polinomiales, método de Newton para sqrt a [n] = (a [n-1] + k / a [n-1]) / 2, etc.) para calcular la raíz cuadrada dentro de este rango
• denormalizar: desplazar a la derecha en k bits

Prueba \ $ x = (y + d) ^ 2 \ approx y ^ 2 + 2dy \ $ así que vamos a $ d = (x-y ^ 2) / 2y = (x / y-y) \ gg 1 \ $ y siguiente \ $ y = y + d. PS Si MSb está n de derecha, deje primero \ $ y = 1 \ ll (n / 2) \ $. Convierte en < 4 iteraciones.

Prueba: adivinanzas mejoradas para la primera variable

Su número puede ser considerado: A * 2 ^ n
La primera aproximación es entonces: A * 2 ^ (n / 2)

Digamos que está utilizando un número de 32 bits, con 24 bits utilizados para contener fracciones. Para los números > 1:
1. Cuente el número de bits utilizados en la parte entera (N)
2. Reduzca a la mitad este número (N '= N / 2, es decir, un bit a la derecha desplazado)
3. Gire a la derecha el número original por N ': esta es su primera estimación.

En este formato, el número más pequeño que puede tener es 2 ^ -24. La raíz cuadrada será aproximadamente 2 ^ -12. Entonces, para los números < 1:
1. Cuente el número de bits "cero" en la fracción, hasta que alcance un bit establecido (N)
2. Reduzca a la mitad este número (N '= N / 2, es decir, un bit a la derecha desplazado)
3. IZQUIERDA desplaza el número original por el recuento revisado: esta es tu primera estimación.

Ejemplo:
    0.0000 0000 0000 0000 1 [16 ceros iniciales] se aproxima a: 0.0000 0000 1

Finalmente, si todavía tienes problemas con la pequeña A: ¿puedes calcular 1 / A?
Si es así, invierta su número, luego intente usar el algoritmo de la raíz cuadrada inversa:
x' = 0.5x * (3 - Ax^2)