PatentDe  


Dokumentenidentifikation DE102005045519A1 29.03.2007
Titel Verfahren und Vorrichtung zur FFT Berechnung
Anmelder NewLogic Technologies AG, Lustenau, AT
Erfinder Meilhac, Lisa, Dr., Le Cannet, FR;
Chiodini, Alain, Cagnes Sur Mer, FR
Vertreter Riebling, P., Dipl.-Ing. Dr.-Ing., Pat.-Anw., 88131 Lindau
DE-Anmeldedatum 23.09.2005
DE-Aktenzeichen 102005045519
Offenlegungstag 29.03.2007
Veröffentlichungstag im Patentblatt 29.03.2007
IPC-Hauptklasse G06F 17/10(2006.01)A, F, I, 20060119, B, H, DE
Zusammenfassung Die Erfindung betrifft ein Verfahren und eine Vorrichtung zur Berechnung einer 2N-Punkt-Fourier-Transformation, direkt oder invertiert, einer Eingangssequenz, bestehend aus 2N-Abtastwerten. Gemäß der Erfindung wird ein Signalverarbeitungsverfahren bzw. eine Vorrichtung vorgeschlagen, die einen bestehenden N-Punkt-FFT-Prozessor sowie andere Blöcke, wie beispielsweise ein CORDIC oder ein Filter, verwendet, um eine 2N-Punkt-FFT zu berechnen.

Beschreibung[de]
Technisches Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich auf ein IFFT/FFT Signalverarbeitungsverfahren zur Konvertierung von Signalen im Frequenzbereich in Signale im Zeitbereich und umgekehrt. Ein IFFT/FFT Signalprozessor zur Durchführung dieses Verfahrens wird beispielsweise in jedem auf OFDM-basierenden Kommunikationssystem verwendet, beispielsweise WLAN Systeme gemäß dem 802.11a, g Standard, wo diese Vorrichtung eine Schlüsselrolle in der Signalverarbeitungskette spielt. OFDM (Orthogonal Frequency Division Mulitplexing) ist eine Übertragungstechnik, die auf der Idee eines Frequenzmulitplex-Verfahrens (FDM) basiert, bei dem mehrere Signale zur selben Zeit, aber auf verschiedenen Frequenzen ausgesendet werden. Bei OFDM sendet ein einzelner Sender auf vielen unterschiedlichen orthogonalen (unabhängigen) Frequenzen (typischerweise Duzende oder Tausende). Ein OFDM Basisbandsignal ist die Summe einer Anzahl von orthogonalen Unterträgern, wobei die Daten auf jedem Unterträger unabhängig voneinander moduliert werden und üblicherweise eine Art von Quadraturamplitudenmodulation (QAM) oder Phasenmodulation (PSK) verwendet wird. Dieses zusammengesetzte Basisbandsignal wird typischerweise für die Modulation eines Haupt-HF-Trägers verwendet. Obwohl die Erfindung wohl verstanden wird im Zusammenhang mit zunehmenden populären WLAN-Systemen, wie beispielsweise HiperLAN2, 802.11a, 802.11g und bald 802.11n, &mgr;m nur ein paar zu nennen, ist es offensichtlich, dass sie auch auf jedes andere Signalverarbeitungs- oder Kommunikationssystem angewendet werden kann, welches einen IFFT/FFT Prozessor beinhaltet.

Hintergrund der Erfindung

Der 802.11n Standard, welcher sich augenblicklich in der Spezifizierungsphase befindet, wird erwartungsgemäß den 802.11a/g Standard zum Ende 2006 ersetzen. Unterdessen wurden zwei konkurrierende Vorschläge (genannt TGnSync und WWise) gemacht und werden diskutiert. Obwohl keiner von beiden bisher einen ausschlaggebenden Vorteil gegenüber dem anderen erzielt hat, zeichnen sich jedoch bereits jetzt zahlreiche Merkmale ab:

  • • OFDM ist als Modulationsart gewählt worden.
  • • Eine Rückwärtskompatibilität mit 802.11a soll sichergestellt sein
  • • Die Anzahl von OFDM Unterträgern wurde vergrößert von 52 auf entweder 56 (in beiden TGnSync und WWise Vorschlägen), wenn ein 20 MHz Kanal verwendet wird oder 114 (TGnSync), wenn ein 40 MHz Kanal verwendet wird.

