CH627010A5

CH627010A5 -

Info

Publication number: CH627010A5
Application number: CH256976A
Authority: CH
Inventors: Georges Bonnerot
Original assignee: Trt Telecom Radio Electr
Priority date: 1975-03-05
Filing date: 1976-03-02
Publication date: 1981-12-15
Also published as: FR2303326A1; DK89076A; SE406254B; FR2303326B1; DK144629C; AU500735B2; DE2608515A1; GB1540883A; DE2608515C2; BE839153A; NL7602083A; JPS51112242A; DK144629B; JPS5611181B2; US4051357A; CA1057400A; AU1160176A; SE7602933L

Description

Die Erfindung bezieht sich auf eine Anordnung zum Berechnen von reellen Fourier-Koeffizienten eines reellen Signals aus den reellen Abtastwerten des Signals gemäss dem Oberbegriff des Patentanspruchs 1 und auf eine Anordnung zum Berechnen von reellen Abtastwerten eines reellen Signals aus den reellen Fourier-Koeffizienten des Signals gemäss dem Oberbegriff des Patentanspruchs 2. Derartige Anordnungen sind für die Spektralanalyse oder zum Filtern von Signalen verwendbar.

Die Berechnung der diskreten Fourier-Transformation einer Reihe äquidistanter Abtastwerte eines Signals ist bereits Gegenstand vieler Veröffentlichungen. Es seien hierzu die nachfolgenden Literaturhinweise angeführt:

1. Digital Signal Processing; Part 2; L.R. Rabiner, C.M. Radar; IEEE Press 1972;

2. Real Signals Fast Fourier Transform Storage Capacity and Step Number Réduction by Means of an Odd Discrete Fourier Transform; J.L. Vernet; Proceedings of the IEEE, October 1971; Seiten 1531-1532.

3. A Fast Fourier Transform Algorithm for Symmetrie Real Valued Sériés; H. Ziegler; IEEE Transactions on Audio and Elektroacoustics, Heft AU-20, No. 5, December 1972; Seiten 353-356.

Die wirtschaftliche Art und Weise der Berechnung der diskreten Fourier-Transformation, im folgenden mit DFT bezeichnet, ist unter dem Namen «Fast Fournier Transform», im folgenden mit FET bezeichnet, bekannt, d. h. als schnelle diskrete Fourier-T ransformation.

Wenn die Reihe durch N Abtastwerte eines reellen Signals gebildet wird, entspricht für eine FET die Anzahl durchzuführender Bearbeitungen der Anzahl Berechnungen, die von der FET durchgeführt wird, wenn die Reihe durch N komplexe Abtastwerte gebildet wird. Infolge der Eigenschaften reeller Signale ist die Anzahl Bearbeitungen, die in einem FET durchgeführt wird, wenn ihr reelle Signalabtastwerte zugeführt werden, unnötig hoch. Wie im Literaturhinweis 2 beschrieben ist,

5 kann die Anzahl Bearbeitungen an N reellen Abtastwerten auf eine Anzahl zurückgebracht werden, die der Anzahl Bearbeitungen, die an N/2 komplexen Abtastwerten durchgeführt werden muss, nahezu entspricht.

Bei dieser bekannten Anordnung wird von einer FFT 10 ausgegangen, die auf übliche Weise aufgebaut ist und sich ausschliesslich zum Verarbeiten komplexer Signalabtastwerte und zum Erzeugen komplexer Fourier-Koeffizienten eignet. Mittels einer Vorverarbeitungsanordnung und der ersten Multiplikationsanordnung werden die reellen Signalabtastwerte in kom-15 plexe Zahlen umgewandelt, die der FFT zugeführt werden. Wenn, wie für Signale mit bestimmten Symmetrieeigenschaften die Fourier-Koeffizienten reell sind, kann die Anzahl durchzuführender Bearbeitungen noch weiter verringert werden, und zwar kann diese Anzahl Bearbeitungen in einer her-20 kömmlichen FFT (siehe Literaturhinweis 3) zurückgebracht werden. Zum Erreichen dieser Verringerung der Anzahl durchzuführender Bearbeitungen wird die herkömmliche Struktur der FFT geändert, was unerwünscht oder bei einer als Bauelement vorgesehenen FFT-Recheneinheit sogar unmöglich ist. 25 Die Erfindung bezweckt nun, unter Verwendung einer herkömmlichen FFT Anordnungen der eingangs erwähnten Art zu schaffen. Die erfindungsgemässen Merkmale der eingangs genannten Anordnungen ergeben sich aus den kennzeichnenden Teilen der Patentansprüche 1 und 2. 30 Die erfindungsgemässen Massnahmen erlauben es, eine FFT der Ordnung N/4 anzuwenden.

Die erfindungsgemässen Anordnungen werden nachstehend anhand der Zeichnungen beispielsweise erläutert. Es zeigen;

35 Fig. 1 Diagramme zur Erläuterung des Zusammenhangs zwischen Zeit- und Frequenzdomänenabtastwerten für eine herkömmliche FFT,

Fig. 2 ein Blockschaltbild einer herkömmlichen FFT, Fig. 3 ein Blockschaltbild einer erfindungsgemässen Anord-4c nung,

Fig. 4 ein Diagramm einer Reihe von Signalabtastwerten, die der Anordnung der Fig. 3 zugeführt werden,

Fig. 5 Diagramme zur Erläuterung des Zusammenhangs zwischen Zeit- und Frequenzdomänenabtastwerten für die 45 erfindungsgemässe Anordnung,

Fig. 6 ein Blockschaltbild, das den zur Fig. 3 inversen Fall darstellt.

Die herkömmliche diskrete Fourier-Transformation DFT wird wie folgt definiert:

Cv = Cl/N)

N-l

I

n=0

X • exp (-2TTj n

k-n.

N J

(1)

In dieser Beziehung ist Ck der k-te zu berechnende Fourier- sind ganze Zahlen mit den Werten 0,1,2,... N — 1.

Koeffizient, Xn ein Eingangssignalabtastwert, N die Anzahl in Auf entsprechende Weise wird die inverse diskrete Fourier-

Betracht gezogener Eingangssignalabtastwerte X„; n und k 6o Transformation IDFT wie folgt definiert:

N-l

\ = J Ck • exp (2Tj ^p) (2)

k=0

627010 4

Der Zusammenhang, der durch die DFT oder die IDFT zwi- werte, die in den Registerteilen mit einer geraden Rangnum-schen die Zeitdomäne und die Frequenzdomäne gelegt wird, ist mer gespeichert sind und die zum linken Teil des Registers 4 in Fig. 1 auf schematische Weise dargestellt. Im Diagramm la gehören, werden, wie in der Figur dargestellt, den Eingängen sind N Signalabtastwerte Xo, Xi, X2,... XN_, dargestellt. Diese R(i) zugeführt. Die Signalabtastwerte, die in den Registerteilen Signalabtastwerte treten zu den Zeitpunkten 0, T, 2T,... (N- 1)T 5 mit einer geraden Rangnummer gespeichert sind, und die zum auf. Mit Hilfe der in der Beziehung (1) definierten DFT können rechten Teil des Registers 4 gehören, werden, wie in der Figur mit diesen N Signalabtastwerten N Fourier-Koeffizienten Co, dargestellt, nach Polaritätsumkehrung den Eingängen I(i) der Ci, C2,... CN_! berechnet werden. Insbesondere sind diese Koef- Multiplizieranordnung 5 zugeführt. Die obengenannte Polari-fizienten Abtastwerte des Frequenzspektrums des Signals, das tätsumkehrung ist in der Figur auf symbolische Weise mittels durch die Signalabtastwerte Xo,..., XN-i repräsentiert wird. 10 Inverter 6,... 8 angegeben. Der einem Eingang R(i) zugeführte Diese Frequenzabtastwerte sind bei den Frequenzen 0,1/NT, Signalabtastwert wird nun als der reelle Teil einer komplexen 2/NT... (N-l)/NT genommen. Diese Frequenzabtastwerte sind Zahl betrachtet, deren imaginärer Teil durch den Signalabtast-im Diagramm 1 b dargestellt wert gegeben wird, der dem zugehörenden Eingang I(i) zuge-

Umgekehrt können mit Hilfe der in der Beziehung (2) defi- führt wird. Dem Eingangspaar R(2m), I(2m) wird folglich bei-nierten IDFT aus den Frequenzabtastwerten Co,... CN-i des Dia- 15 spielsweise die komplexe Zahl X2m - jXN/2 +2m zugeführt, gramms 1 b die Signalabtastwerte Xo,... XN_t des Diagramms la In der Multiplikationsanordnung 5 wird diese komplexe abgeleitet werden. Zahl X2m-jXN/2+2m mit der komplexen Zahl

Die Berechnungen der Ausdrücke (1) bzw. (2) sind vom selben Typ. Die untenstehende Beschreibung wird sich deswegen —2 Tij m+^

auf das Berechnen des Ausdrucks (1) beschränken. 20 ^

Die herkömmlichen Fourier-Transformationsanordnungen sind zur Behandlung komplexer Signalabtastwerte und zur Lie- deren Wert für jeden Wert von m (m = 0,1,2,... N/4 -1) einem ferung komplexer Fourier-Koeffizienten entworfen worden. Speicher 9 entnommen wird, multipliziert. Diese Multiplizier-Eine derartige Fourier-Transformationsanordnung der Ord- anordnung liefert nun N/4 komplexe Zahlen Z2m (m = 0,1,2,... nung N kann, wie in Fig. 2 dargestellt, als eine Recheneinheit 1 25 N/4 -1). Diese komplexen Zahlen werden nun einer herkömmbetrachtet werden, die mit N Eingangspaaren (ao, bo), (ai, bi)... liehen DFT 10 der Ordnung N/4 zugeführt. Diese DFT liefert (aN-i, bN_i) versehen ist, denen die komplexen Zahlen Xo, Xi,... N/4 komplexe Zahlen 0(2q q = 0,1,2, N/4 -1). Zur Bestimmung XN_! zugeführt werden und die mit N Ausgangspaaren (do, eo), dieser komplexen Zahlen a2q werden der DFT 10 Koeffizienten (di, ei)... (dN_), eN-i) versehen ist, an denen die komplexen Zah- zugeführt, die ebenfalls dem Speicher 9 entnommen werden, len Co, Ci... CN_i auftreten. Der Recheneinheit 1 werden weiter 30 Die N/4 komplexen Zahlen a2q werden den Eingangspaaren die komplexen Koeffizienten exp (-2 xjkn/N) mit n = 0,1,2,... einer zweiten Multiplizieranordnung 11 zugeführt, die der (N—1 ) und k = 0,1,2,... (N—1 ) zugeführt. Diese komplexen ersten Multiplizieranordnung 5 entspricht. Die komplexen Zah-

Koeffizienten werden von einem Speicher 2 geliefert. Ausge- len a2q werden darin abermals mit einer komplexen Zahl exp hend von diesen komplexen Koeffizienten und von komplexen Eingangszahlen Xo,Xi,...XN_i berechnet die Einheit 1 entspre- 35 (—2 7tj )',

chend der Formel (1) die komplexen Zahlen Co, Ci...Cn-i, die N

an den obengenannten Ausgangspaaren verfügbar werden. deren Wert bei jedem Wert von q(q = 0,1,2,...N/4 -l)dem

Mit einer derartigen herkömmlichen DFT werden viele Speicher 9 entnommen wird, multipliziert. Die N/4 auf diese

überflüssige Berechnungen durchgeführt, falls die Fourier- Weise gebildeten Produkte sind an den komplexen Ausgangs-

Koeffizienten eines reellen Zeitsignals bestimmt werden müs- 40 paaren [R'(0), I'(0)],... [R'(N/2 -2), I'(N/2 -2)] der Multiplizier-sen, das ausschliesslich reelle oder auschliesslich imaginäre anordnung 11 als N komplexe Zahlen (C2q + jCN/2 +2q) verfüg-

Fourier-Koeffizienten enthält. bar. Das Ganze aus den N/4 reellen Abtastwerten der Fre-

Die Anordnung entsprechend der vorliegenden Erfindung quenzdomäne wird nun auf die folgende Weise erhalten: an den ermöglicht es, mit einfachen Mitteln den Speicherraum auf ein N/4 reellen Ausgängen R' (2q) (q = 0,1,2,... N/4 -1 ) sind die N/4 Viertel zu reduzieren und falls N gross ist, die Anzahl durchzu- 45 Abtastwerte C2q verfügbar. Durch Umkehrung des Vorzei-führender Berechnungen auf etwa ein Viertel zurückzubringen. chens dieser Abtastwerte C2q, und zwar mit Hilfe der Schaltun-Ein Ausführungsbeispiel der erfindungsgemässen Anord- gen 12,14,16, werden die N/4 Abtastwerte CN_ f_2q erhalten. An nung ist in Fig. 3 dargestellt. Diese Anordnung enthält eine den N/4 imaginären Ausgängen I' (2q) sind die N/4 Abtastwerte

Speicheranordnung 4, in der über einen Eingang 3 die Signalab- CN/2 +2q vorhanden. Durch Umkehrung des Vorzeichens dieser tastwerte eingeschrieben werden. Diese Speicheranordnung 4 50 Abtastwerte CN/2 +2q, und zwar mit Hilfe der Schaltungen 13,15, ist dabei als Schieberegister mit N Registerteilen 4(0) - 4(N -1) 17 werden die N/4 Abtastwerte CN/2 _!_2q erhalten.

(wobei N s 0 mod 4) ausgebildet, die je zum Speichern eines Der erfindungsgemässen Anordnung liegt eine neue dis vollständigen Signalabtastwertes Xn eingerichtet sind. Zugleich krete Fourier-Transformation zugrunde. Diese neue Transfor-enthält diese Anordnung eine erste Multiplizieranordnung 5, mation wird als doppelt ungerade diskrete Fourier-Transformadie mit N/4 Eingängen R(0), R(2), R(4),... R(N/2 -2) und N/4 Ein- 55 tion bezeichnet. Diese Transformation wird gekennzeichnet gängen 1(0), 1(2), 1(4),... I (N/2 -2) versehen ist. Die Signalabtast- durch die Beziehung:

N-l ck = (l/N ^ Xn • exp (-2-Iîj C2k-H) (2n+l) 3 (3)

n=0

65

Diese Beziehung, in der n und k ganze Zahlen sind, und tion N Abtastwerten Xn eines Signals N Fourier-Koeffizienten wobei n sowie k die Werte 0,1,2,3,... N-1 annehmen, ordnet Q zu, wobei Xn und Ck im allgemeinen Fall komplexe Zahlen ebenso wie die im Ausdruck ( 1 ) definierte Fourier-Transforma- sind.

5

627010

Wenn T das Intervall zwischen den Abtastwerten Xn des ungeraden DFT des Ausdrucks (3) wie folgt geschrieben wer-Zeitsignals ist, kann die exponentielle Funktion in der doppelt den :

exp (-2TJJ • (2n+l)T/2)

Daraus folgt, dass die Werte der exponentiellen Funktion dere sind im Diagramm 5a die Signalabtastwerte Xo, Xi,... XN-i zu den Zeitpunkten (2n+ l)T/2 genommen werden müssen, die dargestellt, die zu den Zeitpunkten T/2,3T/2... (2N- l)T/2 aufungerade Vielfache von T/2 sind und bei den Frequenzen 10 treten. Im Diagramm 5b sind die Fourier-Koeffizienten Co, Ci, ... 2k + 1)2NT, die ungerade Vielfache der Frequenz 1/2NT sind. Cn-i dargestellt, die durch die doppelt ungerade DFT erhalten

Daraus geht hervor, dass die doppelt ungerade DFT sind und die bei den Frequenzen 1/2NT, 3/2NT... (2N- 1)2NT

gemäss Ausdruck (3) ausgehend von Abtastwerten Xn eines auftreten.

Zeitsignals, die zu Zeitpunkten (2n+1 )T/2 genommen sind, d. h. Ausser einer doppelt ungeraden diskreten Fourier-Trans-

zu ungeraden Vielfachen von T/2, Fourier-Koeffizienten Ck lie- ,5 formation kann auch eine inverse doppelt ungerade diskrete fert, die auf ungeraden Vielfachen der Frequenz 1/2NT liegen. Fourier-Transformation wie folgt angegeben werden:

In Fig. 5 ist dies auf schematische Weise dargestellt. Insbeson-

Xn - ) Ck - exp (2Tj C4)

n=0

25

Durch Verwendung der Eigenschaften der exponentiellen Abtastwerte X„ sowie die Fourier-Koeffizienten Ck reell sind,

Funktionen lässt sich darlegen, dass die doppelt ungerade DFT dass die folgenden Eigenschaften aufweist: Xn=-XN_t_n (7)

- Wenn die Abtastwerte Xn des Signals reell sind, sind die 30 <"k ^N-,~k ® komplexen Signalabtastwerte derart, dass Mit Hilfe der obenstehenden Ausdrücke wird nun darge-

legt, dass in der erfindungsgemässen Anordnung nach Fig. 3

Ck = — Cn-i-ic (5) eine doppelt ungerade diskrete Fourier-Transformation durch-

. geführt wird.

in der CN_i.k den konjugierten komplexen Wert von CN_i_k dar- 35 Aus dem Ausdruck (8) folgt, dass es genügt, entweder die stellt. Koeffizienten mit einer geraden oder die mit einer ungeraden

- Wenn die Fourier-Koeffizienten Ck reell sind, sind die Rangnummer zu berechnen, da die Koeffizienten mit einer kompelxen Signalabtastwerte derart, dass ungeraden bzw. geraden Rangnummer daraus abgeleitet wer-

den können. Werden nun insbesondere die Koeffizienten mit

Xn=-XN_,_n (6) 40 einer geraden Rangnummer berechnet, so geht der Ausdruck

(3), wenn dabei k dem Wert 2q entspricht (mit q = 0,1,2,...

- Aus den beiden Eigenschaften (5) und (6) folgt, wenn die n/2 -) über in:

N-l

C2q " (1/N) ' 8XP (4q+1^2ntl) )

(9)

n=0

Die Reihe von N Abtastwerten Xn (mit O^n^N—1) kann in eine teilt werden. Wenn nun die bekannten Eigenschaften der Reihe mit N/2 Abtastwerten Xn (mit 0 ^ n ^ N/2 -1) und eine exponentiellen Funktion verwendet werden, geht der Ausdruck Reihe mit N/2 Abtastwerten XN/2+n (mit 0 ^ n ^ N/2 -1) aufge- (9) in den folgenden Ausdruck über

N/2 -1

C2q * (1/N) y (ViXN/2 ^ (4^1^2n'1)) (10)

11=0

Wenn nun die Reihen von Abtastwerten Xn und XN/2 +n der- einer ungeraden Rangnummer X2m+1 und XN/2 +2m+, mit m = 0, art betrachtet werden, dass sie aus Abtastwerten mit einer ^ 2>3. - N/4 ~1 zusammengestellt sind, kann der Ausdruck (10)

geraden Rangnummer X2m und XN/2 +m und Abtastwerten mit 65 wie fol8* geschrieben werden:

m-0

Cil)

N/4 -1

(1/10 y (X2m+1 - jXN/2 t2m+1)-exp (-215 («q*l)(«»*l)j m=0

Durch den Ausdruck (11) werden nun N/2 Fourier-Koeffi- 20 Ausdruckes (11) zum Berechnen der Koeffizienten C2q und CN/2 zienten C2q, mit q = 0,1,2,... (N/2 -1) definiert. Diese N/2 Fou- +2q (mit 0 ^ q ^ N/4 -1) und durch Verwendung der bekannten rier-Koeffizienten können in N/2 Fourier-Koeffizienten C2q mit Eigenschaften der exponentiellen Funktionen lässt sich darle-q = 0,1,2,... N/4 -1 und N/4 Fourier-Koeffizienten CN/2 +2q mit q Sen-dass N/4 komplexe Zahlen C2q + jCN/2 +2q erhalten werden = 0,1,2,... N/4-1 aufgeteilt werden. Durch Verwendung des können, die dem nachfolgenden Ausdruck entsprechen:

C2q + **CN/ 2 +2q m=0

exp c-2-irj C12)

Dieser Ausdruck lässt sich weiter vereinfachen zu:

C2q + jCN/2 +2q = C2/N)-exp (-2*3

N/4 -1

m=0

(X2m *;)"XN/2 + 2nP "exp ^N^ ^

exp (-2Tfj ^^) C13)

Entspricht nun das Eingangssignal dem Ausdruck (7), so Obenstehend wurde nur derjenige Fall beschrieben, in dem sind alle Fourier-Koeffizienten reell und der Real- und der Ima- reelle Zeitsignalabtastwerte in reelle Frequenzsignalabtast-ginärteil des Ausdrucks (12) oder (13) stellt dann je einen Fou- werte umgewandelt werden, und zwar durch Verwendung des rier-Koeffizienten dar. Die N/4 komplexen Ausgangszahlen der Ausdrucks (3). Wenn nun vom Ausdruck (4) ausgegangen wird, Multiplikationsanordnung 11 nach Fig. 3 sind also N/2 reellen 65 lässt sich darlegen, dass die Anordnung nach Fig. 3 sich auch Fourier-Koeffizienten gleichwertig. Die übrigen N/2 Fourier- zum Umwandeln von reellen Frequenzsignalabtastwerten in Koeffizienten werden nun mit Hilfe des Ausdrucks (8) berech- reelle Zeitsignalabtastwerte eignet. Die dazu geeignete Anordnet. nung ist in Fig. 6 dargestellt. Diese Anordnung enthält eine

627010

Speicheranordnung 4', in der über einen Eingang 3' die reelle Fourier-Koeffizienten Cn eingeschrieben werden. Diese Speicheranordnung 4' ist dabei als Schieberegister mit N Registerteilen 4'(0) -4'(n-1) ausgebildet, die je zum Speichern eines vollständigen Koeffizienten C„ eingerichtet sind. Zugleich enthält diese Anordnung eine erste Multiplizieranordnung 5', die mit N/4 Eingängen Ri(0), Ri(2), Ri(4)... Ri(N/2) -2) und mit N/4 Eingängen li(0), Ii(2), Ii(4),... Ii(N/2 -2) versehen ist. Die Fourier-Koeffizienten, die in den Registerteilen mit einer geraden Rangnummer gespeichert sind und die einen Teil des linken Teils des Registers 4' bilden, werden, wie in der Figur dargestellt, den Eingängen Ri(i) zugeführt. Die Fourier-Koeffizienten,die in den Registerteilen mit einer geraden Rangnummer, die grösser als oder gleich N/2 ist, gespeichert sind, und die also zum rechten Teil des Registers 4' gehören, werden nach Polari-tätsumkehrung den Eingängen Ii(i) zugeführt. Die obengenannte Polaritätsumkehrung ist in der Figur auf symbolische Weise mittels Invertierer 6', 7', 8' angegeben. Der einem Eingang Ri(i) zugeführte Fourier-Koeffizient wird nun als der reelle Teil einer komplexen Zahl betrachtet, deren imaginärer Teil durch den Fourier-Koeffizienten gegeben wird, der dem zugehörenden Eingang Ii(i) zugeführt wird. Dem Eingangspaar Ri(2m), Ii(2m) wird folglich beispielsweise die komplexe Zahl C2m - jCN/2 +2m zugeführt (m = 0,1,2,... N/4 -1).

In der Multiplizieranordnung 5' wird diese komplexe Zahl mit der komplexen Zahl exp

(2 Ttj*

m+1/8 N

),

deren Wert für jeden Wert von m mit m = 0,1,2,... N/4 -1 Speicher 9' entnommen wird, multipliziert. Diese Multiplizieranordnung liefert nun N/4 komplexe Zahlen Z2m'. Diese komplexen Zahlen werden nun einer IDFT der Ordnung N/4 zugeführt.

