DE2221693A1 - Anordnung zur Ausfuehrung einer Multiplikation in einem Rechner - Google Patents

Description

Dfpl.-Ing. Heinz Bardehle

Patentanwalt

Müncten 22, üermstr. 15, Tel. 29 25 55 Pestansctoift München Ik, Postfach 4

L a Mai 1972

Mein Zeichen: P 1377

Anmelder: Honeywell Information Systems Inc.
200 Smith Street,
Waltham, Mass., V. St. A.

Anordnung zur Ausführung einer Multiplikation
in einem Rechner

Die Erfindung bezieht sich auf elektronische digitale
Multipliziereinrichtungen·

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 η der Operanden ist, da nämlich das Produkt das Zweifache der Größe der Operanden annehmen kann. Der Multiplikator wird zweckmäßigerweise in der Hälfte niederer Wertigkeit des Akkumulatorregisters gespeichert. Die Hälfte höherer Wertigkeit des Akkumulators und der Inhalt eines Multiplikandenregisters werden einem Addierer zugeführt. Das Ausgangssignal des Addierers stellt die Summe der akkumulierten Teilprodukte und des potentiellen Teilprodukts dar, das

2098A6/1137

aus dem Einfachen des Multiplikanden besteht· Dabei wird eine Reihe von η Zyklen ausgeführt« Bei jedem Zyklus wird das Bit niedrigster Wertigkeit des Akkuaulators überprüft, und das Ausgangssignal des Addierers wird in der Hälfte höherer Wertigkeit des Akkumulators gespeichert oder nicht, und zwar in Abhängigkeit davon, ob das betreffende Bit eine "1" oder eine "0" ist. Der Akkumulatorinhalt wird um ein Bit nach rechts verschoben, und der Zyklus wird solange 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 Verschiebungen, die das Ergebnis um 2 je Zyklus untersetzen, in richtiger Ausrichtung akkumuliert worden. Es existieren bereits verschiadsne Verfahren zur Verarbeitung der unterschiedlichen Vorzeiclienkombinationen von Operanden sowie zur Verarbeitung von unt^s-oMedlichen Arten von Zahlendarstellungen, d.h. Vorzeichen und Größe, Einerkomplement und Zweierkomplement. Im Zusammenr ang mit Standard-Multiplikationsalgorithmen sei bemerkt* iaß diese in dem Buch "Digital Computer Design Fundamentals" von Yaohan Chu, KcGraw-Hill 1962, Seiten 24 bis 35? beschrieben sind«

Bei 1,6-Bit-Operanden erfordert dieser Vorgang 36 Zyklen, und zwar einschließlich einer Addieroperation je "1" in dem Multiplikator. Damit ist aber Zeit erforderlich, um den ü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 Akkumulator bzw. Akkumulatorinhalt hinzuzuaddierön oder von diesem zu

2 Ü 9 e ·■< Ü / 1 1 3 7

subtrahieren, Beispiele für diese Art von Multiplikation sind in dem Buch "The Logic of Computer Arithmetic" von Ivan Flores, Prentice-Hall, Inc., I963, Seiten 164 bis 174, beschrieben. Bei dieser Verfahrensweise wird eine Bitfolge "11" als Bitfolge behandelt, die eine Subtraktion des Multiplikanden und. ein Übertragsausgangssignal fordert, das gespeichert wird und das effektiv die Addition des Vierfachen des Multiplikanden während des nächsten Zyklus bewirkt. Eine Modifikation dieses Algorithmus ist in Zeitschrift "Proceedings of the IRE", Januar I96I, Seiten 73 bis 75 unter dem Titel "High-Speed Arithmetic in Binary Computers" von O.L.MacSorley beschrieben.

Bei diesem Algorithmus ist die nachstehende Entscheidungstabelle angegeben:

Multiplikator-Bits Benutztes Multiplikanden-Vielfach

+2 +2 +4 -4 -2 -2

Ein Merkmal des Algorithmus besteht darin, daß auf die Überprüfung des jeweiligen Bit-Paares von rechts nach links angenommen ist, daß bei ungeradzahligen Werten im vorausgehenden Zyklus das akkumulierte Teilprodukt um das Einfache des Multiplikanden zu niedrig gemacht worden ist«. Wenn das

0	00
0	01
0	10
0	11
1	00
1	01
1	10
1	11

209846/1137

nächste Bit-Paar ungerade ist, führt dies darüber hinaus zu einem Teilprodukt, auf Grund 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 niedrigster Wertigkeit eine besondere Behandlung, In der zuletzt genannten Zeitschrift ist die Anwendung eines Sonderzyklus angegeben, in welchem ein Paar von Blind-Null-Bits dem Multiplikator hinzuaddiert wird; im übrigen ist in der zuletzt genannten Zeitschrift eine Modifikation des ersten Zyklus angegeben, und zwar eine solche Modifikation, daß eine Subtraktion des Multiplikanden erfolgt, wenn das Bit niedrigster Wertigkeit eine "1" ist.