Aufgrund dieser Tatsachen benötigen 802.11n Modems die Einbettung eines Doppelmodus (d.h. 64-Punkt + 128-Punkt) IFFT/FFT Prozessors. Eine 128-Punkt IFFT/FFT wird daher benötigt, um den 64 IFFT/FFT Block, der in einem 801.11n Modem eingebaut ist zu komplettieren, um einen Dualmodul IFFT/FFT Prozessor zu bilden.

Eine geradlinige Lösung besteht in der Entwicklung und Programmierung einer 128-Punkt FFT von Grund auf und der Zusammenfassung mit einer existierenden 64-Punkt FFT, um den oben erwähnte Dualmodusprozessor zu schaffen. Das bedeutet, dass wir von Grund auf einen 128-Punkt IFFT/FFT Block entwickeln und diesen neben einen 64-Punkt Prozessor stellen müssen. Es weren somit zwei separate IFFT/FFT Prozessoren, welche übrigens auch aller Wahrscheinlichkeit nach verschiedene Radices unterstützen müssen, benötigt, um einen Dualmodus IFFT/FFT Prozessor der oben beschriebenen Art zu bilden. Es versteht sich von selbst, dass diese Lösung in jeder Hinsicht sehr teuer ist, denn ein relatives großes Projekt muss initiiert und durchgeführt werden, um dieses Ziel zu erreichen. Dieser Ansatz bedingt neben anderen Dingen das Aufbringen des benötigten Personals, die Durchführung einer theoretischen Studie, die Entwicklung eines entsprechenden Matlab Fest-Punkt Models, das Schreiben der VHDL Datei, die Durchführung der Bit-true Verifizierung, etc. In Bezug auf die Gatteranzahl ist zu erwarten, dass die Größe des Dualmodus IFFT/FFT Prozessors mehr als dem doppelten (sogar dem dreifachen, sollten wir meinen) entsprechen wird. Dasselbe kann im Hinblick auf den Stromverbrauch gesagt werden.

Offenbarung der Erfindung

Es ist die Aufgabe der Erfindung, ein IFFT/FFT Signalverarbeitungsverfahren und einen zugehörigen Signalprozessor zur Berechnung einer 2N-Punkt Fourier Transformation anzugeben.

Diese Aufgabe wird durch die Bereitstellung eines IFFT/FFT Signalverarbeitungsverfahrens und eines Signalprozessors erreicht, wie sie in den unabhängigen Ansprüchen beschrieben sind.

Andere Merkmale, welche als für die Erfindung charakteristisch betrachtet werden, sind in den abhängigen Ansprüchen ausgeführt.

Gemäß der Erfindung wird ein Signalverarbeitungsverfahren vorgeschlagen, das von einem bestehenden N-Punkt FFT Prozessor sowie auch anderen Blöcken wie z. B. einem CORDIC oder einem Filter Gebrauch macht, um eine 2N-Punkt FFT zu berechnen.

Die Erfindung wiederverwendet einen bestehenden N-Punkt IFFT/FFT Block und integriert ihn in ein größeres System entweder durch Verallgemeinern des Schmetterlingskonzepts oder Durchführung einer entsprechenden Tiefpassfilterung. Somit können wir sehr einfach eine 2N-Punkt IFFT/FFT berechnen. Diese Lösung benötigt einen minimalen Aufwand von Zeit, Personal und Technologie und resultiert damit in erheblichen Einsparungen in Bezug auf Mannmonate, Gatteranzahl (die Chipgröße sollte nicht mehr als 20 % bis 40 % steigen) Stromverbrauch (was heutzutage eine große Rolle spielt) und letztendlich Kosten.

Vier Ausführungsformen der Erfindung werden vorgeschlagen. Es ist zu beachten, dass wir uns nur auf die Beschreibung der direkten FFT beschränkt haben. Die inverse FFT kann aus den nachfolgenden Blockdiagrammen ohne jede Schwierigkeit abgeleitet werden.

