DE3879373T2

DE3879373T2 - Residuen-arithmetische Rechenschaltung.

Info

Publication number: DE3879373T2
Application number: DE88402676T
Authority: DE
Inventors: Claude-Alain Wambergue
Original assignee: Thomson CSF SA
Current assignee: Thales SA
Priority date: 1987-10-30
Filing date: 1988-10-24
Publication date: 1993-10-14
Anticipated expiration: 2008-10-25
Also published as: EP0314559B1; DE3879373D1; US4949294A; JPH01149129A; FR2622713A1; EP0314559A1

Description

Gegenstand der Erfindung ist hauptsächlich eine Rechenschaltung oder ein Rechner, worin eine residuelle Arithmetik, insbesondere über komplexe Zahlen, Anwendung findet.
Einerseits ist es bekannt, Rechenschaltungen zu verwirklichen, bei denen Basen in positioneller Notation verwendet werden. In einer solchen Basis wird jede ganze Zahl in eindeutiger Weise über die Elemente der Basis zerlegt, die im allgemeinen die aufeinanderfolgenden Potenzen einer ganzen Zahl sind.
Jede Ganzzahl A kann zu einer Basis b in folgender Form angegeben werden:
A = anbn + an-1bn-1 + ...aibi +... + a&sub3;b³ + a&sub2;b² + a&sub1;b + a&sub0;
Es gibt eine zweieindeutige Entsprechung zwischen den ganzen Zahlen und den Mengen von Koeffizienten ai ihrer Zerlegung mit einer gegebenen Basis.
Die Rechenschaltungen auf der Grundlage von Halbleiterbauteilen, die mit positioneller Basis arbeiten, beruhen aus technologischen Gründen hauptsächlich auf der Verwendung der Basis 2. Ihre Arbeitsgeschwindigkeit wird durch die Multiplikationsoperation beschränkt, die in Verschiebungs und Additionsschritte sowie eine Fortschreibung der Überträge zerlegt werden muß.
Andererseits ist die residuelle Arithmetik bekannt, die es ermöglicht, Rechnungen unabhängig über jede Ziffer auszuführen ("digit" in der angelsächsischen Terminologie), deren Umfang geringer ist und die ohne Fortschreibung von Überträgen arbeitet. Sie ist insbesondere in "The Residue Number System" H. L. Garner IRE Trans. Elect. Comp. Juni 1959, beschrieben.
Ferner ist aus dem Artikel von M. A. Bayoumi Nineteenth Asilomar Conference on Circuits, Systems and Computers, 6-8. November 1985 P 48 - 52 bekannt, daß es mit einer residuellen Arithmetik möglich ist, Multiplikationen mit reellen Zahlen zu vereinfachen, indem sie in Additionen von Indizes umgeformt werden. Es findet sich darin jedoch keine Anregung zur Ausdehnung dieser Eigenschaft auf die komplexen Zahlen, wenngleich die Anwendung einer residuellen Arithmetik auf das Gebiet der komplexen Zahlen bereits bekannt war, insbesondere aus der GB-A-1 235 676, welche die Verwendung der Eigenschaften einer residuellen Arithmetik beschreibt, um eine Multiplikation zwischen komplexen Zahlen in eine Menge von Multiplikationen zwischen reellen Darstellungen, die tabelliert werden können, umzuformen.
Der Erfindung liegt hauptsächlich die Aufgabe zugrunde, die Eigenschaften einer besonderen residuellen Arithmetik auszunutzen, um eine Multiplikation zwischen zwei komplexen Zahlen auf eine einfache Addition von Indizes zurückzuführen, die für Rechenschaltungen auf der Grundlage von Halbleiterbauteilen bedeutend einfacher auszuführen ist.
Ihr Gegenstand ist eine Rechenvorrichtung, umfassend:
- eine Digitalcodier-Einheit, die komplexe Zahlen in positioneller Notation in eine residuelle Notation umschreibt;
- eine Recheneinheit, die am Ausgang der Digitalcodierer- Schaltung angeordnet ist und Berechnungen mit den Komponenten der komplexen Zahlen in residueller Notation ausführt; und
- eine am Ausgang der Recheneinheit angeordnete Digitaldecodierer-Einheit, welche die von der Recheneinheit in residueller Notation ausgegebenen Ergebnisse in positionelle Notation umschreibt.
Diese Rechenvorrichtung ist dadurch gekennzeichnet, daß ihre Codierer-Einheit die komplexen Zahlen in eine residuelle Notation mit Resten umschreibt, die modulo Primzahlen mi der Form Mi = 4k + 3, worin k eine ganze positive Zahl ist, berechnet sind.
Gemäß einem vorteilhaften Merkmal enthält die Recheneinheit Mittel, die es ermöglichen, jeder komplexen Zahl einen solchen Index zuzuordnen, daß eine Multiplikation von zwei komplexen Zahlen in zweieindeutiger Weise einer Addition der Indizes entspricht.
Ein besseres Verständnis der Erfindung ergibt sich aus der folgenden Beschreibung und aus den beigefügten Figuren als nicht einschränkende Beispiele, worin:
- die Fig. 1 ein Schema einer ersten Ausführungsvariante der erfindungsgemäßen Vorrichtung ist;
- die Fig. 2 ein Schema einer zweiten Ausführungsvariante der erfindungsgemäßen Vorrichtung ist;
- die Fig. 3 ein Schema einer dritten Ausführungsvariante der Vorrichtung nach der Erfindung ist;
- die Fig. 4 ein viertes Ausführungsbeispiel der erfindungsgemäßen Vorrichtung ist;
- die Fig. 5 das Schema eines Ausführungsdetails der erfindungsgemäßen Vorrichtung ist;
- die Fig. 6 ein Schema eines Ausführungsdetails der in Fig. 5 gezeigten Vorrichtung ist;
- die Fig. 7 ein Schema der Vorrichtungen nach der Erfindung ist;
- die Fig. 8 ein Schema eines bekannten Prinzips ist, welches bei der erfindungsgemäßen Vorrichtung Anwendung findet;
- die Fig. 9 ein Schema eines Ausführungsdetails der Vorrichtung nach der Erfindung ist;
- die Fig. 10 ein Schema eines Ausführungsdetails der Vorrichtung nach der Erfindung ist;
- die Fig. 11 ein Schema eines Ausführungsdetails der Vorrichtung nach der Erfindung ist.
In den Figuren 1 bis 11 werden dieselben Bezugszahlen für die Bezeichnung gleicher Elemente verwendet.
Es folgt zunächst ein Überblick über die üblicherweise in der Mathematik verwendeten Notationen und Definitionen.
Es sei Z die Menge der rationellen ganzen Zahlen als geordnete Menge.
Wir definieren die Division von Ganzzahlen, die auch als euklidische Division bezeichnet wird.
Es seien a und b zwei Ganzzahlen, worin b eine positive Ganzzahl ist. Die Division von a durch b ist definiert durch:
a = b . q + r, 0 ≤ r < b
worin q der Quotient und r der Rest ist.
Wenn r Null ist, sind b und q Faktoren oder Divisoren von a; man sagt: b dividiert a.
Wenn a keine anderen Divisoren als 1 und a hat, ist a eine Primzahl. In allen anderen Fällen ist a eine zusammengesetzte Zahl.
Die größte positive Ganzzahl d, die zwei Ganzzahlen a und b dividiert, wird als GGT von a und b bezeichnet, mit folgender Notation: d = (a, b).
Die grundlegende Theorie der Arithmetik fordert, daß jede Zahl in ein Produkt von Potenzen von Primzahlen faktorisiert werden kann:
a = π i pi ci, worin ci eine ganze Zahl ist,
und diese Zerlegung ist eindeutig.
Wenn zwei Zahlen a und b keine anderen gemeinsamen Faktoren als 1 haben, werden sie als teilerfremd bezeichnet:
d = (a, b) = 1.
Es werden nun die Kongruenz und die Reste definiert.
Die Division einer Ganzzahl a durch eine Ganzzahl b ergibt einen Rest r.
Alle Ganzzahlen, die denselben Rest ergeben, wenn sie durch b dividiert werden, können als zu derselben Äquivalenzklasse für die Äquivalenzrelation gehörig angesehen werden:
a = bq + r
Zwei Ganzzahlen a&sub1; und a&sub2;, die derselben Klasse angehören, werden als kongruent modulo b bezeichnet, und die Äquivalenz wird wie folgt beschrieben:
a&sub1; a&sub2; modulo (oder mod b)
Tatsächlich interessiert man sich nur für den Rest r der Division von a durch b, und dieser wird als Rest von a modulo b bezeichnet, oder auch r = a modulo b.
Mit den Kongruenzen ist die Division nicht definiert. Man kann jedoch etwas diesem nahekommendes definieren, indem folgende Kongruenz betrachtet wird:
a x = c mod b
Man zeigt, daß x nur dann existiert, wenn c durch d dividiert wird, worin d der GGT von a und b ist.
Insbesondere hat, wenn a und b teilerfremd sind (d = 1) die Kongruenz:
a x 1 mod b
eine Lösung, und x wird als Kehrwert von a modulo b bezeichnet, gemäß folgender Notation: a&supmin;¹.
Wenn der GGT von a und b die Größe 1 hat, sagt man, a ist der quadratische Rest von b, wenn:
x² a mod b
eine Lösung hat. Wenn diese Kongruenz keine Lösung hat, ist a ein quadratischer Nicht-Rest von b.
Es werden nun die Gruppen definiert:
A sei eine Menge von Elementen a, b, c ...
Wir nehmen an, daß die Elemente durch die Operation T (oder binäre Relation) verknüpft sind:
c = a q T b, worin a, b und c &epsi; A
Als Gruppe bezeichnet man dann die gesamte Menge A, welche folgende Bedingungen erfüllt: - Assoziativität: - Identität: - Kehrwert:
Wenn die Operation T kommutativ ist (a T b = b T a, a, b &epsi; A), so wird die Gruppe als Abel'sche Gruppe bezeichnet.
Die Ordnungszahl einer Gruppe ist die Anzahl von Elementen dieser Gruppe.
Wir definieren die zyklischen Gruppen:
Wir betrachten eine endliche Gruppe (mit einer endlichen Anzahl von Elementen) und die aufeinanderfolgenden Operationen:
a T a, a T a T a, a T a T a T a, ...
Jede dieser Operationen ergibt ein Element der Gruppe. Da diese endlich ist, wiederholt die Sequenz sich notwendigerweise selbst mit einer Periode r.
r wird als Ordnungszahl des Elements a bezeichnet.
Wenn die Ordnungszahl eines Elements g dieselbe wie die Ordnungszahl der Gruppe ist, so sind alle Elemente der Gruppe durch g erzeugt, mit folgenden Operationen:
g, g T g, g T g T g, ...
In diesem Fall wird g als Erzeugerelement der Gruppe bezeichnet. Die Gruppe ist eine zyklische Gruppe.
Wir definieren nun den Ring und den Körper:
Eine Menge A ist ein Ring für die beiden Operationen T und o, wenn folgende Bedingungen eingehalten sind:
- A ist eine Abel'sche Gruppe für das Gesetz T;
- wenn c gleich a o b, a und b &epsi; A, dann c &epsi; A;
- Assoziativität: a o (b o c) = (a o b) o c;
- Distributivität: a o (b T c) = (a o b) T (a o c) und (b T c) o a = (b o a) T (c o a)
Der Ring ist kommutativ, wenn das Gesetz o kommutativ ist. Der Ring ist ein unitärer Ring, wenn es ein (und nur ein) Identitätselement o für das Gesetz o gibt.
Man verifiziert leicht, daß die Menge der Ganzzahlen ein Ring bezüglich der Addition und der Multiplikation ist.
Wenn man zu der Bedingung hinzufügt, daß jedes Element a einen (und nur einen) Kehrwert besitzt, ( o = u), dann wird der unitäre Ring zu einem Körper.
Man verifiziert leicht, daß für jede ganze Primzahl p die Menge der Ganzzahlen (0, 1, 2, ..., p - 1) einen Körper für die Addition und die Multiplikation modulo p bildet.
Jeder endliche Körper wird als Galois-Körper bezeichnet, in der Notation GF (p).
Es kann gezeigt werden, daß in jedem Galois-KÖrper primitive Wurzeln g (oder Erzeugerelemente) existieren, die mit Ausnahme von e alle Elemente des Körpers durch aufeinanderfolagende Operationen: g o g, g o g o g, ... erzeugen.
Es wird ein kommutativer Körper K angenommen. L ist eine Erweiterung von K, wenn L ein Überkörper von K ist (d. h. ein Körper, wovon K ein Unterkörper ist), wovon jedes Element eine Wurzel einer Gleichung von festem Grad n mit Koeffizienten in K ist. n ist die Ordnung von L in bezug K.
Beispielsweise ist der Körper der komplexen Zahlen C ein Überkörper zweiten Grades des Körpers der reellen Zahlen R, denn jede koinplexe Zahl z = a + ib ist die Wurzel einer Gleichung zweiten Grades mit reellen Koeffizienten:
z² - 2 a z + a² + b² = 0
Wenn K ein endlicher Körper GF (p) ist, beschreibt man die Erweiterungen der Ordnung d von GF (p) wie folgt: GF (pd). Diese Körper haben eine Anzahl von Elementen, die gleich pd ist, worin p eine Primzahl und d eine positive Ganzzahl ist.
Wir definieren nun das Ideal eines Ringes.
Ein Ideal I eines kommutativen Ringes A ist ein solcher Unterring von A, das für ein beliebiges Eleinent y aus I und ein beliebiges Element a aus A das Element a.y stets zu I gehört.
Es sei A ein unitärer kominutativer Ring. Als Hauptideal von A wird die Untermenge von A bezeichnet, die aus Vielfachen eines willkürlichen Elements von A gebildet ist. Ein Ring, der nur aus Hauptidealen besteht, wird als Hauptring bezeichnet.
Der Schnitt von zwei Idealen enthält wenigstens das Element Null (e) und ist ebenfalls ein Ideal.
Die Summe von zwei Idealen ist ein Ideal.
Das Produkt von zwei Hauptidealen I (a) und I (b) ist das Hauptideal I (a.b).
Zwei Ideale werden als fremd oder teilerfremd bezeichnet, wenn ihre Summe der Ring selbst ist.
Ein nicht triviales Ideal (verschieden von {e} oder A) ist maximal, absolut teilerfremd oder teilerfremd, wenn es in keinem anderen Ideal als dem Ring A selbst enthalten ist.
Das Produkt von zwei teilerfremden Idealen ist ihr Schnitt.
Bei einem gegebenen Ideal I in einem kommutativen Ring A und einem Element x von A bezeichnet man als Seitenklasse von I, die durch x gekennzeichnet ist, die Menge von Elementen der Form y + x, worin y ein beliebiges Element von I ist.
Wenn zwei Seitenklassen ein Element gemeinsam haben, stimmen sie überein, was bedeutet, daß jedes Element von A einer und nur einer einzigen Seitenklasse I angehört. Die Summe und das Produkt von zwei Seitenklassen gehören beide zu derselben Klasse, die als Summe oder Produkt der beiden Klassen bezeichnet wird. Die Seitenklassen des Ideals I in bezug auf diese Operationen Summe und Produkt bilden einen Ring, der als Quotientenring von A in bezug auf das Ideal I bezeichnet wird, mit der Notation: A/I. Damit ein Ideal I maximal ist, ist es notwendig und ausreichend, wenn der Quotientenring A/I ein Körper ist.
Die Morphismen sind die Anwendungen zwischen Strukturen.
Das Studium jeder algebraischen Struktur umfaßt die der Morphismen für diese Struktur.
Man versteht unter einem Morphismus (oder Homomorphismus) eine Anwendung einer Menge in einer anderen, welche die "Form" wahrt, d. h. kompatibel mit den Strukturen ist. So gibt es Morphismen zwischen Gruppen, Ringen, Vektorräumen, algebraischen Größen, Beträgen ...
Man verallgemeinert die Definition des Morphismus für die Fälle von Mengen, die mit algebraischen Strukturen versehen sind: es seien E und F zwei Mengen, die mit algebraischen Strukturen (S) und (T) versehen sind. Man nimmt als gegeben an: eine Anwendung, die jedem internen Gesetz , das zu (S) gehört, ein internes Gesetz T zuordnet, das zu (T) gehört, sowie eine Anwendung, die jedem externen Gesetz über E ein externes Gesetz über F zuordnet. Da diese zwei Gesetze denselben Bereich von Operatoren haben, sind die betrachteten Anwendungen bijektiv.
Man sagt dann, daß eine Anwendung f von E in F ein Morphismus bezüglich der Strukturen (S) und (T) ist, wenn für jedes Gesetz über E und für jedes Paar (x, y) von Elementen aus E die Formel
f (x y) f (x) T f (y)
erfüllt ist und wenn für jedes externe Gesetz von E mit dem Bereich Ω von Operatoren und für jedes Element (α, x) von Ω x E die Formel:
f (αx) = α f (x)
erfüllt ist.
Ein bijektiver Morphismus von E über F ist ein Isomorphismus:
die Eigenschaften von E werden auf F "transportiert" (und umgekehrt).
Wir definieren nun die Basen eines Vektorraums.
Es sei E ein endlicher Vektorraum, der über einen kommutativen Körper K definiert ist, und (ai), i = 1, ..., n eine Familie von Vektoren von E. Diese Familie ist eine Basis von E, wenn sie frei und erzeugend ist, was darauf hinausläuft, daß jeder Vektor a von E in eindeutiger Weise geschrieben werden kann:
a = α&sub1; a&sub1; + α&sub2; a&sub2; + ... + αn an αi &epsi; K, i = 1, ..., n
Die Definition einer Basis ist eng verknüpft mit dem Begriff der Summe und der direkten Summe von vektoriellen Unterräumen.
Man sagt, daß die Summe E&sub1; + E&sub2; von zwei vektoriellen Unterräumen E&sub1; und E&sub2; von E direkt ist, und man schreibt sie E&sub1; + E&sub2;, wenn für jeden Vektor dieser Summe die Zerlegung
x = x&sub1; + x&sub2;, x&sub1; &epsi; E&sub1;, x&sub2; &epsi; E&sub2;
eindeutig ist.
Die Zweckmäßigkeit des Begriffes der Basis ist aus dem folgenden Ergebnis ersichtlich:
es seien E und F zwei Vektorräume über K, B = (ej), j = 1, ..., n, eine Basis von E, und (yj), j = 1, 2, ...n, eine Familie von Elementen von F. Es existiert dann eine lineare Anwendung f von E in F und nur eine solche, das für jedes j = 1, 2, ...n.
f(ej) = yj
Wenn darüber hinaus F mit einer Basis C = (gi), i = 1, 2, ..., k, verfügt, so kann man die Vektoren yj durch ihre Komponenten in der Basis C definieren:
Eine lineare Anwendung ist also durch das Datum der Familie αij, für i = 1, 2, ... k und j = 1, 2, ... n, gegeben.
Dies ist das Prinzip der Matrixrechnung.
Wir definieren nun eine Algebra über einen kommutativen Körper.
Diese algebraische Struktur, die oft angetroffen wird, ist eng mit dem Begriff des Vektorraums verknüpft.
Es sei K ein kommutativer Körper. Als Algebra über K bezeichnet man einen Vektorraum E über K, der mit einer bilinearen Anwendung von E x E in E versehen ist. Eine Anwendung von E x E in E ist dasjenige, was als Gesetz der internen Zusammensetzung bezeichnet wird; die Menge E verfügt also über eine algebraische Struktur, die durch das Datum von drei Zusammensetzungs-Gesetzen definiert ist:
- ein Gesetz der internen Zusammensetzung, die Anwendung von E x E in E, in der Notation +;
- ein zweites Gesetz der internen Zusammensetzung, die Anwendung von E x E in E, in der Notation (x, y) T x y;
- ein Gesetz der externen Zusammensetzung, die Anwendung von K x E in E, mit der Notation (α, x) T α x.
Diese drei Gesetze gehorchen folgenden Bedingungen:
- mit dem ersten und mit dem dritten Gesetz versehen ist E ein vektorieller Raum über K;
- für jedes Triplet (x, y, z) von Elementen aus E
x (y + z) = x y + x z
(y + z) x = y x + z x
- für jedes Paar (x, y) von Elementen aus E und für jedes Paar (α, β) von Elementen aus K
(α x) (β y) = (α β) (x y)
Die Definitionen für die Vektorräume sind natürlich auf die Algebren anwendbar. Andererseits sind gewisse Eigenschaften mit dem zweiten Gesetz interner Zusammensetzung verknüpft. So ist eine Algebra kommutativ oder assoziativ, wenn dies für die Multiplikation zutrifft; die Algebra ist unitär, wenn die Multiplikation ein neutrales Element zuläßt.
Eine assoziative Algebra kann als ein Ring (für die beiden Gesetze interner Zusammensetzung) angesehen werden.
Wir definieren nun die Beträge und Algebren über einen unitären kommutativen Ring.
Vom Begriff des Vektorraums gelangen wir zu dem des Moduls, indem einfach der kommutative Körper K durch einen kommutativen unitären Ring A ersetzt wird. Die Zweckmäßigkeit dieser Erweiterung besteht hauptsächlich darin, daß jeder unitäre kommutative Ring als ein Modul über sich selbst angesehen werden kann; in gleicher Weise kann jede kommutative Gruppe als ein Modul über den Ring Z der rationellen Ganzzahlen angesehen werden. Auf diese Weise sind die Methoden der linearen Algebra auf die Theorie der Gruppen und die der Ringe anwendbar.
Man kann auch den Begriff der Algebra über einen kommutativen Körper zu dem der über einen unitären kommutativen Ring definierten Algebra verallgemeinern.
Die Theorie der Modulen weicht deutlich von der der Vektorräume ab, denn bestimmte Existenztheoreme können versagen. Dies ergibt sich aus der Tatsache, daß ein Teil, der auf ein nicht verschwindendes Element reduziert ist, nicht mehr notwendigerweise frei ist.
Ein Modul wird als frei bezeichnet, wenn er wenigstens eine Basis besitzt.
Jede Zahl kann in residueller Notation dargestellt werden, indem der Satz vom chinesischen Rest Anwendung findet.
Gegeben seien die Ganzzahlen m&sub1;, m&sub2; ..., mk, die jeweils zu zweit teilerfremd sind:
(mi, mj) = 1, für i = j.
Das System der linearen Kongruenzen
x xi mod mi, für i = 1, 2, ..., k
besitzt dann eine eindeutige Lösung x modulo q, die gegeben ist:
worin
(was in folgende Form gebracht werden kann:
oder auch
q = mj×Mj , mit j = 1,...,k worin
und worin Mi - 1 in eindeutiger Weise (modulo mi) die Kongruenz
Mi . Mi-1 1 mod mi, erfüllt, für i = 1, 2, ..., k

Darstellung der Zahlen:

Der so formulierte Satz vom chinesischen Rest rechtfertigt die Existenz eine zweieindeutigen Entsprechung zwischen der eindimensionalen Darstellung einer ganzen Zahl x und der mehrdimensionalen Darstellung, welche durch ihren residuellen Ausdruck (x&sub1;, x&sub2;, ..., xk) gebildet ist.
x E> (x&sub1;, x&sub2;, ... xk) mod (m&sub1;, m&sub2;, ..., mk)
Die residuelle Notation ist jedoch schwierig anwendbar, wenn eine Zahl interpretiert oder ihr Vorzeichen geprüft werden soll, oder auch wenn sie mit einer anderen Zahl verglichen werden soll.
Wir definieren die positionelle Notation mit gemischten Basen.
mit : 0 ≤ xi < bi für jedes i
Diese Notation findet überwiegend Anwendung, wenn mit Ganzzahlen gearbeitet wird.
Man nimmt beispielsweise:
x= 13,y=22
m&sub1; = 3,m&sub2; = 5,m&sub3; = 7 und folglich q = 105
In positioneller Notation zur Basis 10
x= 0.10² + 1.10¹ + 3.10
y=0.10² + 2.10¹ + 2.10
In residueller Notation (m&sub1;, m&sub2;, m&sub3;) :
m&sub1; = 3, m&sub2; =5 und m&sub3; = 7 führt zu
M&sub1; = 5.7 = 35 et M&sub1;&supmin;¹ = 2 car M&sub1; . M&sub1;&supmin;¹ 1 mod m&sub1;
M&sub2; = 3.7 = 21 et M&sub2;&supmin;¹ = 1 car M&sub2; . M&sub2;&supmin;¹ 1 mod m&sub2;
M&sub3; = 3.5 = 15 et M&sub3;&supmin;¹ = 1 car M&sub3; . M&sub3;&supmin;¹ 1 mod m&sub3;
Ferner
13 1 mod 3
13 3 mod 5
13 6 mod 7
Daraus ergibt sich durch Rekonstruktion ausgehend vom Satz des chinesischen Restes (Beziehung 1):
x = 1(35.2) + 3(21.1) + 6(15.1)
x = 223
x = 13 mod q = 105
Daraus folgt
x E> (1,3,6) mod (3,5,7)
man findet ferner
y E> (1,2,1) mod 3,5,7
In positioneller Notation zu gemischten Basen mit (b&sub0; = m&sub1;, b&sub1; = m&sub2; und b&sub2; = m&sub3;) ergibt sich gemäß der Definition (Beziehung 2)
x = 13 = 0(5.3.1) +4(3.1) + 1
Daraus folgt
und
y = 22 = 1(5.3.1) + 2(3.1) + 2
Daraus folgt
Man kann auch verifizieren, daß diese Notation eindeutig und geordnet ist.
In der Vorrichtung nach der Erfindung werden also die Zahlen von der positionellen Notation in die residuelle Notation umgeschrieben, man führt die gewünschten Additionen, Subtraktionen und Multiplikationen aus, und anschließend werden die Ergebnisse in positioneller Notation oder eine Notation mit gemischten Basen zum Zweck der Anzeige und/oder der weiteren Verwendung umgesetzt. Es ist vorteilhaft, den größtmöglichen Teil von Operationen vor der Umsetzung auszuführen, um die Anzahl von erforderlichen Umsetzungen für eine gegebene Berechnung zu beschränken.
Die bemerkenswerte Eigenschaft der residuellen Notation rührt daher, daß die Operationen der Addition und Multiplikation unabhängig über jede Ziffer (Rest) ausgeführt werden.
Es seien (m&sub1;, m&sub2;, ... mk), (mi, mj) = 1 ν i ≠ j, q = i 1 mi
Gegeben seien x, y, für die wir die folgende residuelle Notation verwenden:
darin ist x&sub1; der Restmodulo m&sub1;, x&sub2; ist der Restmodulo m&sub2;, und xk ist der Restmodulo mk.
Man kann aber auch für jedes i schreiben:
xi + yi = zi ri . mi (d.h. xi + yi zi mod mi)
Und folglich:
x + y = z&sub1;M&sub1;M&sub1;&supmin;¹ + z&sub2;M&sub2;M&sub2;&supmin;¹ + ... + zkMkMk&supmin;¹ + q i 1 riMi&supmin;¹
denn definitionsgemäß gilt q = mi . Mi
worin zi xi + yi mod mi, für i = 1, 2, ..., k
Also:
Ferner
Aber:
worin K eine Konstante ist
Und folglich:
t = x . y = xiyi MiMiMi&supmin;¹ Mi&supmin;¹ + K'q
worin K' eine Konstante ist.
Andererseits kann geschrieben werden:
MiMi&supmin;¹ = βi . mi + 1, denn Mi . Mi&supmin;¹ 1 mod mi gemäß Definition
Dann:
t = x . y = xiyi (βimi + 1) MiMi&supmin;¹ + K'q
t = x . y = xiyiMiMi&supmin;¹ + xiyiβimiMiMi&supmin;¹ + K'q
und da q = mi . Mi, erhält man:
worin K" eine Konstante ist.
worin ti xi . yi mod mi, für i = 1, 2, ..., k
(wir stellen fest, daß die Unizität folgendes impliziert: 0 ≤ x, y, z, t < q)
Also t = x . y t&sub1;M&sub1;M&sub1;&supmin;¹ + t&sub2;M&sub2;M&sub2;&supmin;¹ + ... + tkMkMk&supmin;¹ mod q
mit ti xi . yi mod mi, für i = 1, 2, ..., k
Man stellt fest, daß in der residuellen Arithmetik keinen Übertrag gibt, worin der Hauptunterschied zu der herkömmlichen positionellen Arithmetik liegt. Bekanntlich können in der letzteren Darstellung die Operationen der Addition und der Multiplikation nicht getrennt über jede Ziffer ausgeführt werden, da eine wichtige Information, der Übertrag, von Ziffer zu Ziffer und in Richtung zunehmender Wertigkeit weitergegeben werden muß.
Es ist zweckmäßig, eine komplexe Arithmetik über einen Ring zu definieren. In diesem Falle sind nicht nur die Summen über jeden Rest unabhängig, sondern die Berechnungen werden dadurch vereinfacht, daß eine komplexe Multiplikation auf eine Indexaddition zurückgeführt wird, d. h. von zwei Ganzzahlen.
Wir sind bisher auf dem elementaren Niveau der Operationen verblieben, indem wir eine Arithmetik entwickelt haben, die für die Darstellung der Zahlen geeignet ist. Wir werden nunmehr die algebraische Sprache verwenden und das Niveau der Operation verlassen, um uns den strukturellen Relationen zwischen Mengen von Zahlen zuzuwenden, die über Gesetzmäßigkeiten ihrer Zusammensetzung wie die Addition und die Multiplikation verfügen.
Es seien R&sub1;, R&sub2;, ..., Rk unitäre kommutative Ringe.
Die direkte Summe (die auch als kartesisches Produkt bezeichnet wird) von R&sub1;, ..., Rk wird geschrieben:
und ist die Menge der K-fachen:
R bildet einen kommutativen unitären Ring für die Operationen der Addition und Multiplikation Komponente für Komponente.
Es sei R ein endlicher kommutativer und unitärer Ring.
R erlaubt dann eine eindeutige Zerlegung in eine direkte Summe von lokalen Ringen.
Ein lokaler Ring ist ein unitärer kommutativer Ring, der ein (und nur ein) maximales Ideal M aufweist. In einem endlichen lokalen Ring enthält M alle Elemente, die Divisoren von Null sind, sowie das Element Null.
Die Zerlegung in lokale Ringe basiert auf dem Satz vom chinesischen Rest, der wie folgt formuliert werden kann:
Es sei Y ein unitärer kommutativer Ring, und A sei ein Ideal von Y, welches in ein Produkt aus untereinander teilerfremden Idealen faktorisiert werden kann:
A = A&sub1;A&sub2; ...Ak, Ai + Aj = Y für i = j
der Quotientenring Y/A ist dann isomorph mit der direkten Summe lokaler Ringe:
Y/A Y/A&sub1; Y/A&sub2; ... Y/Ak
Der Ring residueller Klassen von Ganzzahlen modulo q, R (q) ist zerlegbar in die direkte Summe:
worin (mi, mj) = 1, für i = j
und
Die Zerlegung eines Ringes R in endliche lokale Ringe tritt natürlich auch dann auf, wenn R das homomorphe Bild eines Ringes Y in bezug auf ein Ideal ist, welches in ein Produkt von maximalen Idealen faktorisierbar ist: dies ist der Sonderfall, bei welchem Y der Ring der Ganzzahlen eines Körpers von algebraischen Zahlen ist.
Ein Dedekind-Ring hat die Eigenschaft, daß jedes Ideal in ein Produkt von maximalen Idealen faktorisierbar ist, und tatsächlich ist jedes nicht verschwindende teilerfremde Ideal maximal (der Ring ist "noetherisch"): der Ring der Ganzzahlen eines Körpers von algebraischen Zahlen ist ein noetherischer Dedekind-Ring.
Es seien k ganze Zahlen m&sub1;, m&sub2;, ..., mk, für die (-1) ein quadratischer Nicht-Rest ist.
Wir setzen
gleich, und es sei R (q) der unitäre kommutative Ring der ganzen Zahlen modulo q.
Dann ist (-1) ein quadratischer Nicht-Rest von q.
Es sei eine Lösung von x² -1, die in R (q²) gefunden wird, woraus folgt:
R(q²) = {(a + b), a und b R (q))}
Wir definieren nun die Operationen der Addition und der Multiplikation in R (q²) durch:
(a + b) + (c + d) = (a + c) mod q + (b + d) mod q
(a + b) . (c + d) = (ac - bd) mod q + (ad + bc) mod q
Die Menge R (q²) ist aus ganzen ganzen Gauß'schen Zahlen gebildet und gleicht den gewöhnlichen komplexen Zahlen, mit ² = -1.
Es ist dann R (q²) ein endlicher kommutativer und unitärer Ring.
Es seien k teilerfremde Ganzzahlen m&sub1;, m&sub2;, ... mk in solcher Weise, daß (-1) ein quadratischer Nicht-Rest einer jeden von ihnen ist, und wir ersetzen:
Es sei R (q²) = {a + b, 0 ≤ a, b < q} der zuvor definierte Ring.
Dann ist die direkte Summe der Galois-Körper:
S(q²) = GF(m&sub1;²) GF (m&sub2;²) ... + GF (mk²)
S(q²) = {(α&sub1;, α&sub2;, ..., αk), αi &epsi;GF (mi²), i = 1, 2, ..., k}
daraus werden die Operationen der Addition und der Multiplikation wie folgt abgeleitet:
(α&sub1;, α&sub2;, ..., αk) + (β&sub1;, β&sub2;, ..., βk) = (α&sub1; + β&sub1;, α&sub2; + β&sub2;, ..., αk + βk)
(α&sub1;, α&sub2;, ..., αk) . (β&sub1;, β&sub2;, ..., βk) = (α&sub1; . β&sub1;, α&sub2; . β&sub2;, ..., αk . βk)
Dies ist ein Ring von q² Elementen, der zu dem Ring R (q²) isomorph ist.
Jeder Galois-Körper GF (min) besitzt Erzeugerelemente g, die alle Elemente des Körpers außer dem Element Null durch aufeinanderfolgende Multiplikationsoperationen erzeugen:
g.g, g.g.g, ...
Die Menge {0, 1, 2, ..., mi² - 2}, die mit der Addition modulo (mi²-1) versehen ist, ist eine Abel'sche Gruppe und isomorph zur zyklischen Gruppe [GF(mi²)-{o + o}], die durch g mittels des multiplikativen Gesetzes erzeugt wird.
Wir sehen auch, daß durch eine zweckmäßige Wahl der Ganzzahl q auf dem Ring R (q) verschiedene algebraische Strukturen aufgebaut werden können, die über sehr interessante Eigenschaften verfügen und durch Isomorphie transponierbar sind:
- der Ring R (q²), der als eine über R (q) definierte Algebra angesehen wird (oder als ein Modul über R (q)), besitzt eine orthogonale Basis, die es ermöglicht, die in dieser kanonischen Basis ausgedrückten Elemente von R (q²) Komponente für Komponente abzuarbeiten.
Durch die Isomorphie zwischen der Gruppe von Indizes und der zyklischen Gruppe der Galois-Körper GF (mi²) verfügt man über ein bemerkenswert einfaches Mittel zur Ausführung einer komplexen Multiplikation in einer einzigen reellen Additionsoperation über die Indizes der Elemente;
- der Ring R (q), der als eine Algebra (oder ein Modul) über sich selbst angesehen wird, besitzt gleichfalls eine orthogonale Basis. Folglich sind die Elemente von R (q), die auch der Realteil und der Imaginärteil der komplexen Ganzzahlen von R (q²) sind, in dieser Basis zerlegbar und können komponentenweise getrennt abgearbeitet werden.
In einer über einen Körper definierten Algebra (oder ein Vektorraum über einen Körper) haben die zugeordneten Basen alle dieselbe Dimension. Dies trifft aber für eine über einen Ring definierte Algebra (oder einen Modul) nicht mehr zu. Ein Modul ist frei, wenn er eine Basis besitzt. Im Falle von R (q) und R (q²) gibt es wenigstens eine Basis (algebraische Interpretation des Satzes vom chinesischen Rest). Insbesondere ergibt für R (q) die herkömmliche Formulierung des Satzes die orthogonale kanonische Basis (bi = MiMi&supmin;¹). Es gilt nämlich:
Die positionellen Notationen (zur Basis b oder zu gemischten Basen) definieren weitere Basen, die nicht notwendigerweise die "Dimension" k haben.
Ein Problem bei der Behandlung von komplexen Daten, worin der Realteil und der Imaginärteil in eine nicht-orthogonalen Basis angegeben sind (binäre positionelle Notation für den Rechner, dezimale Notation für den Menschen) wird in herkömmlicher Weise gelöst, ohne die Basis zu wechseln (man bleibt bei der positionellen Notation). Daraus ergibt sich die Notwendigkeit einer schwerfälligen Arithmetik mit Fortschreibung der Uberträge.
Die vorgeschlagene komplexe residuelle Arithmetik besteht also darin, das Problem in eine orthogonale Basis umzusetzen (residuelle Notation), um die "orthogonale" Arithmetik zu nutzen, und man geht noch darüber hinaus, indem die Operation der komplexen Multiplikation auf eine Operation der Addition von Indizes reduziert wird. Sobald also die Größe eines Ergebnisses bestimmt werden soll, oder Ergebnisse verglichen werden sollen, wird erneut die Basis gewechselt, und zu einer positionellen Notation zurückzugelangen (vorzugsweise die zu gemischten Basen, denn sie hat dieselbe Dimension wie die residuelle Notation). Schließlich führt man eine zusätzliche Umsetzung in binäre Notation durch, wenn sich dies als notwendig erweist.
Um eine komplexe Arithmetik auf einem Ring aufzubauen, müssen als Elemente der residuellen Basis die Zahlen mi gewählt werden, für welche die Zahl -1 ein quadratischer Nicht-Rest ist. Die Zahlen sinddurch folgende Formel gegeben:
mi = 4k + 3, worin k eine ganze Zahl ist.
In Fig. 1 ist ein erstes Ausführungsbeispiel eines Rechners 7 gemäß der Erfindung ersichtlich. Der Rechner 7 enthält einen Codiermodul 21, einen Rechenmodul 1 und einen Decodiermodul 22.
Der Codiermodul 21 ist an wenigstens einen Datenbus 33 und/oder 34 angeschlossen. Der Codiermodul 21 ist an den Rechenmodul 1 über wenigstens einen Datenbus 35 und/oder 36 angeschlossen. Der Rechenmodul 1 ist an den Decodiermodul 22 über einen Datenbus 33 angeschlossen. Der Decodiermodul 22 ist an einen Datenbus 39 angeschlossen.
Der Codiermodul 21 empfängt nacheinander über einen einzigen Bus oder gleichzeitig über die beiden Bussysteme 33 und 34 zwei digitale Daten in positioneller Notation.
Der Codiermodul 21 setzt die digitalen Daten aus der positionellen Notation in die residuelle Notation um. Beispielsweise werden die digitalen Daten durch den Codiermodul 21 in binärein Format empfangen und werden in eine residuelle Notation umcodiert, deren Ziffern aus technologischen Gründen binär codiert sind.
Der Rechenmodul 1 empfängt nacheinander über einen einzigen Bus oder gleichzeitig über die zwei Bus Systeme 35 und 36 zwei digitale Daten in residueller Notation. Der Rechenmodul 1 führt mit diesen zwei Daten die Berechnung aus, für die er vorgesehen wurde, beispielsweise die Addition, Subtraktion oder Multiplikation. Bei einer Ausführungsvariante wird die Subtraktion einer Zahl durch die Addition der entgegengesetzten Größe ersetzt.
Der Decodiermodul 22 empfängt über den Bus 33 das Ergebnis der durch den Rechenmodul 1 ausgeführten Berechnung. Dieses Ergebnis wird in residueller Notation empfangen. Der Decodiermodul 22 setzt dieses Rechenergebnis von der residuellen Notation in eine Notation um, deren Weiterverwendung einfacher ist, beispielsweise die Notation mit gemischter Basis, binäre Notation, Hexadezimal-Notation oder dezimale Notation.
Das einfach weiter zu verwendende Ergebnis wird über den Bus 39 ausgegeben.
Vorzugsweise ist der Rechenmodul an einen Steuerbus 37 angeschlossen. In diesem Falle kann mittels desselben Rechenmoduls 1 je nach der über dem Bus 37 empfangenen Steuerung eine Addition, eine Subtraktion oder eine Multiplikation ausgeführt werden, oder auch eine Division, sofern diese Operation in residueller Notation möglich ist.
Die Rechenvorrichtung 7 ist eine Vorrichtung vom Typ Pipeline. Zum kten Taktzyklus bewirkt der Codiermodul 21 die Umsetzung von zwei Daten der Ordnungszahl k aus der positionellen Notation in die residuelle Notation, der Rechenmodul 1 bewirkt eine Operation, z. B. die Addition der zwei digitalen Daten der Ordnungszahlen k-1, während der Decodiermodul 22 die Umsetzung des Ergebnisses der Ordnungszahl k-2 aus der residuellen Notation in die positionelle Notation durchführt.
In Fig. 2 ist eine besonders leistungsfähige Ausführungsform der erfindungsgemäßen Rechenvorrichtung ersichtlich. Diese Vorrichtung ist besonders geeignet für komplexe Berechnungen, für die Verkettungen von Berechnungen sowie für Berechnungen, bei denen dieselben Daten wiederholt verwendet werden. Diese Art von Berechnungen tritt insbesondere bei der digitalen Filterung auf.
Die Rechenvorrichtung nach Fig. 2 enthält außer dem Codiermodul 21, dem Rechenmodul 1 und dem Decodiermodul 22 einen Steuermodul 6.
Der Steuermodul 6 ermöglicht die aufeinanderfolgende Ausführung von mehreren Berechnungen und verwendet beispielsweise mehrfach dieselbe digitale Datengröße in residueller Notation, oder die Verwendung des Ergebnisses einer Berechnung als Datengröße für eine der darauffolgenden Berechnungen.
Die Rechenvorrichtung 7 nach der Erfindung enthält Mittel 41, 42, 382, 402, 403, die es ermöglichen, dem Rechenmodul 1 mehrmals dieselbe Datengröße zuzuführen, ohne daß es erforderlich ist, mehrmals dem Übergang von der positionellen in die residuelle Notation auszuführen.
Die erfindungsgeinäße Rechenvorrichtung enthält beispielsweise zwei Speicher 41 und 42, die zwischen den Codiermodul 21 und den Rechenmodul 1 geschaltet sind.
Beispielsweise empfängt der Speicher 41 die Daten aus dem Codiermodul 21 über einen Bus 35 und gibt Daten an den Rechenmodul 1 über einen Bus 31 ab.
Beispielsweise empfängt der Speicher 42 Daten aus dem Codiermodul 21 über einen Bus 36 und gibt Daten über einen Bus 32 an den Rechenmodul 1 ab.
In zweckmäßiger Weise können die Ergebnisse der Berechnung durch den Rechenmodul 1 an den Eingang dieses Rechenmoduls 1 beispielsweise über einen Bus 380, einen Bus 378 und einen Bus 32 angelegt werden.
In zweckmäßiger Weise können die Ergebnisse der Berechnung durch den Rechenmodul 1 an den Eingang eines der Speicher 41, 42 beispielsweise über den Bus 380, einen Bus 360 und den Bus 36 angelegt werden.
In zweckmäßiger Weise können die Ergebnisse der Berechnung durch den Rechenmodul 1 an einen Arbeitsspeicher 403, der beispielsweise extern zur Rechenvorrichtung 7 vorgesehen ist, beispielsweise über den Bus 33, den Bus 380 und einen Bus 381 abgegeben werden.
In zweckmäßiger Weise können die digitalen Daten in residueller Notation an den Rechenmodul 1 beispielsweise über über einen Bus 381, den Bus 378 und den Bus 32 ausgehend von einem Festwertspeicher 402 oder von dem Arbeitsspeicher 403 abgegeben werden.
Bei einem Ausführungsbeispiel der erfindungsgemäßen Vorrichtung ist der Festwertspeicher 402 extern zu der Rechenvorrichtung 7 vorgesehen.
Bei einer zweiten Ausführungsform ist der in der Rechenvorrichtung 7 enthaltene Festwertspeicher 403 ein programmierbarer Festwertspeicher (PROM, EPROM oder EEPROM gemäß angelsächsischer Terminologie).
In zweckmäßiger Weise können die digitalen Daten in residueller Notation an einen der Speicher 41 oder 42 über den Arbeitsspeicher 402 und/oder den Festwertspeicher 403, beispielsweise über den Bus 381, den Bus 360 und den Bus 36, abgegeben werden.
In zweckmäßiger Weise können die digitalen Daten durch den Codiermodul 21 an den Arbeitsspeicher 43 beispielsweise über den Bus 36, den Bus 360 und den Bus 381 angelegt werden.
Es versteht sich, daß keine Kombination der oben angegebenen Datenwege den Rahmen der vorliegenden Erfindung verläßt.
Bei einem ersten Ausführungsbeispiel sind die Speicher 41 und 42 Pufferspeicher, die imstande sind, jeweils eine digitale Datengröße in residueller Notation zu speichern. Jede neue Datengröße überschreibt die vorausgehende.
Bei einem zweiten Ausführungsbeispiel der erfindungsgemäßen Vorrichtung sind die Speicher 41 und/oder 42 Schieberegister, die imstande sind, n Daten gleichzeitig zu speichern. Bei jedem Steuersignal 60 werden die gespeicherten Digitalwerte um eine Ordnungszahl verschoben, wobei der Digitalwert der Ordnungszahl n auf dem Bus 31 der 32 ausgegeben wird.
In zweckmäßiger Weise kann ein Digitalwert bei Auftreten einer Steuerung 60, die von dem Steuermodul 6 ausgeht, über den Bus 361 in einem beliebigen Schieberegister 41 und/oder 42 gespeichert werden. Wenn beispielsweise an einem der Eingänge des Rechenmoduls 1 über einen Digitalwert in zwei Rechenzyklen verfügt werden soll, so wird dieser Digitalwert in dem Register mit dem Index n-2 des Speichers 41 oder 42 gespeichert, welches an den genannten Eingang des Rechenmoduls 1 angeschlossen ist.
Bei einem dritten Ausführungsbeispiel der erfindungsgemäßen Vorrichtung sind die Speicher 41 und/oder 42 Arbeitsspeicher (RAM in der angelsächsischen Terminologie). Der Steuermodul 6 gewährleistet die Steuerung und Adressierung der Speicher 41 und 42.
In zweckmäßiger Weise ist der Decodiermodul 22 an einen Pufferspeicher 43 über einen Bus 370 angeschlossen. Der Pufferspeicher 43 ermöglicht die Ausgabe der Rechenergebnisse über einen Bus 39.
Der Festwertspeicher 402 ermöglicht die Speicherung der Koeffizienten, die bei der Berechnung verwendet werden sollen. Die Koeffizienten werden nur einmal in die residuelle Notation umgesetzt, bevor die Programmierung des Speichers 402 erfolgt.
Der Arbeitsspeicher 403 speichert Zwischenergebnisse und/oder Daten, die mehrfach benutzt werden sollen, in residueller Notation. Wenn der Codiermodul 21 frei ist, können ferner in dem Speicher 403 in residueller Notation und im Rhythmus ihrer Verfügbarkeit Digitalwerte gespeichert werden, die beispielsweise von einer (nicht gezeigten) Datenerfassungsvorrichtung herrühren, die beispielsweise an den Bus 34 angeschlossen ist.
In zweckmäßiger Weise ist ein Speicher 404 über einen Bus 37 an den Steuermodul 6 angeschlossen. Der Speicher 404 kann Programmbefehle speichern, durch welche die Vorrichtung 7 die gewünschten Berechnungen ausführen kann. Die in dem Speicher 404 gespeicherten Befehle ermöglichen es dem Steuermodul 6, den Datenfluß zu lenken, die Speicher 41, 42, 402 und 403 zum Lesen oder Schreiben anzusteuern und zu adressieren sowie die Operation zu steuern, die durch den Rechenmodul 1 ausgeführt werden soll.
Der Speicher 404 wird beispielsweise durch einen Zähler 600 über einen Bus 405 adressiert. Der Zähler 600 ist beispielsweise in dem Steuermodul 6 enthalten.
Die Architektur des Steuermoduls 6 ist an die Berechnungen angepaßt, die mit der Vorrichtung 7 ausgeführt werden sollen, sowie an die verwendeten Modulen 1, 21 und 22 und an die Speicher 41, 42, 402 und 403 angepaßt.
Der Steuermodul ist in bekannter Weise ausgeführt. Beispielsweise enthält er Ablaufsteuerungen. Diese Ablaufsteuerungen sind beispielsweise in Form von programmierbarer Logik (PLD oder EPLD in angelsächsischer Terminologie) oder in mikroprogrammierter Form ausgeführt.
In zweckmäßiger Weise werden die im Speicher 404 abgelegten Programmbefehle mittels eines geeigneten Assemblers oder Compilers gewonnen, der in bekannter Weise ausgeführt ist.
Für die Klarheit der Figuren sind die Steuerverbindungen 60 nicht eingezeichnet.
In Fig. 3 ist eine Ausführungsvariante der Rechenvorrichtung 7 ersichtlich. Die in Fig. 3 gezeigte Ausführungsvariante enthält vereinfachte Datenwege.
In Fig. 3 ist der Codiermodul 21 in Form von zwei Vorrichtungen 21 dargestellt, deren Aufgabe darin besteht, Digitaldaten in positioneller Notation in Digitaldaten residueller Notation umzusetzen und auf den Bus 33 bzw. 34 auszugeben.
Die erste der beiden Decodiervorrichtungen 21 ist über einen Bus 391 an den Speicher 41 und an einen ersten Eingang des Rechenmoduls 1 angeschlossen.
Die zweite der beiden Decodiervorrichtungen 21 ist über einen Bus 392 an den Speicher 42, an den Decodiermodul 22 und an einen zweiten Eingang des Rechenmoduls 1 angeschlossen.
Der Bus 391 ermöglicht es der ersten Decodiervorrichtung 21, Daten in den Rechenmodul 1 und/oder an den Speicher 41 zu liefern und den bidirektionalen Datenaustausch zwischen dem Speicher 41 und dem Rechenmodul 1 auszuführen.
Der Bus 392 ermöglicht es der zweiten Decodiervorrichtung 21, dem Rechenmodul 1 und/oder dem Speicher 42 Daten zuzuführen sowie einen bidirektionalen Datenaustausch zwischen dem Speicher 42 und dem Rechenmodul 1 auszuführen und Ergebnisse vom Rechenmodul 1 zu dem Decodiermodul 22 zu übertragen.
Der Steuermodul 6 überwacht den Datenaustausch und die durch den Rechenmodul 1 ausgeführten Operationen.
In Fig. 4 ist ein Ausführungsbeispiel der Rechenvorrichtung 7 ersichtlich, die bezüglich des Datenaustausches besonders leistungsfähig ist.
Eine erste Codiervorrichtung 21 kann über den Bus 33 einen ersten Strom von zu verarbeitenden Daten empfangen. Die erste Vorrichtung 21 ist über den Bus 35 an den Speicher 41 angeschlossen. Der Speicher 41 ist über einen Bus 31 an einen ersten Eingang des Rechenmoduls 1 angeschlossen. An den Bus 31 ist über einen Bus 385 ein Festwertspeicher 402 angeschlossen. Eine zweite Codiervorrichtung 21 kann über den Bus 34 einen zweiten Strom von zu verarbeitenden Daten empfangen.
Die zweite Codiervorrichtung 21 ist über einen Bus 36 an den Speicher 42 angeschlossen. Der Speicher 42 ist über einen Bus 32 an einen zweiten Eingang des Rechenmoduls 1 angeschlossen. Der Ausgang des Rechenmoduls 1 ist über den Bus 33 an den Decodiermodul 22 angeschlossen. Der Decodiermodul 22 ist über den Bus 370 an den Pufferspeicher 43 angeschlosen. Der Pufferspeicher 43 ist an einen Bus 39 angeschlossen.
Ein Bus 380 verbindet den Bus 33 mit dem Bus 32 und mit dem Speicher 42.
Ein Bus 383 verbindet bidirektional einen Arbeitsspeicher 403 mit dem Bus 380.
Ein Bus 384 verbindet den Bus 36 mit dem Bus 380 und mit dem Bus 383.
Die Rechenvorrichtung 7, die in Fig. 4 gezeigt ist, ermöglicht den gleichzeitigen Datenaustausch insbesondere zwischen:
- dem Ausgang des Rechenmoduls 1 und dem zweiten Eingang des Rechenmoduls 1 über die Bussysteme 33, 380 und 32 sowie zwischen der Codiervorrichtung 21 und dem Arbeitsspeicher 403 über die Busse 36, 384 und 383;
- dem Ausgang des Rechenmoduls 1 und dem zweiten Eingang des Rechenmoduls 1 über die Busse 33, 380 und 32 sowie zwischen der Codiervorrichtung 21 und dem Speicher 42 über den Bus 36;
- dem Ausgang des Rechenmoduls 1 und dem zweiten Eingang des Rechenmoduls 1 über die Busse 33, 380 und 32 sowie zwischen dem Arbeitsspeicher 403 und dem Speicher 42 über die Busse 383, 384 und 36;
- dem Ausgang des Rechenmoduls 1 und dem Decodiermodul 22 sowie die verschiedenen Austauschvorgänge zwischen den Codiervorrichtungen 21, dem Speicher 42 und dem Speicher 403.
Die durch den Steuermodul 6 überwachten Möglichkeiten des Datenaustausches ermöglichen einerseits die Verwendung einer Codiervorrichtung 21 zur Umsetzung von Digitaldaten in positioneller Notation, die beispielsweise über den Bus 34 von einer Datenerfassungsvorrichtung ankommen, im Rhythmus ihrer Verfügbarkeit in Digitaldaten residueller Notation und ihre Speicherung in dem Arbeitsspeicher 403 sowie andererseits die direkte Ausführung von komplexen Berechnungen durch die Rechenvorrichtung 7; diese Berechnungen können bei der digitalen Filterung sehr nützlich sein, beispielsweise bei der Berechnung der Faltung, den Korrelationsberechnungen oder den Wichtungsberechnungen. Die Berechnungen werden durch den Modul 6 überwacht, indem ein geeignetes Programm ausgeführt wird, das in dem Programmspeicher 404 abgelegt ist.
Gemäß einer nicht dargestellten Ausführungsvariante der erfindungsgemäßen Vorrichtung enthält die Rechenvorrichtung Mittel zum Umcodieren von der residuellen Notation in die Notation mit gemischten Basen (und umgekehrt) sowie Komparatoren. Die Umcodierung in die gemischte Basis (und umgekehrt) ist leichter als die Umcodierung zwischen residueller Notation und positioneller Notation. Bei einer Umcodierung in die Notation mit gemischten Basen wird nämlich die Dimension des verwendeten Raums beibehalten. Die Notation mit gemischten Basen ermöglicht einen Vergleich. Man kann so im Verlauf einer Berechnung verifizieren, ob eine Zahl größer als eine andere Zahl ist oder ob sie kleiner als ein gegebener Schwellwert ist. Für die Fortsetzung der Berechnungen wird die geprüfte Zahl in residuelle Notation umcodiert.
In zweckmäßiger Weise wird die geprüfte Zahl vor ihrer Umcodierung in einem Arbeitsspeicher abgelegt. Bei den anschließenden Berechnungen wird der gespeicherte Wert verwendet.
In Fig. 5 ist ein Ausführungsbeispiel des Rechenmoduls nach den Figuren 1 bis 4 ersichtlich. Der Rechenmodul 1 nutzt die Tatsache aus, daß es in einer residuellen Arithmetik möglich ist, Berechnungen unabhängig über jede Ziffer ohne Fortschreibung von Überträgen auszuführen. Der Rechenmodul 1 enthält also mehrere elementare Rechner 11, die eine Berechnung über eine Ziffer in residueller Notation ausführen sollen.
Der Rechenmodul 1 ist an zwei Busse 31 und 32 angeschlossen. Im Inneren des Rechenmoduls 1 wird jeder dieser Busse verzweigt, um jedem elementaren Rechner 11 die gewünschte Ziffer zuzuführen. Jeder elementare Rechner 11 empfängt zwei Ziffern.
Bei einem ersten Ausführungsbeispiel der erfindungsgemäßen Vorrichtung kann jeder elementare Rechner 11 einen einzigen Operationstyp ausführen, beispielsweise die Multiplikation.
In vorteilhafter Weise können die elementaren Rechner 11 die gewünschte Operation beim Auftreten eines Befehls 60 ausführen, der aus dem Steuermodul 6 empfangen wird. Beispielsweise können die elementaren Rechner 11 auf Befehl eine Addition, eine Subtraktion oder eine Multiplikation ausführen.
Jeder elementare Rechner 11 liefert an den Bus 33 das Ergebnis der ausgeführten Berechnung.
Bei einer Ausführungsvariante enthalten die elementaren Rechner 11 eine Kombinationslogik, welche die gewünschten Berechnungen ausführen kann.
In vorteilhafter Weise werden, sofern die Berechnungen unabhängig über jede Ziffer ausgeführt werden, die Ergebnisse jeder Operation tabellarisch festgehalten. Man kann in der residuellen Arithmetik eine gute Dynamik (über jede Ziffer) erzielen, wenn Festwertspeicher üblicher Kapazität verwendet werden, beispielsweise ROM-Speicher mit 14 Adressenbits.
In Fig. 5 ist ein Beispiel eines elementaren Rechners 11 gezeigt, bei dem tabellarisch definierte Funktionen verwendet werden, und das Prinzip der Berechnung unter Verwendung von im Festwertspeicher abgelegten Tabellen ist in Fig. 8 dargestellt.
Jeder elementare Rechner 11 führt die Berechnungen getrennt über eine Ziffer aus.
Der Rechenmodul 1 enthält eine Anzahl von elementaren Rechnern 11, die ausreicht, um alle Ziffern der größten Zahlen zu verarbeiten, mit denen Berechnungen ausgeführt werden sollen.
Die Tabelle I gibt ein Beispiel für einen Rechenmodul 1, der 16 elementare Prozessoren enthält. Diese 16 elementaren Prozessoren können unter Verwendung von ROM-Speichern mit 14 Adreßbits verwirklicht werden. Die Zahlen mi der Tabelle I sind von der Form mi = 4k + 3, worin k eine positive Ganzzahl ist.
Es versteht sich, daß ein Rechenmodul 1, der eine größere Anzahl von elementaren Rechnern 11 enthält, den Rahmen der Erfindung nicht verläßt. Tabelle I Anzahl der Elemente GF(mi²) Anzahl von Bits zum Codieren von GF(mi²)
Je nach der Dynamik des betrachteten Problems wird ein geeigneter Modul gewählt:
Zur Gewährleistung der Eindeutigkeit des Ergebnisses muß jede seiner Komponenten kleiner als k sein, wodurch der Datendynamik Zwänge auferlegt werden.
In Fig. 6 ist ein Ausführungsbeispiel eines elementaren Rechners 11 ersichtlich, der beim Auftreten von Steuerbefehlen 60 aus dem Steuermodul 6 eine Multiplikation, eine Addition oder eine Subtraktion ausführen kann.
Eine Multiplikation besteht darin, daß jeder Ziffer ein Ordnungszahl-Index in der Gruppe GF (mi²) zugeordnet wird und eine Aufsummierung der erhaltenen Indizes erfolgt.
Zur Gewinnung des Ergebnisses einer Multiplikation muß dann lediglich der Index zu der ihm zugeordneten Zahl konvertiert werden.
In vorteilhafter Weise ist die Index-Zuordnung tabellarisch in einem Festwertspeicher 57 festgehalten.
Der Addierer ist ein Addierermodulo mi²-1.
In vorteilhafter Weise wird derselbe Addierer 55 verwendet, um eine "Additionsoperation" auszuführen und um die Indizes bei einer Multiplikation aufzuaddieren.
In vorteilhafter Weise ist die Addition in einem Festwertspeicher 55 tabellarisch festgelegt.
Wenn jedoch die Addition modulo mi²-1 ausgeführt wird, ist es wichtig, mi²-1 vom Ergebnis abzuziehen, solange dieses größer als oder gleich mi²-1 ist.
Das Beispiel der Addition modulo 8 ist in Tabelle III angegeben.
Ein Beispiel für einen Addierer modulo mi 3 - 1 , d. h. 11²-1 = 120, ist in Fig. 7 gezeigt.
In vorteilhafter Weise können die Busse 31, 313, 314, 315, 316, 32, 323, 324, 325, 326 und 33 die beiden Komponenten einer Zahl, Realteil und Imaginärteil, parallel übertragen.
Der Bus 31 ist einerseits an einen Bus 313 und andererseits an einen Bus 314 angeschlossen.
Der Bus 32 ist einerseits an einen Bus 323 und andererseits an einen Bus 324 angeschlossen.
Die Busse 313 und 323 bilden die Adreßbusse eines Festwertspeichers 57. Der Festwertspeicher 57 enthält tabellarisch die Indizes, die in GF(mi²) einer komplexen Zahl zugeordnet werden sollen, um sie mit einer anderen komplexen Zahl zu multiplizieren.
Ein Beispiel für eine Indizierung ist in den Tabellen II für die ersten drei elementaren Rechner 11 angegeben. Für jeden Rechner ist die Tabelle in aufsteigender Ordnung der Zahlen sowie in aufsteigender Ordnung der Indizes angelegt.
Re bedeutet: Realteil
Im bedeutet: Imaginärteil
Das Element (0+ 0) ist mit einem Index versehen, denn es gehört nicht zur zyklischen Gruppe und muß gesondert behandelt werden. Eine einfache Logik-Testvorrichtung ermöglicht die Erfassung der Multiplikation mit dem absorbierenden Element (0+ 0), wovon das Ergebnis natürlich dieses selbe verschwindende Element (0+ 0) ist. Tabelle II Indizes der Elemente von GF(3²) mit g&sub1; = 1 + i als Erzeugerelement Indizes Indizes der Elemente von GF(3²), geordnet nach aufsteigenden Indizes Indizes Tabelle II Indizes der Elemente von GF(7²), mit g&sub2; = 4 + 1 als Erzeugerelement Indizes Indizes der Elemente von GF(7²), Fortsetzung Indizes Indizes der Elemente von GF(7²), geordnet nach aufsteigenden Indizes Indizes Indizes der Elemente von GF(7²), geordnet nach aufsteigenden Indizes, Fortsetzung Indizes Tabelle II Indizes der Elemente von GF(11²) mit g&sub3; = 2 + 15 als Erzeugerelement Indizes Indizes der Elemente von GF(11²) (Fortsetzung) Indizes Indizes der Elemente von GF(11²) (Fortsetzung) Indizes Indizes der Elemente von GF(11²) (Fortsetzung) Indizes Tabelle II Indizes der Elemente von GF(11²), geordnet nach aufsteigenden Indizes Indizes Indizes der Elemente von GF(11²), geordnet nach aufsteigenden Indizes (Fortsetzung) Indizes Indizes der Elemente von GF(11²), geordnet nach aufsteigenden Indizes (Fortsetzung) Indizes der Elemente von GF(11²), geordnet nach aufsteigenden Indizes (Fortsetzung) Indizes
In Fig. 7 ist ein Ausführungsbeispiel eines Addierers modulo 120 ersichtlich. Der Addierer modulo 120 enthält einen Addierer über sieben Bits 551 und eine Tabelle 57. Der Addierer 551 empfängt über zwei Busse 33 die zu addierenden Zahlen, beispielsweise über sieben Bits. Der Addierer 551 enthält sieben Ausgangsleitungen für das Ergebnis mit den Wichtungen 0 bis 6 sowie R, wobei über die Leitung R der Übertrag weitergegeben wird. Die Leitungen mit den Wichtungen 3 bis 6 sowie die für den Übertrag sind an den Eingang der Tabelle 57 zu 2&sup5; x 4 Oktetts angeschlossen. Die Ergebnisse sind auf den Leitungen mit den Wichtungen 0 bis 2, die direkt aus dem Addierer 551 herausführen, und auf den Leitungen mit den Wichtungen 3 bis 6, die von der Tabelle 57 ausgehen, vorhanden.
In Fig. 8 ist das Prinzip der Berechnung durch Tabellierung einer Funktion dargestellt, welches bei der Vorrichtung nach der Erfindung ausgenutzt wird. Zwei Datenbusse 321 und 322 bilden den Adreßbus 333 eines Festwertspeichers 57. In dem Speicher 57 ist die gewünschte Funktion tabellarisch festgehalten, z. B. die Addition oder die Subtraktion. Das Ergebnis der Operation wird durch den Festwertspeicher 57 auf den Datenbus 323 ausgegeben.
Einige Beispiele von tabellierten Operationen, die ausgeführt werden können, sind in den Tabellen III bis VI angegeben.
Die Tabelle III enthält die Addition modulo 8.
Die Tabelle IV enthält die Addition modulo 3.
Die Tabelle V enthält die Addition modulo 7.
Die Tabelle VI enthält die Addition modulo 11. Tabelle III Tabelle IV Addition modulo m&sub1; = 3 Tabelle V Addition modulo m&sub2; = 7 Tabelle VI Addition modulo m&sub3; = 11
Zur Ausführung der tabellarisch festgehaltenen Umcodierungen wird ein einziger Adressenbus 33 verwendet. Der Wert, welcher umcodiert werden soll, wird auf den Bus 333 gegeben. Der gewünschte Umcodierungswert wird in dem Festwertspeicher 57 an der Adresse gespeichert, die gleich dem umzucodierenden Wert ist.
Die Tabelle VII gibt die Umcodierungswerte für die drei ersten Galois-Gruppen an. Tabelle VII Ganzzahl Rest mod m&sub1; = 3
Die Anwendung der Tabellierung ist jedoch durch die Größe der verfügbaren Permanentspeicher begrenzt.
Um erneut Zahlen in positioneller Notation zu gewinnen, kann dasjenige, was bei der Operation der Basisänderung geschieht, unabhängig von der Art ihrer Verwirklichung formuliert werden.
Es sei: (bj) die orthogonale Basis des Moduls R(q), worin
(bi) eine nicht-orthogonale Basis des Moduls R(q), worin:
i = 0, 1, 2, ..., n
mit n = [logb q]
(q1) eine weitere nicht-orthogonale Basis, die der gemischten Basen:
pour 1 = 2, ..., k
und q&sub1; = 1
Jedes Element von R(q) gestattet somit eine eindeutige Zerlegung in diesen Basen:
Die Umsetzung der Koordinaten (Änderung der Basis) erfolgt, indem die alte Basis in Termen der neuen geschrieben wird und in dem dann diese Ausdrücke in der alten Zerlegung substituiert werden.
In einem ersten Falle wird die Umcodierung von der positionellen Notation mit der Basis (bi) in die residuelle Notation mit der Basis (bj) ausgeführt:
Über den Satz von chinesischen Rest erhält man:
Also:
worin:
Die eindeutige Angabe von x in der Basis (bj) verlangt:
0 ≤ xj < mj
Man schreibt also:
x'j = xj + rj . mj x'j xj mod mj
Da die Weitergabe des Übertrags in der Basis (bj) überflüssig ist, erhält man:
Wenn die Ziffern ci Bits sind (b = 2), läuft die Umcodierung der binären Notation in die dezimale Notation auf eine Folge von Additionen der Terme αij modulo mj hinaus. Bei ausreichender Dynamik, z. B. für n = 13, ist es vorteilhaft, die Umcodierung ausgehend vom Code ci tabellarisch auszuführen.
Es ist stets möglich, die Umcodierung mittels Addierer modulo mj auszuführen.
In einem zweiten Falle wird die Umcodierung von der residuellen Notation mit der basis (bj) in die positionelle Notation mit gemischten Basen (q&sub1;) durchgeführt.
Dies ist die für die residuelle Arithmetik am meisten gebrauchte Umcodierung, die ferner im Verlaufe der Verarbeitung zum Vergleichen beispielsweise von Zwischenergebnissen verwendet wird, denn es werden nur Operatoren modulo mj verwendet.
Man schreibt:
worin 0 ≤ βj1 < m&sub1;
Also:
Damit x eindeutig angegeben werden kann, muß gelten:
0 ≤ a&sub1; < m&sub1;
Folglich:
a'&sub1; = a&sub1; + r&sub1; . m&sub1; a'&sub1; a&sub1; mod m&sub1;
Die mit der positionellen Notation verbundene Arithmetik fordert aber die Fortschreibung eines Übertrags von einer Ziffer zur anderen. Der Algorithmus stellt sich also wie folgt dar:
Da mi . qi = qi + 1 gilt m&sub1; = q&sub2;
usw...
x = a&sub1; . q&sub1; + a&sub2; . q&sub2; + a&sub3; . q&sub3; + ... + ak qk + rk . q
und
x a&sub1; q&sub1; + a&sub2; q&sub2; +... + ak qk mod q
Bei der Umcodierung wird also die modulare Arithmetik (modulo mj) verwendet, jedoch muß die Übertrag-Information bewahrt werden, um sie nacheinander an die nächste Ziffer weiterzugeben.
Der von Szabo vorgeschlagene Algorithmus zur Umcodierung wird wie folgt zerlegt:
Da q&sub1; = 1, x&sub1; = a&sub1; (Initialisierung)
x = x&sub1; . b&sub1; . x&sub2; . b&sub2; + ... + xk . bk
= a&sub1; . 1 + a&sub2; m&sub1; + a&sub3; m&sub1; m&sub2; + ... + ak m&sub1; m&sub2; ... mk-1