Für praktische Anwendungsfälle stellt die Forderung, dass Multiplikanden-Vielfache von 2 und 4 zu verarbeiten sind, ein praktisches Problem insofern dar, als zwei Wege zu dem Addierer Mn beschritten werden müssen, und zwar zusätzlich zu dem Grundweg, der zur Ausführung der direkten Operationen nach Art von Additionen dient. Darüber hinaus muß die Verknüpfungslogik richtige Ergebnisse für sämtliche Kombinationen von Vorzeichen des Multiplikanden und des Multiplikators sicherstellen.

Der Erfindung liegt demgemäß die Aufgabe zu Grunde, eine Anordnung zur Zweier-Komplement-Multiplikation zu schaffen, die bei η Bits umfassenden Multiplikatoren nur n/2-Zyklen erforderte

Gelöst wird die vorstehend aufgezeigte Aufgabe durch die im Patentanspruch 1 angegebene Erfindung. Die erfindungsgemäße Anordnung ist dadurch gekennzeichnet,

6/1 137

a) daß ein Addierer vorgesehen ist, der die algebraische Binärsumme eines ersten und zweiten Eingangsoperanden erzeugt,

b) daß mit dem Addierer eine Akkumulatoreinrichtung ver« bunden ist, die das Ausgangssignal des Addierers speichert und den ersten Addierer-Eingangsoperanden liefert,

c) daß mit dem Addierer eine Multiplikandeneinrichtung verbunden ist, die den zweiten Addierer-Eingangsoperanden liefert,

d) daß eine Multipliziereinrichtung vorgesehen ist, die einen m-Bit-Multiplizierfaktor speichert,

e) daß mit der Multipliziereinrichtung eine Verknüpfungseinrichtung verbunden ist, die auf den Zustand einer Vielzahl von n+1 aufeinanderfolgender Multiplizierbit-Positionen zum Zwecke der Auswahl eines algebraischen Vielfachfaktors des Multiplikanden anspricht, und zwar zur Abgabe des betreffenden Faktors an den Addierer, wobei der betreffende Faktor den algebraischen Wert der überprüften Bits besitzt, welche in der Weise modifiziert sind, daß das Faktorvorzeichen in dem Fall negativ ist, daß das Bit höchster Wertigkeit eine 1 ist, und daß die Faktorgröße um 1 in dem Fall vergrößert wird, daß das Bit niedrigster Wertigkeit eine 1 ist,

f) daß eine Zyklussteuereinrichtung vorgesehen ist, die die Speicherung des Addiererausgangssignals in der Akkumulatoreinrichtung und die Verschiebung des Inhalts der Multiplikatoreinrichtung und der Akkumulatoreinrich· tung um η Bit-Positionen bewirkt, und

g) daß Abschlußeinrichtungen vorgesehen sind; die die Zyklussteuereinrichtung nach m/n Zyklen außer Betriefe setzen·

2038 4 6/1137

Gsmä3 einer AusfüIirungsforoL der Erfindung wird die Multiplikation auf fclgsnda Wsise ausgeführt. Der Multiplikator ^ird in ein Multiplikator:Bister geladen und vor Ausführung der Mnltiplitati^- .art zwei multipliziert. Dies bedeutst, daß dsr Multiiylikst:·^ im ein Bit nach links verschoben gespeichert r ,r·-_; wobei lie Bitposition niedrigster Wertigkeit alt sin^r Iiul.1 i^HgeiülLc vrird, Ein Standar-dzyklus wird wie -wlgt gswäMt* Das aidßsv:iicrts Teilprodukt wird um zwei ^T*its nach rechts marsch-·:,s.^i, d*h. durch vl«r dividiert, w-3^;"4wn di5 i^ltÄplikaLasiifalctareii entsprechend nach

stehender	or-3its	Multiplikandenfaktor·
Multi		0
		1/2
		1/2
		1
		-1
		-1/2
		-1/2
		0
.ßiikat
O OO
0 01
G 10
0 11
1 00
1 01
1 10
1 11

Wenn das Multiplikatorbit-Paar erreicht ist, welches das Vorzeichenbit besitzt wie das Bit in dein nächsten zu überprüfenden Bit-Paar« so wird nach der Standardtabelle vorgegangen, und die Multiplikationszyklen werden abgeschlossen. Dies bedeutet» daß das Vorzeichenbit die Ausführung als Steuerung der Operation bezüglich der beiden benachbarten Multipiikatorbits in die Wege leitet, ansonsten aber unberücksichtigt bleibt. Dies führt genau zu n/2 Zyklen.

;? λ et c /,!] /

~⁷~ 222Ί693

An Hand von Zeichnungen wird die Erfindung nachstehend an Beispielen näher erläutert.

Fig. 1 zeigt in einem Blockdiagramm eine bevorzugte Ausführungsforai der Erfindung unter Yeranschaulichung von eine Operationseinheit für einen mit einem Zweier-Komplement arbeitenden binären digitalen Rechner bildenden Registern, Schaltern und Addierern.

Fig. 2 zeigt in einem Blockdiagramm Verknüpfungselemente, die eine Steuereinheit für die Operationseinheit gemäß Fig. 1 bilden.

