DE2848096A1 - Digitale addieranordnung - Google Patents

Description

25-7-1978 / ■ PHN 8935

Digitale Addieranordnung.

Die Erfindung betrifft eine digitale Addieranordnung für die Bestimmung der Summe einer Anzahl binär kodierter Zahlen mit einem digitalen Parallelalckumulator
der eine der Bitanzahl der zu addierenden Zahlen ensprechenr de Anzahl Volladdierer und einen an Ausgänge der Voladdie— rer angeschlossenen ersten Speicher zur Speicherung der
sich aus der Addition ergebenden Zivischensummen- und Zwi— schenübertragsjzahlen enthält, und mit einem Endaddierer
für die Bestimmung der Summe der im ersten Speicher gespeicherten Zahlen und weiterhin mit einer Koppelschaltung für die Kopplung des Endaddierers mit dem ersten Speicher sowie mit einer Zeitsteuerschaltung für die Steuerung des digitalen Parallelakkumulators und des Endaddierers.

Eine derartige digitale Addieranordnung ist aus der US-PS 3 023 9^2 bekannt.

Digitale Addieranordnungen werden beispielsweise in Digitalfiltern benutzt, wobei ein Ausgangskodewort als die Summe der gewichteten ¥erte einer Anzahl dem Filter zu zu führ end ei- binärkodierter Eingangskodewörter
gebildet wird.

Bei der bekannten digitalen Addieranordnung kann die zur Bestimmung einer Anzahl von Summen benötigte Zeit sehr lang sein, weil die Bildung einer neuen Summe
erst erfolgen kann, nachdem die sich aus der Addition ergebende Zwischenübertragszahl ihren Einfluss auf das End-

909820/0668

25-7-1978 2^ PHN 8935

erge"bis hat ausüben können und das Endergebnis gelesen worden ist. Dies bedeutet in der Praxis, dass beispielsweise bei der Verwendung dieser bekannten Addieranordnung in einem Digitalfilter die Ausgangsfrequenz, d.h. die Frequenz, mit der die Ausgangskodewörter des Filters auftreten, sowohl durch die Anzahl der im Ausgangskodewort mitzugewichtenden Eingangskodewörter als auch durch die Zeit bestimmt.wird, die die Ubertragszahlen benötigen, um ihren Einfluss auf die Endsumme ausüben zu können.

Der Erfindung liegt die Aufgabe zugrunde, eine Digitaladdieranordnung der eingangs erwähnten Art zu schaffen, bei dem die Gesamtzeit für die Bestimmung einer Anzahl von Summen drastisch reduziert ist.

Die erfindungsgemässe digitale Addieranordnung ist dadurch gekennzeichnet, dass die Knüppelschaltung einen an den ersten Speicher angeschlossen Schalter mit einem ersten und einem zweiten Schaltzustand und einen an den Endaddierer· angeschlossenen zweiten Speicher enthält und dass die Zeitsteuerschaltung ebenfalls die Koppelschal— tung derart steuert, dass im ersten Schaltzustand der erste Speicher mit Eingängen der Voladdierer und im zweiten Schaltzustand der erste Speicher mit dem zweiten Speicher für die Übernahme der Zwiscliensummen-' und der.Zwischenübertragzahlen gekoppelt ist.

Bei der Vervendung der erfindungsgemässen digitalen Addieranordnung in einem Digitalfilter wird erreicht, dass die Ausgangsfrequenz des Digitalfilters ausschliesslich entweder dux"ch die Zeit für die Bestimmung dex" Zwischenzumme der zu gewichtenden Eingangskodewörter oder durch die für die Verarbeitung der übertragszalilen in dem Endergebnis erforderliche Zeit in Abhängigkeit davon, welche der zwe.i Zeiten am grössten ist, bestimmt wird.

Ausführungsbeispiele der erfindungsgemässen digitalen Addieranordnung werden nachstehend an Hand der Zeichnung näher erläutert. Es zeigen

Fig. 1 eine digitale Addieranordnung nach dem Stand der Technik,

Fig. 2 ein erstes Ausführungsbeispiel der

909820/0668

25-7-1978 /. PHN 8935

erfindungsgemässen digitalen Addieranordnung, bei dem der Endaddierer als Serienaddierer ausgeführt ist,

