DE2756832A1

DE2756832A1 - Addierer fuer fibonacci-codes

Info

Publication number: DE2756832A1
Application number: DE19772756832
Authority: DE
Inventors: Aleksei Petrovitsch Stachov
Original assignee: Taganrogsky Radiotekhnichesky Institut Imeni VD Kalmykova
Current assignee: Taganrogsky Radiotekhnichesky Institut Imeni VD Kalmykova
Priority date: 1976-12-22
Filing date: 1977-12-20
Publication date: 1978-07-06
Also published as: JPS53101242A; SU732864A1; FR2375655B1; FR2375655A1; US4159529A; GB1565460A; PL203158A1; PL109971B1; JPS573100B2; CA1103807A; DD136317A1

Description

Taganrogaky Radiotekhnichesky Institut imeni V.D. Kalmykova, Taganrog, UdSSR

Addierer für Fibonacci-Codes

Die Erfindung bezieht sich auf digitale Datenverarbeitungsanlagen, insbesondere auf einen Addierer, der die Operation Addition in Fibonacci-Codes vornimmt.

Ein derartiger Addierer kann in Digitalrechnern auf der Grundlage von Fibonacci-Codes verwendet werden.

Es gibt einen Addierer für Fibonacci-Codes (A. P. Stachow, Einführung in die algorithmische Meßtheorie, Moskau, 1977), der einen n-stelligen Halbaddierer enthält, bei dem die mehrstelligen Betrags- und Übertragsausgänge an die Eingänge von Normalisatoren angeschlossen sind, während die Ausgänge dieser Normalisatoren mit den Eingängen des ersten und zweiten Summanden des n-stelligen Halbaddierers (n = Stellenzahl des Codes) verbunden sind. Die anderen Eingänge der Normalisatoren bilden Summandeneingänge des Addierers für Fibonacci-Codes.

53O-(O8O2/l P.72i21-E-6l)-HdSl

80982^/0759

Wesentlich für die Funktion dieses Addierers ist die Mehrfach-Ausführung von Additionsmikrozyklen, bis in der Kombination des Übertrages nur Nullen vorhanden sind ("NullUbertrag"). Jeder Additionsmikrozyklus besteht in der Bildung von Zwischenbetrags- und Übertragscodekombinationen im n-stelligen Halbaddierer und in der Reduzierung der Fibonacci-Codes auf eine Minimal-Form, die in den Normalisatoren erfolgt.

Der beschriebene Halbaddierer für Fibonacci-Codes arbeitet relativ langsam wegen einer großen Zahl von Additionsmikrozyklen. Außerdem hat er eine niedrige Fehlersicherung bzw. Kontrolle (Kontrollvermögen), da bei ihm die Prüfung nur eines Kontrollverhältnisses zwischen den Stellen des Fibonacci-Codes erfolgt, indem, wenn gleichzeitig in jeder i-ten Stelle des Halbaddierers zwei L-übertragssignale aus der (i+l)-ten und (i-2)-ten Stelle auftreten, am Kontrollausgang des Addierers ein Fehlersignal erscheint.

Es ist daher Aufgabe der Erfindung, zur Erhöhung der Arbeitsgeschwindigkeit und zur Verbesserung der Fehlerkontrolle den Addierer für Fibonacci-Codes so aufzubauen, daß die Mehrfachausführung von Additionszyklen ausgeschlossen ist,und mit einem n-stelligen Halbaddierer zu versehen, der die Gewinnung von Zwischenbetrags- und Übertragscodekombinationen zu deren nachfolgender Umsetzung in die Minimalform des Fibonacci-Codes sichert, sowie die Funktionskontrolle mit drei Kontrollverhältnissen zwischen Stellen des Fibonacci-Codes vorzunehmen.

Die Lösung dieser Aufgabe erfolgt erfindungsgemäß durch das Kennzeichen nach dem Patentanspruch 1.

Vorteilhafte Ausgestaltungen der Erfindung sind in den Unteransprüchen angegeben.

8098 2V 0759

Die Erfindung gestattet, die Arbeitsgeschwindigkeit des Addierers durch Ausschluß einer großen Zahl von Additionsmikrozyklen und Zurückführen des gesamten Additionsvorganges auf die Durchführung nur zweier Operationen zu erhöhen:

die Bildung eines Zwischenbetrages und eines Übertrages sowie die Umsetzung der Gesamtheit der Zwischenbetrags- und Übertragscodekombinationen in eine Endbetragscodekombination, dargestellt in Minimalform des Fibonacci-Codes. Die Arbeitsgeschwindigkeit des Addierers wird auch durch die parallele Zwischenbetrags- und Übertragsbildung und die Pibonacci-Code-ümsetzung dank der Informationsumspeichereinrichtung erhöht.

Beim erfindungsgemäßen Addierer ist die Fehlerkontrolle durch Erhöhung der Anzahl der Kontrollverhältnisse in jedem einstelligen Halbaddierer sowie durch die Kontrolle der Informationsspeicherung in dem Umsetzer und der Faltung der Binärstellen in diesen verbessert.

Die Arbeitsgeschwindigkeit des Addierers wird auch durch Festhalten des Zeitpunktes der Additionsbeendigung erhöht, wodurch die für die Addition einer Reihe von Codekombinationen erforderliche mittlere Zeit vermindert wird.

Zum leichteren Verständnis der nachfolgenden Figurenbeschreibung _{8el kurz an} einige Grundbegriffe aus der Theorie von Fibonacci-p-Codes erinnert, die z. B. in der Monographie A. P. Stahow, Einführung in die algorithmische Meßtheorie, Moskau, 1977, dargelegt sind.

80982^/0759

Unter einem n-stelligen Fibonacci-p-Code einer gegebenen natürlichen Zahl N wird deren Darstellung in Form folgender Summe verstanden:

N = ΣΓ H₁ y_p(i) (i)

i = Nummer einer Binärstelle „
aj = Binärziffer an der i-ten Stelle des Codes tf_O(i) ^s Gewicht der i-ten Stelle entsprechend folgender Vorschrift:

0 bei i < O

1 bei i = O (2) Yp(i - 1) + f_p(i - ρ - 1) bei i > O ,

Eine Besonderheit des Fibonacci-p-Codes besteht in der Mehrdeutigkeit der Darstellung jeder natürlichen Zahl N. Z. B. kann die Zahl 10 bei ρ = 1 durch folgende Fibonacci-l-Codes dargestellt werden:

8 5 3 2 1 1 - Stellengewichte 10 0 IQQ

IQO 011
0 110 11

Unter verschiedenen Fibonacci-p-Codes ein und derselben natürlichen Zahl N kann man einen und hierbei einzigen Fibonacci-p-Code ausscheiden, bei dem in einer beliebigen Gruppe aus ρ + 1 hintereinander folgenden Codestellen keine zweite L-Stelle auftritt. Ein solcher Fibonacci-p-Code wird ein normaler (oder minimaler) Fibonacci-p-Code der gegebenen natürlichen Zahl N genannt.

8098 2^/0759

Eine Besonderheit des Fibonacci-p-Codes besteht auch darin, daß bei der Impulszählung der übergang vom normalen Fibonacci-p-Code der Zahl N zum normalen Fibonacci-p-Code der Zahl η ♦ 1 über anormale Fibonacci-p-Codes der Zahl η ♦ 1 erfolgen kann. Der übergang vom normalen Fibonacci-1-Code der Zahl 5¹* zum normalen Fibonacci-1-Code der Zahl 55 geschieht z. B. wie folgt:

55 3Ί 21 13 8 5 3 2 1 1 - Stellengewichte

	1	O	1	O	1	O	1	O	O
O	1	O	1	O	1	O	1	O	1 I
	1	O	1	O	1		1		—J
1°	1	O	1	O	1	1	O	»J O	O
< ο	1	O f	1	Χ— 1	O	O	O	O	O
	1	1	O	O	O	O	O	O	O
	O	O	O	O	O	O	O	O	O

O
O t
1

Durch das Zeichen » _t . wird die Operation einer Faltung der Binärstellen bezeichnet.

10982^/0759

Nachstehend wird die Erfindung durch einen Ausführungsbeispiel unter Bezugnahme auf die beiliegenden Zeichnungen erläutert. Es zeigen:

Fig.l das Blockschema eines Addierers für Fibonacci- -Kodes, gemäß der Erfindung;

Fig. 2 das Funktionsschema eines n-steil igen Halbaadleres, gemäß der Erfindung;

Fig. 2 das Prinzipschaltbild einer Informationsumspeloherungseinrichtung, gemäß der Erfindung;

Fig. 4 das Prinzipschaltbild einer Umsetzungeeinrichtung für Fibonacci-Kodes, gemäß der Erfindung.

