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

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

Rápido
Cree una tabla de 256 bytes, 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 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-th 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.

Usted camina a través de la tabla 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 mayor para los 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á restringido a soluciones enteras. Si necesita la raíz cuadrada de X, lo más cercano que puede obtener es el entero más grande cuyo cuadrado es menor o igual que 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 hacer eso: cuente cuántos números impares, comenzando con 1, puede restar de X. Podría hacerlo con lógica como tal: un registro R1 de 8 bits contiene el valor de trabajo, un 7- el contador de bits R2 contiene (la mayoría de) el número impar, y un contador de 4 bits R3 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. Un circuito restador de 8 bits se alimenta con R1 para la entrada 'A', y el valor de R2 se combina con un LSB fijado en '1' (a través de pull-up) para la entrada 'B'. El restador emite una diferencia de 8 bits A-B y un bit de préstamo. En cada reloj, si el bit de préstamo está despejado, 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 ya está listo en R3.

ALTERNATIVAMENTE

Solo hay 16 valores de salida posibles, por lo que la respuesta es un número de cuatro bits. Esencialmente, 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 solo se puede crear un circuito combinatorio para cada parte de la respuesta. Tome las salidas de esos cuatro circuitos combinatorios juntos e interprételas 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 una ayuda, pero hay una manera ingeniosamente sencilla 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 la lógica secuencial, pero como este algoritmo finaliza en solo 4 ciclos, 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 \ $ valores posibles, 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;