DE2135590A1 - Vorrichtung und Verfahren zur Er zeugung trigonometrischer und anderer Funktionen - Google Patents

Description

Patentanwälte

Dr.-Ing. Wilhelm ßeichel Dipl-Ing. Woligang Reichel

6 Frankfurt a. M. 1

Parkeiraße 13

THE SOLARTRON ELECTRONIC GROUP LIMITED, Farnborough, England

Vorrichtung und Verfahren zur Erzeugung trigonometrischer und anderer Funktionen

Die Erfindung betrifft eine Vorrichtung und ein Verfahren zur Erzeugung trigonometrischer und anderer Funktionen durch Interpolation zwischen zwei Punktwerten. Es gibt zahlreiche Fälle in der Datenverarbeitung, in denen es erforderlich ist, den Wert einer Funktion F(x) für irgendeinen Wert von χ innerhalb eines vorgegebenen Bereiches zu kennen. F(x) kann in einem Festspeicher (auch Festwertspeicher genannt) tabuliert werden, doch wird die Größe des Speichers übermäßig, wenn bis auf eine Genauigkeit von beispielsweise 16 Bits gerechnet werden soll. Es gibt die verschiedensten bekannten Interpolationsverfahren, doch wenden diese hauptsächlich nur die lineare Interpolation an, so daß eine große Anzahl von Punktwerten der Funktion F(x) oder der ersten Differenzen dieser Werte gespeichert werden müssen, um die gewünschte Kurve hinreichend genau anzunähern.

Die Erfindung umfaßt die Entwicklung einer linearen Interpolation, bei der quadratische, kubische und höhere Korrekturglieder berücksichtigt werden können, so daß eine äußerste genaue Interpolation durchgeführt werden kann. Bei diesen Gliedern kann es sich um die Glieder einer polynomen Reihe handeln, die im folgenden binäre polynome Reihe genannt wird und deren Eigenschaften nachstehend erläutert werden.

109884/1779

Das Prinzip des nach der Erfindung angewandten Interpolationsverfahrens wird Interpolation durch wiederholte Zweiteilung des Interpolationssegments, d.h. des Segments, das die beiden Punktwerte der Funktion verbindet, die den vorgegebenen Wert von x, der unabhängigen Variablen, einklammern, genannt. Der Punktwert in der Mitte dieses Segments läßt sich durch Interpolation ermitteln. Dann erhält man zwei neue Halbsegmente, d.h. die durch Zweiteilung des ursprünglichen Segments gebildeten Hälften, von denen die eine den vorgegebenen Wert von χ enthält und das neue, interessierende Segment ist. Dieses Segment kann in der gleichen Weise zweigeteilt v/erden, usv/. so )| oftwie es erwünscht ist, wobei man sich dem vorgegebenen χ annähert. Die wiederholte -Zweiteilung des Interpolationssegments ist daher ein iterativer Vorgang, der sich sehr leicht durch eine Hardware oder Software ausführen läßt.

Nach der Erfindung wird eine Vorrichtung zum Interpolieren des Wertes einer Funktion einer unabhängigen Variablen durch wiederholte Zweiteilung eines Wertebereiches der unabhängigen Variablen geschaffen, mit mindestens einem ersten, zweiten und dritten Register zum Speichern von Größen, die die Funktion definieren, und mit einer Vorrichtung zum Eingeben einer linearen Kombination des durch eine Potenz von zwei devidierten Inhalts eines oder mehrerer der Register in jedes Register, wobei die Potentz für alle Register unterschiedlich ist und die lineare Kombination bei mindestens einem der Register wählbar in Abhängigkeit von Bits eines binären Wortes, das den Wert der unabhängigen Variablen darstellt, steuerbar ist und die Bits nacheinander abgearbeitet werden, und zwar jeweils ein Bit pro Zweiteilung.

Zur Erzielung einer hinreichenden Genauigkeit sind vorzugsweise mehr als drei Register vorgesehen. Neben dem ersten und zweiten Register können daher mehrere geordnete Register vorgesehen sein, die das dritte Register umfassen, von denen jedes eine lineare algebraische Kombination ihres eigenen Inhalts

109884/1779

mit Ausnahme des Registers der höchsten Ordnung, den Inhalt des Registers oder der Register höherer Ordnung erhält, wobei diese Kombination durch 2 = 4 im Falle des dritten Registers, durch 2? = 8 im Falle des vierten Registers usw. dividiert wird, wenn mehr als drei Register vorgesehen sind.

Bei den Anfangseingaben in das dritte und jedes Register höherer Ordnung muß es sich um genau vorherbestimmte Y/erte handeln, die der Funktion angepaßt sind, die interpoliert wird, und sie werden vorzugsweise von einem Festspeicher zusammen mit den beiden Anfangspunktwerten vorgegeben. Nach der Erfindung ist es möglich, Funktionen aus einer sehr kleinen gespeicherten Informationsmenge genau zu interpolieren.

Die Vorteile der Erfindung'können an Hand einiger Beispiele kurz erläutert werden. Die Funktion sin χ kann in einem Bereich von 0° bis 90° bis auf eine Genauigkeit von 12 Bits unter Verwendung von (neben den beiden Anfangswerten von sin 0° und sin 90°) nicht mehr als drei Koeffizienten als gespeicherte Information für jeweils quadratische, kubische und biquadratische Glieder interpoliert werden. Darüberhinaus läßt sich mit Hilfe der gleichen Hardware oder Software eine ganze Gruppe anderer Funktionen interpolieren, wobei für jede von diesen lediglich zwei geeignete Anfangswerte und drei Koeffizienten gespeichert zu werden brauchen.

Bei den Registern kann es sich um -Einzel- oder Sonderregister in Spezialzweckrecheneinrichtungen handeln, wie bei nachstehend beschriebenen Ausführungsbeispielen. Sie können jedoch auch aus verschiedenen Adressen im Speicher eines Universal- oder Mehrzweck-Digitalrechners bestehen, der so programmiert ist, daß er wie die nach der Erfindung ausgebildete Vorrichtung wirkt.

Die iterative Bildung der linearen algebraischen Kombinationen stellt einen Algorithmus dar, dessen genaue Form stark unterschiedlich sein kann. Spezielle Beispiele und einige mögliche

109884/1779

. Abwandlungen der Algorithmen sind nachstehend erläutert. Es ist unmöglich, alle Abwandlungen anzugeben, die vorgenommen werden können. Die Form des Algorithmus ist weitgehend von den als Anfangswerten gewählten Größen abhängig, die in die . Register eingegeben werden. Dies brauchen nicht die hier angegebenen Größen zu sein. Als Beispiel für einen Algorithmus mit entsprechenden Abwandungen sei die Bildung einer Folge oder Reihe von Interpolationen angegeben, bei denen als Anfangswerte Abtastwerte der abhängigen Variablen verwendet werden. Dabei wird jedoch immer noch das gleiche Schema der Registrierung in den Registern verwendet, nämlich a : 1 im ersten * Register, a : 2 im zweiten Register, a : 4 im dritten Register usw.

Im Prinzip handelt es sich bei den Algorithmen^ um Additions-Schiebe-Algorithmen, die leicht durchführbar sind, da die einzigen Operationen, die erforderlich sind, Additionen (unter Berücksichtigung des Vorzeichens) und Stellenverschiöbungen, bei denen sich eine Division durch 2, 4 usw. ergibt, sind. Diese Verschiebungen lassen sich, wie nachstehend beschrieben wird,, leicht bitseriell durchführen. Für einen Bitparallel-• Betrieb gibt es ebenfalls Verfahren zur Durchführung der Ver-Schiebungen. Ein Verfahren besteht in der Verwendung von Par- \ allelzugriff-Registern, die auch Schieberegister darstellen. Nachdem 'eine Zahl über einen Bitparallel-Mehrfachkanal in ein Register eingegeben v/orden ist, werden Schiebeimpulse zugeführt, um durch die erforderliche Potenz von 2 zu dividieren. Ein anderes Verfahren besteht darin, die Zahl über einen Datenmehr fachkanal einzugeben, der derart an das Register angeschlossen ist, daß die Eingabe mit bereits erfolgter Verschiebung durchgeführt wird. Um beispielsweise durch 4 zu dividieren, ist der höchststellige Kanal des Mehrfachkanals mit der dritt- ■ höchsten Bitstelle des Registers, das zweithöchste Bit des Kanals des Mehrfachkanals mit der vierthöchsten Bitstelle des Registers usw. verbunden.

10988A/1779

Soweit beschrieben, wird, der Algorithmus im Vorwärtsbetrieb verwendet, d.h. χ vorgegeben und y berechnet. Ein wesentlicher Vorteil der Erfindung besteht darin, daß die Algorithmen leicht im umgekehrten Betrieb angewandt werden können, d.h. um χ zu berechnen, wenn y vorgegeben ist. So kann beispielsweise die gleiche Hardware zur Berechnung von sin χ im Vorwärtsbetrieb und von aresin y im umgekehrten Betrieb verwendet werden. Dies ist möglich, weil im Vorwärtsbetrieb die aufeinanderfolgenden Bestimmungen, ob das obere oder untere Halbsegment ausgewählt werden soll, von den aufeinanderfolgenden Bits von χ bitweise gesteuert werden.- Im Umkehrbetrieb wird bei jeder Interpolation geprüft, ob die Auswahl des oberen Halbsegments das berechnete y größer oder nicht größer als das gegebene y, das als Y geschrieben wird, macht. Wenn y kleiner als Y ist, wird ein 1-Bit in χ eingegeben und die Auswahl des oberen Halbsegments beibehalten. Wenn y größer als Y ist, wird ein O-Bit in χ eingegeben und die Auswahl des oberen Halbsegments gelöscht und das untere Halbsegment gewählt. Auf diese Weise bewirken die aufeinanderfolgenden Interpolationen eine Annäherung des berechneten y an das vorgegebene Y, und die Bits von χ werden entsprechend vom höchststelligen Bit an abwärts aufgebaut. Wenn jedoch in irgendeiner Stufe y = Y, kann der Vorgang bei allen restlichen Bits von x=0 abgeschlossen werden.

Die Erfindung und ihre Weiterbildungen, die in den Ansprüchen gekennzeichnet sind, werden an Hand der beiliegenden Zeichnungen bevorzugter Ausführungsbeispiele näher beschrieben.

Die Fig. 1 stellt eine lineare Interpolation dar.

Die Figuren 2 und 3 stellen eine quadratische Interpolation

dar. .

Die Fig. 4 stellt ein Blockschaltbild eines Ausfüh

rungsbeispiels nach der Erfindung zur Ausführung des quadratischen Interpolationsalgorithmus dar.

109884/1779

Die Figuren 5 und Die Fig. 7

Die Fig. 7A Die Figuren 8A bis 8G

Die Figuren 9 bis Die Fig. 11A Die Fig. 14

Die Fig; 15

