DE69424790T2

DE69424790T2 - Prozessor für schnelle Fourier-Transformation

Info

Publication number: DE69424790T2
Application number: DE69424790T
Authority: DE
Inventors: Peter Reusens; Geert Verhenne
Original assignee: Alcatel SA; Alcatel NV
Current assignee: Alcatel Lucent SAS; Alcatel Lucent NV
Priority date: 1994-11-07
Filing date: 1994-11-07
Publication date: 2000-12-28
Anticipated expiration: 2014-11-08
Also published as: ES2146245T3; EP0710915A1; DE69424790D1; EP0710915B1; AU703643B2; US5633817A; AU3450895A

Description

Die vorliegende Erfindung betrifft einen Prozessor für schnelle Fourier-Transformation, welcher beinhaltet:
a. Speichermittel zum Speichern einer Eingangsdatenfolge;
b. Verschlüsselungsmittel zum Verschlüsseln der Eingangsdatenfolge, wodurch eine Mehrzahl von verschlüsselten Daten-Unterfolgen erzeugt wird, eine erste verschlüsselte Daten-Unterfolge, die ungeradzahlige Eingangsdatenelemente enthält, und eine zweite verschlüsselte Daten-Unterfolge, die geradzahlige Eingangsdatenelemente enthält;
c. eine Recheneinheit, die an die Verschlüsselungsmittel gekoppelt und dafür ausgelegt ist, eine Ausgangsfolge von schnellen Fourier-Transformierten der Eingangsdatenfolge aus den verschlüsselten Daten-Unterfolgen zu erzeugen, wobei die Recheneinheit dazu beinhaltet:
c1. Rechenmittel, die dafür ausgelegt sind, Schritte der schnellen Fourier-Transformation für eine Zeitverminderung auf einer komplexen Datenfolge rekursiv auszuführen, wodurch eine Zwischenreihe von schnellen Fourier-Transformierten erzeugt wird.
In der Technik ist bereits ein Prozessor für schnelle Fourier-Transformation bekannt, z. B. aus dem US-Patent US 4,612,626, worin der Absatz von Spalte 3, Zeile 12 bis Spalte 3, Zeile 20 eine Prozessorstruktur für schnelle Fourier- Transformation beschreibt, bei der reelle Eingangsfolgen verschlüsselt und Kanälen einer Recheneinheit zugeführt werden, die die grundlegenden Schritte einer schnellen Fourier-Transformation auf einer komplexen Eingabe ausführt. In der US 4,612,626 wird eingeräumt, daß der Entschlüsselungsvorgang, der im bekannten Prozessor für schnelle Fourier-Transformation auszuführen ist, um die Ausgangsfolge von schnellen Fourier-Transformierten der Eingangsfolge aus den von der Recheneinheit erzeugten, verschlüsselten Fourier-Transformierten zu erzeugen, eine beträchtliche zusätzliche Hardware erfordert, und es wird daher empfohlen, den bekannten Prozessor nicht zu verwenden. Das US-Patent US 3,638,004 offenbart einen Prozessor zum Berechnen einer potenzdiskreten Transformation (DFT), bei dem die Eingangsdatenfolge in zwei Unterfolgen verschlüsselt wird, eine erste, die die Eingangsdatenproben mit ungerader Ordnung beinhaltet, und eine zweite, die die Datenproben mit gerader Ordnung beinhaltet, und bei dem diese beiden verschlüsselten Daten-Unterfolgen zusammen in einer komplexen Datenfolge kombiniert werden, bevor sie in eine Recheneinheit eintreten, und bei dem die Recheneinheit zwei Multiplikatoren umfaßt.
Eine Aufgabe der vorliegenden Erfindung ist es, einen Prozessor für schnelle Fourier-Transformation des obigen bekannten Typs bereitzustellen, bei dem aber der auszuführende Entschlüsselungsvorgang die mathematische Komplexität nicht merklich erhöht und keine wesentliche Hardware-Ergänzung erfordert.
Gemäß der Erfindung wird diese Aufgabe aufgrund der Tatsache gelöst, daß der Prozessor zur Verarbeitung einer reellen Eingangsdatenfolge zusätzlich beinhaltet:
d. eine Datenerzeugungsschaltung, die zwischen den Verschlüsselungsmitteln und der Recheneinheit angeschlossen und dafür ausgelegt ist, aus den verschlüsselten Daten-Unterfolgen die komplexe Datenfolge herzuleiten, die einen reellen und einen imaginären Teil gleich den jeweiligen des Paares von verschlüsselten Daten-Unterfolgen aufweist; und daß die Recheneinheit ferner beinhaltet:
c2. eine Datenregenerierungsschaltung, die dafür ausgelegt ist, aus der Zwischenreihe von schnellen Fourier-Transformierten einzelne Reihen von schnellen Fourier-Transformierten des Paares verschlüsselter Daten-Unterfolgen entsprechend den Formeln 2 A(i) = Y(i) + Y(2N-i)cc und 2 B(i) = j Y(i) - j Y(2N-i)cc zu erzeugen, worin A(i) und B(i) die einzelnen Reihen von schnellen Fourier-Transformierten sind; Y(i) die Zwischenreihe von schnellen Fourier-Transformierten ist; 2N die Länge von Y(i) ist; Y(2N-i)cc die komplex konjugierte Zahl von Y(2N-i) ist;
c3. kombinatorische Mittel, die dafür ausgelegt sind, einen Endschritt der schnellen Fourier-Transformation für eine Zeitverminderung auf den einzelnen Reihen von schnellen Fourier-Transformierten auszuführen, um dadurch die Ausgangsfolge von schnellen Fourier-Transformierten zu liefern;
c4. eine Steuereinheit, die dafür ausgelegt ist, die Recheneinheit selektiv in die Rechenmittel, die Regenerierungsschaltung und die kombinatorischen Mittel umzuwandeln; und
c5. einen Datenspeicher, um nacheinander die komplexe Datenfolge zu speichern, die Zwischenreihe von schnellen Fourier- Transformierten zu speichern, die einzelnen Reihen von schnellen Fourier-Transformierten zu speichern und die Ausgangsfolge von schnellen Fourier-Transformierten zu speichern.
Auf diese Weise wird durch Herleiten der komplexen Datenfolge aus dem Paar verschlüsselter Daten-Unterfolgen mit beispielsweise der Länge N/2 und durch Ausführen der schnellen Fourier-Transformation auf dieser komplexen Datenfolge die Anzahl von beim Entschlüsselungsvorgang auszuführenden Rechenoperationen beträchtlich verringert und sie sind dann einfach mit Hardware auszuführen, die in der Recheneinheit bereits verfügbar ist.
Verglichen mit dem bekannten Prozessor bedeutet die Verwendung der Regenerierungsschaltung eine zusätzliche Anzahl auszuführender Operationen. Der Betrieb der Regenerierungsschaltung basiert jedoch auf den Symmetrieeigenschaften der Ausgangsdatenreihe von schnellen Fourier-Transformierten einer reellen Eingangsdatenfolge, infolge dessen diese Regenerierung nur Additions/Subtraktions-Operationen ausführt, um die einzelnen Reihen von schnellen Fourier-Transformierten aus den Zwischenreihen von schnellen Fourier-Transformierten herzuleiten, und daher erhöht ihr Vorhandensein im erfindungsgemäßen Prozessor die Rechenzeit nicht merklich.
Darüber hinaus ist dieselbe Recheneinheit der Reihe nach fähig, die Funktionen der Rechenmittel, der Regenerierungsschaltung und der kombinatorischen Mittel auszuführen. Mit anderen Worten: das Vorhandensein der Regenerierungsschaltung und der kombinatorischen Mittel erhöht abgesehen von einer Steuereinheit nicht die Komplexität der Hardware.
Ein weiteres kennzeichnendes Merkmal des Prozessors der vorliegenden Erfindung ist, daß die Recheneinheit erste Registermittel, die dafür ausgelegt sind, reelle und imaginäre Teile von Datenelementen der Eingangsdaten und für Berechnungen von schnellen Fourier-Transformierten charakteristische Wichtungskoeffizienten vorübergehend zu speichern, zweite Registermittel, die an die ersten Registermittel gekoppelt und dafür ausgelegt sind, Daten vorübergehend zu speichern, Multiplikatormittel, die dafür ausgelegt sind, in den zweiten Registermitteln gespeicherte Daten zu multiplizieren, eine erste Addier/Subtrahier-Einrichtung, die an die Multiplikatormittel gekoppelt und dafür ausgelegt ist, Ausgangsprodukte der Multiplikatormittel zu addieren/subtrahieren, eine Schiebeschaltung, die dafür ausgelegt ist, ihr zugeführte Zwischenergebnisse hin- und herzuschieben und vorübergehend zu speichern, eine zweite Addier/Subtrahier-Einrichtung, auf deren Eingänge die Zwischenergebnisse gegeben werden, eine Ausgangsschaltung, die an den Datenspeicher gekoppelt ist und die Kaskadenschaltung einer Ordnungseinrichtung und eine Skaliereinrichtung umfaßt, um ihr zugeführte Daten anzuordnen und zu skalieren und sie im Datenspeicher zu speichern, und Auswahlmittel beinhaltet, die von der Steuereinheit so gesteuert werden, daß sie die Umwandlung der Recheneinheit selektiv ausführt.
Noch ein weiteres kennzeichnendes Merkmal des Prozessors der vorliegenden Erfindung ist, daß die Auswahlmittel unter Kontrolle der Steuereinheit dafür ausgelegt sind, die Recheneinheit in die Rechenmittel umzuwandeln, indem die zweiten Registermittel über die Kaskadenschaltung der Multiplikatormittel und die erste Addier/Subtrahier-Einrichtung, wenn der Schritt der schnellen Fourier-Transformation für eine Zeitverminderung vom Typ mit Radix 2 ist, und über die Kaskadenschaltung der Multiplikatormittel, die erste Addier/Subtrahier-Einrichtung, die Schiebeschaltung und die zweite Addier/Subtrahier- Einrichtung, wenn der Schritt der schnellen Fourier-Transformation für eine Zeitverminderung vom Typ mit Radix 4 ist, an die Ausgangsschaltung gekoppelt werden, und daß die Auswahlmittel unter Kontrolle der Steuereinheit dafür ausgelegt sind, die Recheneinheit in die kombinatorischen Mittel umzuwandeln, indem die zweiten Registermittel über die Kaskadenschaltung der Multiplikatormittel, die erste Addier/Subtrahier-Einrichtung, die Schiebeschaltung und die zweite Addier/Subtrahier-Einrichtung an die Ausgangsschaltung gekoppelt werden, um den Endschritt der schnellen Fourier-Transformation für eine Zeitverminderung vom Typ mit Radix 4 auszuführen.
Somit kann unter Kontrolle der Steuereinheit die Recheneinheit leicht dafür ausgelegt werden, entweder einen Schritt der schnellen Fourier-Transformation für eine Zeitverminderung mit Radix 2 oder Radix 4 auszuführen.
Noch ein weiteres kennzeichnendes Merkmal des Prozessors der vorliegenden Erfindung ist, daß die Auswahlmittel unter Kon trolle der Steuereinheit dafür ausgelegt sind, die Recheneinheit in die Regenerierungsschaltung umzuwandeln, indem ein Eingangsdaten speichernder Teil der ersten Registermittel über die Kaskadenschaltung der Schiebeschaltung und die zweite Addier/Subtrahier-Einrichtung an die Ausgangsschaltung gekoppelt wird.
Somit führt die Recheneinheit den Regenerierungsschritt nur mittels der zweiten Addier/Subtrahier-Schaltung, d. h. ohne Verwendung der beiden Multiplikatoren und der ersten Addier/Subtrahier-Schaltung aus. Es wird später gezeigt, daß eine solche Additions/Subtraktions-Operation ausreicht, um die verflochtenen einzelnen Reihen von schnellen Fourier- Transformierten von der Zwischenreihe von schnellen Fourier- Transformierten zu trennen.
Noch ein weiteres kennzeichnendes Merkmal des Prozessors der vorliegenden Erfindung ist, daß die Recheneinheit darüber hinaus Speichermittel für Wichtungskoeffizienten, die die Wichtungskoeffizienten speichern, eine Datenverarbeitungsschaltung, die an den Datenspeicher gekoppelt und dafür ausgelegt ist, die reellen und imaginären Teile der Datenelemente der Eingangsdaten zu überlagern, und eine Verarbeitungsschaltung für Wichtungskoeffizienten beinhaltet, die an die Speichermittel für Wichtungskoeffizienten gekoppelt und dafür ausgelegt ist, reelle und imaginäre Teile der in den Speichermitteln gespeicherten Wichtungskoeffizienten zu überlagern und zu invertieren.
Beispielsweise aus den Seiten 369-379 des Buches 'Digital Filters: Analysis and Design' von Andreas Antoniou, veröffentlicht 1979 von McGraw Hill, ist bekannt, daß Wichtungskoeffizienten, die für Berechnungen der schnellen Fourier- Transformation kennzeichnend sind, durch einen Parameter α gekennzeichnet sind, der einem Winkel in einer komplexen Ebene entspricht. Durch Überlagern und Invertieren von reellen und imaginären Teilen der in den Speichermitteln gespei cherten Koeffizienten erzeugt die Koeffizientenverarbeitungsschaltung alle Wichtungskoeffizienten, die durch α-Werte größer als 90º gekennzeichnet sind, aus Wichtungskoeffizienten, die durch niedrigere α-Werte gekennzeichnet sind. Somit wird eine merkliche Verringerung der erforderlichen Speichermittel für Koeffizienten erhalten.
Die vorliegende Erfindung wird gemäß dem Prozessor für schnelle Fourier-Transformation des beigefügten unabhängigen Anspruchs 1 ausgeführt.
Die oben genannten und weitere Aufgaben und Merkmale der Erfindung werden deutlicher und die Erfindung selbst wird besser verstanden, indem auf die folgende Beschreibung einer Ausführungsform in Verbindung mit den beigefügten Zeichnungen Bezug genommen wird, in welchen:
Fig. 1 ein Funktions-Blockdiagramm einer Ausführungsform eines erfindungsgemäßen Prozessors P für schnelle Fourier-Transformation ist; und
Fig. 2 ein ausführliches Diagramm der Recheneinheit AU von Fig. 1 ist.
Der in Fig. 1 gezeigte Prozessor P ist fähig, aus einer Eingangsdatenfolge x(i) von Datenelementen eine Ausgangsfolge X(i) von schnellen Fourier-Transformierten zu berechnen. Er beinhaltet einen Speicher mm, um diese Eingangsdatenfolge x(i) zu speichern, und eine Verschlüsselungseinrichtung SM, um die so gespeicherte Eingangsdatenfolge x(i) zu verschlüsseln und eine verschlüsselte Daten-Unterfolge a(i), die ungeradzahlige Eingansdatenelemente x(2i+1) enthält, und eine verschlüsselte Daten-Unterfolge b(i) zu erzeugen, die geradzahlige Eingangsdatenelemente x(2i) enthält. Die Verschlüsselungseinrichtung SM verschlüsselt die Eingangsdatenfolge x(i) und erzeugt die verschlüsselten Daten-Unterfolgen a(i) und b(i), um die wohlbekannte Implementierung mit Radix 2 des Al gorithmus der schnellen Fourier-Transformation ausführen zu können.
Der Speicher mm kann sowohl eine komplexe als auch eine reelle Datenfolge speichern. Obwohl der Prozessor P in erster Linie dafür ausgelegt ist, eine reelle Eingangsdatenfolge x(i) zu verarbeiten, kann er auch verwendet werden, um die Reihe von schnellen Fourier-Transformierten einer komplexen Eingangsdatenfolge x(i) zu berechnen. Im folgenden wird jedoch zuerst die Verarbeitung einer reellen Eingangsdatenfolge x(i) betrachtet.
Wie gezeigt beinhaltet der Prozessor P zusätzlich eine Datenerzeugungsschaltung GC, um aus den obigen beiden verschlüsselten Daten-Unterfolgen a(i) und b(i) eine komplexe Datenfolge y(i) zu erzeugen, deren reeller und imaginärer Teil aus den jeweiligen dieser Unterfolgen bestehen.
Wegen der Ähnlichkeit der von der Verschlüsselungseinrichtung SM und der Datenerzeugungsschaltung GC auszuführenden Operationen können beide beispielsweise einen Teil einer Datenordnereinheit DSU bilden, wie in Fig. 1 angegeben.
Der Betrieb der Datenerzeugungsschaltung GC basiert auf der Einsicht, daß bei einer reellen Eingangsdatenfolge x(i) die Hälfte des Speichers mm wegen des Nichtvorhandenseins imaginärer Teile mit Nullen gefüllt ist. Diese normalerweise leere Hälfte von mm könnte mit einer zweiten fortlaufenden reellen Eingangsdatenfolge gefüllt werden, infolge dessen würde es möglich, eine Reihe von schnellen Fourier-Transformierten einer reellen Eingangsdatenfolge mit doppelter Länge zu berechnen. Jedoch und wie bereits erläutert würde dann die zur Speicherung der Ausgangsdatenfolge X(i) erforderliche Speicherfähigkeit zweimal so groß sein und es können möglicherweise Verzögerungseffekte auftreten.
Um eine solche Erhöhung der Ausgangsspeicherfähigkeit zu vermeiden, werden die beiden reellen Daten-Unterfolgen a(i) und b(i) daher von GC als reeller Teil bzw. imaginärer Teil einer komplexen Datenfolge y(i) behandelt. GC speichert diese Teile von y(i) in der ersten und der zweiten Hälfte eines Speichers DMM, der einen Teil einer Recheneinheit AU bildet.
Der Speicher MM, die Verschlüsselungseinrichtung SM und die Datenerzeugungsschaltung GC werden nicht ausführlicher beschrieben, da ihre Implementierung für einen Fachmann auf dem Gebiet aus der obigen Funktionsbeschreibung offensichtlich ist.
Die letztere Recheneinheit AU ist fähig, eine Reihe von Funktionen auszuführen, die durch die Funktionsblöcke oder Einrichtungen AM, RC, CM, DMM und CSM dargestellt sind. Insbesondere ist AM eine Recheneinrichtung, ist RC eine Datenregenerierungsschaltung, ist cm eine kombinatorische Einrichtung, ist DMM ein Datenspeicher und ist CSM eine Speichereinrichtung für Wichtungskoeffizienten, wobei diese Koeffizienten in Berechnungen der schnellen Fourier-Transformation verwendet werden.
Die Recheneinrichtung AM berechnet aus der komplexen Datenfolge y(i), die auf ihren Eingang gegeben wird und in DMM gespeichert ist, eine Zwischenreihe Y(i) von schnellen Fourier- Transformierten.
Wie später erläutert wird, leitet die Datenregenerierungsschaltung RC, deren Logik auf den Symmetrieeigenschaften der Ausgangsfolge von schnellen Fourier-Transformierten für eine reelle Eingangsdatenfolge basiert, aus der auf ihren Eingang gegebenen Zwischenreihe Y(i) von schnellen Fourier-Transformierten einzelne Reihen A(i) und B(i) von schnellen Fourier- Transformierten der verschlüsselten Daten-Unterfolgen a(i) und b(i) her.
Schließlich führt die kombinatorische Einrichtung cm den wohlbekannten Schritt der schnellen Fourier-Transformation für eine Zeitverminderung durch und leitet dadurch aus den auf ihren Eingang gegebenen einzelnen Reihen A(i) und B(i) von schnellen Fourier-Transformierten die Ausgangsfolge X(i) von schnellen Fourier-Transformierten der Eingangsdatenfolge x(i) her.
Im folgenden werden mathematische Berechnungen, die von den Symmetrieformeln der Reihen von schnellen Fourier-Transformierten einer reellen Datenfolge ausgehen, verwendet, um zu erläutern, wie die obige Erzeugung einzelner Reihen A(i) und B(i) von schnellen Fourier-Transformierten in der Datenregenerierungsschaltung RC erhalten wird.
Es ist wohlbekannt, daß aufgrund von Symmetrieeigenschaften der schnellen Fourier-Transformation symmetrisch positionierte Datenelemente in der Ausgangsfolge von schnellen Fourier- Transformierten einer reellen Eingangsdatenfolge komplex konjugiert sind.
Werden die beiden komplexen Reihen A(i) und B(i) betrachtet, die einzelne Reihen von schnellen Fourier-Transformierten der beiden reellen Daten-Unterfolgen a(i) und b(i) sind, die 2N Datenelemente beinhalten, bringen die oben genannten Symmetrieeigenschaften mit sich, daß:
A(i) = A(2N-i)cc und
B(i) = B(2N i)cc
worin A(2N-i)cc und B(2N-i)cc die komplex konjugierten Zahlen von A(2N-i) und B(2N-i) bezeichnen.
Wird andererseits die komplexe Datenfolge y(i) betrachtet, deren reelle und imaginäre Teile gleich den beiden reellen Daten-Unterfolgen a(i) und b(i) sind, d. h.
y(i) = a(i) + jb(i)
und werden die Linearitätseigenschaften der schnellen Fourier-Transformation berücksichtigt, kann Y(i) geschrieben werden als:
Y(i) = A(i) + jB(i) (1)
worin Y(i) die Zwischenreihe von schnellen Fourier-Transformierten der komplexen Datenfolge y(i) ist.
Somit: Y(2N-i) = A(2N-i) + jB(2N-i)
und gemäß dem obigen bedeutet dies, daß:
Y(2N-i) = A(i)cc + jB(i)cc
und: Y(2N-i)cc = A(i) - jB(i) (2)
Die Kombination der Gleichungen (1) und (2) zeigt, daß es möglich ist, die beiden einzelnen Reihen A(i) und B(i) von schnellen Fourier-Transformierten aus der Zwischenreihe Y(i) von schnellen Fourier-Transformierten zu berechnen. Tatsächlich:
2A(i) = Y(i) + Y(2N-i)cc (3)
2B(i) = jY(i) - jY(2N-i)cc (4)
Aus den letzteren Beziehungen (3) und (4) ist klar, daß die Datenregenerierungsschaltung RC die einzelnen Reihen A(i) und B(i) von schnellen Fourier-Transformierten aus den Zwischenergebnissen Y(i), von denen einige komplex konjugiert sind, erzeugen kann, indem nur Additions/Subtraktions-Operationen ausgeführt werden.
Es wird nun auf Fig. 2 Bezug genommen, die die Recheneinheit AU von Fig. 1 ausführlich zeigt. Es können jedoch nur DMM und CSM von Fig. 1 und nicht AM, RC und cm davon in Fig. 2 erkannt werden, weil AU fähig ist, eine ausgewählte dieser Funktionen AM, RC und cm durch eine geeignete Auslegung ihrer logischen Struktur unter Kontrolle geeigneter, von einer Steuereinheit CoM gelieferter Steuersignale auszuführen. Dies bedeutet, daß AU nacheinander als Funktionsblöcke AM, RC und cm von Fig. 1 funktioniert.
Wie bereits erwähnt, speichert CSM Gewichtskoeffizienten, die für Berechnungen von schnellen Fourier-Transformierten kennzeichnend sind, und nimmt DMM die zu verarbeitenden Daten r und s auf.
Eine Koeffizientenverarbeitungsschaltung CT ist mit der CSM verbunden, um die reellen und imaginären Teile, cr und ci, der auf ihre Eingänge gegebenen, gespeicherten Wichtungskoeffizienten zu überlagern und zu invertieren, wodurch die reellen und imaginären Teile w und z der Wichtungskoeffizienten erzeugt werden, die für den Verarbeitungsbetrieb notwendig sind.
Auf ähnliche Weise ist die Datenverarbeitungsschaltung DT, die u, v ausgibt, mit dem Speicher DMM verbunden, um die Daten r und s zu verarbeiten.
Die in der CSM gespeicherten Wichtungskoeffizienten sind komplexe Exponentialgrößen ejα, die durch einen einzigen Parameter α gekennzeichnet sind, dessen Wert einem Winkel in einer komplexen Ebene entspricht. Somit sind reelle und imaginäre Teile der Wichtungskoeffizienten gleich dem Cosinus bzw. Sinus des Winkels α:
ejα = cos(α) + j sin (α)
Cosinus- und Sinuswerte von Winkeln, die α-Werten größer als 90ºC entsprechen, können leicht aus dem Cosinus und Sinus von Winkeln im ersten Quadranten der komplexen Ebene erhalten werden. In der Tat reicht es aus, einen Cosinus durch einen Sinus, mit einem möglichen Vorzeichenwechsel, zu ersetzen oder umgekehrt. Diese Ersetzungen und Vorzeichenwechsel werden von der CT ausgeführt.
Die DT und CT sind auf die folgende Weise an Register u1, u2, v1, v2, w1, w2, z1 und z2 gekoppelt: der Ausgang u von DT ist mit den Registern u1 und u2 verbunden, die zur zeitweisen Speicherung der reellen Teile zweier aufeinanderfolgender erster bzw. zweiter komplexer Ausgangsdatenelemente von DT verwendet werden, und der Ausgang v von DT ist mit den Registern v1 und v2 verbunden, die zur zeitweisen Speicherung der imaginären Teile dieser beiden ersten bzw. zweiten komplexen Ausgangsdatenelemente verwendet werden. Auf ähnliche Weise ist der Ausgang w von CSM mit den beiden Registern w1 und w2 verbunden, um darin die reellen Teile zweier aufeinanderfolgender erster bzw. zweiter Wichtungskoeffizienten zu speichern, während der Ausgang z von CSM mit den Registern z1, und z2 verbunden ist, um darin die imaginären Teile jeweiliger dieser ersten und zweiten Wichtungskoeffizienten zu speichern.
Ferner sind Paare der obigen Register mit den jeweiligen der vier taktgesteuerten Multiplexer mx1, mx2, mx3, mx4 verbunden, d. h. Ausgänge von u1 und v1 sind mit jeweiligen Eingängen 1 und 2 von mx1 verbunden, um zu ermöglichen, daß mx1 entweder den reellen oder den imaginären Teil des ersten komplexen Datenelements auszuwählen, das in einem Register r1 gespeichert werden soll, das zwischen mx1 und einem Eingang 1 eines Multiplikators M1 angeschlossen ist. Mx3, mit dessen Eingängen 1 und 2 jeweilige Register w1 und 21 verbunden sind, ist über ein Register r2 an einen zweiten Eingang 2 von M1 gekoppelt. Die Ausgänge u2 und v2 sind mit mx2 verbunden, der entweder den reellen oder imaginären Teil des obigen zweiten komplexen Datenelements auswählt, der in einem Register r3 gespeichert werden soll, welcher mx2 an den Eingang 1 eines Multiplikators M2 koppelt. Schließlich koppelt das Register r4 mx4 an einen zweiten Eingang 2 von M2, wobei die Eingänge von mx4 mit w2 bzw. 22 verbunden sind.
Die Ausgänge von M1 und M2 sind mit jeweiligen Eingängen 1 und 2 einer ersten Addier/Subtrahier-Schaltung AS1 verbunden.
Es ist zu bemerken, daß in Fig. 2 eine Verzögerungseinrichtung D zusätzlich zwischen M1 und AS1 angeschlossen ist, weil verglichen mit jenen von M2 die Ausgangsprodukte von M1 früher verfügbar sind.
Außerdem sind jeweilige Ausgänge 1 und 2 von AS1 an erste Eingänge i1 und i1' jeweiliger Multiplexer mx5 und mx6 mit 3 Eingängen gekoppelt, die beide einen Teil einer Schiebeschaltung SC bilden. SC umfaßt auch eine Speichereinrichtung ST und einen Multiplexer mx7. ST enthält vier Register a, b, c und d, um vorübergehend Zwischenergebnisse zu speichern, die von mx5 und mx6 erhalten werden, und der Multiplexer mx7 koppelt die Register a, b, c und d an eine zweite Addier/Subtrahier-Schaltung AS2. Daher wählt mx7 zwei seiner Eingaben aus, die auf jeweilige Eingänge 1 und 2 von AS2 gegeben werden.
Um fähig zu sein, Daten auf eine Ausgabeschaltung OC zu geben, die eine Kaskadenverbindung einer Ordnungseinrichtung OM und eine Skaliereinrichtung ScL umfaßt, sind Auswahlmittel S1 und S1' zwischen die Ausgänge von M1 und M2 und jeweilige Eingänge 1 und 2 von OM gekoppelt, sind Auswahlmittel S2 und S2' zwischen Ausgänge 1 und 2 von AS1 und jeweilige Eingänge 1 und 2 von OM gekoppelt und sind Auswahlmittel S3 und S3' zwischen Ausgänge 1 und 2 von AS2 und jeweilige Eingänge von OM gekoppelt.
Schließlich ist ScL mit DMM verbunden, um die Ausgangsdaten O von ScL zu speichern.
Die Auswahlmittel S1, S1', S2, S2', S3, S3', Multiplexer mx5, mx6, mx7 und die Ordnungseinrichtung OM werden von der oben genannten Steuereinheit CoM so gesteuert, daß es ermöglicht wird, daß AU entweder einen schnellen Fourier-Schritt mit Radix 2, einen schnellen Fourier-Schritt mit Radix 4, einen Regenerierungsschritt, einen anfänglichen Addier/Subtrahier- Schritt, der für Berechnungen von inversen schnellen Fourier- Transformierten notwendig ist, einen speziellen Umkehrschritt, der auch bei Berechnungen von inversen schnellen Fourier-Transformierten verwendet wird, oder eine komplexe Multiplikation auszuführen.
Wie später klar wird, sind daher die Ausgänge von M1 und u1 auch mit jeweiligen Eingängen i2 und i3 von mx5 verbunden, während die Ausgänge von M2 und v1 an jeweilige Eingänge i2' und i3' von mx6 gekoppelt sind.
Es ist zu bemerken, daß aus Gründen der Klarheit der Zeichnung in Fig. 2 die Verbindungsleitungen zwischen der Steuereinheit CoM und den Steuereingängen verschiedener Hardware- Komponenten nicht gezeigt sondern durch zwei Pfeile symbolisch dargestellt sind, die die Richtung des Steuersignalflusses angeben. Auch sind in Fig. 2 die Verbindungsleitungen für Taktsignale nicht gezeigt sondern durch einfache Pfeile symbolisch dargestellt, die mit c1 bezeichnet sind.
Im folgenden ist erläutert, wie es ermöglicht wird, daß AU einen ausgewählten der obigen Schritte ausführt.
Nacheinander wird beschrieben, wie ein Schritt der schnellen Fourier-Transformation für eine Zeitverminderung mit Radix 2 (AM von Fig. 1), ein Schritt der schnellen Fourier-Transformation für eine Zeitverminderung mit Radix 4, ein Regenerierungsschritt (RC von Fig. 1), ein kombinatorischer Schritt (cm von Fig. 1), ein anfänglicher Addier/Subtrahier-Schritt, ein spezieller Umkehrschritt und eine komplexe Multiplikation ausgeführt werden. Danach wird erläutert, wie eine komplexe Eingangsdatenfolge x(i) von P verarbeitet wird.
Wird immer noch eine reelle Eingangsdatenfolge x(i) betrachtet, wird angenommen, daß ein Schritt der schnellen Fourier- Transformation für eine Zeitverminderung mit Radix 2 ausgeführt werden soll. In diesem Fall sind die Eingangsdaten r und s die reellen und imaginären Teile der komplexen Datenfolge y(i), die in DMM gespeichert ist und die beiden verschlüsselten Daten-Unterfolgen a(i) und b(i) umfaßt.
Um die komplexe Multiplikation (u1.w1 - v1.z1) + j (u1.z1 + v1.w1) eines komplexen Datenelements u1 + j v1 und eines komplexen Wichtungskoeffizienten w1 + j z1 auszuführen, werden vier partielle reelle Multiplikationen ausgeführt, d. h. u1.w1, -v1.z1, u1.z1 und v1.w1. Das negative Vorzeichen im Faktor -v1.z1 wird von CT geliefert.
Die Datenverarbeitungsschaltung DT überlagert die reellen und imaginären Teile r und s, um u1 und v1 eines komplexen Datenelements u1 + j v1 zu erzeugen, und die Verarbeitungsschaltung CT für Koeffizienten erzeugt aus einem in CSM gespeicherten Wichtungskoeffizient einen komplexen Wichtungskoeffizienten w1 + j z1.
Es ist zu bemerken, daß die reellen und imaginären Teile der Daten und Wichtungskoeffizienten, die multipliziert werden sollen, zeitweise in den Registern u1, v1, w1 und z1 gespeichert werden.
Dann speichern taktgesteuerte Multiplexer mx1 und mx3 zeitweise eine ihrer Eingaben in einer solchen Weise in jeweiligen Ausgangsregistern r1 und r2, daß M1, der die in r1 und r2 gespeicherten Daten multipliziert, sofort den reellen Teil u1.w1 - v1.z1 und den imaginären Teil u1.z1 + v1.w1 des obigen Produkts erzeugt. Dies bedeutet, daß M1 u1 und w1 multipliziert, außerdem v1 und -z1 multipliziert und schließlich diese beiden Produkte addiert. Daher sind M1 und M2 keine herkömmlichen Multiplikatoren, die nach jeder Multiplikation automatisch einen Rücksetzschritt ausführen. Das Ausgangsprodukt von M1 oder M2 wird immer zu seinem vorherigen Ausgangsprodukt addiert, außer wenn ein externes Steuersignal auf seinen Rücksetzeingang r gegeben wird. Im letzteren Fall wird ein vorheriger Rücksetzschritt ausgeführt, bevor der Multiplikator das Multiplizieren beginnt.
Auf ähnliche Weise erzeugt der zweite Multiplikator M2 den reellen Teil u2.w2 - v2.z2 und den imaginären Teil u2.z2 + v2.w2 des Produkts (u2 + j v2). (w2 + j z2).
Die Produkte von M1 und M2 werden an AS1 gegeben, um den Schritt der schnellen Fourier-Transformation für eine Zeitverminderung mit Radix 2 mit einer Additions/Subtraktions- Operation abzuschließen.
Unter Kontrolle der Steuereinheit CoM und um diese schnellen Fourier-Ergebnisse mit Radix 2 auszugeben, werden S2 und S2' aktiviert, während S1, S1', S3 und S3' deaktiviert werden.
Als Folge werden somit die Ausgangsdaten von AS1 durch OM und ScL geschickt, um das angeordnete und skalierte Ausgangsergebnis 0 zu erhalten, das die Zwischenreihe Y(i) von Fourier- Transformierten ist. Y(i) wird schließlich in DMM gespeichert.
In dem Fall, in dem ein Schritt der schnellen Fourier-Transformation für eine Zeitverminderung mit Radix 4 ausgeführt werden muß, muß die Verschlüsselungseinrichtung SM von Fig. 1 entsprechend dem Rest der Anzahl von Eingangsdaten, modulo 4, vier verschlüsselte Daten-Unterfolgen statt zwei erzeugen. Die Datenerzeugungsschaltung GC von Fig. 1 muß dann Paare dieser Unterfolgen zu zwei komplexen Datenfolgen kombinieren, die im Speicher DMM von AU gespeichert werden.
Um zu ermöglichen, daß AU einen Schritt der schnellen Fourier-Transformation für eine Zeitverminderung mit Radix 4 ausführt, werden S1, S1', S2 und S2' deaktiviert, während S3 und S3' aktiviert werden. Um einen solchen Schritt mit Radix 4 auszuführen, werden M1, M2 und AS1 wieder verwendet, um Schritte mit Radix 2 auszuführen, aber zusätzlich werden die Ergebnisse dieser Schritte mit Radix 2 an die Addier/Subtrahier-Schaltung AS2 gegeben, um den Schritt mit Radix 4 abzuschließen. Insbesondere koppeln die in SC eingeschlossenen Multiplexer mx5 und mx6 auf der Basis von von CoM erhaltenen Steuersignalen ihre jeweiligen ersten Eingänge i1 und i1' an ST, so daß die Ergebnisse der schnellen Fourier-Transformation mit Radix 2 am Ausgang von AS1 zeitweise in den Registern a, b, c und d von ST gespeichert werden. Der Multiplexer mx7 wird dann von CoM derart gesteuert, daß diese Ergebnisse der schnellen Fourier-Transformation mit Radix 2 in Paaren an AS2 gegeben werden. Wieder werden die Ausgangsdaten O, die die Ergebnisse der schnellen Fourier-Transformation mit Radix 4 darstellen, von OM bzw. ScL angeordnet und skaliert, bevor sie in DMM gespeichert werden.
Wenn die Zwischenreihe Y(i) von schnellen Fourier-Transformierten in DMM gespeichert wurde, muß AU derart umgewandelt werden, daß sie fähig ist, sich wie Funktionsblock RC von Fig. 1 zu verhalten. AU ist dann fähig, aus Y(i) A(i), B(i) herzuleiten, was an DT gegeben wird.
In Fig. 2 sind somit die Eingangsdaten r und s die reellen und imaginären Teile von Y(i), aus welchen die DT die komplex konjugierten und nicht komplex konjugierten Terme Y(i) bzw. Y(2N-i)cc der obigen Gleichungen (3) und (4) erzeugt.
Wie bereits erwähnt und wie aus diesen Gleichungen folgt, genügt es, diese Terme zu addieren oder zu subtrahieren, um die einzelnen Reihen A(i) und B(i) von schnellen Fourier-Transformierten zu erzeugen. Daher sind Ausgänge von u1 und v1 mit jeweiligen Eingängen i3 und i3' von mx5 und mx6 verbunden, die unter Kontrolle von CoM die obigen Terme über ST und mx7 sofort an AS2 gibt. Darüber hinaus deaktiviert CoM S1, S1', S2 und S2' und aktiviert S3 und S3', so daß A(i) und B(i) daher an OC gegeben werden und sie über den Ausgang O in DMM gespeichert werden.
Es wird bemerkt, daß es nicht von Bedeutung ist, ob M1, M2 und AS1 die Daten an ihren Eingängen verarbeiten oder nicht, da Ausgangsergebnisse von M1, M2 und AS1 keinen Einfluß auf die Ausgangsfolge O von AU haben, weil der Zugang von M1, M2 oder AS1 zu SC durch mx5 und mx6 versperrt ist. Auch sind M1, M2 und AS1 aufgrund dessen, daß S1, S1', S2 und S2' deaktiviert sind, von OC getrennt.
Schließlich wird AU in einen Zustand gebracht, in dem sie fähig ist, einen kombinatorischen Schritt gleich dem des Funktionsblocks cm in Fig. 1 auszuführen.
Dieser kombinatorische Schritt ist ein Endschritt der schnellen Fourier-Transformation für eine Zeitverminderung mit Radix 4 und wird wie bereits oben für AM beschrieben ausgeführt. Weil die Eingangsdaten A(i), B(i) sind, sind jedoch die Ausgangsergebnisse 0 nun gleich der Folge X(i) von schnellen Fourier-Transformierten der Eingangsdatenfolge x(i).
Darüber hinaus und wiederum abhängig vom Zustand der Auswahlmittel kann die Recheneinheit AU entweder einen einfachen Algorithmus der schnellen Fourier-Transformation oder einen Umkehralgorithmus der schnellen Fourier-Transformation ausführen. Tatsächlich wird eine Folge von Rechenoperationen eines Vorwärtsalgorithmus der schnellen Fourier-Transformation schematisch dargestellt als:
worin x eine Multiplikation darstellt, +/- eine Additions/Subtraktions-Operation darstellt, aufeinanderfolgende Schritte abgrenzt, r2/r4 einen Schritt der schnellen Fourier- Transformation für eine Zeitverminderung vom Typ Radix 2 oder Radix 4 darstellt, r4 einen Schritt der schnellen Fourier- Transformation für eine Zeitverminderung vom Typ Radix 4 darstellt, r einen durch die obigen Gleichungen (3) und (4) gekennzeichneten Regenrierungsschritt darstellt und fr4 einen kombinatorischen Schritt oder einen Endschritt der schnellen Fourier-Transformation für eine Zeitverminderung vom Typ Radix 4 darstellt.
Wie zum Beispiel aus dem oben genannten Buch bekannt ist, umfaßt ein Umkehralgorithmus der schnellen Fourier-Transformierte einen anfänglichen Schritt der schnellen Fourier- Transformation für eine Frequenzverminderung, der ausgeführt werden muß, bevor die Folge von Umkehr-Rechenoperationen des Vorwärtsalgorithmus der schnellen Fourier-Transformation ausgeführt wird.
Somit könnte eine Folge von Rechenoperationen eines Umkehralgorithmus der schnellen Fourier-Transformation dargestellt werden als:
worin r2 einen anfänglichen Schritt der schnellen Fourier- Transformation für eine Frequenzverminderung vom Typ Radix 2 darstellt, r einen durch die Umkehrgleichungen (1) und (2) von (3) und (4) gekennzeichneten Regenerierungsschritt darstellt, r2/r4 und r4 wieder die oben genannten jeweiligen Schritte der schnellen Fourier-Transformation für eine Zeitverminderung mit Radix 2 oder Radix 4 und der schnellen Fourier-Transformation für eine Zeitverminderung mit Radix 4 darstellen.
Der obige Schritt der schnellen Fourier-Transformation für eine Frequenzverminderung und die Schritte der schnellen Fourier-Transformation für eine Zeitverminderung umfassen eine Multiplikation und eine Additions/Subtraktions-Operation. Jedoch beginnt ein Schritt der schnellen Fourier-Transformation für eine Zeitverminderung mit einer Multiplikation, gefolgt von einer Additions/Subtraktions-Operation, während für einen Schritt der schnellen Fourier-Transformation für eine Frequenzverminderung diese Folge umgekehrt ist. Daher kann die obige Recheneinheit AU, die für Schritte der schnellen Fourier-Transformation für eine Zeitverminderung optimiert ist, auch für Schritte der schnellen Fourier-Transformation für eine Frequenzverminderung verwendet werden, indem die Auswahlmittel auf geeignete Weise gesteuert werden. Tatsächlich kann die Folge von Rechenoperationen eines Umkehralgorithmus der schnellen Fourier-Transformation umgeschrieben werden:
worin x1 eine Multiplikation mit Faktor 1 darstellt und somit addiert werden könnte, im einen anfänglichen Addier/Subtrahier-Schritt für Berechnungen von inversen schnellen Fourier- Transformierten darstellt und sp einen speziellen Umkehrschritt für Berechnungen von inversen schnellen Fourier- Transformierten darstellt. Wie zu sehen ist, sind sowohl die Folgen von Rechenoperationen eines einfachen als auch eines Umkehralgorithmus der schnellen Fourier-Transformation bis auf die anfänglichen Schritte gleich.
Um einen anfänglichen Addier/Subtrahier-Schritt für Berechnungen von inversen schnellen Fourier-Transformierten auszuführen, werden die Daten r und s, die die reellen und imaginären Teile der gespeicherten komplexen Datenelemente X(i) darstellen, von M1 und M2 mit einem Faktor 1 multipliziert.
Außerdem werden die Daten an AS1 gegeben, die die Additions/Subtraktions-Operation des obigen anfänglichen Schrittes der schnellen Fourier-Transformation für eine Frequenzverminderung ausführt.
Die Ausgangsergebnisse von AS1 werden an die Ausgangsschaltung OC gegeben, indem S2 und S2' aktiviert werden, während die anderen Auswahlmittel deaktiviert werden.
Um einen speziellen Umkehrschritt für Berechnungen von inversen schnellen Fourier-Transformierten auszuführen, multiplizieren M1 und M2 die Daten r und s mit komplexen Koeffizienten w und z, die von CT aus den gespeicherten komplexen Koeffizienten cr und ci erzeugt werden. Ferner werden die Daten nicht durch AS1 geführt, weil die Multiplexer mx5 und mx6 unter Kontrolle von CoM ihre jeweiligen Eingänge i2 und i2' mit ST verbinden.
Der Multiplexer mx7 gibt die in ST gespeicherten Datenelemente in Paaren an AS2. Die letztere führt die Additions/Subtraktions-Operation des Regenerierungsschrittes r in der obigen Folge von Rechenoperationen für Berechnungen von inversen schnellen Fourier-Transformationen aus.
CoM ermöglicht, daß mx5 und mx6 ihre Eingänge i2 und i2' auswählen, aktiviert S3 und S3' und deaktiviert alle anderen Auswahleinrichtungen.
Die Ausgangsdaten O werden in DMM gespeichert und können als Eingangsdatenfolge für nachfolgende Schritte für eine Zeitverminderung mit Radix 2 oder Radix 4 verwendet werden.
Es wird bemerkt, daß AU auch eine komplexe Multiplikation ausführen könnte. In der Tat können die Ausgangsergebnisse von M1 und M2 sofort an die Ausgangsschaltung OC gegeben werden, indem S1 und S1' aktiviert und S2, S2', S3 und S3' deaktiviert werden. Die Ausgangsergebnisse O werden wieder in DMM gespeichert. Auf diese Weise wird ermöglicht, daß AU auch eine digitale Filteroperation oder Fensteroperation ausführt.
Schließlich werden im Falle einer komplexen Eingangsdatenfolge x(i) die Zwischenergebnisse Y(i) transparent durch die Datenregenerierungschaltung RC und die kombinatorische Einrichtung cm von Fig. 1 geführt, weil sie sofort die Ausgangsfolge X(i) von schnellen Fourier-Transformierten darstellen. Somit können für eine komplexe Eingangsdatenfolge x(i) die Funktionsblöcke AM, RC und CM von Fig. 1 durch einen einzigen Block ersetzt werden, in welchem Schritte der schnellen Fourier- Transformation mit Radix 2 und Radix 4 kombiniert werden, um X(i) zu erzeugen.
Es ist zu bemerken, daß im Falle einer sogenannten Berechnung von schnellen Fourier-Transformierten an der Verwendungsstelle, die Speicher DMM und MM von Fig. 1 einen einzigen Speicher bilden können.
Eine einfache Modifikation des in Fig. 2 gezeigten Diagramms ermöglicht es jedoch, daß die Recheneinheit AU ihre Eingangsdatenfolge y(i) nicht überschreibt. Daher sollte ein zusätzlicher Speicher, z. B. ein ergänzender RAM, mit der Recheneinheit verbunden sein. Dieser ergänzende RAM wird in Fig. 2 von DMM gebildet.
Zusammenfassend erzeugt die Recheneinheit AU abhängig von den Steuersignalen von der Steuereinrichtung CoM entweder die Zwischenreihe Y(i) von schnellen Fourier-Transformierten, die einzelnen Reihen A(i) und B(i) von schnellen Fourier-Transformierten eines Regenerierungsschrittes oder die Ausgangsreihe X(i) von einfachen oder inversen schnellen Fourier- Transformierten.

