DE2221693C3 - Schaltungsanordnung zur Ausführung einer Multiplikation zwischen zwei Binärzahlen - Google Patents

Description

Die Erfindung bezieht sich auf Schaltungsanordnungen gemäß den Oberbegriffen der Patentansprüche I und 2.

Die Multiplikation von Binärzahlen kann auf relativ einfache Weise vorgenommen werden. Die klassische Lösung des betreffenden Problems besteht darin, ein Akkumulatorregister vorzusehen, dessen Länge dem Zweifachen der Länge des Operanden ist, da nämlich das Produkt aas Zweifache der Größe des Operanden annehmen kann. Der Multiplikator wird zweckmäßigerweise in der Hälfte niederer Wertigkeit des AUkumulatorregisters gespeichert Der Inhalt in der Hälfte höherer Wertigkeit des Akkumulatorregisters und der Inhalt eines Multiplikandenregisters werden einem Addierer zugeführt Das Ausgangssignal des Addierers stellt die Summe der akkumulierten Teilprodukte und des potentiellen Teilprodukt« dar, das aus dem Einfachen des Multiplikanden besteht Dabei wird eine Reihe von η Zyklen ausgeführt Bei jedem Zyklus wird das Bit niedrigster Wertigkeit des Akkumulators überprüft, und das Ausgangssignal des Addierers wird in der Hälfte höherer Wertigkeit des Akkumulatorregisters gespeichert oder nicht, und zwar in Abhängigkeit davon, ob das betreffende Bit eine »1« oder eine »0« ist Der Inhalt des Akkumulatorregisters wird um ein Bit nach rechts verschoben, und der Zyklus wird so lange wiederholt bis der gesamte Multiplikator überprüft worden ist Als Ergebnis ist dann der Multiplikand mit 2" multipliziert worden, und zwar je »1«-Bit in dem Multiplikator; diese Teilprodukte sind auf Grund der zyklischen Verschicbungen, die das Ergebnis um zwei je Zyklus untersetzen, in richtiger Ausrichtung akkumuliert worden. Dabei existieren verschiedene Verfahren zur Verarbeitung de unterschiedlichen Vorzeichenkombinationen von Operanden sowie zur Verarbeitung von unterschiedlichen ArUn von Zahlendarstellungen, d. h. von Vorzeichen und Größe, Einerkomplement und Zweierkomplement. In dem Buch »Digital Computer Design Fundamentals« von Yaohan C hu, McGraw-Hill, 1962, Seiten 24 bis 35. sind Standard-Multiplikationsaigorithmen beschrieben.

, Bei 36-Bit-Operanden erfordert dieses Multiplikationsverfahren die Bereitstellung von 36 Zyklen, wobei eine Addieroperation jeweils dann ausgeführt wird, wenn eine »1« an einer Bitposition des Multiplikators vorhanden ist Damit ist aber Zeit erforderlich, um den

in Übertrag durch den Addierer je Addiereroperation hindurchzuleiten. Ein Weg zur Beschleunigung der Multiplikation besteht darin, die Multiplikatorbits paarweise zu überprüfen und Vielfache des Multiplikanden zu dem Inhalt des Akkumulatorregisters hinzuzuad- -, dieren oder von diesem Inhalt zu subtrahieren. Beispiele für diese Art von Multiplikation sind in dem Buch »The Logic of Computer Arithmetic« von Ivan F1 ο r e s, Prentice-Hall, Ine, 1963, Seiten 164 bis 174 beschrieben. Bei dieser Verfahrensweise wird eine Bitfolge »11« als

:n Bitfolge behandelt, die eine Subtrakr.i des Multiplikanden und ein Übcrtrags-Ausgangssigni! erfordert, das gespeichert wird und das effektiv die Addition des Vierfachen des Multiplikanden während des nächsten Zyklus bewirkt. Eine Modifikation dieses Algorithinus

j-, ist in der Zeitschrift »Proceedings of the IRE«, Januar 1961, Seiten 73 bis 75 beschrieben.

Bei dem gerade erwähnten Algorithmus wird die nachstehend angegebene Entscheidungstabelle benutzt:

Muiiipiika tor-	isenuizics rviuiii-
Bits	plikandcri-
	Vielfachc,
0 00	0
001	+2
0 10	+2
0 11	+4
100	-4
101	-2
1 10	-2
1 11	0

Ein Merkmal des betreffenden Algoritnmus besteht darin, daß eine Überprüfung des jeweiligen Bit-Paares von rechts nach links angenommen ist und daß bei ungeradzahligen Werten im vorausgehenden Zyklus das akkumulierte Teilprodukt um das Einfache des Multiplikanden zu niedrig gemacht worden ist Wenn das nächste Bit-Paar ungerade ist führt dies darüber hinaus zu einem Teilprodukt aufgrund dessen das akkumulierte Teilprodukt für den nächsten Zyklus um das Einfache des Multiplikanden zu niedrig ist In dem ersten Zyklus erfordert jedoch eine Eins in der Bitstelle „»pdrigster Wertigkeit eine besondere Behandlung. In der zuletzt genannten Zeitschrift ist dabei die Anwendung eines Sonderzyklus angegeben, in welchem ein Paar von Blind-Null-Bits den·. Multiplikator vorgesetzt wird; im übrigen ist in der zuletzt genannten Zeitschrift eine Modifikation des ersten Zyklus angegeben, derart, daß eine Subtraktion des Multiplikanden erfolg·, wenn das Bit niedrigster Wertigkeit eine »1« ist.