Kurze Beschreibung der Zeichnungen

1 zeigt ein Blockdiagramm einer ersten Ausgestaltung des Signalprozessors gemäß der Erfindung.

2 zeigt ein Blockdiagramm einer zweiten Ausfgestaltung des Signalprozessors gemäß der Erfindung.

3 zeigt ein Blockdiagramm einer ditten Ausgestaltung des Signalprozessors gemäß der Erfindung.

4 zeigt ein Blockdiagramm einer vierten Ausgestaltung des Signalprozessors gemäß der Erfindung.

Ausführliche Beschreibung von bevorzugten Ausführungsformen der Erfindung

1 zeigt ein Blockdiagramm einer ersten Ausführungsform des Signalprozessors gemäß der Erfindung. Ein Signal im Zeitbereich, z. B. ein OFDM Basisbandsignal, das beispielsweise aus N = 128 digitalen Abtastwerten x(n) besteht, wird in ein unteres Teilsignal xlower(n) und ein oberes Teilsignal xupper(n) aufgeteilt, wobei jedes Teilsignal aus N/2 = 64 Abtastwerten besteht. Das untere Teilsignal xlower(n) und das obere Teilsignal xupper(n) werden beide einem 64-Punkt FFT Signalprozessor 1, 2 zugeführt und parallel (oder nacheinander) einer 64-Punkt FFT mit einer 2/4/8 gemischten Wurzel unterzogen. Die FFT Signalverarbeitung ergibt ein unteres Teilsignal im Frequenzbereich und ein oberes Teilsignal im Frequenzbereich. Diese beiden Signale und werden einer Addierschaltung 6 zugeführt und aufaddiert und ergeben ein Signal im Frequenzbereich, welches die "geradzahligen" Unterträger Nr. 0, 2, 4,...., 126 (Matlab Notation: 0:2:126) des OFDM Basisbandsignals enthält.

Zur selben Zeit werden das untere Teilsignal xlower(n) und das obere Teilsignal xupper(n) in einen CORDIC (Coordinate Rotation Digital Computer) Rotator 5 eingeben, wo sie um eine Phasenfolge von gedreht werden.

Das gedrehte untere Teilsignal xlower(bis)(n) und das gedrehte obere Teilsignal xupper(bis)(n) werden jeweils einem 64-Punkt FFT Signalprozessor 3, 4 zugeführt und parallel (oder nacheinander) einer 64-Punkt FFT mit 2/4/8 gemischter Wurzel unterzogen. Dies ergibt ein gedrehtes unteres Teilsignal im Frequenzbereich und ein gedrehtes oberes Teilsignal im Frequenzbereich. Diese beiden Signale und werden einer Addiererschaltung 7 zugeführt und dort aufaddiert, um ein Signal im Frequenzbereich zu bilden, welches die "ungeraden" Unterträger Nr. 1, 3, 5,..., 127 (Matlab Notation: 1:2:127) des OFDM Basisbandsignals enthält.

Gemäß einer zweiten Ausgestaltung der Erfindung, dargestellt in 2, wird ein Signal im Zeitbereich, z. B. ein OFDM Basisbandsignal, welches beispielsweise aus N = 128 digitalen Abtastwerden x(n) besteht, in ein unteres Teilsignal xlower(n) und ein oberes Teilsignal xupper(n) geteilt, wobei jedes Signal aus N/2 = 64 Abtastwerten besteht. Das untere Teilsignal xlower(n) und das obere Teilsignal xupper(n) werden jeweils einem 64-Punkt FFT Signalprozessor 1, 2 zugeführt und parallel (oder nacheinander) einer 64-Puntk FFT mit 2/4/8 gemischter Wurzel unterzogen. Dies ergibt ein unteres Teilsignal im Frequenzbereich und ein oberes Teilsignal im Frequenzbereich. Diese beiden Signale und werden einem Addierer 6 zugeführt und dort aufaddiert und bilden ein Signal im Frequenzbereich, welches die „geradzahligen" Unterträger 0:2:126 des OFDM Basisbandsignals umfasst.