Claims

1. Prozessor (P) für schnelle Fourier-Transformation, welcher beinhaltet:

a. Speichermittel (mm) zum Speichern einer Eingangsdatenfolge (x (i));

b. Verschlüsselungsmittel (SM) zum Verschlüsseln der Eingangsdatenfolge (x(i)), wodurch eine Mehrzahl von verschlüsselten Daten-Unterfolgen (a(i), b(i)) erzeugt wird, eine erste verschlüsselte Daten-Unterfolge (a(i)), die ungeradzahlige Eingangsdatenelemente (x(2i+1)) enthält, und eine zweite verschlüsselte Daten-Unterfolge (b(i)), die geradzahlige Eingangsdatenelemente (x(2i)) enthält;

c. eine Recheneinheit (AU), die an die Verschlüsselungsmittel (SM) gekoppelt und dafür ausgelegt ist, eine Ausgangsfolge (X(i)) von schnellen Fourier-Transformierten der Eingangsdatenfolge (x(i)) aus den verschlüsselten Daten-Unterfolgen (a(i), b(i)) zu erzeugen, wobei die Recheneinheit (AU) dazu beinhaltet:

c1. Rechenmittel (AM), die dafür ausgelegt sind, Schritte der schnellen Fourier-Transformation für eine Zeitverminderung auf einer komplexen Datenfolge (y(i)) rekursiv auszuführen, wodurch eine Zwischenreihe (Y(i)) von schnellen Fourier- Transformierten erzeugt wird,

