DE3416536C2 - - Google Patents

Description

Die Erfindung betrifft eine Schaltung zum Durchführen einer schnellen Fourier-Transformation gemäß dem Oberbegriff des Anspruchs 1 sowie eine solche Schaltung gemäß dem Oberbegriff des Anspruchs 5.

Es ist bekannt, daß das Frequenzspektrum einer analogen Signalwellenform dadurch erzeugt wird, daß eine Fourier- Transformation bei der analogen Signalwellenform durchgeführt wird und deshalb eine Frequenzanalyse und ähnliches eines analogen Signals erreichbar sind, indem eine solche Fourier-Transformation und eine inverse Fourier- Transformation unter Verwendung eines elektronischen Rechners durchgeführt werden. Es ist ebenfalls bekannt, daß ein Signal dadurch gefiltert werden kann, daß das Ergebnis der Fourier-Transformation mit der Übertragungsfunktion eines Filters multipliziert und dann eine inverse Fourier-Transformation bei dem Produkt durchgeführt wird. Bisher benötigten die Fourier-Transformation und andere damit verbundene Rechnungen sehr viel Zeit, selbst bei Verwendung eines elektronischen Rechners. Seit Cooley und Tukey die schnelle Fourier-Transformation (FFT) 1965 angegeben haben, was eine sehr erhebliche Verbesserung in Bezug auf das der Fourier-Transformation zu eigene Zeitproblem darstellt, ist die FFT in hohem Maße auf verschiedenen Gebieten verwendet worden, wie für die Frequenzanalyse, das Erkennen und die Synthese von Sprachsignalen, digitales Filtern, Bilddaten-Verarbeitung, medizinische Tomographie und optische Messungen.

Die FFT ist in zahlreichen Schriften behandelt worden, wie z. B. E.O. Brighan "Fast Fourier Transform", Prentice Hall, 1974, und diesbezügliche Einzelheiten werden hier nicht beschrieben. Kurz gesagt, wurde FFT erarbeitet, um die übergroße Wiederholung der gleichen Multiplikation in den folgenden Gleichungen zu verhindern, welche die diskrete Fourier-Transformation (DFT) und die inverse diskrete Fourier-Transformation (IDFT) definieren:

mit W = exp ((-j 2π )/N) (3)

und N ist die Anzahl der Daten.

Dies bedeutet, daß die schnelle Fourier-Transformation ein Algorithmus ist, um eine diskrete Fourier-Transformation einer langen Reihe durchzuführen, indem diese in kurze Blöcke unterteilt wird, um die Anzahl der Multiplikationen zu verringern und damit auch die Rechenzeit. In den Gleichungen (1) und (2) bedeuten x _p eine Abtastwertfolge der Zeitfunktion und X _k eine Abtastwertfolge des Frequenzspektrums, und p und k sind ganze Zahlen innerhalb des Bereichs von 0 bis N - 1. Einsetzen von s für pk in die Gleichungen (1) bis (3) ergibt für W ^pk :

W ^pk = W ^s

= cos ((2π s)/N) - jsin ((2f s)/N) (4)

In der Gleichung (4) ist W ^s eine Variable, die im allgemeinen als Phasenfaktor (phase rotation factor) bezeichnet wird.

Um die Gleichung (1) direkt auszurechnen, sind, da W eine komplexe Zahl ist, und sich p und k innerhalb des Bereiches von 0 bis N - 1 ändern, N² Mul­ tiplikationen von komplexen Zahlen und N(N - 1) Additionen komplexer Zahlen erforderlich. Soweit es andererseits die schnelle Fourier-Transformation betrifft, benötigt sie eine Anzahl von Multiplikationen, die gleich dem Produkt von N/2, was der der Hälfte der Anzahl der Daten N einer Eingabe­ datenreihe ist, und log₂ N ist, was gleich der Anzahl Stufen (Anzahl von Rechenreihen) ist, und die Anzahl von Additionen komplexer Zahlen beträgt das Doppelte der Anzahl von Multiplikationen. Wenn man annimmt, daß die Rechenzeit proportional der Multi­ plikationshäufigkeit ist, ist die schnelle Fourier- Transformation wesentlich kürzer bezüglich der Rechenzeit als eine direkte Berechnung.

Wie vorhergehend erörtert, ist die schnelle Fourier- Transformation tatsächlich wirkungsvoll, um eine beträchtliche Verringerung der Rechenzeit zu erhalten. Nichtsdestotrotz haben sich Schwierigkeiten dahingehend ergeben, die Rechenzeit bei der schnellen Fourier-Transformation soweit zu verringern, daß bei der Betrachtung mit dem menschlichen Auge die gerade durch die schnelle Fourier- Transformation erzeugten Daten mit Realzeitbasis als ein Bild auf einem Schirm erscheinen.

Aus der GB-A-20 06 485 sind Schaltungen zum Durchführen einer schnellen Fourier-Transformation bekannt, die die Merkmale der Oberbegriffe der Ansprüche 1 und 5 aufweisen. In dieser Druckschrift ist eine Einrichtung zum Analysieren eines Spektrums mittels einer schnellen Fourier-Transformation (FFT) beschrieben, die eine erste Speichereinrichtung zur Aufnahme einer ersten Reihe von Ein­ gangssignalen, eine zweite Speichereinrichtung, in der Gewichtsfaktoren gespeichert sind, eine arithmetische Verarbei­ tungseinrichtung und Steuermittel aufweist, um die Signale und Gewichtskoeffizienten der arithmetischen Verarbeitungs­ einrichtung zuzuführen. Diese berechnet mittels eines Verfahrens aufeinanderfolgender Einfügung Koeffizienten, durch die die Reihen von Eingangssignalen als eine Summe von Frequenzkomponenten mit gleich­ beabstandeten Frequenzen ausgedrückt werden können. Die von der Steuereinrichtung angewandten Gewichtskoeffizienten sind derart, daß die Frequenzen der Frequenz­ komponenten gegenüber ganzzahligen Vielfachen des Frequenzabstands um ein Viertel des Frequenzabstands verschoben werden.

Der Erfindung liegt die Aufgabe zugrunde, eine Schaltung zum Durchführen einer schnellen Fourier-Transformation gemäß dem Oberbegriff des Anspruchs 1 bzw. des Anspruchs 5 derart weiterzubilden, daß eine Fourier-Transformation in kürzerer Zeit durchgeführt werden kann.

Diese Aufgabe wird erfindungsgemäß durch die Merkmale des Anspruchs 1 bzw. des Anspruchs 5 gelöst.

Die erfindungsgemäßen Schaltungen zum Durchführen einer schnellen Fourier-Transformation zeichnen sich durch eine schnellere und auch einfachere Transformationsberechnung gegenüber den bekannten Schaltungen aus. Ein besonderes Merkmal der Erfindung besteht darin, daß sich für spezielle Werte von W durch Überbrücken der Multiplikationsschaltungen mit Schaltern die Berechnung vereinfachen läßt.

Vorteilhafte Weiterbildungen des Erfin­ dungsgegenstands ergeben sich aus den Un­ teransprüchen.

Ausführungsbeispiele der Erfindung werden im folgenden unter Bezugnahme auf die Zeichnungen näher erläutert. Es zeigt

Fig. 1 ein beispielhaftes Flußdiagramm bei einer schnellen Fourier-Transformation,