Fig. 3 einige Zeitdiagramme zur Erläuterung der Wirkung der Anordnung nach Fig. 1 und Fig. 2, Fig. 4 ein zweites Ausführungsbeispiel der erfindungsgemässen digitalen Addieranordnung, bei dem als Endaddierer ein Paralleladdierer verwendet ist,

Fig. 5 ein Digitalfilter mit einer erfindungsgemässen digitalen Addieranordnung.

Es sei bemerkt, dass die in der Zeichnung dargestellten digitalen Addieranordnungen aus einer Anzahl Addierer aufgebaut sind, die mit je einem einziffrigen Bezugszeichen versehen sind. Die Addierer sind mit Ein- und Ausgängen versehen, die durch zweiziffrige Bezugszeichen bezeichnet sind, deren erste Ziffer gleich dem Bezugszeichen des zugeordneten Addierers ist und deren zweite Ziffer angibt, ob es sich um einen Ein- oder um einen Ausgang handelt. Die Eingänge werden durch eine zweite Ziffer gleich 1, 2 oder 3 gekennzeichnet und die Ausgänge führen als zweite Ziffer eine 4 oder eine 5· Die mit den Addierern gekoppelten Elemente sind ebenfalls mit aus zwei Ziffern bestehenden Bezugszeichen bezeichnet, wobei die erste Ziffer gleich dem Bezugszeichen des zugeordneten Addierers ist. ¥enn in nachstehender Beschreibung auf eine Gruppe von Ein- oder Ausgängen oder auf eine Menge Elemente verwiesen wird, werden Gruppenbezugszeichen benutzt, die aus einer Buchstabenzifferkombination bestehen. Beispielsweise wird mit X1 die Eingangsgruppe bezeichnet, die als zweite Ziffer des Bezugszeichens der betreffenden Eingänge die Ziffer 1 führen.

Die bekannte digitale Addieranordnung nach Fig. 1 ist für die Bestimmung der Summe einer Anzahl aus vier Bits bestehender, binar kodierter Zahlen eingerichtet und enthält dazu einen digitalen Parallelakkumulator JO mit vier Volladdierern 1, 2, 3 und 4. Die Bits mit aufeinanderfolgend grösserem Gewicht werden durch Eingabeeinrichtungen 16, 2.6, 36 bzw. 46 (nachstehend gemeinsam mit X6 bezeichnet) den Eingängen 12. 22. 3,2^bzw. 42 (weiter gemeinsam

25-7-1978 Ä * PHN 8935

mit X2 bezeichnet) zugeführt. Mit den Ausgängen Λ%, 2k, 3k und kk (Xk) sind Speicherelemente 17, 27, 37 und k7 (X7) und mit den Ausgängen 15» 25 und 35 (X5) sind Speicherelemente 18, 28 und 38 (X8) verbunden, die je ein Bit speiehern können. Die Speicherelemente X7 und X8 bilden zusammen den ersten Speicher 10 und sind mit den Eingängen 11, 21, 31 und k^ (X1 ) bzw. mit den Eingängen 23, 33 und k-3 (X3) der Voladdierer 1, 2, 3 und k derart verbunden, dass die Bits der im ersten Speicher 10 gespeicherten Zahlen von den Volladdierern 1, 2, 3 und h zu den Bits der nächsten, von den Eingabeeinrichtungen X6 den Eingängen X2 zuzuführenden Zahl addiert werden.

Nachdem die letzte Zahl der Zahlenfolge, deren Summe bestimmt werden muss, den Eingängen X2 zugeführt worden ist und zu einem Ergebnis, d.h. zu einer Zwischensumme- und einer Zwischenübertragszahl, im ersten Speicher 10 geführt hat, wird durch einen über eine Koppelschaltung kO, die hier nur aus galvanischen Verbindungen besteht, mit dem ersten Speicher verbundenen Endaddierer 20 die Endsumme der in den Speicherelementen X7 und X8 gespeicherten Zahlen bestimmt. Der Endaddierer 20 enthält dazu einen Volladdierer 5 mit einem ersten Eingang 51> dem nacheinander die Bits der in den Speicherelementen X7 gespeicherten Zwischensummenzahl zugeführt werden, mit einem zweiten Eingang 52, dem über ein Verzögerungselement 56 nacheinander die Bits der in den Speicherelementen X8 gespeicherten Zwischenübertragungszahl zugeführt werden, und mit einem dritten Eingang 53» dem über ein Verzögerungselement 58 das am Ausgang 55.auftretende, sich aus der Addition ergebende Ubertragbit zugeführt wird. Die am Ausgang $k des Volladdierers 5 aufti-etenden Bits werden in die Speicherelemente 57-1, 57-2, 57-3 und 57-'+ (57-X) eingeschrieben und bilden dort die Endsumme. Der Verlauf des oben beschriebenen Additionsverfahrens erfolgt unter der Steuerung einer Zeitsteuerschaltung 30, die auf bekannte Weise Steuersignale a, b, c, d und e erzeugt und sie den mit a, b, c, d, und e bezeichneten Steuereingängen des Akkumulators und des Endaddierers zuführt.