Big. 1 zeigt das Blockschema eines Addierers für Fibonacci- -Kodes, das einen n-stelligen Halbaddierer 1 enthält, dessen Eingänge Jeweils als mehrstellige Eingänge 2 und 2 des ersten und zweiten Summanden in Fibonacci-Kodes dienen. Das Blockachema des Addierers enthält auch eine Informationsumspeicherungseinrichtung 4, die einen Steuereingang 5

zum Anlegen eines Informationsumspeicherungssignals und mehrstellige Eingänge 6 und 7 für den Zwischenbetrag bzw. den übertrag, die mit dem Zwlsohenbetragsausgang bzw.dem

8098 2^0759

Ubertragsauagang des n-srt ell igen Halbaddierers 1 verbunden sind, hat. Der Addierer enthält auch eine Umsetzungseinrichtung 8 für Fibonaccl-Kodes, bei welcher der mehrstellige Zwischenbetragseingang 9, der mehrstellige Übertragseingang 10, der üteuereingang 11 und der Kontrolleingang 12 mit

dem Zwiechenbetragsausgang, dem Übertragsausgang, dem Steuerausgang der Informationsumspeichefungselnrichtung 4 bzw. dem Kontrollausgang des n-stelligen Halbaddierers 1 verbunden sind. Der eine Ausgang der Einrichtung 8 ist mehrstellig ausgeführt und dient als Informationsausgang 13 des Addierers, während der andere Ausgang der Hinrichtung 8 als Ausgang 14 für das Additionssendesignal des Addierers dient· Der restilohe Ausgang der Umsetzungseinrichtung 8 dient als Kontroll ausgang 13 des Addierers, der zur Jäntnahme des Fehlersignals, welches von der fehlerhaften Funktion des Addierers zeugt, dient·

flg. 2 zeigt das Funktionsschema eines n-stelligen Fibonaccl-Kodes-Halbaddlerere 1 für η ■ 4· i/er n-stellige HaIbaddierer 1 enthalt vier einstellige Halbaddierer 16^..Ie₄ und ein logisches ODJffi-Glled 17, dessen Ausgang als Kontrollausgang des n-stelligen Halbaddierers 1 dient. Jeder i-te einstellige Halbaddierer Ie₁ (gegebenenfalls ist 1 . 1,2,3,4) umfaßt eine Reihe logischer UND- und ODER-Glieder. Sämtliche einstellige Halbaddierer 16^..Ie₄ sind von gleicher Ausführung

Betrachten wir die Schaltung eines i-ten einstelligen

80982^/0759

- 13 -

Halbaddierers 16J₁, beispielsweise für i = 2, d.h. des zweiten einstelligen Halbaddierers 16₂· Hier dient der eine Eingang des logischen ODER-Gliedes 18₂ für die Summandenanalyse als einstelliger Eingang 2₂ des ersten Summanden des Addierers während der andere Eingang des logischen ODER-Gliedes 18₂ als einstelliger Eingang 3₂ des zweiten Summanden des Addierers dient.Die Gesamtheiten der einstelligen Eingänge 2₁...2^ und 3-,...2λ sämtlicher einstelliger Halbaddierer 16^...16^ bilden jeweils die mehrstelligen Eingänge 2 und 3 (Fig. 1). Die Eingänge des logischen ODER-Gliedes 18₂ (Fig. 2) sind an den einen und den anderen Eingang des logischen UM)-Gl led es 19₂ für die Summandenanalyse, das auch einen Auegang 2O₂ hat, angeschlossen. Der Ausgang 2I₂ des logischen Gliedes 18₂ ist an einen der Eingänge des logischen ODER-Gliedes 22₂ für den Primärbetrag, an einen der Eingänge des logischen ODER- -Gliedes 23₂ für das erste Kontrollsignal und an einen der Eingänge des logischen UM)-Gl iedes 24v> für Übertrags analyse angeschlossen.

Der Ausgang des logischen ODER-Gliedes 22₂ ist an einen der Eingänge des logischen OUER-Gliedes 25₂ ^für den Zwischenbetrag angeschlossen und dient als Zwischenbetragsausgang 26₂ des i-ten, d.h. des zweiten einstelligen Halbaddierers 16₂, der restliche Eingang des logischen ODER-Gliedes 22~ dient als erster Primärübertragselngang 27₂ des zweiten einstelligen Halbaddlerers 16₂ und ist an einen der Eingänge des logischen UWD-Giiedes 28₂ für das erste Kontroll-

8 0 9 8 2ψ/ 0 7 5 9

signal angeschlossen. JJer andere Eingang des logischen UND- -Gliedes 28p let an den Ausgang des logischen ODER-Gliedes 23p gelegt. Der Ausgang des logischen UND-Gliedes 28₂ 1st an einen der Eingänge des logischen üDER-Gliedes 29₂ für die Rontrolle, dessen Ausgang als Kontrollausgang 3O₂ des zweiten einstelligen Halbaddierers 16₂ dient, angeschlossen. Der Kontrollausgang 3O₁ bis -pO^ jedes der einstelligen Halbaddierer 16^ ...16^ iat an einen der Eingänge des logischen ODER-Gliedes 1? angeschlossen. Der eine übriggebliebene Eingang des logischen ODER-Gliedes 29₂ ist an den Ausgang des logischen UND-Gliedes 31p ^für das zweite Kontrollsignal angeschlossen, während der andere übriggebliebene Ausgang an den Ausgang des logischen UND-Gliedes 32p für das dritte Kontrollsignal angeschlossen ist. Der Eingang des logischen UND-Gliedes 31p ist an den Ausgang des logischen UWD-Gliedes 33p ^für den Sekundärübertrag, der als Sekundärübertragsausgang 34p des zweiten einstelligen Halbaddierers 16p dient, angeschlossen. Der andere Eingang des logischen UND-Gliedes 3I₂ ist an den Ausgang des logischen ODER-Gliedes 35₂ für das zweite Kontrollsignal angeschlossen. Der eine Eingang des logischen ODER-Gliedes 35₂ ist an einen der Eingänge des logischen UND-Gliedes 36^ für den übertrag sowie an den Eingang dee Negators 37₂ angeschlossen und dient als Primärbetragseingang des zweiten einstelligen Halbaddierers 16₂, der an den Primärbetragsausgang 26^ des ersten einstelligen Halbaddierers 16^ gelegt ist. Der andere Eingang des logi-

80982^/0759

sehen ODER-Gliedes 35₂ ist an einen der Eingänge des logischen UND-Gliedes 32₂ und an den Ausgang des logischen UND- -Gliedes 36₂, der als Ubertragsausgang 38₂ des zweiten einstelligen Halbaddierers 16₂ dient, angeschlossen. Der restliche Eingang des logischen ODER-Gliedes 35₂ ist an den Ausgang 20 des logischen UND-Gliedes 19₂, der als Primärübe rtragaausgang des zweiten einstelligen Halbaddierers 16p dient, angeschlossen. Der eine übriggebliebene Eingang des logischen Gliedes 25₂ ist an einen der übriggebliebenen Eingänge des logischen ODER-Gliedes 23₂ angeschlossen und dient als erster bekundärübertrageeingang des zweiten einstelligen Halbaddierers 16p» der an den Sekundärübertragsausgang; 3^3 des dritten Halbaddierers 16, angeschlossen ist, der restliche Eingang des logischen ODER-Gliedes 25₂ ist an den restlichen Eingang des logischen UND-Gliedes 24p, an den restlichen Eingang 0?s logischen ODER-Gliedes 23₂ und den Ausgang des logischen ODER-Gliedes 39₂ für Ubertragsanalyse, bei welchem der eine und der andere Eingang jeweils als zweiter Primärübertragseingang und als zweiter Sekundärübertragseingang des zweiten einstelligen rialbaddierers 16„ dienen, angeschlossen. i>er Ausgang des logischen UND-Gliedes 24^ iat «n den restlichen Eingang des logischen UND-Gliedes J56_? und an einen der Eingänge des logischen UND-Gliedes 33₂i dessen anderer Eingang mit dem Ausgang des Negators 3?₂ verbunden ist, angeschlossen. Der Ausgang des logischen ODER-Gliedes 25₂ dient als Zwischen-

8 0 98 2^07 5 9

