DE2727051C3

DE2727051C3 - Einrichtung zur binären Multiplikation einer ersten Zahl als Multiplikand mit einer den Multiplikator ergebenden Summe aus einer zweiten und dritten Zahl im Binärcode

Info

Publication number: DE2727051C3
Application number: DE2727051A
Authority: DE
Inventors: Stanislaw Dr. Warschau Majerski
Original assignee: INSTYTUT MASZYN MATEMATYCZNYCH WARSCHAU
Current assignee: INSTYTUT MASZYN MATEMATYCZNYCH WARSCHAU
Priority date: 1977-06-09
Filing date: 1977-06-15
Publication date: 1980-07-17
Also published as: DE2727051A1; US4215419A; GB1582958A; DE2727051B2; FR2401458A1

Description

Die Erfindung betrifft eine digitale Einrichtung gemäß dem Oberbegriff des Hauptanspruchs,

Eine Einrichtung der eingangs genannten Art ist bereits aus der DE-AS 11 90 705 bekannt, bei der verschiedene Register für den Multiplikanden und den ϊ Multiplikator vorgesehen sind. Dabei können bei dieser Einrichtung Additionen in Verbindung mit Multiplikationen ausgeführt werden.

In anderen bekannten Lösungen für schnelle digitale Multiplikationsschaltungen läßt sich die schnelle Durch- ι ο führung der binären Multiplikation einer Zahl mit einer Summe aus zwei Zahlen durch eine schnelle Addition dieser Summanden und darauffolgende schnelle Multiplikation dieser Zahl mit dem Ergebnis der Addition erreichen. Eine hohe Geschwindigkeit der Addition wird in den Rechenmaschinen durch Anwendung von parallelen Addierern erzielt, welche mit zusätzlichen, oft sehr komplexen, die Übertragungsweiterleitung, d.h. die Zeit für eine Änderung des Übertrags verkürzenden Schaltungen versehen sind. Wesentlicher ist es, die Zeit der Multiplikation, die wesentlich länger ist als die der Addition, zu verkürzen.

Eine binäre Multiplikation in den Rechenmaschinen läßt sich in der Regel durch die Addition einer Reihe von Teilprodukten ausführen, welche gegeneinander verschobene Mehrfache des Multiplikanden bilden, die durch Multiplikation des Multiplikanden mit den Summanden des Multiplikators gewonnen werden, die in den binären Multiplikationsschaltungen durch Bits oder Bitgruppen vertreten sind. Sehr hohe Geschwin- jo digkeiten bei der binären Multiplikation werden durch gleichzeitiges, paralleles Addieren von mehreren Teilprodukten erzielt, von welchen jedes einer Gruppe einiger Binärstellen des Multiplikators entspricht. Die schnellste bekannte Methode der gleichzeitigen Addition von mehreren Mehrbitteilprodukten ist in C. S. Wallace, »Α Suggestion for a Fast Multiplier«, The Institute of Electrical and Electronics Engineers Transactions of Electronic Computers, Band EC-13, Seiten 14 bis 17, Februar 1964, und T. G. Hallin, M. J. Flynn, »Pipelining of Arithmetic Functions«, The Institute of Electrical and Electronics Engineers Transactions of Electronic Computers«, Band EC-21, Seiten 880 bis 886, August 1972, beschrieben. Die Anwendung dieser Methode in digitalen Schaltungen ist an dem Beispiel mit aus einer g^voßen Anzahl von Addierern mit Übertragsspeicherung zusammengesetzten Schaltung erläutert, wobei diese Addierer eine Baumstruktur mit an den Ausgang des Addiererbaumes angeschlossenen Addier?rn mit Übertragsweiterleitung bilden; der letzte Addierer weist die die Übertragsänderung maximal beschleunigenden Schaltungen auf. Die Gesamtzahl der den Ausgängen dieses Addiererbaumes zugeführten und während der Durchführung der Multiplikation zu addierenden Teilprodukte kann größer als die Zahl der Multiplikatorbits sein, wenn die einzelnen Teilprodukte, die mehrere Bits enthalten, solche Bitgruppen darstellen, die Mehrfache des Multiplikanden sind.

Die verhältnismäßig oft in numerischen Berechnungen Vorkommende wechselweise Durchführung der Addition und der Multiplikation erfordert die Einhaltung einer gewissen Zeitperiode für die Übertragsweiterleitung oder -änderung während der Addition. Diese muß nach der die letzte Multiplikation beendenden Übertragsänderung erfolgen. Bei Anwendung der beschriebenen, sehr schnellen Multiplikationsschaltung kann der relative Zeitverlust für die Durchführung der Addition bedeutsam sein. Dies stellt einen wesentlichen Nachteil der bisher bekannten, sehr schnellen Schaltungen dar, welche die binäre Multiplikation einer Zahl mit einer Summe von Zahlen ausführen.

Der Erfindung liegt demgegenüber die Aufgabe zugrunde, eine Einrichtung gemäß dem Oberbegriff des Hauptanspruchs zu schaffen, mit der bei einer Recheneinrichtung zur Durchführung von Additionen und Multiplikationen eine getrennte Addition mit Übertragsbildung vermieden wird.

Diese Aufgabe wird erfindungsgemäß durch den Gegenstand des Hauptanspruchs gelöst Weitere Ausgestaltungen der Erfindung ergeben sich aus den Unteransprüchen.

Mit der digitalen Einrichtung zur binären Multiplikation ist nur ein Minimum an Vielfachen des Multiplikanden zu berechnen; bei Bitgruppen mit zwei Bits je Bitgruppe sind nur ein Einfaches und ein Zweifaches des Multiplikanden erforderlich, wobei das Zweifache des Multiplikanden durch einfache Verschiebung der dem Einfachen entsprechenden BinärcLcstellung um eine Stelle erhalten wird. Negative Werte dei ganzen Zahlen werden dabei dadurch berücksichtigt, daß die betreffende Binärdarstellung des Einfachen oder Zweifachen des Multiplikanden unter Hinzufügung eines Korrekturbits negier;, wird.