Zur selben Zeit werden die beiden Signale und einzeln jeweils Filterschaltungen 8, 9 zugeführt und einer Filterung Hlower bzw. Hupper im Frequenzbereich unterzogen. Die komplexen Koeffizienten der Filter 8, 9 im Frequenzbereich erhält man wie folgt (Matlab Notation):

Das gefilterte untere Teilsignal im Frequenzbereich und das gefilterte obere Teilsignal im Frequenzbereich werden nachfolgend einer Addierschaltung 7 zugeführt und aufaddiert und ergeben ein Signal im Frequenzbereich, welches die "ungeraden" Unterträger 1:2:127 des OFDM Basisbandsignals umfasst.

Gemäß einer dritten Ausgestaltung der Erfindung, wie sie in 3 dargestellt ist, wird ein Signal im Zeitbereich, z. B. OFDM Basisbandsignal, das beispielsweise aus N = 128 digitalen Abtastwerten x(n) besteht in ein unteres Teilsignal xlower(n) und ein oberes Teilsignal xupper(n) aufgeteilt, wobei jedes Signal aus of N/2 = 64 Abtastwerten besteht. In einem ersten Zweig werden das untere Teilsignal xlower(n) und das obere Teilsignal xupper(n) mittels einer Addierschaltung 10 addiert, und in einen 64-Punkt FFT Signalprozessor 1 eingegeben und einer 64-Punkt FFT mit 2/4/8 gemischter Wurzel unterzogen. Dies ergibt ein Signal im Frequenzbereich, welches die „geradzahligen" Unterträger 0:2:126 des OFDM Basisbandsignals umfasst. In einem zweiten Zweig wird das obere Teilsignal xupper(n) von dem unteren Teilsignal xlower(n) mittels eines Addierers 11 (Subtrahieres) subtrahiert. Das sich ergebende Signal wird in einen 64-Punkt FFT Signalprozessor 2 eingegeben und einer 64-Punkt FFT mit 2/4/8 gemischter Wurzel unterzogen. Das ergibt ein Signal im Frequenzbereich, welches einer Filterschaltung 9 zugeführt wird und nachfolgend einer Filterung im Frequenzbereich unterzogen wird Das resultierende gefilterte Signal im Frequenzbereich umfasst die „ungeraden" Unterträger 1:2:127 des OFDM Basisbandsignals.

Nachfolgend werden die mathematischen Gleichungen in Verbindung mit den drei Ausgestaltungen der Erfindung erläutert. Lassen sie uns mit einigen nützlichen Notationen beginnen:

  • • x(n), 0 ≤ n ≤ N – 1, gibt das Signal im Zeitbereich an, dessen FFT berechnet werden soll.
  • • XN(k), 0 ≤ k ≤ N – 1, gibt das entsprechende Signal im Frequenzbereich an (d.h. das nach der Durchführung einer N-Punkt FFT auf x(n)) erhaltene Signal).
  • • xlower(n) = x(n), 0 ≤ n ≤ N2 – 1, gibt die erste Hälfte von x(n) an.
  • • gibt das entsprechende Signal im Frequenzbereich an ( d.h. das Signal, das man nach einer Durchführung einer N2 -Punkt FFT auf xlower(n) erhält).
  • • xupper(n) = x( N2 + n), 0 ≤ n ≤ N2 – 1, gibt die zweite Hälfte des von x(n) an.
  • • gibt das entsprechende Signal im Frequenzbereich an (d.h. das Signal, das man nach der Durchführung einer N2 -Punkt FFT auf xupper(n) erhält).

Die Zeichnungsfiguren 1, 2, und 3 in Verbindung mit jeder der drei Ausgestaltungen der Erfindung beschreiben die Erfindung für N = 128.

Aufgrund der Definition der diskreten Fourier Transformation ergibt sich: mit M = N2

Für "gerade" Unterträger, d.h. wenn k = 2m mit 0 ≤ m ≤ M – 1, erhalten wir:

Es ist leicht zu erkennen, dass die oben stehende Gleichung den drei zuvor beschriebenen Ausgestaltungen der Erfindung zugrunde liegt, wenn es darum geht, die „ geraden" Unterträger zu berechnen.

Nun für "ungerade" Unterträger, d.h. wenn k = 2m + 1 mit 0 ≤ m ≤ M – 1, erhalten wir:

Die oben stehende Gleichung unterliegt der ersten Ausgestaltung wenn es darum geht, die "ungeraden" Unterträger zu berechnen. Sie kann auch umgeschrieben werden wie folgt:

Wobei * das Faltungsprodukt angibt.

Die obige Gleichung unterliegt der zweiten Ausführungsform, wenn es darum geht, die "ungeraden" Unterträger zu berechnen.

Die oben stehende Gleichung unterliegt der dritten Ausgestaltung, wenn es darum geht, die „ungeraden" Unterträger zu berechnen.

Gemäß einer vierten Ausgestaltung der Erfindung, beschreibt 4a) das Spektrum eines OFDM Basisbandsignals mit einer Kanalbandbreite von 40 MHz und 128 Unterträgern. Das Signal umfasst 64 untere Unterträger und 64 obere Unterträger.

Es wird nun auf 4b) Bezug genommen. Um die oberen 64 Unterträger von den unteren 64 Unterträgern zu trennen, wird das Signal um eine negative Frequenz verschoben, die einem Viertel der Kanalbandbreite, d.h. –10 MHz, beträgt, um so die Mitte (ausgedrückt im Hinblick auf die Unterträger) der oberen Unterträger auf Null zu zentrieren. Das frequenzverschobene Signal wird dann hochpassgefiltert, um die unteren 64 Unterträger zu eliminieren. Auf die resultierenden oberen 64 Unterträger kann eine gewöhnliche 64-Punkt FFT angewandt werden.

Es wird nun auf 4c) Bezug genommen. Um die unteren 64 Unterträger von den oberen 64 Unterträgern zu trennen, wird das Signal frequenzverschoben, um eine positive Frequenz verschoben, die einem Viertel der Kanalbandbreite, d.h. +10 MHz, entspricht, um so die Mitte (ausgedrückt in Bezug auf die Unterträger) der unteren Unterträger auf Null zu zentrieren. Das frequenzverschobene Signal wird dann tiefpassgefiltert, um die oberen 64 Unterträger zu eliminieren. Auf die resultierenden unteren 64 Unterträger kann eine gewöhnliche 64-Punkt FFT angewandt werden.

Die Verarbeitung der oberen und der unteren Unterträger kann sequenziell oder parallel erfolgen unter Verwendung von einem oder zwei 64-Punkt FFT Signalprozessoren.


Anspruch[de]
Ein Verfahren zur Berechnung einer 2N-Punkt Fourier Transformation, direkt oder invertiert, einer Eingangssequenz S bestehend aus 2N-Abtastwerten, dadurch gekennzeichnet, dass eine N-Punkt Fourier Transformation direkt oder invertiert, verwendet wird. Das Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass N ein Vielfaches von 2 ist. Das Verfahren nach den Ansprüchen 1 oder 2, dadurch gekennzeichnet, dass die N-Punkt Fourier Transformation eine diskrete Fourier Transformation (DFT), direkt oder invertiert, ist. Das Verfahren nach den Ansprüchen 1 oder 2, dadurch gekennzeichnet, dass die N-Punkt Fourier Transformation eine schnelle Fourier Transformation (FFT), direkt oder invertiert, ist. Das Verfahren nach den Ansprüchen 1 bis 4, dadurch gekennzeichnet, dass die Eingangssequenz S von 2N-Abtastwerten gleichmäßig in zwei zusammenhängende Subsequenzen Slower und Supper von jeweils N-Abtastwerten aufgeteilt wird. Das Verfahren nach Anspruch 5, dadurch gekennzeichnet, dass jede Subsequenz Slower und Supper durch eine Phasenfolge gedreht wird: um gedrehte Sequenzen Slower(bis) bzw. Supper(bis) zu erzeugen. Das Verfahren nach Anspruch 6, dadurch gekennzeichnet, dass die Sequenzen Slower, Supper, Slower(bis) und Supper(bis) nacheinander oder parallel einer N-Punkt Fourier Transformation, direkt oder invertiert, unterzogen werden, um jeweils die Sequenzen Flower, Fupper, Flower(bis) und Fupper(bis) zu erzeugen. Das Verfahren nach Anspruch 7, dadurch gekennzeichnet, dass Flower und Fupper addiert werden, um Feen zu erzeugen, welche die geradzahligen Abtastwerte der 2N-Punkt Fourier Transformation zwischen 0 und 2N-2 umfasst, und dass Flower(bis) and Fupper(bis) addiert werden, um Fodd zu erhalten, welche die ungeraden Abtastwerte der 2N-Punkt Fourier Transformation zwischen 1 und 2N-1 umfasst. Das Verfahren nach den Ansprüchen 1 bis 5, dadurch gekennzeichnet, dass auf die Sequenzen eine Frequenzfilterung angewandt wird, um ausschließlich eine direkte 2N-Punkt Fourier Transformation zu berechnen. Das Verfahren nach Anspruch 9, dadurch gekennzeichnet, dass das Eingangssignal eine Frequenzumsetzung erfährt, um die Mitte, ausgedrückt in Bezug auf die Unterträger, von seiner unteren Hälfte auf Gleichspannung (DC) zu zentrieren. Das Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass das resultierende Signal tiefpassgefiltert wird, um die Abtastwerte, d.h. die Unterträger, mit der Nummerierung 0 bis N-1 der 2N-Punkt Fourier Transformation zu erzeugen. Das Verfahren nach Anspruch 9, dadurch gekennzeichnet, dass das Eingangssignal eine Frequenzumsetzung erfährt, um die Mitte, ausgedrückt in Bezug auf die Unterträger, seiner oberen Hälfte auf Gleichspannung (DC) zu zentrieren. Das Verfahren nach Anspruch 12, dadurch gekennzeichnet, dass das resultierende Signal tiefpassgefiltert wird, um die Abtastwerte, d.h. die Unterträger, mit der Nummerierung N bis 2N-1 der 2N-Punkt Fourier Transformation zu erzeugen. Eine Vorrichtung zur Berechnung einer 2N-Punkt Fourier Transformation, direkt oder invertiert, aus einer Eingangssequenz S bestehend aus 2N-Abtastwerten, dadurch gekennzeichnet, dass sie mindestens eine Signalverarbeitungseinheit (1, 2, 3, 4) zur Ausführung einer N-Punkt Fourier Transformation umfasst. Die Vorrichtung nach Anspruch 14, dadurch gekennzeichnet, dass sie Mittel zur gleichmäßigen Teilung der Eingangssequenz von 2N-Abtastwerten in zwei zusammenhängende Subsequenzen Slower und Supper bestehend aus jeweils N-Abtastwerten umfassen. Die Vorrichtung nach Anspruch 14 oder 15, dadurch gekennzeichnet, dass sie des weiteren einen Phasendreher (5) zur Phasendrehung der Subsequenzen Slower und Supper umfasst, um gedrehte Subsequenzen Slower(bis) bzw. Supper(bis) zu erzeugen. Die Vorrichtung nach Anspruch 16, dadurch gekennzeichnet, dass der Phasendreher (5) ein Coordinate Rotation Digital Computer, CORDIC, ist. Die Vorrichtung nach den Ansprüchen 14 oder 15, dadurch gekennzeichnet, dass sie ferner eine digitale Struktur zur Ausbildung eines Filters (8, 9) im Frequenzbereich umfasst, welches mit dem Ausgang des FFT Signalprozessors (2, 3, 4) verbunden ist. Die Vorrichtung nach den Ansprüchen 14 oder 15, dadurch gekennzeichnet, dass sie ferner einen Addierer oder Subtrahierer (10, 11) umfasst, zum Addieren oder Subtrahieren der Eingangssequenzen Slower und Supper voneinander, bevor sie dem FFT-Signalprozessor zugeführt werden. Die Vorrichtung nach Ansprüchen 14 oder 15, dadurch gekennzeichnet, dass sie ferner einen Addierer (6, 7) umfasst, zum Addieren der Sequenzen Flower und Fupper, die vom FFT Signalprozessor ausgegeben werden.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com