betragsausgang ⁴K)₂ des zweiten einstelligen Halbaddierers 16p nährend der restliche Eingang des logischen UND-Gliedes 32_P als Übertragseingang des zweiten einstelligen Halbaddierers 16₂, der an den Ubertragsausgang 38^ des (i+l)-ten, d.h. des dritten einstelligen Halbaddierers 16, angeschlossen ist, dient. Der PrimärübertragseIngang 2?₂ des zweiten einstelligen Halbaddierers 16₂ 1st an den Primärüb^rtrtragsausgang dee (i+l)-ten_t d.h. des dritten einstelligen Halbaddierers 16, und an den anderen Primärübertragseingang des (i-l)-ten, d.h. dee ersten einstelligen Halbaddierers 16^ angeschlossen. Der Primarübertrageausgang des (i+l)-ten_f d.h. des dritten einstelligen Halbaddierers 16, ist an einen der Sekundärübertragseingänge dee i-ten, d.h. des zweiten einstelligen Halbaddierers 16₂ und den anderen Sekundärübertragseingang dee (i-l)-ten, d.h. des ersten einstelligen Halbaddierers 16, angeschlossen. Der Primärbetragsausgang 26₂ des i-ten (zweiten) einstelligen Halbaddierers 16₂ ist an den Primarübertragseingang dee (i+l)-ten d.h. des dritten βineteil igen Halbaddierers gelegt. Die-Gesamtheit der Ausgänge 5O₁...38^ aller einstelliger Halbaddierer 16^..1O₄ dient ale mehrstelliger übertragaausgang des n-steiligen Halbaddlerers 1 (Fig.l), während die Gesamtheit der Zwischenbetragsausgänge 4Ο_χ...4Ο₄ (Fig« 2) aller einstelliger Halbaddierer 16^ ...16₄ den mehreteiligen Zwischenbetragsausgang dee η-st ell igen Halbaddierers 1 bilden.

80982^0759

Die logischen ODER-Glieder 18₂,22₂, 25₂ dienen zur Formierung von Primärbetragssignalen und Zw1achenbetragsSignalen des einstelligen Halbaddierers 16₂· Die logischen ODER-Glieder 39₂ und 25₂ sind auch zur Formierung von Zwischenbetragssignalen bestimmt, während das logische Glied 19₂ zur Formierung von Primärübertragssignalen bestimmt ist. Das logische UND-Glied 24_χ und das logische UND-Glied 3€>₂ sind zur Formierung von Ubertragssignalen bestimmt, während die logischen UHD-Glieder 24p und 33? und der Negator 37₂ zur Formierung von Sekundärübertragssignalen dienen. Das logische ODER-Glied 23₂ und das logische UND-Glied 28₂ sind zur Formierung des ersten Kontrollsignals bestimmt. Das logische ODER-Glied 35₂ und das logische UND-Glied 3I₂ dienen zur Formierung des zweiten Kontrollsignals, während das logische Glied 32₂ zur Formierung des dritten Kontrollsignals bestimmt ist. Das logische ODER-Glied 29₂ dient zur Formierung des Kontrollfehlersignals am Kontrollausgang 3O₂ des einstelligen Halbaddierers 16₂· Die einstelligen Halbaddierer 16_λ, 16z und 16^ sind analog dem oben beschriebenen auegerührt·

Fig. 3 zeigt das Funktionsschema einer Informationsumspeicherungseinrichtung 4, die in diesem Falle zwei identische Umspeicherungszellen 4I₁ Und 4I₂ enthält. Die Umspeichtungszelle 4I₂ enthält, zum Beispiel, ein Verzögerungsglied 42₂ zur Impulsverzögerung um die Zeit C » die die Formierungsdauer sämtlicher Auegangssignale in den beiden benachbarten einstelligen Halbaddierern 16, und 16^ (Fig. 2) über-

80982^70759

eteigt, bei welchen die Zwischenbetrags- und Ubertragsausgänge jeweils an die beiden einstelligen Eingänge 6^ und 6₄ und die beiden einstelligen Eingänge 7z und 7₄ der Zelle 4I₂ angeschlossen sind. Die Gesamtheiten der einstelligen Eingänge 6,, 6^, 6g und 6^ und der einstelligen Eingänge 7/.t 7x» 7p ¹^ ^l ^{der 2}^¹¹*^{11 41}2 ¹^ ^¹I bilden d^{eweils den} mehrstelligen Zwischenbetragseingang 6 und den mehrstelligen

Ubertragseingang 7 (Fig. 1) der Einrichtung 4.

Der einstellige Zwischenbetragseingang 6₄ (Fig. 3) bildet einen Eingang des logischen UND-Gliedes 43₂ für den Zwischenbetrag der höchsten Stelle, der einstellige Zwischenbetragseingang 6₂ gilt als Eingang des logischen UND-Gliedes 44₂ für den Zwischenbetrag der niedrigsten Stelle. Die Ausgänge der logischen Glieder 4J₂ und 44₂ bilden den zweistelligen Zwischenbetragsausgang der Umspeioherungszelle 4I₂. Die einstelligen Ubertragseingänge 7^ und 7* gelten jeweils als Eingang des logischen UND-Gliedes 45₂ für den Übertrag der höchsten Stelle und des logischen UND-Gliedes 46₂ für den übertrag der niedrigsten Stelle, deren Ausgänge den zweistelligen Übertragsausgang der Informationsumspeicherungszel-Ie 4I₂ bilden. Die anderen Eingänge uer logischen UND-Glieder 4J₂, 44₂, 45₂ und 46₂ sind an den Ausgang des Verzögerungsgliedes 42₂ gelegt. Der Ausgang des Verzögerungsgliedes 42g ist an den Eingang des Verzögerungsgliedes 42, der Umspeicherungszelle 41^ angeschlossen, während der Ausgang

8 0 9 8 2φ/ 0 7 5 9

des Verzögerungsgliedes 42·^ als Steuerausgang der Unu. sicher ung se inrichtung 4 dient. Die Gesamtheiten der zweistelligen Zwischenbetragaausgänge und der zweistelligen Ubertragsausgänge der Umspeicherungszellen 41, und 4I2 bilden jeweils die mehrstelligen Zwischenbetrags- und Ubertragsausgänge der Einrichtung 4, die zur seriellen Umspeicherung der Information aus dem n-stelligen Halbaddierer 1 (Fig. 1) in die Kodeumsetzungseinrichtung 8, begonnen mit den höchsten Stellen und mit der Formierung der Zwischenbetragssignale und Ubertragssignale an den Ausgängen 4O₁...40^ und 38-^...5O^

der einstelligen Halbaddierer 16^...16^ bestimmt ist.

Fig. 4 zeigt das Funktionsschema einer Fibonacci-Kode-Umsetzungseinrichtung 8, die zur Umsetzung der Zwischenbetrags- und Ubertragskodekombinationen in die minimale Form des Fibonacoi-Kodes für den Endbetrag bestimmt ist. Die Einrichtung 8 enthält (n+1), d.h. fünf gleichartige Umsetzungszellen 47i...47t-» die zur Durchführung der Faltungsoperation in den entsprechenden Stellen der Kodekombination bestimmt sind. Die Informationseingänge 9^...9^ der Zellen 47,...47^ bilden den mehrstelligen Zwischenbetragseingang 9 (Fig. 1) der Einrichtung 8, während die Informationseingänge 10,... 1O₄ (Fig. 4) dieser Zellen 47_χ...47₄ den mehrstelligen Ubertragseingang 10 (Fig. 1) der Einrichtung 8 bilden. Die Informationseingänge 9c und 1O₅ (Fig. 4) der fünften Zelle 47^ sind an die Nullachiene angeschlossen, während die fünfte

80 98 2^/07 5 9

Zelle 47c für die Speicherung und Umsetzung der Kodesteile im Falle, wenn die Anzahl der Kodestellen des iSndbetrages die Zahl der Kodestellen der Ausgangssummanden übersteigt, vorgesehen ist. Die Kontrollausgänge 48^.. 48^ sämtlicher Zellen W₁...47_C sind an die Eingänge des logischen ODER-Gliedes 4-9 für die Kontrolle der Einrichtung 8, an dessen Ausgang ein Funktionsfehlersignal für die der Zellen 47^... 47c formiert wird, angeschlossen. Der erste Kopplungsausgang ^O₁...50c jeder Zelle 47_1#..47_C ist an einen der Eingänge des logischen ODER-Gliedes 51 für die Analyse des Ubergangsvorganges, das zur Formierung eines Signals für den Ubergangsvorgang in der Einrichtung 8 bestimmt ist, angeschlossen. Der Ausgang des logischen ODER-Gliedes 51 ist an den Eingang des Negators 52 und den Eingang des elektrischen Filters 53, dessen Zeitkonstante die maximale Zeit des Ubergangsvorganges in der Einrichtung 8 übersteigt, angeschlossen. Der Ausgang des Filters 53 ist an den restlichen Eingang des logischen ODER-Gliedes 49 gelegt. Der Ausgang des Negators 52 ist mit einem der Eingänge des logischen UND-Gliedes 54 für Additionsende, dessen Ausgang als Ausgang für das Additionsendeslgnal des Addierers dient, verbunden. Der andere Eingang des logischen UND-Gliedes 51 ist an den L-Ausgang Informatlonsumspeioherungsende-Flipflops 55, dessen L-Eingang als Steuereingang 11 der Umsetzungseinrichtung 8 dient, angeschlossen. Jede Umaetzungszelle, zum Beispiel, die Zelle 47₂, enthält ein Zwischenbetrag-Flipflop 56₂ und