Für praktische Anwendungsfälle stellt die Forderung, daß Multiplikanden-V itlfache von 2 und 4 zu verarbeiten sind, ein praktisches Problem insofern dar, als zwei Wege zu dem Addierer hin beschriften werden müssen, und zwar zusätzlich zu dem Grundweg, der zur

M) ODr

Ausführung der direkten Operationen nach Art von Additionen dient. Darüber hinaus muli die Verkniipfungslogik richtige Ergebnisse für sämtliche Kombinationen von Vor/eichen des Multiplikanden und des Multiplikators sicherstellen, Hin weiterer Nachteil bei dieser bekannten Art der Multiplikation ergibt sich aus der Notwendigkeit der Durchführung von Korrekiuioperationen, und zwar entweder in Form einer Addition oder in Form einer Subtraktion.

Es ist schließlich auch schon eine Multiplikationsvorrichtung bekannt (DEi-OS 14 74 022). bei der ein erstes Register /um Speichern von Vielfachen eines Multipli kanden und ein /weites Register /um Speichern des Multiplikators vorgesehen sind, wobei mit Hilfe einer Vorrichtung zugeteilte Vielfache des Multiplikanden in dem ersten Register mit einem Teil des Multiplikators in dem /weiten Register multipliziert werden. Außerdem erfolgt bei dieser bekannten Vorrichtung gleichzeitig eine Multiplikation eines zugeteilten Vielfaches des Multiplikanden mit dem anderen Teil des Multiplikators in dem /weiten Register. Auf diese Weise werden Teilprodukte gebildet, die dann zur Bildung des Endproduktes hinzuzuziehen sind. Auch bei dieser bekannten Multiplikationsvorrichtung ist wie bei dem eingangs betrachteten Stand der Technik eine große Anzahl von Zyklen für die Durchführung von Multiplikationen bereitzustellen.

Der Erfindung liegt demgemäß die Aufgabe zugrunde, einen Weg zu zeigen, wie bei den Schaltungsanordnungen der eingangs genannten Art bei der Multiplikation zweier Binärzahlen mit einer relativ geringen Anzahl von Zyklen und zugleich ohne Korrekturoperationen ausgekommen werden kann.

Gelöst wird die vorstehend aufgezeigte Aufgabe durch die in den Patentansprüchen 1 und 2 angegebenen Merkmale.

Die Erfindung bringt den Vorteil mit sich, daß ohne die Ausführung von Korrekturoperationen mit einer relativ geringen Anzahl von Zyklen bei der Durchführung einer Multiplikation zwischen zwei Binärzahlen ausgekommen wird. Es wird nämlich in vorteilhafter weise lediglich mn einfachen Äuuiiioiisvorgängen ausgekommen. Damit ergibt sich im vorliegenden Fall insgesamt eine einfachere Operationsweise als bei den bisher bekannten Schaltungsanordnungen zur Multiplikation zweier Binärzahlen.

Weiterbildungen der Erfindung sind in den Unteransprüchen gekennzeichnet.

An Hand von Zeichnungen wird nachstehend ein Ausführungsbeispiel der Erfindung näher erläutert.

F i g. 1 zeigt in einem Blockdiagramm eine bevorzugte Ausführungsform der Erfindung unter Verwendung von eine Operationseinheit für einen mit einem Zweier-Komplement arbeitenden binären digitalen Rechner bildenden Registern, Schaltern und Addierern;

F i g. 2 zeigt in einem Blockdiagramm Verknüpfungselemente, die eine Steuereinheit für die Operationseinheit gemäß F i g. I bilden;

Fig.3 zeigt in einem Verknüpfungsdiagramm eine Ausführungsform eine? Schalters der in F i g. 1 dargestellten Operationseinheit.

Im folgenden sei die in Fig. 1 dargestellte besondere Ausführungsform der Erfindung näher betrachtet. In F i g. 1 sind die für das Rechenwerk erforderlichen Haupteiernente und die Zwischer.verbir.dunger! dargestellt, die zur Ausführung der vorliegenden Erfindung im Rahmen einer bevorzugten Ausführungsform dienen. Bezüglich einer vollständigeren Beschreibung des Datenverarbeitungssystrms sei auf die US-PS !4 I 3 bl hingewiesen.

