DE1956209A1

DE1956209A1 - Schneller Multiplikator

Info

Publication number: DE1956209A1
Application number: DE19691956209
Authority: DE
Inventors: Stampler William A
Original assignee: Burroughs Corp
Current assignee: Unisys Corp
Priority date: 1968-11-07
Filing date: 1969-11-07
Publication date: 1970-06-18
Also published as: DE1956209B2; DE1956209C3; BE741276A; US3610906A; GB1280906A; BR6913949D0; FR2022785A1

Description

Beschreibung zu der Patentanmeldung der Firma

Burroughs Corporation, 6071 Second Avenue, Detroit, Mich. ^8232, USA

betreffend

Schneller Multiplikator

Die Erfindung betrifft einen schnellen Multiplikator, der ein anderes «Multiplikationsverfahren anwendet als bei den üblichen digitalen Datenverarbeitungssystamen« Bei dem System nach der Erfindung werden die beiden Operanden in der arithmetischen Einheit eines Rechners so behandelt, daß die Multiplizierschaltung lediglich zwei Quadrierfunktionen auszuführen hat sowie eine darauffolgende Subtraktion' · Letztere läßt sich mittels der arithmetischen Einheit des »Rechners durchführen,

Das Quadrieren kann das Multiplizieren von zwei verschiedenen Operanden auf unterschiedliche Weise ersetzen« Im allgemeinen werden die Operanden a und b addiert und quadriert. Zuletzt wird das zweite Produkt von dem ersten subtrahiert und durch vier geteilt, um das Ergebnis zu erhalten, Mit Digitalrechnern lassen sich bekanntlich Produkte von zwei Ziffern auf verschiedene Weise bilden«

009825/1781

Das übliche Verfahren besteht darin, durch eine wiederholte Addition zu multiplizierenc Andere Verfahren verwenden gespeicherte Logarithmentafeln oder speichern sogar sämtliche möglichen Produkte, wobei der Zugriff durch eine übliche Matrixschaltung erfolgt, bei der der Multiplikand und der Multiplikator als Eingangssignale dienen*

Die Multipliziervorrichtung nach der Erfindung zeichnet sich im wesentlichen aus durch eine einen ersten und einen zweiten zu multiplizierenden Operanden aufnehmende arithmetische Einheit, welche eine Einrichtung zum vorübergehenden Speichern und zum Bilden des Produktes der Multiplikation auf einen Befehl hin umfaßt, durch eine mit der arithmetischen Einheit verbundene Quadrierschaltung, die aus der arithmetischen Einheit ein Paar identischer Operanden zur Multiplikation und zur Erzeugung der zweiten Potenz der identischen Operanden empfängt.

Das Verfahren nach der Erfindung ist im wesentlichen darin zu sehen, daß der erste und der zweite zu multiplizierende Operand addiert werden, daß der kleinere von dem größeren Operanden .subtrahiert wird, daß sodann gleichzeitig die Summe und die Differenz der beiden Operanden quadriert wird und danach die quadrierte Differenz von der quadrierten Summe der Operanden ..subtrahiert und schließlich das Ergebnis dieser .Subtraktion durch vier geteilt wird.

Gemäß der Erfindung werden die beiden Operanden in der arithmetischen Einheit also so behandelt, daß die Multiplizierschaltung lediglich zwei Quadrierfunktionen und sodann eine Subtraktion 'ausführen muß, weichletztere ebenfalls in der arithmetischen Einheit erfolgt. Diese Multiplikation erfordert also eine Addition, zwei Subtraktionen und zwei Verschiebungen nach rechts (oder eine ähnliche Funktion), die sämtlich· ;mit einer üblichen arithmetischen Einheit eines Rechners durchgeführt werden können, sowie schließlich zwei Quadrieroperationen, welche mit einer neuartigen Quadrierschaltung durchgeführt werden kannc Diese Anforderungen nehmen mit zunehmender Wortlänge des Operanden nicht zu= Es ist ein Parallelbetrieb möglich, da eine

009825/1781

Subtraktion in der arithmetischen Einheit ausgeführt werden kann, während die Quadrierschaltung das Quadrat der Summe der Operanden bildet=

Die Erfindung ist im folgenden anhand schematischer Zeichnungen an mehreren Ausführungsbeispielen ergänzend beschrieben„

Fig« 1 zeigt eine Anzahl Verfahren zum Multiplizieren;

Fig₀ 2 zeigt ein bekanntes System zum Multiplizieren von zwei·3-Bit-Operanden;

Fig_a 3 zeigt das System nach der Erfindung sun» Hultipli-

zieren von zwei 3-Bit-Operanden mittels Quadrieren;

Fig, ** zeigt die Weiterbildung des Systems für eine 10-ßit-Quadrierschaltung|

Fig.. 5 ist ein vereinfachtes Schaltbild einer» Quadrierschaltung;

Fig«. 6a bis Bu zeigen dia ^rfordö^ÜGhsn Seltaltuiigskreise

für jedes Bit beim Quadrieren eines iO-Bit-Operanden; Die Gatter für die Ableitung des¹ PsPi:ialprodukte und der einstufige Addierer sind in diesen Figuren zusammen dargestellt;

Fig, 7a zeigt die übliche Obertragweiterleitung bei einem 10-Eit-Einstufenaddierer;

Fig. ?b zeigt die Abkürzung der längsten Öbertragkette in demselben 10-Bit-Einstufenaddierer«,

Fig, 8 zeigt ein vereinfachtes Schaltbild einer Multipliziervorrichtung nach der Erfindung;

Fig. 9 zeigt den der Vorrichtung nach Figo 8 entsprechenden Algorithmus;

Fig IO zeigt einen abgeänderten Algorithmus;

Fig_r 11 zeigt die Schiebeoperation am Eingang der Quadrierschaltung;

Fig. 12 ist ein algorithmisches Diagramm, welches den minimalen Scheitungsaufwand erkennen läßt;

009825/1781

Fig. 13 und l¹» sind Blockschaltbilder von Multipliziervorrichtungen nach der Erfindung,

Figo 1 zeigt drei verschiedene Verfahren zum Multiplizieren unter Verwendung von logischen Schaltungen, nämlich das direkte Verfahren unter Verwendung einer Einstufenmultiplizierschaltung, das direkte Quadrierverfahren mit einer einstufigen Quadrierschaltung, und ein Multipliziersystem unter Verwendung einer Quadrierschaltung. Bei letzterem werden die Operanden an eine arithmetische Einheit gegeben zum Addieren und Subtrahieren» bevor sie an die einstufige Quadrierschaltung und den Speicher weitergegeben werden»

Fig. 1 zeigt ein theoretisches Multiplizierverfahren, bei dem das Produkt direkt aus den Operanden (Multiplikand und Multiplikator) gebildet wirdc Wegen der Komplexität der erforderlichen logischen Schaltung hat dieses Verfahren kaum Bedeutung erlangt» Beim Multi-

20 plazieren von zwei 20-Bit-Wörtern sind aufgrund der 2 möglichen Kombinationen jedes Operanden 1 048 576 Bit-Anordnungen in den einzelnen Operanden möglich. Die Gesamtzahl der Kombinationen, die multipliziert werden müßten, wäre dann 2 entsprechend etwa 10

Fig. Ib zeigt ein Quadrierverfahren mit einem verringerten Schaltungsaufwand, da die beiden Operanden identisch sind= Das Quadrieren eines 20-Bit-Wortes erfordert dann lediglich 1 0U8 576 Eingangsmöglichkeiten, und die Verringerung der Komplexität der logischen Schaltung ist beachtliche Gemäß Fig. Ic werden die beiden Operanden in der arithmetischen Einheit so behalten, daß die logische Schaltung zwei Quadrieroperationen ausführen muß und anschließend eine Subtraktion erfolgt, wobei die Vorteile der logischen Einfachheit des Quadrierens in allen Fällen erhalten bleibt, auch wenn die Operanden nicht gleich sindο

