Wie kann man zwei Q15-Werte in Verilog unterteilen, ohne Verwendung von '/' (Division) Operator?

Question

Da Division Operation (/) ist teuer im Falle von FPGA? Ist es möglich, mit grundlegenden Shift-Operationen zwei Q15-Format-Nummern (16-Bit-Festkommazahl) zu unterteilen?

Kann mir jemand helfen, indem ich ein Beispiel gebe?

Vielen Dank im Voraus!

Answer 1

Festkommaarithmetik ist nur Integer-Arithmetik mit etwas eingeworfen Skalierung. Q15 ein rein fraktioniertes Format als eine vorzeichenbehaftete 16-Bit-Integer-Zahl mit Skalierungsfaktor von 2 , in der Lage zu repräsentieren Werte in dem Intervall gespeichert ist [-1, 1). Es ist klar, dass die Division nur in Q15 sinnvoll ist, wenn die Größe des Divisors die Magnitude der Dividende übersteigt, da sonst die Größe des Quotienten den darstellbaren Bereich übersteigt.

Bevor Sie mit einer benutzerdefinierten Verilog-Implementierung der Festkommadivision beginnen, sollten Sie die Bibliotheksangebote Ihres FPGA-Anbieters überprüfen, da eine Festkomma-Bibliothek mit Pipeline-Teilung häufig verfügbar ist. Es gibt auch offene Quellprojekte, die relevant sein können, z. B. this one.

Wenn integer Verwendung Teilungs Operatoren für Festpunkt-Division, müssen wir die Tatsache anzupassen, dass die Division des Skalierungsfaktors entfernen wird, dh (a * 2 ^Skala)/(b * 2 ^Skala) = (a/b), während das korrekte Festpunktergebnis (a/b * 2 ^Maßstab) ist. Dies ist leicht fixiert Vormultiplizieren die Dividende um 2 ^Skala, wie in der folgenden C-Implementierung:

int16_t div_q15 (int16_t dividend, int16_t divisor) 
{ 
    return (int16_t)(((int32_t)dividend << 15)/(int32_t)divisor); 
} 

Wikipedia gibt eine vernünftige ÜBERSICHT wie Binärteilung auf einer Bit-für-Bit-Basis zu implementieren, mit Operationen hinzufügen, subtrahieren und verschieben. Diese Methoden sind eng verwandt mit der in der Grundschule gelehrten Langdistanz. Für FPGAs ist die Verwendung der nichtwiederherstellenden Methode, wenn oft bevorzugt, wie z. B. this paper,

Nikolay Sorokin, "Implementierung von High-Speed-Festpunktteiler auf FPGA". Journal of Computer Science & Technologie, vol. 6, Nr. 1, April 2006, S. 8-11.

ist hier C-Code, der zeigt, wie die Nicht-Wiederherstellungsverfahren für die Aufteilung von 16-Bit-verwendet werden können Operanden Zweierkomplement-:

/* bit-wise non-restoring two's complement division */ 
void int16_div (int16_t dividend, int16_t divisor, int16_t *quot, int16_t *rem) 
{ 
    const int operand_bits = (int) (sizeof (int16_t) * CHAR_BIT); 
    uint16_t d = (uint16_t)divisor; 
    uint16_t nd = 0 - d; /* -divisor */ 
    uint16_t r, q = 0; /* remainder, quotient */ 
    uint32_t dd = (uint32_t)d << operand_bits; /* expanded divisor */ 
    uint32_t pp = dividend; /* partial remainder */ 
    int i; 

    for (i = operand_bits - 1; i >= 0; i--) { 
     if ((int32_t)(pp^dd) < 0) { 
      q = (q << 1) + 0; /* record quotient bit -1 (as 0) */ 
      pp = (pp << 1) + dd; 
     } else { 
      q = (q << 1) + 1; /* record quotient bit +1 (as 1) */ 
      pp = (pp << 1) - dd; 
     } 
    } 
    /* convert quotient from digit set {-1,1} to plain two's complement */ 
    q = (q << 1) + 1; 

    /* remainder is upper half of partial remainder */ 
    r = (uint16_t)(pp >> operand_bits); 

    /* fix up cases where we worked past a partial remainder of zero */ 
    if (r == d) { /* remainder equal to divisor */ 
     q = q + 1; 
     r = 0; 
    } else if (r == nd) { /* remainder equal to -divisor */ 
     q = q - 1; 
     r = 0; 
    } 

    /* for truncating division, remainder must have same sign as dividend */ 
    if (r && ((int16_t)(dividend^r) < 0)) { 
     if ((int16_t)q < 0) { 
      q = q + 1; 
      r = r - d; 
     } else { 
      q = q - 1; 
      r = r + d; 
     } 
    } 
    *quot = (int16_t)q; 
    *rem = (int16_t)r; 
} 

