Teiler-Prinzip (Festkomma)

Ähnlich wie bei der Dezimaldivision verläuft die Berechnung von 27 geteilt durch 5 wie folgt:

Der Divisionsvorgang verläuft wie folgt:

  • (1) Nehmen Sie die höherwertigen Bits des Dividenden, mit einer Bitbreite gleich der des Divisors (im Beispiel 3-Bit-Daten).
  • (2) Vergleiche die höherwertigen Daten des Dividenden mit dem Divisor. Wenn die höherwertigen Daten nicht kleiner als der Divisor sind, ist das entsprechende Quotientenbit 1, und die Differenz zwischen beiden ergibt den Rest des ersten Schritts; andernfalls ist das entsprechende Quotientenbit 0, und die höherwertigen Daten werden direkt als Rest verwendet.
  • (3) Verkette den Rest aus dem vorherigen Schritt mit den verbleibenden höchstwertigen 1-Bit-Daten des Dividenden zu neuen Daten und vergleiche diese dann mit dem Divisor. Ein neuer Quotient und ein neuer Rest können erhalten werden.
  • (4) Wiederhole Prozess (3), bis auch das niederstwertigste Bit des Dividenden an der Berechnung beteiligt ist.

Es ist zu beachten, dass die Bitbreite des Quotienten mit der des Dividenden übereinstimmen sollte, weil der Divisor 1 sein kann.Daher sollte im obigen manuellen Divisionsbeispiel beim ersten Vergleich das höchstwertige Bit 1 der Zahl 27 (3'b001) mit 3'b101 verglichen werden.Basierend auf diesem Berechnungsprozess entwirf einen Pipeline-Dividierer mit konfigurierbarer Bitbreite, wobei die Anzahl der Pipeline-Verzögerungszyklen gleich der Bitbreite des Dividenden ist.

Dividierer-Design

Entwurf der Einzelschritt-Operation

Bei der Einzelschrittdivision muss die Bitbreite des Einzelschritt-Dividenden (Signal dividend) um 1 Bit breiter als die des ursprünglichen Divisors (Signal divisor) sein, um Überlauf zu vermeiden.

Um das Pipelining zu erleichtern, benötigt die Ausgabe Register, um den ursprünglichen Divisor (Signale divisor und divisor_kp) und Dividendeninformationen (Signale dividend_ci und dividend_kp) zu speichern.

Das Ergebnis der Einzelschrittoperation ist ein neuer 1-Bit-Quotient (Signal merchant) und ein Rest (Signal remainder).

Um das endgültige Divisionsergebnis zu erhalten, muss der neue 1-Bit-Quotient (Signal merchant) außerdem verschoben und mit dem Quotientenergebnis des vorherigen Zyklus (merchant_ci) akkumuliert werden.

Der Entwurf der Einzelschritt-Operationseinheit ist wie folgt (Dateiname: divider_cell.v):

Beispiel

// Parameter M bedeutet die tatsächliche Breite des Divisors
module    divider_cell
    #(Parameter N=5,
      Parameter M=3)
    (
      input                     clk,
      input                     rstn,
      input                     en,

      input [M:0]               dividend,
      input [M-1:0]             divisor,
      input [N-M:0]             merchant_ci , //Quotienten-Ausgang aus der vorherigen Stufe
      input [N-M-1:0]           dividend_ci , //Ursprünglicher Divisor

      output reg [N-M-1:0]      dividend_kp,  //Ursprüngliche Dividendeninformation
      output reg [M-1:0]        divisor_kp,   //Ursprüngliche Divisorinformation
      output reg                rdy ,
      output reg [N-M:0]        merchant ,  //Quotienten-Ausgang aus der Recheneinheit
      output reg [M-1:0]        remainder   //Rest-Ausgang aus der Recheneinheit
    );

    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            rdy            <= 'b0 ;
            merchant       <= 'b0 ;
            remainder      <= 'b0 ;
            divisor_kp     <= 'b0 ;
            dividend_kp    <= 'b0 ;
        end
        else if (en) begin
            rdy            <= 1'b1 ;
            divisor_kp     <= divisor ;  //Ursprünglicher Divisor bleibt unverändert
            dividend_kp    <= dividend_ci ;  //Ursprünglicher Dividend wird durchgereicht
            if (dividend >= {1'b0, divisor}) begin
                merchant    <= (merchant_ci<<1) + 1'b1 ; //Quotient ist 1
                remainder   <= dividend - {1'b0, divisor} ; //Rest berechnen
            end
            else begin
                merchant    <= merchant_ci<<1 ;  //Quotient ist 0
                remainder   <= dividend ;        //Rest unverändert
            end
        end // if (en)
        else begin
            rdy            <= 'b0 ;
            merchant       <= 'b0 ;
            remainder      <= 'b0 ;
            divisor_kp     <= 'b0 ;
            dividend_kp    <= 'b0 ;
        end
    end

endmodule

Instanziierung der Pipeline-Stufe

Verknüpfe den Rest (Signal remainder) aus der Einzelschritt-Berechnung mit den entsprechenden 1-Bit-Daten des ursprünglichen Dividenden (Signal dividend) und verwende ihn als neuen Einzelschritt-Dividenden-Eingang für die nächste Einzelschritt-Divisionseinheit.

Unter ihnen müssen die Dateninformationen von Dividend, Divisor und Quotient auch an die nächste Operationseinheit übergeben werden.

Das Design des Dividers, das durch Instanziierung von Pipeline-Stufen-Modulen vervollständigt wird, lautet wie folgt (Dateiname: divider_man.v):

Beispiel

//parameter N bedeutet die tatsächliche Breite von dividend
//unter Verwendung von 29/5=5...4
module    divider_man
    #(Parameter N=5,
      Parameter M=3,
      parameter N_ACT = M+N-1)
    (
      input                     clk,
      input                     rstn,

      input                     data_rdy ,  //Datenfreigabe
      input [N-1:0]             dividend,   //Dividend
      input [M-1:0]             divisor,    //Divisor

      output                    res_rdy ,
      output [N_ACT-M:0]        merchant ,  //Bitbreite des Quotienten: N
      output [M-1:0]            remainder ); //Endrest

    wire [N_ACT-M-1:0]   dividend_t [N_ACT-M:0] ;
    wire [M-1:0]         divisor_t [N_ACT-M:0] ;
    wire [M-1:0]         remainder_t [N_ACT-M:0];
    wire [N_ACT-M:0]     rdy_t ;
    wire [N_ACT-M:0]     merchant_t [N_ACT-M:0] ;

    //Erste Operationseinheit initialisieren
    divider_cell      #(.N(N_ACT), .M(M))
       u_divider_step0
    ( .clk              (clk),
      .rstn             (rstn),
      .en               (data_rdy),
      //Die höchstwertigen 1-Bit-Daten des Dividenden als Dividenden für die erste Einzelschrittoperation verwenden, wobei die höheren Bits mit 0 aufgefüllt werden
      .dividend         ({{(M){1'b0}}, dividend[N-1]}),
      .divisor          (divisor),                  
      .merchant_ci      ({(N_ACT-M+1){1'b0}}),   //Quotient anfangs 0
      .dividend_ci      (dividend[N_ACT-M-1:0]), //Ursprünglicher Dividend
      //Ausgabe
      .dividend_kp      (dividend_t[N_ACT-M]),   //Ursprüngliche Dividendeninformation durchgereicht
      .divisor_kp       (divisor_t[N_ACT-M]),    //Ursprüngliche Divisor-Information durchgereicht
      .rdy              (rdy_t[N_ACT-M]),
      .merchant         (merchant_t[N_ACT-M]),   //Erstes Quotienten-Ergebnis
      .remainder        (remainder_t[N_ACT-M])   //Erster Rest
      );

    genvar               i ;
    generate
        for(i=1; i<=N_ACT-M; i=i+1) begin: sqrt_stepx
            divider_cell      #(.N(N_ACT), .M(M))
              u_divider_step
              (.clk              (clk),
               .rstn             (rstn),
               .en               (rdy_t[N_ACT-M-i+1]),
               .dividend         ({remainder_t[N_ACT-M-i+1], dividend_t[N_ACT-M-i+1][N_ACT-M-i]}),   //Rest mit Einzelbit-Daten des ursprünglichen Dividenden verketten
               .divisor          (divisor_t[N_ACT-M-i+1]),
               .merchant_ci      (merchant_t[N_ACT-M-i+1]),
               .dividend_ci      (dividend_t[N_ACT-M-i+1]),
               //Ausgabe
               .divisor_kp       (divisor_t[N_ACT-M-i]),
               .dividend_kp      (dividend_t[N_ACT-M-i]),
               .rdy              (rdy_t[N_ACT-M-i]),
               .merchant         (merchant_t[N_ACT-M-i]),
               .remainder        (remainder_t[N_ACT-M-i])
              );
        end // Block: sqrt_stepx
    endgenerate

    assign res_rdy       = rdy_t[0];
    assign merchant      = merchant_t[0];  // Letztes Quotientenergebnis als endgültiger Quotient
    assign remainder     = remainder_t[0]; // Letzter Rest als endgültiger Rest

endmodule

testbench

Setze die Bitbreite des Dividenden auf 5 und die Bitbreite des Divisors auf 3, und füge in der Testbench eine Selbstprüfung hinzu, die wie folgt beschrieben wird:

Beispiel

`timescale 1ns/1ns

module test ;
    Parameter    N = 5 ;
    Parameter    M = 3 ;
    reg          clk;
    reg          rstn ;
    reg          data_rdy ;
    reg [N-1:0]  dividend ;
    reg [M-1:0]  divisor ;

    wire         res_rdy ;
    wire [N-1:0] merchant ;
    wire [M-1:0] remainder ;

    //Takt
    always begin
        clk = 0 ; #5 ;
        clk = 1 ; #5 ;
    end

    //Treiber
    initial begin
        rstn      = 1'b0 ;
        #8 ;
        rstn      = 1'b1 ;

        #55 ;
        @(negedge clk ) ;
        data_rdy  = 1'b1 ;
                dividend  = 25;      divisor      = 5;
        #10 ;   dividend  = 16;      divisor      = 3;
        #10 ;   dividend  = 10;      divisor      = 4;
        #10 ;   dividend  = 15;      divisor      = 1;
        repeat(32)    #10   dividend   = dividend + 1 ;
        divisor      = 7;
        repeat(32)    #10   dividend   = dividend + 1 ;
        divisor      = 5;
        repeat(32)    #10   dividend   = dividend + 1 ;
        divisor      = 4;
        repeat(32)    #10   dividend   = dividend + 1 ;
        divisor      = 6;
        repeat(32)    #10   dividend   = dividend + 1 ;
    end

    //Verzögere die Eingabe, sodass die Datenresultate im selben Zyklus verglichen werden können, um die Selbstprüfung abzuschließen
    reg  [N-1:0]   dividend_ref [N-1:0];
    reg  [M-1:0]   divisor_ref [N-1:0];
    always @(posedge clk) begin
        dividend_ref[0] <= dividend ;
        divisor_ref[0]  <= divisor ;
    end

    genvar         i ;
    generate
        for(i=1; i<=N-1; i=i+1) begin
            always @(posedge clk) begin
                dividend_ref[i] <= dividend_ref[i-1];
                divisor_ref[i]  <= divisor_ref[i-1];
            end
        end
    endgenerate

    //Selbstprüfung
    reg  error_flag ;
    always @(posedge clk) begin
    # 1 ;
        if (merchant * divisor_ref[N-1] + remainder != dividend_ref[N-1] && res_rdy) beginb      //In der Testbench kann das Multiplikationszeichen direkt verwendet werden, ohne die Operationszyklen zu berücksichtigen
            error_flag <= 1'b1 ;
        end
        else begin
            error_flag <= 1'b0 ;
        end
    end

    //Modulinstanziierung
    divider_man  #(.N(N), .M(M))
    u_divider
     (
      .clk              (clk),
      .rstn             (rstn),
      .data_rdy         (data_rdy),
      .dividend         (dividend),
      .divisor          (divisor),
      .res_rdy          (res_rdy),
      .merchant         (merchant),
      .remainder        (remainder));

   //Simulationsende
   initial begin
      forever begin
         #100;
         if ($time >= 10000)  $finish ;
      end
   end

endmodule // test

Simulationsergebnisse

Wie in der Abbildung dargestellt, erzeugen die beiden Eingabedaten nach einer Verzögerung, die der Anzahl der Zyklen der Bitbreite des Dividenden entspricht, korrekte Divisionsergebnisse. Darüber hinaus wird eine Pipeline-Ausgabe ohne zusätzliche Verzögerung erreicht, was dem Design entspricht.

Quellcode-Download

Herunterladen