FHD - baeckmann.de · ( ) e π d (4) Da die DFT auf einem Rechner implementiert werden soll, muß man zur Berechnung dieses Integralausdrucks auf ein Näherungsverfahren ausweichen

FHD Fb EA

SignalverarbeitungDie diskrete Fouriertransformation (DFT)

Marcus Bäckmann

VorlesungSignalprozessoren

Prof. Dr. Münter

-1-

Vorlesung Signalprozessoren

Vortrag: Diskrete Fouriertransformation und Anwendungen

Vorlesung Signalprozessoren ......................................................................1Vortrag: Diskrete Fouriertransformation und Anwendungen ........................1

Einleitung ................................................................................................................2Herleitung der Transformationsgleichungen.............................................................3Die diskrete Fouriertransformation und das Abtasttheorem......................................8Rechengesetze für den diskreten Fourieroperator ...................................................11Meßtechnische Probleme der DFT - die Wahl des Zeitfensters ...............................20Übersicht über Signaltransformationen....................................................................29Die schnelle Diskrete-Fouriertransformation ............................................................30Mischung von DFT und kontinuierlicher Fouriertransformation ................................40Digitale Systemidentifikation ...................................................................................43

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-2-

Einleitung

Mitte der siebziger Jahre begann in den USA die Entwicklung eines technischen Systems, das imweiteren Sinne zu den militärischen Frühwarnsystemen gerechnet werden kann. Aufgabe diesesSystems war es, den Funkverkehr der sowjetischen Luftwaffe abzuhören. Dies allein war aber nochnicht die eigentliche Aufgabe. Vielmehr sollten mit Hilfe der Computertechnik die Stimmen dersowjetischen Piloten identifiziert werden, so daß man jeden Piloten an Hand seines Stimmusterserkennen konnte. Der Sinn dieses Aufwandes war folgender: ein Großteil der sowjetischen Pilotenwar nicht in Osteuropa stationiert. Vor einem eventuellen Angriff auf Westeuropa - so die Theorie -wären aber verstärkt neue Piloten nach Osteuropa abkommandiert worden. Und diese neuenPiloten konnte man nur auf Grund ihrer Stimme eindeutig erkennen [HACK].

Glücklicherweise wurde dieses Systems nur angewendet, aber nie auf seine Effektivität überprüft.Das eigentlich erstaunliche aber daran war die Technik: wie kann man einen Menschen nur mitseiner - evtl. sogar verrauschten - Stimme erkennen?

Heutzutage ist diese Stimmerkennung keine Hexerei mehr. Mit der im größeren Verbreitung vondigitalen Signalprozessoren gibt es inzwischen vielfältige Anwendungen dieser Technik:

− Soundkarten im PC, die auf die Benutzerstimme reagieren− behindertengerechte Geräte, die eine Steuerung von Aktoren nur über die Stimme ermöglichen− Sicherheitssysteme, die Türen nur bei bekannter Stimme öffnen− selbst einem so simplen Gegenstand wie einem Lichtschalter kann über einen Mikrochip Leben

eingehaucht werden: er reagiert auf die Kommandos "Licht an", "Licht aus"

Die Frage, die sich der Techniker stellt, liegt auf der Hand: wie geht das mit der Spracherkennung?Im wesentlichen beruht das Prinzip der Spracherkennung darauf, daß jeder Mensch in seinerSprache bei jedem Laut bestimmte, für ihn charakteristische Frequenzen erzeugt.

Also ist die Laut- und Stimmerkennung im wesentlichen auf die Erkennung von Signalenbestimmter Frequenzen und Amplituden in einem bestimmten Zeitabschnitt reduziert.

Signalfrequenzen mit bestimmten Amplituden zu erkennen, ist natürlich eine Domäne derFouriertransformation. Und genau da liegt das Problem: die Fouriertransformation beschäftigt sichmit kontinuierlichen (im mathematischen Sinn stetigen) Funktionen, und setzt unendlich langeMeßdauer voraus. Im vorliegenden Fall ändern sich die Signale ständig, so daß ein Signal inbestimmte kurze Zeitabschnitte unterteilt werden muß. Damit liegen aber keine stetige Funktionenvor, sondern Zahlenfolgen mit einer bestimmten Anzahl von Werten und einer festgelegtenZeitdauer, die von einem A/D-Umsetzer im Speicher einer Recheneinheit abgelegt wurden.

So bleibt uns nichts anderes übrig, als die Begriffe "Stetigkeit" und "Unendlichkeit" über Bord zuwerfen, und eine Theorie zur Fouriertransformation endlicher Zahlenfolgen zu entwerfen.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-3-

Herleitung der Transformationsgleichungen

Bekanntlich ist die Fourierreihe der Sonderfall der Fouriertransformation genau dann, wenn die zutransformierende Funktion periodisch ist.

Es gilt also (z.B. nach [OPPE]):

Transformation aperiodischer Funktionen: X f x t tj ft( ) ( )= ⋅ −

− ∞

∞

∫ e d2π (1)

dimdim

Xx

Hz=

Transformation periodischer Funktionen: cT

x t tmjm ft

T

= ⋅ −∫1 2

0

( ) e dπ (2)

dim dimc x=T : Periodendauer von f

Im letzten Fall wurden die Koeffizienten der komplexen Fourierreihe zur Darstellung derSpektralanteile gewählt.

Betrachtet werden soll nun folgender Fall: es liegt eine Funktion vor, die durch ein Zeitfensterausmaskiert wurde, d.h.

~( )( ) ,

,x t

x t t Tsonst

F=≤ <

00

(3)

Hierbei ist TF die Zeitdauer des Zeitfensters. Diese Funktion kann wie folgt aussehen:

T

t

F

x(t)

Bild 1: Funktion, die durch ein Fenster nur in einem Intervall [0,TF] existiert

Diese Funktion wird nun mit der Periode TF periodisch fortgesetzt. Man erhält die folgendeFunktion:

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-4-

T

t

F

x(t)

Bild 2: Periodische Fortsetzung einer Funktion

Eine periodische Funktion läßt sich bekanntlich in eine Fourierreihe entwickeln. Man macht nun mit(1) Ansatz für die komplexen Fourierkoeffizienten:

XT

x t tmj ft

T

= ⋅ −∫1 2

0

( ) e dπ (4)

Da die DFT auf einem Rechner implementiert werden soll, muß man zur Berechnung diesesIntegralausdrucks auf ein Näherungsverfahren ausweichen. Aus der Analysis ist folgendeseinfaches Verfahren bekannt: man nähert das Integral durch seine Untersumme, d.h. dieIntegrantenfunktion wird in äquidistante Stützstellen aufgeteilt, und die Flächen der dadurchentstehenden Rechtecke werden aufsummiert. Dieses Vorgehen ist auch bei komplexwertigenFunktion ( x t e j ft( ) − 2π ist komplexwertig) erlaubt, nur kann man hier nicht mehr von Flächen undRechtecken im geometrischen Sinn sprechen.

Die Anzahl der äquidistanten Stützstellen sei N , wodurch sich ihr Abstand zu TTN

F= ergibt.

Insgesamt erhält man für (4) den Ausdruck

XT

x t t

TT x nT

x nT

mj ft

T

jm fnT

n

N

jm fnT

n

N

= ⋅

≈ ⋅ ⋅ ⋅

= ⋅

−

−

=

−

−

=

−

∫

∑

∑

1

1

2

0

2

0

1

2

0

1

( )

( )

( )

e d

e

e

π

π

π

(5)

Da TF die Periodendauer ist, gilt: fTF

= 1, und somit auch f

N T=

⋅1

Damit wird die obige Gleichung zu:

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-5-

X x nT

x x x nT

mn

N j mnN

nn

N j mnN

n

= ⋅

= ⋅ =

=

− −

=

− −

∑

∑

( )

, : ( )

0

1 2

0

1 2

e

e mit

π

π(6)

Um eine standardisierte Bezeichnung zu erhalten, werden die Folgen umbenannt (d.h. fn statt xn,und Fm statt Xm):

F fm nn

N j mnN= ⋅

=

− −∑0

1 2e

π(7)

dim dimF fm n=

Die Bezeichnung Fm bezeichnet dabei jeweils die m-te Spektrallinie, mit 0≤m≤N-1.

Das erhaltene Spektrum ist also diskret, d.h. ein Linienspektrum. Es ist dabei zu beachten, daßsowohl fn als auch Fm komplexwertig sein können!

Die Definitionsgleichung (7) wird als "Diskrete Fouriertransformierte (DFT) von fn" bezeichnet (ZurHerleitung siehe zum Beispiel: [ENDE], [HESS], [SCHR], für die globale Einordnungkontinuierlicher und diskreter Verfahren auch [OPPE]).

In der Literatur, insbesondere der mathematischen, findet man vereinzelt auch die Schreibweise

{ }F fm n= FN für die diskrete Fouriertransformierte einer Folge, wobei FN dann "diskreterFourieroperator" heißt. Allerdings ist diese Schreibweise nicht einheitlich, wie überhaupt in derLiteratur die Definition von (5) teilweise stark voneinander abweicht. Eine verbreitete andereDefinitionen ist die, daß die Gleichung (5) noch mit der Abtastzeit multipliziert wird, um die gleicheDimension wie bei der kontinuierlichen Fouriertransformation zu erhalten. Dies ergibt prinzipiellkeine Unterscheide zu der hier verwendeten Definition, allerdings sind gewisse Aussagen undSätze in der Form etwas abweichend.

Beispiel:

Für eine 4-Punkte DFT (N=4) seien die folgenden Zahlenwerte gegeben:

ff f f f

n == = = =

( , , , ), , ,1 2 3 0

1 2 3 00 1 2 3

Für diese Folge wird nun die DFT berechnet:

F f e f e f e f ej j j j

0 0

2 0 04

1

2 014

0

2 0 24

0

2 0 34

1 1 2 1 3 1 0 1 6= ⋅ + ⋅ + ⋅ + ⋅= ⋅ + ⋅ + ⋅ + ⋅ =

− ⋅ − ⋅ − ⋅ − ⋅π π π π

F f e f e f e f ej j j

j j j j

1 0

2 1 04

1

2 114

0

2 124

0

2 134

1 1 2 3 1 0 2 2= ⋅ + ⋅ + ⋅ + ⋅= ⋅ + ⋅ − + ⋅ − + ⋅ = − −

− ⋅ − ⋅ − ⋅ − ⋅π π π π

( ) ( )

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-6-

F f e f e f e f ej j j j

2 0

2 2 04

1

2 214

0

2 2 24

0

2 2 34

1 1 2 1 3 1 0 1 2= ⋅ + ⋅ + ⋅ + ⋅= ⋅ + ⋅ − + ⋅ + ⋅ − =

− ⋅ − ⋅ − ⋅ − ⋅π π π π

( ) ( )

F f e f e f e f ej j j

j j j j

3 0

2 3 04

1

2 314

0

2 3 24

0

2 334

1 1 2 3 1 0 2 2= ⋅ + ⋅ + ⋅ + ⋅= ⋅ + ⋅ + ⋅ − + ⋅ − = − +

− ⋅ − ⋅ − ⋅ − ⋅π π π π

( ) ( )

Also erhält man als Ergebnis:

{ }F f j jm n= = − − − +FN ( , , , )6 2 2 2 2 2

Bei dieser Rechnung zeigt sich ein erstaunlicher Effekt: die Exponenten innerhalb derExponentialfunktion kommen mehrfach vor. Da die komplexe Exponentialfunktion außerdemperiodisch (mit j2π) ist, sind auch Exponenten wie 6/4 und 2/4 identisch, d.h. sie ergeben dengleichen Wert. Diese Tatsache sollte man sich zunächst einmal im Hinterkopf behalten.