Beachten Sie, dass es mehrere Wege für den Umgang mit den verschiedenen Sonder sind Fälle, die bei nicht-wiederherstellender Teilung auftreten. Zum Beispiel sieht man häufig Code, der einen Nullteilrest pp erkennt und die Schleife in diesem Fall früh über die Quotientenbits verlässt. Hier nehme ich an, dass eine FPGA-Implementierung die Schleife vollständig ausrollen würde, um eine Pipeline-Implementierung zu erstellen. In diesem Fall ist eine vorzeitige Beendigung nicht hilfreich. Stattdessen wird eine endgültige Korrektur auf die Quotienten angewendet, die durch das Ignorieren eines Teilrests von Null betroffen sind.

Um eine Q15 Division von oben zu erstellen, müssen wir nur eine einzige Änderung vornehmen: die Erhöhung der Dividende.Statt:

uint32_t pp = dividend; /* partial remainder */ 

jetzt wir verwenden:

uint32_t pp = dividend << 15; /* partial remainder; incorporate Q15 scaling */ 

Der resultierende C-Code (sorry, ich werde nicht liefern lesen zu bedien Verilog-Code), einschließlich dem Test-Framework ist:

#include <stdio.h> 
#include <stdlib.h> 
#include <stdint.h> 
#include <limits.h> 
#include <math.h> 

/* bit-wise non-restoring two's complement division */ 
void q15_div (int16_t dividend, int16_t divisor, int16_t *quot, int16_t *rem) 
{ 
    const int operand_bits = (int) (sizeof (int16_t) * CHAR_BIT); 
    uint16_t d = (uint16_t)divisor; 
    uint16_t nd = 0 - d; /* -divisor */ 
    uint16_t r, q = 0; /* remainder, quotient */ 
    uint32_t dd = (uint32_t)d << operand_bits; /* expanded divisor */ 
    uint32_t pp = dividend << 15; /* partial remainder, incorporate Q15 scaling */ 
    int i; 

    for (i = operand_bits - 1; i >= 0; i--) { 
     if ((int32_t)(pp^dd) < 0) { 
      q = (q << 1) + 0; /* record quotient bit -1 (as 0) */ 
      pp = (pp << 1) + dd; 
     } else { 
      q = (q << 1) + 1; /* record quotient bit +1 (as 1) */ 
      pp = (pp << 1) - dd; 
     } 
    } 
    /* convert quotient from digit set {-1,1} to plain two's complement */ 
    q = (q << 1) + 1; 

    /* remainder is upper half of partial remainder */ 
    r = (uint16_t)(pp >> operand_bits); 

    /* fix up cases where we worked past a partial remainder of zero */ 
    if (r == d) { /* remainder equal to divisor */ 
     q = q + 1; 
     r = 0; 
    } else if (r == nd) { /* remainder equal to -divisor */ 
     q = q - 1; 
     r = 0; 
    } 

    /* for truncating division, remainder must have same sign as dividend */ 
    if (r && ((int16_t)(dividend^r) < 0)) { 
     if ((int16_t)q < 0) { 
      q = q + 1; 
      r = r - d; 
     } else { 
      q = q - 1; 
      r = r + d; 
     } 
    } 
    *quot = (int16_t)q; 
    *rem = (int16_t)r; 
} 

int main (void) 
{ 
    uint16_t dividend, divisor, ref_q, res_q, res_r; 
    double quot, fxscale = (1 << 15); 

    dividend = 0; 
    do { 
     printf ("\r%04x", dividend); 
     divisor = 1; 
     do { 
      quot = trunc (fxscale * (int16_t)dividend/(int16_t)divisor); 
      /* Q15 can only represent numbers in [-1, 1) */ 
      if ((quot >= -1.0) && (quot < 1.0)) { 
       ref_q = (int16_t)((((int32_t)(int16_t)dividend) << 15)/
            ((int32_t)(int16_t)divisor)); 
       q15_div ((int16_t)dividend, (int16_t)divisor, 
         (int16_t *)&res_q, (int16_t *)&res_r); 
       if (res_q != ref_q) { 
        printf ("!r dividend=%04x (%f) divisor=%04x (%f) res=%04x (%f) ref=%04x (%f)\n", 
          dividend, (int16_t)dividend/fxscale, 
          divisor, (int16_t)divisor/fxscale, 
          res_q, (int16_t)res_q/fxscale, 
          ref_q, (int16_t)ref_q/fxscale); 
       } 
      } 
      divisor++; 
     } while (divisor); 
     dividend++; 
    } while (dividend); 

    return EXIT_SUCCESS; 
}