DE2132999A1 - Datenverarbeitungseinheit zur Ausfuehrung des schnellen Fourier-Transformationsalgorithmus - Google Patents

Description

Dr. phil. G. B. HAGEN

MUNCHEN-SOLLN

Franz-Hais-straße21 München, den2 5. Mai 1971

Telefon796213 ^Dr- H./P./fr

International Business Machines Corporation

Armonk, N.Y. 10504, V.8t.A.

Datenverarbe itungseinheit zur Ausführung des schnellen Fourier-Transformationsalgorithmus

Priorität: 6. Juli 1970; U.S.A.; Nr. 52 332

Die Erfindung bezieht sich auf Datenverarbeitungsanlagen und insbesondere auf numerische Methoden von Lösungen mit Hilfe der diskreten Fourier-!Trans format ion. Die Erfindung betrifft insbesondere die Maschinenausrüstung schneller Fourier-Transformationsalgorithmen für die Berechnung diskreter Fourier-Transformation.

Viele aktuelle Probleme erfordern die Verwendung verschiedener numerischer Methoden für ihre Lösung. Eine in weitem Maße angewendete Technik ist die Integraltransformationsmethode.

109084/1190

Bayerisdie Vereinsbank München 820993

Die gewöhnliche unendliche Fourier-Integraltransformation ist gut bekannt und wird weithin angewendet. Der Physiker beim Lösen einer partiellen Differentialgleichung, der Eachrichteningenieur beim Suchen nach Rauschen urn/der Statistiker bei der Betrachtung von Verteilungen greifen auf Fourier-Transforinationen zurück, und das nicht nur, weil dadurch die mathematische Behandlung vereinfacht wird, sondern auch, weil das Verständnis in Frequenztermen einfacher ist. Die Technik wurde bereits angewendet bei der Sprachsimulation, der Wellenfilterung, der Analyse von seismischen Signalen, der Analyse von Unterwasser-Schallaufnahmen, der Analyse von eLektroencephalographischen Daten und in vielen anderen Bereichen. Viele Anwendungen wurden vorgenommen zum Herausfinden des Energie gehaltes der Frequenzen, die die Signale in den verschiedenen Bereichen bilden. Eine bekannte und billige Methode verwendet eine Reihe von Filtern, aber dabei handelt es sich um eine Analognäherung, die von Natur aus bezüglich ihrer Lösung und Flexibilität begrenzt ist.

Heute werden numerische Probleme generell mit Hilfe eines digitalen Computers giöst, der nicht dafür vorgesehen ist, kontinuierliche Wellenformen zu behandeln, die bei Verwendung von Integraltransfοrmationsmethoden auftreten.

Aus diesem G-runde ist es notwendig, eine kontinuierliche Zeitfolge oder andere Funktionen in eine Reihe von diskreten Datenbeispielen umzuformen, um numerische ' Operationen wie die endliche Fourier-Transformation dieser Beispiele vornehmen zu können. Beispielsweise soll eine Funktion x(t) die folgende Fourier-Transformation haben:

109884/1 190

ID 2872 - 3 -

^a(f)

Dns Inverse ist dann x(t) * / a(f)e^20rifJb df.

(2)

Wird x(t) in Intervallen der Länge Δ t gemessen, dann
„ird die Gleichung (2) an den Meßpunkten jAt, j*0,
-1, ί2,..., ausgedrückt durch

(3)

wobei P » "Z~t— ist. F ist das Zweifache der Nyquist-Frequenz 1/(2At). Jetzt ist der Exponent eine periodische Funktion von f mit der Periode F, so daß bei Änderung
der Variablen der Integration die Gleichung (3) geschrieben

werden kann:

(f)e^27iri3^f/^F df , (4)

a_p

wobei

a (f) -/ a(f+kF) ist. (5)

M ._ T

k—

10 9 8 8 4/1190

Der Index ρ bezeichnet eine periodische Punktion, die durch die Überlagerung der nicht-periodischen Funktion verschoben um alle Vielfachen der Grundperiode gebildet ist. Die Punktion &_Ό(£) wird als Umkehr (aliased version) von a(f) bezeichnet, wobei die Umwandlung relativ zur Nyquist-Frequenz p/2 geschieht.

Da es sich bei äff) um eine periodische Punktion von f handelt, existiert eine Fourier-Reihenentwicklung. Weiter kann aus Gleichung (4) gesehen werden, daß die Koeffizienten dieser Entwicklung gegeben sind durch l/P-Zeiten der Folge x(jZit). Daher besitzt Gleichung (4) die reziproke Gleichung