Um die Größenordnung der Vereinfachung zu verstehen, die sich mit dem Verfahren nach der Erfindung erreichen läßt, sei die Multiplikation von zwei 3-Bit-Wörtern anhand des linken Teiles von Fig. 2 gezeigt» Die erforderliche logische Schaltung zur direkten

009825/1781

BAD ORIGINAL

Multiplikation ist auf der rechten Seite von Fig. 2 dargestellt» Fig, 3 zeigt die Multiplikation eines 3-Bit-Wortes (a, b und c5 mit sich selbst (Quadrieren) und die dazu erforderliche logische Schaltung . Man erkennt, daß das nicht vereinfachte Produkt ist:

(a²)2^l* + 2ab(2³) + (2ac + b²)2² + (2bc)2¹ + (c²)2° .

Dieser Ausdruck läßt sich gemäß den folgenden Überlegungen vereinfachen:

Quadrieren einer Binärzahlο Jedes Bit xⁿ ist gemäß den binärarith-....._„,. — .... metischen Gesetzen gleich x, wenn η

eine positive Zahl ungleich Null ist* Zum Beispiel: O¹ = 0; O² - Oj O³ a Oj etc.
I¹ - Ij I² = 1; I³ ' Ij etc.

2 2 2

Daher ist bei dem Beispiel nach Fig„ 3a = a» b, = b und c = Co

Das Multiplizieren mit zwei wird gewöhnlich ausgeführt durch Stellen-... —... ... ygpgjjj^gkyjjg _nacjj links um 1 Bit» Daher

(2ab)2³ = (ab)2⁴j C2ac)2² = (ac)2³j (2bc)2¹ a (bc)2² ₀

Vereinfachtes Produkt, Gemäß Fig. 3 führen die beiden obigen Oberlegungen""zu""dem"foigenden vereinfachten Produkt:

(a + ab)2^l* + (ac)2³ ♦ <b + bc)2² + (0)2¹ + (c>2°

Wenn gemäß dem obigen Beispiel irgendeine ganze Binärzahl quadriert wird, ist das Bit 2 immer gleich Null, und es ist nur eine einfache logische Schaltung erforderlich, um diesen Teil des Produktes zu bilden, Da c = c ist in dem Beispiel nach Fig₄ 3, ist das niederrangigste Bit (2°) des Produktes immer gleich demselben Bit des Operanden. fl)as Quadrieren einer ungeraden Zahl erzeugt eine gerade Zahl. Das Quadrieren einer geraden Zahl erzeugt ebenfalls eine gerade

00982E/1781 _eAOOfiI«NAU

Zahl. £3 ist da ebenfalls nur ein geringfügiger Schaltaufwand erforderlich, UJl
übertragen,

derlich, um das Bit 2 des Operanden in das Bit 2 des Produktes zu

Unter Berücksichtigung der obigen Vereinfachungen läßt sich zum Quadrieren eines 3-Bit-Wortes die im rechten Teil von Fig„ 3 dargestellte Schaltung verwenden, Hierbei wird das Register zum Speichern des Produktes gelöscht (auf Null gestellt), bevor das Produkt hineingegeben wird» Fig„ 3 zeigt, daß die Quadrier logik lediglich acht einfache Gatter erfordert, während die Multiplizierlogik nach Figo 2 neun einfache Gatter sowie drei Volladdierer und drei Halbaddierer erfordert» Die dargestellte Quadrierlogik ist nicht nur wesentlich einfacher als die Multiplizierlogik, sondern auch schneller. Bei dem Ausführungsbeispiel ist keine Öbertragweiterleitung erforderlich <>

Die folgende Tabelle zeigt, wie ein Produkt von zwei unterschiedlichen Operanden sich durch die Differenz zweier Quadrate erzielen läßt.

Tabelle A

Operanden uT>Iich"e1f"* gleichwerti-

Ca) χ (b) Produkt ges Produkt

20 χ 20 = i»00 = ItOO - 0

21 χ 19 = 399 = WO - 1

22 χ 18 = 396 s 400 - 4

23 χ 17 = 391 = 400 - 9

24 χ 16 = 384 = 400 - 16

25 χ 15 = 375 = 400 - 25

26 χ 14 = 364 = 400 - 36

27 χ 13 = 351 = 400 - 49

28 χ 12 = 336 = 400 - 64

29 χ 11 a 319 s 400 - 81

30 χ 10 = 300 = 400 - 100

31 χ 9 s 279 = 400 - 121

32 χ 8 = 256 = 400 - 1U4

33 χ 7 s 231 = 400· - 169

34 κ 6 a 204 a 400 - 196

009825/1781

Tabelle A (Fortsetzung)

35	X	5
35	X	4
37	X	3
38	X	2
39	X	1
40	X	0
41	X	(-1)
42	X	(-2)

175

mn

111

-41 -84

400 - 225 400 - 256 400 - 289 400 - 324 400 - 361 400 - 400 400 - 441 400 - 484

Die linke Spalte zeigt die Operanden, deren arithmetisches Mittel 20 ist (z.B. 15._+-2§, = 20)= Die nächste Spalte zeigt das übliche Produkt jedes Operanden* DjLe letzte Spalte zeigt ein gleichwertiges Produkt (z.Bc 364 = 400 - 36)„ Die Zahl 400 ist das Quadrat des Durchschnittswertes der Operanden, und die von 400 subtrahierten Ziffern sind gleich dem Quadrat^der halben Differenz der Operanden, in dem Beispiel: 36 = (-—-*■—«-—) Ό Die Tabelle zeigt» daß das Verfahren der Differenzbildung aus zwei Quadratwerten das übliche Multiplikationsverfahren ersetzen kann=

Tabelle A gilt für den Fall, daß beide Operanden entweder ungeradzahlig oder geradzahlig sind, Wenn einer der Operanden ungeradzahlig und der andere geradzahlig ist, erfolgt der Rechenablauf gemäß Tabelle B₀

Tabelle B

Operanden
(a) χ (b)

9,5 χ 9,5

9 χ 10
8 χ 11

übliches Produkt

90,25

gleichwertiges Produkt

90,25 - 0 90,25 - 0,25 90,25 - 2,25

009825/1781

BAD OBtOtNAL

R ■"

Tabelle B (Fortsetzung)

7	X	12
6	X	13
5	X	IU
4	X	15
3	X	16
2	X	17
1	X	18
0	X	19
1	X	20
2	X	21
3	X	22

8«+ 78 70 60 48 3t* 18 0

-20 -i»2 -66

90,25 -	6,25
90,25 -	12,25
90,25 -	20,25
90,25 -	30,25
90,25 -	42,25
90,25 -	56,25
90,25 -	72,25
90,25 -	90,25
90,25 -	110,25
90,25 -	132_r25
90,25 -	156,25

Für das Beispiel 7 χ 12 a 84 ergibt sich nach dem beschriebenen Verfahren ein Mittelwert aus 7 und 12 von 9,5 und eine zweite Potenz dieses Mittelwertes von 90,25. Sodann werden die Operanden subtrahiert (12 - 7 = 5). durch zwei dividiert (·| = 2,5) und quadriert (2,5² = 6,25), Schließlich wird dieser Wert 6,25'von 90,25 subtrahiert, so daß man als Ergebnis 84 erhält.

