Mehrzyklus-Unsigned-Multiplizierer mit Shift-and-add

Voraussetzungen: Sequenzielle Logik, nichtblockierende Zuweisungen^{iNonblocking Sequenzielle RTL-Zuweisung mit <=. Nach Auswertung der rechten Seite wird die Aktualisierung geplant, sodass Register derselben Flanke den alten Zustand verwenden. Mehr erfahren}, Zähler, Schieber und Addierer.

Einen Addierer über mehrere Takte wiederverwenden

Unsigned-Multiplikation^{iUnsigned Interpretation einer Bitfolge als nichtnegative Ganzzahl. Der n-Bit-Bereich ist 0 bis 2^n−1 und kann sich von der signed-Interpretation derselben Bits unterscheiden. Mehr erfahren} mit W Bit ist die Summe der durch B-Bits ausgewählten Teilprodukte.

Alle Teilprodukte gleichzeitig zu addieren braucht viel Logik. Hier wird ein Addierer W-mal verwendet: ein Kompromiss zwischen Fläche und Durchsatz. Eine RTL-Schleife allein erzeugt noch keine Mehrzyklusschaltung; Register^{iRegister Speichert einen Zustand aus mehreren Bits. Die synchronen Register dieses Kurses übernehmen festgelegte Eingaben an Taktflanken. Mehr erfahren} für Zwischenzustände und ein Abschlusskriterium sind nötig.

Akkumulator P und verschobener Multiplikand M haben 2W Bit, der rechtsgeschobene Multiplikator Q hat W Bit. Anfangs P=0, M=zero-extend(A), Q=B. Je Arbeitstakt wird bei Q[0]=1 M zu P addiert, M links und Q rechts um eins verschoben.

Nach W Schritten ist Q=0 und P das volle Produkt. 2W Bit genügen, weil $(2^W-1)^2<2^{2W}$ und die unsigned-Zwischensummen das Endprodukt nicht überschreiten.

Für A=13, B=11, W=4 sind Qs niedrige Bits 1,1,0,1. P folgt 0→13→39→39→143, verwendetes M 13→26→52→104. Auch im dritten Schritt mit Q[0]=0 müssen Schieber und Zähler fortschreiten.

Jede Spalte zeigt den Zustand nach einer Anforderungs- oder Arbeitsflanke. Die erste initialisiert, die folgenden vier rechnen. Im dritten Schritt hält nur P, während M und Q schieben.

Annahme und Abschluss zuerst festlegen

Eine steigende Flanke^{iSteigende Flanke Übergang des Takts von 0 auf 1. Nicht zu verwechseln mit dem gesamten hohen Pegelintervall CLK=1. Mehr erfahren} mit start=1 im Idle nimmt den Auftrag an. An t0 werden nur Eingaben gespeichert. t1 bis tW führen W Schritte aus; direkt nach tW sind product und done gültig. Zwischen Annahme und Abschluss liegen W Perioden, einschließlich Startflanke werden W+1 Flanken genannt.

Bei busy=1 wird start ignoriert. Auch die Abschlussflanke nimmt keinen neuen Auftrag an, da busy davor 1 ist. Früheste nächste Annahme ist tW+1; der Mindestabstand beträgt W+1 Perioden. Dauerhaftes start=1 beginnt an der nächsten Idle-Flanke erneut. Üblicherweise liefert der Aufrufer einen zur Annahme passenden Puls.

module mul_iter #(parameter int W = 8) (
  input  logic clk, rst, start,
  input  logic [W-1:0] a, b,
  output logic busy, done,
  output logic [2*W-1:0] product
);
  localparam int CW = (W <= 1) ? 1 : $clog2(W);
  localparam logic [CW-1:0] LAST = CW'(W-1);
  logic [CW-1:0] step;
  logic [2*W-1:0] acc, m, next_acc;
  logic [W-1:0] q;

  assign next_acc = acc + (q[0] ? m : {2*W{1'b0}});

  always_ff @(posedge clk) begin
    if (rst) begin
      busy <= 1'b0;
      done <= 1'b0;
      product <= '0;
      acc <= '0;
      m <= '0;
      q <= '0;
      step <= '0;
    end else begin
      done <= 1'b0;
      if (!busy) begin
        if (start) begin
          busy <= 1'b1;
          acc <= '0;
          m <= {{W{1'b0}}, a};
          q <= b;
          step <= '0;
        end
      end else begin
        acc <= next_acc;
        m <= m << 1;
        q <= q >> 1;
        if (step == LAST) begin
          product <= next_acc;
          busy <= 1'b0;
          done <= 1'b1;
        end else begin
          step <= step + 1'b1;
        end
      end
    end
  end
endmodule

Vorausgesetzt ist W≥1; CW ist mindestens 1, damit W=1 keinen Nullbitzähler erzeugt. Synchroner active-high-Reset hat Vorrang vor laufender Arbeit. Änderungen externer a, b nach Annahme wirken nicht auf gespeicherte m, q. product ändert sich nur bei Reset oder Abschluss. done ist ein Einzykluspuls, kein bis zum Verbrauch gehaltenes valid.

Die letzte Zuweisung lautet product<=next_acc, nicht product<=acc. Nonblocking liest alte Werte; acc als Ausgang ließe das letzte Teilprodukt fehlen. Ebenso verwendet next_acc das aktuelle Q[0], selbst wenn die q-Schiebezuweisung im Code davor steht.

Invariante und reale Entwurfsentscheidungen

Nach k Arbeitsschritten gilt:

Zerlegen Sie Q in geraden Anteil und niedrigstes Bit: Damit bleibt die Beziehung im nächsten Schritt erhalten. Bei k=W ist Q=0, also P=AB. Die Invariante^{iInvariante Bedingung, die bei jeder zulässigen Ausführung stets wahr bleiben muss. Eine FIFO mit Tiefe vier enthält etwa immer zwischen null und vier Elemente. Mehr erfahren} begründet Akkumulations- und Schiebereihenfolge klarer als wenige Beispielkurven.

Ein Arbeitsschritt hat einen kritischen Pfad über 2W-Bit-Addierer und Eingangsauswahl. Das Entfernen von * garantiert weder weniger Fläche noch mehr Geschwindigkeit. Vergleichen Sie FPGA-DSP-Blöcke, Synthese und erforderlichen Durchsatz^{iDurchsatz Anzahl angenommener oder abgeschlossener Aufgaben je Zeiteinheit. Eine Pipeline kann ihn erhöhen, ohne die Latenz einer einzelnen Aufgabe zu verkürzen. Mehr erfahren}. Nicht enthalten sind Early-exit, signed-Arithmetik und Ergebnis-Backpressure. Der Verbraucher darf done nicht verpassen.

Testen Sie 0,1, Maximum und B mit ausschließlich gesetztem MSB sowie start und Eingabeänderungen während busy und Abbruch durch Reset. Nur ein gesetztes höchstes B-Bit deckt besonders gut eine ausgelassene letzte Akkumulation auf.