("in Hauptspeicher 10 gibt Befehlswörter über einer .//-Schalter 11 an einen ZV-Schalter 88 und an eir Hefehls- /Register 78 ab. Außerdem gibt der Hauptspeicher 10 Datenwörter über einen Z/t-Schalter 13 ab. Eir Paar von Datenworten wird über den Z/t-Schalter 15 sowie über einen Zl'-Schalter 12 zu einem 72 Hit-A-f-Register 14 hin geleitet, welches den Multiplikaloroperam enthält. Ein Z/Schalter 20 leitet selektiv Datenwörtet von dem M-Rcgister zu einem 72-Bit-// Register 36 hin bei dem es sich um eines der zwei Operandenregister fin den Haupt-Λ-Addierer 38 handelt. Dieser Datcnwej: wird für verschiedene Operationen benutzt, wie für der Ladebefehl. Das zweite Operandenregister ist eir 72-Bit-/VRegistcr 40, welches von einem ZQJSchaltei 42 her geladen wird. Der Λ-Addierer ist ein 72-Bit-Ad diercr, der selektiv die Rechenoperationen »Addieren« und »Subtrahieren« bezüglich Zweier-Komplement Zahlen sowie die Verknüpfungsoperationen ODER LIND und Exklusiv-ODER ausführt. Die Eingangssigna Ie des Λ-Addiercrs werden durch das Z//-Glied 37 unc durch das Z/V-Glicd 41 ausgewählt. Durch das Z//-Gliec 37 wird als ein erster Eingangsoperand der Operand de; /-/-Registers .36 geliefert, und durch das Z/V-Glicd 41 wird als zweiter Eingangsoperand der Operand de< AZ-RegistTS 40 geliefert. Für die Multiplikation dient da; //-Register als Teilproduktakkumulator, und das AZ-Rc gister enthält das Teilprodukt, das durch den ausgcwähl ten Multiplikandenfaktor gebildet ist. Das Ausgangssi gnal des Α-Addierers wird in einem 72-Bit-/45-Registei 55 gespeichert, oder es kann selektiv über der Zy-Schalter 20 zu dem //-Register hingeleitet werden und über den ZQ-Schelter 42 zu dem /V-Register hin Der jeweilige Inhalt des /4SRegisters wird selektiv zui Speicherung in dem Speicher oder in einem 72-Bit Hauptakkumulator, dem ,4(?-Register 56, weitergeleitet und zwar über den ZD-Schalter 32 bzw. der ZL-Schaltcr 48. Über den ZH-Schalter 46 wird dei jeweilige Inhalt des Hauptakkumulators selektiv derr //- oder dem JV-Register zugeführt, und zwar über der ZySciiaiier 20'uzw.ucn ^Tv-SiMalici 42.

Die Exponententeile von Worten bzw. Wörtern au: dem Speicher 10, die über den Z/-Schalter 11 gelangen werden ebenfalls selektiv, und zwar rechtsbündig, übei einen Zi7-Schalter 16 einem 10-Bit-i>Register T. zugeführt, und zwar zum Zwecke der Trennung eine: Exponenten von einer Gleitkommazahl, oder aber dif betreffenden Exponententeile werden über den ZC Schalter 27 einem lO-Bit-MCT-Register.28 zugeHtet und zwar zum Zwecke der Beibehaltung von Verschie bezählanzeigen und dgl. Zur Ausführung der Exporten tenverarbeätung und von Hüfsfunktionen ist eir Exponenten- F-Addierer 34 vorgesehen. Die Eingangs signale für den Exponenten-Addierer werden über der ZE-Schalter 35 und den ZG-Schalter 26 geliefert Dei Ausgang des Exponenten-Addierers ist mit derr ZF-Schalter 24, dem ZU-Schalter 16 und den ZC-Schalter 27 verbunden. Der ZF-Schalter leite Operanden aus dem D-Register und Ausgangssignali des Exponentenaddierers zu einem F-Register 30 hin.

Die in F i g. 1 dargestellte Anordnung besteht au einer Kombination von Schaltern, Registern um Addierern. Die besondere Ausführung dieser Einrich tungen ist nicht Gegenstand der vorliegenden Erfin dung. Zur Realisierung des A-Addierers 38 genügt es, T. Volladdierer zu verwenden, deren jeder als Eingangs signale ein Bit aus der entsprechenden Bitposition de

jeweiligen ziigeführten Operanden erhall und ein Übertragungssignal von dem Volladdierer nächst niederer Wertigkeit. Der Volladdierer nächst niederer Wertigkeit ist imstande, eine I oder eine 0 als I Ibertragseingangssignal aufzunehmen, und /war entsprechend den Gatter- bzw. .Schallsignalen. Die SuniMir,,yiisgangsM^nale eier Vollnddierer dienen als Addiererausgangssignale für die betreffenden Bitpositionen. und die Ausgangssignale an den Ubcrtragsausgängen der Volladdierer stellen die Ubcrtragseingangssignale für den Volladdierer eier nächst höheren Wertigkeit dar. Der IJbertragsausgang des Volladdicrers nächst höherer Wenigkeit ist mit einem Addicrer-Ubertragsausgangs-I lipflof) verbunden. Neben den betrachteten Elementen ist noch eine Verknüpfungslogik vorgesehen, die einen I 'berlatif feststellt, auf den hin ein OV-Klipflop 44 gesetzt wird. Ir. der Praxis wird der gerade beschriebene einfache Addierer zweckmaßigerweise derart modifiziert. daLl die I Ibcrtrags-Weiterleitungszeil vermindert wird, und zwar durch eine Dbertrags-Vorschau-I.ogik. durch eine ßedingungs-.Summenlogik, etc., und /war wie nach der gewünschten Verarbeitungslcistung. Die Register sind herkömmlicherweise /X-Flipflops, die durch Steuersignale gesteuert bzw. getastet werden. Die Schalter bestehen aus einem Saz von parallelgeschalteten Vcrknüpfungsgliedcrstufen. wie dies bezüglich der ersten Stufe des in I"i g. I angegebenen ZQ-Schalters 42 im einzelnen in F i g. 3 gezeigt ist. Kür die wählbaren Eingangssignale sind UND-Glieder 301, 302, 303, 304 vorgesehen, und zwar für die Eingangssignale von dem ^-Addierer 38. von dem Zfl-Schalter 46. das sind die tatsächlichen Eingangssignale und das Einerkomplement, und für ein Dauersignal »0«. Diese Eingangssignale werden durch Anjegen der entsprechenden Steuersignale M, <fZR, <tZR und $OQ weitergeleitet bzw. getastet. Die Ausgänge dieser UND-Glieder sind odermäßig mit Hilfe eines NOR-Gliedes 306 zusammengefaßt, dessen Ausgangssignal durch ein NAND-Glied 307 invertiert wird.