80982^/0759

ein Ubertrag-Flopflop 57₂, deren L-Eingänge jeweils als Informationseingänge 9p u*¹⁰* lOo der Umsetzungszelle 47₂ dienen. Der Nulleingang 58₂ des Flipflops 56₂ ist an den Ausgang des logischen UND-Gliedes 59pt das zur Zustandsanalyse des Flipflops 57₂ bestimmt ist, angeschlossen. Der eine Eingang 6O₂ des logischen UND-Gliedes 59₂ ist an den 0-Ausgang des Flipflops 57₂ und sein anderer Eingang 6I₂ - an den 0-Eingang des Flipflops 57₂ und den Ausgang des logischen ODER-Gliedes 62₂, das zur Formierung eines Rückstellsignals für das Flipflop 57p bestimmt ist, angeschlossen. Der eine Eingang des logischen ODER-Gliedes 62₂ ist an den Ausgang des logischen UND-Gliedes 6^₂, das zur Formierung eines Signals zur Faltung der Stellen in der Kodekombination bestimmt ist, angeschlossen. Der Ausgang des logischen Gliedes 6^₂ dient als erster Kopplungsausgang 5O₂ der Umsetzungszelle 47₂. Der erste Eingang des logischen UND-Gliedes 63₂ dient als erster Kopplungseingang aer Zelle 47_P, der an den

einstelligen Betragsausgang 1^₁ der ersten Umsetzungszelle 47₁ gelegt ist. Der andere Eingang des logischen ülieaes 6^₂ dient als zweiter Kopplungseingang 64„ der Zelle 47^,

der an üen zweiten Kopplungsausgang der Zelle 47, angeschlossen ist. Der restliche Eingang des logischen UND-Gliedes 63₂ ist an den L-Ausgang des Flipflops 56₂, der als ein-

8 0 9 8 2^/ 0 7 5 9

stelliger Betragsausgang IJ₂ der zweiten Zelle 47₂ gilt, angeschlossen. Der O-Ausgang des Flipflops 5^₂ ^di-^en* ^als zweiter Kopplungsausgang der Zelle 47₂ und ist an einen der Eingänge des logischen UHD-Gliedes 65₂ für die Kontrolle der Zelle 47p angeschlossen. Der Ausgang des logischen UND-Gliedes 65₂ dient als Kontrollausgang 48₂ der zweiten Zelle 47₂, während der restliche Eingang an den L-Ausgang des Flipflops 57p angeschlossen ist. Der erste Kopplungsausgang 50, der (i+l)-ten, d.h. der dritten Zelle 47^ ist an den dritten Kopplungseingang der (i+2)-ten, d.h. der vierten Zelle 47^, der als Reoheneingang des Flipflops gilt, und an den vierten Kopplungseingang des i-ten, d.h. der zweiten Zelle 47₂, der den restlichen Eingang des logischen ODER-Gliedes 622 bildet, angeschlossen. Der erste Kopplungsausgang 50,

der fünften Zelle 47,- ist an den L-Eingang des Flipflops 60, das auch zur Speicherung der Information im Falle, wenn die Zahl der Kodestellen des Endbetrages die Zahl der Kodestellen der Ausgangssummanden übersteigt, vorgesehen ist. Die einstelligen Ausgänge 13^...1Jc der Zellen 47₁«..47_t- und der Ausgang IJ₆ des Flipflops 66 bilden den mehrstelligen Informationsausgang 13 (Fig. 13) des Addierers, dem die Kodekombination des Endbetrages entnommen wird.

Der Ausgang des logischen ODER-Gliedes 49 (Fig. 4) ist an einen der Eingänge des logischen ODER-Gliedes für die Addiererkontrolle, dessen anderer Eingang als Kontrolleingang der Umsetzungseinrichtung ü für Fibonacci-Kodea dient,

8098 2V0759

angeschlossen. Der Ausgang des logischen UDER-Gliedes 67 dient als Kontroll aus gang des Addierers 15·

Der Addierer für Fibonacci-Kodes funktioniert wie folgt. Die Kodekombinationen der Zahlen in minimaler Form der Fibonacci-Kodes gelangen zu den mehrstelligen Eingängen 2 und des n-stelligen Halbaddierers 1, in dem die Formierung der Kodekombinationen des Zwischenbetrages und des Übertrages von den höchsten Stellen zu den niedrigsten Stellen realisiert wird. Hierbei haben die Kodekombinat ionen des Zwischenbetrages und des Übertrages eine von der minimalen Form unterschiedliche Form. Gleichzeitig mit dem Anlegen der Summandensignale an die mehrstellige Eingänge 2 und 5 wird ein Informationsumspeicherungasignal auf den ^t euer eingang 5 gegeben, mit dessen Eintreffen die Umspeicherungseinrichtung 4 eine übertragung der Information aus dem n-stelligen Halbaddierer 1 in die Umsetzungseinrichtung 8 für Fibonacci-Kodes bewirkt. Die Informationsumspeicherung in der Einrichtung erfolgt seriell, begonnen mit den einstelligen Halbaddierern 16^ und 16^ (Fig. 2), die den höchsten Stellen des Fibonacci-Kodes entsprechen. Mit dem Eintreffen der Kodekombinationen des Zwischenbetrages und des Übertrages in der Umsetzungseinrichtung 8, setzt die letztere die Kodekombinationen in die minimale Form des Fibonacci-Kodes um, die den Endbetrag darstellt. Bei Abschluß der Informationsumspeicherung in der Einrichtung 4 wird an dem ^teuerausgang derselben ein Signal,

8098 2^/07 5 9

das von der Beendigung des Umspeicherungsvorganges zeugt, formiert, welches zum Steuereingang 11 der Einrichtung 8 gelangt und vom Flipflop 55 (Pig. 4) dieser Einrichtung B gespeichert wird. Nach dem Eintreffen des Signals für Beendigung der Umspeicherung und nach Beendigung des Umsetzungsvorganges in der Einrichtung 8 erscheint am Ausgang 14- derselben ein Signal für Additionsende· Bei Entstehung von Punkt Ionsstörungen an dem n-steiligen Halbaddierer 1 (Fig.l) und der Einrichtung 8 wird am Kontrollausgang 15 des Addierers ein L-Signal formiert, das von einem Funktionsfehler im Addierer zeugt.

Die Umsetzung der KodeKombinat ionen des Zwischenbetrages und des Übertrages erfolgt in dem n-steiligen Halbaddierer 1 (zum Beispiel, für η - 4) wie folgt. Bei der Zulieferung an die mehrstelligen Eingänge 2 und 3 der Kodekombinationen des ersten Summanden (zum Beispiel, 1010) und des zweiten Summanden (zum Beispiel, 1010) beginnt die Bildung des Primärbetrages und des Zwischenübertrages in den einstelligen Halbaddierern 16^... 16^ (das Zählen der .titeilen erfolgt von rechts nach links). In dem einstelligen Addierer 16-treten beispielsweise beim Anlegen von L-Signalen an die einstelligen Eingänge 2₂ und 3₂ am Ausgang des logischen ODER-ülledes 18₂ und am Ausgang des logischen UND-Gliedes auf. Das L-äignal vom Ausgang des logischen

ODER-Gliedes gelangt über die logischen ODER-Glieder 22p und 25₂ zum Zwischenbetragsausgang 4O₂ und zum Primärbetragsausgang 26₂ des einstelligen Halbaddierers lb_o -ä

80982>/0759 ^2>
wa

Ausgang 26„ das gleiche Signal zum Primärbetragseingang des dritten einstelligen Halbaddierers 16, gelangt. Das am Ausgang 26p anliegende Signal stellt ein Primärbetragssignal für den zweiten einstelligen Halbadciierer 16„ dar. Das L-i3ignal vom Ausgang des logischen UND-Gliedes 19₂» ^{das ein} Übertragssignal darstellt, gelangt zum Primärübertragse ingany 27i des ersten einstelligen Halbaddierers 16, , wo es über sein logisches ODER-Glied für den Zwischenbetrag (in Fig. 2 nicht gezeigt), welches dem logischen ODER-Glied 22p ähnlich ist, zum Ausgang 26-, und weiter zum Primär bet ragse ingang des zweiten