Fig. 2 ein Diagramm zur Erläuterung der Schmetterlings-Berechnung,

Fig. 3 und 5 jeweils Beziehungen zwischen Variablen, Stufenzahlen und ganzzahligen Teilen,

Fig. 4 eine Beziehung zwischen dem Wert eines ganzzahligen Teils und einem Winkel des Phasenfaktors,

Fig. 6 ein Blockdiagramm einer Ausführungsform einer Schaltung zum Durchführen einer schnellen Fourier-Transformation nach der Erfindung,

Fig. 7 ein Kurvendiagramm der Multiplikations­ häufigkeit bei einer herkömmlichen Schaltung zum Durchführen einer schnellen Fourier- Transformation und bei einer nach der Erfindung,

Fig. 8 ein Blockdiagramm einer anderen Aus­ führungsform nach der Erfindung,

Fig. 9A bis 9D Diagramme, die verschiedene wesentliche Teile der in Fig. 8 dargestellten Schaltung zeigen,

Fig. 10A und 10B Darstellungen, die andere Ausgestaltungen der Fig. 9B und 9A zeigen, und

Fig. 11 eine graphische Darstellung der Multi­ plikationshäufigkeit bei einer herkömmlichen Schaltung zur Durchführung einer schnellen Fourier-Transformation und bei einer Schaltung nach der Erfindung zur Gegenüberstellung bezüglich der Abtastzahl.

Während die Schaltungen zur Durchführung einer schnellen Fourier- Transformation nach der Erfindung in einer Vielzahl von physikalischen Ausführungsformen in Abhängigkeit von der Umgebung und den Benutzererfordernissen realisiert werden können, ist eine beträchtliche Anzahl von hier gezeigten und beschriebenen Ausführungsformen hergestellt, überprüft und verwendet worden, und sie haben alle einen im höchsten Maße zufrieden­ stellenden Betrieb gezeigt.

Die Erfindung geht von der Überlegung aus, Schmetter­ lingsberechnungen wirkungsvoll dadurch durchzuführen, daß Eingabedaten in erste zwei Arten (Art I und Art II), die keine Multiplikation mit dem Phasenfaktor W ^s benötigen, der eine Variable in einem Flußdiagramm bei der schnellen Fourier-Transformation ist, und zweite zwei Arten (Art III und IV) unterteilt werden, bei denen diese er­ forderlich sind, und daß auf das periodische Erscheinen dieser Arten geachtet wird.

Unter Verwendung eines solchen Signalflußdiagrammes, wie es in Fig. 1 gezeigt ist, kann die für den schnellen Fourier-Transformation-Algorithmus erforderliche Berechnung einfach ausgedrückt werden. Fig. 1 ist ein Fluß­ diagramm, in der die Anzahl der Daten N bei der Abtast­ wertfolge xp der Zeitfunktion in Gleichung (1) 8 sein soll. Eine Datenreihe, die aus den Daten x₀ bis x₇ besteht, ist durch die ganz linke oder erste Knotenspalte in Fig. 1 dargestellt. Die zweite, dritte und vierte Knotenspalte wird hier als Stufe 1, 2 und 3 bezeichnet, obgleich sie üblicherweise Rechenspalten genannt werden. Bei dem Flußdiagramm münden zwei Linien in jeden Knoten in einer Rechenspalte (Stufe) ein und stellen Übertragungswege von den vor­ hergehenden Knoten dar. Ein Übertragungsweg überführt zu einem Knoten in einer gewissen Spalte einen numerischen Ausgangswert von einem Knoten in der unmittelbar vor­ hergehenden Spalte nach Multiplikation mit einem Phasenfaktor W ^s . Das heißt, wie in Fig. 2 gezeigt, wo 4 benachbarte Knoten der Fig. 1 dargestellt sind, daß ein Datenpaar A und B, welches den zwei Knoten eingegeben wurde, zu den folgenden Knoten als Daten C und D überführt wird, und in diesem Fall ergibt sich der Wert für C durch Berechnung A + BW ^s und der Wert für D durch Berechnung von A - BW ^s .

Die Ausgangsdaten ergeben sich zu

C = A + BW ^s (5)

D = A - BW ^s (6)

Diese Grundrechnungen werden als Schmetterlingsberechnungen bezeichnet, wie es auf diesem Gebiet allgemein bekannt ist. Die Schmetterlingsberechnungen schreiten der Reihe nach von Stufe 1, Stufe 2 und Stufe 3 fort.

Die Häufigkeit der Schmetterlingsberechnungen ist gleich dem Produkt aus N/2, was die Hälfte der Anzahl der Eingabedaten darstellt, und log₂N, was die Anzahl der Stufen (Anzahl von Rechenspalten) darstellt. Bei dem in Fig. 1 gezeigten Beispiel ergibt sich hierfür 12, da N gleich 8 ist. In Fig. 1 ist zu erkennen, daß es in jeder Stufe zwei Knoten gibt, in die Übertragungswege von dem gleichen einen Paar von Knoten in der vorhergehenden Stufe münden (solche zwei Knoten werden als ein duales Knotenpaar bezeichnet). Der Abstand zwischen zwei Knoten bei einem dualen Knotenpaar in einer Stufe 1 beträgt N/2¹. Es ist allgemein anerkannt, daß der Realteil und der Imaginärteil des Phasenfaktors bei einem Knoten und die entsprechenden bei dem anderen Knoten eines dualen Knotenpaars die gleichen Abso­ lutwerte aufweisen und sich nur im Vorzeichen unterscheiden und daß deshalb eine einzige Multiplikation zweier komplexer Zahlen ausreicht, um die Werte des dualen Knotenpaars zu erhalten.

Wenn ein gewisser Knoten betrachtet wird, so wird der Wert s des Phasenfaktors W ^s , mit dem Daten an einem Knoten eine Spalte davor zu multiplizieren sind, auf die folgende Weise erhalten.

Die Indizes 0 bis 7 der Daten x₀ bis x₇ werden nun als "Variable" bezeichnet und die entsprechenden Knoten in jeder Spalte werden in Größen der Variablen ausgedrückt und diese Variablen werden durch Binärzahlen der kleinsten Anzahl von Bits γ ausgedrückt, welche den maximalen Wert der Variablen angeben kann. Die Binärzahl wird nach rechts um eine Größe verschoben, die durch Subtraktion einer Stufenzahl 1 von γ erhalten wird, dann werden Nullen zu der linken Seite von ( γ - 1) Bits addiert, und daraufhin wird die Bitfolge der Binärzahl umgekehrt. Um den Wert s zu erhalten, ist es erforderlich, die q-Bit Binärzahl, die eine Variable angibt, ( γ - 1) Bits nach rechts zu verschieben. Um dies in einem Rechenvorgang durchzuführen, wie es allgemein bekannt ist, muß die Umkehrung der Bitfolge an einem ganzzahligen Teil (dieser wird im folgenden mit P bezeichnet) durchgeführt werden, der sich durch Division der Variablen (im folgenden mit n bezeichnet) durch (2 ^γ-1) ergibt. Infolgedessen ist bei dem in Fig. 1 gezeigten Beispiel der Wert s entweder 0, 2, 1 oder 3.