Die Fig. 16

Die Fig. 17 stellen die Anwendung binärer Reihen zur Annäherung der Funktion sin θ dar.

stellt ein Blockschaltbild eines Ausführungsbeispiels nach der Erfindung zur Ausführung des kubischen Interpolationsalgorithmus dar. -

stellt eine Zeitsteuerschaltung für Fig. 7 dar.

stellen grafisch den Verlauf der binären Polynome der zweiten bis · achten Ordnung dar.

stellen Flußdiagramme der quadratischen bis oktalen Algorithmen dar.

zeigt eine Abwandlung des quartischen Algorithmus nach Fig. 11.

ist ein Blockschaltbild der wesentlichen Einzelheiten eines weiteren Außführungsbeispiels nach der Erfindung zur Durchführung des kubischen Algorithmus unter Verwendung einer bitparallelen, wortseriellen Arithmetik.

ist ein Blockschaltbild der wesentlichen Einzelheiten eines weiteren Ausführungsbeispiels nach der Erfindung zur Durchführung des kubischen Algorithmus unter Verwendung.einer bitseriellen, wortseriellen Arithmetik.

ist ein Blockschaltbild, das die Anwen-'dung eines Algorithmus im Umkehrbetrieb darstellt.

stellt in Form eines Diagramms die Bestimmung der Koeffizienten für ein binäres Polynom dar.

09884/1779

Interpolation durch wiederholte Zweiteilung

Die Fig. 1 stellt y als eine lineare Funktion von χ in einem Segment von χ = 0 bis χ = 1 dar. y(O) = 2a und y(i) = 2b. Bei der ersten Interpolation erhält man auf einfache V/eise y(-j) = (2a + 2b)/2 = a + b.. Für die zweite Interpolation stehen zwei Möglichkeiten zur Verfügung. Es ist möglich, entweder

zu berechnen, und die Wahl wird in Abhängigkeit davon getroffen, ob der Wert von χ im Bereich von ^ bis 1 oder von 0 bis ^ liegt. Bei Fig. 1 wurde angenommen, daß der gegebene Viert von χ gleich g ist. Die Reihenfolge der Interpolationen, die durch die vertikalen Pfeile symbolisiert werden, ist also

erstens: Interpolation bis y(^) = a .+ b zweitens: Interpolation bis yCr;) = a + ^ drittens: Interpolation bis y(^) = 4υ(τγ) ⁺ "^^) *

Dieses Verfahren kann auf so viele Interpolationen angewandt werden, wie es zur Annäherung von χ mit der gewünschten Ge*- nauigkeit erforderlich ist. Man hat also nach jeder Interpolation die Wahl, entweder einen oberhalb oder einen unterhalb von dem zuletzt berechneten Wert von y liegenden Viert von y zu berechnen, d.h. entweder aufwärts (UP) oder abwärts (DOWN) zu gehen, was entsprechend dem englischen jeweils mit U und D symbolisiert wird. D.h. y(-|) ist U von y(·^) aus und y(^) ist D von y(Ä) ausi

1 09884/1779

Interpolation auf einer Parabel

__————— ^

Fig. 2 zeigt eine Parabel der Form

y = 4x(1-x), wobei y(O) = y(1) = O und y(^) = 1.

Die Interpolation bis y(4·) kann als eine lineare Interpolation plus Addition eines Korrekturgliedes K = 1 angesehen werden, die "Notwendiger Rest" genannt wird und genauer als K-. = 1 definiert wird, wobei η die. Nummer der Interpolation ist. Für

1 die zweite Interpolation gehen wir entweder nach χ = ^- oder

χ = ^, die beide y = 4 ergeben. Wie sich an Hand der Linien 101 und 102 in Fig. 2 ergibt, erhält man durch lineare Interpolation Werte von ^, so daß sich als notwendiger Rest ergibt: ^Kn-2 ⁼ ~k' ^{Es läßt sich leich}'^t zeigen, daß K_n_, = 1/16, K_n_^ = 1/64 usw. ist. So ergibt sich z.B. für y(4) gleich 15/16. Eine lineare Mittelpunkgsinterpolation zwischen y(^) = τ und = 1 ergibt einen Wert von | und (15/16 - 7/8) = 1/16.

Das Schema ergibt K = -r-K _Λ, und dadurch ist es möglich, genau auf einer Parabel zu interpolieren, wenn die zwei Anfangswerte und der Anfangswert von K gegeben sind, wobei dieser Wert vor jeder neuen Interpolation durch 4 dividiert wird. Dies ist in Fig. 3 ausführlicher dargestellt, in der eine Parabel 103 einer geraden Linie 104 überlagert ist. Zur Vereinfachung sind nicht alle Alternativen angegeben, doch erfolgt bei jedem Schritt eine willkürliche Wahl von U oder von D:

= a

κ/4

^U y(§) = £y<i) + h (?) + K/16

U y(7/i6) = £y(|) + Jy(^) + κ/64

109884/1779

■ - 9 -

Die obigen Schlußfolgerungen können zu folgendem Algorithmus zusammengefaßt werden:

^D
u

= ^an ^{+ b}n ^{+ K}n

wobei a^, b^ und K^ zu Anfang vorgegebene (eingegebene) Werte sind.

^an = ^an-1

Verwirklichung des quadratischen Algorithmus

Bevor mit der allgemeinen Entwicklung der Algorithmen fortgefahren wird, erscheint es zweckmäßig, ein einfaches Ausführungsbeispiel der Erfindung zu betrachten, das in Fig. 4 dargestellt ist. Bei diesem Beispiel ist angenommen, daß die Schieberegister zum Speichern der Werte verwendet werden, die in dem Algorithmus erscheinen, und daß Divisionen durch Potenzen von 2 durch das an sich bekannte Verschieben des Inhalts des Registers in Richtung auf abnehmende Stellenwertigkeit durchgeführt werden.

Es sei darauf hingewiesen, daß die schematischen Schaltbilder nicht die Taktimpulsanordnungen zum Verschieben des Inhalts der Schieberegister und zum Markieren der verschiedenen Operationsphasen darstellen. Sie zeigen.auch nicht die Tore, die zum Steuern des Informationsflusses verwendet werden. Die Darstellung dieser Einzelheiten führt zu einer Überladung der Diagramme, zumal diese Einzelheiten dem Fachmann an sich geläufig

109884/1779

sind. Die Zeit- oder Taktsteuerung wird jedoch für Fig. 7 später kurz beschrieben.

Die Schaltung nach Fig. 4 enthält Schieberegister, die mit einem Code gekennzeichnet sind, der mit SR beginnt, und zv/ei Volladdierer FA1 und FA3. Bei den Schieberegistern handelt es sich um folgende:

SRA	enthält	an
SRB	enthält	bn
SRF	enthält	yn
SRK	enthält	Kn
SRx	enthält	X.
a1'	b1 und K	1 ai

Zu Beginn werden a., b.. und K^ aus einem Festspeicher 9 in entsprechende Register übertragen und der gegebene Wert von χ ins Register SRx eingegeben. FA3 addiert a und b zur Bildung von a + b . FA1 addiert K zu dem von FA3 ausgegebenen Ergebnis zur Bildung von y , das ins Register SRF geschoben wird. y_n wird auch zurückgeführt, und zwar mit einer Überverschiebung um ein Bit, um y_n durch 2 zu dividieren und a_n oder b_n in Abhängigkeit davon zu ersetzen, ob der eingegebene V/ert von χ ein Fortschreiten nach U oder nach D verlangt.

Zu diesem Zweck wird das höchststellige Bit im Register SRx durch eine Schaltung 10 geprüft, um festzustellen, ob es eine 0 oder eine 1 ist. Wenn dieses Bit eine 0 ist, werden die beiden Tore 11a durch das Ausgangssignal eines Inverters 10a geöffnet, so daß b_n durch ^y_n ersetzt wird, während a_n einfach umläuft. Wenn das Bit jedoch eine 1· ist, werden zwei Tore 11b geöffnet, so daß a_n durch ^y_n ersetzt wird, während b_n umläuft.

Nach jedem Umlauf über die beiden Addierer wird der Inhalt des Registers SRx um eine Stelle nach links verschoben, um das höchststellige Bit zu löschen und das nächste Bit nach oben in diese Stelle zu verschieben und den nächsten Zyklus vorzuberei-

109884/1779

ten. Sobald alle Ziffern von χ eine O sind, beendet eine Schaltung 13 die Operationen und gestattet die Ausgabe von y aus dem Register SRF.

Die Funktionseinheiten zur Durchführung dieses Algorithmus, sind bei diesem Ausführungsbeispiel einfache. Schieberegister und Addierer. Dies ist möglich, weil bei diesem Algorithmus nur Additionen und Divisionen durch Potenzen von 2, d.h. Verschiebungen, erforderlich sind, so daß dieser Algorithmus Additions-Schiebe-Algorithmus genannt wird. Es sei jedoch darauf hingewiesen, daß die Erfindung nicht auf irgendeine spezielle Art der Durchführung der arithmetischen Operationen beschränkt ist.

Einführung von Gliedern höherer Ordnung

Vor der Betrachtung der Reihen aus binären Polynomen, ist es zweckmäßig, die Aufgabe zu betrachten, die Funktion y = sin θ im Bereich von O⁰ bis 90° zu interpolieren, d.h. χ = 1 entspricht θ = 90°, x=^ entspricht θ = 45° usw. In Fig. 5 ist die Funktion sin θ durch die Kurve 110 dargestellt. Der lineare Interpolationsalgorithmus mit a = 0, b = 0,5 ergibt die Linie 111, die - von der Kurve 110 subtrahiert - die den notwendigen Rest darstellende Kurve 112 ergibt, die angenähert, jedoch nicht genau gleich einer Parabel ist, die als strichpunktierte Kurve 113 dargestellt ist. Sin 45° = 0,70711 und das quadratische Glied des Algorithmus ergeben die Parabel 113, wenn K^ gleich 0,20711 gesetzt wird. Eine sehr viel kleinere den erforderlichen Rest darstellende Kurve bleibt nicht übrig und ist um der Klarheit willen in einem größeren y-Maßstab als Kurve 114 in Fig. 6 dargestellt.

Man erkennt sofort die kubische Grundform dieser Kurve an Hand eines Vergleichs mit einer echten kubischen Kurve 115 der Form C-y x(i-x)(x-^) mit Nulldurchgängen bei χ = 0, i und 1, wobei der Koeffizient C so gewählt ist, daß sich die beste Annäherung an.die Kurve 114 ergibt. Dies wird dadurch erreicht,

109884/1779

daß man die notwendigen Reste bei χ = ^ und ^ gleichgroß und mit entgegengesetztem Vorzeichen wählt. Die neue Restkurve ist die Kurve 116 und hat weitgehend quartische (biquadratische '-Form. Diese läßt sich wieder durch einen Ausdruck in der Form

Q 256 X(^_x) (_x_l)²
3 2

annähern, wobei Q so gewählt wird, daß exakte Gleichheit bei . x = £ und j- vorliegt. Bei diesem Beispiel ist Q in Wirklichkeit ein negativer Koeffizient.

Man sieht, daß der notwendige Rest, insbesondere der schlechteste mögliche notwendige Rest im gesamten Bereich von x, sehr schnell nach Null konvergiert (beachte die unterschiedlichen y-Maßstäbe in den Figuren 5 und 6). Man sieht also, daß zumindest bei regulären Funktionen die binären Reihen, deren Glieder bis zum quartischen Glied betrachtet wurden, ein wirksames Mittel zur Annäherung der Funktionen darstellen. Es wurde ferner bereits dargestellt, daß die Glieder bis zum quartischen Glied mit Hilfe eines einfachen Algorithmus genau interpoliert v/erden können. Dies gilt auch für die Glieder höherer Ordnung, obwohl dann einige zusätzliche, das Verfahren komplizierende Faktoren auftreten. Der kubische Algorithmus erfordert daher

lediglich die Addition eines Gliedes von der Form C =(C „)/8, . η η— λ

das zuerst eingegeben wird, wenn η = 2 ist, doch wird das kubische Glied wegen der bipolaren Form der kubischen Kurve bei einer U-Interpolation (Interpolation mit Aufwärtsschritt- U) addiert und bei einer D-Interpolation (Interpolation mit Abwärtsschritt D) subtrahiert. Dafür wird im folgenden das Sym-

C verwendet.

η ^η

Die Ergänzung der Fig. 4 zur Durchführung des kubischen Algorithmus ist in Fig. 7 dargestellt. Das Schieberegister SRC speichert C_n, und ein weiterer Volladdierer FA2 kombiniert C mit K_n zur Bildung von TK_n, das zu a_n + b_ß addiert wird. Die*¹

10988A/1779

Ausgangsgröße der Schaltung 10 (z.B. eines Flipflop) hat jetzt die zusätzliche Aufgabe, den Volladdierer FA2 zur Addition zu . veranlassen, wenn das x-Bit gleich 1 ist, und zur Subtraktion zu veranlassen, wenn das x-Bit gleich 0 ist.

Der quartische Algorithmus führt ein quartisches Glied

Q. = (Q _-i)/16, wie erwartet werden könnte, ein, doch hat sich herausgestellt, daß eine_ weitere Komplikation insofern entsteht,

als C_n durch TC_n =

8Q ersetzt werden muß, wobei die

Vorzeichenwahl jetzt davon "abhängt, ob der vorhergehende Schritt (n-1) aufwärts (U) oder abwärts (D) erfolgte. Dies wird nachstehend ausführlicher erläutert.

Als Beispiel für die Steueraufgaben sei angenommen, daß die Rechnung bis zu einer 16-Bit-Genauigkeit fortgesetzt wird und das SRA, SRB, SRK und SRC zwanzig Bit lang sind, um Abrundungsfehler zu berücksichtigen. Die Register SRx und SRF sind sechzehn Bit lang. Der Betrieb wird durch einen Haupttaktoszillator

160 (Fig. 7a) gesteuert, der mit einem 23-stufigen Ringzähler

161 über ein Tor 162 verbunden ist,' das geöffnet wird, wenn ein Start-Flipflop 163 gesetzt wird. Ein ODER-Tor 164, das an den ersten zwanzig Stufen des Ringzählers angeschlossen ist, bildet Gruppen aus zwanzig Schiebeimpulsen für jede Gruppe von dreiundzwanzig Schiebeimpulsen, die vom Tor 162 durchgelassen werden. Das Ausgangssignal des ODER-Tores 164 (20 Impulse) wird dem Schiebeeingang des Registers SRF und auch über ODER- · Tore 165 und 166 den Schieberegistern SRA und SRB zugeführt. Dem einen dieser beiden Register wird auch der einundzwanzigste Impuls über ein ODER-Tor I67 oder I68 zugeführt. \lenxi daher das x-Bit = 1 und SRB für einen Umlauf freigegeben ist, muß y_n ins SRA geschoben werden, und zwar mit einer zusätzlichen Verschiebung zur Durchführung der Division durch 2. Zu diesem Zweck schaltet das Signal auf der Leitung 169 von der Schaltung 10 (Fig. 7) das Tor I67 durch, so daß der einundzwanzigste Schiebeimpuls zum ODER-Glied 165 und somit ins FRA durchgelassen wird. Wenn dagegen das x-Bit 0 ist, schaltet das Signal auf der Leitung 170 vom Inverter 10a das

109884/1779

UND-Tor 168 durch.

Wenn die 21. Verschiebung des SRA (oder SRB) stattfindet, muß ein Stellenwertigkeitsbit daran gehindert werden, in die höchste Stelle des SRA (oder SRB) zu gelangen. Zu diesem Zweck wird ein UND-Tor 171 in dem y -Umlaufkreis über einen Inverter 172 während des 21. Schiebeimpulses gesperrt.

Da SRK eine Division durch 4 durchzuführen hat, erhält es sowohl den 21. als auch den 22. Schiebeimpuls über ODER-Tore und 174 zusätzlich zu den zwanzig Ausgangsimpulsen des Tores 164. Während des 21. und 22. Impulses wird ein UND-Tor 175 im TK_n-Umlaufkreis über einen Inverter I76 gesperrt. Das SRC muß eine Division durch 8 durchführen und erhält daher den 21., 22, und 23. Schiebeimpuls über ODER-Tore 177 und 178 sov/ie die zwanzig Ausgangsimpulse des Tores 164. Während des 21., 22. und 23. Impulses wird ein UND-Tor 179 im C -Umlaufkreis über einen Inverter 180 gesperrt.

Der 23. Impuls jeder Gruppe schiebt den Inhalt des Registers SRx um 1 Bit in der umgekehrten Richtung weiter, um das Bit der nächst niedrigeren Stelle von χ in die Steuerposition zu bringen. Wenn eine derartige Verschiebung anzeigt, daß alle x-Ziffern, die im Register SRx verbleiben, 0 sind, gibt die Schaltung 13 das BEENDE-Signal ab. Dies setzt das Flipflop zurück, um das Tor 162 zu sperren und die Operationen zu beenden, wobei der gewünschte Wert vom y im SRP zurückbleibt.

Da SRx sechzehn Bits aufweist, dauert eine ganze Folge von ■ Iterationen bzw. Wiederholungen 16 · 23 = 368 Taktimpulse. Berücksichtigt man weitere 100 .Taktperioden zum Einspeichern von x, a, b, K und C, dann ergibt sich eine Gesamtrechenzeit von 46,8 Mikrosekunden bei Verwendung eines 10 MHz Taktgebers. Als Vergleich sei darauf hingewiesen, daß das bitparallele, wortserielle System nach Fig. 14, das nachstehend beschrieben ist, etwa 88 Taktperioden benötigt, d.h.,8,8 Mikrosekunden bei gleicher Genauigkeit und Taktfrequenz. Das Serien/Serien-

1 09884/ 1 779r

Ausführungsbeispiel nach Fig. 15 benötigt etwa 1560 Taktperioden oder 156 MikrοSekunden.

Die binären Polynome

Im folgenden werden die binären Polynome bis zum optischen Glied angegeben und ihre Eigenschaften erläutert.

Wenn eine polynome Annäherung für y = f(x) in einem bestimmten Bereich von χ verwendet wird, ist es üblich, die Aufgabe zuerst durch Normalisierung in einen x-Bereich von entweder -1 bis +1 oder 0 bis 1 zu transformieren.

Die Klasse der binären Polynome wird auf die beiden obigen x-Bereiche begrenzt, wobei für das Polynom nter Ordnung die folgende Schreibweise benutzt wird:

B für den x-Bereich von -1 bis +1 η

B* für den x-Bereich von 0 bis 1 η

Unabhängig vom x-Bereich bleiben die grafischen Darstellungen der binären Polynome unverändert, obwohl jede Änderung des x-Maßstabes eine neue Gruppe polynomer Ausdrücke zur Folge hat. Im folgenden wird der x-Bereich von 0 bis 1 weiterhin als Beispiel beschrieben.

Die oben beschriebenen Interpolationsvorgänge führen erstens zum halben Viert von x,

zweitens zu den ungeradzahlingen Viertelwerten von x, drittens zu den ungeradzahlingen Achtelwerten von χ usw. durch wiederholte Zweiteilung, die

eine binäre Folge von x-Punkten ergibt. Die Eigenschaft der binliren Polynome besteht darin, daß bei Auswahl der richtigen Werte für die Koeffizienten K., C₂, usw., die Polynome eine exakte Annäherung an so viele Punkte der binären Folge ergeben, wie es bei der verwendeten polynomen Ordnungszahl möglich ist.

109884/1779

Im folgenden sei die Näherung betrachtet: y = g₀

wobei die Faktoren g_n die Koeffizienten und B* die binären Polynome (im x-Bereich von O bis 1) sind. Die für die binäre Folge genau angenäherter Werte erforderlichen Polynome sind:

Punkt genauer Annäherung Erforderliche polynome Glieder χ = O"und 1 g_QBg und g.

*■*

^S2^B

= 7- und

χ = I und § g₅BJ +

χ = i und I _g?B^ + g₈B*

Eine Grundregel ist die, daß, wenn jeder Punkt genauer Annäherung gebildet ist, alle folgenden Polynome diese Annäherung beibehalten. Z.B. liegt nach der quadratischen Approximation eine genaue Annäherung für χ = 0, i und 1 vor. Das kubische Polynom Bf und alle folgenden Polynome müssen daher die Form x(i-x) (x-75·) aufweisen.

Obiges Beispiel fortsetzend^ fordert die Regel, daß das quartische Polynom B£ ebenfalls die Form x(1-x)(x~i) aufweisen muß, da die ermittelten Punkte genauer Annäherung immer noch χ = 0,, Tj· und 1 sind. B^ muß jedoch von vierter Ordnung sein, und die erforderliche Form ergibt sich in der Tat durch Wiederholung des Faktors (x-1). _B£ enthält x(1-x)(x- ^)². g^ und g₄ werden so gewählt, daß sich eine genaue Annäherung bei χ s ■£ und x=^ ergibt. Die quintischen und sextischen Glieder BJ- und Bg müssen daher (x- ^) und (x- |) enthalten, um Nullstellen bei x = 5 und χ = ·| zu erhalten, während g₅ und g_ß so

109884/1779

gewählt werden, daß sich eine genaue Annäherung bei χ = ^ . und x = § ergibt. Die septischen und oktischen Glieder B£ und Bg müssen daher (x - %) und (x - ~) enthalten, und g„ und g_o

O OO ( ή ö

werden so gewählt, daß sich eine genaue Annäherung bei x=-v>

und χ=?? ergibt. Es sei darauf hingewiesen, daß diese Definitionen oder Grenzen nicht die einzigen sind. Z.B. könnten g= und g/- eine genaue Annäherung bei x=h und x=% ergeben, so daß B£ und Bg dann (x - -^) und (x - ■£) enthielten. Als weiteres

f ö O O Λ -2

Beispiel könnten die Nullstellen χ=τ; und χ=χ in Bit und Bg wiederholt werden. In diesem Falle müssen vier Gleichungen für gc, gci grj und g_Q gleichzeitig gelöst werden, um eine

2 ο / α 15 5 7

genaue Annäherung gleichzeitig bei x=^» _:> _? und ·& zu erhalten. Entsprechendes gilt für die B-Polynome.

Jedes binäre Polynom enthält die von χ abhängigen und mit einem Normalisierungsfaktor multiplizierten Faktoren, die in der eben beschriebenen Weise bestimmt werden. Auf den ersten Blick erscheinen die Normalisierungsfaktoren redundant, da sie in die Koeffizienten hineingezogen werden könnten. Sie haben jedoch einen erheblichen praktischen Wert, da ihre Verwendung es ermöglicht, an den Koeffizienten Abrundungsfehler zu erkennen. Nach der Abrundung bzw. dem Abbrechen binärer polynomer Reihen bei irgendeiner Ordnungszahl, kann an dem oder den nächsten Koeffizienten unmittelbar der resultierende Abrundungsfehler festgestellt werden.

Die Normalisierungsfaktoren wurden auf der Basis gebildet, daß der Spitzenwert jedes Polynoms gleich 1 oder ungefähr gleich 1 ist, wie dies für Additions-Schiebe-Algorithmen gilt. Die Additions-Schiebe-Forderung für alle polynomen Vierte, die sich durch Interpolation bei binären x-Werten ergeben, haben die Form

ganze Zahl
binäre Zahl

Z.B. ist ein Wert von 7/8 zulässig, dagegen ein Wert von 8/7 nicht.

109884/1779

Es ist wichtig zu wissen, daß die Normalisierungsfaktoren so gewählt werden können, daß die ganze Zahl jedes geradzahligen Polynoms gleich 1 ist. Die ganzen Zahlen aller ungeradzahligen Polynome sind 0, so daß sich die ganze Zahl der angenäherten Funktion durch die Summe der Koeffizienten der geradzahligen Glieder ergibt.

In den folgenden Tabellen sind die binären Polynome bis zur achten Ordnung angegeben, wobei die Tabelle I die B*-Polynome und die Tabelle Ildie B-Polynome angibt.

109884/1779

TABELLE I

x-Bereich von O bis 1, binäre Polynome

Polynom-Ordnung

Linear

Polynom

=

= 2x -

Quadratisch Bt = 4x(i-x)

Kubisch B* =

Quartisch Bf =

Quintisch B£ =

Sextisch Bg = Septisch

64

x(1-x) (x

15

x(I-X) (x4)(x4)(x-?)

,17

-x) (x-4) (

Bevorzugte

Koeffizienten

Schreibweise

g₀ = (b+a) g₁ = (b-a)

g₂ = K

= Q — j

g₇ =

Oktisch

,19 = ^E

1 09884/1779

	von -1	bis +1,	TABELLE	II
x-Bereich			binäre	Polvnome
Polynom-_ Ordnung	{.. B1	= 1 = X	Polynom	Bn
Linear

Quadratisch B₂ = Bevorzugte

Koeffizienten

Schreibweise

= (b+a)

= (b-a)

= K

Kubisch

B₃ «§> = C

Quartisch Quintisch

B₅ =^> = Q

= I

Sextisch Septisch

¹⁰

B₇ =

x-J) S₇

» S

_ ρ

Oktisch

2 2/

J^₅X (1+x)(1-3

(x+J)(x-J)

109884/1779 = E

Die B -Polynome sind in den Figuren 8A bis 8G von der zweiten bis zur achten Ordnung dargestellt. Die dargestellten Formen gelten auch für die B* -Polynome, wenn man den Bereich von χ = -1 bis χ = +1 als Bereich von O bis 1 ansieht, d.h. -1 durch O, -0,5 durch 0,25, 0 durch 0,5 usw. ersetzt.

Das bereits an Hand der Figuren 5 und β erläuterte Beispiel von sin θ zeigt, wie die binären Polynome zur Annäherung an eine vorgegebene Funktion verwendet werden können. Weitere Hinweise für die Bestimmung der Koeffizienten K, C, Q, usw., werden nachstehend gegeben.

Binäre polynome Algorithmen

Die linearen, quadratischen, kubischen und quartischen Algorithmen wurden bereits in unterschiedlicher Vollständigkeit erläutert. Im folgenden werden die Algorithmen bis zum optischen Algorithmus in einer systematischen Flußdiagrammdarstellung wiedergegeben, bei der die Blöcke die Größen darstellen, wie a , b , K , die in dem Algorithmus vorkommen, während die zur Bestimmung von y führenden Additionen angegeben sind. Die Anfangsbedingungen sind ebenfalls eingetragen. Umlaufkanäle sind nicht dargestellt. Stattdessen enthält jeder Block eine Gleichung, die die Art ihres Umlaufkanals angibt.

Fig. 9 zeigt den quadratischen Algorithmus in dieser Schreibweise, und die Äquivalenz von Fig. 9 mit Fig. 4 wird sofort ersichtlich. Fig. 10 zeigt den kubischen Algorithmus und entspricht der Fig. 7. Vom kubischen Algorithmus an hat es sich bisweilen als zweckmäßig herausgestellt, die ungeradzahligen und geradzahligen Glieder so zu behandeln, als würden sie in getrennten parallelen Kanälen gebildet, die jeweils links und rechts vom Flußdiagramm dargestellt sind. Ferner wird in dieser Schreibweise der notwendige Rest eines Gliedes K , C usw. in der Form ElK_n, RC_n usw. und TK_n = K_n + RK_n, TC_n = C + usw. angegeben.

109884/1779 ©OPY

Um das Verständnis der Flußdiagramme zu erleichtern, wird der

Zusammenhang zwischen den Figuren 10 und 7 angegeben.

Die Gleichung im Block 120 (Fig. 10) wird durch den um das Register SRC in Fig. 7 herum verlaufenden Kreis "Umlauf und Division durch 8" gebildet.

Das Symbol

-D

^+u -r, η ^η

C (Fig. 10) wird durch die ADD/SUB-Steuerung

des Addierers FA2 in Fig. 7 verwirklicht.

Die Gleichung im Block 121 (Fig. 10) wird durch den Kreis "Umlauf und Division durch 4", der um das Register SRK und den Addierer FA2 in Fig. 7 herumführt, gebildet.

Die Gleichungen in den Blöcken 122 und 123 (Fig. 10) werden durch die Tore 11a, b gebildet, die durch die Schaltung 10 nach Fig. 7 gesteuert werden

Die ADD-Operation 124 (Fig. 10) wird durch den Addierer FA2 in Fig. 7 bewirkt.

Die ADD-Operationen 125 und 126 (Fig. 10) werden durch die Addierer FA1 und FA3 in Fig. 7 bewirkt (mit dem trivialen Unterschied, daß die Ordnung der Additionen in zwei Figuren verschieden ist).

Die Figuren 11, 12 und 13 stellen jeweils den quartischen, sextischen und oktischen Algorithmus dar. Die gerätetechnische Verwirklichung dieser Algorithmen ergibt sich im wesent lichen durch eine Analogie mit den Figuren 4 und 7. Da jetzt

~ -DT

jedoch das Symbol

+U

auftritt, muß offensichtlich das

n-1
höchststellige Bit" zwischengespeichert werden, das sich als höchststelliges Bit im Register SRx in der Stufe n-1 ergab, um es in der Stufe η für die entsprechende .Addition/Subtraktion-Steuerung verwenden zu können. Ferner muß neben einem

103884/1779

Register mit einem 1/16-Umlaufkreis für Q auch für eine Eingabe des Gliedes 8Q = (Q_n-1)/^ z.B. über ein Zwischenspeicherregister gesorgt werden. Während also Q--] mit einer 4-Bit-Überverschiebung für die Division durch 16 ins Q -Register zurückgeschoben wird, um Q zu bilden, wird Q_n_-i gleichzeitig nur mit einer 1-Bit-Überverschiebung zur Durchführung einer Division durch 2 und mithin zur Bildung von 8CL in das Zwischenspeicherregister geschoben.". ' . ..

Andere Algorithmen

Vom quartischen Algorithmus an können zahlreiche andere nach der Erfindung gebildete Algorithmen verwendet v/erden. Die in den Figuren 11 bis 13 dargestellten Formen werden als die wirksamsten angesehen. Geringe Wirkungsgradverluste ergeben sich bei Anwendung einer Form, bei der die ungeradzahligen und geradzahligen Glieder nacheinander statt in getrennten Kanälen behandelt werden. Ein Beispiel dieser Alternative ist in Fig. 11A dargestellt, die den abgewandelten Teil von Fig.11 bis zur Bildung von RK zeigt. Der Rest des Algorithmus ist der gleiche.

Bei den soweit angegebenen Algorithmen ergeben sich keine logischen Änderungen, d.h. sobald ein logisches Glied, wie

TC , von η = 2 an wirksam wird, gilt dieser ohne Ande-

rung für alle weiteren Stufen. Ferner wird jeder Anfangswert, wie K, C usw., nur einmal und für alle Fälle eingegeben. Nach der Erfindung wurden jedoch andere Algorithmen entwickelt, bei denen logische Änderungen auftreten und/oder Koeffizienten in einer späteren Stufe eingegeben oder erneut eingegeben werden. Diese Alternativen sind weniger wirksam als die angegebenen Formen, doch liegen sie ebenfalls im Rahmen der Erfindung.

109884/1779

Quintischer bis oktischer Algorithmus

Fig. 12 zeigt das bevorzugte Ausführungsbeispiel für den sex- , tischen Algorithmus. Der quintische Algorithmus ist der gleiche wie der sextische Algorithmus, jedoch durch Weglassen des sextischen Gliedes abgerundet. Tatsächlich stellt Fig. 12 alle Algorithmen bis zum sextischen dar, da der quadratische, kubische und quartische Algorithmus nach den Figuren 9, 10 und 11 leicht aus der Darstellung nach Fig. 12 durch einfaches Abrunden bei dem quadratischen, kubischen oder quintischen Glied entnommen werden können.

Fig. 13 stellt die bevorzugte Form für den oktischen Algorithmus dar, aus dem sich der septische Algorithmus durch Abrundung gewünschtenfalls ergibt. Dieser Algorithmus läßt sich, jedoch nicht durch Abrundung in den sextkhen Algorithmus nach Fig. 12 ändern. Der bei der sechsten Ordnung abgebrochene Algorithmus nach Fig. 13 würde einen völlig brauchbaren sextischen Algorithmus ergeben, doch ist der sextische Algorithmus nach Fig. 12 etwas wirksamer.

Die ersten beiden Glieder des Algorithmus sind in Fig. 13 etwas anders als in den vorherigen Figuren dargestellt. Bei den Figuren 9 bis 12 sind a und b jeweils die Punktwerte von ) y bei dem unteren und oberen x-Wert des Interpolationssegmentes. Wenn die andere Vereinbarung getroffen wird, daß a stets den Punktwert darstellt,- der nicht durch den neu errechneten Punktwert ersetzt wird, dagegen b stets den neu errechneten Punktwert darstellt, d.h. Cy_n-1)/2, ergibt sich die Reihenfolge der Register, wie es in Fig. 13 dargestellt ist.

Der Vorteil der Verwirklichung des Algorithmus in dieser Weise besteht darin, daß sich eine vollständig geordnete Reihenfolge von Registern von der nullten bis zur achten Ordnung er-. gibt, wobei der Inhalt jedes Registers durch 2^m dividiert und m die zugehörige Ordnungszahl ist. Somit erhält man ein 1/1-Register (nullter Ordnung), ein 1/2-Register (erster Ordnung) usw. bis zum 1/256-Register (achter Ordnung).

109884/1779

Gerätetechnische Verwirklichung der Algorithmen

■ Die Figuren 4 und 7 stellen Beispiele für die gerätetechnische Verwirklichung in bitserieller, wortparalleler Form dar, doch hängt die Erfindung nicht von irgendeiner speziellen arithmetischen Form für die Durchführung der Algorithmen ab. Obwohl man von der binären Basis der Algorithmen nicht abgehen kann, so können doch zumindest theoretisch die tatsächlichen Rechenoperationen in einem nichtbinären Zahlensystem ausgeführt werden. In der Praxis dürfte nur das binäre Zahlensystem oder eine Binär-Dezimal-Codierung von Interesse sein, und dafür gibt es dann grundsätzlich vier Möglichkeiten:

1) Bitparalleler, wortparalleler Betrieb. Dadurch ergibt sich zwar eine nahezu sofortige Interpolation, doch ist dafür eine weitere technische Entwicklung erforderlich, bevor diese praktisch angewandt werden kann, so daß sie hier nicht ausführlicher behandelt wird.