^ap(^f> -y Y ^x (JAt)₈-²*^/*. (6)

L \

In dem Verhältnis zwischen a (f) und x(,jAt) sind die üblichen Rollen von Zeit und Frequenz vertauscht, d. h. eine periodische kontinuierliche Punktion von Frequenzen entspricht einer Folge von Zeitkoeffizienten. Gleichung (6) ist eine diskrete Fourier-Transforination, sie ist ,jedoch nicht endlich. Betrachtet man jedoch die Werte von a„(f) bei N einen gleichen Abstand voneinander aufwo inenden Punkten zwischen 0 und F, d. h. nimmt man Q_O(f) in Intervallen Δ dann erhält man den folgenden Ausdruck:

d. h. nimmt man a (f) in Intervallen Δ f » P/N ■ 1/(NAt),

Ί0988Λ/1190

ID 2872

β_ρ(ηΔί)

D-O

Das letztere Ergebnis folgt aus der Tatsache, daß Q- JuiDn/ eine periodische Reihe von j mit der Periode N ist. Daher gilt

Lj

D-O

wobei

Zp(t)

x(t+LT)

eine in T » ΝΔ-t » ΐ/Δ, Ρ periodische Punktion

ist.

Gleichung (8) ist die Form der diskreten Fourier Transformation, die definiert wird durch

j-o

(9)

(10)

1 0988Λ/1190

2872 - 6 -

2132399

wobei A_n der n-te Koeffizient der diskreten Fourier-Transformation ist und X. den j-ten Wert der Zeitfolge bezeichnet, die aus N-Werten besteht. Die X. können komplexe Zahlen sein, und die A sind fast immer komplex. Aus Darstellungsgründen wird Gleichung (10) oft geschrieben als

Ii-I

X.W^ , (11)

0-0

wobei ¥ - _e~²2tv^N ist.

Die einfache digitale Form der Fourier-Transformation hat sich jedoch als viel Rechenzeit beanspruchend herausgestellt. In der Vergangenheit wurden Fortschritte erzielt durch Herstellung schnellerer Datenverarbeitungssysteme mit der Entwicklung elektronischer Anlagen. Das ist nicht der Fall bei Signal- und Datenanalysentechniken unter Verwendung von Fourier-Transformation. Hier wurden die Fortschritte durch Mathematiker ausgelöst. Der bedeutendste Fortschritt auf diesem Bereich ist ein Algorithmus zur Rechnung der Fourier-Koeffizienten, der weit weniger Rechenzeit als in der Vergangenheit benötigt. Dieser Algorithmus wurde beschrieben von J. ¥. Cooley und J. W. Tukey in dem Artikel "An algorithm for the Machine Calculation of Complex Fourier Series" in Math, of Comput., April 1965· Dieses weithin als schnelle Fourier-Transformation bekannte Verfahren hat eine Reihe von Änderungen in den Rechentechniken der digitalen Spektralanalyse, der

1 0 98 8 4/1190

Filtersimulatjon und damit zusammenhängenden Bereichen hervorgerufen. Die schnelle Fourier-Transformation ist eine Methode zur wirksamen Berechnung der diskreten Fourier-Transformation einer Zeitenfolge durch aufeinanderfolgendes Kombinieren progressiv größer gewichtiger Summen von Datenwerten, so daß die diskreten Fourier-Transformationskoeffizienten in der in Gleichung (11) definierten Weise erzeugt werden. Die Technik kann interpretiert werden in Termen einer Kombination der diskreten Fourier-Transformationen der individuellen Datenwerte, so daß die auftretenden Zeiten dieser Beispiele nacheinanderfolgend berücksichtigt und den diskreten Fourier-Transformationen von progressiven größeren gemeinsamen exklusiven Untergruppen von Datenwerten zugeführt werden, die kombiniert werden, um schließlich die diskrete Fouriertransformation der vollständigen Reihen der Datenwerte zu erzeugen.

Die diskrete Fourier-Transformation und ihr Inverses haben dieselbe Form, so daß eine Vprarbeitungseinheit ader ein Unterprogramm, das die eine berechnen kann, auch zum berechnen der anderen durch einfaches Austauschen der Rollen von X. und A und die geeignete Änderung des Skalenfaktors und der Vorzeichen ausgeführt werden kann. Es bestehen dann zwei Grundformen der schnellen Fourier-Transformation mit ihren verschiedenen Modifikationen, die deslialb vom Standpunkt der Berechnung äquivalent sind. Wegen ihrer Anwendungen ist die Unterscheidung der beiden Formen ,jedoch wichtig. Die von Cooley und Takey verwendete Form wird al a die zeitsparende Form bezeichnet. Durch

4/1190

ID 2872

Umkehren der Rollen von A und X. wird die Form als in der Frequenz dezimiert bezeichnet, was später

noch betrachtet wird.

Eb soll angenommen werden, daß eine Folge X. N-Werte hat und in zwei Funktionen Y. und Z. unterteilt ist, die jeweils nur die halbe Anzahl N/2 der Werteresitzen.

Die Funktion X- ist zusammengesetzt aus den gerad-

J
zahligen Punkten X_Q, Xp» X*, ···> und Z. aus den ungeradzahligen Punkten X-,, X-, X,-> ...

Diese Funktionen können in der Form geschrieben werden

3-0, 1, 2,

- 1

(12)

Da Y. und Z- Reihen mit N/2-Werten sind, besitzen

<j J

sie diskrete Fourier-Transformationen, die definiert

werden	durch	Y.W
	N
Bn	■E	Z.W2
	ö»o
Cn	N " 2-1

(13)

Die gewünschte diskrete Fourier-Transformation ist A , die in Termen der ungeraden und geraden Werte geschrieben werden kann:

1Ö98Ö4/1190

r¹

"'Σ

Σ ¹E

, (15)

i-O i«0

die unter Anwendung von Gleichung (13) in der folgenden Form geschrieben werden kann:

^An * ^Bn ⁺ *"°η· °~ ⁿ

Für Werte n, die größer sind als N/2 wiederholen die diskreten Fourier-Transformationen B und C periodisch

XX λ XL·

die Werte, die angenommen werden bei η *ζ Ν/2. Deshalb erfolgt bei Ersetzen von η + N/2 in Gleichung (16)

n₊N/2

0<n<N/2. (1?)

Aus den Gleichungen (16) und (17) mit den ersten N/2- und den letzten H/2-Werten der diskreten Pourier-Transformation von X. kann eine Reihe mit N-Werten

109884/1190

ID 2872 - 10 -

einfach erhalten werden aus der diskreten Fourier-Transformation Y. und Z., wobei beide Reihen N/2-Werte besitzen.

Da Y. uns Z. zu transformieren sind und die Berechnung der diskreten Fourier-Transformation von N-Werten auf die Berechnung der diskreten Fourier-Transformation der beiden folgen von jeweils N/2-Beispielen reduziert werden kann, kann die Berechnung von B_n oder C auf die Berechnung der Folge von N/4-Beispielen reduziert werden.. Diese Reduzierung kann ausgeführt werden, solange die Funktion eine durch zwei dividierbare Zahl von Werten besitzt. Ist N » 2 , dann können r solcher Reduktionen vorgenommen werden unter Anwendung der Gleichungen (13), (16) und (17) zunächst für N, dann für K/2,... und schließlich für eine Funktion aus zwei Werten. Die diskrete Fourier-Transformation einer Funktion aus einem Wert ist natürlich die Funktion selbst. Die Operation ist dann vollständig zurückgeführt auf komplexe Multiplikationen und Additionen. Im allgemeinen werden N logρ Ν komplexe Additionen und höchstens 1/2 N logp N komplexe Multiplikationen zur Berechnung der diskreten Fourier-Transformation einer N-wertigen Folge benötigt, wobei N eine Potenz von 2 ist.

Die Einsparung an Rechenarbeit durch Verwendung dieses Algorhythmus kann in einem Beispiel illustriert werden. Bei N » 2^r-Werten werden 2rN oder 2N logo N-Operationen zur Berechnung aller N entsprechenden Fourier-

p Koeffizienten benötigt. Vergleichsweise werden N Operationen bei der herkömmlichen Weise vor der Verwendung der schnellen Fourier-Transformation benötigt.

10 9 8 8 4/1190

Die Reduktion der Rechenzeit ist so groß wie die vollständige Änderung der reehenmäßigen ökonomischen Annäherung an verschiedene Probleme. I¹Ur N * 2 oder 8192 Werte benötigt ein IBM 7094-Computer über 8 Sekunden zur Ableitung aller 8192 Fourier-Koeffizienten. Vorher wurde bei Verwendung der herkömmlichen Methode etwa eine halbe Stunde benötigt. Es soll darauf hingewiesen werden, daß die speziellen Vorteile des Faktors 2 geteilt werden um einen Faktor 4, da die Fourier-Transformation von einer 2 einer 4-punktigen Folge allein durch Addition und Subtraktion ausgeführt werden kann, wodurch eine Stufe der komplexen Arithmetik eliminiert wird. Werden Faktoren von 4 verwendet, dann wird ein Endfaktor von 2 benötigt, wenn r ungerade ist. Diese Technik kann in einigen Beispielen die Wirksamkeit der schnellen Fourier-Transformation verdoppeln.

Die zweite als schnelle Fourier-Transformation bezeichnete Dezimierung in der Frequenz wurde von W. M. Gentleman und G. Sande in Proceedings - Fall Joint Computer Conference 1966 in dem Artikel "Fast Fourier Transforms - For Fun and Profit" beschrieben. Diese Arbeit wurde von G. Sande als Folge einer Anregung von J. W. Tukey begonnen, in der dieser eine ähnliche Ableitung nahelegte. Aus Bequemlichkeit wird im weiteren auf die Sande-Tukey-schnelle Fourier-Transformation oder einfach S-T FFT zur Unterscheidung von der Cooley-Tukey oder C-T FFT Bezug genommen.

Es sei angenommen, daß die Zeitenfolge X. eine diskrete Fourier-transformierte A_n hat, wobei die Reihe und die diskrete Fourier-Transformation beide N-Terme aufweisen. Wie vorher ist X. eingeteilt in zwei Folgen mit jeweils

1098 8A/1190

ID 2872

N/2-Beispielen ; in diesem Fall ist die erste Folge Y. zusammengesetzt aus den ersten N/2-Punkten in X.

und die zweite Folge Z. aus den letzten ΪΤ/2-Punkten

J in X.. Das wird ausgedrückt durch

3=0, 1, 2,

(18)

Die N diskreten Fourier-transformierten von X. können

jetzt in Termen von Y. und Z. geschrieben werden:

J J

N
2-^J

A m _

■ Σ

^)zj

► W'

(19)

Betrachtet man die geradzahligen und die ungeradzahligen Werte der Transformation getrennt, dann sollen die geradzahligen Werte mit R_n und die ungeradzahligen Werte mit S bezeichnet werden, wobei

^Sn - ^A2n₊1

~ η <£ N/2.

(20)

109884/1190

Dieser Schritt wird als Dezimierung in der Frequenz bezeichnet. Für die Berechnung der geradzahligen .Spektralpunkte wird Gleichung (19)

2-1
^Rn -

L r

i -o

(21)

welche wieder erkannt wird als die N/2-Wert-diskrete Fourier-Transformation der Funktion (Y^+Z.), aleo der Summe der ersten N/2- und der letzten N/2-Zeitwerte. In gleicher Weise wird Gleichung (19) für ungeradzahlige Werte

^Sn * ^A2n+1

^N ι T¹

3-0

Y.-Z, / (W^) (W²³ⁿ) (22)

Ί 2

welche als die N/2-Wert-diskrete Fourier-Transformation der Funktion (Y₁-Z-Hw³) erkannt wird.

Aus den Gleichungen (21) und (22) kann geschlossen werden, daß die diskrete Fourier-Transformation einer N-wertigen Eeihe X. folgendermaßen bestimmt werden kann: Für die geradzahligen Transformationswerte werden sie als eine H/2-Wert-diskrete Fourier-Transformation einer einfachen Kombination der ersten N/2- und letzten N/2-Werte von X. berechnet. Für die ungeradzahligen Transfor-

1098Ö4/1190

mationswerte kann ein anderer Punkt-diskrete-Fourier-Transformation von verschiedenen Wertekombinationen der ersten und letzten N/2-Werte von X. berechnet werden.

Ein Vergleich der Methoden der Dezimierung in der Zeit und der Dezimierung in der Frequenz zeigt auch, daß beide Methoden 1/2 N log₂ N-komplexe Additionen, komplexe Subtraktionen und komplexe Multiplikationen benötigen. Ferner können beide Berechnungen gleichermaßen ausgeführt werden. Wenn die Koeffizienten in der Berechnung in einer natürlichen und nicht inBitumgekehrter Ordnung verwendet werden, dann arbeitet die Methode der Dezimierung in der Frequenz auf Zeitwerte in nicht vermischter Ordnung und ergibt Frequenzwerte in vermischter oder Bit-umgekehrter Ordnung. Das Gregenteil tritt bei der Methode der Dezimierung in der Zeit ein.

Aus dem vorhergehenden ist klar geworden, daß die schnelle Fourier-Transformationstechnik ein wichtiges Werkzeug bei der Datenverarbeitung darstellt. Schnelle Fourier-Transformations programme wurden für allgemeine Zwecke für. Digitalcomputer aufgestellt, aber gerade mit der schnellen Fourier-Transformation sind Computer für allgemeine Zwecke unpraktisch für manche Anwendungen, die eine große Menge von. Daten enthalten und Ergebnisse in einer angemessenen Zeit benötigen. Beispielsweise erfordert die reale Zeitsignalverarbeitung von Information eine sehr schnelle Ausführungsgeschwindigkeit. Das gilt auch für Simulationsstudien mit Zugriffsdaten und benötigt Tausende von Transformationen. Für solche

103884/1190

Zwecke sind Verarbeitungsanlagen für spezielle Zwecke, die zur Ausführung des Algori thmus ausgelegt sind, besser zur Ausführung der schnellen Fourier-Transformation geeignet, als Computer für allgemeine Zwecke.

Es ist Aufgabe der Erfindung, eine Datenverarbeitungseinheit zu schaffen, die den schnellen Fourier-Trans formationsalgorithmus in schneller und wirksamer Weise ausführen kann.

Es ist weiter Aufgabe der Erfindung, Mittel zur Bewerkstelligung sowohl der Cooley-Tukey-als auch der Sande-Tukey-Formen der schnellen Fourier-Transformation in einer Datenverarbeitungseinheit zu schaffen.

Es ist weiter Aufgabe der Erfindung, eine Maschineneinriohtung des schnellen Fourier-Transformationsalgor ithmus zu schaffen, so daß die arithmetischen Befehle in jeder beliebigen Basis und multiplen Basis-Cooley-Tukey- oder Sande-Tukey-schnellen Fourier-Transfοrmationsalgor ithmenausgeführt werden kann.

Diese Aufgabe wird durch eine Datenverarbeitungseinheit zur Ausführung des schnellen Fourier-Transformationsalgor ithmus gelöst, die sich gemäß der Erfindung dadurch kennzeichnet, daß arithmetische Mittel zur Lösung der Kerngleichungen des Algor ithmus von der Form W*X^Y mit W als einem komplexen Exponenten, X als einem komplexen Eingangswert eines Eingangsdatensatzes und Y als einer vorher erzeugten Zwjsjhenlösung und einen Mikroprogramm zur Steuerung der arithmetischen Mittel zum Bewirken einer stufenweisen Auswertung des

109884/1190

Algorithmus vorgesehen sind, wobei eine Stufe definiert ist als Auswertung der Kern gleichungen für eine bestimmte Basis über alle Punkte in dem Datensatz.

Befehle werden mikroprogrammiert in einem Nur-Auslesespeicher (read only storage) eines FeldProzessors. Für Basen 2 und 4 werden drei Befehle geschaffen. Jeder dieser Befehle führt eine Stufe des schnellen Fourier-Algor ithmus über den Datensatz von N— komplexen Punkten für die durch den Befehl spezifierte Basis aus. Die stufenweise Ausführung des Algorithmus erlaubt sowohl die Gooley-Tukey- (geordnet zu vermischt) als auch die Sande-Tukey- (vermischt zu geordnet) Formendes auszuführenden Algorithmus. Folglich müssen die Daten bei FiIt er anwendung en nicht vermischt sein (oder vermischt, wie es der Fall sein kann), um die inverse Transformation auszuführen, wie es nötig ist, wenn nur eine der Formen zur Verfügung steht. Die gl.eichzeitige Transformation von Multiplex-Komplex-Datensätzen ist möglich durch kurzes A_nhalten in dem Cooley-Tukey-Algor ithmus oder spät starten in dsm Sande-Tukey-Algor ithmus.

Weitere Merkmale und Zweckmäßigkeiten der Erfindung ergeben sich aus den Figuren und der Beschreibung eines Ausführungsbeispieles. Von den Figuren zeigen:

Fig. 1 ein Blockdiagramm des Basisabschnittes eines Feldprozessors mit einer zentralen Verarbeitungseinheit und einem Hauptspeicher;

Fig.' 2 ein Block- und Datenflußdiagramm von dem Abschnitt und Operations-Fetch-Abschnitt des Feldprozessors;

109884/1190

Pig. 3 ein Block- und Datenflußdiagramm des arithmetischen Abschnittes des Feldprozessors;

Fig. 4 eine Tabelle, die die Feldprozessorantwort auf verschiedene Eingangs-/Ausgangsbefehle von der zentralen Verarbeitungseinheit zeigt;

Fig. 5 eine Tabelle, die das Vorhandensein und Funktionieren der durch den Feldprozessor in Ausführung seiner Rechnungen verwendeten Operanden-Steuerwortformat-Bytes beschreibt;

Fig. 6 ein vereinfachtes Flußdiagramm für den Feldprozessorbefehl "FF2", der bei der Ausführung des schnellen Fourier-Transformationsalgor i thmus für die Basis 2 verwendet wird;

Fig. 7A und 7B^usammen, ein vereinfachtes Flußdiagramm für die Feldprozessorbefehle "FF4" und ⁿWI4-ⁿ , die bei der Ausführung des schnellen Fourier-Transformations algor i thmus für gemischte Basis 2+4 oder 4+2 verwendet wird;

Fig. 8 ein Flußdiagramm des Cooley-Tukey-Basis 2-Algor ithffius unter Verwendung des Feldprozessorbefehle 8 ^BFF2^M;

Fig. 9 ein Flußdiagramm des Cooley-Tukey-Basis 2+4-Algor ithmus unter ^verwendung der FeIdprozessorbefehle "FF2", "FF4" und "FI4";

Fig. 10 ein Flußdiagramm des Cooley-Tukey-Basis 4+2-Algori thmus unter Verwendung der Feld prozessorbefehle "FF2", «FF4^M und "FI4";

Fig. 11 ein Flußdiagramm des Sande-Tukey-Basis 2-Algor ithmus unter Verwendung des Feldprozessorbefehls »Μ2";

Fig. 12 ein Flußdiagramm des Sande-Tukey-Basis 2+4-algor ithmus unter Verwendung der Feldprozessorbefehle "FF2^M, "FF4" und "FI4" und

F-jg. 13 ein Flußdiagramm des Sande-Tukey-Basis 4+2-

Algor ithmus unter Verwendung der Feldprozessorbefehle "FF2«, "FF4" und "FI4".

Bei der digitalen Signalverarbeitung wie bei der periodischen Analyse ausgetasteter Analogeingangsdaten müssen viele sich wiederholende mathematische Operationen ausgeführt

10986Ü/1190

ID 2872 - 18 -

2132939

werden, die eine große Anzahl von Multiplikationen und Summationen erfordern. Trotz der schnellen inneren Geschwindigkeiten von Hochgeschwindigkeitsdigitalcomputern benötigt die Verarbeitung dieser ^Λ Art von Daten durch Normalcomputerbefehle durch Programmierung viel Kosten und Zeit. Die arithmetischen Manipulationen von großen Reihen wie solchen der schnellen Fourier-Transformationsklasse von Algor i thmen werden schneller und wirksamer ausgeführt durch einen für diesen Zweck speziell ausgeführten Computer. Ein solcher als peripherer Prozeßor an eine zentrale Verarbeitungseinheit angeschlossener Computer ist in Fig. gezeigt und mit dem Bezugszeichen 10 . Wie darin gezeigt ist, umfassen eine zentrale Verarbeitungseinheit 11 und ein Hauptspeicher 12 einen Hochgeschwindigkeitsallgemeine Zwecke-Digitalcomputer. In typischer Weise für solche Installationen ist ein Multiplexer 15 mit einer Mehrzahl von Kanälen mit der zentralen Verarbeitungseinheit 11 und dem Hauptspeicher 12 verbunden. Der Ausgang des Multiplexers 11 steht mit einer Mehrzahl von Steuereinheiten 14 in Verbindung, welche eine oder mehrere Eingangs-/Ausgangsvorrichtungen steuern. Wo ein Geschwindigkeits- und Schnellzugriff nicht erforderlich sind, kann auch ein separater Selektor mit der zentralen Verarbeitungseinheit 11 und dem Hauptspeicher 12 verbunden vorgesehen sein. Der Ausgang des Selektors 15 steht mit einer anderen Mehrzahl von Steuereinheiten 16 in Verbindung, welche eine oder mehiwe Eingangs-/Ausgangsvorrichtungen steuern.

Wegen der Art der durch den Computer 10 ausgeführten Operationen kann er als Feldprozessor (array processor) bezeichnet werden. Der Feldprozessor 10 Js t mit der

109884/1190

zentralen Verarbeitungseinheit 11 und dem Hauptspeicher 12 verbunden und arbeitet logisch als ein Eingangs-/ Ausgangskanal mit einer einzelnen integralen Steuereinheit und Vorrichtung. Als ein Ergebnis nimmt der Feldprozessor 10 Eingangs-/Ausgangsbefehle von der zentralen Verarbeitungeeinheit 11 auf und führt die Operationen mit Daten aus, die in dem Hauptspeicher gespeichert sind. Nur AusIesespeichermikroprogramme steuern die Operationen des Feldprozessors 10. Der Feldprozessor 10 wird aktiviert durch die gewöhnlichen zentralen Verarbeitungseinheitsbefehle für Eingangs-/ Ausgangseinheiten: SIO (Start Eingang/Ausgang), TIO (Test Eingang/Ausgang), HIO (Halt Eingang/Ausgang) und TCH (Testkanal). Zusätzlich verwendet der Feldprozessor 10 ein Kanaladressenwort (CAW), Kanal befehlswörter (CCW) und Kanal Statuswörter (CSW), die noch genauer definiert werden. Ist die Operation des Feldprozessors 10 durch einen Start Eingang/Ausgangs-Befehl in Gang gesetzt und ist die zentrale Verarbeitungseinheit 11 ausgelöst, dann holt der Feldprozessor 10 Steuer- und Eingangsdaten vom Hauptspeicher 12 herbei und führt die Operationen, die durch die Kanalbefehlswörter initiert sind, aus und gibt die Ergebnisse in den Hauptspeicher ein ohne weiteren Befehl vom zentralen Verarbeitungseinheitsprogramm. Die zentrale Verarbeitungseinheit 11 ist frei in deport Setzung der Programmausführung mit der einzigen Verzögerung durch die Teilung der Speicherperiode mit dem Feldprozessor Nach der Vervollständigung seiner Operation liefert der Feldprozessor 10 eine Unterbrechungsanfrage an die zentrale Verarbeitungseinheit 11 und speichert ein Kanalstatuswort, wenn die^foiterbrechung akzeptiert ist.

109Ö8A/1 190

ID 2872 - 20 -

Wird noch, einmal zusammengefaßt, so führt der FeIdprozessor 10 Adressenanzeige-und Zähloperationen aus, sendet Abhol- und Speie he ranfragen für die Eingangs-/und Ergebnisdaten aus und führt unter Verwendung seiner eigenen arithmetischen Einheit die bezeichneten Rechnungen aus. Der Feldprozessor 10 besitzt zwei Gruppen von Pufferspeichern, in denen Eingangsdaten und Zwischenergebnisse erhalten bleiben. Diese Pufferspeicher dienen zur Reduzierung der Inanspruchnahme der arithmetischen Einheit auf den Hauptspeicher bei Ausführung der iterativen Operationen. Der Feldprozessor 10 ist bezüglich seiner Wirksamkeit in zwei Bereiche unterteilt: Der in Grenzflächen- oder Abschnitt- und Größenherbeiholbereich (IOF) und der arithmetische Bereich. Die Bereiche werden gesteuert durch zwei unabhängige, aber synchronisierte ITur-Ausle se speiche r-Mikro-Programme. Grundsätzlich führt der arithmetische Bereich eine Multiplikations-Additionsfunktion TJ+χίγ aus, wobei U den Multiplikanten bezeichnet, X den Multiplikator und ΐ die Vermehrung (augend). Die Übertragung von Daten zwischen Hauptspeicher 12 und den Pufferspeichern wird gesteuert durch den Abschnittsund Grö fienherbeiholabschnitt, der einen monolothisehen Speicher für Feldadressen, Indexwerte und Zählwerte besitzt mit zwei arithmetischen Einheiten für Adressenanzeige und Zählstandverminderung. Diese Operationen können parallel zu den Daten operationen ausgeführt werden.

Die Gesamtgeschwindigkeit, mit der der Feldprozessor 10 eine gegebene Operation ausführen kann, hängt von der Basisgeschwindigkeit des arithmetischen Bereiches und der Geschwindigkeit, mit der Daten zu

ID 2872 - 21 -

und von dem Hauptspeicher zum System übertragen werde können, ab. Grundsätzlich werden hohe Operationsgeschwindigkeiten erzielt, weil der Feldprozessor das Indizieren, das Zählen und den Hauptspeicherzugriff für eine spezielle Operation parallel zu der arithmetischen Operation der Daten ausführt. Die Organisation der arithmetisiien Einheit macht Gebrauch von der Fließverarbeitunginangriffnahme (assembly-line processing approach), bei der es möglich ist, verschiedene Datengruppen zur gleichen Zeit in verschiedenen Arbeitsstufen zu haben.

Der Abschnitts- und Größenherbeiholbereich ist unterteilt in die Prozessorabschnittseinheit und die Größensteuereinheit. Dieser Bereich nimmt Befehle von der zentralen Verarbeitungseinheit auf, speichert Steuerinformation., plant Übertragungen von Eingangsund Ausgangsdatenelementen zwischen Hauptspeicher und dem arithmetischen Bereich und führt die Funktionen der Formatumwandlung und Vorzeichensteuerung aus. Der Abschnitts- und Größenherbeiholbereich weist also Einrichtungen auf für:

1. das Aufnehmen und behandeln von Start-Eingangs-/ Ausgangs-, Test-Eingangs-/Ausgangs-, Halt-Eingangs-Ausgangs- und Testkanal-Befehlen von der zentralen Verarbeitungseinheit;

2. das Herbeiholen von Steuerinformation von festen

und variablen Adressen im Hauptspeicher und Speichern der Steuerinformation intern zur Verwendung während der Ausführung eines Befehles;

3· das Herbeiholen von Datenelementen vom Hauptspeicher und Speichern sich ergebender Elemente, wie es spezifiziert ist durch die die Operation betreffende

109064/1100

Steuerinformation, von Anfangsadressen, Zählstand, und Indexwerten;

4· Ausführung von Signalsteuerung auf Eingangsdatenelemente, wie sie durch die Steuerinformation spezifiziert sind?

5. Umwandlung der Eingangsdatenelemente von Festpunktformaten zum Flußpunktformat vährend der Übertragung derselben zu dem arithmetischen Abschnitt zur Pufferung oder Rechnung;

6. Unterbrechung der zentralen Verarbeitungseinheit und Speichern eines Kanalstatuswortes bei Vervollständigung des Befehles und Speicherung von logischer Ausgangsinformation (logout information) nach dem Anzeigen einer Funktionsstörung mit dem Feldprozessor.

Die Haupteinheiten und die Gesamtdatenwege für den Abschnitts- und Größenherbeiholbereich sind in Fig. 2 gezeigt. Das A-Register 18 nimmt sowohl Steuerinformation und Daten von Größen von Speichern als auch die sicii ergebenden Daten von Größen vom arithmetischen Abschnitt auf. Ist der Feldprozessor durch eine Start-Eingangs-/ Ausgangsoperation aktiviert, dann wird die Steuerinformation vom Speicher zu dem A-Register 18 übertragen und auf die passenden Steuer- und Formatregister verteilt. Auf die Ausführung eines Steuerbefehles werden Hauptspeicheradressen übertragen über die Speicheradressenhauptleitung (SAB) über den Speicheradressenhauptleitungsabschnitt 19. Y/enn eine Speicheranfrage gewertet wird, dann laufen die Daten vom Hauptspeicher über den Speicheradressenhauptwegabsehnitt 20 in das A-Register 18. Das A-Register kann die Daten entweder zeitweise speichern oder direkt zu dem B-Register 21 übertragen. Das A-Register dient auch als Zwischenspeicher und Akkumulator für die sich ergebenden Daten der Größen,

109884/1190

ID 2872 -23- 2137999

die vom Ergebnisregister 22 übertragen werden. Wenn der Index zwischen Ergebniselementadressefverlaubt, ist die Zahl der für die Datenübertragung benötigten Speicherzugriffe durch Zusammenfassen zweier aufeinanderfolgender Wörter zum Bilden eines Doppelwortes minimalisiert. Die gesammelten Ergebnisdaten iai dem A-Register 18 werden über das B-Megister 21 durch den Spe iche reingangshauptleitungsabsclanitt zum Hauptspeicher übertragen.

Das B-Register 21 ist die Einheit, durch die Eingangsgrößendaten zur arithmetischen Einheit bewegt werden und durch die die Ergebnisgrößendaten zum Speieber bewegt werden. Die Eingangsgrößendatenelemente το» B-Register werden durch die Formatumwandluiigs- und Signalsteuer-Logik 24 unter Steuerung des Abschnitts— und Größenherbeiholbereichs-Mikroprograaeaes gesteuert und werden verteilt auf das XY-Begister 25 und das U-Register 26. Die sich ergebenden Größendaten/uöXer Steuerung des Abschnitts- und Größenherbeiholbere iens— Mikroprogrammes akzeptiert und zum Speichereingangshauptleitungsabschnitt 23 zur Übertragung zum Hauptspeicher geführt.

Die Formatumwandlungs- und Signalsteuereinheit umfaßt die Formatumwandlungs- und Signalsteuerlogik 24 und die Formatumwandlungslogik 27, welche das Festpunktausgangssignal liefert. Diese Einheit führt alle Formatuawandluim?n und Signaländernagen aus, die durch die Steuerinformation in den Formatregistern bezeichnet sind. Diese Einheit wandelt Fes tpunkt eingang sdatene lernen te in Flußpunkte für die Yerarbeitui^g um und in bestimmten Operationen wandelt sie Tom Flußpunktformat in das Fes tpunkt format um, während -rom

109884/1190

ID 2872 - 24 »

2137999

Ergebnisregister 22 zum Α-Register 18 übertragen wird.

Dae XY-Register 25 empfängt Eingangsdatenelemente über die Formatumwandlungs- und Signalsteuerlogik vom B-Register unter Steuerung von dem Abschnittsund Größenherbeiholbereich-Mikroprogramm. Diese Datenelemente werden dann in den X- oder Y-Puffer des arithmetischen Bereiches unter Steuerung des arithmetischen Bereichs-Mikroprogrammes eingegeben.

Das U-Register 26 empfängt Eingangsdatenelemente über die Formatumwandlungs/und Signalsteuerlogik von dem B-Register 21 unter Steuerung durch das Abschnitts- und Größenherbeiholbereichs-Mikroprogramm. Das Ausgangssignal des XJ-Registers wird in den Rechnungen der arithmetischen Einheit unter Steuerung des arithmetischen Bereiche-Mikroprogrammes verwendet.

Das Ergebnisregister 22 empfängt die resultierenden Größendatenelemente unter Steuerung des arithmetischen Bereichs-Mikroprogrammes und sendet diese Daten weiter zum A-Register 18 unter Steuerung des Abschnittsund Größenherbeiholbereichs-Mikroprogrammes. Während der Datenübertragung vom Ergebnis- zum A-Register wird die Datenformatsumwandlung durch die Formatumwandlungslogik 27 in besonderen Operationen, die ein Festpunktausgangssignal ermöglichen, ausgeführt. Das Ergebnisregister nimmt auch teil an dem Hochwertvergleich, der durch die Hochwertvergleichslogik 28 durchgeführt wird, und an der Übertragung der Bits in das Hochwertregister 29·

103064/1190

ID 2872 -25- ^ I 3 2 9 9

Die Speicheradressen, und Indexsteuerungen 30 weisen Pufferspeicher für die mit dem Eingangssignal und Ergebnisgrößen und den Indexwerten, die die Byte-Zahl zwischen aufeinanderfolgenden Größenelementen definieren, verbundenen Hauptspeicheradressen auf. In dieser Einheit ist auch ein Adressenaddierer enthalten. Unter Steuerung des Abschnitts- und Größenherbeiholbereichs-Mikropr*ogrammes werden die Adressen zur Adressierung des Hauptspeichers über die Speicheradressenhauptleitung 19 verwendet und werden auf den neuesten Stand gebracht durch den Adressenaddierer durch Addition (oder Subtraktion) der Indexwerte. Die Indexwerte werden auch von dem Abschnitt - und Größenherbeiholbereich-Mikroprogramm verwendet zur Bestimmung der Zahl und Stelle der Elemente, die herbeigeholt oder in jedem Speicherzugriff gespeichert sind.

Die Zähl - und Dekrementsteuerung 31 enthält die Kanalbefehlswortbytezähl- und Größensteuerwort-Zählfeider. Der Kanalbefehlswortbytezählstand drückt die Zahl von Größensteuerwörtern aus, die zur Ausführung einer Feldoperation nötig ist, oder die Zahl von Bytes, die in einer Lese- oder Ausleseoperation gespeichert werden sollen. Die Größensteuerwort-Zählfeider bestimmen die Zahl von Elementen, die während jeder speziellen Operation verwendet werden sollen. Die Byte- und Elementzählstände werden herabgeschaltet durch einen Addierer, bis alle Daten übertragen und entsprechend der auszuführenden Operation verwendet worden sind.

109884/ 1 1 90

Die Formatregister 32 enthalten die Information, die die Art der Behandlung des Eingangssignales bestimmt, und die sich ergebenden Größendaten müssen vor dem Eingang in den arithmetischen Abschnitt oder die Übertragung zum Hauptspeicher gegeben sein. Diese Information wird verwendet zur Maschinensteuerung der Eormatumkehr- und Signalsteuerlogik 24 während der Übertragung der Daten vom B-Register 21 zu den XY- oder U-Registern 25 bzw. 26.

Das Hochwertregister 29 wird verwendet zum Halten des Signales, der Sechs-Ziffer (hex digit) hoher Ordnung des Teiles und der Charakteristik der von dem Ergebnisregister 22 zum A-Register 18 durch eine Feldoperation oder eine Pufferausleseoperation übertragenen Charakteristik des höchsten absoluten Flußpunktwertes. Jeder Wert in dem Ergebnisregister wird verglichen mit dem Hochwertregisterwert (Bits 1 bis 11 von jedem Register); wird ein höherer oder gleicher Wert gefunden, dann werden Bits 0 bis von dem Ergebnisregister in dem Hochwertregister gespeichert. Alle Ergebniselemente liegen Flußpunktformat vor, wenn sie im Ergebnisregister erscheinen. Deshalb enthält das Hochwertregister immer Bits bis 11 von einem Flußpunktwert, obwohl die zu dem Hauptspeicher übertragenen Elemente Festpunkt format hatten.

Der arithmetische Abschnitt kann eine Flußpunktmultiplikation und Additionsarithmetik vornehmen.

1 09884/ i 1 90

Haben die Eingangsdaten zum Feldprozessor Festpunktformat, dann werden sie in Flußρunktformat umgewandelt, ehe sie in den arithmetischen Abschnitt eingelesen werden. Die Nur-Auslesespeichersteuerung und zwei 32-Wort-Pufferspeicher erlauben die Ausführung verschiedener Operationsfolgen. Mit den sowohl als Akkumulatoren als auch als Operationsspeiche rf elder wirkenden Puffern können viele komplexe Flußpunktalgorithmen ausgeführt werden. Der arithmetische Abschnitt weist Einrichtungen auf für:

1. die temporäre Speicherung für maximal 32 Größenelemente in dem X-Pufferspeicher und 32 Größen oder Zwischenergebniselemente in dem Y-Pufferspeicher;

2. Speicherung bis zu zwei Elementen einer dritten (u) Größe,eine in Verwendung und eine für die nächstfolgende Operation;

3. Ausführung der Operation Z - (X*U)±Y in Kurzformat- (32-Bit) Flußpunkt.

Die Haupteinheiten und die Gesamtdatenwege für den arithmetischen Abschnitt sind in Fig. 3 gezeigt. Das arithmetische Bereich-Nur-AusIesespeicher-Mikroprogramm steuert die Bewegung der Daten zwjsihen XY-, U- und Ergebnisregistern 25, 26 bzw. 22, dem X-Pufferspeicher 34 und dem Y-Pufferspeicher 35, dem Ul-Register 36 und den drei Stufen der Multiplika tions-Additionseinheit. Alle Operationen werden verwirklicht durch FolgeVariationen dieser Datenbewegungen.

Alle arithmetischen Rechnungen werden ausgeführt in der Drei-Stufen-Multiplikations-Additionseinheit

109884/1190

Steht kein X- oder U-Element zur Verfügung für eine bestimmte Operation oder einen Teil einer Operation, dann wird ihr Eingangssignal zufriedengestellt durch Einführung einer 1 durch das Mikroprogramm. Steht kein Y-Element zur Verfugung, dann wird das Eingangssignal erfüllt durch Einführung einer wirklichen 0 durch das Mikroprogramm. Die in der ersten Stufe 58 erfolgte Multiplikation wird durch Addition in der zweiten Stufe 39 und nach Normierung in der dritten Stufe 40 gefolgt. Multiplikation wird ausgeführt durch Charakteristikaddition und Bruchteil-

) multiplikation, und das Vorzeichen des Produktes

wird bestimmt durch Standard-AlgebraregeIn. In dem Bruchteilmultiplikationsprozeß wird das TJ-Eingangs— signal effektiv multipliziert mit - 1, 2, 4, 6 und Diese Werte stehen dem Ut-Re gis te r 36 zum aufeinanderfolgenden Gebrauch in der Multiplikation mit dem X-Registerwert zur Verfügung. Der X-Eingang 41 wird dekodiert als. ein Satz von neun sich überlappenden vier Bit-Gruppen. Jede Gruppendekodierung tastet einen der vier TJ-Faktoren in die richtige Bit-Position eines 9-Eingangs-Paralleladdierers ein, um (l) eine weitere Multiplikation um eine Größe von zwei (LinksSchiebung) und durch die Ziffer/des X-

" Eingangs zu machen und die Addition der Teilprodukt-

form des Vollprodukts in der Form von 48 Summenbits und 48 Trägerbits zu machen. Dieses Produkt wird nach sieben Ziffern abgebrochen, ehe es zu dem Y-Wert addiert wird. Weder eine Nachnormierung der Eingangsdatenelemente, noch eine Nachnormierung des Zwischenproduktes findet statt. Die X- und U-Bruchteile haben sechs signifikante Hexa-Dezimalziffern, und das

0 9084/1190

Zwischenprodukt weist zwölf signifikante Ziffern auf. Mit normierten Eingangssignaleη kann die Ziffer hoher Ordnung dieses Produktes 0 sein. Die 7-Ziffern hoher Ordnung des Produktes werden das Eingangssignal für die zweite Stufe.

Der arithmetische Abschnitt weist zwei Ch/arakteristikaddierer auf. Der erste arbeitet parallel mit der Multiplikationsoperation und der zweite parallel mit der Nachnormierungsoperation. Der erste Addierer addiert den Prozentwert der !!-Charakteristik zu der X-Charakteristik und subtrahiert die Y-Charakteristik zur BestifflJiiung des Ausmaßes der zur Abgleichung des Produktes und Y-Bruchteile zur Addition benötigten Verschiebung. Der mit dem kleineren Charakteristikwert verbundene Bruchteil wird nach rechts um maximal sechs Ziffern verschoben zur Ausführung der Abgleichung. Ist die 6-Ziffer-Yerschiebung nicht hinreichend zur Erzeugung einer richtigen Einstellung der Bruchteile, dann ist einer der Faktoren (Produkt oder Y-Wert) klein in dem Endergebnis und wird in seiner Wirkung während derAdditionsoperation gleich 0 gesetzt. Die Summen- und -Trägerbits des abgeglichenen Produktbruchteils und die Bits des Y-Bruchteils werden addiert in einer 7-Ziffern-3-Eingangsaddierstufe zur Bildung der Zwischensumme, das dann in die Rückerganzungs- und Nachnormierungsstufe 40 eingegeben wird. R_esultiert aus der Addition eine Komplementärzahl, dann wird die Summe rückergänzt zu einer wahren Zahl vor der Nachnormierung.

Der zweite Charakteristikaddierer erzeugt unter Steuerung der Nachnormierungsoperation den richtigen Charakteristikwert für die Endsumme. Wenn während der Bruchteiladdition

109Ö84/1190

ID 2872 - 30 -

ein Übertrag einer Ziffer hoher Ordnung geschieht, wird der sich ergebende Bruchteil um eine Ziffer nach rechts verschoben und die Charakteristik um 1 weitergeschaltet. Sind in dem sich ergebenden Bruchteil Führungs-0-Ziffern vorhanden, dann wird er nach links verschoben, und die Charakteristik wird um die Zahl der Ziffern heruntergeschaltet. Ist eine Verschiebung um sechs Ziffern nicht ausreichend zur Erzeugung eines normierten Ergebnisses oder auch bei Herunterschalten der Charakteristik unter 0, dann werden der Bruchteil, das Signal und die Charakteristik 0 gesetzt. Diese Zahlw M als

P eine Flußpunkt-wahre-Null bezeichnet. In einem

solchen Ergebnis ist keine Exponentenunterströmungsbedingung indiziert, und der Flußpunkt-wahre-Null-Wert kann an den folgenden Operationen teilhaben. Sind die Charakteristiken des Ergebnisses größer als 127- (Exponent größer +63), dann wird das Exponentenüberlauf bit in den Y-Pufferspeicher für dieses Element eingegeben. Wird das Y-Element zum Hauptspeicher übertragen und ist das Überlaufbit in Betrieb, dann .werden alle Bruchteil- und Charakteristikbits für das Element auf 1 eingestellt. Der Flußpunktüberlaufsinn und die Einheitenkontrollstatusbits werden für diese Operation eingestellt.

Das U1-Register 36 wird durch Steuerung des Mikroprogrammes des arithmetischen Abschnittes von dem U-Register 26 geladen. Durch eine "mal 6"-Multiplizierstufe 42 und SchieberschaltlSÄgydas Signal 6U vom Eingang 4-3 und die Signale U, 2ü, 4TJ und 8TJ der Eingänge zu der Multiplikationsstufe 38 geliefert.

109884/1190

ID 2872 - 31 -

Die X- und Y- Pufferspeicher 34 bzw. 35 sind Hochgeschwindigkeitsspeicher, die eine temporäre Speicherung für Elemente (Größen) liefern, die an Feldoperationen teilhaben. Insgesamt können 32 Elemente in jedem Pufferspeicher enthalten sein. Der X-Pufferspeicher wird zum Speichern von Eingangselementen und <fcrY-Puff erspei eher zum Speichern von Zwischen- und Endergebnissen verwendet. Zusätzlich zum Behalten von 32 ganzen Wortelementen besitzt der Y—Pufferspeicher sechs zusätzliche, jedem Element zugeordnete Bit-Positionen. Diese zusätzlichen Bit-Positionen werden zur Speicherung einer siebenten Kontrollziffer auf Zwischenergebnisse, einem Flußpunkt-Überlaufmarkierungs-Bit und einem hinzugefügten Paritäts-Bit verwendet.

Der X-Puf ferspeicher 34- hat zwei Funktionen. Erstens liefert er eine Speicherung für 32 Eingangselemente, die teilhaben an den vielfachen arithmetischen Operationen an der Formulierung von Mehrfachergebnissen (multiple results). Ein einzelnes X-Element kann verwendet werden zur Bildung von ebensoviel wie 32 Zwischen- oder Endergebnis sen,ohne daß es vom Speicher wieder herbeigeholt wird. Zweitens liefert er die Speicherung für 32 X-Elemente, die Element für Element mit U-EingangsSignalen zu verarbeiten sind. Nachdem ein U-Element in das Ul-Register 36 eingeführt ist, können arithmetische Operationen durch Herbeiholen zusätzlicher U-Elemente überlappt werden, bis die X-Elemente ausgeschöpft sind.

109884/1190

ID 2872 - 32 -

2132899

Der Y-Pufferspeicher 35 erfüllt drei Punktionen. Erstens bildet er einen Eingangsspeicher für vorhergehende Ergebnisse, die zu den Ergebnissen der laufenden Operation (Stapelung) addiert werden. Zweitens bildet er einen Speicher für 32 Ergebnis elemente, wodurch die Notwendigkeit der Unterbrechung des Eingangsstromes der Datenelemente zur Speicherung von individuellen Ergebniselementen ausgeschaltet wird. Da der Eingangsstrom nicht unterbrochen wird, können Eingangselemente mit einer maximalen Geschwindigkeit herbeigeholt werden. Schließlich dient er als Akkumulator für !Teil- oder Zwischenergebnisse ψ beider Ausführung der Algorhythmen, die mehrfache

arithmetische Operationen zum Erzielen eines Endergebnissen benötigen. 32 solche Ergebnisse können gleichzeitig gesammelt werden. Die Ergebnisse können entweder dem Y-Eingang 45 oder den TJ-Eingängen 4-3 oder 44 der -arithmetischen Einheit 37 zugeführt werden. Werden die Ergebnisse in den U-Eingang eingegeben, dann werden die Bruchteile der Elemente von dem Y-Pufferspeicher auf sechs Ziffern abgerundet, und das Überlaufbit setefc sich durch die arithmetische Einheit fort und erscheint in dem berechneten Ergebnis.

Die X- und Y-Puffer erlauben in Kombination die Verwendung von Hochgeschwindigkeiten der dreistufigen arithmetischen Einheit zur Ausführung verschiedener Operationen wie der Drehmultiplikation (convolving multiplication). Die drei Abschnitte 38, 39 und 40 der arithmetischen Einheit 37 unterscheiden sich voneinander und sind getrennte Stufen. Diese bilden zusammen mit den X-und Y Pufferspeichern durch

1Ö9Ö84/1190

X- und Y-Pufferspeicher-Eingangssteuerungen 46 bzw. 47 eine vierstufige Folge. Solange die Anfrage für U-Eingangssignale zu der Multiplikationsstufe 38 befriedigt werden kann, können verschiedene Sätze von X- und Y-Elementen in jeder der drei Stufen im Verarbeitungsprozeß sein. Gleichzeitig werden neue X- und Y-Elemente der ersten Stufe 38 zugeführt, und das gerade verarbeitete Element in der dritten Stufe 40 wird in dem Y-Pufferspeicher 35 gespeichert.

Die vier Eingangs-/Ausgangsbefehle START-EINGANG/AUSGANG, TEST-EINGANG/AUSGANG, HALT-EINGANG/AUS GAN G und TESTKANAL· liefern ein Mittel , durch das Programm der zentralen Verarbeitungseinheit den Zustand des Feldprozessors 10 ändern oder den Feldprozessor 10 abfragen kann. Jeder dieser Befehle enthält eine Kanal- und Vorrichtungsadresse, die zum Auswählen des FeldProzessors verwendet wird. Die durch einen Eingangs-/Ausgangsbefehl zugeführte Adresse besitzt zwei Komponenten: die Kanaladresse (Bits 16 bis 23) und die Vorrichtungsadresse (Bits 24 bis 31). Am Ende des Eingangs-/ Ausgangsbefehles bewirkt der Eingangs-/Ausgangskanal, daß der zentrale Verarbeit^ungseinheits-Zustandskode einen von vier Werten annimmt. Dieses Einstellen ist für jeden Eingangs-/Ausgangsbefehl in Fig. 4 beschrieben.

Für die zentrale Verarbeitungseinheit 11 ist der Feldprozessor 10 ein Kanal mit einer Integralvorrichtung. Die Ausführung der Operationen in dem Feldprozessor wird in Gang gesetzt durch einen Start-Eingangs-/Ausgangsbefehl und macht Gebrauch von dem Kanaladressenwort und dem Kanalbefehlswort zur Zuführung

1 09884/1190

der notwendigen Steuerinformation zu dem Feldprozessor. Die gewünschte Operation wird durch den Kanalbefehlskod-a ausgewählt. Operationen in dem Feldprozessor werden durch einen zentralen Verarbeitungseinheitbefehl in G-ang gesetzt. Vor dem Ausgeben dieses Befehles ist es notwendig, das Kanaladressenwort mit dem richtigen Stufenabschirmschlüssel und einer richtungsweisenden Kanalbefehlswortadresse in Gang zu setzen. Wenn der Feldprozessor den START-EINGANGS-/ AUSGANGS-, TEST-EINGANGS-AUSGANGS-, HALT-EI NGANG S-/ AUSGANGS- oder TESTKANAL-BEFEHL· annehmen kann, dann wird das Kanaladressenwort von dem Hauptspeicher her- W beigeholt.

Das Kanaladressenwort hat das folgende Format:

j Schlüssel 0000 Befehlsadresse

0 34 78 29

Die Bits 0 bis 3 bilden den Schutzschlüssel für alle Speicherreferenzen, die mit der Feldprozessoroperation, die durch die zentrale Verarbeitungseinheit in Gang gesetzt wird, zusammenhängen. Dieser Schlüssel trifft zusammen mit einem Schlüssel im Speicher, wenn auf den Hauptspeicher Bezug genommen wird. Die Bits 8 bis 31 bezeichnen die Stelle eines Kanalbefehlswortes in dem Hauptspeicher. Das Kanalbefehlswort kann ^rsten aus einer Reihe von Befehlen sein.

Das Kanalbefehlswort beschreibt einen auszuführenden Befehl, den mit dem Befehl zusammenhängenden Speicherbereich

10 9 8 8 4/1190

und den Vorgang, der auf die Vervollständigung des Befehles hin vorgenommen wird. Kanalbefehlswörter können in einer Doppelwortgrenze überall im Speicher aufgefunden werden. Das erste Kanalbefehlswort
wird herbeigeholt während der Ausführung des START-EINGANGS-/AUSGANGS-BEFEHLES. Beschreibt das erste Kanalbefehlswort eine Befehlsmessung (command
chaining), werden zusätzliche Kanalbefehlswörter
herbeigeholt, wenn die Operation einen Punkt erreicht hat, an dem ein anderes Kanalbefehlswort nötig ist. Das Format des Kanalbefehlswortes für den Feldprozessor wird aus einer Reihe von Feldern in der gezeigten Weise gebildet. Alle Kanalbefehlswörter müssen auf einer Doppelwortgrenze gespeichert werden.

Befehlskode Datenadresse

0 78

Marken I 000 /' / / I Zählstand

32 36 37 39 40 47 48

Die Bits 0 bis 7 spezifizieren einen Befehlskode, der eine auszuführende Operation angibt. Die Bits 8 bis 31 beschreiben eine Datenadresse des Hauptspeichers. Das ist die erste Stelle, die bei Ausführung der durch den Befehlskode definierten Operation in Angriff genommen werden muß. Das Datenadreseenfeld

109884/1190

richtet entweder auf ein anderes Kanalbefehlswort (Übertragung-ein-Kanalbefehl), eine Reihe von Größenbefehlswörtern (Feldsteuerbefehl) oder ein Datenfeld (Befehl lesen oder Steuerbefehl auslesen). Bits 32 bis 39 stellen das Markenfeld dar. Dieses schließt ein Befehlskettenmarkenbit und ein programm-, gesteuertes Unterbrechungsmarkenbit ein. Wenn der Feldprozessor einen Kanalbefehlswort-Befehl ausführt, kann er ein neues Kanalbefehlswort ohne einen neuen Start—^inganga-/Ausgangsbefehl herbeiholen. Diese Folge wird als Befehlsmessung (mit der Kette) bezeichnet und durch das Befehlskettenmarkenbit in Gang

" gesetzt.-Die Befehlsmessung findet normalerweise

nur zwischen Kanalbefehlswörtern statt, die in aufeinanderfolgenden Doppelwortstellen im Speicher angeordnet sind und laufen in aufsteigender Reihenfolge ab; Kanalbefehlswörter in verschiedenen Speicherbereichen können jedoch aneinandergekoppelt werden durch Verwendung eines Übertrage-in-Kanal-Befehles. Das Kanalstatuswort wird normalerweise nur auf Vervollständigung des letzten einer Reihe von Meßbefehlen gespeichert. Eine Programmunterbrechung und Speicherung eines Kanalstatuswortes in einem Befehl oder einer Kette von Befehlen kann bewirkt werden durch Einstellen

| des programmgesteuerten Unterbrechungs-Markenbits in

einem Kanalbefehlswort. Die programmgesteuerte Unterbrechung s -Marke bewirkt, daß der Feldprozessor eine Unterbrechungsanfrage an die zentrale Vererbeitungseinheit sendet. Die Bits 48 bis 63 bilden das Zählfeld. Das Byte-Zählfeld beschreibt die Zahl der Bytes von " Daten, die zu speichern sind oder unter Steuerung des Kanalbefehlswortes dem Zugriff unterliegen. Für Feldsteuerbefehle muß der Zählstand 16 sein für Operationen, die zwei Größensteuerwörter benötigen,

109884/1190

und 24 für Operationen, die drei Größensteuerwörter benötigen.

Das Kanalstatuswort gibt den zentralen Verarbeitungs~ einheits-Programm-Zugriff zu dem Status einer Eingangs-ZAusgangsvorrichtung oder zu den Bedingungen, unter denen ein Eingangs-/Ausgangs-Vorgang beendet wurde. Das Kanalstatuswort wird zusammengebaut oder modifiziert in dem Vorgang der Eingangs-/Ausgangsunterbrechungen oder als Ergebnis der START-EINGAFG-/ AUSGANG-, TEST-EINGANG-/AUSGANG- oder HALT-EINGANG-/ AUSGANG-Befehle. Das Kanalstatuswort wird gespeichert als Doppelwort und hat das folgende Format:

Speicherschutzschlüssel

0000

Befehls

adresse 0 34 78

Statue-Bytes

Zählung

32 47 48 63

Die Bit-Positionen 0 bis 3 enthalten den Speicherschutzschlüssel, der von dem Kanaladressenwort genommen ist. Die Bit-Pos&ionen 4 bis 7 werden immer als Nullen. Die Bit-Positionen 8 bis 31 bilden eine Adresse, die um 8 höher ist als die Adresse

109884/1190

des letzten herausgegebenen Kanalbefehlswortes. Die Bit-Positionen 32 bis 47 identifizieren die Zustände in dem Feldprozessor, die die Speicherung des Kanalstatuswortes hervorgerufen haben. Das übrigbleibende Byte-Zählfeld in den Bit-Positionen 48 bis 63 bezeichnet zusammen mit der Originalzählung, die in dem letzten verwendeten Kanalbefehlswort beschrieben ist, die Zahl der zu oder von dem durch das Kanalbefehlewort bezeichneten Bereich zu übertragenden Bytes. Wenn eine Lesebefehl- oder Auslesesteuerbefehloperation beendet ist, dann ist die Differenz zwischen den ursprünglichen Zählstand in dem Kanalbefehlswort und dem verbleibenden Zählstand in dem Kanalstatuswort gleich der Zahl der zu dem Hauptspeicher zu übertragenden Bytes. Nach einer Feldsteuerbefehloperation ist die Differenz gleich der Zahl der zu dem Feldprozessor übertragenen Bytes von den Größensteuerwörtern.

Zur Ausführung von Feldoperationen benötigt der Feldprozessor die Stelle, Größe und Formate der verschiedenen Felder betreffende Steuerinformation. Diese Information wird durch Größensteuerwörter zugeführt. Die Größensteuerwörter werden definiert als Größensteuerwort Y, Größensteuerwort X und Größensteuerwort U. Größensteuerwort X und Größensteuerwort U definieren die Größen, während Größensteuerwort Y das Ausgangssignal- oder Ergebnisdatenfeld beschreibt. Einige Feldsteuerbefehle verwenden zwei dieser Größensteuerwörter, während andere alle drei verwenden. Die Größensteuerwörter werden abgeglichen

109884/1190

ID 2872

auf Doppelwortgrenzstellen, und alle Größensteuerwörter, die für eine spezielle Operation verwendet werden, müssen in aufeinanderfolgenden Doppelwortstellen liegen. Das Größensteuerwort hat das folgende Format:

Format Byte

Erste Elementadresse

78

Index (Bytes) 32

Zählung (Elemente)

47 48

63

Jedes Bit in dem Größensteuerwort-Format-Byte-Feld hat eine eindeutige Bedeutung. Die Bits 5 bis 7» die nicht verwendet werden, werden als Null beschrieben. Fig. 5 beschreibt das Vorhandensein der Größensteuerwort-Format-Bytes. Die Bit-Positionen 0 und 1 definieren das Format der Datenhauptspeicher. Ist Bit 0 eine Null, dann werden die Datenelemente in Vollwortflußpunktform zugegriffen,und Bit 1 des Format-Bytes wird ignoriert. Ist Bit 0 eine Eins, dann werden die Daten in Halbwort-Ganzzahl-Form zugegriffen; ist Bit 1 eine Null, dann sind die Daten in der bezeichneten wahren Form repräsentiert, und ist Bit 1 eine Eins, dann sind sie in zweier Komplementform (two's complement form) dargestellt. Die Format-Bit-Positionen 2 und 3 liefern eine Steuerung über das Signal (Vorzeichen) von jedem unter Steuerung des Größensteuerwortes (einschließlich

109884/1190

der für die Stapelung herbeigeholten Y-Daten) herbeigeholten Datenelemente. Sind die Bits/und 3 Null, dann wird das im Hauptspeicher gefundene Vorzeichen verwendet. Ist Bit 2 eine Eins, dann tfird das im Hauptspeicher gefundene Vorzeichen der Daten weggenommen und der absolute Wert für jedes Element gebildet. Ist weiter Bit 3 eine Eins, dann wird das sich ergebende Vorzeichen umgekehrt zur Bildung dee Segativen des Vorzeichens im Speicher (wenn Bit 2 eine Null ist) oder des Negativen des absoluten Wertes (wenn Bit 2 eine " Eins)ist). Die Format-Bit-Position 4 (gestapeltes

Bit) des Größensteuerwortes Y steuert normalerweise das Herbeiholen des Inhaltes des Y-Feldes für das Hinzufügen zu den Ergebnissen der Flußoperation. Ist Bit 4 eine Null, dann werden Bits 2 und 3 des Größensteuerwortes Y ignoriert. Bit 4 des Größensteuerwortes X und des Größensteuerwortes U werden ignoriert.

Die Bit-Positionen 8 bis 31 des Größensteuerwortes beschreiben die Adresse des ersten Elementes des Feldes. Diese Adresse muß eine geeignete Ab^gleichung * für den Typ der verwickelten Daten darstellen, d. h.

Halbwort- oder -Vollwortabgleichung. Die Bit-Positionen 32 bis 47 werden als eine Halbwort-bezeichne te Zweier-Komplement zahl behandelt, die die zu den Flußdatenadressen zu addierende Menge beschreiben zur Feststellung des nächsten Elementes im Speicher. Es ist entweder eine positive oder negative Indizierung möglich. Die !Bit-Positionen 48 bis 63 repräsentieren die Zahl der Datenelemente in dem Feld, die durch

109884/1190

eine 16-Bit-positive-binäre Zahl ausgedrückt sind.

. Ein Feld ist ein Satz von Daten, der im Hauptspeicher 12 zu speichern ist und auf den der Feldprozessor zu arbeiten hat. Das Wort "Feld" schließt ein, daß der Feldprozessor in einer ähnlichen Gruppe (section) auf viele Eingangsdatenelemente zur Erzeugung entweder eines einzelnen Ergebnisses oder eines Feldes von Ergebnissen in Abhängigkeit auf den auszuführenden Befehl operiert. Der Feldprozessor ist verbessert durch seine Kapazität zur Ausführung von Adressenindizierung und Elementenzählung parallel zu einer arithmetischen Operation bei Verarbeitung eines Feldes.

Drei Befehle werden bei der Ausführung der Algor i thmen der schnellen Fouriertransformation in den Feldprozessor 10 ausgeführt. Diese drei Befehle können verwendet werden zur Ausführung jedes der einzelnmöglichen Algor i thmen der schnellen Fourier-Transformation für N =■ 2 mit r als einer positiven ganzen Zahl oder zur Ausführung der Basis zwei- und/oder Basis vier-"Stufen", in denen der Wert N ein Faktor von 2^r ist. Für den Fall, daß N zusammengesetzt ist aus r Primfaktoren (die nicht notwendig gleich sein müssen), kann jede der N-Gleichungen, die durch Gleichung (ll) definiert ist, als eine Folge von r verschachtelten Summationen ausgedrückt werden. Jede Summation erfolgt über eine einem der Primfaktoren entsprechende Zahl von Termen. Wie bereits beschrieben wurde, erzielen die Algorhythmen der schnellen Fourier-Transformation ihre Wirksamkeit durch Auswerten der entsprechenden Summationen in den N-Gleichungen in Gruppen. Durch Auswertung der diskreten Fourier-Transformation in

9834/1190

ID 2872 - 42 - 2732999.

dieser Weise werden überzählige Indexoperationen, Speieherzugriffe und arithmetische Operationen ausge schalt et.

Wenn der eine für jede der N-GrIeichungen ausgewerteten Summationen entsprechende Primfaktor <? ist, dann führt der Algorhythmus der schnellen Fourier-Transformation für die Basis ? die Summation in

^ von den N-GIeichungen bei einer Zeit, die im weiteren als ? —Tuple bezeichnet wird, aus, bis diese Summation in allen der N-Gleichungen ausgewertet ) worden ist. Diese Auswertungsoperation solch einer

Summation für alle der N-Gleichungen wird im weiteren als "Stufe" des Algorhythmus der schnellen-Fourier-Transformation bezeichnet. Da r verschachtelte Summationen in jeder der N-Gleichungen vorliegen, gibt es r Stufen in der Auswertung der diskreten Fourier-Transformation bei dieser Methode. Jede der C₁ -Summationen in einem ⁴^ -Tuple besteht aus

^-Termen mit einem komplexen Eingangswert, der mit einer komplexen Exponenten multipliziert wird. Diese

^ -Summationen über ^ -Termen werden als die Kerngleichungen für die Basis ^ bezeichnet. Für den Fall, daß ^gleich 2, haben die Kerngleichungen

die Form
B

(23)

wobei Bi , und B¹.¹ , während der vorhergehenden Stufe (also der Stufe i-l) der diskreten Fourier-Transformation berechnete Zahlen sind, und W ist ein komplexer Exponent

109884/1190

gemäß der früher definierten Weise. Während der Ausführung einer Stufe in der diskreten Fourier-Transformation werden solche λ -Tuples, die unter Verwendung desselben komplexen Exponenten ausgewertet werden, als eine "Division" bildend bezeichnet.

Während der Ausführung des Algori thmus der schnellen Fourier-Transformation im Feldprozessor 10 muß ein Befehl in dem Feldprozessor für jede Stufe der diskreten Fourier-Transformation ausgeführt werden. Diese in dem Feldprozessor 10 mikroprogrammierten Befehle sind für Basen 2 und 4· In den Befehlsformaten für die Befehle der schnellen Fourier-Transformation "FF2", "FF4" und "FI4" muß das folgende beschrieben werden:

a) die Zahl der Divisionen in der Stufe,

b) die Zahl der Tuples in jeder Division und

c) drei Index-Inkremente:

1) Einheiten zwischen Punkten in einem Tuple,

2) Einheiten zwischen Tuple-Oberteil (tops of tuples) und

3) Einheiten zwischen Divisions-Oberteilen (tops of divisions).

Ein "Tuple" im Feldprozessor 10 besteht entweder aus einem Paar oder aus einem Quadruple. Bei passender Beschreibung dieser Größen kann entweder der Co±ey-Tukey- oder Sande-Tukey-Algor i thmus in entweder der Basis 2 oder der gemischten Basis "vier plus zwei"-Form für N ■ 2^r beschrieben werden oder die Basis zwei oder vier Stufen für einen Cooley-Tukey- oder Sande-Tukey-Algor ithmus für Werte von N, welche nur einen Faktor gleich 2^r haben, kann beschrieben werden,

1Ö9884/ 1 190

Der letztere Pall ist möglich, da η indirekt ■beschrieben wird durch die Relation N » (Basis,

^v )x(Zahl von ^ -Tuples/Division)x(Zahl der Divisionen ), und diese Werte werden nicht auf Werte gleich Potenzen von zwei beschränkt.

Der Vorteil der Ausführung der Befehle der schnellen Fourier-Transformation dieser stufenweisen Art gegenüber Einzelbefehl ist:

1) Sowohl die Cooley-Tukey- (geordnet zu vermischt) als auch die Sande-Tukey- (vermischt zu geordnet) Formen des Algori thmus der schnellen Fourier-Transformation können unter Verwendung desselben Befehlssatzes ausgeführt werden.

2) Bei Filteranwendungen oder statistischen Berechnungen, in denen das Drehungs- oder Faltungs-Theorem (convolution theorem) verwendet wird, müssen die Daten nicht unvermischt (oder vermischt) sein, um die inverse Transformation ausführen zu können, wie es notig.wäre, wenn nur eine dieser Formen zur Verfügung stünde.

3) Gleichzeitige Transformation von komplexen

r Multiplex-Datensätzen ist möglich durch "Kurzstoppen"

in dem Cooley-Tukey-Algor i thmus oder "Spätstarten" im Sande-Tukey-Algor i thmus. Diese Wahl ist extrem veränderbar bei Anwendungen, in denen Mehrfach-Datensätze in einem Multiplex-Feld gespeichert sind und in der Berechnung von mehrdimensionalen diskreten Fourier-Transformationen. Im vorhergehenden

109864/1-190

Fall mite sen die Daten nicht wieder entkoppelt werden.

4) Die Befehle "FF2", "FiM-" und "FI4" können mit einer geeigneten Tabelle von komplexen Exponenten zur Traisformation komplexer Felder verwendet werden, deren Länge N das Maximum N überschreitet, welches durch direkte Mittel bei Ausführung dieser Befehle zur Berechnung von Zwischenergebnissen über Teilungen des ganzen Feldes berechnet werden können.

5) Die Befehle "PF2", "FF4" und "FI4" können mit einer geeigneten Tabelle von komplexen Exponenten zur Berechnung der Basis 2-und/oder Basis 4-Stufen einer Vielfachbasistransformation verwendet werden, für die N nur einen Faktor besitzt, der eine Potenz von zwei ist, und N selbst nicht gleich der Potenz von zwei ist.

Vor der Definition der Befehlsformate sollten die oben bereits gegebenen Definitionen noch einmal betrachtet werden:

Ein ^. -Tupfe ist definiert als ein Satz ^. komplexer Ausgangswerte, die von entsprechenden €. komplexen Eingangswerten unter Verwendung der Kerngleichungen für die Basis feiner gegebenen Stufe berechnet werden sollen. In den Befehlen "FF2" und "FF4" (FI4") wird unter einem ^. -Tuple ein Paar oder ein Vierer verstanden.

Eine Division ist definiert als ein Satz aller

<l -Tuples einer gegebenen Stufe, die denselben Satz komplexer Exponenten in den Kerngleichungen

109884/1190

ID 2872

213?993

verwendet. Die Zahl der Divsionen in jeder Stufe ist gleich dem Produkt der Basen der vorhergehenden Stufen.

Die Formate für das Kanalbefehlswort und die Grö'ßensteuerwörter für den Befehl "FF2" sind djß folgenden:

Kanalbefehlswort

Γ ' ~ r

ι Befehlskode i

Adressen-Größensteuerwort

Markierungen

CT = 24 '

78

32

48

Größensteuerwort 1 - Format

Format-Byte

Adresse des Ergebnisfeides

7 8

Einheiten zwischen;

Punkten in einem '.

Paar !

31

Zahl von Paaren pro Division

48

63

Bits 0 und 1 des GrÖßensteuerwortes 1 werden kontrolliert zur Verifizierung dafür, daß sowohl das Eingangs- als auch das Ergebnisfeld in Flußpunktformat sind. Die Bits 2 und 3 führen die Vorzeichensteuerfunktion für (a) des Realteiles der komplexen Exponenten und (b) der Seal- und Imaginärteile des Eingangsdatenfeldes aus. Die Bits 4 bis 7 müssen Null sein.

109884/1190

ID 2872

Größensteuerwort 2 - Format

Format-Byte

Adresse des Feldes? der komplexen j Exponenten j

Einheiten zwischen Oberteilen (tops) der Paare

Zahl der Divisionen

7 8

32

47

Bits O und 1 des Größensteuerwortes 2 werden ausgetastet zur Verifizierung dafür, daß das Feld der komplexen Exponenten Flußpunktformat hat. Bit 2 und 3 führen die Vorzeichensteuerfunktion für den imaginären Teil der komplexen Exponenten aus. Bit 3 wird gleich 1 gesetzt für Vorwärts- und gleich 0 gesetzt für inverse diskrete Fourier-Transformationen. Die Bits 4 bis 7 müssen Null sein. Die Adresse des komplexen Exponenten wird automatisch um 8 Bytes weitergeschaltet in dem Feldprozessor zur Adressierung jeder folgenden komplexen "W"-Komponente..

Größensteuerwort 3 - Format

Format-Byte: Adressen-

j Eingangsfeld

—Ι

7 8

Einheiten zwischen Oberteilen (tops) der Divisionen

31 32

47

Zahl der Bytes pro Einheit

63

Bit 0 wird im Größensteuerwort 3 gleich Eins gesetzt, und die Bits 1 bis 7 sind alle Null. Die Zahl der Bytes

4/1190

ID 2872

pro Einheit sollte gleich Eins gesetzt werden.

Fig. 6 zeigt das vereinfachte Flußdiagramm für den Befehl "FF2". In der Figur wird die folgende Bezeichnungsweise verwendet: A( ) ist das Eingangsfeld komplexer Werte. Es wird zur Vereinfachung hier angenommen, daß dieses Feld angrenzend gespeichert ist und alle Indizes entweder die Real- oder Imaginärteile der komplexen Werte betreffen. Speziell ist (2n-l) der Realteil des komplexen Elementes η und A(2n) der Imaginärteil des komplexen Elementes n. W( ) ist das Feld der komplexen Exponenten, die wie oben angrenzend und in der für die Ausführung des Algorhythmus der schnellen Fourier-Transformation benötigten Ordnung gespeichert sind. B( ) ist das Ausgangsfeld der komplexen Werte und ist gleich dem A( ) von oben. Il ist der Index zwischen Punkten in einem Paar. 12 ist der Index zwischen den Oberteilen (tope) von Paaren. 13 ist der Index zwischen Oberteilen von Divisionen. Cl ist die-Zahl von Paaren pro Division. C2 ist die Zahl der Divisionen. SGN ist gleich 1, wenn eine inverse diskrete Fourier-Transformation zu berechnen ist, und gleich minus 1, wenn eine vorwärtsdiskrete Fourier-Transformation zu berechnen ist.

Die Formate des Kanalbefehlswortes und der Größensteuerwö'rter für den Befehl "FF4" sind die folgenden:

Kanalbefehlswort-Foraat Befehlskode

Adresse-Größensteuerwort 1

Markierungen

CT* = 24

7 8

31 32

47 48

1098Ö4/1 190

*Zählfeld

ID 2872

Größensteuerwort 1 - Format

Format-Byte

Adre ssen-Ergebnisfeld

Einheiten

zwischen
Punkten in
einem Vierer

Zahl der Vierer pro Division

i.

7 8

31 32

47 48

63

Die Bits 0 und 1 des Größensteuerwortes 1 werden ' ausgetastet zur Verifizierung dafür, daß die Eingangs- und Ergebnisfeider Flußpunktformat haben. Bits 2 und 3 führen die Vorzeichensteuerfunktion für (a) den Realteil der komplexen Exponenten und (b) die Real- und Iaaginärteile des Eingangsdatenfeldes aus. Bit wird gleich Null gesetzt für die Cooley-Tukey-Arithmetik und gleich Eins gesetzt für die Sande-Tukey-Arithmetik. Die Bits 5 bis 7 müssen Null sein.

Größensteuerwort 2 - Format

j Format-Byte

! Adresse des Feldes'; der komplexen _; Exponenten '

Einheiten zwischen! Oberteilen (tops) j der Vierer I

Zahl der Divisionen

7 8

31 32

47 48

Bits 0 und 1 des Größensteuerwortes 2 werden daraufhin kontrolliert, daß das Feld der komplexen Exponenten Flußpunktformat hat. Die Bits 2 und 3 führen die Vorzeichens teuerfunktion für den Imaginärteil des komplexen Exponenten aus. Bit 3 sollte gleich Eins gesetzt werden, weil der Befehl "FF4" nur eine Vorwärttj-diekreto Fourier-Transformation ausführt.

10 9884/1190

ID 2872

Die Bits 4 bis 7 müssen Null sein.Die Adresse des komplexen Exponenten ist automatisch um 16 Bytes weitergeschaltet in dem Feldprozessor zur Adressierung jeder folgenden komplexen "W"-Komponente.

Größensteuerwort 3 — Format

Format-Byte Adressen- Einheiten zwischen. Zahl der :

; Eingangsfeld ; Oberteilen (tops) ■ Bytes pro

j '< der Divisionen Einheit

7 8

31

48

63

Bit 0 und G-rößensteuerwort 3 sollten gleich 1 gesetzt werden. Bitρ 1 bis 7 sollten Null sein. Die Zahl der Bytes pro Einheit sollte gleich 1 gesetzt werden.

Die Formate des Kanalbefehlswortes und der Größensteuer■ Wörter für (fen Befehl "FI4" sind die folgenden:

Kanalbefehlswort

ίBefehlskode '■- Adresse-

ßrößeneteuerwort

Markierungen

GT - 24

7 8

32

48

63

Größensteuerwort 1 - Format

•Format-Byte Adressen-

lErgebnisfeld

Einheiten zwischen
Punkten eines Vierers

Zahl der < Vierer pro ; ■£ Division !

O 7 8 31

109884/1190

48

ID 2872

2132399

Die Bits O und 1 des Größensteuerwortes 1 werden kontrolliert zur Verifizierung dafür, daß Eingangsund Ergebnisfelder in Flußpunktformat vorliegen. Die Bits 2 und 3 führen die Signaleteuerfunktion für (a) des Realteiles der komplexen Exponenten und (b) der Real- und Imaginärteile des Eingangsdatenfeldes aus. Bit 4 wird Null gesetzt für die Cooley-Tukey-Arithmetik und Eins gesetzt für die Sande-Tukey-Arithmetik. Die Bits 5 bis 7 müssen Null sein.

Größensteuerwort 2 - Format

Format-Bytes

Adresse des Feldes der komplexen Exponenten

Einheiten zwischen Oberteilen (tops) der Vierer

Anzahl

der

Divisionen

7 8

31 32

47 48

Die Bits 0 und 1 des Größensteuerwortes 2 werden kontrolliert zur Verifizierung dafür, daß das Feld der komplexen Exponenten Flußpunktformat hat. Die Bits 2 und 3 führen die Vorzeichensteuerfunktion für den Imaginärteil des komplexen Exponenten aus. Bit 3 sollte Null gesetzt werden, weil der Befehl "FI4" nur eine inverse diskrete Fourier-Transformation ausführt. Die Bits 4 bis 7 sind Null. Die Adresse des komplexen Exponenten wird automatisch um 16 Bytes weitergeschaltet in dem Feldprozessor zur Adressierung jeder nachfolgenden komplexen "W"-Komponente.

Größensteuerwort 3 - Format

Format-Bytes

Adressen-Eingangsfeld

Einheiten zwischen' Oberteilen (tops) ; der Divisionen

Zahl der Bytes pro Einheit

7 8

31 32

109884/1190

47 48

63

Si.

Bit O des Größensteuerwortes 3 sollte Eins gesetzt werden, während die Bits 1 bis 7 Null sein sollten. Die Zahl der Bytes pro Einheit sollte gleich Eins gesetzt werden.

Die Fig. 7A und 7B zeigen das vereinfachte Flußdiagramm für die "FF4"- und "FI4"-Befehle. In diesen Figuren wird die folgende Bezeichnungsweise verwendet: A( ) ist das Eingangsfeld der komplexen Werte. Das Feld soll in derselben Weise gespeichert werden, wie es in bezug auf Fig. 6 beschrieben ist. W ( ) ist ) das Feld der komplexen Exponenten. B( ) ist das Ausgangsfeld der komplexen Werte und ist ähnlich dem A( ). Il ist der Index zwischen den Punkten in einem Vierer. 12 ist der Index zwischen Oberteilen (tops) eines Vierens. 13 ist der Index zwischen den Oberteilen (tops) von Divisionen. Gl ist die Zahl der Vierer pro Division. 02 ist die Zahl der Divisionen. SGN*ist 1, vvenn die inverse diskrete Fourier-Transformation (FI4) zu berechnen ist, und ist Null, wenn die Vorwärtsdiskrete Fourier-Transformation (FF4) zu berechnen ist. IOPT ist 0, wenn die Cooley-Tukey-Anordnung gewünscht ist, und 1, wenn die Sande-Tukey-Anordnung gewünscht ist.

Während der Ausführung der Algori thmen der Cooley-Tukey- oder Sande-Tukey-schnellen-Fourier-Transib m ation wird eine Aufnahme des transformierten Datenfeldes ausgeführt. Für N als einer Potenz von zwei folgt diese Aufnahme einem Muster, in dem das j-te Element des Eingangsfeldes abgebildet wird in die i-te Stelle des Ausgangsfeldes, wobei i die Zahl ist, die durch Umkehrung der binären Ziffern in der binären Darstellung

«) signal 109884/1190

si

von j repräsentiert wird. In den Cooley-Tukey-Formen der Algor i thmen der sclinellen Fourier-Transformation wird das Eingangsfeld in Ordnung eingeschrieben, und das Ausgangsfeld wird aufgenommen in sogenannter vermischter oder Bit-verkehrter Ordnung. In den Sande-Tukey-Formen der Algorithmen der schnellen Fourier-Transformation ist das Umgekehrte der Fall. Das heißt, das Eingangsfeld wird eingeschrieben in vermischter Ordnung, und das Ausgangsfeld wird so aufgenommen, daß das Ausgangsfeld in natürlicher Anordnung vorliegt.

Mit diesen drei Befehlen "FF2", "FF4" und FI4", deren Operationen, wie in den Fig. 6A und 7A sowie 7B gezeigt ist, in dem Nur-Auslese-Speicher des Feldprozessors 10 mikro-programmiert sind, können die Cooley-Tukey- und Sande-Tukey-schnelle Fourier-Transformationsalgori thmen für Basis 2 und gemischte Basis 2+4 oder 4+2 ausgeführt werden. Jede dieser \a?sehiedenen Kombinationen ist gezeigt in den vereinfachten Flußdiagrammen, die in den Figuren 8 bis 13 dargestellt sind. Diese Flußdiagramme sind vereinfacht worden, um nur die innere Logik und Erzeugung der Indizes und Zählungen, die in den G-rößensteuerwörtern für die Feldprozessor-schnelle Fourier-Transformation-Befehle benötigt werden, zu zeigen. In den Figuren 8 bis 13 wird die folgende Schreibweise verwendet: N ist die Zahl der zu transformierenden komplexen Punkte, m ist der Exponent 2, so daß N * 2 ist. SGN ist 1, wenn die inverse diskrete Fourier-Transformation auszurechnen ist, und ist -1, wenn die Vorwärtsdißkrete Fourier-Transformation zu berechnen ist. Das zu transformierende Datenfeld und die Tabelle der

109884/1190

komplexen Exponenten wird als angrenzend gespeichert m em aup SpQ-L₀J₁₈₁. angenommen zurweiteren Vereinfachung. Das Symbol £a/bj bezeichnet den "ganzzahligen Teil von" dem Quotienten a/b, beispielsweise Γ5/2Ί» NN ist der Index der W-Tabellenstelle, deren Adresse in dem Adressenfeld des Größensteuerwortes 2 beschrieben werden muß. Diese ist immer 1 für alle Cooley-Tukey-Algorithmen.

Unter speziellem Bezug auf die Figuren sind die Flußdiagramme für die Cooley-Tukey-Algorithmen in den Figuren 8, 9 und 10 gezeigt. Der Basis 2 Algorithmus ist in Figur 8 gezeigt, während der Basis 2+$- und 4+2-Algorithmus in den Figuren 9 bzw. 10 gezeigt sind. Die Figuren 11, 12 und 13 zeigen die Sande-Tukey-Algorithmen, während die Figur 11 den Basis 2-Algorithmus und die Figuren 12 und 13 die Basis 2+4- und 4+2-Algorithmen zeigen.

Patentansprüche:

109884/1190

Claims (8)

1. Patentansprüche

   Datenverarbeitungseinheit zur Ausführung des schnellen Fourier-Transformationsalgor ithmus, dadurch gekennzeichnet ,daß

   a) arithmetische Mittel zur Lösung der Kerngleichungen des Algor i thmus von der Form W*X-Y mit W als einem komplexen Exponenten, X als einem komplexen Eingangswert eines Eingangsdatensatzes und Y als einer vorher erzeugten Zwischenlösung und

   b) einem Mikroprogramm zur Steuerung der arithmetischen Mittel zum Bewirken einer stufenweisen Auswertung des /Igor i thmus vorgesehen sind, wobei eine Stufe definiert ist als Auswertung der Kerngleichungen für eine bestimmte Basis über alle Punkte in dem Datensatz.
2. 2. Zur Ausführung des schnellen Fourier-Transformationsalgorhythmus ausgebildete Datenverarbeitungseinheit zur Auswertung der diskreten Fourier-Transformation einer Eingangsfolge von N-komplexen Datenpunkten, wobei N zusammengesetzt ist aus r-Primfaktoren, so daß N-Gleichungen der diskreten Fourier-Transformation als eine Reihe von r-verschachtelten Summationen ausgedrückt ist, dadurch gekennzeichnet, daß

   a) Spei ehermittel für die Speicherung komplexer Eingangswertdaten und wenigstens eine Datentabelle von komplexen Exponenten,

   b) arithmetische Mittel zur Ausführung von Multiplikation-Additionsoperationen zur Lösung der Kerngleichungen

   den /*Jρ,ον i thmus mit νί*χίγ als der Form der

   109884/1190

   ιό 2872

   Multiplikations-Additionsoperation und W als einem komplexen Exponenten von der Datentabelle der komplexen Exponenten in den Speichermitteln, X als einem komplexen Eingangswert von Eingangsdaten in den Speichermitteln und Y als einem vorher erzeugten Zwischenergebnis und c) ein Mikroprogramm zur Steuerung der Speichermittel und der arithmetischen Mittel zum Bewirken einer gegebenen Summation jeder der in ^-Tuples gleichzeitig auszuwertenden N-GIeichungen für alle N-Gleichungen zur Bildung einer Stufe der diskreten Fourier-Transformation, wobei ^ ein entsprechend der gegebenen Summation für den schnellen Fourier-Transformationsalgor ithmus der Basis <£ entsprechen der Primfaktor ist und das vorher erzeugte Zwischenergebnis während der Auswertung der vorhergehenden Stufe der diskreten Fourier-Transformation erzeugt worden ist, vorgesehen sind.
3. 3· Datenverarbeitungseinheit nach Anspruch 2, dadurch gekennzeichnet, daß unterschiedliche Datentabellen komplexer Exponenten in dem Speicher zur Ausführung der Cooley-Tukey- und Sande-Tukey-Algor i thmen der schnellen Fourier-Transformation vorgesehen sind.
4. 4· Datenverarbeitungseinheit nach Anspruch 2 , dadurch gekennzeichnet ,daß ein Feldprozessor (10) vorgesehen ist, der a) eine arithmetische Einheit zur Ausführung einer Multiplikations-Additionsoperation W*X^Y mit W als dem^Iultiplikanten, X als dem Multiplikator und Y als der Ergänzung,

   10988 4/1 190

   - Sl-

   b) ein Eingangsregister zum Empfang der Steuerinformation und Größendaten,

   c) ein W-Register zum E_mpfang komplexer Exponentendatenelemente von dem Eingangeregister, wobei das vi-Register mit dem Multiplikatoreingang der arithmetischen Einheit verbunden ist,

   d) ein mit dem Eingangsregister verbundener X-Pufferspeicher zum Empfang komplexer Eingangswertdaten von dem Eingangsregister für eine temporäre Speicherung der Eingangsdatenelemente, die an den schnellen Fourier-Transformationsoperationen teilnehmen, wobei der X-Pufferspeicher weiterhin mit dem Multiplikatoreingang der arithmetischen Einheit verbunden ist,

   e) ein Y-Pufferspeicher, der mit dem Ausgang der arithmetischen Einheit verbunden ist, zum Aufnehmen von Zwischen- und Endergebnissen von durch die arithmetische Einheit erzeugten komplexen Zahlen zur temporären Speicherung dafür, wobei der Y-Pufferspeicher weiterhin mit dem Ergänzungseingang der arithmetischen Einheit verbunden ist, und

   f) ein auf die Steuerinformation in dem Eingangsregister ansprechendes Nur-Auslese-Speicher-Mikroprogramm zur Steuerung jedes der Register, der Pufferspeicher und der arithmetischen Einheit zum Bewirken einer gegebenen Summation von jeder der N-Gleichungen, die gleichzeitig in den ; -Tuples auszuwerten sind, für alle N-Gleichungen zur Bildung einer Stufe der diskreten Fourier-Transformation, wobei ^ ein Primfaktor entsprechend der gegebenen Summation für einen schnellen Fourier-Transformationsalgor ithmus der Basis ^ ist und die in dem Y-Pufferspeicher gespeicherten Zwischenergebnisse das Ergebnis der während der vorhergehenden Stufe der diskreten Fourier-Transformation ausgeführten

   10 9 8 8 4/1 190

   - Jf-

   Berechnung ist, vorgesehen sind.
5. 5· Datenverarbeitungseinheit nach Anspruch 4, dadurch gekennzeichnet, daß das Nur-Auslese-Speicher-Mikroprogramm eine Mehrzahl von Mikroprogrammbefehlen für Mehrfachbasen K enthält und jeder der Befehle die Beschreibung der Zahl der Divisionen.in der Stufe erfordert, wobei eine Division solche ¹^ -Tuples umfaßt, die ausgewertet werden unter Verwendung derselben komplexen Exponentei in der Stufe, der Zahl der Tuples in jeder Division und drei Indexinkrementen aus den Einheiten zwischen Punkten in einem Tuple, den Einheiten zwischen Oberteilen (tops) von Tuples und den Einheiten zwischen Tops der Divisionen.
6. 6. Datenverarbeitungseinheit nach Anspruch 5» dadurch gekennzeichnet , daß die/Mehrfachbasen %. die Basen 2 uncjA umfassen und ein Tuple in der Mehrzahl der Mikroprogrammbefehle aus einem Paar oder einem Quadruple besteht.
7. 7. Datenverarbeitungseinheit nach Anspruch 4, dadur ch gekennzeichnet, daß sie mit einer Zentralverarbeitungseinheit und einem Hauptspeicher verbunden ist und als Steuerinformation in dem Eingangsregister Eingangs-/Ausgangsbefehle von der zentralen Verarbeitungseinheit empfängt und als Antwort darauf schnelle-Pourier-Transformationsoperationen an komplexen Eingangswertdaten mit einer Datentabelle von komplexen Exponenten ausführt, die beide in dem Hauptspeicher gespeichert sind.

   1 09884/ 1 190
8. 8. Dat en verarbeitung se inhe it nach Anspruch 7» dadurch gekennzeichnet, daß

   unterschiedliche Tabellen komplexer Exponenten in dem Hauptspeicher zur Ausführung der Cooley-Tukey- und Sande-Tukey-Algor j thmen der schnellen Fourier-Transformation gespeichert sind.

   109884/1190

   Leerseite