909820/0668

25-7-1978

PHN 8935

•Es sei bemerkt, dass dem Eingang 13 des

Volladdierers 1 stets eine logische "O" zugeführt werden muss und dass am Ausgang 45 des Voladdierers 4 normalerweise eine logische "0" auftritt, ausser wenn die zu bestimmende Summe durch eine aus vier Bits bestehende Zahl dargestellt werden kann ('.'overflow"), in welchem Fallaam Ausgang 45 eine logische "1" auftritt.

Die Wirkung der an Hand der Fig. 1 beschriebenen bekannten digitalen Addieranordnung wird nachstehend mit Hilfe eines Zahlenbeispiels näher erläutert. Dabei wird die in der Tabelle .1 dargestellte boolesche Verknüpfungstafel für einen Volladdierer benutzt. In dieser Tabelle sind für die Bezeichnung der Ein- und Ausgänge des Volladdierers die zum Volladdierer 1 gehörenden Bezugszeichen

15 erwähnt.

TABELLE 1

20

11	12	13	14	15
0	0	0	0	• 0
0	0	1	1	0
0	1	0	1	0
0	1	1	O	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

25

Die bei der Bestimmung der Summe der Zahlen 2+1+1+4=8 oder in binär kodierter Form 0010+0001+0001+0100 = 1000 nacheinander an den verschiedenen Ein- und Ausgängen der Addierer 1, 2, 3 und 4 auftretenden Binärwerte sind in der Tabelle 2 schematisch dargestellt.

909820/0668

25-7-197.8-

PHN 8935

15 20

Tabelle

4

cn'

2

1.

I

U ZZ

Tabelle

3

P = 5

q =

O

ο

t =

P. =

2.

I

ti

1

O

t9

q =

O

O

O

ti

2

O , ■

t9 .

1

O

O

O

O

ti

3

I O

t9

2

O

O

1

O

t2

4

O

t10

3

O

O

O

O

I

t2

5 .

O

t10

4

O

O

1

O

1

t3

1

O

til

j5

O ·

O

O

O

t3

2

ο ι

t11

1

O

O

1

1

t3

3

Γ O

t11

2

O

O

O

O

tk

4

O

t12

3

O

O

O

1

tk

5 .

1

t12

O

O

1

O

I

t5

1

1

t13

j.

O

O

O

1

t5

2

O ι

t13

1

O

O

1

1

t5

3

O

t13

2

O

O

O

O

t6

4

1

ti4

3

O

O

O

O

■+

te

5

O

ti4

O

O

1

1

t7

1

O

t15

_5_

O

O

O

O

t7

2

1 j_

t15

1

O

1

1

O

t8

3 4

τ

ti6

2

O

O

O

O

t8

5

ti6

3

O

1

1

O

5

O

O

O

O

1

Die Buchstabenkombination pq in der Tabelle 2 gibt die Bezugszeichen der Ein- und Ausgänge an, und der Buchstabe t bezeichnet, mit dem Index 1, 2 usw., die aufeinanderfolgenden Zeitpunkte, zu denen eine Änderung der
Ein- und Ausgangssignale erfolgt. So ist zum Zeitpunkt ti an den Eingängen x1 die Zahl 0000, an den Eingängen X2

die Zahl 0010, an den Eingängen X3 die Zahl 000 und am Eingang 13 eine logische 0 vorhanden.

Die Volladdierer 1, 2_t 3 und 4 erzeugen zum Zeitpunkt t2 an den Ausgängen X4 die Summe 0010 diesel"

Zahlen und an den Ausgängen X5 den sich aus der Addition
der Zahlen ergebenden übertrag 000, während am Ausgang 45 dabei auch eine 0 erscheint. Die Summe 0010 erreicht über die Speicherelemente X7 zum Zeitpunkt t3 die Eingänge X1,

909820/0668

25-7-1978 f_o ' PHN 8935

während ebenfalls zum Zeitpunkt t3 der Übertrag 000 über die Speicherelemente X8 den Eingängen X3 und eine logische 0 dem Eingang 13 zugeführt werden. Zum Zeitpunkt t3 wird ausserdem die zweite Zahl 0001 von den Eingabeeinrichtungen X6 den Eingängen X2 zugeführt.

Dieser Vorgang geht weiter, bis alle Zahlen,

deren Summe bestimmt werden muss, zu einer Zwischensummenzahl 0100 und zu einer Zwischenübertragszahl 010 verarbeitet worden sind. Diese ^Zahlen sind vom Zeitpunkt t8 an im ersten Speicher 10 verfügbar und werden anschliessend im Endaddierer 20 summiert, der als Serienaddierer ausgeführt ist und bei dem am Ausgnag ^h nacheinander in der Reihenfolge vom niedrigstwertigen zum höchstwertigen Bit die Bits der Endsumme auftreten.

Die Summierung im Endaddierer 20 ist in der Tabelle 3 schematisch dargestellt.

Die Endsumme ist also 1000, die die binär kodierte Zahl ist, deren Bits nacheinander zu den Zeitpunkten ti6, ti4, t12 und t10 am Ausgang auftreten, der mit pq = $k bezeichnet ist.

Wenn nunmehr mit der bekannten digitalen Addieranordnung nach Fig. 1 nacheinander Summen verschiedener Zahlenfolgen bestimmt werden müssen, kann erst die Bildung einer neuen Summe angefangen werden, nachdem die vorangehende Endsumme berechnet worden ist. Das bedeutet, dass im gegebenen Beispiel erst zu einem nach dem Zeitpunkt ti6 liegenden Zeitpunkt den Eingängen X2 eine neue Zahl zugeführt werden kann, so dass die Gesamtzeit für die Bestimmung einer Anzahl von Summen sehr lang ist.

Das in Pig. 2 dargestellte Ausführungsbeispiel der digitalen Addieranordnung nach der Erfindung unterscheidet sich von der bekannten digitalen Addieranordnung nach Fig. 1 darin, dass die Koppelschaltung 4o einen an den ersten Speicher 10 angeschlossenen Schalter 50 mit einem ersten und einem zweiten Schaltzustand und einen an den Endaddierer 20 angeschlossenen zweiten Speieher 60 enthält, und dass die Zeitsteuerschaltung 30 ebenfalls die Koppelschaltung ^O derart steuert, dass im ersten

909820/0868

2848036

25-7-1978 Χλ PHN 8935

SchaItzustand 'der erste Speicher 10 mit Eingängen X1 und X3 der Volladdierer 1, 2, 3 und h und im zweiten Schaltzustand der erste Speicher 10 mit dem zweiten Speicher 6θ für die Übernahme der Zwischensummen- und der Zwischen-Übertragszahlen gekoppelt wird.

Die digitale Addieranordnung nach Fig. 2 enthält weiterhin gleich wie die bekannte Anordnung nach Fig. 1 einen digitalen Parallelakkumulator 70> einen Endaddierer 20 und eine Zeitsteuerschaltung 30·

. Wenn sich der Schalter 50 im ersten Schaltzustand befindet, kann die Wirkung des Parallelakkumulators 70 schematisch wie anhand der Tabelle 2 für die bekannte Anordnung bei der Addition von 2+1+1+4 beschrieben werden. Nachdem zu einem nach dem Zeitpunkt t8 fallenden Zeitpunkt der Schalter 50 mit Hilfe eines von der Zeitsteuerschaltung 30 erzeugten Steuersignals vom ersten in den zweiten Schaltzustand gebracht worden ist, werden die Zwischensummenzahl 0100 und die Zwischenübertragszahl 010 in die Speicherelemente 57-5, 57-6, 37-7 und 57-8 (57-Υ) bzw. in die Speicherelemente 56-I, 56-2 und 56-3 (56-Υ) übernommen, die zusammen den zweiten Speicher 60 bilden. Anschliessend wird der Schalter 50 in den ersten Schaltzustand zurückgeführt und kann eine neue Zahlenfolge den Eingängen X2 zugeführt werden.

Die Verarbeitung dieser neuen Zahlenfolge zu einer neuen Zwischensumme und einer neuen Zwischenübertragszahl verläuft dabei wie in Tabelle 2 für die Bestimmung von 2+1+1+4 angegeben, während unabhängig davon gleichzeitig im Endaddierer 20 die Verarbeitung der ersten Zwischensummen und der ersten Zwischenübertragszahl zur ersten Endsumme wie in der Tabelle 3 angegeben erfolgt.

Es sei noch bemerkt, dass die Verwendung des Verzögerungselements 56 auf verschiedene Weisen vermieden werden kann, beispielsweise indem das niedrigstwertige Bit der in den Speicherelementen 57-Ύ gespeicherten Zwischensummenzahl, d.h. das im Speicherelement 57-5 gespeicherte Bit, dem Speicherelement 57-4 direkt zugeführt wird. In Fig. 3 sind einige Zeitdiagramme für die

909820/0668

25-7-1978 rf PHN 8935

Erläuterung der Wirkung der Rechner nach Fig. 1 und Fig. 2 dargestellt. Das in Fig. 3A dargestellte Zeitdiagramm bezieht sich auf die in Fig. 1 dargestellten bekannte digitale Addieranordnung und das Zeitdiagramm in Fig. 3B betrifft die in Fig. 2 dargestellte digitale Addieranordnung nach der Erfindung.

Die mit 1 . , 2. usw. bezeichneten Pfeile symbolisieren stets das Zuführen einer Anzahl von Zahlen, de ~ ren Summe bestimmt werden muss, und die mit 1_, 2_ usw.

bezeichneten Pfeilen symbolisieren das Verfügbarwerden der zu einer bestimmten Zahlenfolge gehörenden Endsumme.

Ausgehend von der in der Tabelle 2 und der Tabelle 3 angegebenen Addition von vier Zahlen mit je vier Bits bedeutet dies, dass im Falle nach Fig. 3A die ersten Zahlenfolge zwischen den Zeitpunkten ti und t8 zugeführt wird und dass die erste Endsumme zwischen den Zeitpunkten t9 und ti6 verfügbar ist, die zweite Zahlenfolge kann dabei zwischen den Zeitpunkten t17 und t24 zugeführt werden, wonach zwischen den Zeitpunkten t25 und t32 die zweite Endsumme verfügbar wird.

•Dagegen wird im Falle nach Fig. 3B gleichzeitig mit dem Verfügbarwerden der ersten Endsumme zwischen den Zeipunkten t9 und ti6 eine zweite Zahlenfolge zugeführt. Die schraffierten Pfeile in Fig. 3B geben an, dass zwisehen den Zeitpunkten t8 und t9 die Übernahme der Zwischensummen und Zwischenübertragszahlen in den zweiten Speicher erfolgen.

Aus Fig. 3 ist klar ersichtlich, dass mit der digitalen Addieranordnung nach der Erfindung eine drastische Reduktion der für die Berechnung einer Anzahl von Endsummen insgesamt benötigte Zeit erreicht werden kann.

In Fig. h ist ein zweites Ausführungsbeispiel einer digitalen Addieranordnung nach der Erfindung dargestellt, die wie das Ausführungsbeispiel nach Fig. 2 mit einem digitalen Parallelakkumulator 70, einer Zeitsteuerschaltung 30) einem Schalter 50, einen zweiten Speicher 60 und einen Endaddierer 20 versehen ist. Der zweite Speicher 6θ wird dabei durch die Speicherelemente 67, 77»