Die folgende Darstellung zeigt die Anwendung des neuen Verfahrens mit Bxnäroperanden an dem Beispiel 6x4« Die äquivalenten Dezimalwerte der Binärziffern sind der Klarheit halber dargestellt. Das Dividieren durch zwei geschieht durch Verschiebung nach rechts„

009825/1781 «AD original

Binärrechnung

Aufgabe: 110 χ 100 - ?
Operanden :

110 100

Summe der Operanden 1010

dividieren durch 2
(Rechtsverschiebung) 101

Quadrieren

Operanden:

011001

110 100

Differenz der Ope- 010 randen

Dividieren durch 2
(Rechtsverschiebung) 001

Quadrieren

-000001

Differenz der beiden Quadratwerte

Produkt

Dezimalrechnung

Aufgabe : 6 χ U =

6 lü

011001-^L 000001

011000

Die Rechtsverschiebung läßt sich ausführen, während die Summe oder Differenz der Operanden in das Eingangsregister der Quadrxerlogik gegeben wird. Es entsteht kein Zeitverlust durch den Verschiebevorgang.

Die oben beschriebene Quadrierlogik erzeugt das Quadrat einer Zahl in einem Schritt mit hoher Geschwindigkeitο Es sind keine Taktimpulse oder dgl, erforderlich» Die Komplexität der Quadrxerlogik hängt von der Länge der Operanden ab,.

009825/1781

Fig, if zeigt ein Verfahren zum Entwickeln der logischen Schaltung für einen 10-Bit-Qperanden. Hierbei wird in gleicher Weise vorgegangen wie vorstehend anhand des 3-Bit-Wortes beschrieben ist» Die logischen Schaltungen für Operanden mit mehr als 10-Bit lassen sich in ähnlicher Weise entwickeln.

In Fig* H ist j das niederrangigste Bit (2°) des Operanden und a das

höchstrangige Bit desselben (2 ). Die Partialprodukte werden durch Multiplizieren jedes Bit des Operanden mit sich selbst und mit jedem anderen Bit gewonnen«. Wie oben beschrieben, erfordert die Quadratbil-

2 2

dung a =a;b=b, usw. keinen Logikaufwand. Da jedes Paar ungleicher Bits zu einer Addition von zwei ähnlichen Teilprodukten führt (z.B. i χ j s ij; j- χ i = ijj ij + ij = 2ij), wird der Koeffizient 2 durch Rechtsverschiebung eliminiert, wie in Fig. *f durch die schräg verlaufenden Pfeile dargestellt ist. Diese Vereinfachung der Verschiebung "auf dem Papier" macht eine Verschiebung in der Quadrierlogik unnötig,

In den Zeichnungen ist das Produkt zweier verschiedener Bits, Z₁B, i und j j als ij dargestellt. Die Tabelle, die die Multiplikation von i und j zeigt.* zeigt den Binärwert 0 am Ausgang mit Ausnahme, wenn i und j beide gleich 1 sind. In diesem Fall ist das Produkt gleich dem Binärwert 1*

Die logische Schaltung zum Multiplizieren von i und j ist ein einfaches UND-Gatter mit zwei Eingängen.

Da die Partialprodukte sich mittels einfacher UND-Gatter erzeugen lassen, braucht man lediglich eine zusätzliche Addierschaltung vorzusehen und diese Partialprodukte zu addieren, um die gewünschte Antwort} d.h. das Quadrat des Operanden, zu erhalten.

Gemäß der Erfindung werden die Partialprodukte in einer logischen Operation kombiniert, die sich als einstufige Addition ansehen läßt.

009825/1781

- ii -

Es sei angenommenj daß getrennte Register vorgesehen sind für den zu quadrierenden Operanden {Eingangsregister) und für das Ergebnis des Quadrierens (Ausgangsregister), wie in Figo 5 dargestellt ist. Die Funktionen der beiden Register lassen sich mit Registern ausführen, welche zu anderer Zeit für andere Zwecke verwendet werden»

Der unten beschriebene Einschritt-Addierer kombiniert die Partialprodukte des 10-Bit-Operanden Coder geringfügiger Variationen desselben) und erzeugt die genaue 20-Bit-Antwort direkt_c Die gesamte Quadrierlogik arbeitet asynchron_s da weder Taktimpulse noch Zähler erforderlich sind. Lediglich das Eingeben eines Operanden in das Eingangsregister ' läßt eine Antwort in dem Ausgangsregister erscheinen.

Der Einstufen-Addierer zum Addieren der Partialprodukte kann so aufgebaut sein, daß jedes Bit des Ergebnisses direkt ohne Obertrag gebildet wird. Jedes Bit des Ergebnisses läßt sich auch durch Verwendung üblicher Halbaddierer₃ Volladdierer und zugeordneter Übertragsschaltkreise erzeugen.. Um eine möglichst schnelle Rechnung zu erzielen ohne übermäßigen Schaltungsaufwand, wird die Kombination beider Verfahren gemäß der Erfindung gewählt. Der einstufige Addierer erzeugt Vielfachüberträge praktisch gleichzeitig. Die zum Weiterleiten der Oberträge zwecks Erzeugen des 20-Bit-Ergebnisses erforderliche Zeit ist niedriger als die zum Weiterleiten eines einzigen Übertrages j bitweise von der niederrangigsten zur höchstrangigsten Stelle in einem üblichen 20-Bxt-Addierer erforderliche Zeit*

Ferner ist neben den üblichen Gattern noch ein Antivalenz-ODER-Gatter nötig. Dieses im folgenden auch XOR-Gatter genannte Schaltungselement erzeugt ein Ausgangssignal (den logischen Wert 1) nur dann, wenn beide Eingangsinformationen voneinander verschieden sind. Wenn die Eingänge A und 1? (nicht B) sind, ist der Ausgang gleich 1, ebenso wenn die Eingänge den Wert A" (nicht A) und B führen. Die Bezeichnungen HA und FA bedeuten Halbaddierer bzw_c Volladdierer,

&AD

009825/1781

Genaue Beschreibung der einstufigen Quadrierlogik für einen 10-Bit-Operanden _a

Die Logik zum Quadrieren eines 10-Bit-Operanden ist in den Figuren 6 dargestellt. Diese Figuren zeigen sowohl die Gatterschaltungen zum Erzeugen der Partialprodukte als auch den einstufigen Addierer« Sie sind in Fig. 5 in getrennten Blocks dargestellt, um die Operation der Quadrierlogik besser erläutern zu können»

Die Logik für jedes Bit des zweifach genauen 20-Bit-Produktes ist unten beschrieben_o Die drei niederrangigsten Bits des Produktes

0 12

(2,2,2) sind wegen ihrer Einfachheit zu einer Gruppe zusammengeschlossen.

Die logische Schaltung braucht lediglich das 2 -Bit des Ausgangsregisters auf 1 zu stellen _t wenn dasselbe Bit des Operanden in dem Eingangsregieter gleich 1 j st. Das Bit 2 in aem 20~Uit-«,i23gangsps» gister ist inaaer gleich Null,, In der logischen Schaltung ffir das 2 <Bit sind dia Satter gemäß den Erfordernissen der Figur Ή eingestell wonach das Addieren der Partialprodukte ij und i die Summe für daa

ο
Bit 2 des Ausgangsregisters erzeugt. Die logische Schaltung stelle; das 2 -Bit in dem Ausgangsregister lediglich auf 1 ein, wenn das Bit i des Operanden gleich 1 ist und das Bit j des Operanden gleich Null istc

