Arithmetik

Dieser bitserielle Multi­plizierer basiert auf einem Multi­plikationsschema, das von Chen und Willoner [CW 79] angegeben wurde. Die ursprüng­liche Implementation wurde unabhängig voneinander von Sips [Sips 82], Gnanasekaran [Gna 83] sowie von Strader und Rhyne [SR 82] verbessert. Diese Implementation wird im Folgenden vorgestellt und mit Hilfe der Methode von Moldovan und Fortes [MF 86] formal verifiziert.

Multiplikationsalgorithmus

Für die Multi­plikation zweier n-Bit-Zahlen a_n-1, ..., a₀ und b_n-1, ..., b₀ müssen die in Bild 1a für n = 4 angegebenen Bit-Produkte gebildet und stellen­richtig addiert werden.

Bild 1: Bit-Produkte bei einer 4-Bit-Multiplikation (a), Weitergabe der Zwischenergebnisse und Eingabebits (b)

Im Multi­plikationsalgorithmus werden an jeder Index­position (i,j) mit i ≤ j die beiden Bit-Produkte a_ib_j und a_jb_i (bzw. nur das eine Bit-Produkt a_ib_i, falls i = j) berechnet und mit drei weiteren Bits, die als Zwischen­ergebnisse auf­treten, summiert. Da insgesamt fünf Bits addiert werden, ist das Ergebnis eine Zahl zwischen 0 und 5, für deren Darstellung drei Bit erforderlich sind. Diese drei Ergebnisbits sind das Summenbit s, ein Übertragsbit c und ein Übertragsbit zweiter Ordnung d.

Die boolesche Funktion, die diese Ergebnisbits berechnet, wird als (5,3)-Zähler bezeichnet, denn sie zählt, wieviele der 5 Eingabebits gleich 1 sind und stellt das Ergebnis durch 3 Ausgabebits dar.¹)

Die Bit-Produkte, die an Position (i,j) berechnet werden, haben einen binären Stellenwert von 2^i+j. Das dort berechnete Summenbit s hat ebenfalls einen Stellenwert von 2^i+j, das Übertragsbit c hat einen Stellenwert von 2^i+j+1, und das Übertragsbit zweiter Ordnung d hat einen Stellenwert von 2^i+j+2. Diese Ergebnisbits werden nun an andere Index­positionen weiter­gegeben, an denen Berechnungen mit dem jeweils passenden Stellenwert stattfinden. Bild 1b zeigt die Weitergabe der Ergebnisbits sowie der Eingabebits.

Die Eingabebits werden in den zwei­dimensionalen Indexraum eingebettet, indem

für alle i, j ∈ {0, ..., n-1} mit i ≤ j gesetzt wird. Hierbei stehen a_i,j und b_i,j für die oberen Eingabebits in den Kästchen von Bild 1 und a'i,j und b'i,j für die unteren Eingabebits. So entspricht a₀b₃ beispiels­weise a_0,3b_0,3, und a₃b₀ entspricht a'0,3b'0,3.

Der Multi­plikationsalgorithmus kann nun durch folgende Rekursions­gleichungen dargestellt werden. Die Funktionen S sind symmetrische boolesche Funktionen, die wie folgt definiert sind:

Die Funktion S_k ist gleich 1, falls genau k ihrer Argumente gleich 1 sind, und sonst 0. S_k,m steht abkürzend für S_k ∨ S_m. Zusammen­genommen bilden S_1,3,5, S_2,3 und S_4,5 einen (5,3)-Zähler.

Rekursions­gleichungen

Das Ergebnis der Multi­plikation sind die Bits r_j = s_-1,j+1 mit j = 0, ..., 2n-1. Der Indexraum, der in Bild 1 dargestellt ist, muss also so erweitert werden, dass die Summen- und Übertrags­bits zu den entsprechenden Index­positionen mit j ≥ n weiter­gegeben werden können. Die Eingabebits a'i,j und b_i,j sind 0 für j ≥ n, sodass die im erweiterten Indexraum berechneten Bit-Produkte ebenfalls 0 sind.

Transformation des Indexraums

Um aus den Rekursions­gleichungen die Multi­pliziererschaltung zu gewinnen, wird der Indexraum {(i,j)} in den Indexraum {(t,p)} aus Zeit und Prozessor­elementen trans­formiert [MF 86].

Die lineare Trans­formation

transponiert im Wesentlichen das Schema von Bild 1. Das Ergebnis ist das folgende Schema (Bild 2). Es ist zu sehen, dass beispiels­weise a₀ b₁ und a₁ b₀ zur Zeit 1 in Prozessor­element 0 berechnet werden.