2) Bitparalleler, wortserieller Betrieb mit hoher Geschwindigkeit .

3) Bitserieller, wortparalleler Betrieb mit mittlerer Geschwindigkeit.

4) Bitserieller, wortserieller Betrieb mit niedriger Geschwindigkeit.

Diese vier Möglichkeiten können gewünschtenfalls gemischt werden.

Als Beispiel und zum vergleichen "mit der bitseriellen, wortseriellen Lösung nach Fig. 7 zeigen die Figuren 14 und 15 jeweils die Grundmerkmale von Schaltungen zur Ausführung deskubischen Algorithmus in bitparalleler, wortserieller bzw. bitserieller, wortserieller Konfiguration.

Nach Fig. 14 erfolgt der Datenfluß über drei parallele Hauptkanäle (Mehrfachkanäle) H1, H2 und H3. Die Hauptkanäle H1 und

1 09884/1779

H2 bilden die beiden Eingänge eines Paralleladdierers 130, der vier torgesteuerte Ausgänge J1 bis J4 auf v/eist. J1 und J2 sind jeweils auf H1 und H2 zurückgekoppelt. J3 gibt ein HaIbsummenausgangssignal an H3 ab, während J4 lediglich zum Auslesen von y am Ende der Operation dient. H3 sorgt für eine Paralleleingabe in die a-> b -, K- und C -Register 131 bis 134 und wird auch zur Eingabe der Anfangswerte aus einem Festspeicher 135 oder einer anderen Quelle dieser V/erte verwendet. b_n und K_n werden auf den Kanal H1 gegeben, während a_n und C_n auf den Kanal H2 gegeben werden.

Die verschiedenen in der Zeichnung dargestellten Tore werden wählbar durch eine nichtdargestellte Reihenfolgesteuerschaltung betätigt, die die Reihenfolge von Operationen , die nachstehend angegeben sind, in an sich bekannter Weise bestimmt. Die K- und C -Register 133 und 134 sind Schieberegister (obwohl mit parallelem Zugriff) zur Ausführung der erforderlichen Divisionen. Das C_n~Register 134 hat ferner die Möglichkeit einer Komplementbildung zur wählbaren Eingabe von ±C, wie es durch den Algorithmus verlangt wird.

Ein Interpolationszyklus läuft wie folgt ab, unter der Voraus-Setzung, daß alle Anfangswerte eingegeben worden sind, d.h. η = 3 oder höher ist.

1) Addition von C_n oder -C_n auf H2 zu K_n auf H1 zur Bildung von TK_n auf J1.

2) Addition von TK_n auf H1 zu a_n auf H2, Summe auf J2.

3) Addition von TK + a„ auf H2 zu b„ auf H1, zur BiI- j, η η i

dung von ^y_n auf. J3 und Rückführung von ^y_n zu a_n oder b_n·

4) Verschiebung von K_n um zwei Bits und von C_n um drei Bits zur Bildung von K-. und C * .

Wenn η der letzte Zyklus ist, wird die Operation 3) so abgewandelt, daß y am Ausgang J4 erscheint, und die Operation 4) wird natürlich weggelassen.

109884/1779

Fig. 15 zeigt, wie der kubische Algorithmus in bitserieller, v/ortserieller Arithmetik verwirklicht werden kann, und zwar unter Anwendung des an sich bekannten Verfahrens der Speicherung aller Größen in einem einzigen langen Schieberegisterspeicher 14O, das somit bei diesem Ausführungsbeispiel die b -, a -, K- und C -Register enthält. Der Ausgang des Speichers ist mit einem Eingang eines Volladdierers 141 verbunden, dessen Aus'gang mit einem Puffer-Schieberegister 142 verbunden ist, das seinerseits mit dem anderen Eingang des Addierers verbunden ist. Der Volladdierer wird in ähnlicher V/eise auf Addition oder Subtraktion umgeschaltet, wie der Addierer FA2 nach Fig. 2.

Zwei Umlaufkreise sind über eine Umlauf- und Divisionslogik 143 gebildet. In dem ersten Kreis 144 werden die Größen ohne Änderung in Umlauf gebracht. In dem zweiten Kreis 145, in dem auch der Addierer 141 liegt, werden C_n, TK_n und y_n in Umlauf gebracht, wobei letztere (durch 2 dividiert) a oder b in Abhängigkeit davon ersetzt, ob die Interpolation nach oben (U) oder nach unten (D) fortgesetzt wird. Die Logik 143 dividiert y durch 2, TK durch 4 und C durch 8, wobei das erste Bit oder die ersten zwei oder drei Bits der umlaufenden Größe je nach dem vorliegenden Fall gelöscht und dem ersten Viertel (von links) des Schieberegisters 140 ein bis drei zusätzliche Schiebeimpulse zugeführt werden, um das erste nichtgelöschte Bit in die niedrigste Bitstelle des Registers zu bringen, das die umlaufende Größe aufnimmt.

Die Logik 143 steuert auch die Eingabe der Anfangsgrößen aus dem Festspeicher 146.

Ein Interpolationszyklus läuft daher wie folgt ab:

1) Verschiebung von C_n in das Puffer-Register 142 über den Addierer 141 und gleichzeitige Neueingabe von C ins Register 140 über die Logik 143, was einer Division durch 8 (wie erwähnt) entspricht, um C_n+1 = C_n/8 zu bilden.

109884/1779

2) Verschiebung von K aus 14O und C aus 142 über den

Addierer, so gesteuert, daß eine Addition oder Subtraktion r-D'l

entsprechend

ausgeführt wird, um TK zu bilden. Gieich-

zeitige Eingabe von TK_n in 142 und 140, wodurch eine Division durch 4 bei der Eingabe in 140 (wie erwähnt) zur Bildung von K ^ = TK_n/4 durchgeführt wird.

3) Verschiebung von a aus 140 und TK aus 142 über den Addierer zur Bildung von a + TK und dessen Eingabe in 142.

4) Verschiebung von b_n aus 14O und a_n + TK_n aus 142

| über den Addierer zur Bildung von y . Bei Abwärts-Interpolation (D) erfolgt gleichzeitige Eingabe von y über den Kreis 145, um b_n zu ersetzen, und Division durch 2 zur Bildung von b > = y_n/2, wobei a unverändert bleibt, um a ^ = a zu erhalten. Bei Aufwärtsinterpolation (U) erfolgt Eingabe von y in 142 und Rückführung von b über Kreis 144 zur Bildung von b y. = b_n und Fortsetzung mit 5).

5) (Nur Aufwärts (U)). Rückführung von C_n+1 und K_n+^ in unveränderter Form über Kreis 144. Herausschiebung von a aus 14O und gleichzeitiges Verschieben von allein y aus 142 über den Addierer und den Kreis 145, um a zu ersetzen und

' durch 2 zu dividieren, so daß sich ergibt a ^ = y_n/2. Unver- k änderte Rückführung von b ^ über den Kreis 144.

Die zur Erzielung des erwähnten Informationsflusses erforderlichen Tore wurden nicht erwähnt·, weil es dem Fachmann der Rechentechnik geläufig ist, wie er diese Steuerung entsprechend einer vorgeschriebenen Operationsfolge auszuführen hat.

Das Ausführungsbeispiel, bei dem im bitseriellen und wortseriellen Betrieb gearbeitet wird, läßt sich besonders vorteilhaft in MSI- oder LSI-Technik ausführen. In dieser Technik läßt sich ein extrem vielseitiger und genauer Funktionsgenerator nach der Erfindung ausbilden.

10988W1779

Vorzeichen und andere in Betracht zu ziehende Faktoren

Um die Erläuterung des der Erfindung zugrundeliegenden Prinzips zu vereinfachen, wurde das Vorzeichen bislang lediglich mathematisch berücksichtigt (neben einem kurzen Hinweis auf die Komplementierfähigkeit der Register 134 in Fig. 14). In der Praxis muß jedoch auch das Vorzeichen gerätetechnisch verarbeitet werden.

Das bevorzugte Verfahren besteht in der Voranstellung eines Vorzeichenbits vor jede Zahl und in der Verwendung der Zweier-Komplementform für negative Zahlen. Wenn dann die Division durch Überverschiebung bewirkt wird, muß die Logik das niedrigststellige Bit oder die niedrigststelligen Bits durch ein äquivalentes höchststelliges Bit oder äquivalente höchststellige Bits, nämlich O-Bits bei einer positiven Zahl und 1-Bits bei einer negativen Zahl, ersetzen.