Fig. 3 zeigt in einem Verknüpfungsdiagramm eine Ausführungsfona. eines Schalters der in Fig. 1 dargestellten Operationseinheit.

Im folgenden sei die in Fig. 1 dargestellte besondere Ausführungsfora der Erfindung näher betrachtet. In Fig„ 1 sind die für das Rechenwerk erforderlichen Hauptelemente und die Zwischenverbindungen dargestellt, die zur Ausführung der vorliegenden Erfindung im Rahmen einer bevorzugten Ausführungsform dienen· Bezüglich einer vollständigeren Beschreibung des Datenverarbeitungssystems sei auf die US-PS 3 413 613 hingewiesen.

Ein Hauptspeicher 10 gibt Befehlswörter über einen ZI-Schal-

Befßhlster 11 an einen ZT-Schalter 88 und an ein/!«Register 78 ab« Außerdem gibt der Hauptspeicher 10 Datenwörter über einen ZA-Schalter 13 ab. Ein Paar von Datenworten wird über den ZA-Schalter 13 sowie über einen ZP-Schalter 12 zu einem 72-Bit-M-Register 14 hin geleitet, welches den Multiplikatoroperand enthält. Ein ZI-Schalter 20 leitet selektiv Datenwörter von dem M-Register zu einem 72-Bit-H-Register 36 hin,

2 0 9 8 A 6 / 1 1 3 7

2221633

bei dem es sich um eines der zwei Operandenregister für den Haupt-A-Addierer 38 handelt. Dieser Datenweg wird für verschiedene Operationen benutzt, wie für den Ladebefehl. Das zweite Operandenregister ist ein 72-Bit-N-Register 40, welches von einem ZQ-Schalter 42 her geladen wird. Der Α-Addierer ist ein 72-Bit-Addierer, der selektiv die Rechenoperationen addieren und subtrahieren bezüglich Zweier-Komplement-Zahlen sowie die Verknüpfungsoperationen ÖDER, UND und Exklusiv-ODER ausführt. Die Eingangssignale des A«Addierere werden durch das ZH-Gatter 37 und durch das ZN-Gatter 41 ausgewählt. Durch das ZH-Gatter 37 wird als ein erster Eingangsoperand der Operand des H-Registers geliefert, und durch das ZN-Gatter 41 wird als zweiter Eingangsoperand der Operand des N-Registers 40 geliefert. Für die Multiplikation dient das H«Register als Teilproduktakkumulator, und das N-Register enthält das Teilprodukt, das durch den ausgewählten Multiplikandenfaktor gebildet ist. Das Ausgangssignal des Α-Addierers wird in einem 72-Bit-AS-Register 55 gespeichert, oder es kann selektiv über den ZJ-Schalter 20 zu dem Η-Register hingeleitet werden, und über den ZQ-Schalter 42 zu dem N-Register hin. Der jeweilige Inhalt des AS-Registers wird selektiv zur Speicherung in dem Speicher oder in einem 72-Bit-Hauptakkumulator , dem AQ-Register 56, weitergeleitet, und zwar über den ZD-Schalter 32 bzw. den ZL-Schalter 48. Über den ZR-Schalter 46 wird der jeweilige Inhalt des Hauptakkumulators selektiv dem H- oder dem N-Register zugeführt, und zwar über den ZJ-Schalter 20 bzw. den ZQ-Schalter 42„

Die Exponententeile von Worten bzw. Wörtern aus dem Speicher 10, die über den ZI-Schalter 11 gelangen, werden

209846/ 1137

ebenfalls selektiv, und zwar rechtsbündig, über einen ZU-Schalter 16 einem 1O-Bit-D-Register 22 zugeführt, und zwar zum Zwecke der Trennung eines Exponenten von einer Gleitkommazahl, oder aber die betreffenden Exponententeile werden über den ZC-Schalter 27 einem 10-Bit-ACT-Register 28 zugeleitet, und zwar zum Zwecke der Beibehaltung von Verschiebezählanzeigen und dgl.. Zur Ausführung der Exponentenverarbeitung und von Hilfsfunktionen ist ein Exponenten-E-Addierer 34 vorgesehen. Die Eingangssignale für den Exponenten-Addierer werden über den ZE-Schalter 25 und den ZG-Schalter 26 geliefert. Der Ausgang des Exponenten-Addierers ist mit dem ZF-Schalter 24, dem ZU-Schalter 16 und dem ZC-Schalter 27 verbunden. Der ZF-Schalter leitet Operanden aus dem D-Register und Ausgangssignale des Exponentenaddierers zu einem E-Register 30 hin.

Die in Fig. 1 dargestellte Anordnung besteht aus einer Kombination von Schaltern, Registern und Addierern. Die besondere Ausführung dieser Einrichtungen ist nicht Gegenstand der vorliegenden Erfindung. Zur Realisierung des A-Addierers genügt es, 72 Volladdierer zu verwenden, deren jeder als Eingangssignale ein Bit aus der entsprechenden Bitposition des jeweiligen zugeführten Operanden erhält und ein Übertragseingangssignal von dem Volladdierer nächst niederer Wertigkeit. Der Volladdierer nächst niederer Wertigkeit ist imstande, eine 1 oder eine 0 als Übertragseingangssignal aufzunehmen, und zwar entsprechend den Gatter— bzw. Schaltsignalen. Die Summenausgangssignale der Volladdierer dienen als Addiererausgangssignale für die betreffenden Bitpositionen, und die Ausgangssignale an den Übertragsausgängen der Volladdierer stellen die Übertragseingangssignale

209846/1 1 37

"¹⁰" · 2 2 216 9

für den Volladdierer der nächst höheren Wertigkeit dar. Der Übertragsausgang des Volladdierers nächst höherer Wertigkeit Ist mit einem Addierer-Übertragsausgangs-Flipflop verbunden.. Heben den betrachteten Elementen ist noch eine Verknüpfungslogik vorge^eh-^., die einen Überlauf feststellt, auf den hin ein OV-Flipflop 92 gesetzt wird. In der Praxis wird der gerade beschrieb^:, y einfache Addierer zweckmäßigerweise derart modifiziert- dsH die ülr-ertrags-Weiterleitungszeit vermindert wird* und sws.r d'irch eine Übertrags-Vorschau-Logik, durch eine Bedingurrn—Summenlogik, etc., und zwar vie nach der gewünschten Verarbeitungsleistung., Die Register «ind hsrkörcmlieherweise DC-*F.lipflops, die durch Steuersignale gesteuert bzw.. geto&tet werden» Die Schalter bestehen aus einem Satz \^ren parallel geschalteten Verknüpfungsgatterstiifen, wie die,= bezüglich der ersten Stufe des ZO«Schalters 42 in Fig. 3 gezeigt ist. Für die wählbaren Eingangssignale sind WIP-Gatter 301, 302, 303, 304 vorgesehen^ und zwar für die Kingsngssignale von dem A-Addierer 38, von dem ZR«Schalter 46_ä, das sind die tatsächlichen Eingangssignale und das Einerkomplement, und für ein Dauersignal "0". Diese Eingangssignal werden durch Anlegen der entsprechenden Steuersignale ^A, ^ZR^ φ TK und ^0Q weitergeleitet bzw. getastet* Die Ausgänge dieser UND-Gatter sind odermäßig mit Hilfe eines NOR-Gatters 306 zusammengefaßt, dessen Ausgangssignal durch ein NAND-Gatter 30? invertiert wird.

In Fig» 2 sind die Hauptelemente einer Steuereinheit bzw. eines Steuerwerks dargestellt, welches Operationscodes decodiertj Maschinenzyklen beginnt und beendet und verschiedene Steuersignale erzeugt« Aus dem Befehls-I-Register gemäß Fig« 1 werden Operationscodeteile der Befehle, nämlich

2098 A6/1137

die Bits 18 bis 26 oder 54 bis 62, selektiv über einen ZOR-Schalter 94 in ein Puffer-B1-Register 96 eingeleitet. Das B1-Register liefert ein Eingangssignal 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 B1-Register erzeugt ferner ein Signal BI-V0II, welches anzeigt, daß das betreffende Register von dem I-Register geladen worden ist. Dabei wird ein B1-Kennzeichen-Flipflop 101 gesetzt, wenn dem ihm vorgeschalteten UND-Gatter 201 ein CX-Takt zugeführt wird. Das Flipflop seinerseits setzt ein P-Ksimzeichen-Flipflop 102, welches das B1-Kennzeichen-Flipflop zurückstellt und einen vorläufigen Operationszyklus GIK dureli Setzen eines GIN-RS-Flipflops 121 einleitet. Währenddessen tritt der gebildete Befehl auf, und der Inhalt des B1»Registers wird zu dem P-Register hin übertragen. Das Setzen des GIN-Flipflops 121 bewirkt, daß der Inhalt des B-Registers zu dem S-Register hin übertragen wird, welches seinerseits bewirkt, daß das S-Kennzeichen-Flipflop 103 gesetzt wird, und das Eingangssignal für das Operations-Decodiernetzwerk liefert.

Generell sind die Maschinenarbeitszyklen bzw. Maschinenoperationszyklen durch ein von einem Taktgenerator 100 geliefertes SG-Taktsignal begrenzt. Dieser Generator enthält einen Rückkopplungszweig und ein Verzögerungselement, wie ein Schieberegister. Durch die Verwendung einer variablen Verzögerung kann die Dauer jedes Maschinenzyklus auf den Minimalwert eingestellt werden, der für den ausgeführten Zyklustyp erforderlich ist, um maximale Leistung hinsichtlich der Befehlsausführung zu erzielen.

20984 6/1137

2 2 216 9

Ist während des Maschinenzyklus das GOS-Flipflop im Einzustand, so wird der Multiplikand-Operand aus dem Akkumulator-AQ-Register zu dem Operand-N-Register hin verschoben. Das Steuersignal für diesen Zyklus wird durch das GOS-RS-Flipflop 123 geliefert, das sich dabei im Setzzustand befindet. Die Verknüpfungslogik 122 steuert das GOS-Flipflop wie folgt:
Setzen von GQS = 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 GOM-Zyklen ausgeführt. Das Steuersignal für diesen Zyklus wird von dem GOM-RS-Flipflop 125 geliefert, welches durch die Logik 124 wie folgt gesteuert wird:

Setzen von GOM = SG · GOS · MPY

Rückstellen von GOM = SG · MPY · (ACT = 1) Das MPY-Signal wird von dem Operationscode-Decodiernetzwerk geliefert«

Während des letzten Maschinenzyklus der Befehlsausführung wird der gerundete Operand in das AQ-Register zurückgeführt. Das Steuersignal für diesen Zyklus wird durch das im Setz-Zustand befindliche GOF-RS-Flipflop 129 geliefert,

logik
Die Verknüpfungsn28 steuert das GOF-Flipflop wie folgt:

Setzen GOF = SG · (GOM · MPY · ACT = 1) Rückstellen GOF = SG · (GOM · MPY · (ACT = 1))

In den Zeichnungen sind die Steuersignale für die Register mit einem vorangestellten "S" bezeichnet, und die übrigen Steuersignals sind mit einem vorangestellten "ji"

209 S 1 6 / 1137

bezeichnet. Die Quellen der zum zweiten Signaltyp gehörenden Signale sind explizit in Verbindung mit den Zyklen GlH, 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 undmäßige Verknüpfung der betreffenden Signale mit dem SC-Taktsignal. Auf diese Weise steht Zeit für eine Übertrags-Weiterleitung bzw. -Ausbreitung, für ein© Leitungs-Einstellzeit, etc₀ zur Verfügung. 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äß Fig. 2 freigegeben werden® Bei eingeschalteter GIN-Stufe bzw. entsprechend eingestelltem Flipflop wird die Abholung des Multiplikatoroperanden beendet, und das Steuersignal j£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 Zweierkomplementzahl5 er wird in den Bitpositionen 35 bis 70 des M-Registers gespeichert«, Die Bitposition 71 niedrigster Wertigkeit des M-Registers wird durch den ZP-Schalter 12 mit einer Null geladen^ wenn der Multiplikator durch das Steuersignal ^ZF eingeführt wird«,

A«i eingeschalteter GOS-Stufe bzw. bei entsprechend eingestellt«» Flipflop wird das H-Register 36, das zur Akkumulierung der Teilprodukte dient, durch das an des Zugschalter

209846/1137

.'.'221693

efvte Steyerslsnal ₄e0J gelöscht; Gleichzeitig wird das ACT-ReP;U.t&T 2C- mit einjm Zählerg-.-VnIs vor 18 beaufschlagt, uric"- ?.v/c:T- £i:i*·?^ «j.as i.®m ZOSeh-Ite¹ -¹O -zugeführte Steuersignal ^13. wer-ϊί d?8 8£.Gf»Sigr;rl dar AC-v¹- '"'^«,Irter zugeführt wird. Ferrer -xirfi ^r I_n Fr?.r:v -T-.ntercr '■:-/':li:pllkari lenfaktor in das N-Rogi-st-ε.·/ geladeru itid^r- ■';;·<-, in y- . _; ^ kcmunanie Steuersignal jiiOQj νΓ:^" M-^r j'ZF Πλ-;· ZC •^^hs'ltar ■ .:. ^--.ciohrt wird und indem aos Ν"?'Λ^ί.^ΐ^Γ οϋ^ΛΐΛ d?.--; Sr " ^ί.£Γ.'"'. ·:. ;--:1,oiiGrt wirr; Der MuIt" pi'' ^::-r-c^: «^-t^lc^: h,o vji?_; f- :lt:t ^:.\;ώ Λ: <.l AQ-Rcgictv-;r 56 über den ZF----'^::"c}..a."-.t"^i.ⁱ 46 ε,ι-^Θηοι^ϊ^ηί ϊ^λαν. dan οίνυβϊίύ nnal £%.Q abgegeb·-⁷ ^^Γ:"ι-Λτ oitr ar νΐ-'ά dure:> l-vfuhi^en des Steuersignals iiRI ι«-* (M?;. Bit lii'^-V- r-^ob^-s versciic:;-·· ^, Im zuletzt genannten Fal2. vl- ' 0^.8 Vor-i;r-lch^i:>b:i-i:- des Kvltiplikanden ebenfalls in d.io ΜΐΚ'ΒΐΐΐοΒ höchster W^i-tigkeit auf der Ausgabehauptleituiig um^e-sc-bali-o't, ^ouur&h eine Yorzeiclienverwischung auftrittί

ilacb /η=ρfübriing d^s Opei'anden^Ycrerrrtellzyklus werden ■·θ Mal^-iVvl'-iiia-iionssyklen ausgeführt, bei denexi die GOM-Stufe b^v. das betreffende Flipflop im "jinzuztand Jst_B Diese Zyk'isK sind mit Ausnahme des letzter Zyklus einander gleich, wie ditici reiter unten noch Daher erläutert werden wird. Während ^«edes Zykltii» e:i*zougt der A-Äddierer die Summe der

ei'teir, Tei.lprodukte aus der: Η-Register und des Multinfalitorii aus dem !!««Register, und zwar auf Steuersignale ^RH und φΕΜ hi,n_t die dem ZH-Schalter bzw. dem ZN-Sohalter zugeführt werden₀ Diese 'oimniv. wird dann in dem !!-Register gespeichert_f um zwei Bitpositionen nach rechts verschoben, und zwar in Abhängigkeit von dem dem ZJ-Schalter zugeführten Steuersignal ^SR2 und in Abhängigkeit von dem dom H~Register zugeführten SH-Steuersignal« Das Vorzeichen

2098A6/1137

wird gemäß der Exklusiv-ODER-Funktion des Vorzeichen-Bit-Ausgangssignals des Α-Addierers und des Überlauf«= Flipflops für das akkumulierte Teilprodukt ausgewählt» Das erzielte Vorzeichen wird in die benachbarte: Bit-Position in dem ZJ-Schalter gezogen. Gleichzeitig wird der in dem M-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 f£M2 und SM. Gleichzeitig bewirkt der Ε-Addierer eine schrittweise Verkleinerung des Inhalts des ACT-Registers₀ Dies erfolgt durch Abgabe eines Steuersignals ji-1 an den ZF-Schalter, eines Steuersignals φΖΈ an den ZE-Schalter, eines Steuersignals ^ACT an den ZG-Schalter, eines Steuersignals φΈ an den ZF-Schalter und eines Steuersignals SAGT an das ACT-Register.

Im letzten Zyklus der 18 Zyklen, also dann, wenn der Inhalt des ACT-Registers gleich 1 ist, vereinfacht sich der GOM-Zyklus. Das akkumulierte Teilprodukt vom Ausgang des A-Addierers wird in dem K-Register unverschoben gespeichert« Demgemäß wird das Steuersignal £k dem ZQ-Schalter 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 Multiplikationsoperation erfolgt bei im Einzustand befindlicher GOF-Stufe. Der betreffende Operationsabschluß umfaßt lediglich die Übertragung des akkumulierten Teilprodukts an das Hauptakkuinulator-AQ~Register 56. Die Steuersignale jiRN, SAS, fiAS und SAQ bewirken, daß der Inhalt des RN-Registers über den ZN-Schalter, den A-Addierer, das AS-Register und den ZL-Schalter zu dem

2098 l> 6/1137

AQ-Register hin übertragen wird. Da kein Steuersignal dam ZH-Schalter zugeführt wird, stellt das Ausgangssignal des Α-Addierers die Summe von Null und das Endprodukt aus dem N-Register dar.

Der Multiplikandenfaktor wird gemäß den letzten drei Bits in dem Multiplikator-M-Register 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, ii bestimmt. Diese Faktoren sind zweckmäßigerweise ein Vorzeichensignal und zwei Signale, die die Größe des Multiplikandenfaktors auswählen. Die Logik bzw. Verknüpfungslogik 155 erzeugt, wie oben beschrieben, die Steuersignale ^0Q, j£ZR, jßÜR", j&l1, j^AQ, und zwar auf das Auftreten der Multiplikandenfaktor-Signale von der Logik 150 her und auf das Auftreten der Signale GOS und GOM gemäß Fig. 2.

Begrifflich gesehen umfaßt der Grundmultiplikationszyklus (1) 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 zu dem akkumulierten Teilprodukt und eine 2-Bit-RechtsverSchiebung des Multiplikators. Dieser Zyklus unterscheidet sich von einem Standard-Multiplikationszyklus in einer Beziehung, und zwar 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

209846/1137

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 nach rechts verschoben gespeichert werden, wodurch der nächste Zyklus erwartet bzw. vorweggenommen wird. Dies trifft mit Ausnahme des letzten Zyklus für die anderen Zyklen zu. Ferner wird gleichzeitig die Auswahl des Multiplikandenfaktors 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-Bit-Operanden ein (2n-1)-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 als Multiplikatorbit benutztj 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 Multiplikationsoperation betrachtet wird, die durch eine Abschlußeinstellung einer Linksverschiebung um eins modifiziert ist, so kann die ursprüngliche Modifikation des Multiplikators in der angegebenen Ausführungsform als eine vorwegnehmende Linksverschiebung des Produkts um eins angesehen werden.

Wenn die Multiplikationsoperation auf einer ganzzahligen Basis betrachtet wird, können der Multiplikator- und Multiplikandenoperand als auf eine Binärzahl des Moduls 2

209846/1137

erweitert betrachtet werden, da das Produkt d£s Modul 2 ⁿ ist. Man kann das Vorzeichenbit als η-Bit nach links gezogen betrachten. Sodann kann das gewünschte Produkt von zwei positiven Zahlen als elementare Akkumulation von Teilprodukten entsprechend den Positionen der "1"-Bits in dem Multiplikator betrachtet 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 jeweils ein Bit. Bei einem negativen Multiplikanden läuft dasselbe Verfahren ab, wobei das Vorzeichen um eins nachgezogen wird und wobei die akkumulierten Teilprodukte auf das Modul 2 beschränkt sind. Bei negativen Multiplikatoren können die erwünschten Ergebnisse dadurch erhalten werden, daß die Operanden 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 nte 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 Teilprodukts 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+1)te Bit hin ausgeführt wird,