Ein Antivalenz-ODER-Gatter und ein UND-Gatter mit drei Eingängen erzeugen die Summe für das Bit 2 des Ausgangsregisters ο Εε sind keine Oberträge von vorhergehenden Stufen zu verarbeiten. Obwohl die Quadrierschaltung ein Ausgangssignal ohne Taktimpulse erzeugt, könnte es erforderlich sein, ein übliches Freigabesignal einzuführen (in den Figuren 6a, 6b und 6c dargestellt), um den Ausgang der logischen Schaltung an das Ausgangsregister durchzuschalten, so daß

009825/1781

Sehaltvorgänge (transient) keinen Flip-Flop umkippen, der im NuIl-Zustand bleiben sollte. Dieses Freigabesignal kann angelegt werden, nachdem sämtliche Oberträge weitergeleitet und alle Schaltvorgänge genügend abgeklungen sind. Ein Vorteil des Freigabesignals und der zugeordneten Gatter besteht darin, daß die Quadrierlogik irgendein verfügbares Register in dem Rechner als Ausgangsregister verwenden kann,. Das Eingangsregister in Fig. 5 läßt sich z.B₀ für das Ergebnis des Quadrierens verwenden} wenn die Null- und Einerausgänge an die Quadrierschaltung gelegt werden« Die Schaltung kann gemäß Fig. 6c oder auch andersartig geändert werden, um die Null- und Einerausgangswerte zu ergeben, so daß das Register für die Aufnahme des Ausgangswertes I der Quadrierschaltung nicht auf Null gestellt werden muß*

Zur Vereinfachung der Erläuterungen sei angenommen, daß das Ausgangssignal der Quadrierschaltung in ein vorher gelöschtes Register durch Freigabe von Gattern gegeben wird, welche in den Zeichnungen fortgelassen sind. Zur weiteren Vereinfachung sind die Flip-Flops des Eingangsregisters in den übrigen Zeichnungen fortgelassen, und lediglich die in bestimmten Flip-Flops gespeicherten Signale sind dargestellte Fig, H zeigt z.B_e, daß das Signal g des Operanden in dem Flip-Flop 2 des Eingangsregisters gespeichert ist« Es sind nur das Signal g und/oder dessen Negation g dargestellt.

Die logische Schaltung nach Figur Bd erzeugt den Ausgabewert das Bit 2 des Ausgangsregisters ohne Oberträge von vorhergehenden Stufen«. Die normalerweise von Volladdierern oder Halbaddierern für die nächste Stufe erzeugten Überträge sind ersetzt durch die Schaltung nach Fig. 6e, welche den "Übertrag"-Eingang für die Schaltungs-

5
stufe 2 erzeugt ■,

Die logische Schaltung wird umso komplizierter, je größer das Eingangsregister wird. Bei Verwendung üblicher Addierer und zugeordneter Obertragsstufen in der Quadrierschaltung ist die einzige

00982S/1781

merkliche Belastung des Eingangsregisters von den UND-Gattern gebildet» welche normalerweise die Partialprodukte kombinieren zur Verwendung in dem einstufigen Addierer» In der optimalen Bemessung werden bei diesem System mehr übliche Schaltungskreise mit Übertragweiterleitung in den meisten aufeinanderfolgenden Stufen verwendet, um eine zu große Kompliziertheit und übermäßige Belastung des Eingangsregisters zu vermeiden.

Es werden zwei Volladdierer verwendet zum Erzeugen des 2 -Bit-Ausgabewertes ο Obwohl zwei Überträge (C5a und C5b) durch diese Addierer erzeugt werden, brauchen sie nicht verwendet zu werden. Um die Übertragkette zu kürzen und die Rechengeschwindigkeit der Quadrierlogik auf diese Weise zu erhöhen, werden die Überträge für die 2 -Bit-

Schaltung gemäß Fig. 6g direkt erzeugt,

§i£-liL(Figur..6h)

In dieser Stufe sind zwei Volladdierer vorgesehen zum Erzeugen der Summe für das Bit 2 des Ausgaberegisters und zum Erzeugen der Über-

träge C6a und C6b zur Verwendung der 2 -Bit-Stufe.

Die Schaltung dieser Stufen ist in herkömmlicher Weise aufgebaut. Vielfachüberträge werden je nach Bedarf erzeugt und/oder weitergeleitet O

Diese Stufe verwendet lediglich ein UND-Gatter mit zwei Eingängen und ein Antivalenz-ODER-Gatter zum Erzeugen der Summe für das Bit

18 19

2 des Ausgaberegistereo Es wird kein Übertrag für die Stufe 2 erzeugte

BAD 009825/1781