Der durch zwei Summanden in binärer Darstellung ausgedrückte Multiplikator wird parallel ohne effektive Addition dieser Summanden in einen redundanten Positionscode mit einem gegenüber Nufl symmetrischen Ziffernwertbereich konvertiert, wobei diese Ziffern die Vielfachen des Multiplikanden für die einzelnen Teilprodukte bestimmten. Die die Bits der Multiplikatorsummanden darstellenden Signale werden in Signale umgeformt, welche die Ziffern des Positionscodes des Multiplikators darstellen.

Die digitale Einrichtung zur binären Multiplikation eignet sich zur Anwendung in Rechenmaschinen und Rechenmaschinensystemen, insbesondere in schnellen, spezialisierten Datenverarbeitungseinheiten für numerische Berechnungen, und in anderen schnellen digitalen Einrichtungen, welche arithmetische Operationen realisieren.

Die Summanden werden vorzugsweise im binären Komplementärcode oder im Binärcode mit Vorzeichenbit dargestellt. Die Binärstellen der beiden Summanden werden in einander entsprechende, bestimmte Stellen aufgeteilt. Vorteilhaft ist die Anwendung der Verteilung der Darstellung der beiden Summanden in Binärstellengruppen mit gleicher Stellenzahl »g« der einzelnen Gruppen, und mit eventuell geringen Abweichungen von dieser Regel, wenn die Zahl der Stellen des Summanden nicht durch die angenommene Zahl der Binä.stallen in der Gruppe teilbar ist. Vorzugsweise wird für »g« ein ganzer Wert von 1 bis 4, vorzugsweise von 2 oder 3, angenommen. Dann wird jede; Bitgruppe mit ^-Binärstellen der beiden Summanden, welche abhängig von der Art der binären Darstellung eine der ganzen Zahlen aus dem Bereich von 0 bis +2*⁺¹ — 2 oder von -2*+l bis +2*-1 oder -2^⁺¹+ 2 bis 0 darstellt, eine Bitgruppe zugeordnet, welche eine ganze Zahl aus dem Bereich von —ϊι-^Λ bis 2*-' darstellt, wobei diese Zahl das Vielfache des Multiplikanden als Teilprodukt bestimmt. Für die Summanden im binären Komplementärcod" und im binären Zeichencode für zwei positive Summanden stellen die Bitgruppen, welche die Vorzeichenbits nicht enthalten, Bitgruppen mit zwei Binärstellen für 00 und 00 bis 11 und 11, d. h. die

Zahlen von 0 + 0 = 0 bis 3 + 3 = 6 dar. Jedem der Binärstellenpaare ist eine Bitgruppe zugeordnet, welche eine Zahl aus dem Bereich von -2 bis +2 darstellt. Für die beiden negativen Summanden im binären Zeichencode und für Bitgruppen mit drei Bits pro Gruppe können die Binärstellen den Code 111 und 111 bis 000

und 000 für die Zahlen von (-7) + (-7) 14 bis

