Arithmetik

Bitserieller Multiplizierer (2)

 English version  aufwärts

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 an-1, ..., a0 und bn-1, ..., b0 müssen die in Bild 1a für n = 4 angegebenen Bit-Produkte gebildet und stellen­richtig addiert werden.

Bit-Produkte bei einer 4-Bit-Multiplikation Weitergabe der Zwischenergebnisse und Eingabebits
(a) (b)
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 ikleiner gleichj die beiden Bit-Produkte aibj und ajbi (bzw. nur das eine Bit-Produkt aibi, falls i = j) berechnet und mit drei weiteren Bits, die als Zwischen­ergebnisse auftreten, 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.1)

Die Bit-Produkte, die an Position (i,j) berechnet werden, haben einen binären Stellenwert von 2i+j. Das dort berechnete Summenbit s hat ebenfalls einen Stellenwert von 2i+j, das Übertragsbit c hat einen Stellenwert von 2i+j+1, und das Übertragsbit zweiter Ordnung d hat einen Stellenwert von 2i+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

ai,j  =   ai
bi,j  =   bj
a'i,j  =   aj
b'i,j  =   bi

für alle i, j Element {0, ..., n-1} mit ikleiner gleichj gesetzt wird. Hierbei stehen ai,j und bi,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 a0b3 beispiels­weise a0,3b0,3, und a3b0 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 Sk ist gleich 1, falls genau k ihrer Argumente gleich 1 sind, und sonst 0. Sk,m steht abkürzend für Sk oder Sm. Zusammen­genommen bilden S1,3,5, S2,3 und S4,5 einen (5,3)-Zähler.

Rekursions­gleichungen
ai,j+1  =  ai,j
bi+1,j  =   bi,j
a'i+1,j  =  a'i,j
b'i,j+1  =   b'i,j
si-1,j+1  =   S1,3,5 (ai,j bi,ja'i,j b'i,jsi,jci,jdi,j)
ci,j+1  =  S2,3 (Argumente wie oben)
di+1,j+1  =  S4,5 (Argumente wie oben)

Das Ergebnis der Multi­plikation sind die Bits rj = 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 ent­sprechenden Index­positionen mit jgrößer gleichn weiter­gegeben werden können. Die Eingabebits a'i,j und bi,j sind 0 für jgrößer gleichn, so dass 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

  i j
  T   = t 0 1
 p 1 0

 

transponiert im wesentlichen das Schema von Bild 1. Das Ergebnis ist das folgende Schema (Bild 2). Es ist zu sehen, dass beispiels­weise a0 b1 und a1 b0 zur Zeit 1 in Prozessor­element 0 berechnet werden.

Bild 2: Transformierter Indexraum
Bild 2: Transformierter Indexraum

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

  s c d a b a' b'
  D  = i -1 0 1 0 1 1 0
 j 1 1 1 1 0 0 1

 

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.

  s c d a b a' b'
TD  = t 1 1 1 1 0 0 1
 p -1 0 1 0 1 1 0

 

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 a0 und b'0 gebraucht, zum Zeitpunkt 1 dann zusätzlich a1 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 ak bk 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 s0 s1 s2 in Bild 3). Der Multi­plizierer berechnet dann r = s + a·b.

Bild 3: Multipliziererschaltung für Operanden der Länge n=3
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

  i j
  T   = t 0 1
 p 1 1

 

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)

1)  Ein Volladdierer ist entsprechend ein (3,2)-Zähler.

 

Weiter mit:   up

 

homeH.W. Lang   Fachhochschule Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 22.04.2003   Updated: 09.02.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Angewandte Informatik

mit Schwerpunkten auf Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik