DE1222717B - Digitaler Interpolationsrechner - Google Patents

Description

BUNDESREPUBLIK DEUTSCHLAND

DEUTSCHES

PATENTAMT

AUSLEGESCHRIFT

Int. α.:

G06f

Deutsche Kl.: 42m-:

I.V8» 3 0. 3.

Nummer: 1 222 717 ^J[Jj₁,

Aktenzeichen: G 39913IX c/42 m

Anmeldetag: 21. Februar 1964

Auslegetag: 11. August 1966

Gegenüber dem im allgemeinen schnelleren Analogrechner besitzt der Digitalrechner den Vorteil, daß Berechnungen theoretisch mit beliebig großer Genauigkeit durchgeführt werden können. Es gibt zahlreiche Anwendungsfälle insbesondere bei Realzeitoperationen, in denen zwar eine hohe Rechengeschwindigkeit erforderlich ist, jedoch die Genauigkeit eines Analogrechners, die normalerweise bis etwa 0,1 °/o geht, nicht ausreicht. Beispielsweise sollen bei einem Flugsimulationsgerät Größen, wie etwa die Schubkraft eines Triebwerks, berechnet werden, die Funktionen mehrerer Unabhängiger, wie etwa der Brennstoffansaugung, der Mach-Zahl, der umgebenden Temperatur und des umgebenden Drucks usw. sind. Um derartige Funktionen mit hinreichender Genauigkeit zu berechnen, ist der Einsatz eines Digitalrechners nötig. Die berechneten Größen werden anschließend in einem Digital-Analog-Wandler umgesetzt und den betreffenden Meß- bzw. Steuergeräten als Analogsignale zugeführt. Um nun bei stetigen Funktionen Funktionswerte an beliebigen Abszissenpunkten aus den nur für bestimmte diskrete Punkte gespeicherten Funktionswerten zu ermitteln, sind in den genannten Anwendungsfällen ständig Interpolationen nötig.

Auf herkömmlichen Digitalrechnern läuft die Interpolation so ab, daß zunächst zu dem Abszissenpunkt, für den der Funktionswert gesucht wird, diejenigen Eingabelungspunkte ermittelt werden, bezüglich deren Funktionswerte gespeichert sind. Diese Eingabelungspunkte sind durch die Ungleichung definiert:

Xn fi X < Xn + i,

wobei χ die unabhängige Abszissengröße ist, für die der Funktionswert gesucht wird, und X_n bzw. X_n+1 die eingabelnden Abszissenpunkte sind. Sodann werden die zu den Eingabelungspunkten gehörigen Funktionswerte f(x_n) bzw. /(X_n+1) aus einem Speicher geladen, und die Interpolation wird nach der folgenden Gleichung durchgeführt:

fix) =

Xn+i

f(x) =

- Xn)

Digitaler Interpolationsrechner

Anmelder:

General Precision Inc.,

Binghamton, N.Y. (V. St. A.)

Vertreter:

Dipl.-Ing. H. v. Schumann,
Patent- und Rechtsanwalt,
München 22, Widenmayerstr. 5

Als Erfinder benannt:
John M. Hunt, Binghamton, N.Y.;
John Kaufmann, Sunnyvale, Calif.;
Harold R. Dell, Palo Alto, Calif. (V. St. A.)

Beanspruchte Priorität:

V. St. ν. Amerika vom 21. Februar 1963 (260 160)

Zur Lösung dieser Gleichung führt ein herkömmlicher Digitalrechner zunächst drei Subtraktionen, dann eine Division und eine Multiplikation und schließlich eine Addition durch. Die Ermittlung eines einzigen Funktionswertes auf diesem Lösungsweg nimmt also relativ viel Zeit in Anspruch. Da ferner in bestimmten Anwendungsfällen ständig wiederkehrend solche Interpolationen ausgeführt werden müssen, akkumuliert sich dieser Zeitbedarf und stellt einen wichtigen Faktor in der gesamten Rechenzeit dar.

Gegenstand der Erfindung ist ein digitaler Interpolationsrechner, der zur Lösung der Interpolationsgleichung weniger Einzelrechenschritte benötigt und daher schneller ist. Der Erfindung liegt eine Umwandlung der obengenannten Gleichung in eine für die Binärverarbeitungsweise geeignetere Form zugrunde. Die Gleichung lautet dabei:

2^m '

Zur Durchführung der Lösung nach der vor- kandenregister zur Aufnahme des kleineren und

stehenden Gleichung besteht der erfindungsgemäße 50 einem weiteren Multiplikandenregister zur Aufnahme

Interpolationsrechner aus einem Multiplikatorregister des größeren der beiden Eingabelungsfunktionswerte

für die unabhängige Veränderliche, einem Multipli- aus einem Speicher, der die Funktionswerte für aus-

609 609/334

3 4

gewählfe-'Abszissenpunkte enthält, und aus einer benützt, um die Genauigkeit des Interpolationsergeb-

Schaltung, die in einzelnen Phasen zunächst den nisses über die eigentliche Stellenzahl der Register

Inhalt des ersten Multiplikandenregisters mittels auszudehnen.

eines Übertragungsgatters in einen Produktakkumu- Weitere Einzelheiten der Erfindung ergeben sich lator kopiert, sodann die jeweils unterste Stelle des 5 aus dem im folgenden beschriebenen Ausführungs-Mültiplikatorregisters mittels einer Abfühlanordnung beispiel an Hand der Zeichnungen, in denen
prüft, bei einer Eins in dieser Stelle den größeren, F i g. 1 ein Blockschaltbild der erfindungsgemäßen bei einer Null den kleineren Multiplikanden über ein Interpolationseinheit für einen Digitalrechner ist,
Addierwerk als jeweiliges binäres Teilprodukt zum F i g. 2 die Funktion einer Veränderlichen dar-Inhalt des Produktakkumulators hinzuaddiert und io stellt, in der die Beziehungen zwischen den gespeinach jedem Rechenschritt das darin entstehende cherten Funktionswerten und der zu einer Eingangs-Teilergebnis sowie den Multipükator um eine Stelle größe gehörigen gesuchten Funktion gezeigt sind,
nach rechts verschiebt. Die in der letztgenannten Fig. 3 in ähnlicher Darstellung wie Fig. 2 die Gleichung enthaltenen drei Summanden werden in Verhältnisse für eine Funktion zweier Veränderdem erfindungsgemäßen Rechner gleichzeitig berech- 15 licher zeigt,

net und aufeinander addiert, so daß — zeitlich F i g. 4 den Aufbau eines nach F i g. 1 verwendeten

gesehen — nur eine einzige Binärmultiplikation Gatters darstellt,

durchzuführen ist. F i g. 5 den Aufbau einer nach F i g. 1 verwendeten

In weiterer erfindungsgemäßer Ausgestaltung um- Vergleichsstufe zeigt und

faßt der Interpolationsrechner eine Vergleichsstufe, ao F i g. 6 die Schaltung der nach F i g. 1 verwendeten

die bei Übereinstimmung der oberen Stellen eines Ladelogik wiedergibt.

Eingangsregisters mit einem Speicheradreßzähler die Gemäß einer bevorzugten Ausführungsform der Inhalte der dem Zähler entsprechenden Speicher- Erfindung werden Digitalsignale, die verschiedene platze über eine Ladelogik mittels Eingangsgattern Punkte 11 von Funktionskurven (F i g. 2 und 3) darin die Multiplikandenregister überträgt. Die oberen 25 stellen, auf einer magnetischen Trommel oder einem Stellen desjenigen Abszissenpunktes, für den ein anderen Datenspeicher 12 großer Kapazität gespei-Funktionswert gesucht wird, stellen also erfindungs- chert (Fig. 1). Eingangssignale, die diex-, y-, z-Werte gemäß gleichzeitig die Speicheradresse für die Ein- der unabhängigen Veränderlichen darstellen, werden gabelungspunkte dar. Damit wird auch der Zeit- in Register 13,14 und 15 eingeführt. Daten, die die . bedarf für die Ermittlung der eingabelnden Funk- 30 Funktionskurven darstellen, werden Punkt für Punkt tionswerte wesentlich herabgesetzt. gespeichert, und die Werte der abhängigen Ver-

In weiterer vorteilhafter Ausgestaltung sieht die änderlichen x₀, X₁, x₂ usw. werden so gewählt, daß

Erfindung weitere Eingangsregister, die mit weiteren die Punkte in gleichen Abständen entlang der

Vergleichsstufen und weiteren Zählern zusammen- Abszisse liegen. Wie in F i g. 2 dargestellt, können

wirken, sowie zwei Zwischenregister zur zwischen- 35 neun solche Punkte gespeichert werden, wobei die

zeitlichen Aufnahme der jeweiligen Inhalte des Pro- Kurve in acht Segmente unterteilt wird, die in

duktakkumulators und deren Wiedergabe an die Abszissenrichtung gleiche Komponenten haben. Die

Multiplikandenregister vor. Dadurch wird die Inter- Eingangsgröße, die im x-Register 13 enthalten ist, ist

polation bei Funktionen von zwei bzw. drei und mehr binär verschlüsselt und stellt einen besonderen

Veränderlichen ermöglicht. 40 x-Wert innerhalb des Nutzbereiches der Funktions-

In weiterer erfindungsgemäßer Ausgestaltung sind kurve zwischen X₀ und x₈ dar. Es ist darauf hinzu-

die gespeicherten Funktionswerte so ausgewählt, daß weisen, daß die drei obersten Binärstellen der x-Ein-

sie zu äquidistanten Abszissenpunkten gehören und gangsgröße daher ein besonderes Segment der Funk-

das Multiplikatorregister nur die unteren Bits des tionskurve bilden. Wenn die Speichertrommel 12 sich

jeweiligen Eingangsregisters aufzunehmen braucht. 45 dreht, werden die verschiedenen Punkte 11 der

Es wird also nicht mit allen Stellen des betreffenden Funktionskurve durch einen Wortzähler 17 gezählt.

Abszissenpunktes, sondern nur mit demjenigen nach Eine Vergleichsstufe 18 vergleicht den Zustand des

dem Komma gerechnet. Neben einer Vereinfachung Wortzählers mit den drei obersten Stellen der x-Ein-

der Schaltung ergibt sich auch daraus eine Ver- gangsgröße vom Register 13. Wenn eine Identität

kürzung der Rechenzeit. 50 zwischen dem Wortzähler 17 und den drei obersten

In weiterer Ausgestaltung der Erfindung umfaßt Stellen der Eingangsgröße festgestellt wird, wird ein der Interpolationsrechner zwei Akkumulatoren, von Signal durch eine Leitung 19 zur Ladelogik 20 gedenen der erste seinen Inhalt mittels eines Über- führt, woraufhin ein erster Satz von Eingangsgattem tragungsgatters in bestimmten Phasen um eine Stelle 21 in die Lage versetzt wird, die Daten hindurchverschoben an den zweiten Akkumulator abgibt, der 55 zulassen, die einen ersten Eingabelungspunkt 22 der seinerseits seinen Inhalt mittels eines Übertragungs- Funktionskurve darstellen. Danach wird ein zweiter garters an das Addierwerk in Zwischenphasen zum Satz von Eingangsgattern 23 in die Lage versetzt, Inhalt des ersten hinzuaddieren kann. Diese Schal- Daten vom zweiten Eingabelungspunkt 24 der Funktung vermittelt eine stabile Speicherung der Informa- tionskurve hindurchzulassen. Auf diese Weise wertionen in den Zwischenregistern, da in keinem Zeit- 60 den die Signale, die die Eingabelungswerte der Funkpunkt eine geschlossene Schleife besteht. tionskurve darstellen, in einem Paar Register 25 und

In weiterer Ausgestaltung der Erfindung verschiebt 26 gespeichert.

der Interpolationsrechner den Inhalt des Multipli- Während die obersten Binärstellen aus den Einkatorregisters bei jedem Rechenschritt bitweise und gangsregistern 13,14 und 15 verwendet werden, um überträgt die aus dem Akkumulator herausgeschobe- 65 die Eingabelungsfunktionspunkte durch die Vernen unteren Bits in die frei werdenden Stellen des gleichsstufen 18 zu bestimmen, werden die unteren Multiplikatorregisters. Die nicht mehr benötigten Stellen durch Übertragungsgatter 28 zu einem MultiStellen des Multiplikatorregisters werden also dazu plikatorregister 29 geleitet. Zur Durchführung der

Interpolation wird zunächst das Register 25 über die Ubertragungsgatter 30 mit einem Akkumulator 31 gekuppelt, wodurch Signale, die den ersten Eingabelungsfunktionswert, /(x„), darstellen, in den Akkumulator 31 geführt werden. Das Ablesen aus dem Register 25 zerstört den Registerinhalt nicht, und daher wird die Größe f(x_n) sowohl im Akkumulator 31 als auch im Register 25 gespeichert.

Nach den anfänglichen Operationen des Einführens der Werte in die Register 25, 26 und 29 und in den Akkumulator 31 wird das Multiplikatorregister 29 Stelle für Stelle durch einen Abfühler 32 abgefragt, und das eine oder das andere der Addiergatter 33 bzw. 34 wird in die Lage versetzt, die Größe f(x_n) aus dem Register 25 bzw. die Größe f (x_n+1) aus dem Register 26 hindurchzulassen. Ein Addierwerk 35 addiert den ausgewählten Funktionswert, /(*„) bzw. /Oc_n+1), zu dem Inhalt des Akkumulators 31, um ein Teilprodukt in einem weiteren Akkumulator 36 zu erzeugen. Nach dem ersten Additionsschritt wird der Inhalt des Akkumulators 36 in den Akkumulator 31 mittels der Übertragungsgatter 37 übertragen. Die Akkumulatoren 31 und 36 sind miteinander durch die Übertragungsgatter 37 so gekuppelt, daß während des Übertragungsvorganges eine Rechtsverschiebung durchgeführt wird. Nach jeder Addition wird das Teilprodukt nach rechts verschoben und in den Akkumulator 31 eingeführt, und das Multiplikatorregister 29 wird ebenfalls nach rechts verschoben. Die Interpolation setzt sich mit dem Abfragen der übrigen Multiplikatorstellen und der Addition des jeweils entsprechenden Multiplikanden fort. Nach jeder Addition werden sowohl das Teilprodukt als auch die Multiplikatorgröße nach rechts verschoben, bis alle Multiplikatorstellen abgefragt sind. Der Akkumulator 31 enthält dann die Ausgangssignale, die den interpolierten Funktionswert f(x) darstellen.

Die Rechenanlage, die in F i g. 1 dargestellt ist, überträgt und verarbeitet die Signale parallel. So wird eine Vielzahl von Eingangssignalen in eines der x-, y- oder z-Register 13, 14 oder 15 gleichzeitig über eine Vielzahl paralleler Eingangsleitungen eingeleitet. In gleicher Art und Weise werden Signale aus dem Speicher 12 gleichzeitig über mehrfache Leitungen zu einer Gruppe von Leseverstärkern geleitet, die gemeinsam als ein einziger Kasten 39 dargestellt sind. Von dort können die Signale durch geeignete Gruppen von Gattern 21 oder 23 in Register 25 bzw. 26 geleitet werden. Die Vielzahl der parallelen Leitungen zwischen den verschiedenen Rechenanlagen-Bausteinen oder Komponenten sind in F i g. 1 durch Doppellinien angedeutet. Die verschiedenen in F i g. 1 gezeigten Gatter, wie z. B. 21, 23, 28, 33 und 34, bestehen in Wirklichkeit aus einer Vielzahl von UND-Gattern 40, wie in F i g. 4 gezeigt. Durch eine Schaltspannung auf der Leitung 41 werden alle Gatter 40 geöffnet, um Signale zwischen den Eingangsklemmen und entsprechenden Ausgangsklemmen hindurchzulassen. Jedes der UND-Gatter 40 kann von üblicher Bauart sein, beispielsweise dem Diodengatter entsprechen, das auf Seite 32 des Lehrbuches mit dem Titel »Arithmetical Operations In Digital Computers« von R. K. Richards, Verlag D. Van Nostrand Company, beschrieben ist.

Die Vergleichsstufen 18 können nach F i g. 5 aus UND-Gattern 41 und 42 und einem ODER-Gatter 43 bestehen. Jedes UND-Gatter ist mit seiner einen