17 Diese Stufe erhält den Übertrag direkt von der Stufe 2 (C17K Durch diese Technik wird die Obertragweitergabe (unter Umgehung der

18

Stufe 2 ) ohne merkliche Erhöhung des Schaltungsaufwandes beschleunigt C

Bei Verwendung üblicher Volladdierer und Übertragerzeugung für die Stufen 2² bis 2 würden die Überträge gemäß den horizontalen Li- , nien in Fig. 7a weitergegeben werden. Es sei bemerkt, daß bis zu . ™

9 13-

vier Überträge gleichzeitig von der Stufe 2 bis zur Stufe 2 auftreten können-. Aufgrund der beschriebenen Schaltungstechnik für die Bits 2², 2³, 2**, 2¹⁸ und 2¹⁹ wij?d die Weitergabakette für die Überträge gemäß Fig* 7 durch die logische Schaltung für den einstufigen Addierer verkürzt, Der längsts ^bertrag beginnt Ligi der Stufe 2 und endet bei der Stufe 2 ₉ scböi -!ia Stuf<3 2" i^ßgangen wird= Die Über tragweit er leitung wird daher- -saf Kostsn einsr» gsringfügig komplexeren Schaltung erhöht»

Vorhergehend ist die Einbeziehung einer logischen Schaltung für den Einstufen~Addierer vorgeschlagen- Zur weiteren Verkürzung der Rechenzeiten kann die Übertragweitergabe durch einen komplexeren i Schaltungsaufwand weiter beschleunigt werden-

Die Vie'itergabe vei^schiedener Überträge zur gleichen Seit verlangsamt die Übertragweitergabe nicht in großem Maße,, Im wesentlichen bestimmt der Weitergabeweg für den längsten Übertrag diese Zeit* Es lassen sich Techniken zum Gruppieren der Überträge von zwei oder mehr Stufen und zum Weiterleiten des sich daraus ergebenden Übertrages verwenden.

009825/1781

Vereinfachungen für einfach genaue Multiplikation

^■B W ^Bi ^BB ^Bl βΒ: W 4Bp OT W fll ft^VB ^^J βΒΙ BJEP CW VIV ^W BÄ t^H Bf W ^He- MM fl^p M^ ββ ί·· ^Bt Vpt ^PP ^BB ^HP Ml 4pBl VBv Vw VHt <B3p Ρ·Ρ ^PW W PP» VMl ■■! W ^HP ■■·

Die bisherige Beschreibung betrifft 10-Bit-Operanden und ein 20-Bit-Produkt, wie es als Ergebnis beim Rechnen mit ganzen Zahlen auftritt ο Ein derartiges 20-Bit-Produkt wird gewöhnlich als zweifach genaues Wort bezeichnet, da es die doppelte Anzahl von Bits aufweist wie das grundlegende Operandenwort. Für die meisten Anwendungen ist jedoch eine einfach genaue Multiplikation ausreichend. Unter diesen Umständen läßt sich die Quadrierschaltung vereinfachen,

Bei einfach genauen Operationen kann die weniger bedeutende Hälfte des Produktes vernachlässigt werdenο Oberträge der logischen Schaltung für die weniger bedeutende Hälfte des Produktes werden der niederrangigsten Bit-Stelle der höherrangigen Hälfte des Produktes zugegeben ο Dies ist anhand von Fig.. Si bei dem Bit 2 mit den Oberträgen C9a_s C9b, C9c und C9d gezeigte Im allgemeinen kann die in den Figuren 5a bis 6f dargestellte Schaltung für einfach genaue Ergebnisse fortgelassen wer., in«, Die Schaltung nach Fig«, 8g wird beibehaltern Die Schaltung für die Bits 2⁶ bis 2⁹ (FIg. Sh bis 6k) wird unter¹ geringfügigen Vereinfachungen beibehalten, da die Susi--* menausgabeweirte der niederrang ig en Hälfte des 20-Bit-Ausgabewert35 nicht benötigt werden.- Es lassen sich Techniken anwenden zum Gi::s:C" ten Erzeugen von Überträgen ohne Durchlaufen der Addierschaltung vorhergehender Stufen (Fig_c 6g), um die Übertrageingangswerte C9a₉

1 η
C9b, C9c und C9d für die Stufe 2 zu erzeugen«

Wenn diese Überträge direkt erzeugt werden, können die Schaltungen nach den Figuren 6a bis 6k fortgelassen werden. Die Multiplikationsgeschwindigkeit wird dann erhöht, da die Obertragkette beträchtlich gekürzt isto

Algol zum Multiplizieren durch Differenzbildung von zwei Quadratwerten

Im folgenden ist die logische Schaltung des Quadrierens in Verbindung mit einer arithmetischen Schaltung deß Rechners beschrieben»

00 9 825/1781
n BAD ORIGINAL

Fig. 8 zeigt ein vereinfachtes Diagramm eines schnellen Multiplikators. Die arithmetische Einheit des Rechners arbeitet unabhängig von der Quadrierstufe. Wenn die arithmetische Einheit ein Wort an das Eingangsregister der Quadrierstufe gibt, kann die Einheit wieder ihre normale Funktion des Addierens, Subtrahierens, Vergleichens usw. ausführenο Diese Fähigkeit zur unabhängigen Operation ist wesentlich für die hohe Geschwindigkeit bei der Multiplikation nach der Erfindung»

Im folgenden sind drei Rechenschemen (Algols) angegeben, Die ersten beiden ,Rechenscheinen ergeben eine hohe'Rechengeschwindigkeit, er- " fordern jedoch den doppelten Aufwand an Schaltungsteilen im Vergleich zu dem dritten Rechenschema ₃

Das Schema nach Fig. 9 entspricht dem vereinfachten Diagramm von Fig. 8 mit der Ausnahme, daß zwei arithmetische Einheiten und zwei Quadrierstufen für Parallelbetrieb erforderlich sind_c

f S§2§ädiesem Rechenschema ist angenommen, daß die beiden zu multiplizierenden Operanden beide in übliche arithmetische Einheiten eingegeben sind= Bei Gleitkommabetrieb werden die Operanden normalisiert, um Null-Bits am Anfang der Operanden zu beseitigen. Da bei Gleitkommaoperanden der Exponentialanteil addiert wird (um den Exponentialanteil des Ergebnisses zu erzeugen), wird dieser Teil der Multiplikation nicht weiter beschrieben, da es sich hierbei um einen getrennten und üblichen Rechenschritt handelt, der viel eher ausgeführt ist, bevor die Mantissenanteile der Operanden verarbeitet sind. Die folgende Beschreibung bezieht sich auf die Mantissenanteile für Gleitkommaoperanden (d„h. auf den gesamten Teil der ganzzahligen Operanden).

Die Quadrierschaltung verwendet die Absolutwerte (jxj; |y|) der Eingangsoperanden χ und Vj also ohne Berücksichtigung der Vorzeichen., Das Addieren von χ und y bildet immer die erste Rechenoperation, da beide Operanden als positiv angenommen werden und keine ergänzenden Operationen innerhalb eines üblichen Addierers erforderlich

00982S/1781

^BAD ORIGINAL

Zur Berücksichtigung des Umstandes, daß der eine Eingangsoperand geradzahlig und der andere ungeradzahlig ist, erfordert die Quadrierschaltung in diesem Fall ein extra Bit. Für ΙΟ-Bit-Operanden müssen also Quadrierschaltung für 11 Bit vorhanden sein. Verfahren, welche unter diesen Umständen kein extra Bit erfordern, sind in den folgenden Algolangaben enthalten.

In einer arithmetischen Einheit werden die Operanden χ und y addiert und die halbe Summe (in Fig. 9 mit A bezeichnet) in die Quadrierschaltung gegeben. Dazu wird die Summe nach rechts um eine Stelle verschoben, was einer Division durch zwei entspricht.

Der Ausgabewert --£-2— der Quadriere ehalt ung ist mit A bezeichnet. Dieser Wert wird in den Minuendenteil des Addierers gegeben. Währenddessen sind die Operanden χ und y verglichen worden, so daß der kleinere Operand von dem größeren subtrahiert werden kann. Falls der Vergleich zeigt, daß die Subtraktion einen negativen Wert ergibt, werden die Operanden Innerhalb der arithmetischen Einheit gewechselt.

Wenn nun χ und y in den richtigen Registern der arithmetischen Einheit eingespeist sind, wird y von χ subtrahiert und der halbe Wert dieser Differenz (als B bezeichnet) an das Eingangsregister der Quadrierschaitung gegeben. Der Ausgabewert der Quadrierschaltung beträgt(~^-^ und ist mit B bezeichnet. Dieser Wert wird als Subtrahendenteil in denselben Addierer gegeben, der den Wert A enthält.

2 2
Wenn die beiden Werte A und B in eines der beiden arithmetischen Einheiten eingespeist sind, wird die Subtraktion ausgeführt, die das gewünschte Ergebnis bringt.

00982S/1781

Dieses in Pig. 10 dargestellte Rechenschema erfordert eine weitere Addition, jedoch kein Extra-Bit für die Multiplikation einer geradzahligen mit einer ungeradzahligen Ziffer. Das Multiplizieren von ΙΟ-Bit-Operanden erfordert eine 10-Bit-Quadrierelnheit.

Bei diesem Rechenschema werden die Operanden χ und y gemäß Pig. Il addiert. Bei der Stellenverschiebung nach rechts wird das niederrangigste Bit der Summe in das Speicherbit M verschoben, Dieses Speicherbit erhält den Wert Null, falls χ und y beide gerade sind. Wenn einer der Operanden ungerade und der andere gerade ist, erhält das Bit M den Wert 1, Dieser Fall erfordert eine besondere Behandlung, da der Durchschnittswert aus einer geraden und einer ungeraden Zahl einen Bruch ergibt. (s.S. 1st das Mittel aus 9 und 10 gleich 9,5). Bei dein betrachtete;! fie-öhenschesia wird der Anteil hinter dem Komma (0,5) vernachlässigt und spSter ksspsnsisF-j_o

Bei der ersten Subtraktion wird y vun i: sabirafei^^ ₃ wie oben beschrieben ist. Der Operand y muß iramsr äsr kleinere *won beiden sein. Diese Unterscheidung muß unbedingt gemacht werden, da der kleinere Operand y zeitweilig in einem Register- gespeichert wird, wenn das Bit M gleich 1 ist. ,

2 2
Nach der zweiten Subtraktion (A -B) wird das Bit M untersucht. Falls es Null ist, liegt das gewünschte Ergebnis vor. Es sei angenommen, daß die zweite Subtraktion in derselben arithmetischen Einheit durchgeführt wird, welche den vorher berechneten Exponententeil des Produktes speicherte. Die Beendigung der Subtraktion bewirkt, daß das gesamte Produkt in einem Register gespeichert ist. Wenn das Bit M gleich 1 ist, wird der in einem Register gespeicherte Operand y zu dem Ergebnis der Subtraktion addiert (y wird zu

2 2
B -A addiert), so daß das gewünschte Ergebnis erzielt wird. Das Addieren von y zu der Differenz aus A und B² bildet die Kompensation für die Vernachlässigung des Bruchteiles bei der Rechtsverschiebung der Summe aus χ und y.

0 0 9 8 2 5/1781 ^⁰ «WON«.

Schaltungsaufwand.

Ein Schaltungsaufbau mit lediglich einer arithmetischen Einheit und einer Quadrierschaltung ist bei Anwendung von Mikrosehaltungen praktisch, obgleich die Bauteilzahl unter den gegenwärtigen Umständen hoch 1st. Z.B. findet man die Zahl η von UND-Gattern mit zwei Eingängen die zum Erzeugen der Partlalprodukte erforderlich ist, gemäß der Formel:

η =

worin b die Anzahl der Bits in dem Operanden ist. Eine Qua^rierschaltung für ein 10-Bit-Wort erfordert also etwa 45 UND-Gatter mit zwei Eingängen. Diese Anzahl ändert sich bei Einführung logischer Sparmaßnahmen, wie sie etwa in Flg. 6 dargestellt sind. Eine Quadrierschaltung für 35 Bit erfordert etwa 595 UND-Gatter mit zwei Eingängen (für ein zweifach genaues 70-Bit-Ergebnis).

Im folgenden sind Verfahre * zum Verringern des Schaltungsaufwandes angegeben.

Dieses Verfahren der Multiplikation unterteilt die Quadriereinhsit. gemäß Fig.. 12. Anfänglich sind die Operanden jxj und jyj te üer öölietos arithmetischen Einheit.

Stufe_l. Hierbei werden χ und y addiert und In die Quafeäereiniisit verschoben» Das niederrangigste Bit der Summe wird in äem Bifc-Sp-Jicher M gespeichert. Zur gleichen Zeit vergleicht sir, !komparator oder dgl. χ und y miteinander, um den niedrigsten yper^aR*ä^öa heraus«* zufinden.

Stufe_2, Die Quadrierschaltung quadriert.Λ uj:i ;>,,:■:«;ugft ä^&^ Σζ^ζ:^-- schen sind π und y falls erforderlich in d-.::·¹ :^i';;v:£t±ssik::i 3iiu;:.i°i vertauscht ^orien, damit der kleinere Opera;;u zn äv^^j u^&lL^ _t, Ζΰ,^ύ, Sodann wird y von κ subtrahiert und y ferrit:;= .'-u; -/-,. ivlg &■■;..... yrl=> chert _s wenn das Bit M gleich 1 ist.

Stufe_3. Cas Produkt A² wird in die ariifcice-'.. ,..; , -:;:^sii; ij^ü-..:,, während die Hälfte der Differenz von y. \ma y (Zl „;\ άίύ ^:^..:Λ<^- schaltung gegeben wird.

00982B/1781

-■ jm&MS* BAD ORIGINAL

Stufe Ί. Die Quadrierschaltung quadriert den Eingangswert B und

erzeugt den Wert B . Inzwischen wird y von der betreffenden Speicher

2 stelle in die arithmetische Einheit gegeben und zu A addiert, falls das Bit M gleich 1 ist.

ρ Stufe 5. Sobald die Quadrierschaltung den Wert B gebildet hat, wird das Ergebnis in die arithmetische Einheit gegeben und von A subtrahiert (oder von A + y, falls das Bit M gleich 1 ist). Die Differenz ist das gewünschte Ergebnis,

Aus Fig. 12 ist zu entnehmen, daß die Multiplikationszeit die Summe der folgenden Zeiten ist:

Stufe 1 - eine Addition (x + y)

Stufe 2 - eine Quadratbildung (A-*A²) Stufe 3 - ein Übertragungsvorgang Stufe Ί - eine Quadrat bildung (B-; Stufe 5 - eine Subtraktion

Wenn der Rechnung die Subtraktion durch Komplementbildung des Subtrahenden und durch Addition ausführt, kann die für die letzte Sub-

2 2
traktion (A -B) erforderliche Zeit verkürzt werden, indem die Komplementbildung fortgelassen und statt dessen die Null-Werte des

Produktes B an die Einereingänge der arithmetischen Einheit gegeben werden. Hierdurch wird eine Komplementbildung während der über-

2
tragung von B erreicht.

2 Am Ende des Multipliziervorganges muß y zu A in ganzen Operationen addiert werden. Beim Gleitkommabetrieb, bei dem die niederrangigste Hälfte des zweifach genauen Produktes gewöhnlich fallen gelassen wird, dürfte das Addieren von y nicht erforderlich sein, da y zu dem nicht weiter betrachteten Teil des Produktes addiert wird.

In manchen Fällen führt das Endprodukt beim Gleitkommabetrieb am Anfang eine Null. Z.B.:

Dezimal: 0,5 x 0,5 ^s 0,25 Binär: 0,1 χ 0,1 - 0,01

^anfängliche Null

009825/1781

In einem solchen Pall wird das Ergebnis normalerweise eine Stelle nach links verschoben und der» Exponententeil, des Produktes dementsprechend eingestellt.

Das Bit 2^ des zweifach genauen Produktes bildet das Bit mit der niedrigsten Ordnung bei dem normalisierten einfach genauen Produkt. Das höchstrangige Bit von y wird zu dem betreffenden Bit des zweifach genauen Produktes vor dem Normalisieren addiert, um die Genauigkeit zu wahren, falls eine Verschiebung nach links erforderlich, ist. Zusätzliche Abrundungsbetrachtungen sind im folgenden nicht beschrieben. Der Schaltungsaufwand für die Quadrierschaltung läßt sich verringern, wenn ein einfach genaues Ergebnis anstatt eines doppelt genauen Ergebnisses gewünscht wird, selbst wenn ein Teil

2
der Summe aus A und y wegen der Genauigkeit beibehalten werden müs-

Die Figuren 13 und I¹I zeigen mögliche Schaltungsaufbauten zur Realisierung der oben beschriebenen Rechenschemen.

Die oben beschriebene Quadrierschaltung ermöglicht nicht nur eine schnelle Multiplikation, sondern läßt sich auch zum Hinzufügen einer neuen Maschineninstruktion verwenden, was man als "Quadrierbefehl" bezeichnen könnte. Diese Operation bildet das Gegenteil von der Quadratwurzelbildung. Bei einer ganzzahligen Operation kann es vorkommen, daß ein Programm das Quadrieren eines Wortes aus einem Speicher, einem Akkumulator oder einem anderen Teil der arith metischen Einheit, aufruft. Das einzelne Wort wird sodann direkt in die Quadrierschaltung gegeben, welche den Ausgabewert in einer öjnstuflgen Operation bildet. Dabei ist keine Addition oder Subtraktion in der arithmetischen Einheit erforderlich. Die Quadratbildung geschieht schneller als bei irgendeinem der bekannten Quadrierverfahren, da lediglich ein Operand in die Quadrierschaltung eingegeben werden muß, während bei Üblichen Multipliziervorrichtungen beide Operanden getrennt eingegeben werden müssen,

9825/1781

selbst wenn sie identisch sind, oder aber von einem einfach eingegebenen Operanden vor dem Multiplizieren ein Duplikat gebildet werden muß. Die Logik des Quadrierens eines Operanden nach der Erfindung ist auch einfacher und schneller als mit einer logischen Schaltung, die für zwei verschiedene Operanden vorgesehen ist.

Bei Gleitkoramaoperationen wird der Exponententeil des Operanden verdoppelt, während der Mantissenteil quadriert wird. Das Verdoppeln läßt sich einfach durch Linksverschiebung in der arithmetischen Einheit um eine Stelle verwirklichen., wie unten vorgeschlagen ist: ι

OPERAND ^

EXPONENT MANTISSE

LINKSVERSCHIEBUNG

QUADRAT-BILDUNG

EXPONENT I MANTISSE [

< PRODUKT —^

p h fi

ben eines Operanden in geraösahlige Potenzen (χ _s χ -, χ usw) brauchen äußer der Verwendung der sehr schnellen Quadriersehaltung lediglich einfache Linksversehiebungen durchgeführt su werden. Das

·2 C ¹T

Erheben eines Operanden in mgeraazalilige Potenzen (χ* , χ , χ' usw) erfordert eine oder mehrere Qaaarleropsraticnsii sowie eine anschließende einfache Multiplikation

Di5 üblichen Frogr-ar-sii-erungen brauchen nlolit geändert su werdpn, \ic-' Vorteil aus dem Quadrierte fehl su sletiSiio Der Operator kanu die Q .■■»<:¹rierfunVM.on -aus deii Programmerfordemissesi ergSnsen und braucht ■: ' ■■.'■* die Multiplikation zwei identischer Gper-aaäsn einzuleiten.

''. "*:■:■?-2tir j--it gezeigt, wls das Produkt aus einer ungeraden und e'.ricv -_;.:i'auen Saiii ,rcöildet ¥ird* Um die Verwendung elne^ Quadriert -,haltung für η ■*■ ί Eit-s zu vermeiden, wenn ungeradsahlige oder geradzahlige Operanden mit jeweils η Bits multipliziert werden

009825/1781

BAD

sollen, wird ein Verfahren verwendet zum Kompensieren des "Fallen· lassens" eines Bit.

BINÄR 1000

+ ooii io)Tö~H

1000

- 0011 10)0101

ΟΟΙΟφ dieses Bit nicht berück x 0010 sichtigen 00000100*1

yooonooi 00000100^ 00010101 + 0011

DEZIMAL

2ΓΪ1 χ 5

nicht berücksichtigen

(^) nicht berücksich« st2 tigen

-> 25 i

00011000

Produkt

"■ 7

2 2

- 0,5 - o,5x - 0,5y - 0,5

= Z

(o,5x + o,

xy - y

Wie in der linken Seite dieser Darstellung zu erkennen ist, wird das niederrangigste Bit (lsb) der Hälfte der Summe der Operanden nicht berücksichtigt, und das niederrangigste Bit der Hälfte der Differenz ebenfalls nicht. Nachdem die Differenz der beiden derart gekürzten Quadratwerte gebildet ist, wird der kleinere der beiden ursprünglichen Operanden zu dieser Differenz addiert, so daß das genaue Ergebnis entsteht.

0 0-9 826/1781

Der rechte Teil der obigen Darstellung zeigt, wie der Bruchteil 0,5 beim Multiplizieren von 8 mit 3 vernachlässigt wird und wie die 3 mit 21 addiert wird und das Ergebnis 2H liefert. Die Rechtfertigung dieses Ausgleichsverfahrens für irgendwelche Operanden (x und y) ist ebenfalls dargestellt. Gemäß der Darstellung wird der Bruch 0,5 von der halben Summe aus χ und y subtrahiert sowie von der halben Differenz aus χ und y. Nach der Vereinfachung und Lösung ergibt sich die Antwort Z zu xy - y. Man erkennt, daß die Antwort um die Ziffer y niedriger ist als das gewünschte Produkt xy. Durch Hinzufügen von y ergibt sich das genaue Ergebnis. Praktisch kann y zu dem Quadrat der g halben Summe der Operanden hinzugegeben werden, und die Endsubtraktion ergibt das gewünschte Ergebnis. Dieses Verfahren ist schneller bei einem geringeren Bauteileaufwand. Als Beispiel sind die links unten angegebenen Operationen durch die rechten Operationen ersetzt.

25 25 - 4 (Endsubtraktion) + 3 (Kompensation)

009826/1711

Claims

Patentansprüche

1. Multipliziervorrichtung, gekennzeic h.n e t durch eine einen ersten und einen zweiten zu multiplizierenden Operanden aufnehmende arithmetische Einheit, welche eine Einrichtung zum vorübergehenden Speichern und zum Bilden des Produktes der Multiplikation auf einen Befehl hin umfaßt, durch eine mit der arithmetischen Einheit verbundene Quadrierschaltung, die aus der arithmetischen Einheit ein Paar identischer Operanden zur Multiplikation und zur Erzeugung der zweiten Potenz der identischen Operanden empfängt.

2. Multipliziervorrichtung nach Anspruch 1, dadurch gekennzeichnet , daß die arithmetische Einheit ein Eingangsregister, eine mit diesem verbundene Addiereinrichtung, eine ebenfalls mit dieser verbundene erste Subtrahiereinrichtung, eine an die Quadrierschaltung angeschlossene zweite Subtrahiereinrichtung, eine mit der zweiten Subtrahiereinrichtung gekoppelte Dividierainrichtung und ein Ausgangsregister aufweist, welches die dividierte Differenz aufnimmt und zeitweise speichert.

3. Multipliziervorrichtung nach Anspruch 1 oder 2, g e k e η η zeichnet durch eine Einrichtung zum Verarbeiten von zwei Eingangsoperanden und zum Erzeugen von zwei variablen Ein gangssignalen aus denselben,und durch eine Einrichtung zum Verarbeiten dieser beiden variablen Signale.

¹I. Multipliziervorrichtung nach Anspruch 1 oder 2, dadurch gekennzeichnet , daß die Quadrier schaltung ein Eingangsregister, eine Anzahl mit diesem verbundene UND-Gatter zum Erzeugen einer Anzahl Partialprodukte, einen einstufigen,

00 9825/1781 BAD

v\

nit den UND-Gattern verbundenen Addierer zum gleichzeitigen Addieren der Partialprodukte und ein an den Addierer angeschlossenes Ausgangsregister zum zeitweiligen Speichern des Summatlonsergebnisses der Partialprodukte aufweist.

5. Multipliziervorrichtung nach Anspruch 1, gekenn zeichnet durch eine Addiereinrichtung (13-^16) zum Addieren des ersten und zweiten Operanden (a,b), durch eine erste, an die Addiereinrichtung angeschaltete Quadrierschaltung (13ri2) zum Quadrieren der Summe (a+b), durch eine erste Subtrahiereinrichtung (13·ν1*Ο zum Subtrahieren des kleineren von dem grö- Λ ßeren Operanden, durch eine zweite, an die Subtrahiereinrichtung angeschaltete Quadrierschaltung(13-16) zum Quadrieren der von der Subtrahiereinrichtung gebildeten Differenz, durch eine zweite, mit der ersten und der zweiten Quadrierschaltung verbundene Subtrahiereinrichtung (13,18) zum Subtrahieren der quadrierten Ausgabewerte derselben, und durch eine an die zweite Subtrahiereinrichtung angeschaltete Div.fc'.lereinrichtung (13-20) zum Dividieren des Ausgangswertes derselben durch vier.

6. Multipliziervorrichtung nach Anspruch 1, gekenn zeichnet durch eine erste Addiereinrichtung zum Addieren der beiden zu multiplizierenden Operanden, durch eine -an die erste Addiereinrichtung angeschlossene erste Quadriereinrichtung I zum Quadrieren der von der ersten Addiereinrichtung gebildeten Summe, durch eine zweite Quadriereinrichtung zum Quadrieren des ersten Operanden, durch eine dritte Quadriereinrichtung zum Quadrieren des zweiten Operanden, durch eine an die zweite und die dritte Quadriereinrichtung angeschlossene zweite Addiereinrichtung zum Addieren der quadrierten Produkte, durch eine an die erste Quadriereinrichtung und die zweite Addiereinrichtung angeschaltete Subtrahiereinrichtung und durch eine an diese angeschaltete Dividiereinrichtung zum Dividieren der von der Subtrahiereinrichtung gelieferten Differenz durch zwei.

009825/ 1781

7. Multipliziervorrichtung nach Anspruch 1, gekenn zeichnet durch eine erste und eine zweite Quadriereinrlchtung, die mit dem ersten bzw. dem zweiten Operanden gespeist werden, durch eine zwischen der ersten und der zweiten Quadriereinrichtung angeschalteten Addiereinrichtung zum Addieren der quadrierten Ausgabewerte der Quadriereinrichtungen, durch eine erste Subtrahiereinrichtung zum Bilden der Differenz der beiden Operanden, durch eine dritte, an die erste Subtrahiereinrichtung angeschaltete Quadriereinrichtung zum Quadrieren des Differenzwertes, durch eine an die Addiereinrichtung und die dritte Quadriereinrichtung angeschaltete Subtrahiereinrichtung zum Subtrahieren des Produktes aus der dritten Quadriereinrichtung von der Summe aus der Addiereinrichtung, und durch eine an die zweite Subtrahiereinrichtung angeschaltete Dividiereinrichtung zum Dividieren der von der Subtrahiereinrichtung gebildeten Differenz durch zwei.

8. Multipliziervorrichtung nach Anspruch 1, gekenn zeichnet durch eine Addiereinrichtung zum Addieren des ersten und des zweiten Operanden, durch eine erste Subtrahiereinrichtung zum Subtrahieren der beiden Operanden voneinander, durch ein Paar Dividiereinrichtungen, von denen die eine mit der Addiereinrichtung und die andere mit der ersten Subtrahiereinrichtung verbunden ist, zum Dividieren der Summe bzw. der Differenz dieser Einrichtungen durch zwei, durch ein Paar Quadriereinrichtungen, die jeweils einzeln mit einer der Dividiereinrichtungen verbunden sind zum-gleichzeitigen Quadrieren der dividierten Summe bzw. der dividierten Differenz aus deifr betreffenden Paar der Dividiereinrichtungen, und durch eine zweite, mit dem Paar der Quadriereinrichtungen verbundenen Subtrahiereinrichtungen zum Subtrahieren der quadrierten Differenz einer der Quadriereinrichtungen von der quadrierten Summe der anderen Quadriereinrichtung .

09 825/1*781

9. Multipliziervorrichtung nach Anspruch 1, dadurch gekennzeichnet , daß die arithmetische Einheit eine Einrichtung zum Zuführen der Summe sowie der Differenz der beiden Operanden an die Quadriereinrichtung umfaßt sowie ferner eine Einrichtung zum Aufnehmen der Quadratwerte der Summe und der Differenz und zum Subtrahieren des kleineren der quadrierten Werte von dem größeren und zum Dividieren der gebildeten Differenz durch vier.

10. Multipliziervorrichtung nach'Anspruch 9> dadurch gekennzeichnet , daß die Quadrierschaltung ein Ein- | gangsregister zum Aufnehmen der Summe und der Differenz der beiden Operanden aufweist und eine Anzahl an das Eingangsregister angeschalteter UND-Gatter, zum Erzeugen von Partialprodukten, und daß ein einstufiger Addierer gemeinsam an die UND-Gatter angeschaltet ist zum gleichzeitigen Addieren der Partialprodukte, und daß an den Addierer ein Ausgangsregister angeschaltet ist zum zeitweiligen Speichern des gebildeten Produktes.

11. Multipliziervorrichtung nach Anspruch 10, dadurch gekennzeichnet , daß die Quadrierschaltung eine zwischen den UND-Gattern und dem einstufigen Addierer angeschaltete Einrichtung zum Vereinfachen der Partialprodukte vor deren Sum- J matlon durch den Addierer umfaßt.

12. Multipliziervorrichtung nach* Anspruch 1, zum Bilden eines Produktes aus identischen Operanden, gekennzeich -net durch ein Eingangsregister und eine Anzahl an dieses angeschalteter Gatter zum Erzeugen einer Anzahl Partialprodukte, durch einen gemeinsam an die Gatter angeschalteten einstufigen Addierer zum gleichzeitigen Addieren der Partialprodukte, und durch ein an den Addierer angeschaltetes Ausgangsregister zum Speichern des.Quadratwertes der identischen Operanden.

009825/1711

13. Multipliziervorrichtung nach Anspruch 12, dadurch gekennzeichnet , daß die Gatter eine Anzahl UND-Gatter bilden sowie eine Anzahl Freigabegatter.

Ik. Multipliziervorrichtung nach Anspruch 12 oder 13, dadurch gekennzeichnet , daß das Eingangsregister und das Ausgangsregister ein einziges Register bilden, welches abwechselnd als Eingangs- und als Ausgangsregister verwendet wird.

15. Multipliziervorrichtung nach Anspruch 1, gekenn zeichnet durch eine an die arithmetische Einheit angeschlossene Quadrierschaltung zum Ausführen einer einstufigen Quadrieroperation, durch einen an die arithmetische Einheit angeschalteten Kurzzeitspeicher für ein Wort, und durch eine an die Quadrierschaltung und den Kurzzeitspeicher angeschaltete getrennte Subtrahierschaltung.

16. Multipliziervorrichtung nach Anspruch 15, dadurch gekennzeichnet , daß die arithmetische Einheit außer einer Addiereinrichtung und einer Subtrahiereinrichtung eine getrennte Subtrahiereinrichtung aufweist.

17. Multipliziervorrichtung nach Anspruch 1, 15 oder 15, dadurch gekennzeichnet , daß der Kurzzeitspeicher einen Teil der arithmetischen Einheit bildet.

18. Multipliziervorrichtung nach Anspruch 15 bis 17, dadurch gekennzeichnet , daß der Kurzzeitspeicher ein in der arithmetischen Einheit enthaltenes Vielfachbitregister umfaßt, welches mit der getrennten Subtraktionseinrichtung gekoppelt iBt.

009825/1711

19. Multiplikationsverfahren, dadurch gekennzeichnet, daß die beiden zu multiplizierenden Operanden addiert werden, daß der kleinere von dem größeren Operanden subtrahiert wird, daß gleichzeitig die Quadrate der Summe und der Differenz der beiden Operanden gebildet wird, daß die quadrierte Differenz von der quadrierten Summe der Operanden subtrahiert wird und daß das Ergebnis dieser Subtraktion durch vier geteilt wird.

20. Multiplizierverfahren, dadurch gekennzeichnet, daß die beiden zu multiplizierenden Operanden addiert und gleichzeitig der kleinere von dem größeren Operariden subtra- f hiert wird, daß die so gebildete Summe und Differenz der Operanden einzeln und gleichzeitig durch zwei geteilt werden, und daß die derart gebildeten Teilergebnisse gleichzeitig quadriert und der aus der Differenz gebildete Quadratwert von dem aus der Summe gebildeten Quadratwert subtrahiert wird.

21. Multiplizierverfahren, us3uroh gekennzeichnet, daß die beiden Operanden quadriert werden, daß gleichzeitig der kleinere von dem größeren Operanden subtrahiert wird, daß sodann die quadrierten Operanden addiert, sodann die quadrierte Differenz von der quadrierten Summe der Operanden subtrahiert wird und schließlich das Teilergebnis durch zwei geteilt wird.

BAD ORIGINAL

009825/1781

Le ers