DE2017132A1 - Binarer Parallel Addierer - Google Patents

Description

BURROUGHS CORPORATION, eine Gesellschaft nach den Gesetzen des Staates Michigan, 6071 Second Avenue, Detroit. Michigan (V.St.A.)

Binärer Parallel-Addierer

Die Erfindung betrifft einen binären Parallel-Addierer, der zu zwei in je einem Eingangsregister enthaltenen Summanden über eine Zwischenstufe .die binäre Summe in ein Ausgangsregister speichert. Sie befaßt sich mit einem extrem schnell arbeitenden Parallel-Addierer, der für alle Größenordnungen bzw. alle Binärstellen der zu addierenden Summanden gleichzeitig den Übertrag erzeugt.

Bei Paralleladdierern werden alle Binärstellen eines ersten und eines zweiten Summanden parallel am Eingang aufgenommen und sämtliche Summenbits parallel am Ausgang erzeugt. Dabei muß Vorsorge für das Weiterleiten einer Übertraginformation von einer niedrigen Binärstelle der Summe zur nächsthöheren Binärstelle getroffen werden. Im allgemeinen wird dieses Weiter-

009885/1883

leiten durch eine Übertragschaltung besorgt, bei der die an der untersten Bitstelle erzeugte Übertraginformation schrittweise bis zur höchsten Bitstelle des Addierers weitergegeben wird. Diese Weiterleitung des Übertrages erfordert jedoch Zeit, und die sich ergebende Verzögerung ist kumulativ, so daß einem Addierer genügend Arbeitszeit gelassen werden muß, die im wesentlichen durch diejenige größte Zeitspanne gegeben ist_f die für das Weiterleiten eines Übertrages durch sämtliche Stelle des Addierers benötigt wird.

Zur Beschleunigung ihres Arbeitsablaufes wurden Parallel-Addierer vorgeschlagen, bei denen der Übertrag mit Hilfe einer sogenannten "bedingten Summe" ("conditional sum") gewonnen wird. Dabei wird eine Summe mit einem Übertrag und ohne einen Übertrag für jede Stelle erzeugt und mit Hilfe einer Übertragsinformation aus den niedrigeren Stellen eine Auswahl getroffen. Eine dritte Art von Parallel-Addierern arbeitet mit einer sogenannten "vorausschauenden" Übertraglogik, bei der die Übertraginformation für alle Stellen des Addierers gleichzeitig erzeugt wird. Wegen der betrachtlichen Kompliziertheit einer hierfür geeigneten Übertragschaltung konnte dieser "Vörwärts-Typ" bislang noch nicht für solche Addierer eingesetzt werden, die eine beträchtliche Anzahl von Bitstellen verarbeiten« Es sind verschiedentliche Hilfseinrichtungen benutzt worden, die den fortlaufenden Übertrag mit dem gleichzeitigen Übertrag kombinieren, um die gesamte Arbeitszeit der nach dem Prinzip des fortlaufenden Übertrags arbeitenden Addierer zu reduzieren und die sich aus dem gleichzeitigen Übertrag ergebende Kompliziert-

009885/1888

heit der Schal tuna zu beschränken.

Die vorliegenden Erfindung befaßt sich mit Parallel-Addierern zur Addition von Summanden, die eine sehr qroße Anzahl von Bits, beispielsweise 48 BinMrbits, enthalten. Der Addierer fsrzielt eine außerordentlich hohe Arbeitsgeschwindigkeit dadurch, daß das Prinzip des gleichzeitigen Übertrags in einer neuartigen Schaltung realisiert wird, die gegenüber den bislang bekannten Schaltungen den Vorzug wesentlicher Einfachheit besitzt. Neben der gleichzeitigen Erzeugung des Übertrags, bei der der Übertrag für die hohen Bitstellen in der gleichen Zeitspanne wie der Übertrag für die niedrigen Bitstellen erzeugt wird, erreicht die erfindungsgemMße Addierschaltung die hohe Arbeitsgeschwindigkeit auch durch Eliminieren solcher Schaltungskomponenten, die aus einer Arbeitsstellung in eine Ruhestellung zurückgestellt werden müssen, beispielsweise also Flip-Flops, Umkehrstufen oder Pufferschaltungen. Es werden lediglich Torschal tuncen, also nicht rücksteliende 5! wen te _c benutzt. Diese Tnrschaltungen bringen eine Verzögerung von nur drei Nanpsekunden, wohingegen Umkehrstufen und Puffer Zeitverzögerunqen in der Größenordnung von 17 - 23 Nanosekunden besitzen. Die erfindungsgemäße Torlogik ist ferner so angeordnet, daß höchstens vier Tore kasksdenförmig zwischen dem Eingang und dem Ausgang des Addierers einschließlich der zugehörigen Übertraglogik in Reihe liegen; damit stellt sich die größtmögliche Zeitverzögerung zur Bildung der Binärsumme einschließlich des Übertrags für alle Bits auf 12 Nanosekunden.

Der erfindungsqemäße Schnei1 addierer ist baukastenartig aufgebaut, was für seinen schnellen Betrieb

00988571888

BAD ORiQINAL