e
einstelligen Halbaddierers 16p passiert. Über das logische ODER-Glied für das erste Kontrollsignal (in Fig. 2 nicht gezeigt), das dem logischen Glied 25p ähnlich ist, gelangt das gleiche Signal zum Zwischenbetragsausgang 40,. Die Bildung der Zwischenbetragssignale in den einstelligen Halbaddierer 16, , 16, und 16^ läuft auf ähnliche Weise ab, so daß an den Ausgängen 4O₁, 4O₂, 40, und 40^ die Kodekombination LLLL als Resultat zur Verfügung steht. Die Bildung der Ubertragskodekomb!nation geschieht wie folgt. (Es sei bemerkt, daß die Ausgangskode kombination die Form LOLO hat). In dem vierten einstelligen Halbaddierer 16₄ wird vom Ausgang des logischen UND-Gliedes für die Summandenanalyse, das dem logischen Glied 19₂ ähnlich ist, das L-Signal, d.h. das PrimärÜbertragssignal auf den einen Primärübertrageeingang 27-, des dritten einstelligen Halbaddierers 16^ und auf den anderen Primärübertragseingang

8098 2^/075 9

-31- /756832

des zweiten einstelligen Halbaddierers 16₂, d.h. auf den Eingang des logischen ODER-Gliedes 39₂ gegeben. Nach Passieren des logischen ODER-Gliedes 39₂ führt das L-Signal an seinem Ausgang zum Auftreten eines L-Signals am Ausgang des logischen UND-Gliedes 24p, welches seinerseits zum Auftreten eines L-Signals am Ausgang des logischen UND-Gliedes 36₂ und somit auch am Übertragsauegang 3&₂ des zweiten einstelligen Halbaddierers 16^ führt. Eine Formierung von Übertragesignalen in dem vierten, dritten und ersten einstelligen Halbaddierer 16g, 16, und 16^ findet nicht statt, da an den zweiten Primärübertragseingängen dieser einstelligen Halbadα ierer ü-Signale anliegen, deshalb ergibt sich an den Ubertragssausgängen 38^, 38,, 38₂ und 3S₁ die Übertragskodekombination OOLU.

Betrachten wir einen anderen Beispiel für die Addition der Summanden LOLO und LOOO. Die Bildung von Zwischenbetrags- und Übertragssignalen in dem vierten 16^, dritten 16, und ersten 1O₁ einstelligen Halbaddierern läuft auf ähnliche Weise ab.

In dem zweiten einstelligen Halbaddierer 16₂ führt das L-Signal an einem der Eingänge des logischen ODER-Gliedes 18p zur Formierung eines L-Signals am Zwischenbetragsausgang 4O₂. In Anbetracht dessen, daß ein der Ausgangssignale ein O-Signal ist, so liegt am Ausgang des logischen UND-Gliedes 19₂, d.h. am PrimärÜbertragsausgang des zweiten einstelligen Halbaddierers 16₂ und am Primärübertragseingang 2?, des ersten einstelligen Halbaddierers 16, ein O-Signal an. Da an den

80982^*0759

Eingängen 2^ und 3-j O-Signale anliegen, so ergibt nich am Zwischenbetragsausgang 26.. dea eraten einstelligen Halbaddierers 18 ein O-Signal, welchea nach Passieren des Negators 37p des zweiten einstelligen Halbaddierers 18p zum Auftreten eines L-Signals an einem der Eingänge des logischen UND-Gliedes 33p fuhrt. Dem einen Primärübertragseingang 27-, des dritten einstelligen Halbaddierera 16., und dem anderen Primärubertragaeingang dea zweiten einstelligen Halbaddierers 16p wird aus dem vierten einstelligen Halbaddierer 16.. ein L-Signal vom Ausgang des logischen UND-Gliedes für Summandenanalyse, das dem logischen UND-Glied 19p ähnlich ist, zugeführt, so daas am Ausgang des logischen ODER-Gliedes 39₂ ein L-Signal erscheint, das zum Auftreten eines L-Signals am Ausgang des logischen UND-Gliedes 24₂ und folglich am Ausgang des logischen UND-Gliedes 33, das als Sekundärübertragsausgang 34p des zweiten einstelligen Halbaddierers 16p gilt, und mit einem der Ausgänge des logischen ODER-Gliedes für den Zwischenbetrag, das dem ODER-Glied 25₂ ähnlich ist, in Verbindung steht, führt. Daher gelangt das L-Signal vom Ausgang 34p zum Zwischenbetragaausgang 40... Im Ergebnis stehen an den mehrstelligen Übertrags- und Zwischenbetragsausgängen des n-stelligen Halbaddierers 1 die Kodekombinationen 0000 (Obertrag) und LLLL (Zwischenbetrag) zur Verfügung.

Betrachten wir nun die Funktionskontrolle der Schaltung des n-stelligen Halbaddierer3 1 am Beispiel der Addition

8 0 9 8 2ψ/ 0 7 5 9

folgender zwei Fibonacci-KodestOLOO und OLCX). Der in diesem Falle ablaufende Vorgang ist den vorstehend betrachteten ähnlich, so daß folglich am Primärübertragseingang 2?₂ ^ein L-äignal anliegt, das zu einem der Eingänge des logischen UND-Gliedes 28_g passiert. Erscheint an einem der Eingänge 2₂ bzw. 3p fehlerhaft ein L-Signal, so gelangt es auch zu einem der Eingänge des logischen UND-Gliedes 28₂, uemzufolge vom Ausgang dieses logischen UND-Gliedes 28₂ ein L-Signal, das ein Dehlersignal darstellt, zum Ausgang des logischen ODER- -Gliedes 29₂ für die Kontrolle passiert. Erscheint fehlerhaft ein L-Signal am Üekundärübertragsausgang 39^ des vierten einstelligen Halbaddierers 16^ bzw. an seinem Primärübertragsausgang, das mit dem Eingang 27z und dem logischen Glied 39p in Verbindung steht, so tritt am Ausgang des logischen ODER-Gliedes 39₂ ein L-Signal auf, das das logische ODER-Glied 23_χ, das logische UND-Glied 28₂ und das logische ODER-Glied 29₂ passiert und zum Auftreten eines L-Signalβ, d.h. eines Fehlersignals am Kontrollausgang 3O₂ führt.

Tritt fehlerhaft ein L-Signal am'Sekundärübertragsausgang 34z des dritten einstelligen Halbaddierera 16, auf, so führt es nach Faseieren des logischen ODER-Gliedes 23₂, des logischen UND-Gliedes 28₂ und des logischen ODER-Gliedes 29₂ zum Erscheinen eines L-Signala, d.h. eines Fehlersignals am Kontrollausgang 3O₂.

Ss sei bemerkt, daß das Vorhandensein eines Negators 37_P und das Vorliegen einer Kopplung zwischen dem Ausgang des

80982^0759

logischen UND-Gliedes 19₂ und dem Primärbetragsausgang 26, über das logische ODER-Glied für den Primärbetrag des ersten einstelligen Halbaddierers 16^, das dem logischen Glied 2^₂ ähnlich ist, schließt die Möglichkeit eines gleichzeitigen Auftretens von L-Signalen am ^ekundärübertragsausgang 3^₂ und zumindest an einem der Eingänge des logischen ODER-Gliedes 35₂ aus. Erscheinen dagegen infolge einer Störung in der Schaltung L-Signale gleichzeitig am Ausgang 3^₂ und zumindest an einem der Eingänge des logischen ODER-Gliedes 35₂» so gelangt in diesem Falle das L-Signal über das logische UND-Glied 3I₂ und das logische ODER-Glied 29₂ zum Kontrollausgang 3O₂*

Ee sei auch bemerkt, daß es bei ordnungsgemäßer Funktion des n-steiligen Halbaddierers 1 bei der Addition von Fibonacci -Kodes in minimaler Form unmöglich ist, daß gleichzeitig L-Signale, beispielsweise an den Ausgängen 3^₂ und 3&z des zweiten und dritten einstelligen Halbaddierers 16p und 16, erscheinen. Falls infolge einer Funktionsstörung in der Schaltung die erwähnten L-Signale gleichzeitig auftreten, so erscheint am Ausgang des logischen UND-Gliedes 32₂ ein L-Signal, das nach Passieren des logischen ODüK-Gliedes 29₂ am Kontrollausgang 3O₂ als Fehlersignal erscheint, während das Auftreten eines Fehlersignal^ zumindest an einem der Kontrollausgänge 3Oj...30^ zum Auftreten eines L-Signals am Ausgang des logischen ODER-Gliedes 17, der als Kontrollaus-

00982^0759

gang dee η-stell igen Halbadd leres 1 dient, führt.