909820/0668

25-7-1978 y6 PHN 8935

. /11.

87 und 97 (Υ7) für die Speicherung der Zwischensummenzahl und durch die Speicherelemente 68, 78 und 88 (y8) für die Speicherung der Zwischenübertragszahl gebildet. Bei diesem Ausführungsbeispiel ist der Endaddierer 20 jedoch als Paralleladdierer mit den Halbaddierern 6, 7» 8 und 9 ausgeführt. Ausserdem werden die Speicherelemente Y7 nicht nur für die Speicherung der Zwischensummenzahl benutzt, sondern es
wii'd darin auch die Endsumme gespeichert. Die Wirkung des Ausführungsbeispiels nach Fig. 4 kann wiederum an Hand

eines Zahlenbeispiels erläutert werden, wobei das bereits früher in bezug auf die Fig. 1 und 2 benutzte Beispiel,
und zwar die Addition 2+1+1+4 = 8, in der Tabelle 4 dargestellt worden ist, um anzugeben, wie die Verarbeitung der Zwischensummenzahl 0100 und der Zwischenübertragszahl 010 zur Endsumme erfolgt.

• Tabelle 4

P =	9	8	7	6	L	t =
q =					\	t9
• 1	0	1	0	0		t9
3	0	1	0	0		t10
4	0	0	0	0	JL.	t10
- 1	O	1	0	0		t11
1	0	0	0	0		■ tu
3	1	0	0	0		t12
4	1	0	0	0	t12
5	0	0	0	0