Zusammenfassende Darstellung über die diskreten Fourieroperatoren:

Diskreter Fourieroperator: { }F F f f em N n n

j mnN

n

N

= = ⋅−

=

−

∑ 2

0

1 π(8)

Inverser Diskreter Fourieroperator: { }f F FN

F en N m m

j mnN

m

N

= = ⋅ ⋅−

=

−

∑1 2

0

11 π(9)

Daß Gleichung (9) wirklich die Umkehrung von (8) ist, läßt sich leicht durch ineinander Einsetzenzeigen.

Für (9) gibt es noch eine alternative Rücktransformationsgleichung, die bei einerRechnerimplementation oftmals von Vorteil ist. Sie lautet:

( )

fN

F eN

F e

NF e

n m

j mnN

m

N

m

j mnN

m

N

m

j mnN

m

N

= ⋅ ⋅ = ⋅ ⋅

= ⋅ ⋅

=

−

=

−

−

=

−

∑ ∑

∑

1 1

1

2

0

1 2

0

1

2

0

1

π π

π

*

**

*

(10)

Der Vorteil in (10) ist der, daß für die eigentliche Transformation der gleiche Algorithmusverwendet werden kann. Nur die Eingangsfolge und die Ausgangsfolge müssen jeweils in ihrkonjugiert Komplexes umgewandelt werden.

Wie man sieht, benötigt die Auswertung der Gleichungen (8) bis (10) Rechenoperationen, die auseiner Multiplikation und anschließender Addition bestehen (multiply-and-accumulate = MAC).Daher bietet es sich an, für die Auswertung der Rechnung einen Signalprozessor zu verwenden,der bekanntlich diese MAC-Operation sehr schnell durchführen kann.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-7-

Der Vollständigkeit halber sei noch erwähnt, daß die Darstellung nicht nur in komplexer Formmöglich ist. Falls für eine Anwendung direkt Betrag und Phase von Interesse sind, so ist die üblicheUmrechnung in der Form:

F F Fm m m= +(Re ) (Im )2 2

(11)

arg

,Re Im

,Re Im

arctan ImRe

,Re

arctanImRe

,Re

F

F F

F F

FF

F

FF

F

m

m m

m m

m

mm

m

mm

=

= ∧ >

− = ∧ <

>

+ >

π

π

π

20 0

20 0

0

0

jederzeit möglich.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-8-

Die diskrete Fouriertransformation und das Abtasttheorem

Bei der Herleitung der DFT-Transformationsgleichungen wird eine periodische Funktion imZeitbereich unterstellt. Dies läßt sich jedoch mit Hilfe der Systemtheorie begründen. Tastet maneine Funktion im Zeitbereich ab, so entsteht nach Shannon eine periodische Funktion imFrequenzbereich. Entwickelt man eine periodische Funktion in eine Fourierreihe, so entstehen diediskreten Fourierkoeffizienten im Frequenzbereich.

Um dies noch einmal gegenüber zu stellen:

Abtastung im Zeitbereich (also Diskretisierung) => Periodizität im Frequenzbereich

Periodizität im Zeitbereich => Diskrete Koeffizienten im Frequenzbereich

Bei der diskreten Fouriertransformation hat man, wie bei jedem numerischen Verfahren, dasProblem, daß man eine Funktion nur mit einer bestimmten Anzahl von Stützstellen beschreibenbzw. speichern kann. Daher liegen bei der DFT auch im Spektralbereich diskrete Koeffizienten vor,zugleich ist das Spektrum periodisch. Mit den obigen Sätzen der Systemtheorie folgt zwingend,daß dann die Zeitfunktion diskret (ist durch Abtastung erfüllt) und periodisch sein muß.

In allen zuvor verwendeten Gleichungen wird für den Index der Folge im Zeitbereich der Buchstaben, für den Index der Folge im Frequenzbereich der Buchstabe m verwendet. Dies allein ist natürlichetwas unbefriedigend, da für eine physikalische Interpretation auch physikalische Größen benötigtwerden.

Die Zuordnung des Index n zu einer bestimmten Zeit ist relativ naheliegend. Es gilt:

t n T n Nn Ab= ⋅ ≤ ≤ −,0 1 (12)

Für die Zuordnung im Frequenzbereich muß man zuerst kurz in die Theorie der Fourierreihenabschweifen. Für eine Funktion der Periode T weiß man, daß die Abstände der Spektrallinien den

Wert ∆ω = 2πT

besitzen. Da bei der Herleitung der DFT-Transformationsgleichungen ein

periodisches Zeitfenster der Periode TF angenommen wurde, gilt somit:

∆ω = =⋅

2 2π πT N TF Ab

(13)

Die Gleichung (13) wird auch als "spektrale Auflösung" der DFT bezeichnet, da sie angibt, mitwelcher Genauigkeit die Darstellung im Frequenzbereich erfolgen kann.

Somit kann man analog zum Zeitbereich die folgende Gleichung aufstellen:

ω π πmAb

Abm mN T

mN

f m N= ⋅ = ⋅⋅

= ⋅ ⋅ ≤ ≤ −∆ω 2 2 0 1, (14)

bzw., wenn man sich nicht für die Kreisfrequenz, sondern für die Frequenz interessiert:

f m mN T

mN

f m NmAb

Ab= ⋅ = ⋅⋅

= ⋅ ≤ ≤ −∆ω2

1 0 1π

, (15)

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-9-

Da bei der DFT im Zeitbereich eine Abtastung vorliegt, muß für den Zeitausschnitt, der abgetastetwurde, selbstverständlich das Nyquist-Kriterium erfüllt sein, das besagt:

f fAbmax < ⋅12

(16)

Das Abtasttheorem besagt aber noch etwas: durch die Abtastung wiederholt sich das Spektrumperiodisch mit der Abtastfrequenz (Aliasing-Effekt), und die Werte zwischen halber Abtastfrequenzund Abtastfrequenz sind eine Spiegelung der Wert zwischen 0 und der halben Abtastfrequenz.

ffabfab0,5fab-0,5 fab2

Bild 3: Periodisches Spektrum durch Abtastung im Zeitbereich

Betrachtet man nun aber Gleichung (15), so sieht man, daß für mN>2

die Frequenzen oberhalb

der halben Abtastfrequenz liegen. Was bedeutet dies für die DFT?

Wegen der Spiegelung an der halben Abtastfrequenz sind die DFT-Werte für N

m N2

1 1+ ≤ ≤ −redundant, das heißt, bereits der halbe transformierte Wertesatz enthält die volle Information überdas Signal im Zeitbereich. Wertet man also die transformierte Folge aus, oder stellt sie grafisch alsSpektrum dar, so genügt es mit dem N/2-ten Wert aufzuhören. Man könnte nun natürlich auf dieIdee kommen, generell auf diese redundanten Werte zu verzichten. Für die Rücktransformationaber werden alle N Werte benötigt, daher muß man diese redundanten Werte weiterhin berechnenund im Speicher halten, wird sich aber für Auswertungen auf den halben Datensatz beschränken.