Die Informationaumspeicherungseinrichtung funkt ioniert wie folgt. Die Zwischenbetrags- und Übertragskodekombinationen gelangen zu den mehrstelligen Eingängen 6 und 7 der Einrichtung 4. Betrachten wir die Umspeicherung der Ubertragskodekombination 0OLO und der Zwischenbetragskodekombination LLLL aus dem ersten Beispiel. Auf. den Steuereingaiig 5 wird ein Umspeicherungssignal gleichzeitig mit dem Eintreffen der Summandenkodekombinationen an den mehreteilIgen Eingängen 2 und J gegeben. Am Ausgang des Verzögerungsgliedes 42₂(Fig.3) und folglioh an den Eingängen der logischen Glieder 43₂, 44₂, 45p und ^o ^erscheint das Steuersignal nach einer Verzöger ungs zeit L· , die die zur GenInnung der Werte zweier höchster Stellen in dem vierten 16^ (Fig. 2) und dritten 16, einstelligen Halbaddierer erforderliche Zeit übersteigt. Nach Abschluß der Bildung der Signale 00 und LL der höchsten Zwischenbetrage- und Ubertragsstellen gelangen die letzteren auf die einstelligen Eingänge 6^, 6, (PIg. 3) und 7₄, 7, der Umspeicne rungszelle 4I₂ und folglich auf die Eingänge der logischen UND-Glieder 43₂, 44₂, 45₂ und 46₂· Auf die anderen Eingänge der gleichen logischen UND-Glieder 43₂...46₂ wird nach einer Zeit L- ein L-Signal vom Ausgang des Verzögerungsgliedes 42p gegeben, so daß eine genaue Reproduaierung der Eingangsinformation an den Ausgängen der logischen UND-Glieder 4^₂ ...46₂ stattfindet. Das gleiche L-Signal vom Ausgang des Verzögerungsgliedes 42₂ löst das Verzögerungsglied 42,

aus, an dessen Ausgang nach der Zeit i'auch ein L-Signal

8098 2^/07 5 9

erscheint und eine Umspeicherung des Übertragssignals LO und des Zwiachenbetragasignals LL der niedrigsten Stellen stattfindet. Somit erscheint die Information an den Ausgängen der Zellen 41p und 41-ι mit einer Verschiebung um die Zeit Ό , Das L-Signal vom Ausgang des Verzogerungsgliedes 42.. erscheint in einer Zeit 2 £" nach dem Eintreffen des Signals am Cteuereingang 5 am Steuerausgang der Einrichtung 4 und folglich am Steuereingang 11 (Fig. 1) der Einrichtung 8. Nach dem Eintreffen deB übertragsaignala 00 und des Zwischenbetragssignals LL an den Eingängen 3. und 9^t 10- und 10- der Umsetzungszellen 47- (Pig. 4) und 47-, der Einrichtung 8 beginnt in den erwähnten Zellen die Umsetzung der Kodekombinationen in die minimale Form des Pibonacci-Kodes. Die Umsetzung besteht in der Durchführung einer Faltung der höchsten (dritten und vierten) Stellen der ZwischenbetragBkodekombination zur fünften Stelle OLL, welcher die

♦-υ

fünfte Zelle 47c entspricht. Mit Zeichen tu wird die FaltungBoperation bezeichnet. Beim Eintreffen eines L-Signals an den-Eingangen der Flipflops 56- und 56., erscheinen an deren L-Ausgängen L-Signale, die nach Passieren des ODER-Gliedes 63 und des UND-Gliedes 62 der Zelle 47*, der logischen Glieder 63o und 62~ der Zelle 47-j zu den Eingangen 61- und 61., der logischen UND-Glieder 59* und 59₃ gelangen, an deren anderen Eingängen 60- und 60-, ein L-Signal von den O-Ausgängen der Flip-flop 57* und 57-, anliegen, demzufolge an den Ausgängen der logischen Glieder 59* und 59-j L-Signale

80982^/07

formiert «erden, die beim Anlegen an die Nulleingänge 58^ und 58, der Flipflops 56^ und 56, diese in den O-Zuatand kippen. Das vom Ausgang des logischen UND-Gliedes 63^ kommende L-Signal wird nach dem Eintreffen am Recheneingang des Flipflops 56c der fünften Zelle *»?,- von diesem gespeichert und nach Fassieren des logischen ODER-Gliedes 51 von dem Negator 52 in ein O-Signal umgesetzt; welcher das Auftreten eines L-Slgnals am Ausgang des UND-Gliedes 54, d.h. eines Additions beendigungselgnals am Ausgang 14 verbietet. Nach Ablauf der Faltung der beiden höchsten Stellen LL der Zwischenbetrags kodekomb!nation «erden in die Flipflopt» 66, 56,-, 56^ und 56, jeweils die Werte OLLL eingespeichert, die zu den einstelligen Betragseingängen 13g» ^3c» 13^. und 13z gelangen. Nach einer Verzögerungszeit u ab dem Eintreffen der Zwischenbetrags8ign4L«und dem übertragen auf die Eingänge 9₄,9τι10₄, 10, werden auf die Eingänge 9₂ und 9^ die Signale der restlichen zwei Stellen des Zwischenbetragskodes LL und auf die Eingänge 1O₂, 1O₁ - die Signale der restlichen zwei Stellen des Übertragskodes LO gegeben. Gleichzeitig trifft.vom Ausgang der Einrichtung 4 (Fig.l) an dem Steuereingang 11 Jer Einrichtung 8 ein L-Signal für Umspeioherungsende ein, welches das Flipflop 55 (Flg. 4) in den L-Zustand kippt, was zum Auftreten eines L-Signals an einem der Eingänge des logischen UND-Gliedes 54 führt, beim Eintreffen der Zwischenbetrags- und Übertragssignale werden die Flipflops 56₂, 57₂f 56_χ in den L-Zustand gebracht, während das Flipflop

8098 2^/0759

57_± im O-Zustand bleibt. Am Eingang 6O₂ des logischen UND-Gliedes 59₂ liegt an O-Üignal vom O-Ausgang des Plipflops 57₂ an, welches das Auftreten eines L-Signals am Ausgang des logischen UND-Gliedes 59₂ verbietet. Da sich das Flipflop 65, im O-Zustand befindet, so liegt an seinem O-Ausgang und folglich auch an dem Eingang 64₂ und dem entsprechenden Eingang des logischen UND-Gliedes 6^₂ ein L-üignal'an. Da von den L-Ausgängen der Plipflops 56₂ und 56^ auf die restlichen Eingänge des logischen UND-Gliedes 63₂ L-Signale gegeben «erden, so liegt am Ausgang desselben auch ein L-Signal an, welches über das logische ODER-Glied 62₂ zum O-Eingang des Plipflops 57₂ gelangt und dieses in den O-Zustand kippt. Das L-Signal vom Ausgang des logischen Gliedes t>3₂ gelangt auch zum Eingang des logischen Gliedes 62-^ der Zelle 4?₁ und von seinem Ausgang - zum Eingang des logischen UND-Gliedes 59^, bei welchem am anderen Eingang auch ein L-Signal vom O-Ausgang des Plipflops 57^ anliegt. Demzufolge erscheint am Ausgang des logischen UND-Gliedes 59_X ein L-Signal, welches zum O-Eingang des Plipflops 56_χ gelangt und dieses in den O-Zustand kippt. Darüber hinaus trifft das L-Signal vom ersten Kopplungsausgang 50_p der Zelle 4·7₂ an dem Recheneingang des Plipflops 56, der dritten Zelle 47^ ein und kippt das Plipflop 56, in den L-Zustaad. Das gleiche L-Signal vom ersten Kopplungsausgang 5O₅ gelangt zu einem der Eingänge des logischen ODER-Gliedes 51

8 0 9 8 ΐψ/ 0 7 5 9

Z756832

und zum Negator 52, wobei ein O-Signal an seinem Ausgang erscheint. Dieses O-üignal gelangt zum logischen UND-ülied i?4, so daß am Ausgang 14 kein Additionsbeendicungssignal anliegt. Zu dieser Zeit ist in den Flipflops £6 und 56c··.5^₁ die Kodekombination OLOLLO und in den Flipflops 57t·».57^ - die Nullkodekombination 00000 eingeschrieben, so daß an den Eingängen 60^..6Ou der logischen UND-Glieder 59₁...59^ ein L-Signal anliegt. Die in den Flipflops 56₄,56₅und 56₂ der Zellen 47^,47_Z und 47₂ eingeschriebene Kodekombination OLL unterscheidet sich von der minimalen Form des Fibonacci- -Kodes. Es entsteht folglich die Faltungsbedingung für diese Stellen. Die Faltung läuft annlich wie vorstehend beschrieben ab, so daß im Ergebnis in den Flipflops 66, 56,-...56^ die Kodekombination OLLOOO eingeschrieben ist. iirneut ist die Bedingung zur Faltung der fünften und vierten stelle zur sechsten Stelle, welchem das Flipflop 66 mit an den ersten Kopplungsausgang 50. der fünften Zelle 47,- angeschlossenen L-Eingang entspricht, erfüllt. Die Faltung läuft auf oben beschriebene Weise ab und im Ergebnis nimmt die Kodekombination die Form L00000 an, was der minimalen Form des Endbetrages im Fibonacci-Kode entspricht. In der Regel liegt bei dem FaItungsVorgang zumindest an einem der ersten Kopplungsausgänge 5O_lf5O₂» 50,, 5O_21- und 50c ein L-Signal an, das über das logische ODER-Glied 51 zum Eingang des Na^ators 52 gelangt. Deshalb liegt am Eingang des logischen UND-Gliedes 54, der mit dem Ausgang des Nagators 52 in

