DE3416536A1 - Recheneinrichtung zur schnellen fourier-transformation - Google Patents

Description

YS

Recheneinrichtung zur schnellen Fourier-Transformation

Beschreibung

Die Erfindung betrifft eine Recheneinrichtung zur schnellen Fourier-Transformation und, insbesondere, eine schnelle Fourier-Transformation-Recheneinrichtung, welche den Zweck einer geringeren Anzahl von Multiplikationen als bei herkömmlichen schnellen Fourier-Transformations-Recheneinriehtungen erzielt und dadurch die Rechenzeit in einem so hohen Maße verringert, daß es· sogar beim Betrachten als Realzeit erscheint.

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, 197*1, 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-Transformaiton (IDFT) definieren:

_Dk * W^pK

_Dk W^pK ■ (1)

1 N - 1 . IDFT: χ=- \ > X_k * W~^p (2)

mit W = exp ( ( - j 2 TT) /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 χ eine Abtastwertfolge der Zeitfunktion und X. eine Abtastwertfolge des Frequenzspektrums, und ρ 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 ( ( 2J7 s ) / N ) (4)

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

^q Um die Gleichung (1) direkt auszurechnen, sind, da W eine komplexe Zahl ist, und sich ρ und k inner-

halb des Bereiches von O bis N - 1 ändern, N Multiplikationen von komplexen Zahlen und N (N - 1) Additionen komplexer Zahlen erforderlich. Soweit

■j^g 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 Eingabedatenreihe ist, und logp N ist, was gleich der Anzahl

2Q 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 Multiplikationshäufigkeit ist, ist die schnelle Fourier-

2g 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.

Der Erfindung liegt deshalb die Zielsetzung zugrunde, eine Recheneinrichtung zur schnellen Fourier-Transformation zu schaffen, welche eine geringerere Multiplikationshäufigkeit als bei dem·herkömmlichen schnellen Fourier-Transformations-Recheneinrichtungen benötigt und dadurch die Rechenzeit ausreichend abkürzt, um beim Betrachten als Realzeit wahrgenommen zu werden.

Eine weitere Zielsetzung der Erfindung besteht darin, eine allgemein verbesserte Recheneinrichtung zur schnellen Fourier-Transformation zu schaffen.

Gemäß einem Gedanken der Erfindung wird eine Recheneinrichtung zur schnellen Fouriertransformation geschaffen, welche eine durch eine schnelle Fourier-Transformation transformierte Datenreihe erzeugt, indem aufeinanderfolgend bei den Eingabedaten eine Schmetterling - Berechnung unter Verwendung eines Phasenfaktors durchgeführt· wird. Die Recheneinrichtung umfaßt.eine erste Addier/.Subtraktionseinrichtung und eine zweite Addier/Subtraktionseinrichtung, denen jeweils von ersten und zweiten Eingabedaten der Realteil von wenigstens den ersten Eingabedaten zugeführt wird, eine dritte Addier/Subtraktionseinrichtung und eine vierte Addier/Subtraktionseinrichtung, denen jeweils wenigstens der Imaginärteil der ersten Eingabedaten zugeführt wird, eine erste und eine zweite Multiplikationseinrichtung, denen jeweils der Realteil der zweiten Eingabedaten zugeführt wird, eine dritte und eine vierte Multiplikationseinrichtung, denen jeweils der Imaginärteil der zweiten Eingabedaten zugeführt wird, und einen

/9 Schalterkreis, um der ersten bis vierten Addier/ Subtraktionseinrichtung den Realteil und den Imaginärteil der zweiten Eingabedaten zuzuführen, ohne daß die ersten bis vierten Multiplikationseinrichtungen den Realteil und den Imginärteil mit dem Phasenfaktor multiplizieren, wenn der Wert des Phasenfaktors 1 und - j ist, und den ersten bis vierten Addier/Subtraktionseinrichtungen das Multiplikationsergebnis des Realteils und des Imaginärteils der zweiten Eingabedaten mit dem Phasenfaktor zuzuführen, welches durch die erste bis vierte Multiplikationseinrichtungen bewirkt wird, wenn der Wert des Phasenfaktors andere Werte als 1 und - j aufweist.
.

Ein anderer Gedanke der Erfindung besteht darin, eine Recheneinrichtung zur schnellen Fourier-Transformation zu schaffen, welche eine mit der schnellen Fourier-Transformation transformierte Datenreihe erzeugt, indem aufeinanderfolgend bei den Eingabedaten eine Schmetterlings - Rechnung unter Verwendung eines Phasenfaktors durchgeführt wird. Die Recheneinrichtung umfaßt einen ersten Schalterkreis, um die Eingabedaten in Abhängigkeit des Wertes des Phasenfaktors umschaltend zuzuführen, einen ersten und einen zweiten Rechenkreis, denen von der ersten Schaltereinrichtung Eingabedaten zugeführt werden, die einer Schmetterlings -Berechnung (butterfly computation) mit dem Phasenfaktor unterworfen werden sollen, wenn der Wert des Phasenfaktors 1 und - j ist, einen dritten Rechenkreis, dem von dem ersten Schalterkreis umschaltend Eingabedaten zugeführt werden, an denen eine Schmetterlings - Berechnung mit einem Phasenfaktor durchgeführt werden soll, der einen Realteil und einen Imaginärteil aufweist, wobei diese Teile

dem Betrag nach gleich sind, einen vierten Rechenkreis, dem von dem ersten Schalterkreis Eingabedaten zugeführt werden, an denen eine Schmetterlings - Berechnung mit einem Phasenfaktor durchgeführt werden soll, der andere Werte aufweist, einen Koeffizientenspeicher, um dem vierten Rechenkreis in vorbestimmter Reihenfolge Multiplikationskoeffizienten zuzuführen, welche in dem Speicher gespeichert sind, und einen zweiten Schalterkreis, um umschaltend Ausgabedaten von den ersten bis vierten Rechenkreisen in einer vorbestimmten Folge zu liefern und die Daten in Realteile und Imaginärteile aufzuteilen.

Die vorstehenden und anderen Zielsetzungen, Merkmale und Vorteile der Erfindung ergeben sich noch näher aus der folgenden, ins einzelne gehenden Beschreibung zusammen mit den Zeichnungen.

Die Erfindung wird im folgenden anhand von Ausführungsbeispielen unter Bezugnahme auf die Zeichnungen näher erläutert. Es zeigt:

Fig. 1 ein beispielhaftes Signalflußdiagratnm bei einer schnellen Fourier-Transfor- · mation,

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

Figuren

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 schnellen

Fourier-Transformation-Recheneinrichtung nach der Erfindung,

Fig. 7 ein Kurvendiagramm der Multiplikationshäufigkeit bei einer herkömmlichen
Einrichtung zur schnellen Fourier-Transformation und bei einer nach
der Erfindung,
10

Fig. 8 ein Blockdiagramm einer anderen Ausführungsform nach der Erfindung,

Fig. 9A

bis 9D Diagramme, die verschiedene wesentliche

Teile der in Figur 8 dargestellten Einrichtung zeigen,

Figuren
10 A und

B Darstellungen, die andere Ausgestaltungen der Figuren 9B und 9A zeigen,
und

Fig. 11 eine graphische Darstellung der Multiplikationshäufigkeit bei einer herkömmlichen Einrichtung zur schnellen
Fourier-Transformation und bei einer
Einrichtung nach der Erfindung zur
Gegenüberstellung bezüglich der Abtastzahl.

Während die Recheneinrichtung zur schnellen Fourier-Transformation nach der Erfindung in einer Vielzahl
von physikalischen Ausführungsformen in Abhängigkeit von der Umgebung und den Benutzererfordernissen realisiert werden kann, 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 zufriedenstellenden Betrieb gezeigt.

Die Erfindung geht von der Überlegung aus, Schmetterlingsberechnungen wirkungsvoll dadurch durchzuführen, daß Eingabedaten in erste zwei Arten (Art I und Art II),

die keine Multiplikation mit dem Phasenfaktor W benötigen, der eine Variable in einem Signalflußdiagramm bei der

schnellen Fourier-Transformation ist, und zweite zwei Arten (Art III und IV) unterteilt werden, bei denen diese erforderlich sind, und daß auf das periodische Erscheinen dieser Arten geachtet wird.
15

Unter Verwendung eines solchen Slgnalflußdiagrammes, wie es in Fig. 1 gezeigt ist, kann die für den schnellen FouriepTransformation-Algorithmus erforderliche Berechnung einfach ausgedrückt werden. Fig. 1 ist ein Signalflußdiagramm, in der die Anzahl der Daten N bei der Abtastwertfolge xp der Zeitfunktion in Gleichung (1) 8 sein soll. Eine Datenrei.he, 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 bzw. Rechenreihen genannt werden. Bei dem Signalflußdiagramm münden zwei Linien in jeden Knoten in einer Rechenspalte (Stufe) ein und stellen Übertragungswege·von den vorhergehenden Knoten dar. Ein übertragungsweg überführt zu einem Knoten in einer gewissen Spalte einen numerischen Ausgangswert von einem Knoten in der unmittelbar vorhergehenden 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 uncT D überführt wird, und in diesem Fall ergibt sich der Wert für C durch Be-

S

rechnung A + BW und der Wert für D durch Berechnung von A - BW^S.

Die Ausgangsdaten ergeben sich zu
5

C = A + BW^S _r ... (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 Absolutwerte 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 xvird, 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 O bis 7 der Daten x_Q 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 ^ausgedruckt, 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 f erhalten wird, dann werden Nullen zu der linken Seite von (f"-l) Bits addiert, und daraufhin wird die Bitfolge der Binärzahl umgekehrt. Um den Wert s zu erhalten, ist es erforderlich, die y-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 worden, der sich durch Division der Variablen (im folgenden mit η bezeichnet) durch (2~ ) ergibt. Infolgedessen ist bei dem in Fig. 1 gezeigten Beispiel der Wert s· ent-

weder 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 η festgelegte Wert gibt den Wert eines 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 1 gleich 1 v~gleich 3 und η einer der Werte 0

bis 3 ist.
35

Wenn sie Stufenzahl 2 und die Variable η 4 oder 5 beträgt, ergibt sich für den ganzzahligen Anteil P 2, da 1 gleich 2, y gleich 3 und η 4 öder 5 ist.

Fig. 4 zeigt die Beziehung zwischen den Werten des ganzzahligen Anteils P und dem Winkel 0 des Phasenfaktors W^s (wobei 0 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 θ 0°; wenn P gleich 2 ist, ist Q₂ gleich 90°; wenn P gleich 4 ist, ist O₁, gleich 45°; und wenn P gleich 6 ist, ist 9,- 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 = logp 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 0 ein solcher, der in Fig. 4 durch eine Gerade 0 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 + j Bi
dann folgt aus Gleichungen (4) - (7)

C = A + BW^S

= (Ar +Br * cos© + Bi sin ö) +

j (Ai + Bi cosO - Br sindO) = Ar + Tr + j (Ai₊ Ti) T8)

D = A - BW^S

= Ar - Tr + j (Ai - Ti) (9)

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ß T-r 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 θ 0° beträgt und cosö = und sinö = 0 ist, so daß. sich aus der Gleichung (¹O für W 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

_o_ berechnet werden können, die lediglich Addition und Sub-Zo

traktion umfassen. Ferner gilt bezüglich der Schmetterlingsberechnungen in der Stufe 1, daß die gesamten Eingabedaten reele 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 30

gleich Ar + Br und D gleich Ar - Br. Das Rechnen mit Realteilen hat als Ausgabewerte wiederum reele Zahlen zur Folge. Deshalb bestehen, wenn der ganzzahlige Anteil P gleich Null ist, sowohl die Eingabedaten als auch

der Phasenfaktor, die einer Schmetterlingsberechnung 35

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 9 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 be-

. _ sonders darauf geachtet, daß eine Multiplikation mit

W 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 20

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 25

eine Multiplikationseinrichtung durchgeführt wird, während für die anderen Arten die erforderlichen Schmetterlingsberechnungen 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 Fourieriransformationsverfahren nach dem Stand der Technik durchgeführt werden.

Es wird auf die Fig. 6 bezug genommen, die eine Rechenein-35

richtung nach der Erfindung als Blockdiagramm zeigt. In Fig. 6 werden Eingabeklemmen 10 bzw. 12 Daten Ar,die die Real-

teile 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 Br, 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 reelen Zahlen, der Anzahl von Daten N und von "N" imaginären Daten ausreicht.

Die Daten Ar werden einer Addier/Subtraktionseinrichtung 20 (genaugenommen einer Addiereinrichtung) und einer Addier/Subtraktionseinrichtung 22 zugeführt, während die Daten Ai an Addier/Subtraktionseinrichtungen 24 und 26 gegeben werden. Die Daten Br werden Mul'tiplikationseinrichtungen 28 und 30 zugeführt, damit sie mit dem Imaginärteil sinO und dem Realteil cosö eines Pha'senfaktors W^s multipliziert werden, welche aus einem Koeffizientenspeicher 32 ausgelesen werden. Die von den Multiplikationseinrichtungen 28 und 30 ausgegebenen Produkte werden Kontakten 33a und 36a von Schaltern 34 bzw. 36 zugeführt. Der Schalter 34 hat drei Kontakte 34a bis 34c und der Schalter 36 drei Kontakte 36a bis 36c. Den Kontakten 34b und 36b werden gemeinsam die Realteile Br zugeführt; die Kontakte 34c und 36 c liegen auf Masse.

Währenddessen werden die Imaginärteile Bi den Multiplikationseinrichtungen 38 und40 zugeführt, damit sie mit dem Imaginärteil sinO und dem Realteil cosO des Phasenfaktors W^s multipliziert werden. Die Ausgänge der Multiplikationseinrichtungen 38 und 40 werden Kontakten 42a und 44a der Schalter 42 bzw.44 zugeführt. Der Schalter ebenso wie die Schalter 34 oder 36 weist drei Kontakte 4?a bis 42c auf und der Schalter 44 besitzt Kontakte 44a bis 44c. Den Kontakten 42b und 44b werden die Daten

Bi unmittelbar von der Eingabeklemme 16 zugeführt; die Kontakte 42c und 44c 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 /Subtraktionseinrichtung 20 summiert den Realteil von der Eingangsklemme 10 und die Daten von den Schaltern 36 und 42, wobei Realteile Cr (= Ar + Br cos 0 + Bi sin ö) der ersten Ausgabedaten C erzeugt werden. Die Daten Cr werden an einen Ausgangsanschluß 46 gegeben. Die Addier/Subtraktionseinrichtung 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 θ - Br sind 0) der ersten Ausgangsdaten C erzeugt werden. Die Werte Ci werden an einen Ausgangsanschluß 48 gegeben. Die Addier/Subtraktionseinrichtung 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/Subtraktionseinrichtung 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 C= Ai - Bi cos 0 + Br sind θ) erzeugt wird. Der Wert Di wird an eine Ausgangsklemme 52 gegeben.

Die Recheneinrichtung mit der vorhergehend genannten Ausgestaltung arbeitet in folgender Weise. Es sei angenommen, daß beispielsweise in dem Speicher 18 in der ersten bis achten Addresse die reellen Zahlen gespeichert sind, die den acht Daten x_Q bis x„ (in diesem Fall mit N. = 8) zugeordnet sind. Wenn N = 8 , werden in der Stufe 1 nur die Schmetterllngsberechnungen 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 36b bzw. 44b 5

verbunden, während die Schalter 34 und 42 mit den Kontakten 34c bzw. 42c 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 10

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 werden nur reelle

Zahlen von dem Speicher 18 den Eingabeklemmen 10 und 14 zugeführt, während keine Imaginärteile den Eingabeklemraen 1|2 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 35

4 und 6 und bei Daten mit den Variablen 5 und 7 durchgeführt. Im Laufe der ersten Schmetterlingsberechnung bei der P gleich O ist, sind die Schalter 36 und 44 mit den

Kontakten 36c bzw. 44c in der gleichen Weise wie bei der 5

Stufe 1 verbunden, während die Schalter 34 und 42 mit den Kontakten 34c bzw. 42c verbunden sind. Während der zweiten Schmetterlingsberechnung, bei der P gleich 2 ist, sind die Schalter 36 und 44 mit den Kontakten 36b bzw. 44b und die Schalter 34 und 42 mit den Kontakten 34b bzw. 42b 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,'Real-

¹^ teile Cr und Dr eingeschrieben, die durch die Schmetterlingsberechnungen 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 eingeschrieben, von dem eine den Variablen 4 oder 5 zugeordnete Größe ausgelesen worden war. Die durch Ar ausge-

drückte reelle Zahl o_r 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

^5 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 Wie in den Fig. 1 und 3 zu erkennen ist, treten Schmetterlingsberechnungen in der Stufe 3 in der Reihenfolge einer ersten .Schmetterlingsberechnung mit einem ganzzahligen Anteil von O für den Variablen· O 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 34a,36a,42a und 44a für die dritte und vierte Schmetterlingsperioden verbunden .

Bei dem vorgenannten Verfahren für die dritte und vierte Schmetterlingsberechr.ungsperiode werden Datenausgaben von den Multiplikationseinrichtungen 28,30,3-8 und 40 durch die zugeordneten Schalter 34,36,42 und 44 als Realteile Br und Imaginärteile Bi geliefert. In der be- ^chriebenen Weise werden Realteile Cr, Imaginärteile Ci, Realteiie 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 Multiplikationseinrichtungen 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

¹S 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 I (N / 2) log ₂ N - [ (N - 1) + {(N / 2) - IJ 3

= (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 42b und 42d 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) logp 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 wer-

Ig den, 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 0 45° oder 135°, wie es Fig. 4 zeigt, wobei sich auf alle Fälle die Gleichung ergibt

sin G| = |cos 8| =

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

-γ- (1 - 3) oder 2~ ^{(1 3)}

daraus ergibt sich mit W"
35

j (1 - 3)

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

C = Ar + ~^(Br + Bi) + j{Ai + ^(Bi -Br)} . (10)

D-Ar- —-(Br + Bi) + JiAi - ^f(Bi - Br)} . (11)

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

JT I t±- (Br + Bi) !

JL

und einmal zur Berechnung von

-^ (Bi - Br) !

Dies gilt auch für D. Obgleich dies auch für den Fall gilt, daß der Winkel θ gleich 135° beträgt,- ist die erforderliche Anzahl von Multiplikationen in einem solchen Fall gerade die Hälfte der vier bisher erforderlichen

Mutiplikationen, wie es durch die Gleichungen (8)und(9) 30

dargestellt ist.

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

Es wird nun auf die Figuren 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 Multiplikation 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 in Hinblick hierauf so ausgebildet, daß die Arten I und II von den Arten III und IV unterschieden werden und spezielle Recheneinheiten den Arten I und II zugeordnet sind, um nur Addition und Subtraktion zuzuführen, und spezielle Recheneinheiten 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 Rechnereinrichtung, 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 5,4 einem Demultiplexer 60 über Eingabeklemmen 55 und 57 zugeführt. Der Demultiplexer 60 besitzt zwei weitere Eingangsklemmen 56 und 58. Im Falle, daß N = 8 ist, gelangt der Realteil von x_Q, welches aus dem Speicher 54 auslesen worden ist, an die Eingabeklemme 55 des Demultiplexers 60 und der Realteil von χ ^. gelangt an die Eingabeklemme 57. Da der Demultiplexer 60, wie man aus Fig.' 3 entnehmen kann, weiß, daß die Schraetterlingsberechnung

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 Ausgangssignals einer Steuereinheit 62. Gemäß Fig. 9A umfaßt die Operationseinheit 64 eine Addiereinrichtung 66 zum Aufsummieren des an die Eingabeklemme 55 gegebenen Realteils Ar und des an die Eingabeklemme 57 gegebenen Realteils Br, sowie eine Subtraktionseinrichtung 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 Operationseinheit 64 wird verwendet, um Schmetterlingsoperationen durchzuführen, wenn der ganzzahlige Anteil P gleich 0 ist.

Die zwei von der Operationseinheit 64 ausgegebenen reelle 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 die reelle Zahl der Größe x^ und die reelle Zahl 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 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_c und die

2 ο

Größen x-, und x„ durchgeführt, wodurch die Schmetterlingsberechnung 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 vorneherein bekannt, daß in der Stufe 2 eine Schmetterlingsberechnung mit einem ganzzahligen Anteil P gleich 0 zuerst für die den Variablen 0 und ^^u 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 SQ 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 die an der zweiten und vierten Adresse des Speichers 54 ausgelesenen reellen ^ Zahlen Schmetterlingsberechnungen in der Operationseinheit

64 unterzogen 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 Operationseinheit 80 über die Eingabeklemmen 55 und 57 und den Demultiplexer 60 zugeführt. Wie es Fig. 9B zeigt, umfaßt die Operationseinheit 80 Addiereinrichtungen 82 und 84 und Subtraktionseinrichtungen 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 Ausgangsklemmen 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 auftreten an neuen Adressen, beispielsweise der dreizehnten bzw. fünfzehnten Adresse des Speichers 54 eingeschrieben.

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. 9 gezeigte Ausbildung durch die in Fig. 1OA dargestellte ersetzt werden. Die in Fig. 1OA 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 T 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. auftreten. Die in Fig. 9C gezeigte Operationseinheit umfaßt Addiereinrichtungen 106, 108 und 110, Subtraktionseinrichtungen 112, 114 und 116 und Multiplikationseinrichtungen 118 und 120. Die Multiplikationseinrichtung 118 erzeugt Größen, in dem die Summe der zweiten Ausgangsgrößen Br und Bi mit dem Koeefizienten ^v0-F'/2 multipliziert werden, während die Multiplikationseinrichtung 120 Größen erzeugt, in dem der durch Subtraktion der

reellen Zahl Br von der imaginären Zahl Bi erhaltene Wert mit dem Koeffizienten l^r2⁷/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 Gleichungen) dargestellt sind.

XO Die in Fig. 9D gezeigte Operationseinheit 104 umfaßt Addiereinrichtungen 130,132,134 und 136, Subtraktionseinrichtungen 138 und 140 und Multiplikationseinrichtungen 142 und 144. Die Multiplikationseinrichtung 142 erzeugt eine Größe durch Multiplikation der Ausgangsgröße (Bi - Br) der Subtraktionseinrichtung 138 mit dem Koeffizienten Π?/2. Die Multiplikationseinrichtung 144 erzeugt eine Größe durch Multiplikation der Ausgangsgröße (Bi +Br) der Additionseinrichtung 134 mit dem Koeffizienten 1/2V2. 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 Schmetterlingsberechnungen aufgrund der Gleichungen (8)und(9) erzeugt wurden, wenn der Phasenfaktor W gleich

- J^- j ^L · i ^ist·

In dem vorhergehend beschriebenen Fall sind, da N gleich 8 ist, die Schmetterlingsberechnungen in drei aufeinanderfolgenden Stufen abgeschlossen, d.h. Schmetterlingsberechnungen 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

-28-

Anteilen von P. Wie bei einer Einrichtung 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 Phasen faktor W passender Koeffizient an einer vorgegebenen Adresse eines Koeffizientenspeichers 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 Operätionseinheit 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 Recheneinrichtung für die schnelle 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 bei einer Recheneinrichtung für die-schnelle Fourier-Transformation nach dem 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) - I) + i (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 35

Häufigkeit als es bisher erforderlich war.

5->

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 crind, die Operationseinheit 64 die in Fig. 1OB dargestellte Ausbildung auf. Jedoch bleibt der Berechnungsalgorhitmus unverändert und wird aus Gründen der Einfachheit nicht beschrieben.

Somit benötigt die vorhergehend beschriebene zweite Ausfü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 beispielweise 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.

Verschiedene Abänderungen sind für den Durchschnittsfach- ^O mann aufgrund der gegebenen Lehre möglich, ohne von dem Grundgedanken der Erfindung abzuweichen.

- Leerseite -

Claims (7)

1. GRÜNECKER, KINKELDEY, STOCKMAIR & PARTNER PATENTANWÄLTE

   PATENT ATTOfNEYS

   A. GRUNECKER. m ι~α

   DR H KiNKELDEY. on. «o

   OR. W STOCKMAIR. on. i~a.Ae!!iCALTEc*i

   DR K SCHUMANN, div-smys

   PH JAK0B.O1·«

   DR G 3EZOLD. ix=u ohkm

   W. MEISTER, an. .no

   H HILGERS on jno

   DR H. MEYER-PLATH. out. .««

   8OOO MÜNCHEN 22

   MAXIMILIANSTRASSE 5S

   P 18 821-46/L Victor Company of Japan, Limited .3-12, Moriya-cho, Kanagawa-ku, Yokohama-shi, Kanagawa-ken, Japan

   Recheneinrichtung zur schnellen Fourier-Transformation

   Patentansprüche

   M.!Recheneinrichtung zur schnellen Fourier-Transformation, die eine schnelle Fourier-transformierte Datenreihe erzeugt, in aufeinanderfolgend an Eingabedaten eine Schmetterlingsberechnung unter Verwendung eines Phasenfaktors durchgeführt wird, gekennzeichnet durch

   eine erste Addier/Subtraktionseinrichtung (20) und. eine zweite Addier/Subtraktionseinrichtung (22), wobei ^ow jeder von ersten und zweiten Eingabedaten der Realteil von wenigstens den ersten Eingabedaten zugeführt wird,

   eine dritte Addier/Subtraktionseinrichtung (24) und eine vierte Addier/Subtraktionseinrichtung (26), denen jeweils wenigstens der Imaginärteil der ersten Eingabe-■35 daten zugeführt wird,

   eine erste Multiplikationseinrichtung (28) und eine zweite Multiplikationseinrichtung (30), denen jeweils der Realteil der zweiten Eingabedaten zugeführt wird, eine dritte Multiplikationseinrichtung (38) und eine vierte Multiplikationseinricht.ung (14), denen jeweils der Imaginärteil· der zweiten Eingabedaten zugeführt wird, und

   Schaltermittel (34,36,42,44),durch die der ersten bis vierten Addier/Subtraktionseinrichtung (20,22,24,26) der Realteil und der Imaginärteil der zweiten Eingabedaten zuführbar sind, ohne daß die ersten bis vierten Multiplikationseinrichtung (28,30,38,40) eine Multiplikation des Realteils und des Imaginärteils mit dem Phasenfaktor durchführen, wenn der Wert des Phasenfaktors 1 bzw. -j ist, und durch die der ersten bis vierten Addier/ Subtraktionseinrichtung (20,22,24,26) die Ergebnisse einer Multiplikation des Realteils und des Imaginärteils der zweiten Eingabedaten mit dem Phasenfaktor zuführbar ist, wenn der Wert des Phasenfaktors andere Werte als 1 und -j aufweist, wobei die Multiplikationen durch die ersten ■ bis vierten Multiplikationseinrichtungen (28,30,38,40) durchgeführt werden.
2. 2. Recheneinrichtung nach Anspruch 1, dadurch g e k e η η zeichnet, daß die erste bis vierte Addier/Subtraktionseinrichtung (28,40,38,40) Addiereinrichtungen umfassen.
3. 3. Recheneinrichtung nach Anspruch 1, dadurch g e k e η η zeichnet, daß ein Datenspeicher (18) zum Speichern der den Realteilen und den Imaginärteilen zugeordneten Werte.n vorgesehen ist, die jeweils wenigstens die gleiche Anzahl wie die Eingabedaten aufweisen.
4. 4. Recheneinrichtung nach Anspruch 1, dadurch gekennzeichnet , daß ein Koeffizientenspeicher (32) zum Speichern der den Werten zugeordneten Realteile und Imaginärteile des Phasenfaktors vorgesehen ist, welche der ersten bis vierten Multiplikationseinrichtung (28,20,38. 40) zugeführt werden.
5. 5. Recheneinrichtung zur schnellen Fourier-Transformation, die eine schnelle Fourier-transformierte Datenreihe erzeugt, indem aufeinanderfolgend an Eingabedaten eine Schmetterlingsberechnung unter Verwendung eines Phasenfaktors durchgeführt wird , gekennzeichnet durch erste Schaltmittel (60), durch die umschaltend die Eingabedaten in Abhängigkeit von dem Wert des Phasenfaktors abgebbar sind,

   eine erste Recheneinrichtung (80) und eine zweite Recheneinrichtung (102), denen durch die ersten Schaltmittel (69) Eingabedaten, an denen eine Schmetterlingsberechnung mit dem Phasenfaktor vorzunehmen ist, zuführbar sind, wenn

   ²^ der Wert des Phasenfaktors 1 und -j ist, eine dritte Recheneinrichtung (104), der durch Umschalten der ersten Schaltermittel (60) Eingabedaten zuführbar sind, an denen eine Schmetterlingsberechnung mit einem Phasenfaktor vorzunehmen ist, welcher einen Realteil und einen Imaginärteil aufweist, die den gleichen absoluten Wert haben,

   eine vierte Recheneinrichtung (154), der durch die ersten Schaltermittel (60) Eingabedaten zuführbar sind, die einer Schmetterlingsberechnung mit einem Phasenfaktor, welcher andere Werte aufweist, vorzunehmen ist, eine Koeffizientenspeichereinrichtung (156), um der vierten Rechnereinrichtung (154) in einer· vorgegebenen Reihenfolge Multiplikationskoeffizienten zuzuführen, die in der Koeffizientenspeichereinrichtung (156) gespeichert sind, und

   zweite Schaltermittel (74), um umschaltend Ausgangsdaten von der ersten bis vierten Recheneinrichtung (80,102, 104,154) in einer vorbestimmten Reihenfolge abzugeben und die Daten in Realteile und Imaginärteile aufzuteilen.
6. 6. Recheneinrichtung nach Anspruch 5, dadurch g ekennzeichnet , daß die ersten und zweiten Schaltermittel jeweils Multiplexer (60,70) umfassen.
7. 7 - Recheneinrichtung nach Anspruch 5, dadurch gekennzeichnet , daß ein Datenspeicher (54) vorgesehen ist, der eine Speicherkapazität zum Speichern der den Realteilen und den Imaginärteilen zugeordneten Daten aufweist, die jeweils wenigstens in der gleichen Anzahl wie die Eingabedaten vorliegen.