Erste Iteration:

Man zieht a&sub1; von den zwei Gliedern der obigen Gleichung ab. Man weiß aber, daß jede Restziffer unabhängig modulo mj bearbeitet werden kann.
(x&sub1; - a&sub1;) b&sub1; + (x&sub2; - a&sub1;) b&sub2; + ... + (xk - a&sub1;) bk = a&sub2; m&sub1; + a&sub3; m&sub1; m&sub2; + ... + ak m&sub1; m&sub2; ... mk-1
Es gilt x&sub1; - a&sub1; = 0
Das rechtsstehende Glied kann durch m&sub1; dividiert werden, da jedes Produkt a&sub1;.q&sub1; diese Größe enthält, und für das linksstehende Glied gilt, da m&sub1; teilerfremd mit mj ist, j ≠ 1, der Kehrwert von m&sub1; modulo mj existiert, j ≠ 1; wir stellen fest:
m1j&supmin;¹, j ≠ 1.
Man erhält dann:
m&sub1;&sub2;&supmin;¹ (x&sub2; - a&sub1;) b&sub2; + m&sub1;&sub3;&supmin;¹ (x&sub3; - a&sub1;) b&sub3; + ... + m1k&supmin;¹ (xk -a&sub1;) bk = a&sub2; + a&sub3; m&sub2; + ... + ak m&sub2; m&sub3; ... mk-1
Diese Gleichung, modulo m&sub2; genommen, ergibt:
m&sub1;&sub2;&supmin;¹(x&sub2;-a&sub1;) a&sub2; mod m&sub2;