dadurch gekennzeichnet, daß

der Prozessor (P) zur Verarbeitung einer reellen Eingangsdatenfolge (x(i)) zusätzlich beinhaltet:

d. eine Datenerzeugungsschaltung (GC), die zwischen den Verschlüsselungsmitteln (SM) und der Recheneinheit (AU) angeschlossen und dafür ausgelegt ist, aus den verschlüsselten Daten- Unterfolgen (a(i), b(i)) die komplexe Datenfolge (y(i)) herzuleiten, die einen reellen und einen imaginären Teil gleich den jeweiligen des Paares von verschlüsselten Daten-Unterfolgen (a(i), b(i)) aufweist; und daß die Recheneinheit (AU) ferner beinhaltet:

c2. eine Datenregenerierungsschaltung (RC), die dafür ausgelegt ist, aus der Zwischenreihe (Y(i)) von schnellen Fourier-Transformierten einzelne Reihen (A(i), B(i)) von schnellen Fourier- Transformierten des Paares verschlüsselter Daten- Unterfolgen (a(i), b(i)) entsprechend den Formeln 2A(i) = Y(i) + Y(2N-i)cc und 2B(i) = jY(i) - j Y(2N-i)cc zu erzeugen, worin A(i) und B(i) die einzelnen Reihen von schnellen Fourier- Transformierten sind; Y(i) die Zwischenreihe von schnellen Fourier-Transformierten ist; 2N die Länge von Y(i) ist; Y(2N-i)cc die komplex konjugierte Zahl von Y(2N-i) ist;