Diese IDFT liefert N/4 komplexe Zahlen a2q' mit q = Ó, 1,2,... N/4 -1. Zur Bestimmung dieser komplexen Zahlen a2q' werden dieser IDFT Koeffizienten zugeführt, die ebenfalls dem Speicher 9' entnommen werden. Die N/4 komplexen Zahlen a2q' werden den Eingangspaaren einer zweiten Multiplizieranordnung 11 ' zugeführt, die der ersten Multiplizieranordnung 5' entspricht. Die komplexen Zahlen a2q' werden darin abermals mit einer komplexen Zahl exp

10 (2 TtJ

q+1/8 N

),

deren Wert bei jedem Wert von q dem Speicher 9' entnommen 15 wird, multipliziert. Die N/4 auf diese Weise gebildeten Produkte sind an den komplexen Ausgangspaaren R2<0), h(0),... R2(N/2 -2), Iz(N/2 -2) der Multiplizieranordnung 11' als N komplexe Zahlen (X2q + jXN/2 +2q) vorhanden. An den N/4 reellen Ausgängen R2(2q) sind die N/4 Abtastwerte X2q verfügbar. 20 Durch Umkehrung des Vorzeichens dieser Abtastwerte X2q und zwar mit Hilfe der Schaltungen 12', 14', 16' werden die N/4 Abtastwerte XN-i-2q erhalten. An den N/4 imaginären Ausgängen h(2q) sind die N/4 Abtastwerte XN/2 +2q vorhanden. Durch Umkehrung des Vorzeichens dieser Abtastwerte XN/2 +2q und 25 zwar mit Hilfe der Schaltungen 13,15,17 werden die N/4 Abtastwerte XN/2 _!.2q erhalten.

Aus dem Obenstehenden geht hervor, dass die Zahl N, die in der erfindungsgemässen Anordnung auftritt, ein Vielfaches 30 von 4 sein muss, was selbstverständlich keine Beschränkung in bezug auf die Anzahl umzuwandelnder Abtastwerte ist. Wenn N/4 eine Potenz von 2 ist, wird man vorzugsweise bekannte Algorithmen der DFT zur Verwirklichung der Anordnung 10 anwenden.

G

4 Blatt Zeichnungen

Claims

627010

2

PATENTANSPRÜCHE zahlgenerators (9) angeschlossen ist, und mit einer an die Multi-

1. Anordnung zum Berechnen von N reellen Fourier-Koeffi- plizieranordnung (5) angeschlossenen Recheneinheit (10) zum zienten Co, Ci, C2,... CN_] eines reellen Signals aus den reellen Ausführen einer diskreten Fourier-Transformation, dadurch Abtastwerten Xo, Xi, X2... XN_t des Signals, wobei N eine durch gekennzeichnet, dass die Speicheranordnung (4) dazu ausgebil-4 teilbare Zahl darstellt, mit einer Vorverarbeitungsanordnung, 5 det ist, um ausgehend von den Abtastwerten Xo, Xi, X2,... Xn- 1 der über einen Eingangskreis die N Abtastwerte zugeführt wer- die N -1 Abtastwerte X2m und die N -1 Abtastwerte XN/2 + 2m, den und die mit einer Speicheranordnung (4) mit mindestens mit m = 0,1,2,... N/4-1, ihren Ausgängen zuzuführen, dass die zwei Ausgängen versehen ist, mit einer ersten Multiplizieran- erste Multiplizieranordnung (5) dazu ausgebildet ist, N/4 kom-ordnung (5) zum Multiplizieren komplexer Zahlen zum Erzeu- plexe Zahlen Z2m aufgrund der Zahlen X2m und XN/2 +2m und der gen erster Produktzahlen, welche Multiplizieranordnung (5) an 10 vom Komplexzahlgenerator (9) erzeugten Zahlen zu erzeugen, die Ausgänge der Speicheranordnung (4) und eines Komplex- wobei