55 Eingangsklemme über eine der Leitungen 44 der entsprechenden der obersten Stellen des x-Registers 13, mit seiner anderen über eine der Leitungen 45 mit dem Wortzähler 17 gekuppelt. Jede aus den UND-Gattern 41 und 42 und einem ODER-Gatter 43 bestehende Gruppe stellt ein »EXKLUSIV-ODER-Gatter« dar, das dann geöffnet ist, wenn zwischen den Signalen auf dem Leitungspaar 44 und denen auf dem Leitungspaar 45 Identität besteht. Ein letztes UND-Gatter 47 ist mit jedem der EXKLU-SIV-ODER-Gatter gekoppelt und führt ein Signal zur Ausgangsleitung 19, wenn von allen ODER-Gattern Signale empfangen werden. In diesem Fall sind alle Eingangssignale der Leitungen 44 identisch den Eingangssignalen der Leitungen 45, d. h., die obersten Bits des x-Eingangssignals sind dem Inhalt des Wortzählers 17 gleich.

Wie vorher angegeben, erzeugt die Rechenanlage nach der vorliegenden Erfindung ein Ausgangssignal, das eine Funktion von einer, zwei oder drei Veränderlichen ist, die durch die Eingangssignale x, y und ζ dargestellt werden. F i g. 2 zeigt ein Beispiel für eine einzige Veränderliche. Durch Interpolation zwischen den Funktionswerten der Eingabelungspunkte 22 und 24 wird ein Ausgangssignal erzeugt, das den Funktionswert f(x) des interpolierten Punktes 49 wiedergibt. F i g. 3 zeigt in dreidimensionaler Darstellung eine Funktion zweier Veränderlicher χ und y. Um ein Ausgangssignal aus einer Funktion von zwei Veränderlichen zu erzeugen, wird eine erste Interpolation zwischen den Funktionswerten eines Paares von Eingabelungspunkten 50 und 51 durchgeführt, wobei ein Zwischensignal entsprechend dem Funktionswert eines interpolierten Punktes 52 entsteht. Eine zweite Interpolation zwischen den Funktionswerten eines Paares von Eingabelungspunkten 53 und 54 ergibt ein zweites Signal, das den Funktionswert an einem Zwischenpunkt 55 darstellt. Durch eine dritte und letzte Interpolation zwischen den Funktionswerten der Punkte 52 und 55 erhält man ein Ausgangssignal, das dem Funktionswert an dem gesuchten Interpolationspunkt 56 entspricht.

Eine Funktion von drei Veränderlichen kann nicht graphisch in einer zufriedenstellenden Art und Weise wie in F i g. 2 oder 3 dargestellt werden, aber dieser Fall wird verständlich, wenn man sich eine Funktion von drei Veränderlichen als eine Reihe von Kurvenblättern vorstellt, von denen jedes ähnlich der Fig. 3 ist. Jedes Blatt kann an sich selbst der Fig. 3 gleichen, aber die einzelnen Punkte können von den Werten der Punkte des benachbarten Blattes ausgehen. Das erfindungsgemäße Gerät kann den Endwert der Funktion bestimmen, indem es vier Initial-Interpolationen zwischen nebeneinanderliegenden Blättern durchführt und Punkte erzeugt, die den Punkten 50, 51, 53 und 54 nach F i g. 3 entsprechen. In diesem Fall kann die Darstellung nach F i g. 3 selbst als eine Interpolation zwischen zwei benachbarten Blättern angesehen werden, die nicht gezeigt sind, die man sich jedoch als von ähnlicher Gestalt vorzustellen hat. Nach den ersten vier Interpolationen wird die Funktion von drei Veränderlichen auf eine Funktion von zwei Veränderlichen reduziert, und daraus wird der gesuchte Funktionswert in Übereinstimmung mit den Schritten gewonnen, die oben angegeben sind. Selbstverständlich kann die Erfindung auch für Funktionen von mehr als drei

Veränderlichen durch die dann erforderliche Erhöhung der Sätze von Kurvenblättern verwendet werden.

Wie in Fig. 1 gezeigt, werden die Signale, die die einzelnen Punkte darstellen, kontinuierlich durch die Leseverstärker 39 von der Speichertrommel 12 abgelesen. Der Wortzähler 17 wird nach jedem Ablesen um Eins erhöht. ■

Nachdem alle Punktwerte einer einzelnen Funktionskurve abgelesen sind, kehrt der Wortzähler 17 auf Null zurück, und es wird ein Signal erzeugt, das einen Kurvenzähler 58 vorschaltet. Während der Trommelspeicher 12 weiterhin Signale durchgibt, die weitere Punkte weiterer Kurven darstellen, kehrt der Kurvenzähler schließlich auf Null zurück, und ein Fortschaltimpuls wird einem Blattzähler 59 zügeführt. Die verschiedenen Vergleichssrufen 18 vergleichen so den x-Eingang mit dem Zustand des Wortzählers 17, den y-Eingang mit dem Zustand des Kurvenzählers 58 und den z-Eingang mit dem Blattzähler 59. Man sieht, daß für Funktionen zweier Veränderlicher der Blattzähler 59 und das Register 15 überflüssig und für Funktionen einer einzigen Veränderlichen weder der Kurvenzähler 58 noch der Blattzähler 59 noch die Register 14 und 15 notwendig sind.