c3. kombinatorische Mittel (cm), die dafür ausgelegt sind, einen Endschritt der schnellen Fourier- Transformation für eine Zeitverminderung auf den einzelnen Reihen (A(i), B(i)) von schnellen Fourier-Transformierten auszuführen, um dadurch die Ausgangsfolge (X(i)) von schnellen Fourier- Transformierten zu liefern;

c4. eine Steuereinheit (CoM), die dafür ausgelegt ist, die Recheneinheit (AU) selektiv in die Rechenmittel (AM), die Regenerierungsschaltung (RC) und die kombinatorischen Mittel (cm) umzuwandeln; und

c5. einen Datenspeicher (DMM), um nacheinander die komplexe Datenfolge (y(i)) zu speichern, die Zwischenreihe (Y(i)) von schnellen Fourier- Transformierten zu speichern, die einzelnen Reihen (A(i), B(i)) von schnellen Fourier- Transformierten zu speichern und die Ausgangsfolge (X(i)) von schnellen Fourier- Transformierten zu speichern

und worin die Recheneinheit (AU) erste Registermittel (u1, u2, v1, v2, w1, w2, z1, z2), die dafür ausgelegt sind, reelle und imaginäre Teile von Datenelementen (u, v) der Eingangsdaten und für Berechnungen von schnellen Fourier-Transformierten charakteristische Wichtungskoeffizienten (w, z) vorübergehend zu speichern, zweite Registermittel (r1, r2, r3, r4), die an die ersten Registermittel (u1, u2, v1, v2, w1, w2, z1, z2) gekoppelt und dafür ausgelegt sind, Daten vorübergehend zu speichern, Multiplikatormittel (M1, M2), die dafür ausgelegt sind, in den zweiten Registermitteln (r1, r2, r3, r4) gespeicherte Daten zu multiplizieren, eine erste Addier/Subtrahier- Einrichtung (AS1), die an die Multiplikatormittel (M1, M2) gekoppelt und dafür ausgelegt ist, Ausgangsprodukte der Multiplikatormittel (M1, M2) zu addieren/subtrahieren, eine Schiebeschaltung (SC), die dafür ausgelegt ist, ihr zugeführte Zwischenergebnisse hin- und herzuschieben und vorübergehend zu speichern, eine zweite Addier/Subtrahier-Einrichtung (AS2), auf deren Eingänge die Zwischenergebnisse gegeben werden, eine Ausgangsschaltung (OC), die an den Datenspeicher (DMM) gekoppelt ist und die Kaskadenschaltung einer Ordnungseinrichtung (OM) und eine Skaliereinrichtung (ScL) umfaßt, um ihr zugeführte Daten anzuordnen und zu skalieren und sie im Datenspeicher (DMM) zu speichern, und Auswahlmittel (S1, S1', S2, S2', S3, S3', mx5, mx6) beinhaltet, die von der Steuereinheit (CoM) gesteuert werden, um die Umwandlung der Recheneinheit (AU) selektiv auszuführen.

2. Prozessor (P) für schnelle Fourier-Transformation nach Anspruch 1, dadurch gekennzeichnet, daß die Auswahlmittel (S1, S1', S2, S2', S3, S3', mx5, mx6) unter Kontrolle der Steuereinheit (CoM) dafür ausgelegt sind, die Recheneinheit (AU) in die Rechenmittel (AM) umzuwandeln, indem die zweiten Registermittel (r1, r2, r3, r4) über die Kaskadenschaltung der Multiplikatormittel (M1, M2) und die erste Addier/Subtrahier-Einrichtung (AS1), wenn der Schritt der schnellen Fourier-Transformation für eine Zeitverminderung vom Typ mit Radix 2 ist, und über die Kaskadenschaltung der Multiplikatormittel (M1, M2), die erste Addier/Subtrahier-Einrichtung (AS1), die Schiebeschaltung (SC) und die zweite Addier/Subtrahier-Einrichtung (AS2), wenn der Schritt der schnellen Fourier-Transformation für eine Zeitverminderung vom Typ mit Radix 4 ist, an die Ausgangsschaltung (OC) gekoppelt werden.

3. Prozessor (P) für schnelle Fourier-Transformation nach Anspruch 1, dadurch gekennzeichnet, daß die Auswahlmittel (S1, S1', S2, S2', S3, S3', mx5, mx6) unter Kontrolle der Steuereinheit (CoM) dafür ausgelegt sind, die Recheneinheit (AU) in die Regenerierungsschaltung (RC) umzuwandeln, indem ein Eingangsdaten speichernder Teil (u1, v1) der ersten Registermittel (u1, u2, v1, v2, w1, w2, z1, z2) über die Kaskadenschaltung der Schiebeschaltung (SC) und die zweite Addier/Subtrahier-Einrichtung (AS2) an die Ausgangsschaltung (OC) gekoppelt wird.

4. Prozessor (P) für schnelle Fourier-Transformation nach Anspruch 1, dadurch gekennzeichnet, daß die Auswahlmittel (S1, S1', S2, S2', S3, S3', mx5, mx6) unter Kontrolle der Steuereinheit (CoM) dafür ausgelegt sind, die Recheneinheit (AU) in die kombinatorischen Mittel (CM) umzuwandeln, indem die zweiten Registermittel (r1, r2, r3, r4) über die Kaskadenschaltung der Multiplikatormittel (M1, M2), die erste Addier/Subtrahier-Einrichtung (AS1), die Schiebeschaltung (SC) und die zweite Addier/Subtrahier-Einrichtung (AS2) an die Ausgangsschaltung (OC) gekoppelt werden, um den Endschritt der schnellen Fourier-Transformation für eine Zeitverminderung vom Typ mit Radix 4 auszuführen.

5. Prozessor (P) für schnelle Fourier-Transformation nach Anspruch 1, dadurch gekennzeichnet, daß die Recheneinheit (AU) darüber hinaus Speichermittel (CSM) für Wichtungskoeffizienten, die die Wichtungskoeffizienten speichern, eine Datenverarbeitungsschaltung (DT), die an den Datenspeicher (DMM) gekoppelt und dafür ausgelegt ist, die reellen (r) und imaginären (s) Teile der Datenelemente der Eingangsdaten zu überlagern, und eine Verarbeitungsschaltung (CT) für Wichtungskoeffizienten beinhaltet, die an die Speichermittel (CSM) für Wichtungskoeffizienten gekoppelt und dafür ausgelegt ist, reelle (cr) und imaginäre (ci) Teile der in den Speichermitteln (CSM) gespeicherten Wichtungskoeffizienten zu überlagern und zu invertieren.

6. Prozessor (P) für schnelle Fourier-Transformation nach Anspruch 1, dadurch gekennzeichnet, daß die Auswahlmittel (S1, S1', S2, S2', S3, S3', mx5, mx6) unter Kontrolle der Steuereinrichtung (CoM) dafür ausgelegt sind, die Recheneinheit (AU) in einen Zustand zu bringen, in dem sie dafür ausgelegt ist, einen anfänglichen Addier/Subtrahier-Schritt für Berechnungen von inversen schnellen Fourier- Transformierten auszuführen, indem die zweiten Registermittel (r1, r2, r3, r4) über die Kaskadenschaltung der Multiplikatormittel (M1, M2), die eine Multiplikation mit Faktor 1 ausführen, und die erste Addier/ Subtrahier-Einrichtung (AS1) an die Ausgangsschaltung (OC) gekoppelt werden, und daß die Auswahlmittel (S1, S1', S2, S2', S3, S3', mx5, mx6) unter Kontrolle der Steuereinrichtung (CoM) dafür ausgelegt sind, die Rechenschaltung (AU) in einen weiteren Zustand zu bringen, in dem sie dafür ausgelegt ist, einen speziellen inversen Schritt für Berechnungen von inversen schnellen Fourier- Transformierten auszuführen, indem die zweiten Registermittel (r1, r2, r3, r4) über die Kaskadenschaltung der Multiplikatormittel (M1, M2), die Schiebeschaltung (SC) und die zweite Addier/Subtrahier-Einrichtung (AS2) an die Ausgangsschaltung (OC) gekoppelt werden, und daß die Auswahlmittel (S1, S1', S2, S2', S3, S3', mx5, mx6) dafür ausgelegt sind, die Recheneinheit (AU) in einen weiteren Zustand zu bringen, in dem sie dafür ausgelegt ist, eine komplexe Multiplikation auszuführen, indem die zweiten Registermittel (r1, r2, r3, r4) über die Multiplikatormittel (M1, M2) an die Ausgangsschaltung (OC) gekoppelt werden.