Berechnung der Quadratwurzel einer 8-Bit-Binärzahl

Ich suchte nach einer Möglichkeit, die Quadratwurzel einer bestimmten 8-Bit-Zahl nur mit digitaler Kombination oder sequentieller Logik zu berechnen. Ist das möglich?

Eine Möglichkeit könnte darin bestehen, einfach eine Nachschlagetabelle zu verwenden, da ich keine gebrochenen Teile in Betracht ziehe (also ) aber es muss einen besseren Weg geben. Kann mich jemand darauf hinweisen?$\sqrt{10} \simeq 3$

Nachschlagetabellen wurden in Kommentaren erwähnt. Es gibt zwei Ansätze.

Schnell
Erstellen Sie eine 256 Byte lange Tabelle, wobei jeder nächste Wert die Quadratwurzel des entsprechenden Index ist. Dies ist schnell, da Sie das Argument als Index verwenden, um direkt auf den richtigen Wert zuzugreifen. Nachteil ist, dass es eine lange Tabelle mit vielen doppelten Werten benötigt.

Kompakt
Wie bereits erwähnt, kann eine 8-Bit-Ganzzahl nur Werte von 0 bis 255 haben, und die entsprechenden Quadratwurzeln sind 0 bis 16 (gerundet). Konstruieren Sie eine Tabelle mit 16 Einträgen (nullbasiert) mit dem n-ten Eintrag, dem Maximalwert für das Argument, für das die Quadratwurzel n ist. Tabelle würde so aussehen:

 0  
 2  
 6  
12  
20
etc.

Sie gehen durch die Tabelle und hören auf, wenn Sie auf einen Wert stoßen, der größer oder gleich Ihrem Argument ist. Beispiel: Quadratwurzel von 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

Während die schnelle Nachschlagetabelle eine feste Ausführungszeit hat (nur eine Nachschlagetabelle), ist hier die Ausführungszeit für Argumente mit höherem Wert länger.

Bei beiden Methoden können Sie zwischen einem gerundeten oder einem abgeschnittenen Wert für die Quadratwurzel wählen, indem Sie unterschiedliche Werte für die Tabelle auswählen.

Wenn Sie mit 8 Bit arbeiten, sind Sie grundsätzlich auf ganzzahlige Lösungen beschränkt. Wenn Sie die Quadratwurzel von X benötigen, können Sie als Nächstes die größte Ganzzahl ermitteln, deren Quadrat kleiner oder gleich X ist. Für sqrt (50) würden Sie beispielsweise 7 erhalten, da 8 * 8 mehr wäre als 50.

Hier ist ein Trick, um dies zu tun: Zählen Sie, wie viele ungerade Zahlen, beginnend mit 1, Sie von X subtrahieren können. Sie könnten es mit folgender Logik tun: Ein 8-Bit-Register R1 enthält den Arbeitswert, ein 7-Bit-Zähler R2 hält (den größten Teil) der ungeraden Zahl und ein 4-Bit-Zähler R3 hält das Ergebnis. Beim Zurücksetzen wird R1 mit dem Wert von X geladen, R2 wird auf Null gelöscht und R3 wird auf Null gelöscht. Einer 8-Bit-Subtrahierschaltung wird R1 für den Eingang "A" zugeführt, und der Wert von R2 wird mit einem auf "1" festgelegten LSB (über Pull-up) für den Eingang "B" kombiniert. Der Subtrahierer gibt eine 8-Bit-Differenz AB und ein Ausleihbit aus. Wenn das Entlehnungsbit bei jedem Takt gelöscht ist, wird R1 mit dem Subtrahiererausgang geladen, R2 wird inkrementiert und R3 wird inkrementiert. Wenn das Entleihbit gesetzt ist, R1 nicht geladen ist und R2, R3 nicht inkrementiert sind, ist das Ergebnis b / c nun in R3 bereit.

ALTERNATIVE

Es gibt nur 16 mögliche Ausgabewerte, die Antwort ist also eine 4-Bit-Zahl. Im Wesentlichen haben Sie vier Einzelbitfunktionen der 8 Eingangsbits. Jetzt kann ich keine 8-dimensionale Karnaugh-Karte zeichnen, aber im Prinzip könnte man einfach eine kombinatorische Schaltung für jedes Bit der Antwort finden. Nehmen Sie die Ausgänge dieser vier kombinatorischen Schaltungen zusammen und interpretieren Sie sie als die Vier-Bit-Antwort. Voila. Keine Uhren, keine Register, nur ein Haufen NAND und NOR würden ausreichen.

Ich weiß nicht, ob dies eine Hilfe ist, aber es gibt einen genial einfachen Weg, eine Quadratwurzel zu berechnen:

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

Ich weiß nicht viel darüber, was in der sequentiellen Logik getan werden kann und was nicht, aber da dieser Algorithmus in nur 4 Schleifen endet, können Sie ihn möglicherweise in 4 Stufen implementieren.

Ich habe die Wahrheitstabellen für die ganze Quadratwurzel von 0-255 mit einem Quine-McCluskey-Logik-Minimierer durchlaufen lassen. Die ganzzahlige Quadratwurzel kann mit nur kombinatorischer Logik erstellt werden, aber auch für eine relativ kleine Eingangsgröße von$2^8$Mögliche Werte, die Antwort ist nichts für schwache Nerven. Das Folgende ist von MSB A bis LSB D des Ausgangs in Bezug auf abcdefgh als Eingänge von MSB bis LSB angeordnet:

    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;