DE1956209B2

DE1956209B2 - Multipliziervorrichtung

Info

Publication number: DE1956209B2
Application number: DE1956209A
Authority: DE
Inventors: William A. Hatboro Pa. Stampler (V.St.A.)
Original assignee: Burroughs Corp
Current assignee: Unisys Corp
Priority date: 1968-11-07
Filing date: 1969-11-07
Publication date: 1979-06-28
Also published as: DE1956209C3; DE1956209A1; BR6913949D0; BE741276A; US3610906A; GB1280906A; FR2022785A1

Description

IO

15

20

25

J5

gekennzeichnet durch

a) eine arithmetische Einheit zum Aufnehmen der beiden Operanden, die mindestens Additionen ausführen kann,

b) mindestens eine nachgeschaltete Quadrierschaltung mit

bl) einem Eingangsregister zum Aufnehmen einer zu quadrierenden Binärzahl,

b2) einer Anzahl daran angeschlossener UND-Glieder zum Bilden der Partialprodukte aus j&i:m Bit der Binärzahl mit jeweils einem von allen Bits derselben,

b3) einer auf die UND-Glieder folgenden Vereinfachungsschaltung, die so ausgebildet ist daß jeweils nur ein aus ungleichen Faktoren gebildetes Partialprodukt um eine Stelle nach links verschoben dem Addierer zugeführt wird und daß an Stelle der aus gleichen Faktoren gebildeten Partialprodukte lediglich der betreffende Faktor an die (2n- l)te Stelle des Addierers geführt wird, wobei η die Stel¹ ? des Faktors im Operanden ist (F i g. 4), ^M

b4) einem an die Vereinfachungsschaltung angeschlossenen Addierer und

b5) einem Ausgangsregister zum Speichern der Teilergebnisse aus der /ereinfachungsschaltung.

2. Multipliziervorrichtung nach Anspruch 1, dadurch gekennzeichnet daß die arithmetische Einheit (13 — 10) die Summe der beiden Operanden bildet und daß diese Summe der nachgesschalteten Quadrierschaltung (13 —12) zugeleitet wird, daß eine erste Subtrahiereinrichtung (13 — 14) vorgesehen ^St, die den kleineren von dem größeren Operanden subtrahiert, daß eine zweite Quadrierschaltung (13—16) an diese Subtrahiereinrichtung angeschal- v·, tet ist und daß eine Subtrahiereinrichtung (13— 18) zum Subtrahieren der Ausgangswerte der Quadrierschaltungen vorgesehen ist sowie eine Dividiereinrichtung (13 — 20) zum Dividieren der gebildeten Differenz durch vier (Fig. 13). w

3. Multipliziervorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die arithmetische Einheit die Summe der beiden Operanden bildet und daß diese Summe der nachgeschalteten Quadrierschaltung zugeleitet wird, daß eine zweite Multipli- ->-> ziervorrichtung nach Anspruch 1 zum Quadrieren des ersten Operanden und eine dritte Multipliziervorrichtung nach Anspruch I zum Quadrieren des zweiten Operanden vorgesehen ist, daß auf diese beiden Multipliziervorrichtungen eine zweite Ad- &o diereinrichtung zum Addieren der Quadratwerte folgt, daß an die erste Multipliziervorrichtung und die zweite Addiereinrichtung eine Subtrahiereinrichtung angeschaltet ist zum Bilden der Differenz der Ausgangswerte und daß auf diese Subtrahiereinrichtung eine Dividiereinrichtung folgt zum Teilen des Ausgangswertes durch zwei.

Bei einer bekannten derartigen Multipliziervorrichtung (US-PS 31 91 017) sind für die Multiplikation eine Vielzahl von Einzeloperationen erforderlich, wobei der Schaltungsaufwand mit zunehmender Wortlänge der Operanden rasch ansteigt

Der Erfindung Hegt die Aufgabe zugrunde, eine digitale Multipliziervorrichtung der eingangs genannten Art zu schaffen, welche eine Vereinfachung der Berechnung und damit einen geringeren Schaltungsaufwand ermöglicht

Die Lösung dieser Aufgabe zeichnet sich aus durch folgende Merkmale:

b) durch mindestens eine nachgeschaltete Quadrierschaltung mit

bl) einem Eingangsregister zum Aufnehmen einer zu quadrierenden Binärzahl,

