Calcul de la racine carrée d'un nombre binaire 8 bits

14

Je cherchais un moyen de calculer la racine carrée d'un nombre 8 bits donné en utilisant uniquement une combinaison numérique ou une logique séquentielle. Est-ce possible?

Une façon peut être d'utiliser simplement une table de recherche car je ne considère pas du tout les parties fractionnaires (donc ) mais il doit y avoir un meilleur moyen que cela. Quelqu'un peut-il m'indiquer cela?dix3

Rick_2047
la source
4
J'utiliserais une table de recherche simple avec des plages. Nombre minimum et maximum pour chaque sortie et vous vérifiez juste.
Kortuk
6
Une recherche semble assez simple. Après tout, il n'y a que 16 réponses possibles pour la racine carrée d'un nombre à 8 bits.
Olin Lathrop
3
hmm .. les seules réponses sont 0000 à 1111; seules les entrées 64 ou supérieures auront le bit le plus haut défini dans la réponse, ce n'est donc qu'un OU des deux bits supérieurs de l'entrée. Maintenant, vous n'avez que trois fonctions de 8 bits à réduire ..
JustJeff

Réponses:

9

Les tables de recherche ont été mentionnées dans les commentaires. Il existe deux approches.


Créez rapidement une table longue de 256 octets, avec chaque valeur suivante la racine carrée de l'index correspondant. C'est rapide car vous utilisez l'argument comme index pour accéder directement à la bonne valeur. L'inconvénient est qu'il a besoin d'une longue table, avec beaucoup de valeurs en double.

Compact
Comme indiqué, un entier de 8 bits ne peut avoir que des valeurs de 0 à 255, et les racines carrées correspondantes sont de 0 à 16 (arrondies). Construisez une table à 16 entrées (base zéro) avec la nième entrée la valeur maximale pour l'argument pour lequel la racine carrée est n. Le tableau ressemblerait à ceci:

 0  
 2  
 6  
12  
20
etc.

Vous parcourez la table et vous arrêtez lorsque vous rencontrez une valeur supérieure ou égale à votre argument. Exemple: racine carrée 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

Alors que la table de recherche rapide a un temps d'exécution fixe (une seule recherche), ici le temps d'exécution est plus long pour les arguments de valeur supérieure.

Pour les deux méthodes, en choisissant différentes valeurs pour le tableau, vous pouvez choisir entre une valeur arrondie ou tronquée pour la racine carrée.

stevenvh
la source
2
Si vous tournez ce tableau à l'envers, vous aurez besoin de moins d'itérations en moyenne
Federico Russo
Une recherche binaire sur la table la plus courte peut accélérer l'algorithme en moyenne. Vous commencez à mi-chemin dans la table de recherche (position 8) puis vous décidez si la valeur trouvée est trop élevée ou trop basse et vous montez soit 4 places vers le haut, soit 4 vers le bas. Répétez jusqu'à ce que vous ayez terminé.
jippie
7

Fonctionnant en 8 bits, vous êtes essentiellement contraint aux solutions entières. Si vous avez besoin de la racine carrée de X, le plus proche que vous pouvez obtenir est le plus grand entier dont le carré est inférieur ou égal à X. Par exemple, pour sqrt (50), vous obtiendrez 7, car 8 * 8 serait supérieur à 50.

Voici donc une astuce pour le faire: compter le nombre de nombres impairs, en commençant par 1, vous pouvez soustraire de X. Vous pouvez le faire avec la logique comme ceci: un registre R1 à 8 bits contient la valeur de travail, un compteur 7 bits R2 détient (la plupart) le nombre impair, et un compteur 4 bits R3 détient le résultat. Lors de la réinitialisation, R1 est chargé avec la valeur de X, R2 est remis à zéro et R3 est remis à zéro. Un circuit soustracteur à 8 bits est alimenté R1 pour l'entrée «A», et la valeur de R2 combinée avec un LSB fixé à «1» (via pull-up) pour l'entrée «B». Le soustracteur génère une différence AB de 8 bits et un bit d'emprunt. A chaque horloge, si le bit d'emprunt est effacé, R1 est chargé avec la sortie du soustracteur, R2 est incrémenté et R3 est incrémenté. Si le bit d'emprunt est défini, R1 n'est pas chargé et R2, R3 ne sont pas incrémentés, b / c le résultat est maintenant prêt dans R3.

ALTERNATIVEMENT

Il n'y a que 16 valeurs de sortie possibles, donc la réponse est un nombre à quatre bits. Essentiellement, vous disposez de quatre fonctions mono-bit des 8 bits d'entrée. Maintenant, je ne peux pas dessiner une carte de Karnaugh à 8 dimensions, mais en principe, vous pourriez simplement trouver un circuit combinatoire pour chaque bit de la réponse. Prenez ensemble les sorties de ces quatre circuits combinatoires et interprétez-les comme la réponse à quatre bits. Voila. Aucune horloge, aucun registre, juste un tas de NAND et de NOR suffirait.

JustJeff
la source
J'ai réfléchi toute la nuit. Le bit 8 de la sortie est clairement fonction des deux bits d'entrée les plus significatifs. De même, je pense que le bit 4 dans la sortie est probablement fonction uniquement des 4 bits d'entrée supérieurs: 00x1, 001x, 1xx1 et 11x1 semblent le définir. Va vérifier cela plus tard.
JustJeff
1
Si vous faites cela dans un FPGA, vous pouvez simplement le jeter dans une grande casedéclaration et laisser l'outil de synthèse faire tout le travail. D'une part, c'est un peu comme faire une grande table de recherche dans la RAM distribuée (utilisée comme ROM); d'autre part, l'outil devrait trouver des optimisations comme vous le mentionnez dans votre commentaire.
The Photon
5

Je ne sais pas s'il s'agit d'une aide, mais il existe un moyen ingénieusement simple de calculer une racine carrée:

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;
}

Je ne sais pas grand-chose sur ce qui peut et ne peut pas être fait en logique séquentielle, mais comme cet algorithme se termine en seulement 4 boucles, vous pourrez peut-être l'implémenter en 4 étapes.

Rocketmagnet
la source
4

J'ai exécuté les tables de vérité pour la racine carrée entière de 0 à 255 via un minimiseur logique Quine-McCluskey. La racine carrée entière peut être effectuée avec une logique combinatoire, mais même pour une taille d'entrée relativement petite de28valeurs possibles, la réponse n'est pas pour les faibles de cœur. Ce qui suit est ordonné de MSB A à LSB D de la sortie, en termes d'abcdefgh en tant qu'entrées, de MSB à 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;
Bitrex
la source
1
Wow, quel logiciel fait ça? Fonctionne-t-il pour des dimensions arbitrairement grandes? Comment dériveriez-vous le nombre minimal de portes pour le construire à partir de ces formulaires SOP? Il semble qu'à ce stade, un cpld ou mieux serait certainement le moyen le plus pratique de le construire.
captncraig
@CMP Désolé pour le retard dans ma réponse. J'ai utilisé le programme disponible ici: home.roadrunner.com/~ssolver qui peut accepter des tables de vérité - J'ai utilisé un simple script Python pour générer une table de vérité pour chacun des chiffres de la racine carrée entière. Ces SOP ci-dessus sont en fait dans leur forme minimale, aux limites de la capacité des algorithmes que le programme utilise pour les minimiser.
Bitrex
1
@CMP Comme vous le dites, il serait fou d'implémenter la racine carrée entière de cette façon, car on pourrait soit utiliser une table de recherche, soit coder l'un des algorithmes pour la racine carrée entière et laisser votre langage HDL de choix la synthétiser.
Bitrex