Die Periodizität im Frequenzbereich hat auch eine Erweiterung der Gleichungen (14) und (15 zurFolge. Da sich die Frequenzwerte auch oberhalb der Abtastfrequenz wiederholen, kann dieEinschränkung von m auf den Bereich 0..N-1 entfallen. Es gilt dann:

f m mN T

mN

fmAb

Ab= ⋅ = ⋅⋅

= ⋅∆ω2

1π

(16)

und das Spektrum besitzt an der allgemeinen Stelle m den Wert:

XmN

f XAb m N( ) ( mod )⋅ = (16)

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-10-

Abschließend noch einmal eine wichtige Warnung:Alle Aussagen zur Transformation von Zeitfolgen gelten nur, wenn das Abtasttheorem tatsächlicherfüllt ist. Dies muß in der praktischen Anwendung unbedingt sichergestellt sein (Antialiasing-Filter!), da sich sonst gravierende Fehler einschleichen können. Denn der mathematischeAlgorithmus wird in jedem Fall ein Ergebnis liefern. Nur wenn das Nyquist-Kriterium erfüllt ist,stimmt das mathematische Ergebnis mit dem physikalischen Spektrum überein, sonst nicht.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-11-

Rechengesetze für den diskreten Fourieroperator

Allein die Definition der diskreten Fouriertransformation ist noch nicht ausreichend umfestzustellen, welchen Wert diese Transformation hat. Denn für die Anwendbarkeit ist es wichtig zuwissen, welche der Sätze über die kontinuierliche Fouriertransformation auch im diskreten Fallerhalten bleiben. Denn nur dann, wenn ein Großteil der Rechengesetze aus demzeitkontinuierlichen Fall auch im zeitdiskreten Fall erhalten bleibt, kann die DFT alsrechnerbasierter Ersatz für die kontinuierliche Fouriertransformation angesehen werden.

Bevor jedoch auf diese Problematik eingegangen wird, soll am Anfang eine kurze Wiederholungfür die Rechengesetze für Folgen stehen.

Exkurs: Rechnen mit (endlichen) Zahlenfolgen

Bei einer Zahlenfolge wird jeder natürlichen Zahl aus dem Definitionsbereich eine beliebige reelleoder komplexe Zahl zugeordnet. In der Regel geschieht dies über eine Berechnungsvorschrift,kann aber auch auf anderem Wege erfolgen.

Schreibweise: f f a an n n: , : ( ) ,ℵ → ℜ = ∈ ℜ

Beispiele: Für Folgen, die durch Rechenvorschriften gegeben sind:

f nn:= fn

nnn: ,= + >

2 10

Für sprachliche Vorgaben:

fn:,

= 0 n ist eine gerade Zahl1 ,n ist eine ungerade Zahl

Mit Folgen wird gerechnet, indem die Verknüpfungen auf jedes einzelne Element der Folgeangewandt werden.

Addition: f a b a bn n n n n= + = +: ( ) ( )

Multiplikation: f a b a bn n n n n= ⋅ = ⋅: ( ) ( )

Skalare Multiplikation: f a an n n= ⋅ = ⋅ ∈λ λ λ: ( ) , C

Faltung: f a b a b a b b an n n r n rr

n r rr

n n= = ⋅ = ⋅ = ∗−∈ℵ

−∈ℵ

∑ ∑* :

Korrelation: k a b a bn n r n rr

( , ) = ⋅ +∈ℵ∑

Beispiele: Sei an

bn

nn n= =+

11

2

, . Dann gilt:

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-12-

f a bn

nn

n nn nn n n= + = +

+= + +

+1

11

1

2 3

( )

f a bn

nn

nnn n n= ⋅ = ⋅

+=

+1

1 1

2

f ann n= ⋅ =33

f a bn

nn n r

rrn n n

r

= ∗ = ∗+

=−

⋅+∈ℵ

∑( ) ( ) ( )1

11

1

2 2

Wichtig ist insbesondere, daß Teile der Folge zu Null gesetzt werden können, die Rechengesetze(vor allem die Faltung) bleiben dann dennoch erhalten:

Beispiel: fn n

nn = <≥

2 240 24

,,

ist eine gültige Folge.

Dieser Typ Folgen, bei dem ab einem bestimmten Wert alle Folgewerte identisch 0 gesetztwerden, wird häufig auch als endliche Folge bezeichnet.

Nun geht es zurück zur eigentlichen Thematik: der DFT

Linearität:

Die Linearität ist eine der wichtigsten Eigenschaften, die eine Transformation erfüllen muß, dasonst keinerlei Parallelen beim Rechnen in Zeit- und Frequenzbereich bestehen. In anderenWorten: das Prinzip der linearen Superposition muß gelten.

{ }

{ } { }

F ( )

F F

N

N N

ax by ax by

a x b y

a x b y

n n n n

j mnN

n

N

n

j mnN

n

N

n

j mnN

n

N

n n

+ = +

= +

= +

−

=

−

−

=

− −

=

−

∑

∑ ∑

e

e e

2

0

1

2

0

1 2

0

1

π

π π

Wegen der Linearität des Summenzeichens gilt dieses Gesetz wirklich, wodurch eine wesentlicheVoraussetzung für die Verwendbarkeit geschaffen ist.

Verschiebungssätze:

In der kontinuierlichen Fouriertransformation sind auch die Verschiebungssätze für den Zeit- undFrequenzbereich wichtig, da hier aus der Verschiebung z.B. im Frequenzbereich Rückschlüsse aufdie Veränderung des Zeitsignals möglich sind. Auch diese Verschiebungssätze sind erfüllt.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-13-

Verschiebung im Zeitbereich:

{ }

{ }

F

F

N

( )

N

x x

x

x

x

n n

j mnN

n

N

n

j mN

n

n

N

j mN

n

j mnN

n

N

j mN

n

− −−

=

−

− +

=−

− −

− −

=

−

−

=

=

= ⋅

= ⋅

∑

∑

∑

α απ

π α

α

α

π α π

π α

e

e

e e

e

2

0

1

21

2 2

0

1

2

Verschiebung im Frequenzbereich:

{ }

F

F

N

N

e

e

j mN

n m

m

j mN

n

x X

X x

2

1 2

π α

α

απ α

⋅

=

= ⋅

−

−−

An dieser Stelle ist ein wichtiger Hinweis angebracht:

Die obigen Verschiebungssätze beziehen sich ja auf die Tatsache, daß die Zeitfunktion periodischist. Dies bedeutet aber, daß die Funktion zyklisch verschoben wird, was an dem einen Rand desZeitfensters hinausgeschoben wird, erscheint am anderen Fensterrand wieder. Eine Grafikverdeutlicht diesen Zusammenhang.

0 1 2 3 4 5 6 7 n

xn

0 1 2 3 4 5 6 7 n

xn-2

Folge xn nach rechts verschobene Folge xn-2

Bild 4: Zyklische Verschiebung von Folgen

Diese Tatsache zu verstehen fällt nicht schwer, da man mit periodischen Funktionen arbeitet.Häufig wird die zyklische Verschiebung dennoch falsch eingesetzt, da man von der Fourier- oderLaplacetransformation gewohnt ist, daß eine Zeitfunktion, die bei t=0 beginnt, nach einerRechtsverschiebung um t0 eben erst bei t0 beginnt. Bei der zyklischen Verschiebung gilt dies abernicht - nach wie vor sind zum Zeitpunkt t=0 Werte vorhanden.

Dem aufmerksamen Beobachter wird nicht entgangen sein, daß man die obigeRechtsverschiebung um 2 auch durch eine Linksverschiebung um 6 hätte darstellen können, alsoals xn+6.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-14-

Differenzen-Satz:

Dieser Satz entsteht durch das Analogon zwischen der Differentiation im kontinuierlichen Fall undder Differenzenbildung im diskreten Fall. Für eine Ableitung existiert bekanntlich die Näherung:

dxdt

xt

x xt

n n≈ = − −∆∆ ∆

1 , womit die Entstehung dieses Satzes hinreichend erklärt

sein dürfte. Die Verschiebung xn-1 ist wie zuvor als eine zyklische Verschiebung zu interpretieren.

{ }

{ }

F x x x x

x x

x x

x

F x

N n n n n

j mnN

n

N

n

j mnN

n

N

n

j mnN

n

N

n

j mnN

n

N

n

j mN

n

n

N

j mN

n

j mnN

n

N

jmN

N n

− = −

= −

= −

= − ⋅

= − ⋅

− −−

=

−

−

=

−

−−

=

−

−

=

− − +

=−

−

− −

=

−

−

∑

∑ ∑

∑ ∑

∑

1 1

2

0

1

2

0

1

1

2

0

1

2

0

1 2 1

1

2

2 2

0

1

2

1

1

( )

( )

( )

( )

e

e e

e e

e e

e

π

π π

π π

π π

π

Summationssatz:

Ein Summationssatz wäre das Analogon zum Integrationssatz bei der kontinuierlichenFouriertransformation, allerdings gibt es bei der DFT keine sinnvolle Definition einesSummationssatzes. Zwar ist eine Summe über die Koeffizienten im Zeitbereich denkbar, es gibtallerdings keinen vernünftigen Zusammenhang zum Frequenzbereich.

Faltungssatz:

Um sich die Bedeutung des Faltungssatzes zu veranschaulichen, ein kurzer Rückblick auf dieSystemtheorie.

Wird ein System mit einer Übertragungsfunktion g t( ) am Eingang durch eine Funktion e t( )angeregt, so erscheint am Ausgang die Funktion a t e t g t( ) ( )* ( )= . Da die Faltungsoperation,gerade bei der Verkettung von mehreren Übertragungsgliedern, nur noch sehr kompliziertausgeführt werden kann, macht man den Schritt in den Frequenzbereich. Man ordnet derÜbertragungsfunktion über die Fouriertransformation die Funktion G( )ω , und der Eingangsgröße

die Funktion E( )ω zu. Am Ausgang erscheint dann im Frequenzbereich die Antwort mit

A E G( ) ( ) ( )ω ω ω= ⋅ , und dies ist durch die gewöhnliche Multiplikation leicht zu berechnen.

Die Erhaltung dieses Satzes bei der DFT ist ebenfalls unabdingbar, da hiermit erst einerechnergestützte Systemanalyse möglich wird, und Systemantworten aus Zahlenfolgenberechenbar sind.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-15-

{ }F * FN N

( )

x y x y x y e

x y e x y e

x e y e

n n rr

N

n r rr

N

n rn

N jmnN

rr

N

n r

j mnN

n

N

rn

N

n r

j mnN

r

N

r

j mrN

n r

j mN

n r

n

N

r

N

=

=

⋅

= ⋅

= ⋅

= ⋅ ⋅

=

−

−=

−

−=

− −

=

−

−−

=

−

=

−

−−

=

−

−−

− −

=

−

=

−

∑ ∑∑

∑∑ ∑∑

∑

0

1

0

1

0

1 2

0

1 2

0

1

0

1 2

0

1

2 2

0

1

0

1

π

π π

π π{

{ } { }

∑ ∑∑= ⋅ ⋅

= ⋅

− −

=

−

=

−

Periodizitä tvon und

exp

N NF Fy

r

j mrN

n

j mnN

n

N

r

N

n n

n

x e y e

x y

2 2

0

1

0

1 π π

Und umgekehrt gilt auch (Beweis verläuft analog):

{ } { } { }FN x yN

x yn n n n⋅ = ⋅1F * FN N

Somit bleibt die Aussage, daß einer Faltung im Zeitbereich eine Multiplikation im Frequenzbereichentspricht, und umgekehrt, in der Tat richtig.

Somit kann eine Faltung im Zeitbereich mit folgenden Rechenvorschriften ausschließlich aufMultiplikationen von Folgen zurückgeführt werden (sogenannte schnelle Faltung):

{ } { }{ }x y x yn n n n* = ⋅−F F FN1

N N

Beispiel:

Zu diesem wichtigen Satz soll ein kurzes Beispiel die Richtigkeit der Aussagen verdeutlichen.

Es sind 2 Polynome gegeben: p x x q x x( ): , ( ):= + = −1 2 1 3

Diese 2 Polynome sind zu multiplizieren, und es ist das Produktpolynom zu ermitteln:

Lösungsmethode a:

Man multipliziert die beiden Polynome schriftlich aus und erhält:

( )( ) ( ) ( ) ( )( )pq x p x q x x x

x x x

x x

= ⋅ = + −= − + −= − −

1 2 1 3

1 3 2 6

1 6

2

2

Nun gibt es in der Mathematik einen Satz, der in etwa besagt: 2 Polynome zu multiplizieren heißt,ihre Koeffizienten zu falten. Dieser Sachverhalt soll einmal unbewiesen akzeptiert werden. Hierausergibt sich die

Lösungsmethode b:

Die Faltung soll durch eine Multiplikation der transformierten Polynom-Koeffizienten erfolgen. Dazuschreibt man die Polynom-Koeffizienten als Folgen:

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-16-

p q= = −( , , , ) , ( , , , )1 2 0 0 1 3 0 0

und wendet man DFT auf die beiden Folgen an, mit dem Ergebnis:

P j j Q j j= − − + = − + −( , , , ) , ( , , , )31 2 11 2 2 1 3 41 3

Multiplikation der transformierten Folgen:

PQ j j= − + − −( , , , )6 7 4 7

Die Folge PQ wird nun mit der inversen DFT zurücktransformiert, und man erhält die Folge:

pq = − −( , , , )1 1 6 0 , bzw. in Polynomschreibweise ( )( )pq x x x= − −1 6 2

Die Lösungsmethode b sieht auf den ersten Blick etwas wie Spielerei aus. Aber gerade beiVerschlüsselungsalgorithmen werden Polynommultiplikationen mit sehr hoher Ordnung derPolynome benötigt. Und dann ist das Verfahren b in der Tat schneller, vor allem wenn zurDurchführung der DFT der FFT-Algorithmus (dazu später mehr) eingesetzt wird ([LOCH]).

Korrelationsatz:

Die Korrelationsfunktion zweier Funktionen ist vor allem für die Meßtechnik von Bedeutung. EineVielzahl von Meßmethoden arbeitet mit dem Prinzip der Korrelation, daher liegt der Gedankenahe, auch diesen Satz der kontinuierlichen Funktionen auf die zeitdiskreten Funktionen zuübertragen.

{ }F ( , ) FN N

( )

k x y x y x y e

x y e x y e

x e y e

n n n rr

N

n r rr

N

n rn

N jmnN

rr

N

n r

j mnN

n

N

rn

N

n r

j mnN

r

N

r

jmrN

n r

jmN

n r

n

N

r

=

=

⋅

= ⋅

= ⋅

= ⋅ ⋅ ⋅

=

−

+=

−

+=

− −

=

−

+−

=

−

=

−

+−

=

−

+− +

=

−

=

∑ ∑∑

∑∑ ∑∑

∑

0

1

0

1

0

1 2

0

1 2

0

1

0

1 2

0

1

2 2

0

1

π

π π

π π

( )

( ){ }( ) { }

0

1 2

0

1 2

0

1

2

0

1 2

0

1

N

r

jmrN

r

N

n r

jmN

n r

n

N

r

j mrN

r

N

n

j mnN

n

N

n n

x e y e

x e y e

x y

−

=

−

+− +

=

−

−

=

− −

=

−

∑ ∑ ∑

∑ ∑

= ⋅

⋅ ⋅

= ⋅

⋅ ⋅

= ⋅

π π

π π

**( )

**

N* *

NF F

Falls die Zeitfolge xn rein reell ist, vereinfacht sich der Zusammenhang noch etwas:

{ } { }( ) { }FN k x y x yn n n n n( , ) F FN

*

N= ⋅

Parseval'sches Theorem:

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-17-

Das Parseval'sche Theorem sagt anschaulich aus, daß die Energie eines Signals im Zeitbereichgleich seiner Energie im Frequenzbereich ist. Daß diese Aussage auch im Falle der diskretenFouriertransformation gelten muß, ist klar: eine Energie kann sich nicht durch eine anderemathematische Darstellung plötzlich erhöhen oder vermindern.

Es gilt:

fN

F e fN

F en m

j mnN

m

N

n m

j mnN

m

N

= ⋅ ⇒ = ⋅=

− −

=

−

∑ ∑1 12

0

1 2

0

1π π( ) ( )* *

Diese Aussage wird im Folgenden verwendet:

f f f fN

F e

NF f e

NF F

NF

nn

N

n nn

N

n mm

N j mnN

n

N

m nn

N j mnN

m

N

m mm

N

mm

N

2

0

1

0

1

0

1 2

0

1

0

1 2

0

1

0

1

2

0

1

1

1 1

1

=

−

=

−

=

− −

=

−

=

− −

=

−

=

−

=

−

∑ ∑ ∑∑

∑∑ ∑

∑

= ⋅ = ⋅

= ⋅ ⋅ = ⋅ ⋅

= ⋅

( )* *

* *

π

π

Man hat also das Parseval'sche Theorem in der Form:

fN

Fnn

N

mm

N2

0

12

0

11

=

−

=

−

∑ ∑= ⋅

Symmetriesätze:

Aus der Theorie der Fouriertransformation und der Fourierreihen kennt man gewisse Symmetrien,die sich bei ungeraden oder geraden Funktionen im Frequenzbereich einstellen. Die beidenwesentlichen Symmetrien sind hierbei:

Zeitfunktion reell und gerade ⇒ Spektrum rein reellZeitfunktion reell und ungerade ⇒ Spektrum rein imaginär

Diese Symmetrien existieren natürlich auch bei der diskreten Fouriertransformation. Es gibt bei derAnwendung allerdings ein kleines Problem: es stellt sich nämlich die Frage, was eine gerade odereine ungerade periodische Folge sein soll. Denn in der Mathematik sind diese Begriffe nichtdefiniert.

Daher wird folgende Vereinbarung getroffen:

Ein periodische Folge heiße ungerade (gerade), wenn ihre zugehörige Zeitfunktion, aus der sieentstanden ist, ebenfalls ungerade (gerade) ist.

Mit dieser Vereinbarung sind nun folgende Aussagen möglich:

Zeitfolge reell und gerade ⇒ diskretes Spektrum rein reellZeitfolge reell und ungerade ⇒ diskretes Spektrum rein imaginär

Dem aufmerksamen Leser ist wahrscheinlich aufgefallen, daß bisher für die Zeitfolgen keineEinschränkung auf reelle Folgen gemacht wurde. Dies hat den einfachen Grund, weil die DFT auchfür komplexwertige Folgen definiert und anwendbar ist. In der Technik wird man aber fast immer

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-18-

mit reellwertigen Folgen arbeiten. In diesem Fall vereinfachen sich einige Sätze etwas (z.B.Korrelation, Parseval'sches Theorem), sind dann allerdings nicht mehr allgemeingültig. Dem Autorwar es aber wichtiger, eine vollständige Definition der DFT und ihrer Eigenschaften niederzulegen,und nicht die rechentechnischen Vereinfachungen ins Detail auszureizen.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-19-

Gegenüberstellung DFT und kontinuierliche Fouriertransformation

Kontinuierliche Fouriertransformation Diskrete FouriertransformationTransformationsgleichung

F( ):ω = { }f t f t e dtj t( ) ( )= ⋅ −

− ∞

∞

∫ ω { }FN f f en n

j nmN

n

N

= ⋅−

=

−

∑ 2

0

1 π

Rücktransformationsgleichung

f t( ):= { }−

− ∞

∞

= ⋅∫1 12

F F e dj t( ) ( )ωπ

ω ωω { }FN−

=

−

= ⋅ ⋅∑1 2

0

11F

NF em m

j nmN

m

N π

Linearität

{ }a f t b g t a F b G⋅ + ⋅ = ⋅ + ⋅( ) ( ) ( ) ( )ω ω { } { } { }F F FN N Nax by a x b yn n n n+ = +Verschiebung im Zeitbereich

{ }f t a e Fj a( ) ( )− = ⋅− ω ω { } { }F FN Nx xn

j mN

n−−

= ⋅απ α

e2

, a N<Verschiebung im Frequenzbereich

{ }e f t F ajta ⋅ = −( ) ( )ωFN e

j mN

n mx X2π α

α⋅

= − , a N<

Differentiation im Zeitbereichd

df t

tj F

( )( )

= ⋅ω ω { } { }F x x F xN n n

j mN

N n− = − ⋅−−

1

21( )e

π

Integration im Zeitbereich

fj

F St

( ) ( ) ( ) ( )τ τω

ω π δωd− ∞∫

= + ⋅ ⋅10

keine sinnvolle Definition

Faltung im Zeitbereich{ }f t g t F G( ) ( ) ( ) ( )∗ = ⋅ω ω { } { } { }F * F FN N Nx y x yn n n n= ⋅

Faltung im Frequenzbereich{ }f t g t F G( ) ( ) ( ) ( )⋅ = ∗ω ω { } { } { }FN x y

Nx yn n n n⋅ = ⋅1

F * FN N

Korrelation reeller Funktionen / Folgen

{ } ( )k F Gf g,*( ) ( )= ⋅ω ω { } { }( ) { }F F FN N Nk x g x yn n n n n( , )

*= ⋅Parseval'sches Theorem

f t t F( ) ( )2 2d d− ∞

∞

− ∞

∞

∫ ∫= ω ω fN

Fnn

N

mm

N2

0

12

0

11

=

−

=

−

∑ ∑= ⋅

(Für die obigen Sätze findet sich in der Literatur kaum eine einheitliche Darstellung. [ENDE] und[OPPE] stellen sehr viele Sätze inklusive Beweis vor, während [BRIG] ziemlich ausführlich auf diediskrete Faltung und Korrelation eingeht.)

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-20-

Meßtechnische Probleme der DFT - die Wahl des Zeitfensters

Um die prinzipielle Problematik der meßtechnischen Anwendung der DFT aufzuzeigen, muß zuBeginn eine kurze Analyse der zu untersuchenden Signale stehen. Daß es überhaupt Probleme beider Anwendung der DFT auf kontinuierliche Signale gibt, sollte leicht einzusehen sein. Schließlichwendet man ein numerisches Näherungsverfahren (also diskretes Verfahren) auf die (heile)analoge Welt an, und muß damit auch gewisse Fehler in Kauf nehmen.

Die im wesentlichen auftauchenden Signale lassen sich in 3 Gruppen einteilen:

a. periodische Signale mit einer solchen Frequenz, daß die Abtastfrequenz ein ganzzahligesVielfaches der Signalfrequenz ist

b. ein beliebiges periodisches Signal oder periodisches Signalgemischc. ein transientes (d.h. nichtperiodisches) Signal

Ein Signal der Gruppe a. ist unproblematisch. Wendet man die DFT auf dieses Signal an, so erhältman in der Tat im Spektrum nur eine einzige Linie, deren Amplitude linear von der Amplitude desSignals abhängt. Allerdings ist dieser Fall eher akademischer Natur: in der Regel wendet man eineFrequenzanalyse ja auf Signale an, deren Frequenz unbekannt ist. Wie soll da die Forderung, daßdie Abtastfrequenz ein Vielfaches der Signalfrequenz ist, überhaupt eingehalten werden?

Man kommt also sehr schnell zu dem Signaltyp b., einem beliebigen periodischen Signal. Undgenau hier treten 2 Fehlerquellen der DFT auf.

Zum einen kann es vorkommen, daß ein Signal mit einer bestimmten Frequenz keine geeignetLinie im diskreten Spektrum hat. Zum Beispiel wurde die Auflösung so gewählt, daß bei 990Hz und1010Hz jeweils eine diskrete Spektrallinie liegt. Analysiert man nun ein Signal mit einer Frequenzvon 1000Hz, so gibt es zwangsläufig ein Problem: an welchen Stellen soll jetzt die Signalenergieim Frequenzbereich dargestellt werden? Führt man diese Rechnung durch, so wird man feststellen,daß sowohl bei 990Hz, als auch bei 1010Hz jeweils eine Spektrallinie erscheinen wird. Es ist daheroffensichtlich, daß eine Spektrallinie nach Anwendung der DFT nicht automatisch bedeutet, daßein Signal mit exakt dieser Frequenz im Zeitbereich vorliegt. Vielmehr ist es so, daß in demFrequenzbereich zwischen 2 Spektrallinien eine bestimmte Signalenergie vorliegt, die sich in derHöhe der Spektrallinie darstellt.

Die folgenden Bilder verdeutlichen diese Auswirkungen.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-21-

Bild 5: Ist die Abtastfrequenz kein Vielfaches der Signalfrequenz, so entstehen zusätzliche Linienim Spektrum (rechts); a) Zeitsignal, b) Spektrum mit Einhüllender

Der andere Fehler, der entsteht, ist wesentlich subtiler. Die DFT unterstellt bei ihrermathematischen Herleitung ein periodisch fortgesetztes Zeitsignal. Es gibt aber durchaus einenUnterschied, wie das Signal periodisch fortgesetzt wird, das folgende Bild zeigt diesen Unterschied.

T

t

F

s(t)

reales Zeitsignal

durch DFT periodisch fortgesetztes Zeitsignal

Bild 6: Periodische Fortsetzung durch DFT

Man sieht deutlich, daß zur Zeit TF eine Sprungstelle auftaucht, die im physikalischen Signal nochnicht vorhanden war. Aus der Theorie der Fourier-Reihen weiß man aber auch, daß Sprungstellenzu Frequenzanteilen führen. Daher erzeugt die mathematische Berechnung der DFT desphysikalischen Signals Frequenzanteile an Stellen, an denen eigentlich keine Frequenzanteilevorhanden sind. Dieser Effekt ist auch als Leck-Effekt (leakage) bekannt.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-22-

Der erste Lösungansatz, die Abtastfrequenz so zu wählen, daß die mathematische Periode mit derphysikalischen Periode zusammenfällt, scheidet aus zuvor genannten Gründen aus. Daher mußman sich mit der Ursache der Sprünge befassen, und versuchen, die Sprunghöhe zu verkleinern.

Ein Sprung an der periodischen Fortsetzung wird im wesentlichen dadurch verursacht, daß dieAbtastung schlagartig beginnt und schlagartig endet. Mathematisch ausgedrückt, multipliziert mandie abzutastende Zeitfunktion mit einem Rechteckfenster, und wertet den entstehenden Ausdruckaus:

Sei s(t) die zu untersuchende Zeitfunktion. Als unterlegtes Zeitfenster verwendet man einRechteck, daß wie folgt definiert ist:

w tt nT

sonstAb( )

,,

=≤ <

1 00

Der Abtastvorgang, also quasi das Einschalten des AD-Umsetzers und das Ausschalten, läßt sichdurch die Fensterfunktion w(t) beschreiben.

Die Fensterfunktion wird mit dem Eingangssignal multipliziert, und das entstehende Signal wird derDFT zugeführt:

s t s t w ts t t nT

sonstAb

0

00

( ) ( ) ( )( ) ,

,= ⋅ =

≤ ≤

Die Funktion w(t) weist an ihren Rändern Unstetigkeitstellen auf. Daher hatte man die Idee,Fensterfunktionen zu verwenden, die an den Rändern stetig gegen Null gehen, so daß dieperiodische Fortsetzung nun keine Sprungstellen mehr besitzt.

Eine Fensterfunktion wird wie folgt angewendet:

Sei w(t) eine Fensterfunktion, für die gilt:

w tf t t nT

sonstAb( )

( ) ,,

=≤ <

00

Außerdem sei fn die zeitdiskrete Wertefolge. Die "gefensterte" Ausgangsfolge berechnet sich dannzu:

g f w n T n Nn n Ab= ⋅ ⋅ = −( ) , ,...,0 1 (17)

Weiter unten sind einige gängige Zeitfensterfunktionen, sowie ihre grafische Darstellung,zusammengestellt.

Nun ist aber mit der alleinigen Anwendung eines Zeitfenster das Problem noch nicht vollständigabgehandelt, denn ein Zeitfenster beeinflußt selbstverständlich auch die Spektraldarstellung desSignals.

Die Multiplikation des Signals im Zeitbereich mit einer Fensterfunktion stellt im Frequenzbereicheine Faltung dar, d.h. das Spektrum des Signals wird mit dem Spektrum des Fenster gefaltet. AusZeit- und Platzgründen kann leider nicht ausführlich auf die konkrete Auswirkung eines Zeitfenstersauf das Ausgangsspektrum eingegangen werden. Im wesentlichen sollte der Leser folgendeAussage behalten: im ursprünglichen Spektrum werden die physikalisch vorhandenen"Frequenzspitzen" etwas in die Breite gezogen, dafür aber die durch die periodische Fortsetzungentstandenen Frequenzen bedämpft.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-23-

Ausführlichere Darstellungen der Auswirkungen von Zeitfenstern finden sich in [SCHR], [BRIG]oder [ENDE], aber für ein umfassendes Verständnis ist es am besten, verschiedene Spektren mitZeitfensterung zu berechnen und sich die Unterschiede zu betrachten.#

Im folgenden soll noch kurz ein Überblick über die Bewertungskriterien und die Definitionen häufigverwendeter Fensterfunktionen gegeben werden.

Das folgende Bild zeigt die Definition der Bewertungskriterien, aber auch das Spektrum einesZeitfensters. Denn für alle Zeitfenster sind die Spektren von der Form her ähnlich.

Bild 7: Kriterien zur Beurteilung eines Fensters

Verhältnis aus der Amplitude des höchsten Nebenzipfels und der Amplitude des Hauptzipfels

Die Fouriertransformation einer Fensterfunktion liefert bei ω=0 die maximale Amplitude desHauptzipfels. Die Amplituden der Nebenzipfel sind geringer. Das Verhältnis

a = Amplitude des höchsten NebenzipfelsAmplitude des Hauptzipfels

wird für den Vergleich verschiedener Fensterfunktionen benutzt.

Maximale Abtastfehler

Die Spektrallinien einer abgetasteten Funktion fallen nicht notwendigerweise mit den Nullstellender Fouriertransformierten eines Fensters zusammen. Die Spektrallinien des Fensters liegen imAbstand ∆ω. Die Amplitude des Hauptzipfels bei ω=0 ist größer als die Amplitude bei der Frequenz

ω = ∆ω2

. Das Verhältnis

b ==Amplitude der Fenster - Fouriertransformierten bei

Amplitude der Fenster - Fouriertransformierten bei = 0

ω

ω

12

∆ω

gibt an, umwieviel eine Amplitude höchstens falsch gemessen wird. Es wird als maximalerAbtastfehler bezeichnet.

# Dies ist übrigens mit dem ausgegebenen Demoprogramm in PASCAL möglich.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-24-

Breite des Hauptzipfels

Fensterfunktionen, bei denen die Nebenzipfel niedrig bleiben, haben einen besonders breitenHauptzipfel. Dies ist ungünstig und führt zu einem Auseinanderlaufen der Spektrallinien. ZurCharakterisierung des Hauptzipfels dient die 3-dB-Grenzfrequenz. Dies ist die Frequenz, bei derdie Amplitude des Hauptzipfels um 3dB abgefallen ist. Das Verhältnis

Amplitude bei Amplitude bei

ω = =−

0 33f

dBdB

$

definiert die Frequenz f-3dB. Sie ist ein Maß für die Breite des Hauptzipfels. (aus [SCHR]).

Zusammenstellung wichtiger Fensterfunktionen und deren Daten

Die Fensterfunktionen sind bereits für den diskreten Fall angegeben, d.h. als Funktion von n, undnicht als Funktionen der Zeit t. Dies erleichtert die Rechnerumsetzung. Für Werte außerhalb desBereichs 0,...,N-1 sind alle Fensterfunktionen identisch 0.

Rechteckfenster:

Zeitfunktion: w n n N0 1 0 1( ) , ,...,= = −

Kontinuierliches Betragsspektrum: W T si fTF F0( ) ( )ω π=

Höchster Nebenzipfel: a dB= − =13 0 224$ ,maximaler Abtastfehler: b = 0 64,Breite des Hauptzipfels: c f= ⋅0 45, ∆

Bild 8: Abtastwerte und Spektralfunktion des Rechteckfensters

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-25-

Dreieckfenster:

(auch Bartlett-Fenster genannt)

Zeitfunktion: w n

nN

n N

w N n nN

N1

1

20

2

21

( ) /, ,...,

( ) , ,...,=

=

− = −

Kontinuierliches Betragsspektrum: WT

sifTF F

1

2

2 2( ) ( )ω π=


Bild 9: Abtastwerte und Spektralfunktion des Dreieckfensters

Von-Hann-Fenster:

(auch Hann-Fenster oder Hanning-Fenster genannt)

Zeitfunktion: w nn

Nn N2 0 5 0 5

20 1( ) , , cos , ,...,= − ⋅ = −π

Kontinuierliches Betragsspektrum:

W W WT

WTF F

2 0 0 00 5 0 252 2

( ) , ( ) ,ω ω ω π ω π= ⋅ + ⋅ +

+ −

Höchster Nebenzipfel: a dB= − =32 0 025$ ,maximaler Abtastfehler: b = 0 85,

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-26-

Breite des Hauptzipfels: c f= ⋅0 72, ∆

Bild 10: Abtastwerte und Spektralfunktion des Hann-Fensters

Hamming-Fenster:

Zeitfunktion: w nn

Nn N3 0 54 0 46

20 1( ) , , cos , ,...,= − ⋅ = −π


W W WT

WTF F

3 0 0 00 54 0 232 2

( ) , ( ) ,ω ω ω π ω π= ⋅ + ⋅ +

+ −


Bild 11: Abtastwerte und Spektralfunktion des Hamming-Fensters

Blackman-Fenster:

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-27-

Zeitfunktion: w n a an

Na

nN

n N4 0 1 22 4

0 1( ) cos cos , ,...,= − ⋅ + ⋅ = −π π


W a W a WT

WTF F

4 0 01

2

0 012 2

( ) ( ) ( )ω ω ω πν ω πννν

ν= ⋅ + − ⋅ +

+ −

=∑

Mit den Koeffizienten:

a a a0 1 239699304

0 4211554652

0 25715

186080 04= ≈ = ≈ = ≈, , , , ,

(Im allgemeinen werden zur praktischen Berechnung die Näherungswerteverwendet, und nicht die exakten Werte der Brüche)


Bild 12: Abtastwerte und Spektralfunktion des Blackman-Fensters

(Die Übersicht wurde im wesentlichen aus [HESS] und [SCHR] zusammengestellt).

Nun fehlt (immer noch) der 3. Typ der Funktionen, nämlich die Gruppe der transienten Signale.Allerdings läßt sich die wesentliche Erkenntnis kurz zusammenfassen:

Zur Analyse transienter Signale und nur innerhalb der Meßdauer, d.h. innerhalb der für dieSignalerfassung notwendigen Zeit definierter Signalvorgänge, dürfen mit Ausnahme desRechteckfensters keine Fensterfunktionen verwendet werden.

Eine Verwendung einer Fensterfunktion würde hier auch keinen Sinn machen: da keineFunktionswerte außerhalb der Beobachtungszeit existieren, und es daher auch keine Randeffektean den Analysegrenzen geben kann, wird der Vorgang grob verfälscht und wahrscheinlichunbrauchbar.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-28-

Daraus ergibt sich die zwingende Konsequenz, daß man die Analyse transienter Signale mit einerDauer, die größer ist als die Erfassungszeit, mit der DFT vermeiden sollte, da die dabeientstehenden Fehler nicht mehr beseitigt werden können.

Das folgende Beispiel zeigt noch einmal einen transienten Vorgang, der fälschlicherweise miteinem Dreieckfenster gewichtet wurde [SCHR].

Bild 13: a) Originalfunktion b) gewichtet (und verfälscht) mit Dreieckfenster