2098A6/1137

welches die Subtraktion des Multiplikanden bewirkte«, Damit hat sich gezeigt, daß die Modifikation des Mutliplikatorojfceranden zu Beginn der Multiplikationsoperation mit den Vorzeichenkombinations-Betrachtungen zusammenpaßt, um die Steuerlogik und die Verarbeitungsoperationen zu minimisieren.

Die Erfindung ist ferner bei der Verarbeitung von jeweils drei Multiplikatorbits geeignet. Die Entscheidungstabelle hierfür lautet:

Multiplikatorbits	Multiplikandenfaktor
0 000	0
0 001	1/4
0 010	1/4
0 011	1/2
0 100	1/2
0 101	3/4
0 110	3/4
0 111	1
1 000	-1
1 001	-3/4
1 010	-3/4
1 011	-1/2
1 100	-1/2
1 101	-1/4
1 110	-1/4
1 111	0 .

Die Faktoren 3/4 und -3/4 erfordern jedoch die anfängliche Bildung einer "Dreifachgruppe", d.h. die Bildung des Dreifachen des Multiplikanden, und ein Register muß zur

209846/1137

/ c 2 1 6 3 3

Speicherung der Dreifachgruppe bzw. 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 ganzzahlige Multiplikationsoperation übergeführt wird, indem lediglich eine arithmetische Rechtsverschiebung um 1 bei dem in dem Hauptakkumulator-AQ-Register gespeicherten Ergebnis während des Abschlusses der Operation ausgeführt wird. Ferner ist die Bruch-Multiplikationsoperation direkt bei der Multiplikation der Bruchteile von Gleitkomma-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 ist, auch Gleitkomma-Operationen mit Operanden auszuführen, deren Brüche langer sind als der Hälfte des Hauptakkumulators entspricht.

Abschließend sei noch bemerkt, daß die Erfindung zwar im Zusammenhang mit einer besonderen Ausfü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 Multiplikatorbits zu einem Zeitpunkt verarbeiten. So werden z.B. bei der beschriebenen Ausführungsform Paarevon Multiplikatorbits von recht nach

209846/Ί 137

links verarbeitet, wobei jedoch die Reihenfolge der Verarbeitung der betreffenden Bitpaarenicht 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 Verarbeitungsanordnung ansteigen.

209846/1 1 37

Claims (1)