80982^/0759

Verbindung steht, während der Faltung stets ein O-Signal an, welches das Auftreten eines L-Signals am Ausgang 14 für Additionsende verbietet. Nach Beendigung der Umsetzung, d.h. nach der Durchführung aller Faltungen, erscheinen an allen ersten Kopplungsausgängen 50^...5Oj- O-Signale, demzufolge am Ausgang 14 ein Signal für Additionsende erscheint, welches das Lesen der Information an dem mehrstelligen Informationsausgang 15 (Fig.l) gestattet.

Die Funlctionkontrolle an der Einrichtung geschieht wie folgt. Eine der Bedingungen für ein ordnungsgemäßen Arbeiten des erfindungsgemäßen Addierers ist das unbedingte Vorliegen eines O-Ubertragssignals beim Vorliegen eines O-Zwischenbetragssignals in ein und derselben Stelle. Bei Nichterfüllung dieser Beeingung erscheinen an den Eingängen der logischen UND-Glieder 6^₁...56^ (Fig. 4),die mit den O-Ausgängen der Flipflops 5^1...56,- und den ö-Ausgängen der Flipflops 57τ···57α verbunden sind, L-Signale, was zum Auftreten von L-iiignalen an den Kontroilausgängen 48,...4Oj- der Zellen ^₁...47,- führt. Über die logischen ODER-Glieder und 67 gelangt dieses Signal zum Kontroll ausgang 15, was von einer Funktionsstörung am Addierer zeugt.

Bei der Einrichtung 8 ist auch eine Kontrolle des FaI-tungEVorgaiiges möglich. Wenn zumindest an einem der ersten Koi.'iilungauiiöKengr J)O₁ ...M^ ein stetigen Signal anliegt, duruen Dauer die maximale zur Durchführung aller Faltungen

IS Ί

/07 Ι, Π

-Hl-

erforderliche Zeit übersteigt, so gelangt es über das logische ODER-Glied 51 zum Eingang des elektrischen filters 53 und erscheint nach einem Zeitintervall, das durch die Ze it konstante des Filters 53 bestimmt wird, an seinem Auegang und folglich am Kontrollausgang 15 des Addierers.

8 0 9 8 2f / 0 7 5 9

Lee te· r s e

ite

Claims

Addierer für Fibonacci-Codes,

der einen n-stelligen Halbaddierer mit zumindest zwei mehrstelligen Eingängen zur Eingabe der Summanden in Minimalform der Fibonacci-Codes enthält,

dadurch gekennzeichnet,

daß verbunden sind:

ein mehrstelliger Zwischenbetrags- und ein mehrstelliger Ubertragsausgang des mehrstelligen Halbaddierers (1) mit einem mehrstelligen Zwischenbetragseingang (6) bzw. einem mehrstelligen Obertragseingang (7) einer Informationsumspeichereinrichtung (M),