In C , „ -> <r,r,A Ata I I , ..nlolnmonln oinor C · n, ,„rn, r, Ii n. I diernetzwerk 99 liefert.

Generell sind die Maschinenarbeitsz.yklcn bzw. Maschinenoperationszyklen durch ein von einem Taktgenerator 100 geliefertes .S'G-Taktsignal begrenzt. !Dieser Generator enthält einen Rückkopplungszwcig und ein Verz.ögerungselcment, wie /.. B. ein Schieberegister. Durch die Verwendung einer variablen Verzögerung kann die Dauer jedes Maschmenzyklus auf den Minimalwcrt eingestellt werden, der für den ausgeführten Zyklustyp erforderlich ist, um maximale Leistung hinsichtlich der Befehlsausführung zu erzielen.

Ist während des Maschinenzyklus das GO.S'-Ilipflop im Ein/ustand. so wird der Multiplikand-Operand aus dem Akkumulator/IQ-Register zu dem Operand-N-Register hin verschoben. Das Steuersignal für diesen Zyklus wird durch das GOS-flS-Klipflop 123 geliefert, das sich dabei im Setzzustand befindet. Die Vcrknüplungsiogik 122 steuert das GÜS-Hip Hop wie folgt:
Setzen von GOS = SG ■ GIN ■ Setzen GOF
Rückstellen von GOS = SG ■ GOS

Nachdem der N-Register-Operand gebildet bzw. eingestellt ist, wird die Teilproduktakkumulation während der GOAf-Zyklen ausgeführt. Das Steuersignal für diesen Zyklus wird von dem GOiV/-/?S-Klipf!op 125 geliefert, welches durch die Logik 124 wie folgt gesteuert wird:

Setzen von GOM = SG ■ GOS ■ MPY
Rückstellen von GOM = SG ■ MPY ■ (ACT= I)

Das MPV-Signal wird von dem Operationscode-Decodiernetzwerk 99 geliefert.

Während des letzten Maschinenzyklus der Befehlsausführung wird der gerundete Operand in das /Κ?-Register zurückgeführt. Das Steuersignal für diesen Zyklus wird durch das im Setz-Zustand befindliche GOF-RS-Flipflop 129 geliefert. Die Verknüpfungslogik 128 steuert das GOF-Flipflop wie folgt:
Setzen GOF= SG ■ (GOM-"MPY■ ACT=])
Rückstellen GOF = SG · (COM ■ MPY (ACT= I))

In den Zeichnungen sind die Steuersignale für die Register mit einem vorangestellten »5« bezeichnet, und

bzw. eines Steuerwerks dargestellt, welches Operationscodes decodiert, Maschinenzyklen beginnt und beendet und verschiedene Steuersignale erzeugt. Aus dem Befehls-/-Register 78 gemäß F i g. 1 werden Operationscodeteile der Befehle, nämlieh die Bits 18 bis 26 oder 54 bis 62, selektiv über einen ZOR-Schalter 94 in ein Puffer-ßl-Register 96 eingeleitet. Das ßl-Register liefert ein Eingangssigna¹ für ein P-Register 97, welches seinerseits ein Eingangssignal für ein S'-Register 98 und ein Decodiernetzwerk 95 liefert. Das Decodiernetzwerk steuert das Laden des Multiplikatoroperanden in das M-Register 14. Das ßl-Register erzeugt ferner ein Signal ßl-Voll, welches anzeigt, daß das betreffende Register von dem /-Register geladen worden ist. Dabei wird ein B I-Kennzeichen-Flipflop 101 gesetzt, wenn dem ihm vorgeschalteten UND-Glied 201 ein CY-Takt zugeführt wird. Das Flipflop seinerseits setzt ein P-Kennzeichen-Flipflop 102, welche das ßl-Kennzeichen-Flipflop zurückstellt und einen vorläufigen Operationszyklus GIN durch Setzen eines GW-/?S-F1ipflops 121 einleitet. Währenddessen trist der gebildete Befehl auf, und der Inhalt des ßl-Registers wird zu dem P-Register hin übertragen. Das Setzen des GIN-FWpflops 121 bewirkt, daß der Inhalt des ARegisters zu dem S-Register hin übertragen wird, welches seinerseits bewirkt, daß das 5-Kennzeichen-Flipfiop 103 gesetzt wird, und das Eingangssignal für das Operations-Deco- !επ »fS< bezeichnet. Die Quellen der zum zweiten Signaltyp gehörenden Signale sind explizit in Verbindung mit den Zyklen GW, GOS, GOM und GOF gezeigt. Die Steuersignale zur Steuerung bzw. Tastung der Register werden ebenfalls während dieser Zyklen erzeugt; ihre Vorderflanke wird jedoch bis zu einem Zeitpunkt verzögert, der nahe des Endes der Zyklen liegt. Dies geschieht durch unmäßige Verknüpfung der betreffenden Signale mit dem SC-Taktsignal. Auf diese Weise steht Zeit für eine Übertrags-Weiterleitung bzw. ■Ausbreitung, für eine Leitungs-Einstellzeit, etc. zur Verfugung. Die Registersteuersignale bewirken entsprechend den erzeugten Eingangssignalen lediglich eine Verriegelung der Register.

Die Ausführung der Befehls-Teilmultiplikation erfolgt in folgender Weise durch die vier aufeinanderfolgenden Stufen GIN, GOS. GOM und GOF, die durch die entsprechenden Flipflops in der Steuerlogik gemäß F i g. 2 freigegeben werden. Bei eingeschalteter GIN-Stufe bzw. entsprechend eingestelltem Flipflop wird die Abholung des Multiplikatoroperanden beendet, und das Steuersignal ?ZF leitet den Operanden über den ZP-Schalter in das M-Register 14 ein, welches durch die SM-Signale gesteuert bzw. getastet wird. Der Operand ist eine 36 Bit umfassende Zweierkomplementzahl; er wird in den Bitpositionen 35 bis 70 des M-Registers gespeichert. Die Bitposition 71 niedrigster Wertigkeit

des /W-Registers wird durch den //'-Schalter 12 mit einer Null geladen, wenn der Multiplikator, durch das Steuersignal (,'//'eingeführt wird.

Bei eingeschalteter O'O.S'-Slufc h/.w. bei eintspre chend eingestelltem Flipflop wird das //-Register 36, das /ur Akkumulierung der Teilprodukte dient, durch das an den //Schalter 2U angelegte Steuersignal «Ό/gelöscht. Gleichzeitig w^;rd das Λ CT-Register 20 mil einem Zählergebnis von 18 beaufschlagt, und /war durch das dem ZC-Schalter 18 zugefiihrte Steuersignal φ 18', wenn das S/4CT-Signal dem ACT-Register zugeführt wird. Ferner wird der in Frage kommende Multiplikandenfaktor in das ^-Register geladen, indem das in Frage kommende Steuersignal (OQ. (ZR oder (ZR dem /(^-Schalter 42 zugeführt wird und indem das /V-Regiiter durch das SAW-Signal gesteuert wird. Der Multiplikand wird, so wie er ist, aus dem /!(^-Register 56 über den ΖΛ-Schalter 46 aufgenommen, indem das Steuersignal ^-4C? abgegeben wird, oder er wird durch Zuführen des Steuersignals (K 1 um ein Hit nach rechts verschoben. Im zuletzt genannten Fall wird das Vorzeichenbit des Multiplikanden ebenfalls in die Bitposition höchster Wertigkeit auf der Ausgabehauptleitung umgeschaltet.

Nach Ausführung des Operanden-Voreinstellzyklus werden 18 Multiplikationszyklen ausgeführt, bei denen die GCW-Stufe bzw. das betreffende Flipflop im Einzustand ist. Diese Zyklen sind mit Ausnahme des letzten Zyklus einander gleich, wie dies weiter unten noch näher erläutert werden wird. Während jedes Zyklus erzeugt der /4-Addierer die Summe der akkumulierten Teilprodukte aus dem //-Register und des Multiplikandenfaktors aus dem /V-Register, und zwar auf Steuersignale (RH und (RN hin, die dem ZH-Schalter bzw. dem ZN-Schalter zugeführt werden. Diese Summe wird dann um zwei Bitpositionen nach rechts verschoben in dem //-Register gespeichert, und zwar in Abhängigkeit von dem dem Z/Schalter zugeführten Steuersignal (SR 2 und in Abhängigkeit von dem dem W-Register zugeführten S/Z-Steuersignal. Das Vorzeichen wird gemäß der Exklusiv-ODER-Funktion des Vorzeichen-Bit-Ausgangssignals des Λ-Addie- __„ „_j j,. QU-J.JJ.J.C p;_;--n f····- -J-- -LL..~..i:«-.«

Teilprodukt ausgewählt. Das erzielte Vorzeichen wird in die benachbarte Bit-Position in dem Z/-Schalter gezogen. Gleichzeitig wird der in dem Λΐ-Register befindliche Multiplikator um zwei Bitpositionen nach rechts verschoben. Dies erfolgt auf das Auftreten der dem ZP-Schalter und dem M-Register zugeführten Steuersignale ^M 2 und SM. Gleichzeitig bewirkt der F-Addierer eine schrittweise Verkleinerung des Inhalts des A CT- Registers. Dies erfolgt durch Abgabe eines Steuersignais φ-i an den iTF-Schalter, eines Steuersignals iZFan den ZF-Schaltcr, eines Steuersignals (ACT an den ZG-Schalter, eines Steuersignals ifE an den ZF-Schalter und eines Steuersignals SACT an das 4CT-Register.

Im letzten Zyklus der 18 Zyklen, also dann, wenn der Inhalt des ACT-Registers gleich 1 ist, vereinfacht sich der GCW-Zykius. Das akkumulierte Teilprodukt vom Ausgang des Λ-Addierers wird in dem /V-Register unverschoben gespeichert Demgemäß wird das Steuersignal φΑ dem ZOSchalter zugeführt. Die Verschiebung des Inhalts des M-Registers ist nicht notwendig, jedoch wird der Inhalt des /ACT-Registers in derselben Weise vermindert.

Die Beendigung der Multiplikationsoperatic-v erfolgt bei im Einzustand befindlicher GOF-Stufe. Der betreffende OperationsabschluU um fallt led ig I ic ti die I .'bei ti a ■ gurig des akkumulierten Teilprodukts an das Haupt akkumulator-4y-Rcgister 56. Die Steuersignale cRN. SAS. iAS und SA(J bewirken, dall der Inhalt des WN-Registers über den //V-Schalter, den /^-Addierer, das /AS-Registers und den //.-Schalter /u dem A(^-Register hin übertragen wird. Da kein Steuersignal dem ///-Schalter zugeführt wird, stellt das Ansgangssignal des /\-Addicrers die Summe von Null und das Endprodukt aus dem /V-Register dar.

Der Mulliplikandcnfaktor wird gemäß den lei/ien drei Bits in dem Multiplikator-M-Rcgister und unter Zugrundelegung der oben angegebenen Entscheidungstabelle ausgewählt. Die drei Bits niedrigster Wertigkeit des M-Registers 14 stellen das Eingangssignal für die Logik 150 dar. die die Multiplikandenfaktoren 0. ± 1/2. ± 1 bestimmt. Diese Faktoren sind zweckmäßigerweist, ein Vorzeichensignal und zwei Signale, die die Größe des Multiplikandenfaktors auswählen. Die Logik b/w. Verknupfungsiogik i55 erzeugt, wie oben beschrieben, die Steuersignale cOQ. CZR. CZR. cR 1. cAQ. und /war auf das Auftreten der Multiplikandenfaktor-Signale von der Logik 150 her und auf das Auftreten der Signale GOSund GCM7gemäß F i g. 2.

Begrifflich gesehen umfaßt der Grundrmilliplikationszyklus (I) die Auswahl des Multiplikandenfaktors gemäß den drei Multiplikatorbits niedrigster Wertigkeit und eine arithmetische Rechtsverschiebung des akkumulierten Teilprodukts um zwei Bitpositionen, sodann (2) die Addition des Multiplikandenfaktors /u dem akkumulierten Teilprodukt und eine 2-Bit-Reehtsverschiebung des Multiplikators. Dieser Zyklus unterscheidet sich von einem Standard-Multiplikationszyklus in einer Beziehung, und /war insofern, als die Verschiebung vor der Addition auftritt. Dieser Unterschied ist aus vorstehendem noch nicht hervorgegangen, da die erste Verschiebung nicht explizit ausgeführt wird. Das ursprünglich akkumulierte Teilprodukt ist nämlich Null, so daß es nicht erforderlich ist, den Inhalt des /■/-Registers tatsächlich zu verschieben. Die Schritte (1) und (2) werden dann derart zusammengefaßt, daß die akkumulierten Teilprodukte um zwei Bits r. .ch rechts .. — -..^UnLnn nnrnoi^linH

rMoti

Zyklus erwartet bzw. vorweggenommen wird. Dies trifft mit Ausnahme des letzten Zyklus für die anderen Zyklen zu. Kerner wird gleichzeitig die Auswahl des Muhipiikandenfaktors und die Verschiebung des Multiplikators bewirkt. Wenn die Verschiebung nach der Addition ausgeführt würde, wären zwei gesonderte Wege zur Bildung des Zweifachen und des Vierfachen des Multiplikanden zu beschreiten.

Bezüglich der Bruchteil-Daten ist zu bemerken, daß das gewünschte Ergebnis für n-Rit-Opcrandcn ein (2n-l)-Bit-Produkt ist, das ist ein Vorzeichenbit und das Zweifache des Bruches. In der beschriebenen Ausführungsform wird der 36-Bit-Multiplikator zunächst verdoppelt, wodurch ein 37-Bit-Operand gebildet wird. Da 18 Zyklen vorhanden sind, wird das Vorzeichenbit nicht direkt ais Muitipükatorbit benutzt; seine alleinige Wirkung besteht darin, während des letzten Zyklus den Multiplikandenfaktor als positiv oder negativ auswählen zu lassen. Wenn eine herkömmliche Bruch-Multiplikationsoperation als herkömmliche ganzzahlige Mu'tiplikationsoperation betrachtet wird, die durch eine Abschlußeinstelliing einer Linksverschiejung um eins modifiziert ist, so kann die ursprüngliche Modifikation des Multiplikators in der angegebenen Ausführungsform als eine vorwegnehmende Linksver-

si. hiebi ng des Produkts um eins angesehen werden

Wenn ti ie Multiplikationsoperation auf einer ganz-/.ihligen Basi* betrachtet wird, können der Multiplikator- und Mjiiiplikandenopcrand als auf eine liiniir/ahl des Moduls 2^;" erweitert betrachtet werden, ciii d;is Produkt das Modul 2²ⁿ ist. Man kann das Vorzeichenbii als «-Bit nach links gezogen betrachten. Sodann kann das gewünschte Produkt von zwei positiven Zahlen als elementare Akkumulation von Teilprodukten einsprechend den Positionen der »I«-Bits in dem Multiplikator bcirachtci werden. Während dieser Vorgang eingangs beschrieben worden ist, kann das Vorzeichen -Nachziehen als implizit durch den Verschiebeschritt ausgeführt betrachtet werden, und zwar bei einer Verschiebung um leweils ein I?it. Bei einem negativen Multiplikanden liiuft dasselbe Verfahren ab, wobei das Vorzeichen um eins nachgezogen wird und wobei die akkumulierten Teilprodukte auf das Modul 2²ⁿ beschränkt sind. Bei negaiiven Multiplikatoren können die erwünschten Ergebnisse uadiiKii ei Hätten wciuci'i, udu uic wpci"tinden multipliziert werden als seien sie positive Zahlen unter Zugrundelegung des Moduls 2²ⁿ. Die Ausführung von 2n Zyklen für n-Bit-Operanden ist nicht praktisch und auch unnötig. Wenn der Multiplikator von rechts nach links überprüft wird und wenn das me Bit erreicht ist, kann der Vorgang abgeschlossen werden. Bei einem positiven Multiplikator sind sämtliche nachgezogenen Bits 0, so daß das Produkt durch weitere Zyklen unverändert bleibt. Wenn der Multiplikator negativ ist, sind sämtliche nachgezogenen Vorzeichen-Bits jeweils 1. so daß die Subtraktion des Teüprodukts und der Abschluß des Vorgangs gleich dem vorhergehenden Verfahren ist, wobei sämtliche Bits 1 sind.

In der angegebenen Ausführungsform bewirkt bei negativen Multiplikatoren der letzte Zyklus, daß der Multiplikandenfaktor derart subtrahiert wird, daß dasselbe Ergebnis erhalten wird wie in dem Fall, daß ein zusätzlicher Multiplikationszyklus auf das (n+l)te Bit hin ausgeführt wird, welches die Subtraktion des Multiplikanden bewirkte. Damit hat sich gezeigt, daß die Modifikation des Multiplikatoroperanden zu Beginn der Multiplikationsoperation mit den Vorzeichenkombinatinnc.Rptrarhdinopn 7iiummpniuRt um Hip Stpiiprldtrik und die Verarbeitungsoperationen zu minimisieren.

Die Erfindung ist ferner bei der Verarbeitung von jeweils drei rviuiupiikäiorbiis geeignet. Die Entscheidungstabelle hierführ lautet:

Mllitll'llk.It(Il-	Mulliplik.iiuicn
lllls	liiktnr
Il I 10	Vi
Olli	1
I 000	I
I 001	-Vi
I till)	■- Vi
I (III	1A
I I!)!!	-'Λ
1 101	- V1
I IH)	■ '.',
I I Il	0

Die Faktoren ¹U und — V4 erfordern jedoch die anfängliche Bildung einer »Dreifachgruppe«, d. h. die Bildung des Dreifachen des Multiplikanden, und ein

Multiplikator	Multiplikanden
bits	faktor
0 000	0
0 001	1A
üüiü	'/4
0 011
0 100	y,
OiOS	1U

Dreiergruppe vorgesehen sein. Ferner müssen zusätzliche Schalter und eine Verknüpfungslogik vorgesehen sein, um die für die Entscheidungstabelle erforderlichen Funktionen auszuführen.

Es sei ferner darauf hingewiesen, daß die beschriebene Bruch-Multiplikationsoperation in eine ganzzahligc Multiplikationsoperation übergeführt wird, indem lediglich eine arithmetische Rechtsverschiebung um 1 bei dem in dem Hauptakkumulator-/\C>-Register gespeicherten Ergebnis während des Abschlusses der Operation ausgeführt wird. Ferner ist die Bruch-Multiplikationsoperation direkt bei der Multiplikation der Bruchteile von Gle'tkomma-Zahlen anwendbar.

Die Erfindung kann durch Modifizierung der eingangs beschriebenen herkömmlichen Verarbeitungsanordnung ausgeführt werden, indem das Haupt-Akkumulatorregister sowohl als Teilproduktakkumulator als auch als Multiplikatorregister ausgenutzt wird. Eine derartige Lösung führt jedoch zu stärkeren Schwierigkeiten, wenn es erwünscht i.^cI, auch Gleitkomma-Operationen mit Operanden auszuführen, deren Brüche länger sind als der Hälfte des Hauptakkumulators entspricht.