Die Ladelogik für die Funktionswerte /(x„) und /(x_n+1) steuert die. Eingangsgatter 21 und 23 so, daß sie die entsprechenden Signale aufnehmen, wenn die obersten Bits in den x-, y- und z-Registern mit dem Inhalt der Zähler 17 bzw. 58 bzw. 59 übereinstimmen. Fig. 6 zeigt eine vereinfachte Anordnung der logischen Schaltung 20. Die Leitungen 19 aus den Vergleichsstufen 18 sind mit einem geeigneten Gitter 61 verbunden. Wenn die Identität hergestellt ist, wird ein Flip-Flop 62 gesetzt, um eine Spannung auf einer Leitung 63 zu erzeugen, die das /(x_n)-Eingangsgatter 21 öffnet. Von der magnetischen Trommel 12 stammende Taktimpulse werden einer Leitung 64 zügeführt, so daß das Flip-Flop 62 gelöscht wird, nachdem die Funktionspunktdaten von der Trommel 12 abgelesen und durch das Eingangsgatter 21 geleitet worden sind. Der gleiche Taktimpuls auf der Leitung 64 wird über ein UND-Gitter 65 geleitet, um ein zweites Flip-Flop 66 zu setzen, das eine Spannung auf einer Leitung 67 erzeugt, die das /(x_n+1)-Eingangsgatter 23 öffnet. Während des nächsten Zeitintervalls werden die Signale, die den Wert /(x_n+1) darstellen, durch das Gatter 23 geführt. Ein weiterer Taktimpuls auf einer Leitung 68 löscht das Flip-Flop 66 und sperrt das Gatter 23. Wie vorher angegeben, vergleichen die Vergleichsstufen 18 die obersten Bmarstellen des Eingangssignals mit den gespeicherten »Wörtern« oder Funktionspunkten, um den ersten Eingabelungspunkt x_n zu ermitteln (x_ä nach

^χ - ^χη)

F i g. 2), der in das Register 25 eingeführt wird. Die Ladelogik 20 sorgt dafür, daß nicht nur die Daten für den Punkt 22 in das Register 25, sondern auch diejenigen für den Punkt 24 in das Register 26 geladen werden. Auf diese Weise werden die beiden Punkte, die die Eingangsgröße χ eingabein, in die Register 25 bzw. 26 geladen. ·

Wie vorher angegeben, lautet die allgemeine Formel für einen durch lineare Interpolation gewonnenen Funktionswert:

_
/(x) = —- [/Oc₇₁₊₁) — f(x_n)] -f-/w , (1)

worin χ die Eingangsgröße ist, x_n und X_n+1 die Werte der unabhängigen Veränderlichen an den Punkten, die die Größe χ eingabein, f(x_n) und /(X_n+1) die abhängigen Funktionswerte der Eingabelungspunkte sind und /(x) der gesuchte Funktionswert für die Eingangsgröße χ ist. Eine Lösung für die obige Glei-

ao chung erfordert drei anfängliche Subtraktionsschritte, einen Divisionsschritt, einen Multiplikationsschritt und schließlich einen Additionsschritt. Gleichung (1) kann verändert werden, wenn erkannt wird, daß die Divisionsgröße (x,_i+1 — x„) den betreffenden Abschnitt auf der Abszisse zwischen benachbarten Punkten der Funktionskurve (s. F i g. 2) darstellt. Wie vorher angegeben, sind die Punkte entlang der Abszisse äquidistant, und daher ist die Größe (^xn+i~^xn) ^eme Konstante. Wenn dieser konstante Divisor gleich der Einheit gemacht wird, kann der Divisionsschritt ausgeschaltet werden. Damit vereinfacht sich Gleichung (1) wie folgt:

/W - (* - *»J LA^+iJ-/WJ+/W- V-) Gleichung (2) kann erweitert wie folgt geschrieben werden:

/0*0 =/(x»+i) · (* — *») —/W · ^(x ~ ^χη)

40

45

wird die Größe /(x„) als gemeinsamer Faktor der beiden letzten Ausdrücke eingesetzt, so ergibt sich die folgende Gleichung:

& ~ ^Xn> +/W l^L (^x

Es ist darauf hinzuweisen, daß die Größe 1—(x—x„) das Zweier-Komplement der Größe (x — X_n) ist.

Diese Größe kann in das Einer-Komplement von (x—X_n) umgewandelt werden, indem man davon den _{w d untersten BinärsteUe} 1 _abzieht

2^m '

worin m die Zahl der Binärstellen in der Multiplikatorgröße ist:

-

- {^χ - ^χη)

Einer-Komplement von (x—xj

Aus Gleichung (5) ergibt sich, daß der gesuchte Funktionswert /(x) gleich der Summe von drei Ausdrücken ist. Der erste Ausdruck /(x_n+1) (x—X_n) ist das Produkt aus dem Multiplikator und dem Funktionswert des zweiten Eingabelungspunktes /(x_n+1). Dieser Ausdruck könnte durch eine übliche Rechenanlagenmultiplikation mit wiederholten selektiven Additionen und Rechtsverschiebungen des Multiplikanden /(^_n+1) errechnet werden. Bei einem der-

artigen herkömmlichen Multiplikationsschritt wird

65, der Multiplikator (x—X_n) Stelle für Stelle abgefragt, ' der Multiplikand /(x„₊₁) hinzuaddiert und jedesmal nach rechts verschoben, wenn die betreffende Multiplikatorstelle eine binäre Eins enthält. Der Multipli-

kator wird nicht hinzuaddiert, wenn die Multiplikatorstelle eine binäre Null enthält. Den zweiten Ausdruck der Gleichung (5) erhält man durch ähnliche selektive Additionen und Registerverschiebungen. Da der Multiplikator für den zweiten Ausdruck das Einer-Komplement der Größe (x—X_n) ist, wird der Multiplikand f(x_n) jedesmal hinzuaddiert, wenn die betreffende Multiplikatorstelle eine Null enthält. Die Addition unterbleibt, wenn die Multiplikatorstelle eine Eins enthält.

Es ist nun verständlich, daß ein kombinierter Wert für zwei Ausdrücke der Gleichung (5)

/(X_n + i) (X — X_n) + /(X

in einem einzigen Multiplikationsschritt entwickelt werden kann. Die beiden Multiplikanden /(X_n+1) und f(x_n) können in getrennte Multiplikandenregister und der Multiplikator (x—x_n) in ein Multiplikatorregister eingeführt werden. Der Multiplikator wird dann Stelle für Stelle abgefragt. Jedesmal, wenn die abgefragte Multiplikatorstelle eine binäre Eins enthält, wird der eine Multiplikand /(x_n+1) zum Teilprodukt addiert, und jedesmal, wenn die Multiplikatorstelle eine binäre Null enthält, wird der andere Multiplikand f(x_n) zum Teilprodukt addiert. Nach jeder Addition wird das Produktregister oder der Produktakkumulator als Vorbereitung für die nächste Multiplikandenaddition nach rechts verschoben.

Der dritte Ausdruck der Gleichung (5), / (x_n) -—, stellt das Produkt aus dem Multiplikanden f(x_n) und dem Bruch -^- dar. Diese Multiplikation kann durchgeführt werden durch Einführen des Multiplikanden / (x„) in einen Akkumulator oder ein Register und nachfolgende m-fache Rechtsverschiebung des Registers, wobei m die Stellenzahl des Multiplikators ist. In der erfindungsgemäßen Interpolarschaltung wird dieses Produkt gleichzeitig mit den oben beschriebenen Rechenschritten entwickelt. Der Multiplikand f(x„) wird am Beginn der Multiplikationsoperation in den Produktakkumulator geladen. Sodann werden die Multiplikanden, wie beschrieben, selektiv und entsprechend der jeweils abgefragten Multiplikatorstelle zum Inhalt des Produktakkumulators hinzuaddiert, der nach jeder Addition nach rechts verschoben wird. Mit anderen Worten wird der Multiplikand f(x_n) in den Produktakkumulator geladen, und danach bewirken die weiteren Multiplikationsoperationen, daß die Größe wiederholt nach rechts verschoben wird, und zwar so oft, wie es der Zahl der Stellen des Multiplikators entspricht. Besondere Operationen brauchen deshalb nicht durchgeführt zu werden.

Als alternatives Verfahren zur Berechnung kann der Initialschritt zur Übertragung der Größe f(x_n) aus dem Multiplikandenregister 25 zum Akkumulator 31 in der Weise ausgeführt werden, daß eine binäre Null in die unterste Binärstelle des Multiplikatorregisters 29 geladen wird. Wenn in Betracht gezogen wird, daß die Multiplikatorgröße ein Binärbruch ist, braucht das Hinzufügen eines weiteren Bits den Wert des anderen Multiplikatorbits, die in das Register 29 über die Gatter 28 übertragen werden, nicht zu beeinflussen. Wenn das Multiplikatorregister stets mit der binären Null beginnt, kann der Akkumulator 31 gelöscht werden, und der erste Additionsschritt führt wirksam die Größe f(x_n) in den Akkumulator durch die Additionsvorrichtung 35 ein.

Wie bereits beschrieben, werden die drei höchsten Stellen der Eingangsgrößen von den Vergleichsstufen dazu benutzt, um die Eingabelungsrößen /(x„) und /(x_n+1) für die Register 25 und 26 zu bestimmen. In der Zwischenzeit werden die unteren Stellen der Eingangsgröße in das Multiplikatorregister 29 geladen. Der Multiplikatorabfühler 32 kann ein einfaches Flip-Flop oder ein bistabiler Stromkreis sein, der in einen ersten Leitzustand versetzt wird, wenn das unterste Bit des Multiplikatorregisters 29 eine binäre Eins ist; es wird in einen zweiten Leitzustand versetzt, wenn das unterste Multiplikatorbit eine binäre Null ist. Die beiden Ausgangsleitungen der Flip-Flop-Schaltung 32 sind mit entsprechenden Gattern 33 und 34 verbunden, so daß ein erster Satz von Eingängen des Paralleladdierwerks 35 je nach dem Zustand des Flip-Flops entweder mit dem Register 25 oder mit dem Register 26 gekuppelt wird. Der Interpolationsvorgang beginnt durch einen Initialadditionsimpuls, der dem Ubertragungsgatter 30 zugeführt wird, wodurch der Multiplikand /(x„) in den zweiten Akkumulator 31 eingeführt wird. Dieser Anfangsschritt, kombiniert mit den anschließenden, im Zusammenhang mit den aufeinanderfolgenden Additionen stattfindenden Rechtsverschiebungen, erzeugt

die Größe des dritten Ausdruckes f(x„)

₂m

obigen Gleichung (5). Nach der Initialaddition werden die Gatter 33 bzw. 34 geöffnet, je nach dem Wert des untersten, im Multiplikatorregister 29 gespeicherten Bits. Der Inhalt des Akkumulators 31 wird zu dem des ausgewählten Registers 25 bzw. 26 über das Addierwerk 35 addiert und durch das Übertragungsgatter 70 in den Akkumulator 36 übergeführt. Anschließend wird das Teilprodukt aus dem Akkumulator 36 in den zweiten Akkumulator 31 zur Vorbereitung des nächsten Additionsschrittes übertragen. Die Übertragungsgatter 37 und 70 werden zu verschiedenen Zeiten während des Operationszyklus in Betrieb gesetzt, wie durch die Bezeichnung Φ_Α und Φ_Β angegeben ist. In diesem arithmetischen Stromkreis sichert die Verwendung der beiden Akkumulatoren 36 und 31 die Stabilität in den Additionsoperationen. Da die Übertragungsgatter 70 und 37 nicht gleichzeitig »offen« sind, ist keine geschlossene Schleife gegeben, wie sie vorhanden wäre, wenn der Akkumulator 31 seinen Inhalt in das Addierwerk 35, damit in den Akkumulator 36 und weiter zum ursprünglichen Akkumulator 31 weitergäbe. Offensichtlich kann der Inhalt des Akkumulators 31 zusammen mit einem weiteren Multiplikanden durch das Addierwerk geleitet werden, um den Akkumulator 36 in einem stabilen Zustand zu halten. Als zweiter Schritt kann der Inhalt des Akkumulators 36 in den Akkumulator 31 übertragen werden. Die Rechtsverschiebung kann durchgeführt werden, während der Inhalt des Akkumulators 36 in den Akkumulator 31 geleitet wird. Während dieser Übertragung kann die unterste Binärstelle des Akkumulators 36 in das Multiplikatorregister 29 übertragen werden, während die anderen binären Stellen dem Akkumulator 31 zugeführt werden.

Bei allen aufeinanderfolgenden Additionsschritten wird die jeweils unterste Stelle des Multiplikator-

609 609/334

registers 29 vom Stromkreis 32 abgefühlt; dann wird das Register nach rechts verschoben, dabei die unterste Stelle fallengelassen und das nächsthöhere Bit in die unterste Registerstelle geschoben. Während die Stellen des Multiplikators nach rechts verschoben, abgefragt und hinausgeschoben werden, werden weitere Stellen vom Akkumulator 36 in die frei gewordenen Stellen des Registers 29 übergeführt. Nachdem sämtliche aufeinanderfolgenden Additionen durchgeführt sind, sind die Stellen des Multiplikators alle abgefragt und aus dem Register 29 hinausgeschoben worden, und die untersten Stellen des Produktes nehmen dann diese Register ein. Die höchsten Stellen des Produktes erscheinen im Akkumulator 31. In einer letzten Übertragungsoperation läßt ein Satz von Ausgangsgattern 72 alle gewünschten Produktstellen zu den Ausgangsklemmen 73 gelangen. Offensichtlich kann eine Abrundung durchgeführt werden, bei der beliebig viele oder alle unteren im Register 29 stehenden Stellen fallengelassen werden. Wenn es in der Tat nicht erwünscht ist, die Produktausgangsgröße auf eine größere Genauigkeit zu bringen als die Eingangsgrößen, so braucht das Multiplikatorregister nicht verwendet zu werden, um die unteren Binärstellen zu speichern, und der Akkumulator 31 allein enthält das Produkt.

Will man eine Funktion von zwei oder mehr Veränderlichen interpolieren, so müssen mehrere Interpolationsoperationen durchgeführt werden, wie oben im Zusammenhang mit F i g. 3 besprochen. Nach dem ersten Interpolationsvorgang kann der Inhalt des Akkumulators 31 über ein IRA-Eingangsgatter 75 in ein Zwischenregister 74 übertragen werden. Das Zwischenregister 74 hält dann das Ergebnis der ersten Interpolation aufrecht, während eine zweite Interpolation durchgeführt wird. Die Größe, die sich aus der zweiten Interpolation ergibt, kann von dort durch das IRB-Eingangsgatter 76 in ein weiteres Register 77 und von dort durch das IRB-Übertragungsgatter 78 in das Multiplikandenregister 26 geleitet werden. In ähnlicher Art und Weise kann der Inhalt des Registers 74 über das IRA-Übertragungsgatter 79 in das andere Multiplikandenregister 25 geleitet und eine Schlußinterpolation durchgeführt werden. Wenn es erwünscht ist, eine Funktion von drei Veränderlichen zu erzielen, kann eine erste Interpolation durchgeführt werden, deren Ergebnis im Register 74 gespeichert wird. Die Ergebnisse einer zweiten Interpolation können im Register 77 gespeichert werden. Eine dritte Interpolation kann von dort aus zwischen dem Inhalt der Register 74 und 77 durchgeführt werden, und die sich ergebenden Signale können wiederum in dem Register 74 gespeichert werden. Die bei einer vierten Interpolation entstehenden Signale werden im Register 77 gespeichert, und eine fünfte Interpolation kann von dort durchgeführt werden, deren Ergebnis wieder im Akkumulator 31 gespeichert wird. Für die sechste Interpolation kann der Inhalt der Register 74 und 77 in die Register 25 und 26 übertragen und von dort kann der Inhalt des Akkumulators 31 zum Register 74 geleitet werden. Das siebte und letzte Interpolationsergebnis kann dann über das Ausgangsgatter 72 zu den Ausgangsendklemmen 73 geleitet werden.

In einem Spezialrechner, wie etwa einem Flugsimulator, können die zu erzeugenden Ausgangssignale Funktionen von einer, zwei pder drei Veränderlichen sein und, wie beschrieben, berechnet werden. Viele dieser Funktionen wurden empirisch von beobachteten Daten abgeleitet und haben sich als kontinuierliche Kurven ohne jegliche Diskontinuitäten, Sprünge oder scharfe Spitzen innerhalb des zu interpolierenden Arbeitsbereichs erwiesen. Es hat sich gezeigt, daß Linearinterpolationen zwischen benachbarten Teilpunkten der aufgezeichneten Funktion Ausgangssignale mit einer Genauigkeit von zwölf bis vierzehn binären Stellen hefern, was einem Fehler

ίο von ungefähr 0,01% äquivalent ist. Es kann daher gesagt werden, daß die Notwendigkeit der Darstellung von Funktionen als eine Serie geradliniger Segmente in gleichen Abständen entlang der Abszisse keinen erheblichen Fehler in die Berechnungen einbringt.

Wie in F i g. 2 dargestellt, kann jede der Funktionen mit den Werten für neun Teilpunkte gespeichert werden, um acht lineare Segmente zu schaffen. Da die drei höchsten Stellen acht binäre Kombinationen erlauben, kann, wie durch F i g. 2 dargestellt, jedes Liniensegment mit einem der Werte X₀ bis X₇ identifiziert werden, was den binären Zahlen 000 bis 111 entspricht. Offensichtlich kann dieses Rechenverfahren ausgedehnt werden, um eine größere Genauigkeit mit zusätzlichen gespeicherten Teilpunktwerten zu schaffen. Beispielsweise können die Funktionskurven 17 Teilpunkte haben. Dadurch ergeben sich sechzehn lineare Segmente, die mit den sechzehn binären Kombinationen identifiziert werden können, die durch die vier höchsten Stellen der Eingangsgrößen dargestellt werden.

Claims (7)

Patentansprüche:

1. Digitaler Interpolationsrechner, gekennzeichnet durch ein Multiplikatorregister

(29) für die unabhängige Veränderliche, ein Multiplikandenregister (25) zur Aufnahme des kleineren und ein weiteres Multiplikandenregister (26) zur Aufnahme des größeren der bei-

■to den Eingabelungsfunktionswerte aus einem Speicher (12), der die Funktionswerte für ausgewählte Abszissenpunkte enthält, und eine Schaltung, die in einzelnen Phasen zunächst den Inhalt des ersten Multiplikandenregisters mittels eines Übertragungsgatters (30) in einen Produktakkumulator (31) kopiert, sodann die jeweils unterste Stufe des Multiplikatorregisters (29) mittels einer Abfühlanordnung (32) prüft, bei einer Eins in dieser Stelle den größeren, bei einer Null den kleineren Multiplikanden über ein Addierwerk (35) als jeweiliges binäres Teilprodukt zum Inhalt des Produktakkumulators (31) hinzuaddiert und nach jedem Rechenschritt das darin entstehende Teilergebnis sowie den Multiplikator um eine Stelle nach rechts verschiebt.

2. Interpolationsrechner nach Anspruch 1, ge-. kennzeichnet durch eine Vergleichsstufe (18), die bei Übereinstimmung der oberen Stellen eines Eingangsregisters (13) mit einem Speicheradreß-. zähler (17) die Inhalte der dem Zähler entsprechenden Speicherplätze über eine Ladelogik (20) mittels Eingangsgattern (21, 23) in die Multiplikandenregister (25, 26) überträgt.

3. Interpolationsrechner nach Anspruch 2, gekennzeichnet durch ein weiteres Eingangsregister (14), das mit einer weiteren Vergleichsstufe (18) und einem Zähler (58) zusammenwirkt, und zwei Zwischenregister (74, 77) zur zwischenzeitlichen

Aufnahme der jeweiligen Inhalte des Produktakkumulators (31) und deren Wiedergabe an die Multiplikandenregister (25,26).

4. Interpolationsrechner nach Anspruch 3, gekennzeichnet durch ein drittes Eingangsregister (15), das mit einem Zähler (50) und einer dritten Vergleichsstufe (18) zusammenwirkt.

5. Interpolationsrechner nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß die gespeicherten Funktionswerte zu äquidis'tanten Abszissenpunkten gehören und das Multiplikatorregister (29) nur die untersten Bits des jeweiligen Eingangsregisters (13,14, 15) aufnimmt.

6. Interpolationsrechner nach einem der vorhergehenden Ansprüche, gekennzeichnet durch zwei Akkumulatoren (31, 36), von denen der erste (36) seinen Inhalt mittels eines Übertragungsgatters (37) in bestimmten Phasen um eine

Stelle verschoben an den zweiten Akkumulator (31) abgibt, der seinerseits seinen Inhalt mittels eines Ubertragungsgatters (70) und des Addierwerks (35) in Zwischenphasen zum Inhalt des ersten hinzuaddieren kann.

7. Interpolationsrechner nach Anspruch 6, gekennzeichnet durch bitweise Verschiebung des Inhalts des Multiplikatorregisters (29) bei jedem Rechenschritt und Übertragung der aus dem Akkumulator (36) herausgeschobenen unteren Bits in die frei werdenden Stellen des Multiplikatorregisters (29).

In Betracht gezogene Druckschriften:
»Handbook of Automation, Computation and

Control«, Vol. 1, The Ramo-Wooldridge Corp., Los Angeles, 1958, S. 14—01 bis 14—06;

»A. I. E. E. Transactions«, Part I, Juli 1958,

S. 316 bis 319.

Hierzu 1 Blatt Zeichnungen

609 609/334 8.66 © Bundesdruckerei Berlin