b2) einer Anzahl daran angeschlossener UND-Glieder zum Bilden der Partialprodukte aus jedem Bit der Binärzahl mit jeweils einem von allen Bits derselben,

b3) einer auf die UND-Glieder folgenden Vereinfachungsschaltung, die so ausgebildet ist daß jeweils nur ein aus ungleichen Faktoren gebildetes Partiaiprodukt um eine Stelle nach links verschoben dem Addierer zugeführt wird und daß an Stelle der aus gleichen Faktoren gebildeten Partialprodukte lediglich der betreffende Faktor an die (2n-1)te Stelle des Addierers geführt wird, wobei π die Stelle des Faktors im Operanden ist

b4) einem an die Vereinfachungsschaltung angeschlossenen Addierer und

b5) einem Ausgangsregister zum Speichern der Teilergebnisse aus der Vereinfachungsschaltung.

Eine besondere Ausführungsform ist darin zu sehen, daß die arithmetische Einheit die Summe der beiden Operanden bildet und daß diese Summe der nachgpschalteten QuadrVerschaltung zugeleitet wird, daß eine erste Subtrahiereinrichtung vorgesehen ist die den kleineren von dem größeren Operanden subtrahiert, daß eine zweite Quadrierschaltung an diese Subtrahieroinrichtung angeschaltet ist und daß eine Subtrahiereinrichtung zum Subtrahieren der Ausgangswerte der Quadrierschaltungen vorgesehen ist sowie eine Dividiereinrichtung zum Dividieren der gebildeten Differenz durch vier.

Eine andere Ausführungsform zeichnet sich dadurch aus, daß die arithmetische Einheit die Summe der beiden Operanden bildet und daß diese Summe der nachgeschalteten Quadrierschaltung zugeleitet wird, daß eine zweite Multipliziervorrichtung der erfindungsgemäßen Art zum Quadrieren des ersten Operanden und eine dritte Multipliziervorrichtung der erfindungsgemäßen Art zum Quadrieren des zweiten Operanden vorgesehen ist, daß auf diese beiden Multipliziervorrichtungen eine zweite Addiereinrichtung zum Addieren der Quadratwerte folgt, daß an die erste Multipliziervorrichtung und an die zweite Addiereinrichtung eine

Subtrahiereinrichtung angeschaltet ist zum Bilden der Differenz der Ausgangswerte und daß auf diese Subtrahiereinrichtung eine Dividiereinrichtung folgt zum Teilen des Ausgangswertes durch zwei.

Ausführungsbeispiele der Erfindung sind im folgenden anhand schematischer Zeichnungen ergänzend beschrieben.

F i g. 1 veranschaulicht eine Anzahl Verfahren zum Multiplizieren;

F i g. 2 zeigt ein bekanntes System zum Multiplizieren von zwei 3-Bit-Operanden;

F ι g. 3 zeigt das System zum Multiplizieren von zwei 3-Bit-Operanden mittels Quadrieren;

F i g. 4 zeigt die Weiterbildung des Systems für eine 10-Bit-Quadrierschaltung;

F i g. 5 ist ein vereinfachtes Schaltbild einer Quadrierschaltung;

F i g. 6a bis 6u zeigen die erforderlichen Schaltungskreise für jedes Bit beim Quadrieren eines 10-Bit-Operanden. Die Verknüpfungsglieder für die Ableitung der Partiaiprodukte und der einstufige Addierer sind in diesen Figuren zusammen dargestellt;

F i g. 7a zeigt die übliche Übertragweiter'eitung bei einem 10-Bit-Einstufenaddierer;

F i g. 7 b zeigt die Abkürzung der längsten Übertragketie in demselben lO-Bit-Einstufenaddierer;

Fig.8 zeigt ein vereinfachtes Schaltbild einer Multipliziervorrichtung;

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

F i g. 10 zeigt einen abgeänderten Algorithmus;

F i g. 11 zeigt die Schiebeoperation am Eingang der Quadrierschaltung;

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

Fig. 13 und 14 sind Blockschaltbilder von Multipliziervorrichtungen.