Abschließend sei noch bemerkt, daß die Erfindung zwar im Zusammenhang mit einer besonderen A 'isführungsform erläutert worden ist, daß die Erfindung darauf jedoch nicht beschränkt ist. Vielmehr ist die Erfindung generell bei digitalen Rechnern anwendbar, die eine Multiplikation dadurch ausführen, daß sie eine Vielzahl von Muitiplikatorbits zu einem Zeitpunkt verarbeiten. So werden z. B. bei der beschriebenen Ausführungsform Paare von Multiplikatorbits von rechts nach links verarbeitet, wobei jedoch die Reihenfolge der Verarbeitung der betreffenden Bitpaare nicht notwendig ist Vielmehr können die betreffenden Bitpaare in irgendeiner Reihenfolge oder, sofern erwünscht, parallel verarbeitet werden; bei derartigen Modifikationen zeigt sich jedoch die Neigung, daß die Kosten der Verarbeiiungsannrdrning ansieigen

Hierzu 2 Blatt Zeichnungen

Claims (5)

Patentansprüche:

1. Schaltungsanordnung zur Ausführung einer Multiplikation zwischen zwei Binärzahlen, mit einem Addierer, der die algebraische Summe eines ersten Operanden und eines zweiten Operanden zu liefern vermag, mit einer an dem Addierer angeschlossenen Akkumulatoreinrichtung, die die von dem Addierer jeweils abgegebene Bitfolge zu speichern und den ersten Operanden für den Addierer zu liefern vermag, mit einem an dem Addierer angeschlossenen Multiplikandenregister, in welchem der durch den Multiplikanden gebildete zweite Operand für den Addierer aufnehmbar ist, und mit einem Multiplikatorregister für die Aufnahme des Multiplikators, dessen Bits in Gruppen von jeweils (n+1) einander unmittelbar benachbarten Bits nach einer vorgegebenen Regel zur Bildung eines Multiplikanden-Vervielfacriingsfaktors bewertet werden, mit welchem der Multiplikand zu multiplizieren ist, wobei das aus dem Multiplikanden und dem jeweiligen Multiplikanden-Vervielfachungsfaktor gebildete Produkt in der Akkumulatoreinrichtung einem in dieser gegebenenfalls bereits enthaltenen entsprechenden, zuvor gebildeter Produkt hinzuzuaddieren ist und wobei mit jeder derartigen Addition eine Verschiebung des Inhalts der Akkumulatoreinrichtung und eine Verschiebung der Auswahl der jeweils zu bewertenden (n+1) einander unmittelbar benachbarten lilts jeweils um η Bits verbunden ist, gekennzeichnet durch

