Calcular la raíz cuadrada del número binario de 8 bits

Estaba buscando una manera de calcular la raíz cuadrada de un número de 8 bits dado usando solo una combinación digital o lógica secuencial. ¿Es eso posible?

Una forma puede ser simplemente usar una tabla de búsqueda ya que no estoy considerando partes fraccionarias (así que $\sqrt{10} \simeq 3$ ) pero tiene que haber una mejor manera que esta. ¿Alguien puede señalarme eso?

Las tablas de búsqueda se han mencionado en los comentarios. Hay dos enfoques.

Rápido
Cree una tabla de 256 bytes de longitud, con cada valor siguiente la raíz cuadrada del índice correspondiente. Esto es rápido ya que utiliza el argumento como índice para acceder directamente al valor correcto. El inconveniente es que necesita una tabla larga, con muchos valores duplicados.

Compacto
Como se dijo, un número entero de 8 bits solo puede tener valores de 0 a 255, y las raíces cuadradas correspondientes son de 0 a 16 (redondeadas). Construya una tabla de 16 entradas (basada en cero) con la entrada n-ésima el valor máximo para el argumento para el cual la raíz cuadrada es n. La tabla se vería así:

 0  
 2  
 6  
12  
20
etc.

Camina por la mesa y se detiene cuando encuentra un valor mayor o igual a su argumento. Ejemplo: raíz cuadrada de 18

set index to 0
value[0] = 0, is less than 18, go to the next entry  
value[1] = 2, is less than 18, go to the next entry  
value[2] = 6, is less than 18, go to the next entry  
value[3] = 12, is less than 18, go to the next entry
value[4] = 20, is greater than or equal to 18, so sqrt(18) = 4

Si bien la tabla de búsqueda rápida tiene un tiempo de ejecución fijo (solo una búsqueda), aquí el tiempo de ejecución es más largo para argumentos de mayor valor.

Para ambos métodos, al elegir diferentes valores para la tabla, puede seleccionar entre un valor redondeado o truncado para la raíz cuadrada.

Trabajando en 8 bits, básicamente está limitado a soluciones enteras. Si necesita la raíz cuadrada de X, lo más cercano que puede obtener es el número entero más grande cuyo cuadrado es menor o igual a X. Por ejemplo, para sqrt (50) obtendría 7, ya que 8 * 8 sería más que 50

Así que aquí hay un truco para hacerlo: cuente cuántos números impares, comenzando con 1, puede restar de X. Podría hacerlo con la lógica de esta manera: un registro R1 de 8 bits contiene el valor de trabajo, un contador R2 de 7 bits contiene (la mayoría de) el número impar, y un contador R3 de 4 bits contiene el resultado. En el reinicio, R1 se carga con el valor de X, R2 se borra a cero y R3 se borra a cero. Se alimenta un circuito de resta de 8 bits R1 para la entrada 'A', y el valor de R2 se combina con un LSB fijo en '1' (mediante pull-up) para la entrada 'B'. El sustractor genera una diferencia AB de 8 bits y un bit de préstamo. En cada reloj, si el bit de préstamo está libre, R1 se carga con la salida del sustractor, R2 se incrementa y R3 se incrementa. Si se establece el bit de préstamo, R1 no se carga y R2, R3 no se incrementan, b / c el resultado ahora está listo en R3.

ALTERNATIVAMENTE

Solo hay 16 valores de salida posibles, por lo que la respuesta es un número de cuatro bits. Básicamente, tiene cuatro funciones de un solo bit de los 8 bits de entrada. Ahora, no puedo dibujar un mapa de Karnaugh de 8 dimensiones, pero en principio podrías crear un circuito combinatorio para cada bit de la respuesta. Tome las salidas de esos cuatro circuitos combinatorios e inténtelos como la respuesta de cuatro bits. Voila Sin relojes, sin registros, solo un montón de NAND y NOR serían suficientes.

No sé si esto es de alguna ayuda, pero hay una manera ingeniosamente simple de calcular una raíz cuadrada:

unsigned char sqrt(unsigned char num)
{
    unsigned char op  = num;
    unsigned char res = 0;
    unsigned char one = 0x40;

    while (one > op)
        one >>= 2;

    while (one != 0)
    {
        if (op >= res + one)
        {
            op -= res + one;
            res = (res >> 1) + one;
        }
        else
        {
            res >>= 1;
        }

        one >>= 2;
    }
    return res;
}

No sé mucho sobre lo que se puede y no se puede hacer en lógica secuencial, pero dado que este algoritmo termina en solo 4 bucles, es posible que pueda implementarlo en 4 etapas.

Ejecuté las tablas de verdad para la raíz cuadrada entera de 0-255 a través de un minimizador lógico Quine-McCluskey. La raíz cuadrada entera se puede hacer solo con lógica combinatoria, pero incluso para un tamaño de entrada relativamente pequeño de$2^8$posibles valores, la respuesta no es para los débiles de corazón. Lo siguiente se ordena de MSB A a LSB D de la salida, en términos de abcdefgh como entradas, MSB a LSB:

    A =     a
     or     b;

    B =     a and     b
     or not b and     c
     or not b and     d;

    C =     a and     b and     c
     or     a and     b and     d
     or     a and not b and not c and not d
     or     a and not c and not d and     e
     or     a and not c and not d and     f
     or not a and     c and     d
     or not a and     c and     e
     or not a and     c and     f
     or not a and not b and not d and     e
     or not a and not b and not d and     f;

     D =     a and     b and     c and     e
     or     a and     b and     c and     f
     or     a and     c and     d
     or     a and not b and not c and not d
     or     a and not b and not d and     e and     f
     or     a and not b and not d and     e and     g
     or     a and not b and not d and     e and     h
     or     a and not c and not d and not e and not f
     or     b and     c and not d and not e and not f and     g
     or     b and     c and not d and not e and not f and     h
     or not a and     b and not c and     d and     e
     or not a and     b and not c and     d and     f
     or not a and     b and not c and     d and     g
     or not a and     b and not c and     d and     h
     or not a and     c and not d and not e and not f
     or not a and     d and     e and     f
     or not a and     d and     e and     g
     or not a and     d and     e and     h
     or not a and not b and     c and not e and not f and     g
     or not a and not b and     c and not e and not f and     h
     or not a and not b and not c and     e and     f
     or not b and     c and     d and     e
     or not b and     c and     d and     f
     or not b and not c and not d and not f and     g
     or not b and not c and not d and not f and     h;