Es sei bemerkt, dass die in der Zeichnung

dargestellten Speicherelemente bei der Verwendung dynamischer 4-Phasen-MOS-LSI-Technologie für die Verwirklichung der Voll- und der Halbaddierer durch geringe Kapazitäten
gebildet werden, die vorwiegend aus den Streukapazitäten
der inneren Verdichtung bestehen.

In Fig. 5 ist schematisch ein Digitalfilter dargestellt, in dem die erfindungsgemässe Digitaladdieranordnung verwendet ist. Das Digitalfilter enthält ein
erstes ringgekoppeltes Schieberegister 100 mit einem Ein-

' 909820/0668

25-7-1978 y(. PHN 8935

gang 101, dem mit einer Eingangsabtastfrequenz f. auftretende Eingangskodewörter X. zugeführt werden, die in einem Multiplizierer 102 mit Gewichtsfaktoren C. multipliziert werden, die in einem zweiten ringgekoppelten Schieberegister 103 gespeichert sind. Für die Bestimmung eines Ausgangskodeworts Y muss die Summe N-I bestimmt

^=²= ^Ci^Xn-i

X=O

werden. Die Ausgangskodewörter Y müssen mit einer Ausgangsfrequenz f auftreten und dazu wird in der digitalen Addieranordnung ΛOh einmal pro Ausgangsperiode i/f die Summe N-1 bestimmt. Durch einen Schrägstrich

^ ^Ci^Xn-i
1=0

in den Verbindungsleitungen zwischen den verschiedenen Elementen wird angegeben, dass die Bits, aus denen die Kode-IS Wörter bestehen, parallel verarbeitet werden.

909820/0668

Claims (1)

1. 25-7-1978 . y PHN 8935

   PATENTANSPRÜCHE

   Digitale Addieranoz"dnung für die Bestimmung der Summe einer Anzahl binär kodierter Zahlen mit einem Parallelakkumulator, der eine der Bitanzahl der zu addierenden Zahlen entsprechenden Anzahl Volladdierer und einen an Ausgänge der Volladdierer angeschlossenen ersten Speicher zur Speicherung der sich aus der Addition ergebenden Zwischensummen— und Zwischenttbertragszahlen enthält, und mit einem Endaddierer für die Bestimmung der Summe der im ersten Speicher gespeicherten Zahlen und weiterhin mit einer Koppelschaltung für die Kopplung des Endaddierers mit dem ersten Speicher sowie mit einer Zeitsteuerschaltung für die Steuerung des digitalen Parallelakkumulators und des Endaddierars, dadurch gekennzeichnet, dass die Koppelschaltung einen an den ersten Speicher angeschlos— senen Schalter mit einem ersten und einem zweiten Schaltzustand und einen an den Endaddierer angeschlossenen zweiten Speicher enthält, und dass die Zeitsteuerschaltung ebenfalls die Koppelschaltung derart steuert, dass im ersten Schaltzustand dei- erste Speicher mit Eingängen der VoIladdierer und im zweiten Schaltzustand der ersten Speicher mit dem zweiten Speicher für die Übernahme der Zwischensummen- und der Zwischenübertragszahlen gekoppelt ist.

   909820/0668