Die Beziehung zwischen den Variablen n, Stufen und ganzzahligen Teilen P, die vorhergehend beschrieben worden sind, kann dargestellt werden, wie es in Fig. 3 gezeigt ist, wobei das Beispiel gemäß Fig. 1 verwendet wurde. In Fig. 3 ist mit X ein Paar von zwei Knoten, die ein duales Knotenpaar bilden, bezeichnet, d. h. der Knoten, bei dem keine Multiplikation erforderlich ist. Der durch die Stufennummer P und eine Variable n dargestellte Wert gibt einen Wert des ganzzahligen Teils P an. Wenn beispielsweise die Stufennummer 1 und die Variable eine der Zahlen 0 bis 3 ist, beträgt der ganzzahlige Anteil P 0, weil l gleich 1, γ gleich 3 und n einer der Werte 0 bis 3 ist.

Wenn die Stufenzahl 2 und die Variable n 4 oder 5 beträgt, ergibt sich für den ganzzahligen Anteil P 2, da l gleich 2, γ gleich 3 und n 4 oder 5 ist.

Fig. 4 zeigt die Beziehung zwischen den Werten des ganzzahligen Anteils P und den Winkeln R des Phasenfaktors W ^s (wobei R gleich 2π s/N in Gleichung (4) ist). Im Fall der Fig. 1 beträgt der ganzzahlige Anteil P 0, 2, 4 oder 6, wie es sich auch aus Fig. 3 ergibt. Wenn P gleich 0 ist, ist R 0°; wenn P gleich 2 ist, ist R₂ gleich 90°; wenn P gleich 4 ist, ist R₄ gleich 45°; und wenn P gleich 6 ist, ist R₆ gleich 135°.

Wenn beispielsweise die Anzahl der Daten in der Eingabe­ datenspalte gleich 256 (= 2⁸) ist und das gleiche Prinzip gemäß Fig. 3 verwendet wird, kann die Beziehung zwischen der Anzahl der Variablen d. h. 256, der Anzahl von Stufen d. h. 8 = log₂ 256 und den Werten des ganzzahligen Teils P durch das in Fig. 5 gezeigte Diagramm dargestellt werden. In Fig. 5 kann die ganze Zahl P irgendeine gerade Zahl, die nicht kleiner als 8 und nicht größer als 254 ist, zusätzlich zu den vorhergehend erwähnten Werten 0, 2, 4 und 6 sein. Wenn der ganzzahlige Teil P gleich 8, 10, 12 oder 14 ist, ergibt sich für den Winkel R ein solcher, der in Fig. 4 durch eine Gerade O und eine Gerade 8, 10, 12 oder 14 eingeschlossen ist.

Es wird nun angenommen, daß die Eingabedaten A und B die in Fig. 2 dargestellt sind, ausgedrückt werden durch:

A = Ar + jAi (7)

B = Br + jBi

dann folgt aus Gleichungen (4)-(7)

Aus der Gleichung (8) folgt, daß zwei Multiplikationen erforderlich sind, um Tr zu erhalten, und zwei Multiplikationen erforderlich sind, um Ti zu erhalten. Infolgedessen sind vier Berechnungen erforderlich, um C (dies gilt auch für D) zu erhalten. Man sieht, daß Tr und Ti in einem Speicher gespeichert werden können, wenn C berechnet wird, um auszuschließen, daß diese Werte erneut berechnet werden, wenn D berechnet werden soll.

Aus Fig. 4 ergibt sich, daß, wenn der ganzzahlige Anteil P gleich Null ist, der Winkel R 0° beträgt und cos R = 1 und sin R = 0 ist, so daß sich aus der Gleichung (4) für W ^s 1 ergibt. Deshalb folgt aus den Gleichungen (8) und (9), daß gilt C = A + B und D = A - B, was zur Folge hat, daß C und D durch einfache Schmetterlingsberechnungen berechnet werden können, die lediglich Addition und Subtraktion umfassen. Ferner gilt bezüglich der Schmetter­ lingsberechnungen in der Stufe 1, daß die gesamten Eingabedaten reelle Zahlen und nicht imaginäre sind, so daß, wenn der ganzzahlige Anteil P gleich Null ist, gilt Ai = Bi = 0 in Gleichung (7) und infolgedessen ist C gleich Ar + Br und D gleich Ar - Br. Das Rechnen mit Realteilen hat als Ausgabewerte wiederum reelle Zahlen zur Folge. Deshalb bestehen, wenn der ganzzahlige Anteil P gleich Null ist, sowohl die Eingabedaten als auch der Phasenfaktor, die einer Schmetterlingsberechnung unterzogen werden sollen, nur aus reellen Zahlen, selbst in der Stufe 2 und den folgenden, wodurch die Berechnung von Imaginärteilen ausgeschlossen wird. Wenn der ganzzahlige Anteil P gleich 2 ist, beträgt der Winkel R gleich 90° und deshalb ergibt sich für W ^s gleich - j. Auch in diesem Fall können C und D lediglich durch Addition und Subtraktion berechnet werden, obgleich ein Realteil und ein Imaginärteil in den Ausgabedaten vorliegen.

Wenn der ganzzahlige Anteil P gleich 4 oder größer ist, werden Schmetterlingsberechnungen mit 4 Multiplikationen gemäß den Gleichungen (8) und (9) durchgeführt.

Bei einer ersten Ausführungsform der Erfindung ist besonders darauf geachtet, daß eine Multiplikation mit W ^s für die Art I, bei der der ganzzahlige Anteil P gleich Null ist, und für die Art II bei der P gleich 2 ist, nicht erforderlich ist, und daß eine viermalige Multiplikation wie beim Stand der Technik für die anderen Arten, bei denen P gleich 4 oder größer ist, und die Art 4, bei der P gleich 8 oder größer ist, durchgeführt werden muß. Somit werden die Arten I und II von den anderen Arten unterschieden. Für die Arten I und II wird ein Schalter betätigt, so daß nur die erforderliche Addition und Subtraktion mit Daten von der Eingabeseite einer Multiplikationseinrichtung durchgeführt wird, während für die anderen Arten die erforderlichen Schmetterlings­ berechnungen durchgeführt werden können. Ein solches Vorgehen, welches eine Besonderheit der Erfindung darstellt, ermöglicht, daß Schmetterlingsberechnungen mit einer geringeren Häufigkeit von Multiplikationen als bei dem schnellen Fourier-Transformationsverfahren nach dem Stand der Technik durchgeführt werden.

Es wird auf die Fig. 6 bezug genommen, die eine Schaltung nach der Erfindung als Blockdiagramm zeigt. In Fig. 6 werden Eingabeklemmen 10 bzw. 12 Daten Ar, die die Realteile von ersten Daten A darstellen, und Daten Ai zugeführt, die die Imaginärteile der gleichen Daten A darstellen. Die Eingangsklemmen 14 bzw. 16 erhalten Daten Br, die die Realteile zweiter Eingabedaten B darstellen, und Daten Bi, die die Imaginärteile der gleichen Daten B darstellen. Die Daten Ar, Ai, Br und Bi werden einzeln aus einem Speicher 18 ausgelesen, dessen Kapazität größer ist, als diejenige die zum Speichern der gleichen Anzahl von reellen Zahlen, der Anzahl von Daten N und von "N" imaginären Daten ausreicht.