a) eine Einleiteinrichtung (M, 1? 13), die vor der ersten Bewertung des Multiplikators dessen Wert verdoppelt;

b) Verknüpfungseinrichtungen (150), die von dem im Wert verdoppelten Multiplikator ausgehend zwischen jeweils (n+1) unmittelbar benachbarten zu bewertenden Bits und den Multiplikanden-Vervielfachungsfaktoren folgende Zuordnung festlegen

(n+ 1) zu be Multiplikandcn- wertende Bits Vervielfachungs- faktor 000 0 001 '/2 0 10 '/2 011 1 100 -1 101 -'/2 1 10 -'/2 1 11 0

c) derart ausgestattete Zyklussteuereinrichtungen (120-129),

daß lediglich der Wert des mit dem jeweiligen Multiplikanden-Vervielfachungsfaktor multiplizierten Multiplikanden zu dem Inhalt der Akkumulatoreinrichtung (36) hinzuaddiert wird, bevor gegebenenfalls die Bewertung einer weiteren Bitgruppe des im Wert verdoppelten Multiplikators und eine Verschiebung des Inhalts der Akkumulatoreinrichtung (36) erfolgen.

2. Schaltungsanordnung zur Ausführung einer Multiplikation zwischen zwei Binärzahlen, mit einem Addierer, der die algebraische Summe eines ersten Operanden und eines zweiten Operanden zu liefern vermag, mit einer an dem Addierer angeschlossenen Akkumulatoreinrichtung, die die von dem Addierer jeweils abgegebene Bitfolge zu speichern und den ersten Operanden für den Addierer zu liefern vermag, mit einem an dem Addierer angeschlossenen Multiplikandenregister, in welchem der durch den Multiplikanden gebildete zweite Operand für den Addierer aufnehmbar ist, und mit einem Multiplikatorregister für die Aufnahme des Multiplikators, dessen Bits in Gruppen von jeweils (n+1) einander unmittelbar benachbarten Bits nach einer vorgegebenen Regel zur Bildung eines Multiplikanden-Vervielfachungsfaktor bewertet werden, mit welchem der Multiplikand zu multiplizieren ist, wobei das aus dem Multiplikanden und dem jeweiligen Multiplikanden-Vervielfachungsfaktor gebildete Produkt in atr Akkuirrdiatoreinricniung einem in dieser ggf. bereits enthaltenen entsprechenden, zuvor gebildeten Produkt hinzuzuaddieren ist und wobei mit jeder derartigen Addition eine Verschiebung des Inhalts der Akkumulatoreinrichtung und eine Verschiebung der Auswahl der jeweils zu bewertenden (//+1) einander unmittelbar benachbarten Bits jeweils um η Bits verbunden ist, gekennzeichnet durch:

a) eine hinieiteinrichtung (ίί, ί2, Ϊ3), die vor der ersten Bewertung des Multiplikators dessen Wert verdoppelt;

b) Verknüpfungseinrichtungen (150), die von dem im Wert verdoppelten Multiplikator ausgehend zwischen jeweils (n+ 1) unmittelbar benachbarten zu bewertenden Bits und den Multiplikanden-Vervielfachungsfaktoren folgende Zuordnungfestlegen:

(n+1) zu be Multtplikanden- wertende Bits Vervielfachungs- Taktor 0 000 0 0001 ¹A 0010 ¹A 0011 ¹A 0 100 'Λ 0 101 ³A 0110 ³A Olli 1 1000 -1 1001 -³A 1 010 -³A 1011 -'/2 I 100 -'/2 I 101 -¹A 1 110 -¹A 1 111 0

c) derart ausgestattete Zyklussteuereinrichtungen (120-129),

daß lediglich der Wert des mit dem jeweiligen Multiplikanden-Vervielfachungsfaktor multiplizierten Multiplikanden zu dem Inhalt der Akkumulator-

einrichtung (36) hinzuaddiert wird, bevor ggf. die Bewertung einer weiteren Bitgruppe des im Wert verdoppelten Multiplikators und eine Verschiebung des Inhalts der Akkumulatoreinrichtung (36) erfolgen.

3. Schaltungsanordnung nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß den Einleiteinrichtungen (11, 12, 13) ein Register (14) nachgeschaltet ist, welches zur Aufnahme des Multiplikators dient und mit dem die Verknüpfungsschaltung (150) verbunden ist, und daß am Ausgang des Registers (14) ein die Akkumulatoreinrichtung (36) bildendes Akkumulator-Register (36) mit seinem Eingang angeschlossen ist.

4. Schaltungsanordnung nach Anspruch 3, dadurch gekennzeichnet, daß ein Addierer (38) eingangsseitig am Ausgang des Akkumulator-Registers (36) und am Ausgang eines Multiplikanden-Registers (40) angeschlossen ist, welches selektiv einen dem jeweiligen Multiplikandenfaktor entsprechenden Teil des Multiplikanden abgibt, und daß der Addierer (3S) ausgangsseitig mit dem Akkumulator-Register (36) verbunden ist.

5. Schaltungsanordnung nach Anspruch 4, dadurch gekennzeichnet, daß dem Ausgang des Addierers (38) wenigstens ein zusätzliches Register (55, 56) nachgeschaltet ist