0 + 0 = 0 darstellen. Jeder Bitgruppe mit drei Bits je Bitgruppe wird eine Bitgruppe zugeordnet, welche eine ganze Zahl aus dem Bereich von —4 bis +4 ist. Die die ganzen Zahlen aus dem Bereich von -2f-^[ bis +2'-' vertretenden Bitgruppen werden durch eine gleichzeitige und parallele Umwandlung der beiden Summanden gewonnen, damit bei der Änderung des Wertes der einzelnen Bitgruppen sich der Wert des Multiplikators nicht ändert. Der konvertierte Multiplikator wird im Positionscode mit der Basis If durch verschiedene Ziffern 2?+ 1 dargestellt. Es ist dabei nicht wesentlich, ob TU? Rinärstrl|pr>7ahl »g« rinr Konstante für allr Bitgruppen des Multiplikators ist oder für einzelne Bitgruppen unterschiedlich ist. Die Parallelumwandlung der Multiplikator-Bitgruppen wird so durchgeführt, daß bei Vorliegen des binären Komplementärcodes der Summanden zur Bestimmung der Bitgruppe, welche ein Vielfaches des Multiplikanden bildet und die den Bitgruppen der beiden Summanden zugeordneten Zahl des Bereichs von - 2? ' bis + 2? ' ist. maximal drei Bits der Bitgruppen jedes Summanden verwendet werden. Bei einer Binärdarstellung dieser Summanden mit einer Vorzeichenbitgruppe werden außerdem die Vorzeichenbits der Summanden berücksichtigt. Dann werden die die Teilprodukte darstellenden Vielfachen des Multiplikanden ermittelt, wozu man den Multiplikanden oder voneinander verschiedene, vorher gebildete Vielfache des Multiplikanden, und die aus der Multiplikatorumwandlung erhaltenen Bitgruppen, welche die die Vielfachen des Multiplikanden darstellenden Zahlen aus dem Bereich von -2? ' bis +2^^--' sind, verwendet. Für g=\ und g=2 und für die diesen ^•-Werten entsprechenden Vielfachen des Multiplikanden — 1,0, +1 und -2. -1,0, + 1, +2 reicht zur Ermittlung der Teilprodukte nur ein Multiplikand aus, für g=3 und die Vielfachen von -4 bis +4 ist ein verdreifachter Multiplikand, und für g=4 und die Vielfachen von -8 bis +8 ein fünffacher und ein siebenfacher Multiplikand erforderlich. Die geraden Vielfachen des Multiplikanden erhält man durch Verschieben der voneinander verschiedenen Vielfachen um eine entsprechende Binärstellenzahl nach links, die negativen Vielfachen des Multiplikanden durch Negation der Bits der positiven Vielfachen und Addition einer Eins zur gültigen Binärstelle der niedrigsten Ordnung des negierten Vielfachen des Multiplikanden. Die erhaltenen, zueinander verschobenen Vielfachen des Multiplikanden, welche die Teilprodukte darstellen, werden addiert, wobei es vorgezogen wird, parallel gleichzeitig alle Teilprodukte oder gleichzeitig mehrere Teilprodukte zu addieren. Als Ergebnis der Addition der Teilprodukte erhält man das Endprodukt einer mit der Summe aus zwei Zahlen multiplizierten Zahl.

Bei der Umwandlung der Bitgruppen mit £--Bits der beiden Summanden in die die ganzen Zahlen aus dem Bereich von — 2f-' bis +2?-' darstellenden Bitgruppen werden die ausgewählten Bits eines oder der beiden Summanden bzw. deren Teile negiert. Die Negation der Bits. d. h. Umformung der Null-Bits in die Eins-Bits und der Eins-Bits in die Null-Bits wird nach der Konvertierungsregel des Binärcodes in seinen äquivalenten.

binären Komplcmcntärcodc durchgeführt. Nach den Formeln

"σΊι,2' =1-2" -'Wl -<i,)2' -1-2"

-7. i/,2' = - I -2ⁿ + ν (i -_tli) 2'

¹ ι O

+ 1-2"

in können nämlich die Bits </, (i = 0,1 ..., »i—I) des Binärcodes der Zahl

durch ihre Negationen I —a, ersetzt werden, indem gleichzeitig die Wertigkeit dieser Bits von Positiv in Negativ und umgekehrt geändert wird und indem die Zahlencodes durch Korrektureinheiten an den niedrigst- und höchstwertigen Stellen ergänzt werden. Unabhängig von der Negation der Bits der Summanden werden in den ausgewählten Bitgruppen des Multiplikators die die Werte (-1) vertretenden Eins-Bits der höchstwertigen Stellen in der Gruppe gegen die

äquivalenten Eins-Bitgruppen ersetzt, welche Il darstellen, und analog die Werte + 1 gegen 11 nach der Rege',

-1-2'= - 1-2"' + 1-2'

und der Regel

wobei die Bits der Bitgruppc einer Wertigkeit zu den Bits der benachbarten Bitgruppen höherer Wertigkeit gezählt werden. Über den !Ersatz der Einheiten 1 und I der Bits höchster Wertigkeit durch die Bitpaare 11 und

11 entscheiden die Bits der Bilgruppen der Summanden abhängig von den Werten der Bits in benachbarten Bitgruppen geringerer Wertigkeit. Sowohl die Negation der Bits oder der Bitfolgen in den beiden Summanden als auch der Ersatz der höchsten gültigen Eins-Bits in

— t , -

den Gruppen durch die bins-uitpaare π, π wird nach den oben angegebenen Regeln, also ohne den Wert des ganzen Multiplikators zu ändern, durchgeführt. Die so erhaltenen Bits in den Bitgruppen, von welchen jede Bitgruppe eine ganze Zahl aus dem Bereich von — 2f-' bis +2^t- ' darstellt, werden gesondert innerhalb jeder Bitgruppe unter Berücksichtigung der durch einzelne Bits dargestellten Werte und Vorzeichen addiert. Als Ergebnis erhält man eine Folge ganzer Zar'-m im Bereich von —2'-' bis +2?-', welche binär in der geforderten günstigen Form kodiert ist Das Kodieren dieser Zahlen wird bevorzugt, damit den einzelnen ganzen Zahlen von — 2?~' bis + 2^-' mit Ausnahme von Null einzelne Eins-Bits entsprechen, oder damit den Wertigkeiten dieser Zahlen einzelne Eins-Bits entsprechen und die Vorzeichen »Plus« und »Minus« als getrennte Eins-Bits kodiert werden.

Die digitale Einrichtung zur binären Multiplikation weist zwei Register für die Summanden, ein Register für den Multiplikanden, eine Wandlereinheit zur Konvertierung der aus den Summanden-Registern einzugebenden Zahlen, eine Einheit zur Vorbereitung der die zueinander verschobenen Vielfachen des Multiplikanden darstellenden Teilprodukte, welcher der Multiplikand und der konvertierte Multiplikator von der Wandlereinheit zugeführt werden, und eine Einheit zur

Addition der aus der Vorbereitungs-Einheit erhaltenen Teilprodukte des Multiplikanden auf.

Die Wandlereinheit enthalt zur Umwandlung der Summanden niefit direkt miteinander verbundene, parallel arbeitende Schaltungen mit vorzugsweise gleichem logischem Aufbau für die Bitgruppen mit konstanter Bitzahl g der Binärstellen. Direkte Verbindungtif. dienen zur Übertragung von Null- und Eins-Signalen, die in einer Schaltung erzeugt werden, unmittelbar zu einer anderen Schaltung. Jede Schaltung der Wandlereinheiten enthält die Eingänge, welche mit den Ausgängen von nicht mehr als drei aufeinanderfolgenden Bitgruppen der beiden Register der Summanden und eventuell mit den Ausgängen der Vorzeichenstellen dieser Register verbunden sind, z. B. bei einer Binärkodierung mit sieben Vorzeichenbits. Jede dieser Schaltungen konvertiert die Signale, die höchstens drei Bitgruppen jedes Summanden entsprechen und gegebe

diese Addition bestimmten Zeit. Dies ist besonders vorteilhaft bei sehr schnellen digitalen Schaltungen, bei denen bisher die Zeit für die Übertragsänderung bei einer einfachen Addition einen erheblichen Zeitanteil der Multiplikationszeit bildet, d. h. bei Einrichtungen, in welchen gleichzeitig parallel alle Teilprodukte, welche die Summanden des Endprodukts bilden, oder mindestens eine erhebliche Zahl dieser Teilprodukte addiert wird. Ein weiterer Vorteil der Einrichtung ist, daß eine verhältnismäßig kleine Zahl der während der Multiplikation zu addierenden Teilprodukte und eine sehr kleine Zahl von verschiedenen Vielfachen des Multiplikanden zur Bildung der Teilprodukte erforderlich sind. Beispielsweise entspricht bei der Verteilung der Darstellung der Summanden in Bitgruppen mit drei Bits einer Bitgruppe für beide Summanden, also den sechs Bits der Summanden, nur ein Teilprodukt. Zur Bildung jedes dieser Teilprodukte genügt es, außer dem Multiplikan-

mc νυΓ/.ciiiiciiim» uci jiiiiiiiiitnucn. ms

Ergebnis dieser Konvertierung erhält man an den Ausgängen jeder dieser Schaltungen die Signale, die eine das Vielfache des Multiplikanden für ein Teilprodukt bestimmende ganze Zahl aus dem Bereich von — 2*- ' bis +2'-' ist. Vorzugsweise werden Schaltungen mit einem logischen Aufbau verwendet, welche die Erzeugung der Null- und Eins-Ausgangssignale gewährleisten, damit jeder ganzen Zahl mit Ausnahme von Null des Bereichs von —2*-' bis +2?-' ein Eins-Signal des anderen Schaltungsausgangs entspricht oder damit jedem absoluten Wert einer ganzen Zahl außer Null aus dem gegebenen Bereich ein Eins-Signal am anderen Schaltungsausgang, und jedem der Vorzeichen »Plus« und »Minus« ein Eins-Signal am entsprechenden Schaltungsausgang entspricht. Bei einer Ausführungsform der Einrichtung weist die Wandlereinheit zwei oder drei Stufen solcher Schaltungen auf. Die Eingänge dieser Schaltungen sind jeweils mit Ausgängen der Schaltungen der vorangehenden Stufen und/oder mit solchen Ausgängen der Summanden-Register verbunden, so daß die Signale der Ausgänge jeder Schaltung der letzten Stufe, welche eine das Vielfache des Miiltinlikanrlpn für ein Teilprodukt bestimmende Zahl liefern, durch die Ausgangssignale von höchstens drei aufeinanderfolgenden Binärstellengruppen bzw. Bits des Summanden-Registers und eventuell von den Ausgangssignalen der Vorzeichenstellen der beiden Register (z. B. im Binärcode mit Vorzeichenbit) bestimmt sind. Die Anwendung von zwei oder drei Stufen von Schaltungen ermöglicht eine Vereinfachung des logischen Aufbaus der Wandlereinheit. Die nicht miteinander verbundenen Schaltungen, die den benachbarten Binärstellengruppen des Multiplikators zugeordnet sind, weisen untergeordnete Schaltkreise auf, welche dieselbe Logikfunktion realisieren. Die Trennung der Schaltungen in Schaltungsstufen ermöglicht eine wesentliche Vereinfachung der Wandlereinheit. Eine weniger sparsame Schaltungsanordnung wird dann angewandt, wenn es wichtiger ist die Wirkungszeit der Wandlereinheit zu verkürzen und die Zahl der Stufen der Logikelemente zu vermindern, anstelle die Gesamtzahl dieser Elemente und die Kosten der Wandlereinheit zu reduzieren.

Die binäre Multiplikation einer Zahl mil einer Summe aus zwei Zahlen mit der digitalen Einrichtung ermöglicht eine sehr schnelle Summenmultiplikation durch sehr schnelle Addierer. Dabei wird eine effektive Addition vor der Multiplikation vermieden, d. h. eine Übertragserhöhung oder -änderung während der durch tfUI ULII

IVIUIllL/lll\ailULII

und zu speichern. Durch Verschiebung und Negation der Bits des Multiplikanden können neun aufeinanderfolgende Vielfache des Multiplikanden, ausgedrückt mit den ganzen Zahlen -4, -3, -2, - 1,0, + 1, +2, +3, +4, erhalten werden. Bei Bitgruppen mit jeweils zwei Bits ergeben sich entsprechend die Vielfachen des Multiplikanden aus den ganzen Zahlen -2. -I₁ 0, +1. +2. Diese Vielfachen können durch Verschiebung und Negation des Multiplikanden in Binärdarstellung, d. h. des Einfachen des Multiplikanden, erhalten werden.

Im folgenden wird eine bevorzugte Ausführungsform der Einrichtung anhand der Zeichnung näher erläutert. Es zeigt

F i g. 1 ein Blockschaltbild der Einrichtung,

F i g. 2 ein Blockschaltbild der Wandlereinheit,

Fig. 3 eine Abwandlung der in Fig. 2 gezeigten Wandlereinheit und

F i g. 4a, 4b die logische Schaltung einer Schaltung mit der Funktion Di*

Eine digitale Einrichtung zur binären Multiplikation wird nachstehend anhand eines Zahlenbeispiels erklärt, in welchem die einzelnen Schritte der binären Multiplikation einer Zahl mit einer Summe au·; 7wpi Zahlen angegeben sind. Die Konvertierung von zwei Summanden in eine Folge von ganzen Zahlen aus dem Bereich von -2<-' bis +2?-' wird für Bitgruppen mit jeweils zwei Bits, d. h. für die ganzen Zahlen von - 2 bis + 2 beschrieben.

Im folgenden wird angenommen, daß der Multiplikand die Summe aus zwei Summanden »a« und »b« darstellt, wobei ein Summand des Multiplikators a = + 688, und der zweite Summand des Multiplikators b — — 783 ist. Diese Zahlen haben im binären Komplementärcode folgende Form:

« = 01010110000 +688
/>=10011I1000! -783

Die Binärstellen der beiden Summanden werden gleichmäßig in bestimmte Gruppen mit gleicher Stellenzahl g=2 aufgeteilt. Man erhält den Multiplikatorcode

1 0
0 0

1 0
1 1

1 1
1 1

0 0 0 0

0 0 0 1

in welchem die nachfolgenden Bitgruppen aus den beiden Summanden die ganzen Zahlen

-l,+2,+5,+6,0,+1

sind. In jeder Bitgruppe jedes Summanden entspricht die niedrige Stelle dem Wert 2° und die höhere Stelle dem Wert 2'; die der höchsten Binärstelle entsprechende Bitgruppe definiert ein negatives Vorzeichen für die Summe, wenn ein Bit dieser Bitgruppe eine »1« ist. In dem hier angenommenen Zahlencode, und zwar im binären Komplementärcode, sind, außer dem ersten Bitpaar von links, welche die Vorzeichen sind, die restlichen Bitgi-uppenpaare die ganzen Zahlen aus dem Bereich von 0 bis + 2^⁺¹-2, also für g=2 aus dem Bereich 0 bis 6. Die angegebene Folge von ganzen Zahlen drückt den Multiplikatorwert in der Darstellung mit der Basis 2^ = 4, d. h. im Vierercode nach der Formel

-1 ■4^ί + 2·4⁴ + 5·4' + 6·4-' + 0·4^ι + 1 ·4" = -95
aus, was dem angenommenen Wert des Multiplikators
a + b = +688-783 = -95

entspricht.

Die Bitgruppen werden jetzt in die Zahlen aus dem Bereich von -2? ' = -2 bis + 2' ' = +2, welche die Vielfachen des Multiplikanden ausdrücken werden, darstellenden Bitgruppen konvertiert. Diese Umwandlung wird derart ausgeführt, daß sich der Wert des ganzen Multiplikators nicht ändert. Beim Binärkomplementärcode kann sich z. B. eine solche Konvertierung aus den zwei nachstehend beschriebenen Operationen ergeben. Die erste dieser Operationen ist die Negation des Vorzeichenbits des Summanden »a« und aller Bits des Summanden »b«, wobei die Konvertierung des Binärcodes in sein binäres Komplement erfolgt und wobei die Subtraktion einer zusätzlichen Eins an der niedrigwertigsten Stelle erforderlich ist. Nach dieser Operation nehmen die Bitgruppen der Multiplikatorsummen folgende Form an

,/ \ h = I I 1 ();l 0:1 I |0 OiO Oj f

IiI 1 0 ()!() Oil hl ()| - (Operation I I

Die erste Bitreihe gibt die positiven Werte und die zweite und dritte Bitreihe die negativen Werte wieder.

lvic entbeinen Ljitgi υμμν-ιι υιιΐ3μι ut-iiiii ut.il gciii/.\,n Zahlen

0, -1, +2, +3, -3, -3

welche im Vierercode dem Multiplikatorwert

0·4~> - 1 ·4⁴ + 2·4> + 3-4- - 3-4' - 3-4"

-95

Ziffern I höherer Wertigkeit (2¹) in den Bitgruppen, wenn der Inha!'. der zwei benachbarten Binärstellen geringerer Wertigkeit positiv ist. In dem Beispiel genügen dieser Bedingung alle vier der mit Kreisen versehenen Bits. Diese Bits werden durch Eins-Paare mit verschiedenen Vorzeichen ersetzt, welche nachfolgend angegeben und mit Kreisen versehen sind:

entsprechen.

In einer übersichtlicheren Form kann der Multiplikator a + b durch mit Vorzeichen versehene Einsen und Nullen folgendermaßen wiedergegeben werden:

i/ + h = OjO IM Oil I; I IjI 0 (Operation 2)

Die zweite Operation besteht im Ersatz von den die

Werte 1 und 1 darstellenden Eins-Bits höchster

Ordnung in den Bitgruppen durch äquivalente Eins-Bit-

-1- '
paare 11 und 11, wonach die Bits gleicher Wertigkeit

bzw. gleicher Bitstelle addiert werden. Die Ziffern ' mit höherer Wertigkeit (2^!) in den Bitgruppen werden ersetzt, wenn der Inhalt der zwei benachbarten Binärstellen niedriger Wertigkeit negativ ist, und die + h = 0

I
I 1

1
I I

(Operation 3)

Dadurch wird eine Änderung des Inhalts der einzelnen Multiplikatorstellengruppen erreicht und man erhält in jeder Gruppe die ganzen Zahlen aus dem Bereich -2f ' = - 2 bis + 2*' ' = + 2. Der vorstehend angegebene Multiplikatorcode kann auch als

b = oll) 0 Io ill 0 Io olo ί (Operation 4)

dargestellt werden, wobei die nacheinanderfolgenden Gruppen die ganzen Zahlen

0. 0, -1, -2. 0, +1

sind, deren Folge im Vierercode den Multiplikatorwert 0 . 4^; + 0 ■ 4¹- 1 · 4'-2 ■ 4- + 0 · 4¹ + 1 · 4"= -95

darstellt.

Die parallele Umwandlung der Bitgruppen der Summanden wurde so durchgeführt, daß bei der Ermittlung des der gegebenen Bitgruppen aus den beiden Summanden zugeordneten Vielfachen des Multiplikanden die Bits ausgenutzt wurden, welche höchstens drei aufeinanderfolgenden Bitgruppen eines Summanden zugeordnet sind, was ein für die Erfindung

wesentliches Merkmal ist. Den Ersatz des Bits 1 durch das Paar 11 und des Bits I durch das Paar 11 bestimmen die zwei Binärstellen höherer Ordnung bzw. Bits, wobei

das hintere Bit (d. h. 1 bzw. 1) der 11-, 11-Paare an die Stelle des ausgewählten Bits höherer Ordnung gesetzt

■.j r-v 1_ i__ j:_ n:»_ _i~:-.L~.. /"Λ-J

innerhalb jeder Bitgruppe addiert. Der Wert der Bitgruppen ist dann wie folgt:

0, 0, -1, -2, 0. +1

Die vorstehend angegebenen Zahlen, die anschließend im Binärcode (Operation 4) dargestellt werden, stellen die ganzen Vielfachen des Multiplikanden dar, welche zur Ermittlung eines Vielfachen des Multiplikanden für die einzelnen Teilprodukte dienen. Diese Vielfachen des Multiplikanden werden derart ermittelt, daß den positiven Zahlen +1 bzw. +2 der Multiplikand bzw. der um eine Binärstelle nach links verschobene Multiplikand, und den Zahlen - 1 bzw. —2 die Negation des Multiplikanden bzw. die um eine Stelle nach links verschobene Negation des Multiplikanden zugeordnet wird, wobei bei der Negation des Multiplikanden die Addition einer Korrektur-Eins auf der gültigen Multiplikandenstelle der niedrigsten Ordnung erforderlich ist Der Bereich der Vielfachen des Multiplikanden von — 2*-' bis +2*-', welcher in dem besprochenen Beispiel, d.h. für g=2, die Zahlen -2, -1, 0, +1, +2 umfaßt, macht die Berechnung von aufeinanderfolgenden, voneinander verschiedenen Vielfachen des Multiplikanden nicht erforderlich, was bei der Berechnung des dreifachen Multiplikanden für g= 3, d. h. bei drei Bits

innerhalb jeweils einer Bitgruppe, erforderlich ist. Wenn der Multiplikand c = +1000 ist und im binären Komplementärcode die Form

c=0 1 1 1 1 10 1 0 0 0

hat, werden die drei die Teilprodukte darstellenden Vielfachen des Multiplikanden addiert, welche den drei vorher erhaltenen, nicht Null darstellenden Bits des Multiplikanden a+b entsprechen, wie nachfolgend angegeben ist.

(i]_h_= ο ο ο_(ο Πι ο ο ο|ο ι
ι οοποο Ί οι ι

I
1 i O 0 0 0 0 I 0 I I 1 erscheinen, daß das Eins-Signal eines der vier Ausgänge einer der Zahlen -2, —1, +1, +2 entspricht. Diese Schaltung D₂, ist nachstehend in Form von Booleschen Gleichungen beschrieben, welche gleichzeitig die Signale fit¹, AV, /Yi¹, /Yi²als Funktion der Zustände der

Ausgänge a₂,_₃, fc/-j, a₂,_₂, bu-i a_2/r;, bn+\ der

Register A, B darstellen. Diese Booleschen Gleichungen haben folgende Form:

; — (ijhj,Zj — cii

bjj — 0,1,2...

^r2, = ^V2, I '.'·;, !»-;■ 2 V₂, ., V -2i 2 -Ii .\)

— ^r2i V ^U2, V ^:2,

0 0 0 0 0 0 0 0 0 Ol I MlOI 0 0 0

1 I 1 0 1 0 0 0 I 10 0 IM 0 I CIO 0

Die aufeinanderfolgenden Summanden der Addition gemäß vorstehender Tabelle sind eine Multiplikandennegation, eine Korrektur-Eins, eine Multiplikandennegation, eine Korrektur-Eins und ein nicht negierter Multiplikand. Die Vielfachen des Multiplikanden, welche den Nullgruppen der Multiplikatorbits entsprechen, sind nicht dargestellt. Mit Pfeilen sind in vorstehender Darstellung die gültigen Ziffern der niedrigsten Ordnung der den Bits des umgewandelten Multiplikators entsprechenden Vielfachen gezeigt. Die als Ergebnis erhaltene Binärzahi stellt im binären Komplementärcode die Zahl -95 000 dar, welche das Ergebnis der Multiplikation des Multiplikanden c = 1000 mit der Summe der Multiplikatorsummanden a = + 688 und b = -783 ist.

Eine Ausführungsmöglichkeit der Einrichtung zur Binärmultiplikation einer Zahl mit einer Summe aus zwei Zahlen ist in Fig. I gezeigt. Die Einrichtung enthält zwei parallele Multiplikatorsummanden-Register A, B, ein paralleles Multiplikanden-Register C, eine Wandlereinheit D zur parallelen Umwandlung der von den Registern A, B erhaltenen Multiplikatorsumman-

I U₂,-ι V :_2l-2

, -2, ι ν

j„_ „: r?:_u^:» η D :.„.~h

'/2, = .V₂₁-I(V₂,- _{2 v}r,,_, y₂, ₂)

ν '■:, μ v₂, /i,, v-v₂,m V₂, />:■

/2," = (V₂, _M V V₂, M l^r2, V2, I V .*'>,"M V-2.M V₂, '/2, VV₂, ., V₂, (/,,

lii' Iv₂, μ _v V₂,., I Iv₂, C₂, ν r₂, (/,,I ν r_{2l M} (ν-,, r·., ν r-,, /),,)

/2,' = (-V₂₁M ν V₂, · 111 v₂, r₂, _vr₂,/i₂,|

^vr2, M (V₂, ''2, ^{v r}2, </₂i)V

mit /= 0, 1. 2.3,... Mit ν sind in den obigen Booleschen Gleichungen die Disjunktionen, d. h. die diesen Summen entsprechenden ODER-Glieder angegeben. Die waagerechten Striche über den Buchstaben geben die Negationen an. Die Produkte und die entsprechenden UND-Glieder sind in den vorstehenden Gleichungen als einfache Produkte in algebraischen Ausdrucken dargestellt. Alle tiefgestellten Indizes entsprechen den Nummern der Binärstellen des Multiplikators. Die

verschobenen Vielfachen des Multiplikanden darstellenden Teilprodukten, welcher der Multiplikand aus dem Register Cund der transformierte Multiplikator aus der Einheit D parallel zueinander zugeführt werden, und eine Einheit S. welche parallel gleichzeitig alle von der Einheit ^enthaltenen Teilprodukte addiert.

Die Wandlereinheit D zur Umwandlung der Summanden, welche miteinander nicht direkt verbundene Schaltungen aufweist, ist teilweise in Fig. 2 dargestellt. Diese Einheit D enthält vier aufeinanderfolgende, den vier aufeinanderfolgenden Paaren der Doppelstellengruppen der Binärstellen der Multiplikatorsummanden zugeordnete gleiche Schaltungen D₀, Di, D4, Ds. In F i g. 2 sind mit ao, bo, a\, b\,..., ai, b, die entsprechenden Ein-Bit-Eingänge der acht aufeinanderfolgenden Binärstellen der Register A, B, beginnend mit den Stellen höherer Wertigkeit, und mit üb, J₂, d», d_b die Eingänge der parallelen Schaltungen D₀, D₂. D₄, D₁, angegeben. Jede Schaltung D₂/ mit / = 0, 1, 2, 3 hat einen solchen logischen Aufbau, daß infolge der von den Ausgängen a₂i-i, bii-i, a₂i-2, 62,-2,··-.a_2l>i der Register Λ Banden Eingängen der Schaltung angelegten Null-Eins-Signale an den vier Ein-Bit-Ausgängen, welche mit einer gemeinsamen Bezeichnung d₂i / = 0, 1, 2, 3 dargestellt sind, solche Null- und Eins-Signaie /V,², fn\ /7,', fi,¹

·~ιιικαιικν.

haben einen konstanten Zustand im 0-Zustand Logikschaltungen, die das Signal v. erzeugen und einen Teil der Schaltung D₂ bilden, sind in Fig. 4a und 4b dargestellt. In Fig. 4a ist die Schaltung für die vorstehend angegebene Gleichung der Booleschen Funktion r₂, gezeigt, in F i g. 4b die Schaltung für dieselbe Gleichung für die Funktion v₂, nach der Multiplikation der in dieser Gleichung in Klammern angegebenen Ausdrücke mit A₂,- ;. Mit den Zahlen von 1 bis 6 sind der Reihe nach die Eingangssignale V₂, .._\; .-, Z21-2,>'.'/-}, Z21-1 und das Ausgangssignal v₂, bezeichnet. Mit den Zahlen von 7 bis 12 sind die UND-Glieder und mit den Zahlen 13,14 die ODER-Glieder bezeichnet.

Bei einer abgewandelten Ausführungsform der Wandlereinheit D sind nach F i g. 3 die vier aufeinanderfolgenden gleichen Schaltungen der ersten Schaltungsstufe mit Do, Di, Di, Dri und die vier aufeinanderfolgenden gleichen Schaltungen der zweiten Schaltungsstufe mit Dn, Di, Dx, D" angegeben. Bei dieser Wandlereinheit D sind die in jeder Schaltung der ersten Stufe erzeugten Signale, welche den vorstehend angegebenen logischen Funktionen x_h y,. z, mit j — 0, 1, 2, 3, ... entsprechen, zweimal in den zwei benachbarte;; Schaltungen der zweiten Stufe verwendet.

Jede Schaltung der ersten Stufe erzeugt die Signale

D2i(i = 0,1,2,3), welche die Werte der elf Funktionen yit, Z2h -Vj₁+ 1, .V'2,+ I,

₊I, H'3,+ 2, ρ?,,_Ύ2, φ,+ Λ Γι,ν ι

liefern. Die sechs ersten Funktionen werden durch die Signale dargestellt, welche durch eine parallele Sechs-Bit-Verbindung d it in den zur zweiten Stufe gehörenden Schaltkreis D ί'* Obertragen werden und die sechs letzten Funktionen, einschließlich der Funktion zj +ι, werden durch die Signale dargestellt, welche durch eine parallele Sechs-Bit-Verbindung d'i, in den benachbarten Schaltkreis Di'i+ider zweiten Stufe übertragen werden. Auf dem Vier-Bit-Ausgang du der Schaltung D ü der zweiten Stufe werden analog vorstehender Beschreibung die Signale /Yi², /Yi¹, /Yr, fff erhalten. Der logische Aufbau der einzelnen Schaltungen der beiden Schaltungsstufen ergibt sich durch die beschriebenen logischen Funktionen für die betreffenden Schaltungen. Mit drr beschriebenen Einrichtung läßt sich die binäre Multiplikation einer Zahl mit einer Summe aus zwei Zahlen ausführen, bei welcher die Teilprodukte addiert werden, welche die zueinander verschobenen Vielfachen des Multiplikanden darstellen und den Gruppen von Binärstellen des Multiplikators mit bestimmter Stellenzahl in jeder Gruppe zugeordnet sind, inüem der durch zwei Summanden im Binärcode ausgedrückte Multiplikator parallel, ohne effektive Addition dieser 2^ Summanden, in einen Positionscode mit einem zu Null symmetrischen Ziffernbereich so umgewandelt wird, daß die Binärstellen des Multiplikators der beiden Summanden des Multiplikators in bestimmte, einander entsprechende Gruppen aufgeteilt werden, vorzugsweise in die Gruppen mit gleicher Stellenzahl »g«, wobei »g« einer der ganzen Werte 1 bis 4 ist, daß dann jeder g-Bits enthaltenden Bitgruppe der beiden Summanden derselben Gruppe der Binärstellen, die abhängig von der Art des Binärcodes eine der ganzen Zahlen aus dem Bereich von 0 bis 2*+ '-2 oder von -2?+ I bis 2f- 1 oder von — 2?⁺ ' + 2 bis 0 ist, eine Bitgruppe zugeordnet wird, welche eine der ganzen Zahlen aus dem Bereich von — 2*-' bis 2*-' entsprechend dem Vielfachen des Multiplikanden für ein Teilprodukt darstellt, was durch gleichzeitige und parallele Umwandlung der Bitgruppen der beiden Multiplikatorsummanden erreicht wird, damit bei der Änderung der Werte der einzelnen Bitgruppen der Wert des ganzen Multiplikators unverändert bleibt Diese parallele Umwandlung wird so durchgeführt, daß zur Ermittlung einer Zahl aus dem Bereich von —2*-' bis 2'-', welche das betreffende Vielfache des Multiplikanden darstellt, die Bits ausgenutzt werden, die höchstens drei Binärstellen jeder Bitgruppe der Summanden bei Vorliegen des binären Komplementärcodes zugeordnet sind. Außerde.n werden die Vorzeichenbits der Summanden im Falle des Binärcodes dieser Summanden mit Vorzeichenbit berücksichtigt Bei der Umwandlung der Bitgruppen der beiden Summanden des Multiplikators in die die ganzen Zahlen aus dem Bereich von — 2e ' bis +2*-' darstellenden Bitgruppen werden die ausgewählten Bits aus einem oder aus beiden Summanden des Multiplikators bzw. deren Teile negien, wobei die Regel der Umwandlung des Binärcodes in das äquivalente binäre Komplement befolgt wird, und/oder es werden in den ausgewählten Bitgruppen des Multiplikators die die

Werte Ϊ auf den höchsten gültigen Stellen in der Gruppe darstellenden Eins-Bits durch 11 und die Werte 1 durch

11 nach der Regel

und der Regel

+ 1·2'= +1-2·"+' —1-2'"

ersetzt, wobei die Bits höheren Werts in den Bitpaaren zu den benachbarten Stellen höherer Wertigkeit gezählt werden.

Hierzu 4 Blatt Zeichnungen

Claims

Patentansprüche:

1. Digitale Einrichtung zur binären Multiplikation einer ersten Zahl als Multiplikand mit einer den ί Multiplikator ergebenen Summe aus einer zweiten und dritten Zahl im Binärcode, welche zwei parallele Register für die die Summe bildenden zweiten und dritten Zahlen als Summanden und ein Register für den Multiplikanden aufweist, dadurch gekennzeichnet, daß eine Einheit (P) zur Bereitstellung von Teilprodukten und eine Einheit (S) zur Addition der Teilprodukte vorgesehen sind, daß die Register (A, B) für die Summanden (a, b)dts Multiplikators an eine VVandlereinheit (D) angeschlossen sind, welche parallel die Summanden (a, b) in Bitgruppen zur Darstellung ganzer Zahlen im Bereich —2*-' bis +2^-' umwandelt, wobei g = 1 bis 4 ist und die ganzen Zahlen die Ziffern eines Positionscodss mit der Basis 2« darstellen und die zur m Erzeugung der Teilprodukte erforderlichen Vielfachen des Multiplikanden bilden, wobei die Wandlereinheit (D) parallelen Aufbau zur Zuführung der Bits der beiden Summanden (a, b) in identischen ^■-Bitgruppen und zur Zuordnung eines einander entsprechenden Bitgruppenpaares der beiden Summanden (a, b) jeweils einer eine ganze Zahl des Bereichs — 2*-' bis +2*-' darstellenden Bitgruppe hat, wobei in der Wandlereinheit (D)zur Bildung von eine ganze Zahl des Bereichs -2«-' bis +2*-' so darstellender. Bitgruppen höchstens drei Bits innerhalb einer Bitgruppe jedes Summanden (a, b) verwendet werden, w,enn d.-jse Summanden im binären Komplementän-orfe dargestellt sind und zusätzlich die Vorzeichenbits de Summanden (a, b) j3 berücksichtigt werden, wenn die Summanden im Binärcode mit Vcrzeichenbit dargestellt sind.

2. Einrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Umwandlung der Summanden (a,

b) in der Wandlereinheit (D) durch Negation -to ausgewählter Bits der Summanden und Umwandlung der Binärcodes in das äquivalente binäre Komplement (Operation 1) und durch Ersatz der

Werte 1 bzw. 1 bestimmter Bitgruppen des 4> Multiplikators (a + b) an den Stellen höchster

Ordnung durch äquivalente Wertpaare 11 bzw. 11 nach der Regel

-1-2." 1-2-. + 1-2-

(Operation 3) erfolgt, wobei die Werte höherer Wertigkeit jedes Wertpaares zur benachbarten Bitgruppe höherer Ordnung hinzugezählt werden (Operation 4).

3. Einrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Wandlereinheit (D) nicht miteinander verbundene, parallele Schaltungen (Do, Di, D^ Dh) aufweist, wobei jede dieser Schaltungen Eingänge hat, die mit den Ausgängen von höchstens drei Bitgruppen innerhalb der beiden Summanden-Register (A, B), wenn die Summanden im binären Komplementärcode dargestellt sind, und außerdem mit den Ausgängen für die Vorzcichensteilen dieser Register verbunden sind, wenn die Summanden im Binärcode mit Vorzeichenbit dargestellt sind, wobei jede- Schaltung die Signale von höchstens drei

wi Bitgruppen jedes Summanden und gegebenenfalls der Vorzeichenbits transformiert und Ausgangssignale liefert, welche ein Vielfaches des Multiplikanden eines Teilprodukts darstellen.

4. Einrichtung nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die Wandlereinheit (D) zwei oder drei Stufen aufeinanderfolgender Schaltungen (D'ü, D'₂, D'_M D't und D'O, D"₂, D\ D'%) aufweist, deren Eingänge mit den Ausgängen der Schaltungen der vorangehenden Stufen und/oder mit den Ausgängen der Register (A, B) für die Summanden (a, b) verbunden sind, daß die durch die Ausgänge der Schaltungen abgegebenen Signale der Schaltungen (D"o, D"i, D"₄, D"₆) der letzten Stufe, die eine das Vielfache des Multiplikanden für ein Teilprodukt bestimmende Zahl liefert, durch die Ausgangssignale von höchstens drei Bitgruppen jedes Summanden-Registers bei Darstellung der Summanden im binären Komplement und außerdem von Ausgangssignalen der Vorzeichenpositionen bei Darstellung der Summanden im Binärcode bestimmt sind.

5. Einrichtung nach Anspruch 2, dadurch gekennzeichnet, daß zur Umwandlung der Summanden (a, b) in Bitgruppen zur Darstellung ganzer Zahlen im Wandler (D) zuerst das Vorzeichen eines Summanden (a) positiven Werts negiert und der Binärcode eines negativen ,Summanden (b) mit Ausnahme der Vorzeichenbits negiert werden, wobei an der Bitstelle niedrigsten Werts ein Korrekturzeichen-Bit 1 hinzugefügt wird (Operation 1), daß die Bits des zweiten Summanden (b) von den Bits des ersten Summanden subtrahiert werden und daß die sich

daraus ergebenden Werte 1,0,1 sind, daß die Werte

f - f

1 bzw. 1 dieser Bitstellen durch das Zahlenpaar 11

bzw. 11 ersetzt werden, wobei die vordere Zahl des

Zahlenpaares 11 bzw. 11 an die Bitstelle geringerer Wertigkeit in der vorangehenden Bitgruppe gegen-

über dem ausgewählten Wert 1 bzw. 1 gesetzt wird

(Operation 3).

6. Einrichtung nach Anspruch 5, dadurch gekenn-

_ t-

zeichnet, daß nach dem Ersatz der Werte 1 bzw. 1

durch die Zahlenpaare 11 bzw. 11 die Werte gleicher Bitstellen addiert und die erhaltenen ganzen Zahlen für -2*-' bis +2*-' im Binärcode dargestellt werden (Operadon 4), duß in der Einheit (P) zur Bereitstellung der Teilprodukte die durch die Binärcode-Darstellung erforderlichen Teilprodukte gebildet und in der Additions-Einheit (S) addiert werden.

7. Einrichtung nach Anspruch 6, dadurch gekennzeichnet, daß bei der Bereitstellung der Teilprodukte in der Einheit (P) abhängig von den Zahlen des Bereichs —2*-' bis +2*-' der Binärcode des Multiplikanden (c) dargestellt und/oder verschoben und/oder unter Addition eines Korrekturbits negiert v/ird.