Die Daten Ar werden einer Addier-Subtraktions-Schaltung 20 (genaugenommen einer Addiereinrichtung) und einer Addier-Subtraktions-Schaltung 22 zugeführt, während die Daten Ai an Addier-Subtraktions-Schaltungen 24 und 26 gegeben werden. Die Daten Br werden Multiplikationsschaltungen 28 und 30 zugeführt, damit sie mit dem Imaginärteil sin R und dem Realteil cos R eines Phasenfaktors W ^s multipliziert werden, welche aus einem Koeffizientenspeicher 32 ausgelesen werden. Die von den Multiplikationsschaltungen 28 und 30 ausgegebenen Produkte werden Kontakten 34 a und 36 a von Schaltern 34 bzw. 36 zugeführt. Der Schalter 34 hat drei Kontakte 34 a bis 34 c und der Schalter 36 drei Kontakte 36 a bis 36 c. Den Kontakten 34 b und 36 b werden gemeinsam die Realteile Br zugeführt; die Kontakte 34 c und 36 c liegen auf Masse.

Währenddessen werden die Imaginärteile Bi den Multipli­ kationsschaltungen 38 und 40 zugeführt, damit sie mit dem Imaginärteil sin R und dem Realteil cos R des Phasenfaktors W ^s multipliziert werden. Die Ausgänge der Multi­ plikationsschaltungen 38 und 40 werden Kontakten 42 a und 44 a der Schalter 42 bzw. 44 zugeführt. Der Schalter 42 ebenso wie die Schalter 34 oder 36 weist drei Kontakte 42 a bis 42 c auf und der Schalter 44 besitzt Kontakte 44 a bis 44 c. Den Kontakten 42 b und 44 b werden die Daten Bi unmittelbar von der Eingabeklemme 16 zugeführt; die Kontakte 42 c und 44 c liegen auf Masse. Die Schalter 34, 36, 42 und 44 werden unabhängig voneinander durch Schaltimpulse gesteuert, die von einem Schaltimpulsgenerator (dieser ist nicht dargestellt) abgegeben werden.

Die Addier-Subtraktions-Schaltung 20 summiert den Realteil von der Eingangsklemme 10 und die Daten von den Schaltern 36 und 42, wobei Realteile Cr (= Ar + Br · cos R + Bi · sin R ) der ersten Ausgabedaten C erzeugt werden. Die Daten Cr werden an einen Ausgangsanschluß 46 gegeben. Die Addier-Subtraktions-Schaltung 24 summiert die Imaginärteile Ai von der Eingangsklemme 12 und Daten von dem Schalter 44, während Daten von dem Schalter 34 subtrahiert werden, wodurch Imaginärteile Ci (= Ai + Bi · cos R - Br · sin d R ) der ersten Ausgangsdaten C erzeugt werden. Die Werte Ci werden an einen Ausgangsanschluß 48 gegeben. Die Addier-Subtraktions-Schaltung 22 subtrahiert die Ausgangswerte der Schalter 36 und 42 von dem Realteil Ar, wobei reelle Zahlen Dr der zweiten Ausgangsdaten D erzeugt werden. Die Zahlen Dr werden an einen Ausgangsanschluß 50 gegeben. Ferner summiert die Addier-Subtraktions-Schaltung 26 den Imaginärteil Ai und den Ausgangswert des Schalters 34, während der Ausgangswert des Schalters 44 subtrahiert wird, wodurch ein Imaginärteil Di (= Ai - Bi cos R + Br sin d R ) erzeugt wird. Der Wert Di wird an eine Ausgangsklemme 52 gegeben.

Die Schaltung mit der vorhergehend genannten Ausgestaltung arbeitet in folgender Weise. Es sei angenommen, daß beispielsweise in dem Speicher 18 in der ersten bis achten Adresse die reellen Zahlen gespeichert sind, die den acht Daten x₀ bis x₇ (in diesem Fall mit N = 8) zugeordnet sind. Wenn N = 8, werden in der Stufe 1 nur die Schmetterlingsberechnungen mit einem ganzzahligen Anteil P von 0 nacheinander bei Daten mit den Variablen 0 und 4, mit den Variablen 1 und 5, mit den Variablen 2 und 6 und mit den Variablen 3 und 7 durchgeführt. Dann werden die Schalter 36 und 44 mit den Kontakten 36 b bzw. 44 b verbunden, während die Schalter 34 und 42 mit den Kontakten 34 c bzw. 42 c verbunden werden. Als Ergebnis hiervon liefert der Schalter 36 die an die Eingabeklemme 14 gegebenen Realteile Br unmittelbar ohne Multiplikation und der Schalter 44 liefert die Imaginärteile Bi, die an die Eingabeklemme 16 gelegt werden, direkt ohne Multiplikation. Währenddessen wird von dem Schalter 36 oder 42 kein Ausgangssignal abgegeben.

Bei der vorhergenannten Bedingung erscheinen Daten, die durch Ar + Br dargestellt sind, an der Ausgangsklemme 46, Daten Ai + Bi erscheinen an der Ausgangsklemme 48, Daten Ar - Br treten an der Ausgangsklemme 50 auf und Daten Ai - Bi erscheinen an der Ausgangsklemme 52. Zu diesem Zeitpunkt werden der Stufe 1 nur reelle Zahlen von dem Speicher 18 den Eingangsklemmen 10 und 14 zugeführt, während keine Imaginärteile den Eingabeklemmen 12 und 16 zugeführt werden. Als Ergebnis hiervon werden nur reelle Werte von den Ausgangsklemmen 46 und 50 abgegriffen und in die erste bis achte Adresse des Speichers 18 als den Variablen 0 bis 7 zugeordnete Daten eingeschrieben.

Als nächstes werden die ersten Schmetterlingsberechnungen in der Stufe 2 durchgeführt. Wie in den Fig. 1 und 3 zu erkennen ist, wird eine erste Schmetterlingsberechnung mit einem ganzzahligen Anteil P von 0 bei den Daten mit den Variablen 0 und 2 und bei den Daten mit den Variablen 1 und 3 und dann eine zweite Schmetterlingsberechnung mit einem ganzzahligen Anteil P von 2 bei Daten mit den Variablen 4 und 6 und bei Daten mit den Variablen 5 und 7 durchgeführt. Im Laufe der ersten Schmetterlingsberechnung bei der P gleich 0 ist, sind die Schalter 36 und 44 mit den Kontakten 36 c bzw. 44 c in der gleichen Weise wie bei der Stufe 1 verbunden, während die Schalter 34 und 42 mit den Kontakten 34 c bzw. 42 c verbunden sind. Während der zweiten Schmetterlingsberechnung, bei der P gleich 2 ist, sind die Schalter 36 und 44 mit den Kontakten 36 b bzw. 44 b und die Schalter 34 und 42 mit den Kontakten 34 b bzw. 42 b verbunden.

Mit dem vorgenannten Vorgehen werden an der ersten und dritten Adresse des Speichers 18, von dem den Variablen 0 und 2 zugeordnete Daten ausgelesen worden sind, Realteile Cr und Dr eingeschrieben, die durch die Schmetter­ lingsberechnungen der obigen Daten erzeugt und an den Ausgangsklemmen 46 und 50 abgenommen worden sind. Auch werden an der zweiten und vierten Adresse des Speichers 18, von dem den Variablen 1 und 3 zugeordnete Daten ausgelesen worden sind, die Realteile Cr und Dr eingeschrieben, die durch Schmetterlingsberechnungen der obigen Daten erzeugt und an den Ausgangsklemmen 46 und 50 abgenommen worden sind.