Im Hinblick auf die große Anzahl der angewandten Widerholungen, müssen Vorkehrungen zur Berücksichtigung von Abrundungsfehlern getroffen werden. Der Einfachheit halber wird nicht die Verwendung einer Abrundungslogik, sondern von Registern mit Überkapazität (Überlänge) bevorzugt. Für eine Genauigkeit bis auf 24 Bits (Binärstellen) genügt gewöhnlich ein Register mit einer Kapazität von vier Überschußbi.ts. Mit 28~Bit-Registern erhält man daher eine Genauigkeit bis auf 24 Bits, bei vier Überschußbits. Die Anfangswerte von a, b und K sollten mit einem Bit mehr vorgegeben werden, als es der gewünschten Genauigkeit entspricht.

Mehrfachfunktionserzeugung

Es wurde zwar nur die Funktion sin θ ausführlich behandelt, doch dürfte klar sein, daß die binären Polynome auch zur Annäherung zahlreicher anderer Funktionen verwendet werden können, wie Kreis-, Hyperbel-, Exponential-, V/urzel-, reziproke, logarithmische und deren Umkehrfunktionen. Jede Funktion er-

10988A/1779

fordert die Festlegung des passenden Bereiches der unabhängigen Variablen und der richtigen Koeffizienten a, b, K, C usw. für die Funktion. Wenn beispielsweise der quartische Algorithmus angewandt wird, wird ,jede Funktion durch fünf Ausdrücke vollständig beschrieben, so daß die gleiche Hardware so ausgebildet werden kann, daß sich damit jede Funktion erzeugen läßt, vorausgesetzt, daß ein kleiner Festspeicher zur Verfügung steht, in dem die Koeffizienten für die verschiedenen Funktionen enthalten sind. Ein Programm, das Zugriff zu diesen Funktionen verlangt, braucht dann lediglich die richtigen Koeffizienten sowie den Wert der unabhängigen Variablen in dem " Festspeicher zu adressieren.

Verbesserung der Genauigkeit

Der wirksamste Weg, die Interpolationsgenauigkeit zu verbessern, ist im allgemeinen der Übergang auf einen Algorithmus höherer Ordnung, z.B. vom quartischen auf den sextischen. Wenn jedoch eine Gruppe von Funktionen durch die gleiche Hardware erzeugt werden soll, dann sind.darunter häufig bis zu zwei Funktionen, die mehr Schwierigkeiten als die anderen bereiten. Wegen dieser schwierigen Funktionen kann es daher unzweckmäßig sein, einen Algorithmus mit höherer Ordnung zu wählen. Stattdessen können diese Funktionen nach dem an sich bekannten Interpolationsverfahren behandelt werden, bei dem die Funktion in mehrere Zonen oder Anfgangssegmente mit jeweils ihrem eigenen a,, b, K, C usw. unterteilt wird. So wird beispielsweise eine Quadratwurzelfunktion so in Zonen aufgeteilt, daß zumindest die Bereiche χ = 0,5 bis 1 und χ = 0,25 bis 0,5 getrennt behandelt werden. Obwohl mit Hilfe von Algorithmen höherer Ordnung periodische Funktionen interpoliert werden können, z.B. sin θ über 180° oder 360°, kann es dennoch zweckmäßig sein, nur über 90° zu interpolieren und eine Vorzeichen- und Komplementierlogik zur Erzielung eines Vierquadrantenbetriebs, wie dies an sich bekannt ist, zu verwenden.

109884/1779

Eine andere Möglichkeit, die Genauigkeit zu verbessern, besteht darin, nicht allein errechnete Glieder zu verwenden (nach der Eingabe der Anfagnswerte), sondern auch Korrekturglieder zu addieren, z.B. SK oder SC, zumindest bei den ersten Werten von n·. Dies Verfahren wird jedoch nicht bevorzugt, weil die Korrekturglieder in einem Festspeicher gespeichert werden müssen und im allgemeinen für die verschiedenen Kurvensegmente unterschiedlich sind. Trotzdem ist der Speicheraufwand im Vergleich zu bekannten Verfahren sehr gering. Die gleiche Genauigkeit läßt sich jedoch wirksamer durch Anwendung eines Algorithmus mit höherer Ordnung erzielen.

Ein Ausführungsbeispiel der Erfindung, bei dem Korrekturglieder varvenaet werden, ist in der "Provisional specification " der britischen Patentanmeldung 34900/70 beschrieben. Diese Beschreibung ist hier weggelassen, weil die Verwendung von Korrekturgliedern nicht bevorzugt wird, doch sei darauf hingewiesen, daß die vorliegende Fig. 4 die gleiche wie Fig. 1 dieser provisional specification ohne die Mittel zur Eingabe von Korrekturgliedern ist.

Umkehrbetrieb

Diese Algorithmen können auch ohne weiteres im Umkehrbetrieb bzw. auf Umkehrfunktionen angewandt werden, also zur Bestimmung von x, wenn y vorgegeben ist. Das Verfahren besteht in einer schrittweisen Annäherung an y, ähnlich wie bei einem Analog/Digital-Umsetzer, der mit schrittweiser Annäherung arbeitet .

Im Vorwärtsbetrieb (unter Vorwärtsbetrieb wird hier das Gegenteil von Umkehrbetrieb verstanden) steuern die Binärzeichen des x-Registers das Weitergehen in Aufwärts- oder Abwärtsrichtung in jeder Stufe des Interpolationsalgorithmus. Beim Umkehrbetrieb muß daher die Bestimmung, ob aufwärts oder abwärts weitergegangen werden soll, durch einen Vergleich und entsprechendes Laden des x-Schieberegisters durchgeführt werden.

109884/1779

Als Beispiel sei wieder die Funktion sin θ und speziell der Fall aresin 0,800... betrachtet. Mit dem ersten Schritt des Algorithmus muß dann sin 45° = 0,7071 gewählt werden. Ein Vergleich mit 0,800.... zeigt, daß die Lösung zu niedrig ist, so daß der nächste Schritt ausgeführt werden muß - in die erste Binärstelle des x-Registers wird eine 1 gesetzt*

Der nächste Versuch erfolgt mit sin 67^° = 0,9238 Da

die Lösung "zu hoch" ist, erfolgt der nächste Schritt nach unten, und ins x-Register wird eine 0 gesetzt, usw.

Wenn die gespeicherte Funktion monoton ist, ergibt sich nur eine Lösung, doch muß die Grenze oder Definition der +ve- oder -ve-Steigung gespeichert (oder eingegeben) werden. Wenn die Funktion nicht monoton ist, sind zwei oder mehr Lösungen möglich. Einige erste Schritte des Algorithmus werden dann so vorgeschrieben, daß gewährleistet wird, daß sich die gewünschte Lösung ergibt.

Das Prinzip ist in Fig. 16 dargestellt. Der Block 150, der mit ALGORITHMUS beschriftet ist, enthält die a-, b-, K-, usw. Register und zugehörigen Schaltungen, einschließlich den Fest-Speicher zur Eingabe der Anfangswerte. Die Register 151 und 152 für χ und y sind getrennt dargestellt, während ein sog. inverses oder N-Register 153 den vorgegebenen Wert von y enthält. Ein Vergleicher 154 signalisiert, ob y höher, niedriger oder gleich y ist. Eine Schrittlogik 155 setzt dann "Zu hoch" mit "Abwärts" (D) und "Zu niedrig" mit "Aufwärts" (U) gleich, wenn die Steigung der Funktion positiv ist, und ändert die Zuordnung, wenn die Steigung negativ ist.

Funktionen von zwei oder mehr Variablen

Eine Funktion von zwei oder mehr Variablen kann durch binäre polynome Koeffizienten bestimmt und durch wiederholte Anwendung des gleichen Algorithmus interpoliert werden, indem man jedesmal die gleiche Hardware verwendet.

109884/1779

Es sei ein einfaches Beispiel betrachtet, bei dem eine gekrümmte Oberfläche durch ihren Abstand ζ von der x— y-Ebene beschrieben ist und diese Abhängigkeit quadratisch ist. Es seien die Koordinaten χ und y gegeben und ζ gesucht. Für einen bestimmten Wert von y, d.h. y = y¹, ist -die Abhängigkeit ζ von χ durch die Koeffizienten a', b^f und K' bestimmt. Wenn diese drei Koeffizienten gegeben sind, erhält man ζ für irgendeinen Wert von χ durch eine einzige Interpolation des Algorithmus.

Jeder der drei obigen Koeffizienten hat wiederum eine durch drei gespeicherte Koeffizienten bestimmte Abhängigkeit von y.

a ist bestimmt durch a„ b K

a a a

b ist bestimmt durch a^ b^ K^ K ist bestimmt durch a_K b_K K_K

Bei einem gegebenen Wert von y sind daher drei Algorithmus-Durchgänge erforderlich, um die drei Koeffizienten für den letzten Durchgang zu ermitteln.

Bei zwei unabhängigen Variablen müssen daher beim quadratischen Algorithmus neun Wörter gespeichert und vier Interpolationsalgorithmus-Durchgänge erfolgen, während beim kubischen Algorithmus sechzehn Wörter gespeichert und fünf Durchgänge des Algorithmus durchgeführt, werden müssen, usw. Bei drei unabhängigen Variablen erfordert der quadratische Algorithmus siebenundzwanzig Speicherwörter und dreizehn Durchgänge des Algorithmus, während beim kubischen Algorithmus vierundsechzig Wörter gespeichert und einundzwanzig Durchgänge des Algorithmus durchgeführt werden müssen, usw.

Bestimmung der natürlichen Koeffizienten

Die natürlichen Koeffizienten K, C, Q usw. der binären Polynome sind durch diejenigen Koeffizienten festgelegt, die eine genaue Annäherung an die binäre Folge von x-Werten ermögli-

109884/1779

chen, und können leicht algebraisch bestimmt v/erden. Dies ist ein sehr großer Vorteil der binären Polynome, wie ihn die Tschebyscheff-Polynome aufweisen, die gewöhnlich zur Annäherung von Funktionen verwenden werden. Die Tschebyscheff-Polynome sind orthogonal und erfordern ein kompliziertes Multiplikations- und Integratxonsprogramm für die Koeffizientenbestimmung. Die binären Polynome sind nicht orthogonal, sondern die Koeffizientenbestimmung erfolgt rein algebraisch.

In Fig. 17 ist die Länge verschiedener Ordinatenwerte dargestellt. Es sei angenommen, daß die erforderlichen Punktwerte " y(O)> Υίτ) usw. der anzunähernden Funktion bekannt sind.

Für a und b erhält man sofort jeweils iy(O) und -Iy(I). Damit

1
ergibt sich K als y(w) - (a + b). Damit können die beiden zusammengehörigen Gleichungen für C und Q aufgestellt werden.

Die Lösung dieser Gleichungen ergibt:

2C = y(|) - _Ύφ - b + a oder C=^|y(|) - γφ + a - bj

2Q = y(|) + γφ - 2a - 2b -

Setzt man y(?y) = a + b + K und dividiert man durch 2, dann vereinfacht sich dies zu:

Dieses Verfahren kann systematisch erweitert werden. So können zwei zusammengehörige Gleichungen für I und S aus y(-s) und

* 5 ° 7

y(g) und zwei Gleichungen für P und E aus y(^) und y(g) aufgestellt werden.

109884/1779

Die zur Durchführung des Algorithmus verwendete Hardv/are kann selbst zur Unterstützung der Bestimmung der Koeffizienten '

1 13 durch schrittweise Interpolation bis zu χ = ^ ^{x =} "ζ "¹^ Tj! usw. bis zur Ordnungszahl des zur Verfügung stehenden Algorithmus verwendet werden, um dadurch die "notwendigen Restwerte" ζ zu bestimmen, die wie folgt definiert sind:

Ί 1

z(^) =- y(^) - (lineare Interpolation bei χ

z(r) = yCir) "" (quadratische Interpolation bei χ = j·)

ζ(4) = y(4) - (quadratische Interpolation bei x = 4)

z(~) = y(g) - (sextische Interpolation bei χ = 4)

ζ(4) = y(f|) ~ (quartische Interpolation bei χ = 4)

ζ(^) = y(fj) ~ (quartische Interpolation bei χ = §)

z(~) = y(^) - (sextische Interpolation bei χ = ~)

Zur Vereinfachung der Schreibweise wird im folgenden ζ(-Λ) als

^Z1» ^z(tj;) ^a^^{s Z}2» ^z(§) ^^{8 Z}3 ^usw· geschrieben. Dann läßt sich zeigen, daß gilt:

K =

Q =