Z2m = (X2m " ^XN/2 +2m^ * exp "2irj N^1 '

dass die Recheneinheit (10) dazu ausgebildet ist, N/4 komplexe Zahlen er2q aufgrund der N/4 komplexen Zahlen Z2m zu erzeugen, mit q = 0,1,2,... N/4-1, wobei

<^q ' y Z2m . exp C-2TTj Syf ),

m=0

dass eine zweite Multiplizieranordnung (11) vorhanden ist, wel- vom Komplexzahlgenerator (9) herrührenden komplexen Zah-cher die Zahlen a2q zugeführt werden und welcher ebenfalls der len die N/4 reellen Zahlen C2q und die N/4 reellen Zahlen CN/2 Komplexzahlgenerator (9) zugeordnet ist, und welche dazu 30 +2q als Real- bzw. Imaginärteil von N/4 komplexen Zahlen C2q ausgebildet ist, aufgrund der ihr zugeführten Zahlen cr2q und der + jCNß +2q zu liefern, wobei

C2q + j°N/2 +2q = 2<52q * 6Xp und dass Invertierer (12 bis 17) vorhanden sind zum Invertieren (5') an die Ausgänge der Speicheranordnung (4') und eines der Polarität der Zahlen C2q und Cn/2 +2q zwecks Erzeugens der Komplexzahlgenerators (9' ) angeschlossen ist, und mit einer an N/4 reellen Zahlen CN_i_2q und der N/4 reellen Zahlen Cn/2 -i-2q- die Multiplizieranordnung (5') angeschlossenen Recheneinheit
2. Anordnung zum Berechnen von N reellen Abtastwerten 40 (10') zum Ausführen einer inversen diskreten Fourier-Transfor-Xo, Xi, X2,... XN_i eines reellen Signals aus den reellen Fourier- mation, dadurch gekennzeichnet, dass die Speicheranordnung Koeffizienten Co, Ci, C2,... CN_! des Signals, wobei N eine durch (4') dazu ausgebildet ist, um ausgehend von den Fourier-Koeffi-4 teilbare Zahl darstellt, mit einer Vorverarbeitungsanordnung, zienten Co, Ci, C2,... CN_i die N/4 Fourier-Koeffizienten C2m und der über einen Eingangskreis die N Fourier-Koeffizienten zuge- die N/4 Fourier-Koeffizienten CN/2 +2m, mit m = 0,1,2,... N/4 -1, führt werden und die mit einer Speicheranordnung (4') mit min- 45 ihren Ausgängen zuzuführen, dass die erste Multiplizieranord-destens zwei Ausgängen versehen ist, mit einer ersten Multipli- nung (5') dazu ausgebildet ist, N/4 komplexe Zahlen Z2m auf-zieranordnung (5' ) zum Multiplizieren komplexer Zahlen zum grund der Zahlen C2m und CN/2 +2m und der vom Komplexzahl-Erzeugen erster Produktzahlen, welche Multiplizieranordnung generator (9') erzeugten komplexen Zahlen zu erzeugen,

wobei

Z2m' = (C2m " :'CN/2 +2m') * exp NH"

dass die Recheneinheit (10') dazu ausgebildet ist, N/4 komplexe Zahlen o2q' aufgrund der N/4 komplexen Zahlen Z2m' zu erzeugen, mit q = 0,1,2,... N/4 -1, wobei

N/4 -1

CT 1

2q z '

2m exp q.m

CZ"]

111=0

dass eine zweite Multiplizieranordnung (11') vorhanden ist, 65 und der vom Komplexzahlgenerator (9 ' ) herrührenden kom-welcher die Zahlen a2q' zugeführt werden und welcher eben- plexen Zahlen die N/4 reellen Abtastwerte X2q und die N/4 reel-falls der Komplexzahlgenerator (9') zugeordnet ist, und welche len Abtastwerte XN/2 +2q als Real-bzw. Imaginärteil von N/4 dazu ausgebildet ist, aufgrund der ihr zugeführten Zahlen a2q' komplexen Zahlen X2q + jXN/2 +2q zu liefern, wobei

627010

X2q + jXN/2 +2q

= 265q' . exp (2T7j q+^/8 ),

und dass Invertierer (12' bis 17') vorhanden sind zum Invertieren der Polarität der Abtastwerte X2q und XN/2 +2q zwecks Erzeugens der N/4 reellen Abtastwerte XN-i-2q und der N/4 reellen Abtastwerte XN/2 _1_2q.