Zweite Iteration:

Man beginnt erneut mit dem gleichen Verfahren, indem a&sub2; auf beiden Seiten der Gleichung abgezogen wird:
[m&sub1;&sub3;&supmin;¹ (x&sub3;-a&sub1;) - a&sub2;] b&sub3; + ... + [m1k&supmin;¹ (xk - a&sub1;) - a&sub2;] bk = a&sub3;m&sub2; + ... + ak m&sub3; ... mk-1
Man dividiert rechts durch m&sub2;, man multipliziert links mit dem Kehrwert von m&sub2; mod mj, j ≠ 2:
Die Gleichung modulo m&sub3; ergibt:
m&sub2;&sub3;&supmin;¹ [m&sub1;&sub3;&supmin;¹ (x&sub3; - a&sub1;) - a&sub2;] a&sub3; mod m&sub3;
usw. bis zur Erlangung von ak.
Der Algorithmus erfordert (k-1) Iterationen, und er ist mit der Abhängigkeit der Reste voneinander bei jeder Iteration behaftet, denn die Ziffer a&sub1;, die gerade bei den anderen Resten gefunden wurde, muß übertragen werden, um sie zu subtrahieren.
In Fig. 9 ist ein Ausführungsbeispiel eines Codiermoduls 21 ersichtlich, bei dem der Szabo-Algorithmus angewandt wird. Der Modul 21 enthält k Leitungen 81 bis 8k, welche die zu verarbeitenden Ziffern liefern. Die erste Leitung 81 ist einerseits an eine Leitung 811 angeschlossen, die ein erstes Resultat Q&sub1; liefert, und andererseits an erste Eingänge von k-1 Subtrahierern/Multiplizierern 59. Die Leitungen 82 bis 8k sind an zweite Eingänge der Subtrahierer/Multiplizierer 59 angeschlossen.
Der Ausgang des mit der Leitung 82 verbundenen Multiplizierers/Subtrahierers ist einerseits an eine Leitung 812 angeschlossen, die ein zweites Ergebnis Q&sub2; liefert, und andererseits an erste Eingänge von k-2 Subtrahierern/Multiplizierern 59.
Usw. bis zu einer letzten Stufe, die nur noch einen einzigen Subtrahierer/Multiplizierer 59 enthält, dessen Ausgang mit einer Leitung 81k verbunden ist.
In Fig. 10 ist ein Umcodiermodul 21 oder 22 ersichtlich, worin der Rest am Ende weitergegeben wird. Auf diese Weise nutzt der Umcodiermodul 21 oder 22 durch eine parallele Architektur die Unabhängigkeit der Ergebnisse über jede Ziffer aus, um die Rechenzeit zu verkürzen.
Es wurde bereits zuvor ersichtlich, daß die Umsetzung zwei Stufen umfaßt:
- Berechnung von a'&sub1;:
mit:
- Formgebung: (a'&sub1;) T (a&sub1;), in deren Verlauf der Übertrag an die nächste Ziffer weitergegeben wird.
Es können leicht die folgenden Beziehungen angegeben werden:
worin 0 ≤ 1 < m&sub1;
Unter Berücksichtigung der komplexen Arithmetik ohne Multiplikation, wie sie bisher verwendet wurde, ist es vorteilhaft, die angegebenen Operationen nicht auszuführen, zumal überdies der Rest aufbewahrt werden muß.
Die neue Methode beruht auf der folgenden Beobachtung:
Man kann den Code zu gemischten Basen von:
speichern, der somit durch xj adressiert wird. Hierbei vermeidet man den großen Rest, der mit einer Multiplikation verbunden ist.
Der Algorithmus wird dann wie folgt vereinfacht:
Es müssen noch Additionen mit Rest ausgeführt werden, und der Rest muß an die nächste Ziffer weitergegeben werden. Es ist jedoch offensichtlich, daß die zu übertragende Übertrag-Information des Terms a&sub1; vor dem Ende der Berechnung des Terms a'&sub1;&sbplus;&sub1; verfügbar ist, und daß sie klein ist.
Der Transcodiermodul 21 oder 22 enthält k Eingangsleitungen 81 bis 8k, welche die umzucodierenden Ziffern x&sub1; bis xk weitergeben sollen. Die Eingangsleitung 81 ist an k Festwertspeicher 57 angeschlossen. Die Eingangsleitung 82 ist an k-1 Festwertspeicher 57 angeschlossen. Die Eingangsleitung 83 ist an k-2 Permanentspeicher 57 angeschlossen. Die Anzahl von Permanentspeichern nimmt bei jeder weiteren Eingangsleitung um Eins ab. Die Eingangsleitung 8k ist an einen einzigen Festwertspeicher 57 angeschlossen.
Der erste Festwertspeicher 57, der an die Eingangsleitung 81 angeschlossen ist, ist an die Ausgangsleitung 811 angeschlossen, welche eine umcodierte Ziffer a&sub1; weitergeben soll.
Der zweite Festwertspeicher 57, der mit der Eingangsleitung 81 verbunden ist, ist an einen ersten Eingang eines Addierers 55 angeschlossen, der die Addition mit Rest modulo m&sub2; ausführt.
Der dritte Festwertspeicher 57, welcher mit der Eingangsleitung 81 verbunden ist, ist an einen der vier Eingänge eines Addierers 55 angeschlossen, der die Addition mit Rest modulo m&sub3; ausführt.
Der vierte Festwertspeicher 57, der an die Eingangsleitung 81 angeschlossen ist, ist an einen der fünf Eingänge eines Addierers 55 angeschlossen, der die Addition mit Rest modulo m&sub4; ausführt.
Usw. bis zu dem ki-ten Festwertspeicher 57, der mit der Eingangsleitung 81 verbunden und an einen der k-1 Eingänge eines Addierers 55 angeschlossen ist, der die Addition modulo mk ausführt.
Der Übertrag des Addierers 55 modulo m&sub2; wird an einen der Eingänge des Addierers 55 modulo m&sub3; weitergegeben.
Der Übertrag des Addierers 55 modulo m&sub3; wird an einen der Eingänge des Addierers 55 modulo m&sub4; weitergegeben.
Usw. bis zu dem Übertrag des Addierers 55 modulo mk-1, der an einen der Eingänge des Addierers 55 modulo mk weitergegeben wird.
Ein erster Festwertspeicher 57, der an die Eingangsleitung 82 angeschlossen ist, ist an einen Eingang des Addierers 55 modulo m&sub2; angeschlossen.
Ein zweiter Festwertspeicher 57, der mit der Eingangsleitung 82 verbunden ist, ist an einen der Eingänge des Addierers 55 modulo m&sub3; angeschlossen.
Usw. bis zu dem ki-ten Festwertspeicher 57, der mit der Eingangsleitung 82 verbunden und an einen der Eingänge des Addierers 55 modulo mk angeschlossen ist.
Die Festwertspeicher 57, welche mit der i-ten Eingangsleitung (8i) verbunden sind, sind an den Addierer 55 angeschlossen, der die Addition modulo mi ausführt, bis zu dem Addierer 55, der die Addition modulo mk ausführt.
Die Ausgangsleitungen 812 bis 81k sind mit den jeweils entsprechenden Ausgängen der Addierer 55 modulo m&sub2; bis modulo mk verbunden.
In Fig. 10 sind die Eingangswerte mit xi bezeichnet, von x&sub1; bis xk; die aus einem Festwertspeicher erhaltenen Ergebnisse mit x'ij, von x'&sub1;&sub1; bis x'kk; die Reste ri, von r&sub2; bis rk-1; die Ergebnisse ai, von a&sub1; bis ak.
Die Addierer modulo mi sind beispielsweise in Form von Tabellen verwirklicht.
In vorteilhafter Weise werden für die Umcodierung Addierer 55 in Baumstruktur verwendet, worin der Übertrag des vorausgehenden Zweiges jeweils zu der ersten Stufe der Addierer hinzugefügt wird. Ein Beispiel für einen Addierer modulo m&sub4; mit Baumstruktur ist in Fig. 11 gezeigt. In Fig. 11 werden die gleichen Bezeichnungen wie in Fig. 10 verwendet.
Der Addierer 53 modulo m&sub4; von Fig. 11 umfaßt vier elementare Addierer, die ebenfalls mit 55 bezeichnet sind.
Jeder elementare Addierer 55 empfängt zwei zu addierende Ziffern und liefert ein Ergebnis. Die zwei ersten elementaren Addierer 55 empfangen x'&sub1;&sub4;, x'&sub2;&sub4; bzw. x'&sub3;&sub4;, X'&sub4;&sub4;.
Der dritte elementare Addierer 55 addiert die Ergebnisse der zwei ersten elementaren Addierer 55. Der vierte elementare Addierer 55 fügt den Rest r&sub3; des vorausgehenden Zweiges dem Ergebnis hinzu, das durch den dritten elementaren Addierer 55 gewonnen wird. Das Ergebnis a&sub4; der durch den vierten elementaren Addierer 55 ausgeführten Summierung wird auf einer Leitung 814 ausgegeben.
Die Gesamtzeit für die Umsetzung wird auf die Zeit zum Summieren des Terms ak reduziert, d. h. (1+[log 2 (k = 1)]) mal die Zeit für die elementare Addition, worin [x] die unmittelbar auf x folgende ganze Zahl ist.
Der Durchsatz wird dann durch den Kehrwert der längsten Zeit zwischen dem Zeitpunkt des Auslesens aus dem Speicher und dem Zeitpunkt der Umsetzung bestimmt. Diese Methode ist ersichtlich schneller als die herkömmliche Methode nach Szabo.
Umcodierung: positionelle Notation - Basis (q&sub1;) in positionelle Notation Basis (b&sub1;):
Diese Umsetzung betrifft nur das Endergebnis, um gewünschtenfalls in die herkömmliche positionelle Notation zurückzugelangen:
Die Umsetzung impliziert auch die Berücksichtigung eines Restes, jedoch nimmt, bei Bearbeitung in binärer Notation (was zumeist der Fall sein dürfte), γ1i die Werte 0 oder 1 an, und für die Umsetzung werden nur Addierer benötigt, deren maximale Anzahl k pro Zweig beträgt, bei einer Bitbreite, die maximal in der Größenordnung von log2q liegt.
Wiederherstellung von Z = AX + BY in R(q²). Die Umcodierung in die Basis (q&sub1;) ist in Tabelle VIII angegeben. Tabelle VIII mit gemischten Basen der Reste
Die erfindungsgemäße Vorrichtung ermöglicht die sehr schnelle Durchführung von digitalen Berechnungen. Jener Art der notwendigen Berechnung bildet die erfindungsgemäße Vorrichtung einen Koprozessor eines herkömmlichen Rechners, einen Rechner, der einen (nicht gezeigten) vorgeschalteten Rechner enthält, oder einen völlig autonomen Rechner.
Die erfindungsgemäße Vorrichtung kann also in verschiedenen Ausführungen verwirklicht werden, je nach der gewünschten Rechenleistung und der angewandten Technologie.
Die Erfindung ist insbesondere auf die digitale Berechnung anwendbar.
Hauptsächlich ist die Erfindung auf die Signalverarbeitung und auf die digitale Filterung anwendbar.

Claims

1. Rechenvorrichtung mit:

- einer Digitalcodierer-Einheit (21), die komplexe Zahlen in positioneller Notation in eine residuelle Notation umschreibt;

- einer Recheneinheit (1), die am Ausgang der Digitalcodierer-Schaltung angeordnet ist und Berechnungen mit den Komponenten der komplexen Zahlen in residueller Notation ausführt;

- einer am Ausgang der Recheneinheit angeordneten Digitaldecodierer-Einheit (22), welche die von der Recheneinheit in residueller Notation ausgegebenen Ergebnisse in positionelle Notation umschreibt, wobei die Rechenvorrichtung dadurch gekennzeichnet ist, daß die Codierer-Einheit die komplexen Zahlen in eine residuelle Notation mit Resten umschreibt, die Modulo Primzahlen mi der Form mi = 4 k + 3, worin k eine ganze positive Zahl ist, berechnet sind.

2. Rechenvorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Recheneinheit (1) Mittel (57) aufweist, die es ermöglichen, jeder komplexen Zahl einen solchen Index zuzuordnen, daß eine Multiplikation von zwei komplexen Zahlen in zweieindeutiger Weise einer Addition der Indizes entspricht.

3. Rechenvorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß sie eine Steuereinheit (6) umfaßt, welche die Funktion der Recheneinheit (1) überwacht und aus einem Programmspeicher (404) die für die gewünschte Verkettung der Berechnungen erforderlichen Instruktionen enthält.

4. Rechenvorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß sie Busleitungen aufweist, welche die Recheneinheit (1) mit internen oder externen Speichern (41, 42, 402, 403) verbindet, die in residueller Notation geschriebene Zahlen enthalten.

5. Rechenvorrichtung nach Anspruch 4, dadurch gekennzeichnet, daß die Recheneinheit (1) über einen Bus (1) mit einem Festwertspeicher (402) verbunden ist.

6. Rechenvorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Recheneinheit (1) die zur Durchführung von Korrelations- und Faltungsberechnungen erforderlichen Mittel umfaßt.

7. Rechenvorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Recheneinheit (1) Festwertspeicher (57) enthält, worin tabellenförmig geordnete Funktionen gespeichert sind.

8. Rechenvorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Decodier-Einheit (22) Datenwege umfaßt, die es ermöglichen, die Übertrag-Additionsoperationen am Ende der für jede Ziffer erfolgten Umcodierberechnung auszuführen.