S = -4(z₅ +
P = Z₇ -

E = |(z₇ +

109884/1779

Abwandlung der natürlichen Koeffizienten

Es lassen sich viele Verfahren angeben, um die natürlichen Koeffizienten so abzuwandeln, daß.entweder die Genauigkeit der Interpolation verbessert oder die Koeffizientenbestinimung vereinfacht wird. Diese Betrachtung ist nicht sehr wichtig, wenn die Koeffizienten für eine genormte Funktionserzeugung programmiert werden, jedoch dann wichtig, wenn die Erfindung bei einer im Echtzeitbetrieb arbeitenden schnellen Datenverarbeitungsanlage angewandt wird. Bei einem derartigen Betrieb . wird die Hardware so programmiert, daß die Koeffizienten in * regelmäßigen Abständen von den Datenabtastungen bestimmt werden und zwischen diesen Abständen die Interpolation in der gewünschten Weise durchgeführt wird.

Die Genauigkeit einer polynomen Annäherung einer Funktion wird normalerweise durch die schlechteste Differenz zwischen der Annäherung und der richtigen Funktion an irgendeiner Stelle des interessierenden x-Bereiches angegeben. Es hat sich gezeigt, daß die folgenden quintischen und sextischen Koeffizienten die Genauigkeit etwas verbessern, wenn die Polynome beim sextischen Glied abgebrochen werden, und offensichtlich sind sie auch sehr viel einfacher zu bestimmen als die natür- ) liehen Koeffizienten:

I« = - Z₁ - Z₃ + Z₅ + Z₇ S¹ = ^(Z₁ - Z₃ - Z₅ + Z₇)

wobei 'alle vier z-Werte nach der quartischen Approximation bestimmt werden.

Derartige abgewandelte Koeffizienten können auch dadurch ermittelt werden, daß man Koeffizienten höherer Ordnung als eigentlich erforderlich bestimmt und die Information von diesen aus zurück in die tatsächlich erforderlichen Koeffizienten "teleskopiert". Wenn beispielsweise beim sextischen Glied ab-

1 09884/1779

gebrochen wird, jedoch die septischen und oktischen Koeffizienten bestimmt werden, dann läßt sich das folgende einfache Schema

S¹ = S + I E
oder ein erweitertes Schema aufstellen:

C1	— P	_,_ P + TE
Q1	= Q	E " 32
I»	= I
S'	= S	Q

Es wurde gezeigt, daß sich bei Anwendung dieses letzten Schemas auf cos θ von 0° bis 90° eine schlechteste Differenz ergibt, <lie nur das 1,20-fache derjenigen beträgt, die sich durch die Tschebyscheff-Polynomanordnung sechster Ordnung ergibt (Tschebyscheff-Polynome sind als die genaueste polynome Annäherung bekannt, die möglich ist). Selbst die binäre polynome Annäherung sechster Ordnung mit natürlichen Koeffizienten ergibt eine schlechteste Differenz von nur dem 5,03-fachen derjenigen nach Tschebyscheff.

Demgegenüber haben die binären Polynome den Vorteil gegenüber Tschebyscheff-Polynomen, daß sie an den Enden des x~Bereiches eine genaue Annäherung ergeben.

Extrapolation

Yfenn die Funktion geeignet ist, können die oben angegebenen Algorithmen zur Extrapolation außerhalb des normalen x-Bereiches verwendet werden. Wählt man den normalen Bereich von 0 bis 1 und nimmt man an, daß die natürlichen Koeffizienten a, b, K, C und Q dafür bereits bestimmt wurden, dann erhält man für die Koeffizienten a¹, b«, K¹,C und Q¹ im Bereich von

1 09884/1779

x=O bis χ = 2 folgendes:

a' = a

b« = 2b - a - 4K - 32G - 192Ü

K' = 4K + 32C + 192Q

C¹ = 8C + 64Q

Q¹ = 16Q

Software-Aufbau

Es sei darauf hingewiesen, daß die Algorithmen leicht durch Programmierung eines digitalen Universal- bzw. Mehrzweckrechners ausgeführt werden können. Die dargestellten Flußdiagramme genügen dem fachkundigen Programmierer als Anweisung. Der Programmaufbau ist sehr einfach, da bei jedem Algorithmus lediglich eine Folge vorzeichengerechter Additionen (einige Vorzeichen sind bedingt bestimmt) und Divisionen von Koeffizienten durchgeführt zu werden braucht.

Re chneraufbau

Im Gegensatz zu dem vorhergehenden Abschnitt muß darauf hingewiesen werden, daß die zur Durchführung eines Algorithmus nach der Erfindung aufgebaute Hardware auch das Herz eines kleinen, aber ungewöhnlich leistungsfähigen Rechners bilden kann. Mit einem kleinen Festspeicher verfügt der Rechner über einen großen Bereich von Funktionen, wie es in dem Abschnitt "Mehrfachfunktionserzeugung" beschrieben wurde. Die gleiche Hardware kann auch zur Durchführung der Grundoperationen Addition und Subtraktion und auch zur Durchführung einer Multiplikation und Division verwendet werden. Die Multiplikation von χ und y entspricht der linearen Interpolation mit a = 0, b = ^y,; während die Division als die Umkehrung der Multiplikation durchgeführt werden kann. So kann die gleiche Hardware als Funktionsgenerator und als Recheneinheit betrieben werden.

109884/1779

Claims (28)

1. Patentansprüche

   /Ό Vorrichtung zum Interpolieren des Wertes einer Funktion einer unabhängigen Variablen durch wiederholte Zweiteilung eines Wertebereiches der unabhängigen Variablen, gekennzeic hnet durch mindestens ein erstes, zweites und drittes Register zum Speichern von Größen, die die Funktion definieren, eine Vorrichtung zum Eingeben einer linearen Kombination des durch eine Potenz von 2 dividierten Inhalts eines oder mehrerer der Register in jedes Register, wobei die Potenz für alle Register unterschiedlich ist und die lineare Kombination bei mindestens einem der Register wählbar in Abhängigkeit von Bits eines benären Wortes, das den Wert der unabhängigen Variablen darstellt, steuerbar ist und die Bits nacheinander abgearbeitet werden und zwar jeweils ein Bit pro Zweiteilung.
2. 2. Vorrichtung nach Anspruch 1,
   dadurch gekennzeichnet, daß das erste und zweite Register Vierte speichern, die den Schnittpunkt und die Steigung bestimmen, die einer linearen Interpolation der Funktion entsprechen.
3. 3. Vorrichtung nach Anspruch 2,
   dadurch gekennzeichnet, daß das erste und zweite Register an den Enden des Interpolationssegments liegende Punktwerte der Funktion speichern.
4. 4. Vorrichtung nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, daß das dritte Register ein Korrekturglied zur Korrektur einer linearen Interpolation speichert.

   109884/1779
5. 5. Vorrichtung nach einem der Ansprüche 1 bis. 4, . dadurch gekennzeichnet, daß die lineare Kombination bei einem der ersten beiden Register durch die nullte Potenz von 2, die lineare Kombination bei dem anderen der ersten beiden· Register durch die erste Potenz von 2 und die lineare Kombination bei dem dritten Register durch eine höhere Potenz von 2 dividiert wird.
6. 6. Vorrichtung nach Anspruch 5,
   dadurch gekennzeichnet,

   daß in das erste oder das zweite Register, je nachdem, ob das k untere oder das obere Halbsegment den gewünschten Wert der unabhängigen Variablen enthält, sein durch die nullte Potenz von 2 dividierter vorheriger Inhalt eingegeben ist, und daß in dem anderen dieser ersten beiden Register die durch die erste Potenz von 2 dividierte Summe des Inhalts mindestens des ersten, zweiten und dritten Registers gespeichert ist.
7. 7. Vorrichtung nach Anspruch 5,
   dadurch gekennzeichnet,

   daß in dem ersten Register der durch die nullte Potenz von 2 dividierte Inhalt des ersten oder zweiten Registers, in Abhängigkeit davon, ob das untere oder das obere Halbsegment den gewünschten Wert der unabhängigen Variablen enthält, und in ψ dem zweiten Register die durch die erste Potenz von 2 dividierte Summe des Inhalts mindestens des ersten, zweiten und dritten Registers gespeichert ist.
8. 8. Vorrichtung nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß zusätzlich zu dem ersten und zweiten Register mehrere geordnete Register vorgesehen sind, die das dritte Register umfassen, von denen mit Ausnahme des Registers der höchsten Ordnung jedes eine lineare algebraische Kombination ihres eigenen Inhalts mit dem Inhalt der (des) Register(s) höherer Ordnung erhält, wobei diese Kombination im Fall des dritten Registers

   2 ^5

   durch 2 =4, im Falle des vierten Registers durch 2^=8 usw. bei weiteren Registern dividiert wird.

   109884/1779
9. 9. Vorrichtung nach Anspruch 8,
   dadurch gekennzeichnet, daß einige der linearen algebraischen Korabinationen ein Vielfaches eines Gliedes höherer Ordnung enthalten, wobei das Vielfache durch Summieren mehrerer Zwischenquotienten gebildet ist, die sich bei der Berechnung des Gliedes höherer Ordnung während der vorausgehenden Interpolation bei aufeinanderfolgenden Divisionen durch 2 ergeben.
10. 10. Vorrichtung nach Anspruch 8 oder 9ι gekennzeichnet durch Mittel, die das Vorzeichen mindestens eines Gliedes in einer linearen algebraischen Kombination in Abhängigkeit davon auswählen, welches Halbsegment bei der vorhergehenden Interpolation ausgewählt wurde.
11. 11. Vorrichtung nach einem der Ansprüche 8 bis 10, gekennzeichnet durch Mittel, die das Vorzeichen mindestens eines Gliedes in einer linearen algebraischen Kombination in Abhängigkeit davon auswählen, welches Halbsegment bei der laufenden Interpolation ausgewählt wird.
12. 12. Vorrichtung nach einem der Ansprüche 1 bis 11, gekennzeichnet durch ein binäres Register zum Speichern eines gegebenen Wertes der unabhängigen Variablen und Mittel zum Prüfen der Bits in diesem Register der Reihe nach, jeweils eines pro Interpolation, um an Hand des Wertes des Bits festzustellen, welches der beiden Hälften des zweigeteilten Segments ausgewählt werden muß.

    109884/1779
13. 13. Vorrichtung nach einem der Ansprüche 1 bis 11, dadurch gekennzeichnet, daß sie im Umkehrbetrieb betreibbar ist, um cen Wert der unabhängigen Variablen zu bestimmen, der einem vorgegebenen Wert der abhängigen Variablen entspricht, wobei bei jeder Interpolation eine Prüfung dahingehend erfolgt, ob der Viert der abhängigen Variablen, die durch Auswahl eines vorbestimmten Halbsegments erzeugt worden ist, größer oder kleiner als der gegebene Viert der abhängigen Variablen ist, um bei einem dieser Vorgänge die vorbestimmte Auswahl beizubehalten und bei dem an- ψ deren Vorgang die vorbestimmte Auswahl durch die Auswahl des anderen Halbsegments zu ersetzen und entsprechend ein 1-Bit oder ein O-Bit in ein Register für die unabhängige Variable einzugeben, wobei die so angegebenen Bits nacheinander in Stellen mit absteigender Stellenwertigkeit eingegeben werden.
14. 14. Vorrichtung nach Anspruch 12 und Anspruch 13, dadurch gekennzeichnet, daß sie als Digitalrechner ausgebildet ist und Steuerschaltungen sowie einen Festspeicher zum Speichern von Anfangswerten, die in die Register eingegeben werden müssen, enthält und daß die Steuerschaltungen derart betreibbar sind, daß sie die Vorrichtung wählbar als Funktionsgenerator oder als Recheneinheit, die eine Multiplikation durch lineare Interpolation und Division durch dessen Umkehrung durchführt, wirken lassen.
15. 15. Vorrichtung nach einem der Ansprüche 1 bis 14, dadurch gekennzeichnet, daß die| Register Schieberegister sind und die Vorrichtung mehrere Volladdierer zum Addieren des Inhalts der Register in bit— seriellem, wortparallelem Betrieb, mehrere Umlaufverbindungen zur erneuten Eingabe der linearen algebraischen Kombinationen in die Register und Steuermittel enthält, die derart betreibbar sind, daß sie eine Überverschiebung der erneut in die Schieberegister eingegebenen Größen bewirken, so daß die Divisionen durch die Potenzen von 2 ausgeführt werden.

    109884/1779
16. 16. Vorrichtung nach einem der Ansprüche 1 bis 14, dadurch gekennzeichnet, daß die Register Parallelzugriff-Register sind und die Vorrichtung einen Paralleladdierer, mehrere Hauptdatenübertragungskanäle, die die Register und den Addierer über wählbar betreibbare Tore verbinden, und Steuermittel enthält, die derart betreibbar sind, daß sie die Tore in einer solchen Reihenfolge betreiben, daß die linearen algebraischen Kombinationen durch eine Folge bitparalleler, wortserieller Operationen gebildet und die so gebildeten Größen in die Register zurückgeleitet werden.
17. 17. Vorrichtung nach Anspruch 16,
    dadurch gekennzeichnet, daß zumindest eines der Register zusätzlich als Schieberegister ausgebildet ist und die Steuermittel derart betreibbar sind, daß die in sie zurückgeleiteten Größen derart verschoben werden, daß die Division durch die entsprechende Potenz von bewirkt wird.
18. 18. Vorrichtung nach einem der Ansprüche 1 bis 14, dadurch gekennzeichnet, daß ein Hauptschieberegister in die erwähnten Register unterteilt ist, daß ein Volladdierer an dem Hauptschieberegister angeschlossen und ein Pufferregister zur Ausführung von Additionen in bitseriellem, wortseriellem Betrieb vorgesehen ist und daß der Ausgang des Addierers mit dem Eingang des Pufferregisters und einem Umlaufkreis zur Rückleitung der linearen algebraischen Kombinationen in die verschiedenen Teile des Hauptregisters über eine Divisionslogik angeschlossen ist, die derart betreibbar ist, daß sie die Kombinationen durch entsprechende Potenzen von 2 dividiert.

    10988A/1779
19. 19. Verfahren zur selbsttätigen Berechnung eines Wertes der einen Variablen von einer ersten und einer zweiten Variablen, die miteinander in Beziehung stehen, entsprechend einem gegebenen Wert der anderen Variablen,

    dadurch gekennzei-chnet, daß eine Gruppe von mindestens drei Anfangswerten, die die Funktion in Abhängigkeit von der zweiten Variablen definieren, wiederholt zur Bildung aufeinanderfolgender Gruppen neuer Werte verarbeitet werden, die nacheinander die Anfangswerte ersetzen, von denen jeder neue Wert aus einer linearen Kombination mindestens eines der Werte aus der vorhergehenden Gruppe besteht, die durch eine entsprechende Potenz von 2 mehrerer verschiedener Potenzen von 2, einschließlich der nullten, ersten und mindestens einer höheren Potenz von 2, dividiert ist, und daß die neuen Werte, die der Division durch die nullte und erste Potenz von 2 entsprechen, wählbar veranlaßt werden, die entsprechenden Werte der vorhergehenden Gruppe in Abhängigkeit von einer vorbestimmten Zuordnung der Größen O und 1 zu Bits in absteigender Reihenfolge der Stellenwertigkeit des ersten Wertes zu ersetzen, derart, daß sich jener eine Wert durch aufeinanderfolgende Lösungen demjenigen Wert nähert, der dem gegebenen Wert jener anderen Variablen entspricht.
20. 20. Verfahren nach Anspruch 19,

    dadu. rch gekennzeichnet, daß' ein angenäherter Wert der Funktion der unabhängigen Variablen durch Interpolation zwischen zwei gespeicherten Punktwerten errechnet wird, daß das Interpolationssegment wiederholt zweigeteilt wird, und zwar durch Mittelpunktsinterpolation innerhalb des Segments und Ersetzen eines der beiden Punktwerte durch den durch die Mittelpunktsinterpolation neu erzeugten Wert, derart, daß ein neues Interpolationssegment erzeugt wird, das den gegebenen Wert der unabhängigen Variablen enthält, und daß die schrittweise kleiner werdenden Segmente in Richtung auf diesen gegebenen Wert konvergieren und bei mindestens einer weiteren Vielzahl der Interpolationen jeder neu erzeugte Wert durch Addition mindestens eines ersten Korrekturgliedes korrigiert wird, wobei das erste Korrekturglied sukzessiv durch 4 dividiert

    109884/1779

    wird, um das Korrekturglied für die sukzessiven Interpolationer. • zu bilden.
21. 21. Verfahren nach Anspruch 20,
    dadurch gekennzeichnet, daß ein zweites Korrekturglied sukzessiv durch 8 dividiert wird, um das Korrekturglied für sukzessive Interpolationen zu bilden.
22. 22. Verfahren nach Anspruch 20,
    dadurch gekennzeichnet, daß mehrere Korrekturglieder zur Korrektur des neu erzeugten Wertes bei der ersten und einigen nachfolgenden Interpolationen eingeführt werden und jedes dieser Korrekturglieder vor jeder sukzessiven Interpolation durch eine entsprechende Potenz von 2 dividiert wird.
23. 23. Verfahren nach Anspruchs22,
    dadurch gekennzeichnet, daß mindestens eines der Korrekturglieder dadurch abgewandelt wird, daß es mit einem Kreuztransferglied kombiniert wird, das ein Vielfaches eines weiteren Korrekturgliedes ist.
24. 24. Verfahren nach Anspruch 22 oder Anspruch 23, dadurch gekennzeichnet, daß das Vorzeichen mindestens eines der Glieder davon abhängig gemacht ist, ob das durch die laufende Interpolation neu erzeugte Segment unterhalb oder oberhalb des in der laufenden Interpolation neu erzeugten Wertes liegt.
25. 25. Verfahren nach einem der Ansprüche 22 bis 24, dadurch gekennzeichnet, daß das Vorzeichen mindestens eines der Glieder davon abhängig gemacht ist, ob das durch die vorhergehende Interpolation erzeugte^ neue Segment unterhalb oder oberhalb des bei der vorhergehenden Interpolation erzeugten neuen Wertes lag.

    109884/1779
26. 26. Verfahren nach einem der Ansprüche 20 bis 25, dadurch gekennzeichnet, daß mehrere Anfangswerte der Korrekturglieder nach demselben Verfahren wie Funktionen einer anderen unabhängigen Variablen berechnet werden.
27. 27. Verfahren nach einem der Ansprüche 20 bis 25, dadurch gekennzeichnet,

    daß Anfangswerte der Korrekturglieder im Echtzeitbetrieb in Abständen aus vorgegebenen Punktwerten der Funktion und zwi- ^ sehen diesen Abständen diejenigen Funktionswerte, die zwischen den Punktwerten liegen, durch die Interpolation berechnet werden.
28. 28 Verfahren nach Anspruch 19,
    dadurch gekennzeichnet, daß der Wert der unabhängigen Variablen entsprechend einem gegebenen Wert der Funktion der unabhängigen Variablen berechnet wird, daß zwei Punktwerte der Funktion, die den gegebenen Wert, einschließen, wiederholt so linear mittelpunktsinterpoliert werden, daß ein neuer Punktwert erzeugt wird, daß der neue Punktwert durch Addition mindestens eines Korrekturgliedes korrigiert wird, daß das Korrekturglied sukzessiv durch 4 di-" vidiert wird, um das Korrekturglied für die sukzessiven Interpolationen zu bilden, daß einer der zwei Punktwerte durch den neuen Punktwert ersetzt wird, um zwei neue Punktwerte zu ermitteln, die den gegebenen Wert einschließen, und daß eine Folge von Bits mit absteigender Stellenwertigkeit, von denen jedes' so festgelegt ist, daß sein Wert anzeigt, ob der obere oder der untere der beiden Punktwerte durch einen neuen Punktwert ersetzt worden ist, aufgestellt wird, um den Wert der unabhängigen Variablen zu bilden.

    K/Gu

    109884/1779

    Leerseite