Die Problematik dieses Abschnitts wird in der Literatur überwiegend ausführlich dargestellt, waswohl daran liegt, daß es sich um meßtechnische, und weniger um mathematische Problemehandelt. Dazu: [ELPR], [ENDE], [HESS], [SCHR].

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-29-

Übersicht über Signaltransformationen

Den meisten Lesern werden die Begriffe Fouriertransformation, Laplacetransformation und z-Transformation geläufig sein. Im Folgenden soll gezeigt werden, daß die diskreteFouriertransformation nicht etwa eine Untergruppe einer bestehenden Transformation ist, sondernals vierte Transformationsart das fehlende Glied der obigen Transformationen darstellt.

Ausgehend von der Laplace-Transformation gelangt man zur Fouriertransformation, indem manden Realteil des komplexen Operators s zu 0 setzt. In der Regelungstechnik wird die soentstehende Übertragungsfunktion auch als Frequenzgang bezeichnet. Während also die Laplace-Transformation das System allgemein beschreibt, gibt der Frequenzgang, also dieFouriertransformierte, Auskunft über das Verhalten des Systems für bestimmte Frequenzen.

Aus der Laplace-Transformation einer Zahlenfolge entsteht bei entsprechender Umbenennung diez-Transformation, die wie folgt definiert ist:

F z f zkk

k

( ) = −

=

∞

∑0

In der z-Transformation ist der Operator z die Abkürzung für z esT= . Macht man wieder denÜbergang zum Frequenzgang, indem man {s j= +σ ω

0

setzt, so ergibt sich: z e j T= ω . Und damit

erhält man (fast) schon die Definition der diskreten Fouriertransformation, man muß aber noch dieendliche Summation über eine Periode einführen:

F f f eN k kj T

k

( ) = −

=

∞

∑ ω

0

Man sieht also, so wie die Fouriertransformation als Frequenzgang zur Laplacetransformationgehört, so läßt sich ebenfalls die diskrete Fouriertransformation aus der diskretenLaplacetransformation, = z-Transformation, erhalten.

Und damit wird auch die jeweilige Domäne von z-Transformation und DFT deutlich. Denngrundsätzlich läßt sich ein digitaler Filter sowohl mit der z-Transformation, als auch mit der DFTrealisieren. Die z-Transformation geht dabei aber vom Entwurf dergestalt aus, daß der Entwurf nureinen Momentanwert (und die kurzfristige Vergangenheit) betrachtet. Ein digitaler Filter mit derDFT würde ganz anders aufgebaut: man tastet für einen festen Zeitraum eine Zeitfolge ab,manipuliert im Frequenzbereich alle Frequenzen simultan und führt anschließend eine inverse DFTaus, um wieder ein Zeitsignal zu erhalten.

Aus der umständlichen Vorgehensweise und des größeren Rechenaufwands läßt sich bereitsableiten, daß man in der Regel (es gibt Ausnahmen) die DFT nicht zum Entwurf von Echtzeitfilternverwendet, sondern in diesem Fall den Entwurf mit Hilfe der z-Transformation durchführt. Aberimmer dann, wenn man einen ganzen Abtastsatz vorliegen hat, der ausgewertet oder gefiltertwerden soll, und genügend Zeit vorhanden ist, verwendet man die DFT ([ENDE], [OPPE]).

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-30-

Die schnelle Diskrete-Fouriertransformation

Der wahrscheinlich bekannteste Begriff im Zusammenhang mit der Rechneranwendung vonFouriertransformationen ist die sogenannte "FFT", oder ausführlich Fast Fourier Transform, zudeutsch also schnelle Fouriertransformation. Dieser Begriff ist allerdings etwas unscharf gewählt,denn es wird eigentlich keine Fouriertransformation, sondern eine diskrete Fouriertransformationdurchgeführt. Der FFT-Algorithmus ist keine eigenständige Transformation, vielmehr liefert erexakt das gleiche Ergebnis wie die DFT-Gleichungen, die zuvor besprochen wurden. Wenn alsovom FFT-Algorithmus als ein "Näherungsverfahren" gesprochen wird, so bedeutet dies: die DFT isteine Näherung zur kontinuierlichen Fouriertransformation, also ist auch der FFT-Algorithmus eineNäherung zur kontinuierlichen Fouriertransformation - dennoch ist das Ergebnis von FFT und DFTidentisch, also keine weitere Näherung mehr.

Wie man am Anfang bei der beispielhaften Berechnung einer 4-Punkte-DFT sehen konnte, warenzur Berechnung 42=16 komplexe Multiplikation notwendig. Dies gilt auch allgemein: eine N-PunkteDFT benötigt O(n2)-komplexe Multiplikationen.

In der Informatik gibt es die große Gruppe der Divide-And-Conquer-Algorithmen (kurz DAC-Algorithmen). Bekannte Vertreter dieser Algorithmen sind u.A. auch die Sortierverfahren"Quicksort" und "Heapsort". Die Idee der DAC-Algorithmen soll am Beispiel von Heapsort kurzerläutert werden:

Zu sortieren seien 2n-Zahlen (vereinfachende Annahme) in aufsteigender Reihenfolge. Man zerlegtnun die Zahlen in 2 gleich große Listen, und beginnt für beide Listen den Algorithmus von vorne,also mit 2 zu sortierenden Listen à 2n-1 Zahlen. Dies führt schließlich zu n Listen mit nur noch 2Zahlen. Eine Sortierung von 2 Zahlen ist mit einem einzigen Vergleich erledigt. Also werden nunalle 2-elementigen Listen durch einen Vergleich der Größe nach sortiert. Nun werden immer 2Listen wieder zu einer doppelt so großen sortierten Liste zusammengefügt. Schlußendlich erhältman eine Liste mit 2n Zahlen in sortierter Reihenfolge.

Dies erklärt auch den Namen Divide-And-Conquer: Teilen und Erobern, man teilt also das Problemin klein "Häppchen", und die Hauptaufgabe läßt sich auf einem solch kleinen "Häppchen" trivialerledigen. Danach fügt man alles wieder zusammen, und das Problem ist gelöst. Kennzeichnendfür die DAC-Algorithmen ist ihre Konvergenzklasse, also die Anzahl benötigter Operationen: dieseist O(n log n), also wesentlich unter einem Algorithmus mit quadratischer Laufzeit wie der DFT-Berechnung (Tieferen Einblick in die Thematik der DAC-Algorithmen gibt [GÜTI]).

Eine Schlüsselrolle bei der Ableitung des FFT-Algorithmus spielt einerseits die Linearität der DFT,andererseites die Periodizität der komplexen Exponentialfunktion. Dies zusammen ermöglicht dieZerlegung eines Abtastsatzes in kleinere Partialsätze, auf die ihrerseits die DFT angewendetwerden kann. Das korrekte Ergebnis wird durch eine phasenrichtige Addition der transformiertenPartialsätze gewonnen.

Am einfachsten sind die Verhältnisse, wenn man sich auf Abtastsätze mit Blocklängen beschränkt,die Potenzen von 2 sind, also wenn N=2k. Dies hat zur Folge, daß man den Abtastsatz fortlaufendin 2 kleinere Blöcke zerlegen kann. Das Konzept basiert auf einem 1965 von Cooley und Tukeyvorgestellten Verfahren, das als das klassische FFT-Verfahren anzusehen ist.

Zur Vereinfachung der Herleitung wird, wie in der Literatur üblich, folgende Abkürzung eingeführt:

w eN

jN=

− 2 1π

Dieser Ausdruck wird als Drehfaktor (engl. twiddle factor) oder auch als Einheitswurzel bezeichnet.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-31-

Aus der Definition des Drehfaktors folgen mit der Periodizität der komplexen Exponentialfunktion 2wichtige Eigenschaften:

w wNk

Nk N= mod

w wNk

N

N k= − +2

D.h. es genügt für beliebiges k immer, nur den 0-ten bis ((N/2)-1)-ten Drehfaktor zu bestimmen, dieanderen Exponenten lassen sich auf diese Basisdrehfaktoren zurückführen.

Die Definition der diskreten Fouriertransformation läßt sich unter Verwendung des Drehfaktors wiefolgt umschreiben:

F f e

f e f e

f e f e

f e e f e

f w

m n

jmnN

n

N

n

j mnN

ngerade

N

n

j mnN

nungerade

N

n

j m nN

n

N

n

j m nN

n

N

n

j mnN

n

N

j mN

n

j mnN

n

N

n Nmn

n

N

= ⋅

= ⋅ + ⋅

= ⋅ + ⋅

= ⋅ + ⋅ ⋅

= ⋅

−

=

−

−

=

− −

=

−

−

=

−

+− +

=

−

−

=

−−

+

−

=

−

=

−

∑

∑ ∑

∑ ∑

∑ ∑

2

0

1

2

0

1 2

0

1

2

2 2

0

21

2 1

2 2 1

0

21

2

2

2

0

21

2

2 1

2

2

0

21

220

21

π

π π

π π

ππ

π

, ,

( ) ( )

∑ ∑+ ⋅ ⋅+=

−

w f wNm

n Nmn

n

N

2 120

21

Also ist eine DFT der Länge N auch zu berechnen, indem man 2 DFTs der halben Längeberechnet, und anschließend (phasenrichtig) addiert. Dies setzt allerdings voraus, daß die AnzahlN geradzahlig ist. Die gezeigte Halbierung läßt sich sooft durchführen, bis am Ende nur noch DFTsder Länge 2 zu berechnen sind. Dies setzt aber voraus, daß die Anzahl der Werte immer einePotenz von 2 ist, also:

N kk= ∈ℵ2 ,

Eine solche Minimal-DFT mit nur noch 2 Werten wird grafisch in der Regel als sogenannter"Schmetterling" oder "Butterfly" dargestellt. Ein FFT-Butterfly hat folgenden Signalflußplan:

A

B

A+ B

A- B

ω Nk

ω Nk

ω Nk

Bild 14: Basis-Butterfly-Operation

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-32-

Noch eines ist bei der Zerlegung in Teilfolgen wichtig: wie zuvor gesehen, werden bei derAufteilung in der einen DFT die geraden, in der anderen DFT die ungeraden Werte zur Berechnungherangezogen. Wendet man nun die Aufteilung sooft an, bis man am Ende nur noch Minimal-DFTserhält, sieht man leicht ein, daß die Reihenfolge, in der man die zwei Werte zusammensetzt, nichtmehr der Größe nach sortiert ist. Es läßt sich in der Tat zeigen, daß die Zerlegung in Teilfolgen fürdie Indizes eine Bitumkehr darstellt.

An einem Beispiel sei dies verdeutlicht: der Index 6 läßt sich binär als (z.B. N=8) 110 darstellen.Nach einer Bitumkehr wird der Index zu einer 011, also dezimal 3. Konkret bedeutet das, daß derWert, der in der Ausgangsfolge an der Stelle 6 steht, für die Berechnung an die Stelle 3geschrieben werden muß.

Die Bitumkehr, engl. bit (reverse) shuffling, ist bei Darstellung in binärer Schreibweise dieSpiegelung der Zahl in der Zahlmitte. Die folgende Tabelle zeigt die Bitumkehr für alle Indizeseiner 8-Werte-FFT:

Index vorBitumkehr

BinäreDarstellung

Spiegelung Index nachBitumkehr

0 000 000 01 001 100 42 010 010 23 011 110 64 100 001 15 101 101 56 110 011 37 111 111 7

Bild 15: Bitumkehroperation für 3 Bit

Das folgende Bild zeigt ein Signalflußgraphen für eine 8-Werte-FFT, in der die Abfolge derButterflies und die Wahl der Drehfaktoren deutlich wird.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-33-

Bild 16: Signalflußplan für eine 8-Punkte FFT

Zur Überprüfung des Berechnungsschemas soll für einen bestimmten Wert nun einmal derSignalflußgraph durchlaufen werden, so daß man die Identität zwischen DFT und FFT sehen kann.

( )( ) ( )( )

X x w x

x w x w x w x

x w x w x w x w x w x w x w x

x w x w x w x w x w x w x w x

7 62

83

72

4 82

6 83

5 82

7

0 80

4 82

2 80

6 83

1 80

5 82

3 80

7

0 83

1 82

2 85

3 80

4 83

5 82

6 85

7

= − ⋅= − ⋅ − ⋅ − ⋅

= − ⋅ − ⋅ − − ⋅ − ⋅ − ⋅ − ⋅

= − ⋅ − ⋅ + ⋅ − ⋅ + ⋅ + ⋅ − ⋅

( ) ( )

(1) (1) (1) (1)

Wird der Wert mit Hilfe der DFT-Definitionsgleichungen transformiert, so erhält man:

X w x w x w x w x w x w x w x w x

x w x w x w x w x w x w x w x7 8

00 8

71 8

142 8

213 8

284 8

355 8

426 8

497

0 83

1 82

2 85

3 80

4 83

5 82

6 85

= ⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅= − ⋅ − ⋅ + ⋅ − ⋅ + ⋅ + ⋅ − ⋅

Die Übereinstimmung der beiden letzten Zeilen läßt sich mit Hilfe einer Darstellung der Drehzeigerin der komplexen Ebene leicht nachvollziehen:

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-34-

0

12

3

4

5

6w8

w8

w8

w8

w8

w8

w8

w87

z.B. = -w83

Re

Im

Bild 17: Alle möglichen Drehzeiger für N=8 in der komplexen Ebene

Natürlich kann diese Rechnung nur eine Plausibiltätskontrolle darstellen, reicht aber für dieAnschauung aus, daß FFT und DFT identische Ergebnisse liefern.

Beispiel:

Für die bereits am Anfang betrachtete Zahlenfolge f = ( , , , )1 2 3 0 soll mit Hilfe des FFT-Algorithmus die diskrete Fouriertransformierte berechnet werden.

Zuerst erfolgt die Bitumkehr:0=(00)2=>(00)2=0, 1=(01)2=>(10)2=2, 2=(10)2=>(01)2=1, 3=(11)2=>(11)2=3

Danach erfogt die Berechnung mit dem Butterfly-Schema:

f =1 1+ 3 = 4

1- 3 = -2

ω 40

ω 40

ω 40

2+ 0 = 2

2- 0 = 2

ω 40

ω 40

ω 40

f =3

f =2

f =0

4+ 2 = 6

-2+ 2 = -2-j2

ω 40

ω 40

ω 41

4 - 2 = 2

-2 - 2 = -2+j2

ω 40

ω 41

ω 41

0

2

1

3

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-35-

In der Tat ist das Ergebnis mit F j j= − − − +( , , , )6 2 2 2 2 2 das gleiche wie zuvor mit der DFTberechnet wurde, aber es wurden wesentlich weniger komplexe Multiplikation benötigt.

Der folgende Programmausschnitt in PASCAL zeigt nun eine Implementation eines allgemeinenFFT-Algorithmus, der auch die Möglichkeit der inversen Transformation beeinhaltet. Für dieinverse Transformation wird von der Tatsache Gebrauch gemacht, daß die iFFT als FFT derkonjugiert komplexen Folge dargestellt werden kann (siehe unter "Herleitung derTransformationsgleichungen").

Der hier dargestellte Algorithmus basiert auf dem "radix-2-decimation in-place FFT"-Algorithmus,da er mit einer Basis-FFT mit 2 Werten beginnt (daher radix-2-decimation ≈ Verminderung auf 2er-Wurzeln), und die Umsortierung in-place vornimmt, d.h. führt die FFT-Berechnung mit einemeinzigen komplexen Array durch. Das Ergebnis steht im gleichen Array wie zuvor dieEingabeparameter.

Der eingefleischte Programmierer erkennt beim oben gezeigten Verfahren sicherlich noch eineweitere Optimierungsmöglichkeit: die erste DFT-Stufe mit 2 Werten ist immer eine reine Addition,da der Exponent 0 ist, und der Drehfaktor hoch 0 ergibt 1. Somit läßt sich eine gesamteMultiplikationsstufe einsparen. Diese Änderung wurde im Programm ebenfalls bereits durchgeführt.

Zusätzlich greift der Algorithmus für die trigonometrischen Funktionen auf hinterlegte Sinus- undCosinustabellen zu, so daß die Fließkommaberechnung immer nur für eine Tabelle erstellt werdenmuß. Hierfür wird allerdings relativ viel Speicherplatz benötigt (Stichwort "Trading Place for Time"),falls dieser nicht zur Verfügung steht, berechnet das Programm die Werte wieder automatisch mitden eingebauten Sinus- und Cosinusfunktionen.

TYPE float = single; tFolge = ARRAY [0..8191] OF float; tFolgePtr = ^tFolge; tFFTMode = (FM_Transformation,FM_InverseTransformation);

CONST FFT = FM_Transformation; iFFT = FM_InverseTransformation;

FUNCTION BitReverse(inValue : WORD; inBitCnt : BYTE) : WORD; (* algorithm: FOR i := 1 TO inBitCnt DO Logical Shift Right inValue; carry := inValue MOD 2; inValue := inValue DIV 2; Logical Shift Left dest; dest := dest * 2 + carry; OD; BitReverse := dest; *) BEGIN ASM MOV AX,inValue (* inValue nach AX *) MOV BL,inBitCnt (* inBitCnt nach BL *) MOV CX,0 (* outResult := 0 *) @BitLoop: RCR AX,1 (* inValue DIV 2, CY=inValue.bit0 *) RCL CX,1 (* CY nach outResult.bit0 *) SUB BL,1 (* --inBitCnt *)

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-36-

JNZ @BitLoop (* until (inBitCnt=0) *) MOV @Result,CX (* MathBitReverse := CX *) END (* ASM *); END (* BitReverse *);

PROCEDURE FFT(inPunkte : WORD; inoutDatenReal, inoutDatenImag : POINTER; inModus : tFFTMode); CONST cLN_ZWEI = 0.693147181; (* Ln(2) *) VAR dataRe, dataIm : tFolgePtr; fRe, fIm, fcos, fsin, freal, fimag, fArg : float; wSpruenge, wSprung, wBflyDist, wSprunghoehe, wStufe, wElement1, wElement2, wExponent, wBflies : WORD; bBits : BYTE; wPos, wRevPos : WORD;

BEGIN dataRe := inoutDatenReal; dataIm := inoutDatenImag; ErstelleTabellen(inPunkte); bBits := ROUND( Ln(inPunkte) / cLN_ZWEI );

(* Bitreverse-Shuffling *) FOR wPos := 0 TO (inPunkte - 1) DO BEGIN wRevPos := Bitreverse(wPos,bBits); IF wRevPos > wPos THEN BEGIN fRe := dataRe^[wPos]; fIm := dataIm^[wPos]; dataRe^[wPos] := dataRe^[wRevPos]; dataIm^[wPos] := dataIm^[wRevPos]; dataRe^[wRevPos] := fRe; dataIm^[wRevPos] := fIm; END (* IF *); END (* FOR *);

(* Für den Fall der inversen FFT hier das konjugiert Komplexe der Folge bilden *) IF inModus = FM_InverseTransformation THEN FOR wElement1 := 0 TO (inPunkte - 1) DO dataIm^[wElement1] := - dataIm^[wElement1]; (* END FOR *) (* END FOR *)

(* Erste Stufe ist eine reine Addition zweier benachbarter

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-37-

Elemente, und kann daher vorgezogen werden *) wElement1 := 0; wElement2 := 1; WHILE (wElement1 < inPunkte) DO BEGIN freal := dataRe^[wElement2]; fimag := dataIm^[wElement2]; fRe := dataRe^[wElement1]; fIm := dataIm^[wElement1]; (* Berechnung des Butterfly *) dataRe^[wElement2] := fRe - freal; dataIm^[wElement2] := fIm - fImag; dataRe^[wElement1] := fRe + freal; dataIm^[wElement1] := fIm + fimag; INC(wElement1,2); INC(wElement2,2); END (* FOR *);

(* hier setzt der "gewöhnliche" FFT-Algorithmus ein *) wSpruenge := inPunkte DIV 4; (* 2 *) wBflyDist := 2; (* 1 *) wSprunghoehe := 4; (* 2 *) FOR wStufe := 2 TO bBits DO BEGIN wElement1 := 0; wElement2 := wBflyDist; FOR wSprung := wSpruenge DOWNTO 1 DO BEGIN wExponent := 0; FOR wBflies := 1 TO wBflyDist DO BEGIN fcos := ptCos(wExponent); fsin := ptSin(wExponent); freal := dataRe^[wElement2]; fimag := dataIm^[wElement2]; (* Multiplikation des 2. Elementes mit dem Drehfaktor *) fRe := freal * fcos + fimag * fsin; fIm := fimag * fcos - freal * fsin; freal := dataRe^[wElement1]; fimag := dataIm^[wElement1]; (* Berechnung des Butterfly *) dataRe^[wElement2] := freal - fRe; dataIm^[wElement2] := fimag - fIm; dataRe^[wElement1] := freal + fRe; dataIm^[wElement1] := fimag + fIm; INC(wElement1); INC(wElement2); wExponent := wExponent + wSpruenge; END (* FOR *); wElement1 := wElement1 - wBflyDist + wSprunghoehe; wElement2 := wElement1 + wBflyDist; END (* FOR *); wSpruenge := wSpruenge DIV 2; wSprunghoehe := wSprunghoehe * 2; wBflyDist := wBflyDist * 2; END (* FOR *);

(* Für den Fall der inversen FFT hier wieder das konjugiert Komplexe der Folge bilden, und Real- und Imaginärteil durch die Anzahl der Punkte dividieren *) IF inModus = FM_InverseTransformation THEN BEGIN fRe := - inPunkte; (* Konversion WORD -> float *) fIm := inPunkte; (* ist Schleifeninvariant *) FOR wElement1 := 0 TO (inPunkte - 1) DO BEGIN dataIm^[wElement1] := dataIm^[wElement1] / fRe;

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-38-

dataRe^[wElement1] := dataRe^[wElement1] / fIm; END (* FOR *); END (* IF *);

END (* FFT *);

Für die direkte Berechnung jeder dieser kleineren DFT's benötigt man eine Anzahl vonOperationen der Größenordnung (N/2)2, das macht zusammen 2(N/2)2. Zusätzlich sind noch N/2Operationen für die Multiplikation mit dem Phasendrehfaktor notwendig. Für große N ist diesjedoch vernachlässigbar, so daß für jede Berechnungsstufe die Anzahl notwendiger komplexerMultiplikationen in der Größenordnung O(2(N/2)2) liegt. Da die Gesamtzahl der Punkte einePotenz von 2 ist, läßt sich die Teilung genau log2 N=w-mal durchführen. Insgesamt besitzt daherder Algorithmus eine Komplexität der Klasse O(N log2 N), ist also wesentlich weniger aufwendigals der DFT-Algorithmus mit der Komplexität O(N2). Die folgende Grafik zeigt eineGegenüberstellung der Anzahl komplexer Multiplikation für die beiden Verfahren.

N

O()

0

65536

131072

196608

262144

0 64 128 192 256 320 384 448 512

N*N

N*ld(N)

Bild 18: Komplexitätsvergleich DFT - FFT

Natürlich wird die Geschwindigkeitseinsparung nicht immer genauso stark sein, wie die obigeGrafik zeigt. Dennoch wird deutlich, daß sich der Mehraufwand für die Implementierung einer FFTimmer lohnt.

Prinzipiell gibt es auch noch andere Möglichkeiten, die Periodizität der DFT zu nutzen, um denBerechnungsaufwand zu vereinfachen. Auch ist es im Grunde egal, ob die Bitvertauschung voroder nach der eigentlichen Berechnung durchgeführt wird. Ein Teil der Algorithmen arbeitet auchmit beliebiger Punktanzahl, oder auch mit Punktanzahlen, die Vielfache von 4 oder 16 sind. In[BRIG] ist ein Großteil der gängigen Verfahren vorgestellt, in [BETH] dagegen ist im wesentlichendie mathematisch - algebraische Darstellung der FFT-Theorie dargelegt. Für konkreteImplementationen auf einem Digitalen Signalprozessor der Reihen Motorola DSP56xxx oder DSP96xxx gibt [MOTO] einen umfassenden Einblick in die Programmierung der FFT-Algorithmen inAssembler.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-39-

Ein kleiner Tip zur Implementierung des FFT-Algorithmus:

Der FFT-Algorithmus benötigt zu seiner Ausführung komplexe Multiplikationen. Bekanntlichberechnet sich das Produkt zweier komplexer Zahlen wie folgt:

Seien a,b,c komplexe Zahlen mit a a ja b b jb c c jc: , : , := + = + = +0 1 0 1 0 1 .

Dann gilt:c a b c a b a b

c a b a b= ⋅ ⇔ = ⋅ − ⋅

= ⋅ + ⋅0 0 0 1 1

1 0 1 1 0

Diese Berechnung erfordert 4 reelle Multiplikationen und 2 reelle Additionen, also benötigt dieBerechnung insgesamt die Zeit T T TMult Add1 4 2= + .

Es gibt allerdings folgenden Algorithmus zum Produkt komplexer Zahlen, der mit einerMultiplikation weniger auskommt:

m a bm a b

m a a b b

c m mc m m m

Add Add

Mult

0 0 0

1 1 1

2 0 1 0 1

0 0 1

1 2 1 0

= ⋅= ⋅

= + ⋅ +

= −= − −

( ) ( )678 678

1 24 44 34 4 4

Wie man leicht nachprüft, kommt diese Berechnungsmethode mit 3 reellen Multiplikationen und 5reellen Additionen aus, die notwendige Zeit liegt daher bei T T TMult Add2 3 5= + .

Ein Vergleich von T1 und T2 zeigt, daß die zweite Berechnungsmethode dann schneller ist, wenngilt: T TMult Add> ⋅3 . In diesem Vergleich ist allerdings der Mehraufwand für dieZwischenspeicherung der Ergebnisse nicht enthalten, man kann aber davon ausgehen, daß immerdann, wenn die Multiplikation 4-mal so lange dauert wie eine Addition, die zweite Methode sicherschneller ist.

Bei einem echten Signalprozessor kommt dieser Vorteil nicht so sehr zum Tragen, weil hier dieDauer einer Multiplikation kaum größer ist als die Dauer einer Addition. Aber für die Durchführungeiner FFT steht nicht immer das Optimum zur Verfügung, oftmals müssen die Berechnungen aufeinem konventionellen Mikroprozessor durchgeführt werden, vielfach sogar in einer Hochsprache.Gerade dann machen sich solche Einsparungen wieder bemerkbar, weil hier die Dauer einerFließkomma-Multiplikation immer wesentlich größer ist als die Dauer einer Fließkomma-Addition.

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-40-

Mischung von DFT und kontinuierlicher Fouriertransformation

Aus der Systemtheorie, die ja u.A. auf der kontinuierlichen Fouriertransformation basiert, sindumfangreiche Kenntnisse auf dem Gebiet der Übertragungsfunktionen, insbesondere von Filtern,vorhanden. Wie kann man diese Erkenntnisse auf den diskreten Fall übertragen?

Wie zuvor bereits gezeigt, existiert zwischen den Indizes der transformierten Folgenwerte und derzugehörigen Frequenz eine eindeutige Zuordnung. Will man nun ein diskretes Spektrum, das manmit Hilfe einer DFT gewonnen hat, durch eine kontinuierliche Übertragungsfunktion bewerten, sostellt sich die Aufgabe wie folgt dar: zu jedem Index läßt sich eine Frequenz berechnen. An dieserFrequenz läßt sich die Übertragungsfunktion auswerten, und dieses Ergebnis wird mit dem Wertder Folge multipliziert. Wendet man dieses "Kochrezept" allerdings ohne Nachzudenken auf alleWerte der transformierten Folge an, so wird sich das gewünschte Ergebnis nicht einstellen.

Der Grund dafür liegt wieder einmal in den Effekten, die die Abtastung im Frequenzbereichverursacht. Wie zuvor schon gesehen, enthält nur die erste Hälfte der transformierten FolgeFrequenzen unterhalb der halben Abtastfrequenz. Oberhalb der halben Abtastfrequenz liegt eineSpiegelung der ersten Hälfte vor. In der Konsequenz bedeutet dies, daß man auch diekontinuierliche Übertragungsfunktion an der halben Abtastfrequenz spiegeln muß, damit mankorrekte Ergebnisse erhält. Diese etwas verwirrende Aussage soll zuerst mit einer Skizzeverdeutlicht werden, bevor auf die mathematische Seite der Angelegenheit eingegangen wird.

Ein diskretes Frequenzspektrum hat zum Beispiel folgende Einhüllende:

0,5f ab f

m0 N/2 N-1

|X|

Bild 19: Einhüllende eines periodischen Spektrums

Als Übertragungsfunktion wird ein Tiefpaß gewählt: Gj T

f fg

g ab( ) ,ωω

=+

<<11

, dessen

Übertragungsfunktion folgende Darstellung im Frequenzbereich hat:

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-41-

0,5f ab f

1

|G|

fg

Bild 20: Übertragungsfunktion (Betrag) eines Tiefpaß 1. Ordnung

Um die gewünschte Tiefpaßfilterung zu erreichen, muß die Übertragungsfunktion des Tiefpassesebenfalls an der halben Abtastfrequenz gespiegelt werden. Erst danach ist eine Multiplikation derWerte möglich und sinnvoll.

0,5f ab f

m0 N/2 N-1

|X|

Übertragungsfunktion des gespiegelten Tiefpasses

Bild 21: Gespiegelte Übertragungsfunktion Tiefpaß 1. Ordnung

Berechnet wird dies wie folgt:

Sei G( )ω eine kontinuierliche Übertragungsfunktion, Xm die diskrete Fouriertransformierte derEingangsfolge. Dann gilt für die diskrete Fouriertransformierte der Ausgangsfolge Ym:

02

2

21 1 2

≤ ≤ = ⋅ ⋅

+ ≤ ≤ − = ⋅ − ⋅

mN

Y X GmN

f

Nm N Y X G

N mN

f

m m ab

m m ab

:

:( )

π

π

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-42-

Wobei fab Abtastfrequenz, N die Anzahl der Abtastwerte. Die Anzahl der Abtastwerte muß fürdieses Berechnungsschema geradzahlig sein, was aber keine Einschränkung darstellt: in der Regelwird man die DFT mit Hilfe des FFT-Algorithmus berechnen, so daß die Anzahl der Werte immerdurch 2 teilbar sein wird (für ungerades N wird lassen sich die beiden Gleichungen natürlichebenfalls aufstellen, nur sind dann die Fallunterscheidungen etwas anders; allerdings wird dies inder Praxis nicht benötigt).

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-43-

Digitale Systemidentifikation

Unter dem Begriff Systemidentifikation versteht man die Aufgabe, den Frequenzgang G(ω), bzw.im Zeitbereich die Impulsantwort g(t), eines Systems aus der Erregerfunktion x(t) und derAntwortfunktion y(t) zu berechnen.

Das Problem tritt bei der experimentellen Systemanalyse auf: x(t) und y(t) werden an einemunbekanntem System gemessen, dessen Systemeigenschaften man ermitteln möchte.

Diese Aufgabe ist genau die Umkehrung zur Bestimmung der Antwort eines Systems auf einebestimmte Erregerfunktion (z.B. Sprung, Rampe, etc.):

Y G X( ) ( ) ( )ω ω ω= ⋅

Hieraus folgt für die Systemidentifikation:

G XY

( ) ( )( )

ω ωω

=

Wenn man nun entsprechend den Darlegungen der vergangenen Abschnitte alleFouriertransformierten durch ihre diskreten Fouriertransformierten näherungsweise darstellt, solautet eine numerische Bestimmungsgleichung:

{ }{ }G X

Yxy

m N Ymm

m

n

nm= = ≤ ≤ ≠F

FN

N

, ,02

0 (18)

(Übrigens: die Division in (18) ist eine komplexe Division!)

In (18) ist Xm die diskrete Fouriertransformierte der abgetasteten Erregerfunktion, und Ym diediskrete Fouriertransformierte der abgetasteten Antwortfunktion. Die Division wird nur mit derersten Hälfte der Folgenwerte durchgeführt, da die weiteren Werte wegen der Spiegelung imFrequenzbereich redundant sind.

Somit läßt sich unter Anwendung des Abtasttheorems auch genau die Grenzfrequenz diesesVerfahrens angeben: da man nur die erste Hälfte der Werte verwendet, ist die so bestimmtediskrete Übertragungsfunktion nur bis zur halben Abtastfrequenz eine Näherung zurkontinuierlichen Übertragungsfunktion:

G G mf

Nf

mAb Ab≈ = ⋅ ⋅ < ⋅

( ) , ,ω ω π ω π2 22

Die Abtastung muß natürlich für Erregerfunktion und Antwortfunktion mit derselben Anzahl vonAbtastwerten und derselben Abtastzeit durchgeführt werden. Ein vorhandenes Antialiasing-Filterverursacht übrigens keinen Fehler in der Messung, seine Übertragungsfunktion würdeherausgekürzt. (Natürlich nur, wenn man immer das gleiche Filter verwendet!) Vorsicht dagegen istbei Verwendung von Fensterfunktionen geboten, da man hier eine Faltung im Frequenzbereichdurchführt, so daß das Resultat der Division verändert wird. Es ist hier daher ratsam, außer demRechteckfenster keine anderen Fensterfunktionen einzusetzen.

Für die praktische Durchführung von (18) ist natürlich die Genauigkeit dieser Approximationwichtig. Aus der numerischen Mathematik weiß man, daß bei einer Division durch eine kleine Zahl

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-44-

sich bereits sehr kleine Fehler dieser Zahl fatal auf das Ergebnis auswirken können. Denn bei einerkonkreten Anwendung muß man sich über eines im Klaren sein: bei einer Abtastung ist durch diedamit verbundene AD-Umsetzung immer (!) ein Quantisierungsfehler vorhanden. Und dieserFehler ist bei einer kleinen Zahl prozentual sehr groß, daher wird der relative Fehler desErgebnisses ebenfalls sehr groß.

Beispiel:

Sei der absolute Fehler von Y gleich ∆Y=1. Dann gilt für ein großes Y, z.B. 128, daß man um 127,128 oder 129 teilt. D.h., der Fehler wirkt sich nicht besonders gravierend aus. Ist dagegen Y=1, soteilt man entweder durch 0, 1 oder 2, d.h. das Ergebnis wird unbrauchbar, da man alsFehlerabschätzung Werte zwischen dem halben Wert und "unendlich" erhalten würde.

Besonders ungünstig fällt die Division aus, wenn der Nenner für einen Wert m verschwindet, d.h.gleich Null wird. In diesem Fall läßt sich über den Frequenzgang des Systems bei dieser Frequenzkeine Aussage treffen. Da im Nenner von (18) die DFT der Erregerfunktion auftaucht, bedeutetdies für die praktische Wahl der Erregerfunktion, daß das diskrete Spektrum der Erregerfunktionmöglichst keine Nullstellen besitzen darf.

Es ist daher bei der Systemidentifikation weniger das Problem, die Berechnungen desFrequenzganges durchzuführen, vielmehr ist die Hauptschwierigkeit eine Erregerfunktion zufinden, die keine Nullstellen im Spektrum besitzt, und dennoch real erzeugbar ist.

Im folgenden ist nocheinmal die Rechenvorschrift zur Systemidentifikation zusammengestellt:

1. Man tastet die Erregerfunktion x(t) ab, und bestimmt mit der DFT (oder FFT) die diskreteFouriertransformierte Xm. Die Erregerfunktion sollte im Spektrum im interessierendenFrequenzbereich möglichst wenig Nullstellen besitzen.

2. Man tastet die Antwortfunktion y(t) ab, und bestimm mit der DFT (oder FFT) die diskreteFouriertransformierte Ym.

3. Man bestimmt den diskreten Frequenzgang des Systems durch die Division G XYm

m

m

=

für 02

≤ ≤mN

4. Falls auch im Zeitbereich die Impulsantwort von Interesse ist, so läßt sich diese leicht auseiner inversen diskreten Fouriertransformation gewinnen: { }g Gn m= −FN

1

Näheres zu der Systemidentifikation und der Fehlerabschätzung ist in [LANG] zu finden, zu denmöglichen Fehlerquellen in [ELPR].

FHD Fb EA


Marcus Bäckmann


Prof. Dr. Münter

-45-

Literaturangaben:

[BETH] Beth, Thomas: Verfahren der schnellen Fourier-Transformation. AlgebraischeBeschreibung, Komplexität und Implementierung. Stuttgart: Teubner, 1984

[BRIG] Brigham, E. Oran. FFT Schnelle Fourier-Transformation. München, Wien: OldenbourgVerlag, 1987

[ELPR] Fachartikel Elektronik Praxis Nr. 22, 24. November 1994, "Trivial aber fatal - TypischeFehlerquellen beim Einsatz von FFT-Analysatoren"

[ENDE] van den Enden, Ad W. M.: Digitale Signalverarbeitung. Braunschweig, Wiesbaden:Friedrich Vieweg & Sohn, 1990

[GÜTI] Güting, Ralf Hartmut: Datenstrukturen und Algorithmen. Stuttgart: Teubner Verlag, 1992

[HACK] Sir Hackett, John: Die Welt in Flammen. Tagebuch des 3. Weltkrieges

[HESS] Hesselmann, Norbert: Digitale Signalverarbeitung: Rechnergestützte Erfassung, Analyseund Weiterverarbeitung analoger Signale. Würzburg: Vogel, 1983

[LANG] Lange, Dieter: Methoden der Signal- und Systemanalyse: Eine Einführung mit demPersonalcomputer. Braunschweig, Wiesbaden: Vieweg, 1985.

[LOCH] Locher, Franz: Mathematik III (numerische Mathematik), Studienbrief der FernuniversitätHagen, 1989; erschienen im Hüthig-Verlag unter dem Titel Numerische Mathematik

[LÜKE] Lüke, Hans Dieter. Signalübertragung. Einführung in die Theorie derNachrichtenübertragungstechnik. Berlin, Heidelberg, New York: Springer Verlag, 1979

[MOTO] Implementation of Fast Fourier Transforms on Motorola's Digital Signal Processors.Motorola, Digital Signal Processing Division, 1993. Bestellnummer APR4/D

[OPPE] Oppenheim, Alan: Signale und Systeme. Weinheim, Basel (CH), Cambridge, New York:VCH Verlagsgesellschaft, 1992

[SCHR]: Schrüfer, Elmar: Signalverarbeitung: Numerische Verarbeitung digitaler Signale.München, Wien: Hanser Verlage, 1990

Documents

FHD - baeckmann.de · ( ) e π d (4) Da die DFT auf einem Rechner implementiert werden soll, muß man zur Berechnung dieses Integralausdrucks auf ein Näherungsverfahren ausweichen