Bei der zweiten Schmetterlingsberechnungsperiode erscheint eine reelle Zahl Cr, die durch Ar ausgedrückt ist, an der Ausgangsklemme 46 und wird in die Adresse des Speichers 18 eingeschrieben, von dem eine den Variablen 4 oder 5 zugeordnete Größe ausgelesen worden war. Die durch Ar ausgedrückte reelle Zahl Dr wird an der Ausgangsklemme 50 abgenommen und in die Adresse eingeschrieben, von der eine der Variablen 6 oder 7 zugeordnete Zahl ausgelesen worden war. Gleichzeitig wird eine durch -Bi ausgedrückte Imaginärzahl Ci an der Ausgangsklemme 48 und eine durch Bi ausgedrückte Imaginärzahl Di an der Ausgangsklemme 52 erzeugt. Diese Imaginärzahlen Ci und Di werden in vorbestimmte Adressen des Speichers 18, die von der ersten bis achten Adresse unterschiedlich sind, eingeschrieben. Den in der Stufe 2 durchgeführten Schmetterlingsberechnungen, die vorhergehend beschrieben worden sind, folgen jene in der Stufe 3. Wie in den Fig. 1 und 3 zu erkennen ist, treten Schmetter­ lingsberechnungen in der Stufe 3 in der Reihenfolge einer ersten Schmetterlingsberechnung mit einem ganzzahligen Anteil von 0 für den Variablen 0 und 1 zugeordnete Zahlen, eine zweite Schmetterlingsberechnung mit einem ganzzahligen Anteil P von 2 bei den Variablen 2 und 3 zugeordneten Zahlen, eine dritte Schmetterlingsberechnung mit einem ganzzahligen Anteil von P von 4 bei den Variablen 4 und 5 zugeordneten Zahlen und eine vierte Schmetterlingsberechnung mit einem ganzzahligen Anteil von P von 6 bei den Variablen 6 und 7 zugeordneten Zahlen auf. Die Schalter 34, 36, 42 und 44 werden in der gleichen Weise wie bei der Stufe 1 für die erste Schmetterlingsberechnungsperiode, in der gleichen Weise wie bei der zweiten Schmetterlingsberechnungsperiode in der Stufe 2 für die zweite Schmetterlingsberechnungsperiode betrieben und mit den Kontakten 34 a, 36 a, 42 a und 44 a für die dritte und vierte Schmetterlingsperioden verbunden.

Bei dem vorgenannten Verfahren für die dritte und vierte Schmetterlingsberechnungsperiode werden Datenausgaben von den Multiplikationsschaltungen 28, 30, 38 und 40 durch die zugeordneten Schalter 34, 36, 42 und 44 als Realteile Br und Imaginärteile Bi geliefert. In der beschriebenen Weise werden Realteile Cr, Imaginärteile Ci, Realteile Cr und Imaginärteile Ci, die durch die Gleichungen (8) und (9) bestimmt sind, an den entsprechenden Ausgangsklemmen 46, 48, 50 bzw. 52 erhalten und in vorbestimmte Adressen des Speichers 18 eingeschrieben.

Kurz gesagt, werden bei dem erläuterten Ausführungsbeispiel für die zwei Arten I und II, bei denen keine Multiplikationen erforderlich sind, die Schalter 34, 36, 42 und 44 betätigt, um unmittelbar an ihre Eingangsklemmen 14 und 16 gegebene Daten ohne eine Multiplikation abzugeben. Bei einer Art, bei der eine Multiplikation erforderlich ist (Schmetterlingsberechnungen mit einem Wert P, welcher gleich 4 oder größer ist) werden die Ausgangsdaten der Multiplikationsschaltungen 28, 30, 38 und 40 ausgewählt. Dies verringert die Häufigkeit der erforderlichen Multiplikationen verglichen mit einer Rechnereinrichtung für schnelle Fourier-Transformation nach dem Stand der Technik. Die Häufigkeit des Auftretens von der Art I, bei der die ganze Zahl P 0 ist, beträgt aufgrund der Analogie zwischen den Fig. 3 und 5, N - 1, während die Häufigkeit des Auftretens der Art II, bei der die ganze Zahl P gleich 2 ist, (N/2) -1 beträgt. Damit ist die Häufigkeit der Multiplikation bei dieser Ausführungsform

(N/2) log₂N - [(N - 1) + {(N/2) - 1}] = (N/2) log₂N - (3N/2) + 2

Die Häufigkeit der Multiplikation, die mit der vorhergehend beschriebenen Ausführungsform erhalten und die durch die vorstehende Gleichung ausgedrückt wird, steht mit der Zahl N der Eingabedaten gemäß der in Fig. 7 mit a bezeichneten Kurve in Beziehung. Man sieht, daß die bei der Ausführungsform erzielte Häufigkeit um (3N/2) -2 kleiner als bei einer Rechnereinrichtung nach dem Stand der Technik ist.

Es ist zu erkennen, daß die mit der Ausbildung gemäß Fig. 6 durchgeführten Vorgänge innerhalb eines elektronischen Rechners durchgeführt werden können.

Die Kontakte 42 b und 42 d der Schalter 42 und 44, die bei der Ausbildung gemäß Fig. 6 vorgesehen sind, bilden keinen wesentlichen Teil der Ausführungsform.

Aus dem vorhergehenden ist zu erkennen, daß eine gewünschte schnelle Fourier-Transformation gemäß der ersten Ausführungsform nach der Erfindung mittels einer einfachen und preiswerten Ausbildung und mit einer Anzahl von Multiplikationen erhalten werden kann, die kleiner als die bisher erforderliche Anzahl (N/2) log₂ N ist und durch ((N/2) log₂ N - (3/2)N + 2) dargestellt ist. Da die Verringerung der Anzahl von Multiplikationen in enger Beziehung mit der Verringerung der Rechenzeit steht, kann eine so kurze Berechnungszeit erreicht werden, die beim Betrachten als Realzeit erscheint, selbst wenn die Anzahl N der Abtastwerte 256 beträgt. Die Einrichtung kann deshalb bei der Realzeit-Anzeige von Sprachsignalen in der Form von Musiknoten angewendet werden. Die Verringerung der Multiplikationshäufigkeit spiegelt sich auch im Vorteil einer höheren Genauigkeit der Berechnung.

Bezüglich des ganzzahligen Anteils P, der 4 oder 6 ist, beträgt der Winkel R 45° oder 135°, wie es Fig. 4 zeigt, wobei sich auf alle Fälle die Gleichung ergibt

und deshalb läßt sich W ^s ausdrücken durch

daraus ergibt sich mit W ^s

(mit R = 45°), daß die folgenden Gleichungen aus den Gleichungen (4 und 8) erhalten werden können:

deshalb sind, um C zu erhalten, zwei Multiplikationen erforderlich, nämlich einmal zur Berechnung von

und einmal zur Berechnung von

Dies gibt auch für D. Obgleich dies auch für den Fall gilt, daß der Winkel R gleich 135° beträgt, ist die er­ forderliche Anzahl von Multiplikationen in einem solchen Fall gerade die Hälfte der vier bisher erforderlichen Multiplikationen, wie es durch die Gleichungen (8) und (9) dargestellt ist.

Wenn der ganzzahlige Anteil P gleich 8 oder größer ist, werden Schmetterlingsberechnungen mit vier Multiplikationen gemäß den Gleichungen (8) und (9) durchgeführt.