günstig ist. Für je vier Bitstellen ist ein Unteraddierer vorgesehen, so daß insgesamt 12 Unteraddierer vorhanden sind. Die Übertragschaltung zur Erzeugung des gleichzeitigen Übertrages besteht aus drei kaskadenartigen Stufen, die die Übertragsignale jedem Unteraddierer gleichzeitig zur Verfügung stellen. Die erste Stufe der Übertragschaltung weist mehrere Abschnitte auf, von denen jeder an zwei Bitstellen der Summanden angeschlossen ist. Die zweite Stufe hat nur halb soviele Abschnitte, von denen jeder die Ausgänge von vier Abschnitten der ersten Stufe ' aufnimmt. Die Abschnitte der zweiten Stufe sind in ^ zwei Gruppen gegliedert, in eine ungeradzahlige und

in eine geradzahlige Gruppe, wobei sich die Verbindungen zwischen den Abschnitten der ersten Stufe und den entsprechenden Abschnitten der bei—den Gruppen der zweiten Stufe überlappen. Die dritte Stufe weist schließlich zwei Abschnitte auf, von denen jeder mit eir.fr· der beiden Gruppen aus der zweiten Stufe in Verbindung steht. Die beiden Abschnitte der dritten Stufe liefern für jeden Unteraddierer ein eigenes Übertragsignal, wobei die Übertragssignale aus den Abschnitten in Bezug auf die Stelle der Unteraddierer verkettet sind.

fc Die drei Stufen der Übertragschaltung und die Unteraddierer sind so miteinander verknüpft, daß sich nicht mehr als vier Tore in Kaskade zwischen dem ■in gang und dem Ausgang ergeben und keine rückstellenden Einheiten die Übertragungszeit vom Eingang zum Ausgang verzögern. Um ohne Umkehretufen au«zukommen, ist die gesamte Schaltung in zwei parallelliegende Teile gegliedert, von denen der eine der wahren und der andere der falschen Logik zugeordnet 1st· Oie Sumne am Ausgang der Unteraddierer wird in ein Ausgangsregister in weniger als einer Taktperiode ein-

009885/1888

geschrieben, die auf das Einschreiben der beiden Summanden in das Eingangsregister folgt.

Die Erfindung wird nachstehend an einem Ausführungsbeispiel mit Bezug auf die beigefügten Zeichnungen beschrieben. Es zeigt:

Fig. 1 ein Blockdiagramm des erfindungsgemäßen Addierers mit der dreistufigen Übertragschaltung ;

Fig. 2 die Schaltung eines speziellen Kleinstell enaddierers.;

Fig. 3 die Schaltung eines Abschnittes der

ersten Stufe aus der Übertragschaltung;

Fig. 4 die Schaltung eines Abschnittes aus der zweiten Stufe der Übertragschaltung;

Fig. 5 die Schaltung der dritten Stufe der Übertragschal tung ;

Fig. 6 die Schaltung eines Unäeraddierers; und

Fig. 7 das Blockschaltbild zur Erläuterung der Funktionsweise eines Unteraddierers*

Aus Fiq. 1 ist das Baukastenprinzip des erfindungsgemäßen Addierers zu erkennen. Das Einganqsreqister 10 nimmt den ersten Summand über die mit A bezeichneten paralleln Einqanqsleitunqen bei Vorlieqen eines Taktimpulses CP auf. In einer bevorzuqten Ausführunqsform der Erfindunq bestehen die Operanden aus 48 Bits. Ein ähnliches zweites Einqanqsreqister. 12 speichert die binären Bits des über die parallelen Einqanqsleitunqen BB aufgenommenen zweiten Summanden. Ein einzelnes Flip-Flop 14 speichert die über die Einqanqsleitunq Cj aufgenommene Übertraq-Information, Die Aus-

009885/1888

— ο —

gangssignalpegel aus den Registern 10 und 12 sowie dem Übertrag-Flip-Flop 14 werden auf eine Übertrag-Logik 16 und ein Addierwerk 18 gegeben. Das Addierwerk 18 verknüpft den Ausgang der Übertraglogik mit der Information aus den Registern 10 und 12 und liefert die binäre Summe, die in einem Ausgangsregister 20 gespeichert wird. Das Ausgangsregister gibt die Summe über achtundvierzig Bits auf den Leitungen CC und einen Übertragsausgang auf der Leitung C ab. Das Addierwerk 18 besteht aus 12 Unteraddierern 0-11 _t die voneinander unabhängig sind. Die Unteraddierer sind gleichartig im Aufbau und nehmen jeweils 4 Bits des ersten Summanden aus dem Eingangsregister 10 sowie 4 Bits des zweiten Summanden aus dem, Eingangsregister 12 auf. Außerdem empfängt jeder Unteraddierer sein eigenes Übertragssignal aus dem Ausgang der Übertraglogik 16.

Die Übertraglogik 16 umfaßt eine dreistufige Torkaskade, deren Abstufungen als erste, zweite und dritte Stufe bezeichnet werden* Die erste Stufe der Übertragkaskade besteht aus 23 untereinander gleichen Abschnitten, bezeichnet mit 1-23. Jeder dieser Abschnitte empfängt zwei Bitstellen sowohl vom ersten wie vom zweiten Summanden. Weiterhin enthält die erste Stufe der Übertragkaskade 16 eine spezielle Anfangsstellenschaltung 22, die auf das Anfangsbit an der kleinsten Stelle des ersten und zweiten Summanden sowie auf den Übertrageingang anspricht und das Bit an der kleinsten Stelle in der Summe im Ausgangsregister 20 setzt. Diese Anfangsstellensehaltung bzw. dieser Kleinstell enaddierer 22 gibt Signalpegel auch in die zweite und dritte Stufe der Übertragkaskade 16.

Nach Flg. 2 umfaßt der Übertragteil des Klelnstel-

00 98 85718 88