F i g. 1 zeigt drei verschiedene Verfahren zum Multiplizieren unter Verwendung von logischen Schaltungen, nä.nlich 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. la zeigt ein theoretisches Multiplizierverfahren, bei dem das Produkt direkt aus den Operanden (Multiplikand und Multiplikator) gebildet wird. Wegen der Komplexität der erforderlichen logischen Schaltung hat dieses Verfahren kaum Bedeutung erlangt. Beim Multiplizieren 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 to¹².

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 048 576 Eingangsmöglichkeiten, und die Verringerung der Komplexität der logischen Schaltung ist beachtlich. Gemäß Fig. Ic werden die beiden Operanden in der arithmetischen Einheit so behalten, GiQ 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 bleiben, 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 Teils von Fig.2 gezeigt Die erforderliche logische Schaltung zur direkten Multiplikation ist auf der rechten Seite von F i g. 2 dargestellt F i g. 3 zeigt die Multiplikation eines 3-Bit-Wortes (a, b und c) mit sich selbst (Quadrieren) und die dazu erforderliche logische Schaltung. Man erkennt, daß das nicht vereinfachte Produkt ist:

(a²)2* + 2 ab{2³) + {2 ac+ V)2² + (2 bcJP +

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

Quadrieren einer Binürzahl

jedes Bit λ* ist gemäß den bJnärarithmctischcn Gesetzen gleich x, wenn η eine positive Zahl ungleich Null ist Zum Beispiel:

0< = 0; 02 = 0; (P = 0; etc. 1- = 1; P= 1; P = ljetc.

Daher ist bei dem Beispiel nach F i g. 3 a² = a, b² = öunde* = c.

Das Multiplizieren mit zwei wird gewöhnlich ausgeführt durch Stellenverschiebung nach links um 1 Bit. Daher ist:

(2 abJP = (ab)2*\ (2 acjl² = (ac/2³; (2 bc}?> = (bcjl¹. Vereinfachtes Produkt

Gemäß F i g. 3 führen die beiden obigen Überlegungen zu dem folgenden vereinfachten Produkt:

(a + abp* f (acJP + (b + bcfi? + (0)2' + (CpP.

Wenn gemäß dem obigen Beispiel irgendeine ganze Bir.ärzahl quadriert wird, ist das Bit O¹ 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 F i g. 3, ist das niederrangigste Bit (2°) des Produktes immer gleich demselben Bit des Operanden. Das Quadrieren einer ungeraden Zahl erzeugt eine gerade Zahl. Das Quadrieren einer geraden Zahl erzeugt ebenfalls eine gerade Zahl. Es ist daher ebenfalls nur ein geringfügiger Schaltaufwand erforderlich, um das Bit 2° des Operanden in das Bit 2° des Produktes zu übertragen.

Unter Berücksichtigung der obigen Vereinfachungen läßt sich zum Quadrieren eines 3-Bit-Wortes die im rechten Teil von F i g. 3 dargestellte Schaltung verwen den. Hierbei wird das Register zum Speichern des Produktes gelöscht (auf Null gestellt), bevor das Produkt hineingegeben wird. F i g. 3 zeigt, daß die Quadrierlogik lediglich acht Verknüpfungsglieder erfordert während die Multipltzierlcgik nach F i g. 2 neun Verknüpfungs glieder sowie drei Volladdierer und drei Halbaddierer erfordert. Die dargestellte Quadrierlogik ist nicht nur wesentlich einfacher als die Multipiizierlogik, sondern auch schneller. Man erkennt, daß bei dem Ausführungsbeispiel nach Fig.3 keine Übertragweiterleitung erforderlich ist.

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

Tabelle A

Operanden
(a) X (b)

Übliches Produkt

Gleichwertiges Produkt

20X20

21X19

22X18

23X17

24X16

25X15

26X14

27X13

28X12

29X11

30X10

31X9

32X8

33X7

34X6

35X5

35X4

37X3

38X2

39X1

40X0

41X(-1)

42X(-2)

400 399 396 391

384 375 364 351 336 319 300 279 256 231 204 175 144 111 76 39 0

-41 -84

400-0 400-1 400-4 400-9 400 400 400 400 400 400 400- 400-121 400 400-169 400 400-225 400-256 400 400 400-361 400 400 400-484

Tabelle B	Übliches	Gleichwertiges
Operanden	Produkt	Produkt
(a)X(b)	90,25	90,25-0
9,5X9,5	90	90,25-0,25
9X10	88	90,25 - 2,25
8X11	84	90,25-6,25
7X12	78	90,25 -12,25
6X13	70	90,25-20,25
5X14	60	90,25-30,25
4X15	48	90,25-42,25
3X16	34	90,25 - 56,25
2X17	18	90,25-72,25
1X18	0	90,25-90,25
0X19	-20	90,25-110,25
-1X20	-42	90,25 -132,25
-2X21	-66	90.25 -156,25
-3X22

Die linke Spalte zeigt die Operanden, deren arithmetisches Mittel 20 ist (ι. B. = 2o) . Die nächste Spalte zeigt das übliche Produkt jedes Operanden. Die letzte Spalte zeigt ein gleichwertiges Produkt (z. B. 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.

Für das Beispiel 7 χ 12 = 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 J und quadriert (2,5^J = 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 Binäroperanden an dem Beispiel b χ 4. Die äquivalenten Dezimalwertc der ßinär/iffcrn sind der Klarheit halber dargestellt. Das Dividieren durch zwei geschieht durch Verschiebung nach rechts.

Binärrechnung

Dezimalrechnung

Aufgabe: 110XIOO = ?

Π ι

npranflpn

Summe d. Operanden

Dividieren durch 2

(Rechtsverschiebung)

Quadrieren

Operanden

Differenz d. Operanden
Dividieren durch 2
(Rechtsverschiebung)
Quadrieren

Differenz d.

beiden Quadratwerte

Produkt

!!0
KX)

1010

Aufgabe:

101
011001

110
100

010

001
ΟΟΟΟϋί

011001
000001

011000

6X4

4
IO

5
25

6
-4

25 ^J

24

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

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

F i g. 4 zeigt ein Verfahren zum Entwickeln der logischen Schaltung für einen 10-Bit-Operanden. Hierbei wird in gleicher Weise vorgegangen wie vorst~hend 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.4 ist j das niederrangigste Bit (2°) des Operanden und a das höchstrangige Bit desselben (2⁹J. Die Partialprodukte werden durch Multiplizieren jedes Bit des Operanden mit sich selbst und mit jedem anderen Bit gewonnen. Wie oben beschrieben, erfordert die Quadratbildung a² = a; fi² = b usw. keinen Logikaufwand. Die Partialprodukte aus ungleichen Bits treten jeweils doppelt auf (z. B. / χ j = ij; Jx i = ij; ij + ij = 2 ij) Der Koeffizient 2 wird durch Rechtsverschiebung eliminiert, wie in Fig.4 durch die schräg verlaufenden Pfeile dargestellt ist

&5 In der. Zeichnungen äst das Produkt zweier verschiedener Bits, z. B. /und/ als ij dargestellt Die Tabelle, die die Multiplikation von /undy'zeigt, zeigt den Binärwert 0 am Ausgang mit Ausnahme, wenn /undy beide gleich 1

sind. In diesem Fall is! das Produkt gleich dem Binärwert I.

Die logische Schaltung zum Multiplizieren von /und j bildet ein einfaches UND-Glied mit zwei Eingängen.

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

Die Partialprodukte werden in einer Igosischen Operation kombiniert, die sich als einstuiige Addition ansehen läßt.

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

Der unten beschriebene Einschritt-Addierer kombiniert die Partialprodukle des 10-Bit-Operanden (oder geringfügiger Variationen desselben) und erzeugt die genaue 20-Bit-Antwort direkt. Die gesamte Quadrierlogik arbeitet synchron, 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 Übertrag gebildet wird. Jedes Bit cics 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 Einstufen-Addierer erzeugt Vielfachüberträge praktisch gleichzeitig. Die zum Weiterleiten der Überträge zwecks Erzeugen des 20-Bit-Ergebnisses erforderliche Zeit ist niedriger als die zum Weiterleiten eines einzigen Übertrags bitweise von der niederrangigsten zur höchstrangigen Stelle in einem üblichen 20-Bit-Addierer erforderliche Zeit, wie bei der Beschreibung zu F i g. 6 erläutert ist.

Ferner ist neben den üblichen Verknüpfungsgliedern noch ein Anlivalcnz-ODER-Giied nötig. Dieses im folgenden auch NOR-Glied genannte Schaltungselement erzeugt ein Ausgangssignal (den logischen Wert 1) nur dann, wenn beide Eingangsinformationen voneinander verschieden sind. Wenn die Eingänge Ä und //(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. Volladdierer.

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

Die Logik zum Quadrieren eines 10-Bit-Operanden ist in den Fig.6 dargestellt Diese Figuren zeigen sowohl die Verknüpfungsglieder zum Erzeugen der Partialprodukte als auch den Einstufen-Addierer. Sie sind in F i g. 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. Die drei niederrangigsten Bits des Produktes (2°, 2", 2²J sind wegen ihrer Einfachheit zu einer Gruppe zusammengeschlossen.

Bits 2°,2' und 2²(F ig. 6a)

Die logische Schaltung braucht lediglich das 2°-Bit des Allsgangsregisters auf I zu stellen, wenn dasselbe Bit des Operanden in dem Eingangsregister gleich 1 ist. Das Bit 2¹ in dem 20-Bit-Ausgangsregister ist immer gleich Null. In der logischen Schaltung für das 2²-Bit sind die

ίο Verknüpfungsglieder gemäß den Erfordernissen der F i g. 4 eingestellt, wonach das Addieren der Partialprodukte ij und / die Summe für das Bit 2² des Ausgangsregisters erzeugt. Die logische Schaltung stellt das 2²-Bit in dem Ausgangsregister lediglich auf 1 ein, wenn das Bit /des Operanden gleich 1 ist und das Bit j des Operanden gleich Null ist.

Bit 2³(F ig. 6b und 6c)

Ein Aniivdieiii-ODER-Glicu und ein UND-Glied ilii'i

2Ii drei Eingängen erzeugen die Summe für das Bit 2³ des Ausgangsregisters. Es sind keine Überträ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 Fig. 6a, 6b und 6c dargestellt), um den Ausgang der logischen Schaltung an das Ausgangsregister durchzuschallen, so daß Schaltvorgänge keinen Flip-Flop umkippen, der im NuII-Zustand bleiben sollte. Dieses Freigabesignal kann

so angelegt werden, nachdem sämtliche Überträge weitergeleitet und alle Schaltvorgänge genügend abgeklungen sind. Ein Vorteil des Freigabesignals und der zugeordneten Verknüpfungsglieder 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 NuII- und Einerausgänge an die Quadrierschaltung gelegt werden. Die Schaltung kann gemäß F i g. 6c oder auch andersartig geändert werden, um die Null- und Einerausgangswerte zu ergeben, so daß das Register für die Aufnahme des Ausgangswertes 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 dargestellt. F i,». 4 zeigt z. B., 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

Bit 2« (Fi g.6d)

Man erkennt daß die logische Schaltung nach F i g. 6d den Wert ensprechend dem Bit 2* des Ausgangsregisters

ohne Überträge von vorhergehenden Stufen erzeugt Die normalerweise von Volladdierern oder Halbaddierern für die nächste Stufe erzeugten Überträge sind ersetzt durch die Schaltung nach F i g. 6e, welche den »Übertragw-Eingang für die Schaltungsstufe 2⁵ erzeugt

Die logische Schaltung wird um so komplizierter, je größer das Eingangsregister wird. Bei Verwendung üblicher Addierer und zugeordneter Übertragungsstufen in der Quadrierschaltung ist die einzige merkliche

Belastung des Eingangsregisters von den UND-Gliedern 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 Stufer verwendet, um eine zu große Kompliziertheit und übermäßige Belastung des Eingangsregisters zu vermeiden.

Bit2'ⁱ(Fig.6fund6g)

Es werden zwei Volladdierer verwendet zum Erzeugen des 2⁵-Bit-Ausgabewertes. Obwohl zwei Überträge (C5a und C5b)d\irch diese Addierer erzeugt werden, brauchen sie nicht verwendet zu v/erden. Um die Übertragkette zu kürzen und die Rechengeschwindigkeit der Quadrierlogik auf diese Weise ;tu erhöhen, werden die Überträge für die 2⁶-Bit-Schaltung gemäß F i g. 6 direkt erzeugt.

Bit2⁶(Fig. 6h)

In dieser Stufe sind zwei Volladdierer vorgesehen zum Erzeugen der Summe für das Bit 2⁶ des Ausgaberegisters und zum Erzeugen der Überträge C6aund C6b zur Verwendung in der2⁷-Bit-Stufe.

Bits 2⁷ bis 2" (F i g. 6i bis 6s)

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

Bit2¹⁸(Fig.6t)

Diese Stufe verwendet lediglich ein UND-Glied mit zwei Eingängen und ein Antivalenz-ODER-Glied zum Erzeugen der Summe für das Bit 2¹⁸ des Ausgaberegisters. Es wird kein Übertrag für die Stufe 2'¹· erzeugt.

Bit2>9(Fig.6u)

Diese Stufe erhält den Übertrag direkt von der Stufe 2¹⁷ (C 17). Durch diese Technik wird die Übertragweitergabe (unter Umgehung der Stufe 2¹⁸) ohne merkliche Erhöhung des Schaltungsaufwandes beschleunigt.

Ubertragvereinfachung

Bei Verwendung üblicher Volladdierer und Übertragerzcuguüg für die Stufen 2⁷ bis 2¹⁹ würden die Überträge gemäß den horizontalen Linieii in Fig. 7a weitergegeben werden. Es sei bemerkt, daß bis zu vier Übsrträge gleichzeitig von der Stufe Ί* bis zur Stufe 2¹³ auftreten können. Aufgrund der beschriebenen Schaitungstechnik für die Bits 2³, 2³ _t 2·, 2^!8 und 2'⁹ wird die Weitergabekette für die Oberträge gemäß F i g. 7 durch die logische Schaltung für den einstufigen Addierer verkürzt Der längste Übertrag beginnt bei der Stufe 2⁵ und endet bei der Stufe 2'⁹, wobei die Stufe 2¹⁸ umgangen wird. Die Übertragweiterleitung wird daher auf Kosten einer geringfü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 Obertragweitergabe durch einen komplexeren Schaltungsaufwand weiter beschleunigt werden.

Die Weitergabe verschiedener Überträge zur gleichen Zeit verlangsamt die Obertragweitergabe nicht in großem Maße. I.η wesentlichen bestimmt der Weitergabeweg für den längsten Übertrag diese Zeit. Es lassen sich Techniker, zum Gruppieren der Überträge von zwei oder mehr Stufen und zum Weiterleiten des sich ') daraus ergebenden Übertrages verwenden.

Vereinfachung für einfach genaue Multiplikation

Die bisherige Beschreibung betrifft 10-Bit-Operanden

in und ein 20-Bit-Produkt, wie es als Ergebnis beim Rechnen mit ganzen Zahlen auftritt. Fin 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

i") 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 wer-

:o den. Überträ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. 6i bei dem Bit 2¹⁰ mit den Überträgen C9a. C9b, C9c und

2Ί C9dgezeigt. Im allgemeinen kann die in den F i g. 6a bis 6f dargestellte Schaltung für einfach genaue Ergebnisse fortgelassen werden. Die Schaltung nach F i g. 6g wird beibehalten. Die Schaltung für die Bits 2* bis 2^s* (F i g. 6h bis 6k) wird unter geringfügigen Vereinfachungen

in beibehalten, da die Summenausgabewerte der niederrangigen Hälfte des 20-Bit-Ausgabewertes nicht benötigt werden. Es lassen sich Techniken anwenden zum direkten Erzeugen von Überträgen ohne Durchlaufen der Addierschaltung vorhergehender Stufen (Fig.6g),

r. um die Übertrageingangswerte C9a. C9b. C9c und C9dfür die Stufe 2'°zu erzeugen.

Wenn diese Überträge direkt erzeugt werden, können die Schaltungen nach den Fig. 6a bis 6k fortgelassen werden. Die Multiplikationsgeschwindig-

4(i keit wird dann erhöht, da die Übertragkette beträchtlich gekürzt ist.

Algol zum Multiplizieren durch Differenzbildung
4Ί von zwei Quadratwerten

Im folgenden ist die logische Schaltung des Quadrierens in Verbindung mit einer arithmetischen Schaltung des Rechners beschrieben.

F i g. 8 zeigt ein vereinfachtes Diagramm eines schnellen Multiplikators. Die arithmetische Einheit des Rechners arbeilet unabhängig von der Quadrierstufe, Wenn die arithmetische Einheit ein Wort an das Eingangsregister der Quadrierschaltung 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 Rechenschemata angegeben. Die ersten beiden Rechenschemata ergeben eine hohe Rechengeschwindigkeit, erfordern jedoch den doppelten Aufwand an Schaltungsteilen im Vergleich zu dem dritten Rechenschema.

o5 Das Schema nach F i g. 9 entspricht dem vereinfachten Diagramm von F i g. 8 mit der Ausnahme, daß zwei arithmetische Einheiten und zwei Quadrierschaltungen für Parallelbetrieb erforderlich sind.

Stufe I
Anfangszustände

Bei diesem Rechenschema ist angenommen, dfiß 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 Gleitkommaoperation 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 ganzzahligcn Operanden).

Die Quadrierschaiiung verwendet die Absolutwerte (|λ·|;|>1) der Eingangsoperanden χ und y. 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 sind.

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 10-Bit-O;;eranden müssen also Quadrierschaltungen für 1! Pit vorhanden sein. Verfahren, welche unter diesen Umständen kein extra Bit erfordern, sind in den folgenden Algolangaben enthalten.

Stufe 2

Quadrieren der Summe und der Differenz der Operanden

In einer arithmetischen Einheit werden die Operanden .v und y addiert und die halbe Summe (in F i g. 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 der Quadrierschaltung

ist mit A² bezeichnet. Dieser Wert wird in den Minuendenteii 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 Eingangsregisier der Quadrierschaltung gegeben. Der Ausgabewert der Quadrierschaltung beträgt f J und ist mit B² bezeichnet. Dieser Wert wird als Subtrahendenteil in denselben Addierer gegeben, der den Wert A² enthält.

Stufe 3
Bildung der Differenz A⁷ minus B²

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.

Modifiziertes Rechenschema für hohe ' Geschwindigkeit

Dieses in Fig. 10 dargestellte Rechenschema erfordert eine weitere Addition, jedoch kein Extra-Bit für die Multiplikation einer geradzahligen mit einer ungerad-

K) zahligen Ziffer. Das Multiplizieren von 10-Bit-Operanden erfordert eine 10-Bit-Quadrierschaltung.

Bei diesem Rechenschema werden die Operanden χ und y gemäß Fig. 11 addiert. Bei der Stellenverschiebung nach rechts wird das niederrangigste Bit der

r, Summe in das Speicherbit M verschoben. Dieses Speicherbit erhält den Wert Null, falls * und y be'de gerade sind. Wenn einer der Operanden ungerade und der andere gerade ist, erhält das Bit M den Wert 1. Dicsci Fäii erforderi eine besondere Behandlung, da der

Jn Durchschnittswert aus einer geraden und einer ungeraden Zahl einen Bruch ergibt (z. B. ist das Mittel aus 9 und 10 gleich 9,5). Bei dem betrachteten Rechenschema wird der Anteil hinter dem Komma (0,5) vernachlässigt und später kompensiert.

>-> Bei der ersten Subtraktion wird y von Af subtrahiert, wie oben beschrieben ist. Der Operand /muß immer der kleinere von 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.

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 RegistP·· gespeicherte Operand y zu dem Ergebnis der Subtraktion addiert (y wird zu 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 Verrachlässigung des Bruchteiles bei der Rechtsverschieoung der Summe aus xuxiay.

Betrachtungen über den Schaltungsaufwand

Ein Schaltungsaufbau mit lediglich einer arithmetischen Einheit und einer Quadrierschaltung ist bei v\ Anwendung von Mikroschaltungen praktisch, obgleich die Bauteiizahl unter den gegenwärtigen Umständen hoch ist. Zum Beispiel findet man die Zahl η von UND-Gliedern mit zwei Eingängen, die zum Erzeugen der Partialprodukte erforderlich ist, gemäß der Formel:

η = b

(b-l)

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

Im folgenden sind Verfahren zum Verringern des Schaltungsaufwandes angegeben.

Dieses Verfahren der Multiplikation unterteilt die Quadrierschaltung gemäß Fig. 12. Anfänglich sind die Operanden |x| und \y\ in der üblichen arithmetischen Einheit

Stufe 1

Hierbei werden χ und y addiert und in die Quadrierschaltung verschoben. Das niederrangigste Bit der Summe wird in dem Bit-Speicher //gespeichert Zur gleichen Zeit vergleicht ein Komparator od. dgl. χ und y miteinander, um den niedrigsten Operanden herauszufinden.

Stufe 2

Die Quadrierschaltung quadriert A und erzeugt A². Inzwischen sind χ und y, falls erforderlich, in der arithmetischen Einheit vertauscht worden, damit der kleinere Operand an der Stelle y steht Sodann wird y von χ subtrahiert und y ferner kurzzeitig gespeichert, wenn das Bit M gleich 1 ist.

Stufe 3

Das Produkt A² wird in die arithmetische Einheit gegeben, während die Hälfte der Differenz von χ und y (B)\n die Quadrierschaltung gegeben wird.

Stufe 4

Die Quadrierschaltung quadriert den Eingangswert B und erzeugt den Wert B². Inzwischen wird y von der betreffenden Speicherstelle 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 Mgleich 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 4 - eine Quadratbildung (B-* B²) Stufe 5 — eine Subtraktion

Dezimal:	0,5	χ 0,5	= 0,25
Binär:	0.1	χ 0.1	= 0.01
			^- anfängliche Null

In einem solchen Fall wird das Ergebnis normalerweise eine Stelle nach links verschoben und der Exponentenanteil 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 der Summe aus A² und y wegen der Genauigkeit beibehalten werden müssen.

Die Fig. 13 und 14 zeigen mögliche Schaltungsaufbauten zur Realisierung der oben beschriebenen Rechenschemen.

Quadrieren für erhöhten Durchsatz

Wenn der Rechner die Subtraktion durch Komplementbildung des Subtrahenden und durch Addition ausführt, kann die für die letzte Subtraktion (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 Übertragung von B² erreicht.

Am Ende des Multipliziervorganges muß y zu A² in ganzen Operationen addiert werden. Beim Gleitkommabetrieb, bei dem die niederiangigste Hälfte des zweifach genauen Produktes gewöhnlich fallengelassen 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. Zum Beispiel:

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. Dies? 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 derarithmetischen Einheit aufruft. Das einzelne Wort wird sodann direkt in die Quadrierschaltung gegeben, welche den

j, Ausgabewert in einer einstufigen 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, 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 isl auch einfacher und schneller als mit einer logischen Schaltung, die für zwei verschiedene Operanden vorgesehen ist

Bei Gleitkommaoperationen wird der Exponententeil des Operanden verdoppelt, während der Mantissentei! 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

LINKS VERSCHIEBUNG

QUADRATBILDUNG

65 EXPONENT

MANTISSE

PRODUKT-

Das Potenzieren kann äußerst schnell ausgeführt werden. Beim Erheben eines Operanden in geradzahlige Potenzen (x², x⁴, x* usw.) brauchen außer der Verwendung der sehr schnellen Quadrierschaltung lediglich einfache Linksverschiebungen durchgeführt zu werden. Das Erheben eines Operanden in ungeradzahlige Potenzen (x³, X^s, x⁷ usw.) erfordert eine oder mehrere Quadrieroperationen sowie eine anschließende einfache Multiplikation.

Die üblichen Programmierungen brauchen nicht geändert zu werden, um Vorteil aus dem Quadrierbefehl

to

zu ziehen. Der Operator kann die Quadrierfunktion aus den Programmerfordernissen ergänzen und braucht nicht die Multiplikation zwei identischer Operanden einzuleiten.

Im folgendes ist gezeigt, wie das Produkt aus einer ungeraden und einer geraden Zahl gebildet wird. Um die Verwendung einer Quadrierschaltung für π + 1 Bits zu vermeiden, wenn ungeradzahlige oder geradzahlige Operanden mit jeweils π Bits multipliziert werden sollen, wird ein Verfahren verwendet zum Kompensieren des »Fallenlassens« eines Bit

BINÄR

DEZIMAL

1000
+0011

10) 1011

0101

XOIOl

■ 00011001

Verschieben dieses Bit in die Bitspeicherstelle M

1000 -0011

10) 0101

0010 φ dieses Bit nicht berücksichtigen XOOlO

00000100*

00011001 -00000100«

00010101 +0011

00011000

Produkt 2)

8
+3

2) 11

25

8 -3

2, ® nicht berücksichtigen X2

25 -4«

21 +3

24

(0.5.x + 0,5 >■ - 0.5² - 0,5.x - 0,5 y - O,5² = Z xy — y= Z

Wie in der linken Seite dieser Darstellung zu erkennen ist, wird das niederrangigste Bit (1 sb) 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.

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 24 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 Zzu 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 halben Summe der Operanden hinzugegeben «verden, 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.

55 25

— 4 (Endsubtraktion) 21

+ 3 24

25 + 3 (Kompensation)

28 - 4

Hierzu 11 Blatt Zcichniinücn

Claims

Patentansprüche:

J. Digitale Multipliziervorrichtung zum Bilden eines Produktes gemäß einem der beiden Algorithmen:

Die Erfindung betrifft eine digitale Multipliziervorrichtung zum Bilden eines Produktes gemäß einem der beiden Algorithmen

κ ■ _y=*((x+y)/2¥-({x-yy2yoder