Patentansprüche Anordnung zur Ausführung einer Multiplikation in einem binären Rechner, dadurch gekennzeichnet, a) daß ein Addierer (38) vorgesehen ist, der die algebraische Binärsumme eines ersten und zweiten Eingangsoperanden erzeugt, b) daß an dem Addierer (3B) eine Akkumulatoreinrichtung (36) angeschlossen ist, die das Ausgangssignal des Addierers (38) zu speichern vermag und die den ersten Eingangsoperanden für den Addierer (38) liefert, c) daß mit dem Addierer (38) eine Multiplikandeneinrichtung (40) verbunden ist, die den zweiten Eingangsoperanden für den Addierer (38) liefert, d) daß eine Multiplikatoreinrichtung (14) vorgesehen ist, die einen m Bit umfassenden Multiplikatorfaktor speichert, e) daß mit der Multiplikatoreinrichtung (14) Verknüpfungseinrichtungen (150) verbunden sind, die auf den Zustand einer Vielzahl von (n+1) aufeinanderfolgender Multiplikator-Bits hin einen algebraischen Vervielfachungsfaktor des Multiplikanden zur Abgabe an den Addierer (38) auswählen, wobei der Vervielfachungsfaktor den algebraischen Wert der überprüften Bits enthält, die derart modifiziert sind, daß das Faktorvorzeichen in dem Fall negativ ist, daß das Bit höchster Wertigkeit eine 1 ist, und daß die Faktorgröße um 1 in dem Fall vergrößert ist, daß das Bit an niedrigster Stelle eine 1 ist, f) daß Zyklussteuereinrichtungen (120 bis 129) vorgesehen sind, die die Einspeicherung des Ausgangssignals des Addierers (38) in der Akkumulatoreinrichtung (36) und 209846/1137 die Verschiebung des Inhalts der Multiplikatoreinrichtung (40) und des Inhalts der Akkumulatoreinrichtung (36) um η Bit-Positionen bewirken, und g) daß Abschlußeinrichtungen (100) vorgesehen sind, die den Betrieb der Zyklussteuereinrichtungen (120 bis 129) nach m/n Zyklen beenden. 2. Anordnung nach Anspruch 1, dadurch gekennzeichnet, daß Einrichtungen vorgesehen sind, die die Bitstelle niedrigster Wertigkeit der Multipliziereinrichtung (14) mit einer Null versehen. 3. Anordnung nach Anspruch 1 oder 2, dadurch gekennzeichnet, a) daß der Addierer (38) einen Übertragseingang aufweist, b) daß die Multiplikandeneinrichtung (36) ein Teilprodukt-Akkumulatorregister ist, welches die Jeweils akkumulierten Teilprodukte zu speichern vermag, c) daß die Multiplikandeneinrichtung (40) ein Multiplikandenregister ist, welches einen Multiplikanden speichert und selektiv ein Vielfaches von 1/2, 1 oder des betreffenden Multiplikanden abzugeben vermag, d) daß die Multiplikatoreinrichtung (14) ein Multiplikatorregister ist, welches eine zusätzliche Registerstelle enthält, e) daß eine Einleiteinrichtung (11,12,13) vorgesehen ist, die einen Multiplikator in das Multiplikatorregister (14) zu laden gestattet, der mit zwei multipliziert und rechtsbündig auftritt, f) daß die Verknüpfungseinrichtungen (150) auf die Bits in den beiden Bitpositionen niedrigster Wertigkeit 209 846/1137 des Multiplikatorregisters (14) Lind des Bits der benachbarten Bitposition hin den Multiplikationszyklus entsprechend folgenden Regeln steuern: I. Subtraktion eines von Null verschiedenen Multiplikandenvielfaches bei einer 1 in der benachbarten Bitposition; II. Auswahl eines O-Multiplikandenvielfaches in dem Fall, daß sämtliche überprüften Bits gleich sind; III. Auswahl eines 1-Multiplikandenvielfaches in dem Fall, daß die Multiplikatorbits des Bitpaares gleich sind und von dem Bit der benachbarten Bitposition abweichen; IV. Auswahl eines 1/2-Multiplikandenvielfaches in dem Fall, daß die Bits des Multiplikatorbitpaares verschieden sind; g) und daß die Zyklussteuereinrichtungen (120 bis 129) genau m/2 Multiplikatorzyklen hervorrufen, wobei je Zyklus das Ausgangssignal des Addierers (38) in dem Teilprodukt-Akkumulatorregister (36) gespeichert wird, und zwar um zwer Bitpositionen nach rechts verschoben, abgesehen von dem letzten Zyklus, bei welchem die Additionsoperation ausgeführt und die Verschiebung des Inhalts des Multiplikatorregisters (40) um zwei Bitpositionen nach rechts erfolgt. Anordnung zur Durchführung einer Multiplikation, insbesondere nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, a) daß der Addierer (38) eine binäre Summe der ihm zugeführten Operanden bildet, 209946/1137 b) daß das mit dem Addierer (38) verbundene Akkumulatorregister (36) das Ausgangssignal des Addierers (38) speichert und den ersten Eingangsoperanden für den Addierer (38) abgibt, c) daß ein Hauptregister (56) vorgesehen ist, das eine binäre Multiplikandenzahl speichert, d) daß ein Multiplikandenfaktor-Register (40) ein Vielfaches der Multiplikandenzahl speichert, e) daß eine Multiplikanden-Schalteinrichtung (46, 42) das Hauptregister (56) mit dem Multiplikandenfaktor-Register (40) derart verbindet, daß selektiv entweder die Multiplikandenzahl oder deren Einer-Komplement abgegeben und selektiv die halbe oder ganze Multiplikandenzahl oder gar keine Multiplikandenzahl abgegeben wird, f) daß ein Multiplikatorregister (14) eine m Bits umfassende Binärzahl speichert, g) daß eine Operanden-Schalteinrichtung (11,12,13) vorgesehen ist, die in das Multiplikatorregister (14) eine Zahl zu laden gestattet, die an der Bitstelle niedrigster Wertigkeit eine Null aufweist, h) daß eine Multiplikator-Verschiebeeinrichtung vorgesehen ist, die die Bitpositionen miteinander verbindet und die den Inhalt des Multiplikatorregisters (14) um zwei Bitpositionen nach rechts zu verschieben gestattet, i) daß eine Teilprodukt-Verschiebeeinrichtung vorgesehen ist, die den Addierer (38) und das Akkumulatorregister (36) derart verbindet, daß eine arithmetische Verschiebung des Ausgangssignals des Addierers (38) um zwei Bitpositionen nach rechts ermöglicht ist, 209846/1137 j) daß Zähleinrichtungen vorgesehen sind, die die Anzahl von Multiplikationszyklen steuern und die Einrichtungen zur Einleitung einer m/2-Zählung enthalten, k) daß eine Multiplikandenfaktor-Auswahleinrichtung vorgesehen ist, die auf die drei Bits niedrigster Wertigkeit in dem Multiplikatorregister (14) hin die tatsächliche Form der Multiplikandenzahl oder deren i'inerkompleiaent und einen Addierer-Eintrag gemäß den drei Bits höchster Wertigkeit und ein Vielfaches des Multiplikanden gemäß den beiden Bits niedrigster Wertigkeit auszuwählen gestattet, und zwar aufgerundet und unter Zugrundelegung eines Modules von acht, und

1) daß die ZyklusSteuereinrichtungen (120 bis 129) durch

en

die Zähleinrichtung/ gesteuert zyklisch die Operandenregister ansteuern, den Inhalt des Multiplikatorregisters verschieben und die Stellung der Zähleinrich-

en
tung-'solange verringern, bis eine Zählerstellung von Null erreicht ist.

209846/1137

Leerseite