Es wird nun auf die Fig. 8 bis 11 bezug genommen, um eine zweite Ausführungsform der Erfindung zu beschreiben.

Wie im Zusammenhang mit der ersten Ausführungsform erörtert, sind keine Multiplikationen für die Art I, bei der der ganzzahlige Anteil P gleich 0 ist und die Art II erforderlich, bei der jener 2 ist. Bei der Art III, bei der P gleich 4 oder 6 ist und Multiplikationen erforderlich sind, kann die Anzahl dieser Multiplikationen verglichen mit dem Stand der Technik halbiert werden. Bei der Art IV, bei der P gleich 8 oder größer ist, sind wie beim Stand der Technik vier Multiplikationen erforderlich. Die zweite Ausführungsform nach der Erfindung ist im Hinblick hierauf so ausgebildet, daß die Arten I und II von den Arten III und IV unterschieden werden und spezielle Schaltungen den Arten I und II zugeordnet sind, um nur Addition und Subtraktion zuzuführen, und spezielle Schaltungen den Arten III und IV zugeordnet sind, um die erforderlichen Schmetterlingsberechnungen durchzuführen. Wiederum verringert eine solche Ausbildung die Häufigkeit der Multiplikation, die bisher für die Schmetterlingsberechnungen bei der schnellen Fourier-Transformation erforderlich war.

Fig. 8 zeigt eine Schaltung, die nach dem obengenannten Prinzip ausgebildet ist. In einem Speicher 54 sind die Realteile von "N" Eingabedaten gespeichert. Die Eingabedaten werden der Reihe nach von dem Speicher 54 einem Demultiplexer 60 über Eingabeklemmen 55 und 57 zugeführt. Der Demultiplexer 60 besitzt zwei weitere Ein­ gangsklemmen 56 und 58. Im Falle, daß N = 8 ist, gelangt der Realteil von x₀, welcher aus dem Speicher 54 ausgelesen worden ist, an die Eingabeklemme 55 des Demultiplexers 60 und der Realteil von x₄ gelangt an die Eingabeklemme 57. Da der Demultiplexer 60, wie man aus Fig. 3 entnehmen kann, weiß, daß die Schmetterlingsberechnung mit einem ganzzahligen Anteil von P gleich 0 in der Stufe 1 auftritt, liefert er die zwei eingegebenen Zahlen an eine Operationseinheit 64 aufgrund eines Aus­ gangssignals einer Steuereinheit 62. Gemäß Fig. 9A umfaßt die Operationseinheit 64 eine Additionsschaltung 66 zum Aufsummieren des an die Eingabeklemme 55 gegebenen Realteils Ar und des an die Eingabeklemme 57 gegebenen Realteils Br, sowie eine Subtraktionsschaltung um eine der Zahlen von der anderen abzuziehen. Die Operationseinheit 64 erzeugt eine reelle Zahl Cr des Ausgangswertes C an einer Ausgangsklemme 70 und die reelle Zahl Dr des Ausgangswertes D an einer Ausgangsklemme 72. Die Opera­ tionseinheit 64 wird verwendet, um Schmetterlingsoperationen durchzuführen, wenn der ganzzahlige Anteil P gleich 0 ist.

Die zwei von der Operationseinheit 64 ausgegebenen reellen Zahlen werden einzeln den Ausgangsklemmen 76 und 78 über einen Multiplexer 74 zugeführt, welcher durch einen Ausgang der Steuereinheit 62 gesteuert wird. Die reelle Zahl Cr, die an der Ausgangsklemme 76 auftritt, wird in die erste Adresse des Speichers 54 eingeschrieben, in der der Realteil des Wertes x₀ gespeichert worden war. Andererseits wird die reelle Zahl Dr, die an der Ausgangsklemme 78 auftritt, in die fünfte Adresse des Speichers 54 eingeschrieben, in welcher der Realteil der Größe x₄ gespeichert worden war.

Anschließend werden der Realteil der Größe x₁ und der Realteil der Größe x₅, die beide in dem Speicher 54 gespeichert sind, ausgelesen und gemeinsam der Operationseinheit 64 über die Eingangsklemmen 55 und 57 und den Demultiplexer 60 zugeführt. Die Operationseinheit 64 führt die vorhergehend erwähnte Schmetterlingsberechnung durch und gibt ihren Ausgangswert an die Ausgangsklemmen 76 und 78 über den Multiplexer 74 ab. Die an der Ausgangsklemme 76 erzeugte reelle Zahl Cr wird in die zweite Adresse des Speichers 54 eingeschrieben, in der der Realteil der Größe x₁ gespeichert war, während die reelle Zahl Dr, die an der Ausgangsklemme 78 erzeugt worden ist, an der sechsten Adresse eingeschrieben wird, an der der Realteil der Größe x₅ gespeichert worden war. Ein solches Vorgehen wird der Reihe nach für die Größen x₂ und x₆ und die Größen x₃ und x₇ durchgeführt, wodurch die Schmetter­ lingsberechnung in der Stufe 1 vollendet wird. Die Ergebnisse dieser Berechnungen, d. h. die Realteile angebenden Zahlen werden in die dritte, vierte, siebte und achte Adresse des Speichers 54 eingeschrieben.

Nun werden an der ersten und dritten Adresse des Speichers 54 gespeicherte reelle Zahlen ausgelesen und dem Demultiplexer 60 über die Eingangsklemmen 55 und 57, wie es Fig. 8 zeigt, zugeführt. Wie man den Fig. 1 und 3 entnehmen kann, ist von vornherein bekannt, daß in der Stufe 2 eine Schmetterlingsberechnung mit einem ganzzahligen Anteil P gleich 0 zuerst für die den Variablen 0 und 2 als auch für die den Variablen 1 und 3 zugeordneten Zahlenwerte durchgeführt wird, woraufhin eine Schmetterlingsberechnung mit einem ganzzahligen Anteil von P von 2 für den Variablen 4 und 6 zugeordnete Zahlenwerte und für den Variablen 5 und 7 zugeordnete Zahlenwerte durchgeführt wird. Deshalb steuert, wenn die vorgenannten reellen Zahlen an die Eingangsklemmen 55 und 57 gelangt sind, die Steuereinheit 62 den Demultiplexer 60 derart, daß die reellen Zahlen der Operationseinheit 64 zugeführt werden. Zwei reelle Zahlen Cr und Dr, die von der Operationseinheit 64 ausgegeben werden, werden an der ersten bzw. dritten Adresse des Speichers 54 über den Multiplexer 74 und die Ausgangsklemmen 76 und 78 eingeschrieben. Entsprechend werden mit den an der zweiten und vierten Adresse des Speichers 54 ausgelesenen reellen Zahlen Schmetterlingsberechnungen in der Operationseinheit 64 durchgeführt und dann in die zweite und vierte Adresse eingeschrieben.