ein mehrstelliger Zwischenbetrags- und ein mehrstelliger Übertragsausgang sowie ein Steuerausgang der Informationsumspeichereinrichtung (¹O mit einem mehrstelligen Zwischenbetragseingang (9), einem mehrstelligen Übertragseingang (10) bzw. einem Steuereingang (11) eines Fibonacci-Code-Umeetzers (8),und

ein Kontrollausgang des n-stell-igen Halbaddierers (1) (n = Code-Stellenzahl) mit einem Kontrolleingang (12) des Fibonacci-Code-Umsetzers (8) (Fig. 1).

53O-(O8O2/l P.

80982f/0759

2. Addierer nach Anspruch 1,

dadurch gekennzeichnet,

daß der n-stellige Halbaddierer (1) η gleichartige einstellige Halbaddierer (I6₁...l6 ) enthält, von dessen jedem angeschlossen sind:

ein Kontrollausgang (30^) an einem Eingang eines ODER-Gliedes (17) des n-stelligen Halbaddierers (1),

ein Primärübertragsausgang des i-ten einstelligen Halbaddierers (l6_i)(i = 1, 2, ... n) an einem der Primärübertragseingänge (27^₁) des (i-l)-ten einstelligen Halbaddierers (16. *) und an einem weiteren Primärübertragseingang des (i-2)-ten einstelligen Halbaddierers

ein Sekundärübertragseingang (3¹^) des i-ten einstelligen Halbaddierers (16.) an einem der Sekundärübertragseingänge des (i-l)-ten einstelligen Halbaddierers (16.^_-1) und einem weiteren Sekundärübertragseingang des (i-2)-ten einstelligen Halbaddierers (l6._₂), sowie

ein Übertragsausgang (38p und ein Primärbetragsausgang (26^) des i-ten einstelligen Halbaddierers (16.) am Übertragseingang des (i-l)-ten einstelligen Halbaddierers (¹^_-1) bzw. am Primärbetragseingang des (i+1)-ten einstelligen Halbaddierers (l6_i+1x(Fig. 2).

8098 2^/0759

Addierer nach Anspruch 2,

dadurch gekennzeichnet,

daß der i-te einstellige Halbaddierer (16.) ODER-Glieder, UND-Glieder und ein NICHT-Glied (37_±) enthält, wobei angeschlossen sind:

der eine und der andere Eingang eines ODER-Gliedes (l8j) für Summandenanalyse am einen bzw. anderen Eingang eines UND-Glieds (19j) für Summandenanalyse,

der Ausgang (21^) des ODER-Gliedes (l8_i) für Summandenanalyse an einem Eingang eines ODER-Gliedes (22.) für Primärbetrag, eines ODER-Gliedes (23^) für erstes Kontrollsignal und eines UND-Gliedes (2M.) für Übertragsanalyse,

der Ausgang des ODER-Gliedes (22.) für Primärbetrag, der einen Zwischenbetragsausgang (26.) des i-ten einstelligen Halbaddierers (16.) bildet, an einem Eingang eines ODER-Gliedes (25^ für Zwischenbetrag,

der andere Eingang des ODER-Gliedes (22_i) für Primärbetrag, der einen Primärübertragseingang (27.) des i-ten einstelligen Halbaddierers (16.) bildet, an einen Eingang eines UND-Glieds (28_i) für erstes Kontrollsignal,

dessen anderer Eingang am Ausgang des ODER-Gliedes (23^ für erstes Kontrollsignal, dessen Ausgang an einem Eingang eines ODER-Gliedes (2<K) für Kontra¹ Ie, dessen Ausgang einen Kontrollausgang (30^) des einstelligen Halbaddierers (16^ bildet,

zwei weitere Eingänge des ODER-Glieds (29p für Kontrolle am Ausgang eines UND-Gliedes (31^) für zweites Kontrollsignal bzw. am Ausgang eines UND-Gliedes (32.) für drittes Kontrollsignal,

ein Eingang eines UND-Gliedes (31^) für zweites Kontrollsignal am Ausgang eines UND-Gliedes (33·) für zweiten übertrag, der einen Sekundärübertragsausgang (3¹J.) des einstelligen Halbaddierers (16^ bildet,

ein anderer Eingang des UND-Gliedes (31·) für zweites Kontrollsignal am Ausgang eines ODER-Gliedes (35_i) für

80982^/0759

zweites Kontrollsignal,

dessen einer Eingang, der einen Primärübertragseingang des i-ten einstelligen Halbaddierers (16.) bildet, an einem Eingang eines UND-Gliedes (36.. ) für übertrag und am Eingang eines NICHT-Glieds (37·) und

dessen anderer Eingang an einem Eingang des UND-Gliedes (32^) für drittes Kontrollsignal und am Ausgang des UND-Gliedes (36^) für übertrag, der einen Übertragsausgang (38^) des i-ten einstelligen Halbaddierers (16.) bildet,

ein weiterer Eingang des ODER-Gliedes (35j) für zweites Kontrollsignal am Ausgang des UND-Gliedes (19.) für Summandenanalyse, der einen Primärübertragsausgang des i-ten einstelligen Halbaddierers (16.) bildet,

ein weiterer Eingang des ODER-Gliedes (25·) für Zwischenbetrag, der einen Sekundärübertragseingang des i-ten einstelligen Halbaddierers (16.) bildet, an einem weiteren Eingang des ODER-Gliedes (23.^) für erstes Kontrollsignal,

ein letzter Eingang des ODER-Gliedes (25*) für Zwischenbetrag am letzten Eingang des UND-Gliedes (24.) für Übertragsanalyse, am letzten Eingang des UND-Gliedes (23^) für erstes Kontrollsignal und am Ausgang des ODER-Gliedes (39j_) für Übertragsanalyse, dessen Eingänge die anderen Primärübertrags- bzw. Sekundärübertragseingänge des einstelligen Halbaddierers (16^) bilden,

der Ausgang des UND-Gliedes (2^) für Übertragsanalyse am letzten Eingang des UND-Gliedes (36j) für übertrag und an einem Eingang des UND-Gliedes (33^) für Sekundärübertrag sowie

dessen anderer Eingang am Ausgang des NICHT-Glieds (37_±),

wobei der Ausgang des ODER-Gliedes (25±) für Zwischenbetrag einen einstelligen Zwischenbetragsausgang ) des i-ten einstelligen Halbaddierers (16.) und der

8098 2^/0759

letzte Eingang des UND-Gliedes (32.) für drittes Kontrollsignal einen Übertragseingang des i-ten einstelligen Halbaddierers (16_±) bildet (Pig. 2).

80982^*0759

4. Addierer nach Anspruch 1,

dadurch gekennzeichnet,

daß die Informationsumspeichereinrichtung (4) einen Steuereingang und k gleichartige Umspeicherzellen (41.... 4l_k) enthält,

deren jede ein Verzögerungsglied (42) umfaßt, von dem angeschlossen sind:

der Ausgang an einem Eingang eines UND-Gliedes (43) für Zwischenbetrag der höchsten Stelle, an einem Eingang eines UND-Glieds (45) für übertrag der höchsten Stelle, an einem Eingang eines UND-Gliedes (44) für Zwischenbetrag der niedrigsten Stelle und an einem Eingang eines UND-Gliedes (46) für übertrag der niedrigsten Stelle, wobei bilden:

die anderen Eingänge der UND-Glieder (43, 44) für Zwischenbetrag der höchsten Stelle bzw. Zwischenbetrag der niedrigsten Stelle sämtlicher Umspeicherzellen (41^...4I. den mehrstelligen Zwischenbetragseingang (6) der Informationsumspeichereinrichtung (4),

die anderen Eingänge der UND-Glieder (45, 46) für übertrag der höchsten bzw. der niedrigsten Stelle sämtlicher Umspeicherzellen (4l^...4l. ) den mehrstelligen Übertragseingang (7) der Informationsumspeichereinrichtung (4),

die Ausgänge der UND-Glieder (43, 44) für Zwischenbetrag der höchsten bzw. niedrigsten Stelle sämtlicher Umspeicherzellen (41....41. ) den mehrstelligen Zwischenbetragsausgang der Informationp'Tispeichereinrichtung (4) und

die Ausgänge der UND-Glieder (45, 46) für übertrag der höchsten bzw. niedrigsten Stelle sämtlicher Umspeicherzellen (4l_i...4l_k) den mehrstelligen Übertragsausgang der Informationsumspeichereinrichtung (4),

wobei der Eingang des Verzögerungsgliedes (42 ) der m-ten Umspeicherzelle (4l_m) mit dem Ausgang des Verzögerungs-

8 0 9 8 2+/ 0 7 5 9

gliedes (¹¹S_1n+1) der (m+l)-ten Umspeicherzelle C¹ der Informationsumspeichereinrichtung (¹O verbunden ist,

wobei der Eingang des Verzögerungsgliedes C*2.) der k-ten Umspeicherzelle (^l^) den Steuereingang (5) der Informationsumspeichereinrichtung (¹J) und

der Ausgang des Verzögerungsgliedes (¹^₁) der ersten Umspeicherzelle (¹Il₁) den Steuerausgang der Informationsumspeichereinrichtung (¹J) bildet, mit

"■ bei geradzahligem η

ⁿ⁺ bei ungeradzahligem η

m = 1, 2 ...k (Fig. 3).

8 0 9 8 2>/ 0 7 5

Addierer nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet,

daß der Umsetzer (8) für Fibonacci-Codes ein Speicherflipflop (66) und

zumindest η gleichartige Umsetzzellen (17....1J7 ) enthält,

von denen bilden:

erste Informationseingänge (9·ι · · · 9 ) den mehrstelligen Zwischenbetragseingang (9) Öes Umsetzers (8),

zweite Informationseingänge (1O₁...10 ) den mehrstelligen Übertragseingang (10) des Umsetzers (8) sowie

einstellige Informationsausgänge (13J...13 ) der Umsetzzellen (^/<7₁.. .^7_n) und der L-Ausgang des Speicher-Flipflops (6) den mehrstelligen Informationsausgang (13) des Addierers,

wobei angeschlossen sind:

Kontrollausgänge (¹^₁... Ί8_η) der Umsetzzellen (¹»7₁·.. 47_n) an Eingängen eines ODER-Gliedes (^9) für Kontrolle des Umsetzers (8),

dessen Ausgang an einem Eingang eines ODER-Gliedes (67) für Kontrolle des Addierers,

wobei dessen anderer Eingang den Kontrolleingang (12) des Umsetzers und dessen Ausgang einen Kontrollausgang (15) des .Addierers bildet,

ein erster Kopplungsausgang (50) jeder Umsetzzelle (i<7_i) an einem Eingang des ODER-Gliedes (5D für Kontrolle des Ubergangsvorganges,

dessen Ausgang am Eingang des NICHT-Glieds (52) und am Eingang eines elektrischen Filters (53)>

dessen Ausgang am letzten Eingang des ODER-Gliedes für Kontrolle de» Umsetzers (8),

8098 2V 0759

der Ausgang des NICHT-Glieds (52) an einem Eingang eines UND-Gliedes (5M für Additionsende, dessen Ausgang einen Ausgang (I¹I) für ein Additionsende-Signal bildet,

dessen anderer Eingang am L-Ausgang eines Flipflops (55) für Informationeumspeicherende, dessen L-Eingang einen Steuereingang (11) des Umsetzers (8) bildet,

der erste Kopplungseingang der i-ten Umsetzzelle (47·) am einstelligen Informationsausgang der (i-l)-ten Umsetzzelle (¹^₊₁),

der zweite Kopplungseingang (64.) der i-ten Umsetzzelle (17j) am zweiten Kopplungsausgang der (i+l)-ten Umaetzzelle (^7_i+1),

der erste Kopplungsausgang (50.) der i-ten Umsetzzelle (M7^) am dritten Kopplungseingang der (i+l)-ten Umsetzzelle CWj.«) und am vierten Kopplungseingang der (i-l)-ten Umsetzzelle (^l|7_i_₁N sowie

der erste Kopplungsausgang (5O_n) der Umsetzzelle (l»7 ) der höchsten Stelle am L-Eingang des Speicher-Flipflops (66) (Fig. H).

80982f/0759

Addierer nach Anspruch 5,
dadurch gekennzeichnet,

daß jede Umsetzzelle (47^) ein Zwischenbetrag-Flipflop (5O₁) und ein Übertrag-Flipflop (57_±) enthält,

deren L-Eingänge Informationseingänge (9·, 10.) der Umsetzzelle (¹^) bilden,

wobei angeschlossen sind:

der O-Eingang (58.) der Zwischenbetrag-Flipflops am Ausgang des UND-Gliedes (59^) für Analyse,

dessen einer Eingang (60.) am O-Ausgang des Ubertrag-Flipflops (57^ und

dessen anderer Eingang (61.) am O-Eingang des Übertrag-Flipflops (57·) und am Ausgang des ODER-Gliedes (62_i) der Umsetzzelle (^),

wobei dessen einer Eingang einen vierten Kopplungseingang der Umsetzzelle (^7..) bildet,

dessen anderer Eingang am Ausgang eines UND-Gliedes (63·) für Faltung, der einen ersten Kopplungsausgang (5O₁) der Umsetzzelle (^7_±) bildet,

wobei die ersten zwei Eingänge des UND-Gliedes (63.) für Faltung den ersten bzw. den zweiten Kopplungseingang der Umsetzzelle C*7j) bilden,

der letzte Eingang am L-Ausgang des Zwischenbetrag-Flipflops (56^), der einen einstelligen Betragsausgang (13_±) der Umsetzzelle ^₁) bildet,

der O-Ausgang des Zwischenbetrag-Flipflops (56.), der einen zweiten Kopplungsausgang der Umsetzzelle (^7.) bildet, an einem Eingang eines UND-Gliedes (65.) für Kontrolle der Umsetzzelle (I7_i), dessen Ausgang einen Kontrollausgang (48.^) der Umsetzzelle (^7.) bildet, und der letzte Eingang am L-Ausgang des Übertrag-Flipflops (57_±),

wobei der Recheneingang des Zwischenbetrag-Flipflops einen dritten Kopplungseingang der Umsetzzelle (^7·) bildet (Fig. 1).

8098 2%/ 0759