lenaddlefe'rs- 22 zwei Gruppen von drei UND-Toren, die mit 24, 26, 28, 30, 32 und 34 bezeichnet sind. Die erste Gruppe dieser drei Tore stellt eine Wahrheitsloqik und die zweite Gruppe dieser drei Tore stellt die doppelte Falschlogik dar. Die Wahrheitstore 24, 2C₁ und 28 nehmen die Kl einstel lenbits AA₀₀ sowie BB₀₀ und das Eingangs-Übertragblt C^_n auf und erzeugen ein Ausgangssignal Rl₀₀ gemäß der Gleichung

■ Rloo = ^AAoo * ^BBoo ^{+ (AA}oo ^{+ BB}oo> · ^cin

Entsprechend liefern die Falschheitstore 30,32 und 34 ein Ausgangssignal entsprechend der Relation -

Rl₀₀ - AA₀₀ . BB₀₀₊(AA₀₀ + BB₀₀) .C_1n

Der K*. einstel 1 enaddier er 22 besitzt weiterhin einen Schal turvqsteil, der das Kl einststell enbit der Summe erzeugt und es in das Kleinststellen-Flip-Flop des Ausqanqsreäisters 20 einschreibt. Dieser Addiererteil umfaßt zwei Paare von UND-Toren 36 und 38, die die KIeinstel1enbits der beiden Einganqsregister 10 und 12 empfangen. Die beiden UND-Tore 36 sind mit ihren Ausgängen zusammenqeleqt, so daß sie die EXKLUSIV ODER*Funktion A₀ fc B₀ erfüllen. Die Tore 38 liegen in ähnlicher Weise mit ihren Ausqängen zusammen und erfüllen die negierte EXKLUSIV ODER-Funktion A_n β Β_Λ« Zwei UND-Tore 44 mit zusammengelegten 'Ausgängen bilden eine EXKLUSIV ODER-Schaltung, die das Klelnststellen-Flip-Flop 48 in dem Ausgangsregister 20 auf wahr stellt. Ein zweites Paar UND-Tore 50 zeigt ebenfalls zusammenliegende Ausgänge und stellt das Flip-Flop48 zurück. Somit bilden die vier Paare von Toren die Summe der beiden Binär-Eingangsbits. An den Toren 44 und50 liegt ferner das Inverse des TaJc timpuls es (<fp)_r wodurch erreicht wird« dfcö das Flip-Flop 48 zwischen jßwei ; --Taktimpulsen, wenn die Eingangsregister 10 und 12

00988S7188«

BAD ORIGINAL

ihren Inhalt ändern können, gesetzt oder zurückgesetzt wird.

Die erste Stufe der Übertragkaskade 16 enthält zu dem Kleinstenenaddierer 22 noch 23 untereinander gleiche Abschnitte, von denen jeder zwei Bits des ersten und des zweiten Summanden aufnimmt, ausgehend von den Bifes an den kleinsten Stellen. Eine derartige Schaltung für einen Abschnitt m (wobei m eine ganze Zahl zwischen 1 und 23 ist) zeigt Fig. 3* Von der positiven und negativen Logik jeder Schaltung ist nur die positive Logik dargestellt, da die Schaltungen für die wahre und falsche Logik einander entsprechen mit dem Unterschied, daß die Eingänge der falschen Logik Komplemente der Eingänge der wahren Logik sind. Nach Fig. 3 enthält die Schaltung eine Gruppe vier UND-Toren 54, 56, 58 und 60, deren Ausgänge an der mit Ml_n, bezeichneten Leitung liegen. Die Eingänge für die vier Tore sind mit den Bitstellen AA_2n, _ -jund AA₂ des im Eingangsregister 10 stehenden ersten Summanden und mit den Bitstellen BB2_m _ ₁ und BB2_m des in dem Eingangsregister 12 stehenden Summanden verbunden. Die gleiche Gruppe von Eingangsbits liegt an einer zweiten Gruppe von drei UND-Toren 62, 64 und 66, deren Ausgänge an der mit Rl_m bezeichneten Leitung liegen. Die Schaltung nach Fig. 3 erfüllt folgende Beziehungen

^M1m - ^(AA2m * ^BB2m> · ^iAA2m - 1 ^{+ BB}2m - 1> "

^R1Ä - ^AA2m · ^BB2m ^{+ AA}2m - 1 · ^BB2m - 1 · ^(AA2m ^{+ BB}2m⁾

Für die falsche Logik gelten die entsprechenden Negationen

⁵^ A_n, «· BB_2m) . (AÄ_2m ^_{1 +} BB_21n-1)

ÄÄ2m - BB_2m ♦ AA_2n, _ ^ BB_2n,

00988 5/1888

Man bemerke, daß Rl_m und Rl_m wie auch Ml_m und Ml^ nicht logische Komplemente zueinander darstellen. Jede Abteilung der ersten Stufe der Übertraglogik ermöglicht! einen Übertrag in die Bitstelle 2m + 1 und in die Bitstelle 2m - 1, wo m die Nummer eines bestimmten Abschnittes der ersten Stufe bedeutet (m eine ganze Zahl zwischen 1 und 23).

Die zweite Stufe der Übertragskaskade 16 besteht aus 11 Abschnitten 1 - 11 (Fig. 1). Sie sind in zwei Gruppen gegliedert, nämlich 6 Abschnitte mit ungerader Nummer und 5 Abschnitte mit gerader Nummer, Die schaltungsmäßige Auslegung jeder dieser Abschnitte ist gleich und besteht aus einem logisch wahren Anteil und einem entsprechenden logisch falschen Anteil. Der logisch wahre Anteil ist aus Fig. 4 zu entnehmen. Danach empfängt der logisch wahre Anteil jedes Abschnittes in der zweiten Stufe acht Eingänge, nämlich die Eingänge Rl und Ml aus je vier aufeinanderfolgenden Abschnitten der ersten Stufe der Übertragkaskade_β Weiterhin überlappen sich die Eingänge der ungeradzahligen Abschnitte der zweiten Stufe mit den Eingängen der geradzahligen Abschnitte der zweiten Stufe. So erhält der Abschnitt 2 der zweiten Stufe Eingangssignale aus den Abschnitten 1-4 der ersten Stufe, während Abschnitt 3 der zweiten Stufe die Eingänge aus den Abschnitten 3-6 der ersten Stufe aufnimmt.

Gemäß der Darstellung nach Fig. 4 hat ein Abschnitt η der Zweitstufenabschnitte 1 - 11 die Eingänge Rl und M 1 aus den Erststufenabschnitten mit den Nummern 2n_t 2n - 1, 2n - 2 und 2n - 3. Die vier Ml Ausgänge eines erststufigen Abschnittes, die zu einem einzigen Zweit stufenabschnitt führen, liegen alle «n einem UND-Tor 68_r dessen Ausgang M2'_n ist. Die vier Rl Eingänge werden der Reihe nach an die vier

009885/188 8

UND-Tore 70, 72, 74 und 76 gegeben, deren Ausgänge zu einer Ausgangsleitung R2₂ zusammengelegt sind. Die logische Funktion jedes zweitstufigen Abschnittes ergibt sich aus folgenden Gleichungen:

^M2n * ^M12n · ^M12n - 1 · ^M12n - 2 ' ^M12n - 3

^R2n * ^R12n - 3* ^M12n - 2 ' ^M12n - 1 · ^M12n * ^R12n -

^M12n - 1 · ^M12n * ^R12n - 1 ' ^M12n ^{+ R1}2n

wobei η die Nummer des Abschnittes in der zweiten Stufe ist und zwischen 1 und 11 einschließlich liegen kann. Für n*l wird noch bemerkt, daß Rl« * Rl wird. Dieser letzte Term wird aus dem Ausgang des Kleinstellenaddirers 22 entnommen, da für den Term Rl_2n _ 3 ^für η =* 1 in der zweiten Stufe kein Eingang vorhanden ist, wird dieser Term stets auf 0 gesetzt. Auch für die Terme Ml_2n _ ₂ und Mi_2n _ ist in dem Kleinststellenabschnitt 1 der zweiten Stufe kein Eingang vorhanden. Diese beiden Terme werden jedoch stets auf 1 gesetzt_r 0er Abschnitt zur falschen Logik ist genau so aufgebaut mit der Ausnahme, daß die Terae Wl_n sowie IT dafür vorgesehen sind, zwei Ausgangs terae E2_n und M2 zu erzeugen.

Die dritte Stufe der Übertragkaskade 16 weist zwei Abschnitte auf, nämlich den ungeraden Abschnitt 1 und den geraden Abschnitt 0. Die schaltung^nSßige Logik dieser beide« Abschnitte ist gleich und aus Fig. 5 asu erkennen. Der Abschnitt 1 erhllt dia Ausgänge der wsgeradsialiiigen Abschnitt© 1-11 aus der zweitem Stufe, der Abschnitt 0 nimmt die Ausgänge der geradzahligen Abschnitte 2-10 aus der zweiten Stuf* sowie die Terra© Ut_Q «nd ST₀ aus dem Kl einstellenaddier er 22 aufm Der Abschnitt 1 der dritten Stufe erzeugt die Überträge für jeden der ungeradzahligen Unteraddierer 1 - 11 und deren Komplemente, während der Abschnitt 0 die Überträge für alle gerad-

Q09885/1888

zahligen Unteraddierer O~1O und deren KoiRpienente erzeugt«

Gemäß Fig. 5 besteht die logische Schaltung des Abschnittes O der dritteis Stufe ©us sechs Gruppen von UND·»Toren, von denen <lie oberste Gruppe sechs UND-Tore 78, 80_? 82, 84, 86 und 88 mit gemeinsam zusammengelegtem Ausgang aufweist. Die nHcaste Gruppe umfaßt die fünf UND-Tore 90, 92, 94, 96 und 98 mit gemeinsamem Ausgang. Die dritte Gruppe schließlich umgreift vier UND-Tore 100, 102, 104 und 106 mit gemeinsamem Ausgang. Die vierte Gruppe besitzt drei UND-Tore 108, 110 und 112 mit gemeinsamem Ausgang. Die fünfte Gruppe zeigt zwei UND-Tore 114 und 116 mit gemeinsamem Ausgang, während die sechste Gruppe nur aus dem einzelnen UND-Tor 118 besteht· Das Tor 118 empfängt ein Signal R2 und erzeugt ein Ausgangssignal C , wobei ρ die Nummer des Abschnittes in der dritten Stufe der Kaskadenlogik 16 ist, und demzufolge 0 oder 1 sein kann. Es wird noch bemerkt, daß

der Term R2„ aus dem Term Rl des Kleinsteilenaddieo ο

rers 22 abgeleitet ist. Wo der gleiche Term in Jeder Gruppe auftritt, ist er in ähnlicher Weise von dem Ausgang Rl des Kleinstel1enaddierers 22 abgeleitet. Die logische Funktion des Anteiles von höchster Ordnung ergibt sich aus folgender Beziehung

Cp .10 ". R2p · M<	> "P- +	2 ·	m2p +	M* 4 * *	J	6 "	6 *	M2	P +	8
						•	•	H2	P +	10
+ R2p*	2 *	m2p	+ 4 '	%>♦	8 ·	"2P	♦	8
					10	m2p	+	10
	4 *	m2p	+ 6 *	"2P*		m2p	+	10
+ r2p ♦	6 *	m2p	+ 8 *■	"2P *·
.♦ «2p *	8 '	M2p	+ 10
♦ r2p ♦	10		-

009885/1888

•Die nSchst niedrigeren Stellenteile der dritten Stufe folgen dera gleichen Aufbau Vorstehander Gleichung, wobei jedoch der letzte Terra jeder Zeile wit abnehmender Stellenaahl wechselt«, Beispielsweise C ^ „ ist der gleiche Ausdruck wie vorstehende Gleichung nur mit dem

_in sowie M2_ . ^_n

Unterschied, daß" die Terme R2 . _4n sowie M2 weggelassen sind»

Jeder Abschnitt der dritten Stufe enthält eine zweite Logik zur Erzeugung der Kompl eisen te 2U jedem der Überträge« Ds die falsche Logik in gleicher Weise ausgelegt ist wie die wahre Logik, ist sie nicht besonders dargestellt worden«.

Es sind insgesamt 12 Unteraddierer 0-11 vorhanden, die untereinander identisch ausgelegt sind. Jeder Unteraddierer setzt ein Flip-Flop im Ausgangsregi« "-ster 20 in den Zustand 0 oder 1 je nach der binären Ssirame des entsprechenden Stellenbits am Eingang und des Übertrages aus der Übertragschaltung 16. Gemäß Fig. 6 sind die dem Unteraddierer zugeordneten vier Flip-Flops des Ausgangsregisters mit 120, 122, 124 und 126 bezeichnet. Das kleinststel1 ige Bit CC_4r _ ₃, wobei r der Nummer des Unteraddferers entspricht, und zwischen 0 und 11 einschließlich liegt, wird aus zwei Eingangsbits AA_{4r +} ^ und BB_{4r +} ^ abgeleitet. Diese beiden Bits zusammen mit ihren Komplementen aus den Eingangsregistern 10 und 12, die den ersten und zweiten Summanden speichern, werden auf zwei EXKLUSIV ODER-Schaltungen 128 und 130 gegeben, die jeweils aus zwei UND-Toren mit gemeinsamem Ausgang bestehen. Die Ausgänge der beiden EXKLUSIV ODER-Schaltungen 128 und 130 sind zusammengelegt und liegen an dem UND-Tor 132 bzw. 134 zusammen jeweils mit dem invertierten Taktimpuls cF. Das gewährleistet,

0 0988 ft /1888

daß die Ausführung der Summierfunktion zwischen normalen Taktimpulsen stattfindet und nicht während der Zeit, in der die Eingangsregister sich ändern könnten. Ein zweites Paar EXKLUSIV ODER-Schaltungen und 138 ist vorgesehen zur Ausführung der EXKLUSIV ODER-Funktion, und zwar in Abhängigkeit von einem Eingangs-Übertragssignal C_n, seinem Komplement C_n"

und dem Ausgang der EXKLUSIV ODER-Schaltungen 128 und 130. Der Ausgang der EXKLUSIV ODER-Schaltung 136 setzt das Flip-Flop 120 in den Zustand 1, entsprechend dem Ausgangsbit CC. ^, während der Ausgang der EXKLUSIV ODER-Schalgung 138 das Flip-Flop 120 in den Zustand 0 setzt, entsprechend dem Komplement CC_{4 r +} ^, Die zwei Sätze EXKLUSIV ODER-Schaltungen für die wahre und falsche Logik führen die Funktion eines vollen Addierers für acht mögliche Kombinationen der drei Eingangsbits AA, BB und C entsprechend der folgenden Wahrheits.tabelle aus:

AA	0	1	0	0	1	1	O	1
BB	0	0	1	0	1	0	1	1

C-OOOlOlIl

Summe CC 01110001 · 0 0 0 0 1 1 11

Das Summenbit CC_{4r + 2} an der zweituntersten Stelle wird aus den nächst höhersteiligen Bits aus den zwei Eingangsregistern, nämlich AA ^ und BB₄ .5 ³^"" geleitet. Diese Bits werden zusammen mit ihren Komplementen auf zwei Paare von UND-Toren 140 und 142 gegeben, die zwei EXKLUSIV ODER-Schaltungen für die wahre und falsche Logik darstellen. Die zwei Ausgänge gelan-

009885/1888

gen durch UMD-Tore 144 und 14S₃ an denen das negierte Taktsignal CP* liegt, und gehen von da weiter zu zwei Paaren von UPD-Toren,, die wiederum aus zwei EXKLUSIV ODER-Schaltungen 148 und 150 in ähnlicher Weise gebildet sind, wie das bereits oben im Zusammenhang mit dem Bit an der kleinsten Stelle beschrieben wurde. Die Ausgang© der EXKLUSIV ODER-Schaltungen 148 und 150 sind" mit den Sets- bsw«. Kücksetz-Eingängen des Flip-Flops 122 ^erfeundsn und setzen dieses Flip-Flop in einen der beiden Zustünde 1 oder 0. Die UND-Tore der EXKLUSIV ODER-Schaltungen und 150 sprechen auf externe Übertragsignale Cj; und C"_r an» Weiterhin sind" alle UWD-Tore- der ElKLUSIV-ODER-Schaltungen 148 und ISO mi'c deia Ausgang der E)OiLUSIV ODER-Schaltung 128 des Bits an der niedrigeren Stelle verbunden«, Dadurch ist gewährleistet, daß das zweitstellige Bit von den* ODEE= Toren 148 und ISo nur darm qesetst werden kann, wenn das ein© oder andere der niederstelligeref* Eits ssahr ist; dadurch trira näisalich angezeigt,, daß ein Übertrag von der niederstelligeren Suraoe gebildet wird, wie das aus den Spalten δ und 7 der vorstehenden Mahrheitstabelle hervorgehto

Jede der beiden E3CKLU3IV OOEl-ScBisltungeo 118 und 150 ist von, einero Paar EEKLOSIV ODER-Schaltungen 152 und 154 überbrückt, das ebenfalls' aus je einem Paar von UND-Toren besteht« Die EXKLUSIV ODER-Schaltutsg 152 erapfängt wicht nur dssi Ausgang der EXKLUSIV ODlE-Schaltung 14O₀ sondern noch ein internes Übertragsignal aus einem UND-Tor 156j dessen Ausgang wahr ist_e wenn di® beiden Bits an den untersten Stellen'des Unteraddierers wahr sind« In ähnlicher Weise liefert ein Tor 158 den logisch falschen Term«

009885/1888

Man erkennt, daß beim Erzeugen der Summe der zwei Eingangsbits der zweite Abschnitt des Unteraddierers sowohl ein internes wie auch ein externes Übertragsignal verarbeitet. Das externe Übertragsiqnal wird natürlich von der Übertragschaltung If, abgeleitet, während das interne Übertragsignal von den Bits en niedrigeren Stellen innerhalb des Unteraddierers herkommt. Dadurch wird die gleichzeitige Addition der Überträge in allen vier Größenordnungen innerhalb des Unteraddierers möglich. Die interne Übertraginformation wird Ober die EXKLUSIV rDER- Schaltunq 152 für die logisch wahre Schaltung und über die EXKLUSIV ODER-Schaltung 154 für logisch falsche Schaltung eingeführt, während das externe Übertrsasignai über die EXKLUSIV ODER-Schaltung bzw. 150 für die logisch wahre bzw. falsche Schaltung verarbeitet wird.

Die Arbeitsweise des Unteraddierers kann durch Betrachten der vereinfachten Blpckdarstellung gemäß Fig. ι besser verstanden werden, wobei sich Fig* 7 auf die vierte bzw. höchste Bitstelle bezieht. Weiter ist nur der logisch wahre Anteil der Schaltung dargestellt. Die zwei Eingänge AA- und BB₄ liegen an einer EXKLUSIV ODER-Schaltung 160, die nur dann einen wahren Ausgang liefert, wenn entweder, AA. oder BB im Sinne des ausschließlichen ODER frahr sind. Der Ausgang der EXKLUSIV ODER-Schaltung 160 ist gleichzeitig ein Eingang für eine EXKLUSIV ODER-Schaltung 162, deren zweiter Eingang das externe Übertragsignal C ist. Wenn dies der Übertrag ist, der von dem Bit an niederer'StelIe vorgetragen ist, wie das bei bekannten, vortragenden Paralleladdierern der Fall ist, dann würde der Ausgang der. EXKLUSIV ODER-Schaltung 162 die korrekte binäre Summe darstellen. Mit anderen Werten, die EXKLUSIV ODER-Schaltungen 160 und 162 arbeiten als vollwer-

009885/1 888

tige Addierer in Übereinstimmung mit der vorstehenden Wahrheitstabelle. Die soweit beschriebene Schalr tung entspricht genau der Schaltung für das Bit an der untersten Stelle des schon beschriebenen Unteraddierers. Jedoch liefert das externe Übertragsignal C selbst nur einen wahren Übertrag an den Addiererabschnitt an der untersten Stelle und nicht an die Addiererabschnitte an höheren Stellen innerhalb des Unteraddierers. Das externe Übertragsignal C ist in den höheren Stellen des Unteraddierers nur dann signifikant, wenn die beiden Eingangsbits zu jeder der unteren Stellen nicht gleich sind» Dies geht aus den Spalten 6 und 7 vorstehender Wahrheitstabelle hervor. Daher ist ein dritter Eingang für P die EXKLUSIV ODER-Schaltung 162 vorgesehen, der nur

dann wahr ist, wenn die Bits für jede niedere Ordnung innerhalb des Unteraddierers ungleich sind. Mit anderen Worten, das externe Übertragsignal bestimmt, wenn die Anwesenheit eines Übertrags an der untersten Stelle dazu führt, daß ein Übertrag zu den höheren Stellen des Addierers vorgetragen werden muß. Das externe Übertragssignal kann wie folgt formuliert werden:

Externer Übertrag = C (A₁ 9 B₁) (A₂ © B₂) (A₃ 9 B₃)

Es muß weiterhin Vorsorge dafür getroffen sein, daß " die in den unteren Stelle des gleichen Unteraddie

rers erzeugten Überträge auch bei Abwesenheit eines externen Übertragssignales verarbeitet werden. Dies gelingt mit einer zweiten EXKLUSIV ODER-Schaltung 164, deren einer Eingang am Ausgang der EXKLUSIV ODER-Schaltung 160 liegt und deren anderer Eingang ein internes Lbertragsignal führt, das von den unteren Stellen innerhalb des Unteraddierers abgeleitet wird. Das interne Übertragsignal innerhalb des

00988R/1888

BAD ORIGINAL

Unteraddierers wird entsprechend der folgenden Beziehung erzeugt:

Interner Übertrag =

A₁-B₁ (A₂ © B₅)(A₃ © B₃) +A₂ . B₂ (A₃ « B₃) + A₃ . B₃

Man sieht also, daß der interne Übertrag wahr ist, .wenn die beiden Bits der nächstunteren Stelle wahr sind oder wenn die beiden Bits der zweituntersten Stelle wahr sind und eines oder das andere Bit der nächstunteren Stelle wahr ist, oder wenn die Bits an der untersten Stelle wahr und das eine oder andere Bit der anderen beiden Stellen wahr sind.

Im Zusammenhang mit Fig. 6 wird noch festgestellt, daß der interne Übertrag für die beiden höchsten Stellen des Unteraddierers die von der ersten Stufe der Kaskadenschaltung 16 abgeleiteten Terme R₁ und R₁ verarbeitet. Das ist lediglich deshalb vorgesehen, um die Schaltung für den internen Übertrag des Unteraddierers zu vereinfachen.

Aus vorstehender Beschreibung entnimmt man, daß ein Paralleladdierer entwickelt wurde, in dem die Überträge für alle Größenordnungen gleichzeitig erzeugt werden. Durch Verwendung der jeweils gleichartigen Wahren und falschen Logik werden keine Inverter oder andere Elemente benötigt, die in einen Ausgangszustand zurückgestellt werden müßten. Die gesamte logische Schaltung besteht vollständig aus nicht löschenden UND-Toren, wobei die größte Zahl der in Reihenkaskade liegenden Tore auf vier beschränkt bleibt. Da die UND—Tore so ausgelegt werden können, daß sie mit Verzögerungszeiten von drei Nanosekunden arbeiten, liegt die Gesamtzeit zur Bildung der Summe der 48 Bits umfassenden Operanden bei zwölf Nanosekunden.

009885/1888

Durch Auslegung der Übertraglogik; in drei Stufen mit wechselseitigen Überlappungen und Verzweigungen zwischen den Pegeln werden die stark aufgefächerten und pyramidenartig angelegten logischen Schaltungen bekannter Paralleladdierer praktisch weitgehend vermieden. Es wird also ein Paralleladdierer für Operanden aus 48 Bits beschrieben, bei dem die Übertraginformation gleichzeitig für alle Bitstellen erzeugt wird· Die ausnahmslos aus UND-Toren bestehende Übertraglogik ist in drei Stufen angeordnet. Der Addierer weist ferner voneinander unabhängige Unteraddierer für jeweils 4 Bitstellen auf. Die Übertraglogik und die Unteraddierer sind so verknüpft, daß höchstens vier kaskadenartig hintereinanderliegende Vorstufen zur Erzeugung der Summe an einer Bitstelle nötig sind» In allen Stufen ist eine doppelte Logik, nämlich eine wahre und eine falsche Logik verwendet worden. Die zweite und dritte Stufe der Übertraglogik ist in einer sich überschneidenden Schaltung ausgelegt, um deren Aufblähen zu begrenzen.

009885/1888

Claims (10)

1. Patentansprüche

   1« Binärer Parallel-Addierer, der zu zwei in je einem Eingangsregister enthaltenen Summanden über eine Zwischenstufe die binäre Summe in ein AusganqEregister speichert, dadurch gekennzeichnet, daß zur Verarbeitung von Summanden mit großer Bitzahl die Zwischenstufe (16, 18) ausnahmslos aus UND-Toren besteht, die zwischen die beiden Einqangsregister (10,12) und das Ausgangsregister (?0) qescha¹. tet sind.
2. 2. Addierer nach Anspruch 1, dadurch" gekennzeichnet, daß zwischen einer Binärstelle der Eingangsreqister und der entsprechenden Binärstelle des Ausgangsregisters höchstens vier UND-Tore (m,n,p,r) in Reihe geschaltet sind.
3. 3. Addierer nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die Zwischenstufe eine Übertragschal tunq (16) und eine Addierschaltung (18) aufweist, die beide mit den Eingangsregistern (10,12) verbunden sind und wobei.die Übertragschaltung (16) mit den Eingangsregistern und die Addierschaltung (18) mit der Übertragschaltunq und mit den Eingangsregistern verbunden sind.
4. 4. Addierer nach Anspruch 3, dadurch gekennzeichnet, daß die Addierschaltunq mehrere untereinander gleiche Unteraddierer (r) aufweist, von denen jeder mit einer verhältnismäßigen Anzahl von Bitsteil en der Eingancsregister und mit einer Übertrag-Bit-Leitung aus der Übertragschaltung (16) verbunden ist.

   009885/1888

   - 20- 2017137
5. 5. Addierer nach Anspruch 3 oder 4, dadurch gekennzeichnet,, daß die Übertragschaltung (16) gleichzeitig die Bits aus allen Bitstellen der Eingangsregister aufnimmt und gleichzeitig mehrere Ausgangssignale erzeugt; und daß jeder Unteraddierer (r) eines dieser Ausgangssignale aufnimmt sowie aus diesem zusammen mit der verhältnismäßigen Bitanzahl aus den Eingangsregistern die Binärsumme aus einer entsprechenden Anzahl von Bitstellen bildet.
6. 6. Addierer nach einem der Ansprüche 3 - 5_f dadurch gekennzeichnet, daß die Übertragschaltung drei Stufen (m,n,p) besitzt und daß

   a) die erste Stufe (m) aus mehreren untereinander gleichen Abschnitten besteht, von denen jeder zwei Bitstellen (AA_2m, AA_2n, _ ^; ^BB2m» ^BB2m' - 1^} dfr Eingangsregister (10,12) aufnimmt und zwei •ret^ PinSrsignale (Ml_n,, Rl_) erzeugt;

   b) die zweite Stufe (n) aus mehreren untereinander gleichen Abschnitten besteht, von denen jeder die ersten Binärsignale (Mlpn* *** ^M^2n - 3' ^R^2n' *"* ^R^2n - 3^ ^{aus vier} Abschnitten der ersten Stufe (m) aufnimmt, mit seinem ersten und zweiten Eingang parallel zu: entsprechenden zwei Eingängen eines anderen Abschnittes der zweiten Stufe und mit einem dritten und vierten Eingang parallel zu-entsprechenden zwei Eingängen eines weiteren anderen Abschnittes der zweiten Stufe liegt, sowie zwei zweite Binärsignale (R2_n, M2_n) erzeugt;

   c) die dritte Stufe (p) aus zwei untereinander gleichen Abschnitten besteht, von denen der eine die zweiten Binärsignale derjenigen Abschnitte

   00988^/18 88

   BAD ORIGINAL

   der zweiten Stufe aufnimmt, die untereinander keine parallel liegenden Eingänge besitzen, der andere Abschnitt der dritten Stufe die zweiten Binärsignale der restlichen Abschnitt der zweiten Stufe aufnimmt, und jeder der beiden Abschnitte der dritten Stufe mehrere Übertragbits (C".,- ... C ^q) erzeugt, von denen je eines einen Unteraddierer empfängt. .
7. 7. Addierer nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet, daß jeder Unteraddierer (r) von jedem Eingangsregister vier Bitstellen sowie eines der Übertragbits aufnimmt '.und, vier, die Binärsumme aus diesen Bits repräsentierende Summenbits erzeugt.
8. 8. Addierer nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet, daß jeder Abschnitt aus allen Stufen eine Schaltung für logisch wahre und eine ergänzende Schaltung für logisch falsche Signale enthält; und daß jeder Unteraddierer mit einer Leitung für das Übertragbit sowie mit einer Leitung für das Binärkomplement des Übertragbits verbunden ist.
9. 9. Addierer nach'einem der Ansprüche 6 - 8, dadurch gekennzeichnet, daß die beiden ersten Binärsignale (ftl_m* ^M^m^ i^ec*^es Abschnittes der ersten Stufe den Relationen genügen

   ^R1m - ^AA2m * ^BB2m ^{+ AA}2m - 1 · ^BB2m - 1 · ^(AA2m ^{+ BB}2m⁾

   ^M1m - ^(AA2m ^{+ BB}2rn> · ^(ÄA2m - 1 ^{+ B}% - l>-

   wobei m eine natürliche Zahl ist und AA, BB die aus

   00988571888

   den Eingan.gsregistern von der durch den Index bezeichneten Bitstelle kommenden Bits bedeuten; daß die beiden zweiten Binärsignale (R2 , M2 ) jedes Abschnittes der zweiten Stufe den Relationen genügen

   ^R2n " ^R12n - 3 ' ^M12n - 2 ' ^M12n - 1 ' ^M12n ♦ Rl_2n _ ₂ . Mi_2n _ _t . Ml_2n

   + ^R12n - 1 ^{β m}2n
   ^{+ R1}2n
   η 2n - 3 2n - 2 2n - 1 2n

   wobei η aus dsr Menge der natürlichen Zahlen genommen· ist;

   und aaß die Übertragbits (C ) aus jödem Abschnitt

   P +■ q

   der dritten Stufe dsr Relation genügen

   ^CP - ^R2p

   ^Cp ₊ 2 ' ^R2p · ^M2p * 2 ^{+ R2}p * 2 ^Cp ♦ 4 ³ % · % .♦ 2 · ^M2 _P * 4 ^{+ R2} _P ♦ 2 * ^M2 _{P +}

   "* ^R2P ₊ 4

   ^C _{P +} q - ^R2p · ^M2p ₊ 2 - ^M2p ♦ 4 ··· ^M2p ₊ q * ^R2p ₊

   ^M2 _P ♦ 4 ■·· ^M2 _P * q ⁺ ·'· ^{+ R2} _P ♦ q mit p=»Ö oder p=»l und q eine natürliche, gerade Zahl*
10. 10. Addierer nach einem der vorstehenden Ansprüche,

    009885/1888

    dadurch gekennzeichnet, daß jeder Unteraddierer (r) für jede Bitstelle der Summanden ein erstes . EXKLUSIV ODER-Tor (14C,...)_r- an dessen zwei Eingänge die beiden Bitstellen (AA, ~, BB, . _,...) liegen, sowie ein zweites und ein drittes EXKLUSIV ODER-Tor (148, 152; -....) mit je zwei Eingängen aufweist, wobei je ein Eingang des zweiten und dritten Tores an dem Ausgang des ersten Tores sowie der andere Eingang des zweiten Tores (148,...) an einer Jbertragbitleitung (C , ...) liegt und der andere Eingang des dritten Tores (152, ...) über eine Schaltung (156, ...) für den internen Übertrag an eine niedrigere Bitstelle (AA- ' ^, ...) der von dem Unteraddierer aufgenommenen Bits angeschlossen ist. : "·..'. .. : ■■■'■..';.

    0 0 9885/1888 ■

    BAD ORIGINAL

    Lee rs ei te