Anschließend werden reelle aus der fünften und der sechsten Adresse des Speichers 54 ausgelesene Zahlen einer Opera­ tionseinheit 80 über die Eingabeklemmen 55 und 57 und den Demultiplexer 60 zugeführt. Wie es Fig. 9B zeigt, umfaßt die Operationseinheit 80 Additionsschaltungen 82 und 84 und Subtraktionsschaltungen 86 und 88, und sie ist so ausgebildet, daß an den Ausgangsklemmen 90 und 92 die reelle Zahl Cr bzw. die imaginäre Zahl Ci der ersten Ausgangsgröße C und an den Ausgangsklemmen 94 und 96 die reelle Zahl Dr bzw. die imaginäre Zahl Di der zweiten Ausgangsgröße D erzeugt werden. Die Operationseinheit 80 führt bei den beiden Eingabewerten A und B eine Schmetterlingsberechnung mit einem ganzzahligen P von 2 durch. Die Werte Cr, Ci, Dr und Di, die aus der Operationseinheit 80 ausgelesen werden, werden den Aus­ gangsklemmen 76, 78, 98 bzw. 100 zugeführt. Die an den Ausgangsklemmen 76 und 78 auftretenden reellen Zahlen Cr und Dr werden an der fünften bzw. siebten Adresse des Speichers 54 eingeschrieben, während die imaginären Zahlen Ci und Di, die an den Ausgangsklemmen 98 und 100 auftreten an neuen Adressen, beispielsweise der dreizehnten bzw. fünfzehnten Adresse des Speichers 54 eingeschrieben werden.

In der gleichen Weise wird mit den reellen Zahlen, die an der sechsten und siebten Adresse des Speichers 54 ausgelesen worden sind, eine Schmetterlingsberechnung mit der Operationseinheit 80 durchgeführt. Die sich ergebenden reellen Zahlen Cr und Dr werden an der sechsten bzw. achten Adresse des Speichers 54 eingeschrieben und die imaginären Zahlen Ci und Di werden neu in die vierzehnte bzw. sechzehnte Adresse des Speichers 54 eingeschrieben.

Dies schließt die Schmetterlingsberechnungen in der Stufe 2 ab. Bei der Operationseinheit 80 sind die imaginären Zahlen Ai und Bi die an zwei der vier Eingangsklemmen angelegt werden, stets Null und deshalb kann die in Fig. 9A gezeigte Operationseinheit durch die in Fig. 10A dar­ gestellte ersetzt werden. Die in Fig. 10A gezeigte Operationseinheit umfaßt einen Vorzeichenwandler 158, der das Vorzeichen der Größen ändert. Die in Fig. 10A gezeigte Ausgestaltung kann ohne weiteres verstanden werden, und deshalb ist keine Beschreibung erforderlich.

Als nächstes werden, wie es in den Fig. 1 und 3 zu erkennen ist, Schmetterlingsberechnungen in der Stufe 3 der Reihe nach durchgeführt, nämlich eine Schmetterlingsberechnung mit einer ganzen Zahl P gleich 2 mittels der Operationseinheit 64 bei den den Variablen 0 und 1 zugeordneten Größen, eine Schmetterlingsberechnung mit ganzzahligem P von 2 mittels der Operationseinheit 80 für die den Variablen 2 und 3 zugeordneten Größen, eine Schmetterlingsberechnung mit einer ganzen Zahl P von 4 mittels der Operationseinheit 102 für die den Variablen 4 und 5 zugeordneten Größen und eine Schmetterlingsberechnung mit einer ganzen Zahl 6 mittels einer Operationseinheit 104 für die den Variablen 6 und 7 zugeordneten Größen. Die sich ergebenden reellen Zahlen Cr und Dr treten an den Ausgangsklemmen 76 bzw. 78 auf, während die imaginären Zahlen Ci und Di an den Ausgangsklemmen 98 bzw. 100 auftreten. Die in Fig. 9C gezeigte Operationseinheit 102 umfaßt Additionsschaltungen 106, 108 und 110, Subtraktions­ schaltungen 112, 114 und 116 und Multiplikations­ schaltungen 118 und 120. Die Multiplikationsschaltung 118 erzeugt Größen, indem die Summe der zweiten Ausgangsgrößen Br und Bi mit dem Koeffizienten /2 multipliziert werden, während die Multiplikationsschaltung 120 Größen erzeugt, indem der durch Subtraktion der reellen Zahl Br von der imaginären Zahl Bi erhaltene Wert mit dem Koeffizienten /2 multipliziert wird. An den Ausgangsklemmen 122 bzw. 124 der Operationseinheit 102 treten die reelle Größe Cr und die imaginäre Größe Ci auf, die durch die Gleichung (10) dargestellt sind. Inzwischen treten an den Ausgangsklemmen 126 bzw. 128 die reelle Größe Dr und die imaginäre Größe Di auf, welche durch die Gleichung (11) dargestellt sind.

Die in Fig. 9D gezeigte Operationseinheit 104 umfaßt Additionsschaltungen 130, 132, 134 und 136, Subtraktions­ schaltungen 138 und 140 und Multiplikationsschaltungen 142 und 144. Die Multiplikationsschaltung 142 erzeugt eine Größe durch Multiplikation der Ausgangsgröße (Bi - Br) der Subtraktionsschaltung 138 mit dem Koeffizienten /2. Die Multiplikationsschaltung 144 erzeugt eine Größe durch Multiplikation der Ausgangsgröße (Bi + Br) der Additionseinrichtung 134 mit dem Koeffizienten /2. An den Ausgangsklemmen 146, 148, 150 bzw. 152 der Operationseinheit 104 treten die reelle Zahl Cr, die imaginäre Zahl Ci, die reelle Zahl Dr und die imaginäre Zahl Ci auf, welche durch Schmetter­ lingsberechnungen aufgrund der Gleichungen (8) und (9) erzeugt wurden, wenn der Phasenfaktor W ^s gleich

ist.

In dem vorhergehend beschriebenen Fall sind, da N gleich 8 ist, die Schmetterlingsberechnungen in drei aufeinanderfolgenden Stufen abgeschlossen, d. h. Schmetter­ lingsberechnungen mit 8 oder größeren ganzzahligen Anteilen treten nicht auf. Jedoch, wenn N gleich 16 oder größer ist, was vier oder mehrere aufeinanderfolgende Stufen ergibt, ist eine Schmetterlingsberechnung mit 8 oder einem größeren ganzzahligen Anteil notwendig. Die in Fig. 8 gezeigte Operationseinheit 184 dient für Schmetterlingsberechnungen mit 8 und größeren ganzzahligen Anteilen von P. Wie bei einer Schaltung nach dem Stand der Technik führt die Operationseinheit 154 Schmetterlingsberechnungen durch, die durch die Gleichungen (8) und (9) dargestellt sind. In diesem Fall wird ein zu einem Phasenfaktor W ^s passender Koeffizient an einer vorgegebenen Adresse einer Koeffizientenspeicherschaltung 156 aufgrund eines Ausgangssignals von der Steuereinheit 62 ausgelesen und der Operationseinheit 154 zugeführt.

Wie vorhergehend beschrieben, sind bei der zweiten Ausführungsform nach der Erfindung die Operationseinheit 64 der Addition und Subtraktion bei der Art I, die Operationseinheit 80 der Addition und Subtraktion bei der Art II, die Operationseinheiten 102 und 104 der Berechnung bei der Art III und die Operationseinheit 154 der Berechnung bei der Art IV zugeordnet. Dies verringert in wirkungsvoller Weise verglichen mit einer Schaltung zur Durchführung einer schnellen Fourier-Transformation gemäß dem Stand der Technik die erforderliche Häufigkeit der Multiplikationen. Das heißt, bei den Arten I und II ist keine Multiplikation und bei der Art III nur die halbe Anzahl von Multiplikationen wie beim Stand der Technik erforderlich. Somit ergibt sich für die Anzahl der Multiplikationen bei dieser besonderen Ausführungsform:

(N/2) log₂N - [(N - 1) + {(N/2) - 1} + {(N/4) - 1}] = (N/2) log₂N - (7N/4) + 3

Die durch eine solche Gleichung angegebene Anzahl von Multiplikationen steht mit der Anzahl N der Eingabedaten in Beziehung, wie es durch a in Fig. 11 angegeben ist.

Wie dargestellt ergibt sich eine (7N/4)-3-mal kleinere Häufigkeit als es bisher erforderlich war.

Es ist zu erkennen, daß die bei der in Fig. 8 gezeigten Vorgänge innerhalb eines elektronischen Rechners ausgeführt werden können. Bei der inversen Transformation gemäß Gleichung (2) weist, da die Imaginärteile nicht stets Null sind, die Operationseinheit 64 die in Fig. 10B dargestellte Ausbildung auf. Jedoch bleibt der Berechnungs­ algorithmus unverändert und wird aus Gründen der Einfachheit nicht beschrieben.

Somit benötigt die vorhergehend beschriebene zweite Aus­ führungsform ebenso wie die erste Ausführungsform eine geringere Anzahl von Multiplikationen zur schnellen Fourier-Transformation und somit eine kürzere Rechenzeit. Wenn die Anzahl der Abtastwerte N beispielsweise 256 ist, ist die Berechnung in nur 60 ms abgeschlossen, was ausreichend kurz ist, um bei der Betrachtung mit dem menschlichen Auge als Realzeit zu erscheinen.

Claims (7)

1. Schaltung zum Durchführen einer schnellen Fourier- Transformation, die eine Fourier-transformierte Datenreihe erzeugt, in der aufeinanderfolgend Eingabedaten einer Schmetterlingsberechnung unter Verwenden eines Phasenfaktors unterworfen werden,
mit einer ersten arithmetischen Schaltung und
mit einer zweiten arithmetischen Schaltung,
denen jeweils wenigstens der Realteil von ersten Eingabedaten aus den ersten und zweiten Eingabedaten zugeführt wird, dadurch gekennzeichnet,
daß die erste und zweite arithmetische Schaltung eine erste und eine zweite Additions-Subtraktions-Schaltung (20, 22) sind,
daß eine dritte Additions-Subtraktions-Schaltung (24) und eine vierte Additions-Subtraktions-Schaltung (26) vorgesehen sind, denen jeweils wenigstens der Imaginärteil der ersten Eingabedaten zugeführt wird,
daß eine erste Multiplikationsschaltung (28) und eine zweite Multiplikationsschaltung (30) vorgesehen sind, denen jeweils der Realteil der zweiten Eingabedaten zugeführt wird,
daß eine dritte Multiplikationsschaltung (38) und eine vierte Multiplikationsschaltung (40) vorgesehen sind, denen jeweils der Imaginärteil der zweiten Eingabedaten zugeführt wird, und
daß Schalter (34, 36, 42, 44) vorgesehen sind, mittels denen der ersten bis vierten Additions-Subtraktions- Schaltung (20, 22, 24, 26) jeweils der Realteil bzw. der Imaginärteil der zweiten Eingabedaten zuführbar sind, ohne daß die ersten bis vierten Multiplikationsschaltungen (28, 30, 38, 40) eine Multiplikation des Realteils und des Imaginärteils mit dem Phasenfaktor durchführen, wenn der Wert des Phasenfaktors 1 oder -j beträgt und durch die der ersten bis vierten Additions-Subtraktions-Schaltung (20, 22, 24, 26) jeweils die Ergebnisse einer Multiplikation des Realteils und des Imaginärteils der zweiten Eingabedaten mit dem Phasenfaktor zuführbar sind, wenn der Wert des Phasenfaktors andere Werte als 1 und -j aufweist, wobei die Multiplikation durch die ersten bis vierten Multiplikationsschaltungen (28, 30, 38, 40) durchgeführt werden.

2. Schaltung nach Anspruch 1, dadurch gekennzeichnet, daß die erste bis vierte Additions-Subtraktions-Schaltung (20, 22, 24, 26) Addiereinrichtungen umfassen.

3. Schaltung nach Anspruch 1, dadurch gekennzeichnet, daß ein Datenspeicher (18) zum Speichern von Realteilen und Imaginärteilen zugeordneten Werten vorgesehen ist, deren Anzahl jeweils wenigstens gleich der Anzahl der Eingabedaten ist.

4. Schaltung nach Anspruch 1, dadurch gekennzeichnet, daß ein Koeffizientenspeicher (32) vorgesehen ist, in dem die Realteile und Imaginärteile des Phasenfaktors gespeichert sind, die den ersten bis vierten Multipli­ kationsschaltungen (28, 30, 38, 40) zuführbar sind.

5. Schaltung zum Durchführen einer schnellen Fourier- Transformation, die eine Fourier-transformierte Datenreihe erzeugt, in der aufeinanderfolgend Eingabedaten einer Schmetterlingsberechnung unter Verwenden eines Phasenfaktors unterworfen werden, gekennzeichnet durch
einen ersten Schalter (Demultiplexer 60), durch den Eingabedaten in Ab­ hängigkeit von dem Wert des Phasenfaktors durchschaltbar sind,
eine erste Rechenschaltung (Operationseinheit 80) und eine zweite Rechen­ schaltung (Operationseinheit 102), denen durch den ersten Schalter (60) Eingabedaten, an denen eine Schmetterlingsberechnung mit dem Phasenfaktor durchzuführen ist, zuführbar sind, wenn der Wert des Phasenfaktors 1 und -j beträgt,
eine dritte Rechenschaltung (Operationseinheit 104), der durch Umschalten des ersten Schalters (60) Eingabedaten zuführbar sind, an denen eine Schmetterlingsberechnung mit einem Phasenfaktor durchzuführen ist, dessen Realteil und dessen Imaginärteil den gleichen Absolutwert aufweisen,
eine vierte Rechenschaltung (Operationseinheit 154), der mittels des ersten Schalters (60) Eingabedaten zuführbar sind, an denen eine Schmetterlingsberechnung mit einem Phasenfaktor durchzuführen ist, dessen Realteil und dessen Imaginärteil abweichende Werte aufweisen,
eine Koeffizientenspeicherschaltung (156), mittels der der vierten Rechenschaltung (154) in einer vorgegebenen Reihenfolge Multiplikationskoeffizienten zuführbar sind, die in der Koeffizientenspeicherschaltung (156) gespeichert sind, und
einen zweiten Schalter (Multiplexer 74) zum Durchschalten der in Real- und Imaginärteile getrennten Ausgangsdaten der ersten bis vierten Rechenschaltung (80, 102, 104, 154) in einer vorbestimmten Reihenfolge.

6. Schaltung nach Anspruch 5, dadurch gekennzeichnet, daß der erste Schalter von einem Demultiplexer (60) und der zweite Schalter (74) von einem Multiplexer gebildet ist.

7. Schaltung nach Anspruch 5, dadurch gekennzeichnet, daß ein Datenspeicher (54) zum Speichern von Realteilen und Imaginärteilen zugeordneten Werten vorgesehen ist, deren Anzahl jeweils wenigstens gleich der Anzahl der Eingabedaten ist.