Die Anwendung der Trans­formation auf die Index­positionen, an denen das Ergebnis der Multi­plikation erzeugt wird, ergibt folgendes:

Das Ergebnis der Multi­plikation erscheint bei Prozessor­element -1 (d.h. am Ausgang von Prozessor­element 0) zu den Zeitpunkten 1, ..., 2n. Es sind also noch zusätzliche n Takte erforderlich, um die n höher signifikanten Ergebnisbits aus dem Prozessor­feld heraus­zuschieben.

Die Daten­abhängigkeits­matrix D der Rekursions­gleichungen im Indexraum {(i,j)} ist

Die Daten­abhängig­keiten bedeuten, dass z.B. die Variable s, die an Index­position (i,j) berechnet worden ist, als nächstes an Index­position (i-1,j+1) gebraucht wird, oder dass z.B. die Variable y von Index­position (i,j) auch an Index­position (i,j+1) gebraucht wird.

Die mit der linearen Trans­formation T trans­formierte Daten­abhängigkeits­matrix gibt an, in welcher Weise die Variablen im trans­formierten Indexraum und damit in der Schaltung weiter­gegeben werden.

Beispiels­weise wird s in jedem Takt an das vorher­gehende Prozessor­element weiter­gegeben, c wird in jedem Takt im selben Prozessor­element gehalten, d wird in jedem Takt zum nächsten Prozessor­element weiter­gegeben. Die Eingabebits b und a' werden in 0 Takten zum jeweils nächsten Prozessor­element weiter­gegeben – dies bedeutet, dass sie gleichzeitig an alle Prozessor­elemente gesendet werden.

Die Eingabebits a und b' werden in jedem Takt im selben Prozessor­element gehalten. Sie müssen also offenbar bitparallel an den Prozessor­elementen anliegen. Zum Zeitpunkt 0 werden aber zunächst nur a₀ und b'0 gebraucht, zum Zeitpunkt 1 dann zusätzlich a₁ und b'1 usw. Daher werden a und b' ebenfalls bitseriell eingegeben und mit Hilfe eines Steuer­signals jeweils zum Zeitpunkt k in Prozessor­element k gespeichert..

Multipliziererschaltung

Bild 3 zeigt den Multi­plizierer, hier für eine Operanden­länge von n = 3. Jedes der n Prozessor­elemente besteht aus zwei Latches zur Speicherung der Eingabebits a und b', zwei AND-Gattern zur Bildung der Bit-Produkte, einem (5,3)-Zähler und vier Verzögerungs­elementen.

Im Takt k soll in Prozessor k jeweils nur ein Bit-Produkt a_k b_k addiert werden (siehe Bild 2). In diesem Fall wird das andere Bit-Produkt durch das Steuersignal auf 0 gesetzt.

Es ist möglich, gleichzeitig noch eine Addition auszuführen, indem ein Operand s in den d-Eingang von Prozessor 0 eingegeben wird (Eingabebits s₀ s₁ s₂ in Bild 3). Der Multi­plizierer berechnet dann r = s + a·b.

Bild 3: Multipliziererschaltung für Operanden der Länge n=3

Eine Simulation des Multi­plizierers in Form einer Excel-Datei steht unter Serieller Multi­plizierer 2.xls zur Verfügung.

Zusammenfassung

Es wurde der bitserielle Multi­plizierer von [Sips 82][SR 82][Gna 83] vorgestellt und mit Hilfe des Trans­formationsverfahrens von [MF 86] formal verifiziert. Das zugrunde liegende Multi­plikationsschema stammt von Chen und Willoner [CW 79]. Die ursprünglich dort angegebene Implementation entspricht einer weniger günstigen Trans­formation T, nämlich

Das Ergebnis dieser Trans­formation ist ein Feld mit 2n Prozessor­elementen.

Literatur

[CW 79]   I.N. Chen, R. Willoner: An O(n) Parallel Multiplier with Bit-Sequential Input and Output. IEEE Transactions on Computers C-28, 10, 721-727 (1979)

[Gna 83]   R. Gnanasekaran: On a Bit-Serial Input and Bit-Serial Output Multiplier. IEEE Transactions on Computers C-32, 9, 878-880 (1983)

[MF 86]   D.I. Moldovan, J.A.B. Fortes: Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays. IEEE Transactions on Computers C-35, 1, 1-12 (1986)

[Sips 82]   H.J. Sips: Comments on "An O(n) Parallel Multiplier with Bit-Sequential Input and Output". IEEE Transactions on Computers C-31, 4, 325-327 (1982)

[SR 82]   N.R. Strader, V.T. Rhyne: A Canonical Bit-Sequential Multiplier. IEEE Transactions on Computers C-31, 8, 791-795 (1982)