Signalverarbeitung 1mitarbeiter.hs-heilbronn.de/~vstahl/signalverarbeitung1/skript.pdf · Signalverarbeitung 1 Skript zur Vorlesung an der Hochschule Heilbronn 1 (Stand: 24. Juni

Signalverarbeitung 1

Skript zur Vorlesung an der Hochschule Heilbronn 1

(Stand: 24. Juni 2017)

Prof. Dr. V. Stahl

1Der Inhalt dieses Skripts ist teilweise wörtlich oder sinngemäß aus den im Literaturver-zeichnis genannten Quellen entnommen. Es handelt sich um keine wissenschaftliche Veröffent-lichung.

INHALTSVERZEICHNIS 2

Inhaltsverzeichnis1 Grundlagen 3

1.1 Dirac Impuls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Faltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Fourier Reihen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Fourier Transformation . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Abtastung und Aliasing 102.1 Fourier Reihe des Impulszugs . . . . . . . . . . . . . . . . . . . . 102.2 Abtastung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.4 Bandbegrenzte Signale . . . . . . . . . . . . . . . . . . . . . . . . 142.5 Signalrekonstruktion . . . . . . . . . . . . . . . . . . . . . . . . . 152.6 Tiefpass Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.7 Fensterung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.8 Zeitdiskrete Fourier Transformation . . . . . . . . . . . . . . . . 26

3 Diskrete Fourier Transformation 283.1 Bandbegrenzte periodische Signale . . . . . . . . . . . . . . . . . 283.2 Matrix Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.3 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4 Schnelle Fourier Transformation 40

5 Eigenschaften der DFT 495.1 Zyklische Verschiebung . . . . . . . . . . . . . . . . . . . . . . . . 505.2 Zyklische Faltung . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

6 Schnelle Faltung mit FFT 57

A Anhang 62A.1 Die wichtigsten Fourier Transformationspaare . . . . . . . . . . . 62A.2 Rechengesetze für die Fourier Transformation . . . . . . . . . . . 63

1 GRUNDLAGEN 3

1 Grundlagen1.1 Dirac ImpulsWir betrachten eine Rechteckfunktion im Zeitfenster 0 ≤ t < ε und Ampliude1/ε:

dε(t) ={ 1

ε falls 0 ≤ t < ε0 sonst

Unabhängig von ε ist der Flächeninhalt unter dieser Funktion immer 1, d.h.∫ ∞−∞

dε(t)dt = 1.

Interessant wird diese Funktion, wenn man ε immer kleiner macht. Die Zeitdau-er geht dabei gegen Null, die Amplitude gegen unendlich. Das Ergebnis heißtEinheitsimpuls δ(t) oder Dirac Impuls:

δ(t) = limε→0

dε(t).

Genau genommen existiert dieser Grenzwert gar nicht in der Menge der reellenFunktionen R→ R. Daher nennt man δ(t) eine verallgemeinerte Funktion oderDistribution. Die wesentlichen Eigenschaften von δ(t) sind

δ(t) ={

0 falls t 6= 0∞ falls t = 0

und ∫ ∞−∞

δ(t)dt = 1.

Mit unendlich großen Zahlen ∞ kann man genauso rechnen wie mit unend-lich kleinen Differentialen dx. In beiden Fällen handelt es sich um eine Verein-fachung der Notation, hinter der sich ein Grenzwert versteckt.

Eine recht nützliche Eigenschaft des Einheitsimpulses ist, dass er eine geradeFunktion ist, d.h.

δ(t) = δ(−t).

Wie die Einheitssprungfunktion kann man auch den Einheitsimpuls an einebeliebige Stelle t = a verschieben durch

δ(t− a) ={

0 falls t 6= a∞ falls t = a

Da der Einheitsimpuls eine gerade Funktion ist, gilt

δ(t− a) = δ(a− t).

Multipliziert man eine Funktion f(t) mit dem verschobenen Einheitsimplulsδ(t− a), erhält man das zunächst erstaunliche Ergebnis

f(t)δ(t− a) = f(a)δ(t− a).

1 GRUNDLAGEN 4

Man kann sich aber leicht davon überzeugen, dass das so stimmt: Für t 6= a sindbeide Seiten Null und für t = a steht auf beiden Seiten f(a)δ(0).

Hieraus folgt eine wichtige Eigenschaft für den Dirac Impuls:∫ ∞−∞

f(τ)δ(t− τ)dτ =∫ ∞−∞

f(t)δ(t− τ)dτ

= f(t)∫ ∞−∞

δ(t− τ)dτ

= f(t).

Theorem 1.1Sei f ∈ R→ R. Dann gilt∫ ∞

−∞f(τ)δ(t− τ)dτ = f(t).

1 GRUNDLAGEN 5

1.2 FaltungDie Faltung f ∗ g zweier Funktionen f, g ist definiert durch

(f ∗ g)(t) =∫ ∞−∞

f(τ)g(t− τ)dτ.

Die Faltung ist also eine zweistellige Funktion von Funktionen, ebenso wiez.B. die Komposition oder die Addition von Funktionen.

Die Faltung ist kommutativ, d.h. es gilt

f ∗ g = g ∗ f.

Dies erhält man aus

(f ∗ g)(t) =∫ ∞τ=−∞

f(τ)g(t− τ)dτ

mit der Substitution µ = t− τ und dτ = −dµ:∫ ∞τ=−∞

f(τ)g(t− τ)dτ =∫ −∞µ=∞

−f(t− µ)g(µ)dµ

=∫ ∞µ=−∞

g(µ)f(t− µ)dµ

=∫ ∞τ=−∞

g(τ)f(t− τ)dτ

= (g ∗ f)(t).

Interessant ist z.B. die Faltung einer Funktion f mit dem Einheitsimpuls δ.Aus Theorem 1.1 folgt

(f ∗ δ)(t) =∫ ∞−∞

f(τ)δ(t− τ)dτ

= f(t).

Somit giltf ∗ δ = f,

d.h. δ spielt bei der Faltung die gleiche Rolle wie die Eins bei der Multiplikation.Die Faltung hat viele weitere Eigenschaften, von denen einige im folgenden

Theorem zusammengefasst sind.

Theorem 1.2 (Faltung)

δ ∗ f = f

f ∗ g = g ∗ f(f ∗ g) ∗ h = f ∗ (g ∗ h)a(f ∗ g) = (af) ∗ g

f ∗ (g + h) = (f ∗ g) + (f ∗ h)

1 GRUNDLAGEN 6

1.3 Fourier Reihen

Theorem 1.3Sei f(t) ein stückweise stetiges T -periodisches Signal. Dann gibt es Akund ϕk so dass

f(t) = A0 +∞∑k=1

Ak cos(kωt+ ϕk), ω = 2π/T

für alle t, an denen f(t) stetig ist.

Ein T -periodisches Signal lässt sich also als Überlagerung von harmonischenSchwingungen darstellen, deren Frequenzen ganzzahlige Vielfache der Grund-frequenz ω = 2π/T ist.

Wir können diese Summe unter Verwendung von komplexen Zahlen et-was vereinfachen.

f(t) = A0 +∞∑k=1

Ak cos(kωt+ ϕk)

= A0 +∞∑k=1

re(Ake

j(kωt+ϕk))

= A0 +∞∑k=1

re(Ake

jϕkejkωt)

= A0 + 12

∞∑k=1

Akejϕkejkωt +Akejϕkejkωt

= A0 + 12

∞∑k=1

Akejϕkejkωt +Ake

−jϕke−jkωt

= A0 +∞∑k=1

12Ake

jϕkejkωt +∞∑k=1

12Ake

−jϕke−jkωt

= A0︸︷︷︸z0

+∞∑k=1

12Ake

jϕk︸︷︷︸zk, k=1,2,...

ejkωt +−∞∑k=−1

12A−ke

−jϕ−k︸︷︷︸zk, k=−1,−2,...

ejkωt

= z0 +∞∑k=1

zkejkωt +

−1∑k=−∞

zkejkωt

=∞∑

k=−∞zke

jkωt

wobei

z0 = A0

zk ={

1/2Akejϕk für k > 01/2A−ke−jϕ−k für k < 0.

1 GRUNDLAGEN 7

Die Fourier Koeffizienten zk treten in konjugiert komplexen Paaren auf, d.h.

z−k = zk.

Aus einem Fourier Koeffizenten zk kann man die Amplitude und die Phase derk-ten Oberschwingung ablesen:

A0 = z0

Ak = 2|zk|ϕk = ∠(zk), k = 1, 2, . . .

Zur Berechnung des n-ten Fourier Koeffizienten zn der Funktion f(t) gehtman von der Gleichung

f(t) =∞∑

k=−∞zke

jkωt

aus und multipliziert beide Seiten mit e−jnωt:

f(t)e−jnωtdt =∞∑

k=−∞zke

jkωte−jnωtdt.

Integration für t = 0, . . . , T auf beiden Seiten liefert∫ T

0f(t)e−jnωtdt =

∫ T

0

∞∑k=−∞

zkejkωte−jnωtdt

=∞∑

k=−∞zk

∫ T

0ej(k−n)ωtdt.

Das Integral lässt sich wie folgt berechnen:

• Falls k = n gilt ∫ T

0ej(k−n)ωtdt =

∫ T

01 dt = T.

• Falls k 6= n gilt∫ T

0ej(k−n)ωtdt = 1

j(k − n)ω

[ej(k−n)ωt

]T0

= 1j(k − n)ω

(ej(k−n)ωT − 1

)ω = 2π/T

= 1j(k − n)ω

(e2πj(k−n) − 1

)k − n ∈ Z

= 1j(k − n)ω (1− 1)

= 0

1 GRUNDLAGEN 8

Damit gilt ∫ T

0ej(k−n)ωtdt =

{T falls k = n0 sonst.

und folglich ∫ T

0f(t)e−jnωtdt =

∞∑k=−∞

zk

∫ T

0ej(k−n)ωtdt︸︷︷︸

T falls k = n, 0 sonst= zn T

bzw.

zn = 1T

∫ T

0f(t)e−jnωtdt.

Theorem 1.4 (Fourier Reihe)Sei f ∈ R→ R eine T -periodische Funktion und

zk = 1T

∫ T

0f(t)e−jkωtdt

wobei ω = 2π/T . Dann gilt

f(t) =∞∑

k=−∞zke

jkωt

für alle t, an denen f stetig ist.

1 GRUNDLAGEN 9

1.4 Fourier TransformationEine Fourier Reihenentwicklung ist nur für T -periodische Funktionen f(t) mög-lich. Um auch nichtperiodische Funktionen im Frequenzbereich analysieren zukönnen, wird die Fourier Transformation wie folgt definiert.

Definition 1.5 (Fourier Transformation)Die Funktion

F (ω) =∫ ∞−∞

f(t)e−jωtdt

heißt Fourier Transformierte von f(t). Umgekehrt heißt

f(t) = 12π

∫ ∞−∞

F (ω)ejωtdω

inverse Fourier Transformierte von F (ω).

Die wichtigsten Eigenschaften der Fourier Transformation sind im Anhangzusammengefasst.

2 ABTASTUNG UND ALIASING 10

2 Abtastung und Aliasing2.1 Fourier Reihe des ImpulszugsSei

p(t) =∞∑

n=−∞δ(t− nT )

ein Impulszug mit Periodendauer T . Anschaulich betrachtet ist p(t) überallNull außer an den Stellen t, die ein ganzzahliges Vielfaches von T sind. Manbezeichnet p(t) daher auch als Kamm- oder Rechenfunktion. Da der ImpulszugT -periodisch ist, kann man ihn in eine Fourier Reihe entwickeln:

p(t) =∞∑

k=−∞zke

jkωt, ω = 2π/T.

Die Fourier Koeffizienten zk berechnet man wie folgt:

zk = 1T

∫ T

0p(t)e−jkωtdt

= 1T

∫ T/2

−T/2p(t)e−jkωtdt

= 1T

∫ T/2

−T/2δ(t)e−jkωtdt

= 1T

∫ T/2

−T/2δ(t)e0dt

= 1T

∫ T/2

−T/2δ(t)dt

= 1T

Die Fourier Koeffizienten zk des Impulszugs sind also alle gleich 1/T . Damit istdie Fourier Reihe des Impulszugs

p(t) = 1T

∞∑k=−∞

ejkωt.


2.2 AbtastungUm ein zeitkontinuierliches Signal f(t) in einem digitalen Rechner verarbeitenzu können, muss es zunächst abgetastet werden. Man betrachet also nur nochFunktionswerte zu Zeitpunkten nTs wobei Ts das Abtastinterval ist. Der Index ssteht hierbei für “sampling”, das Englische Wort für Abtastung. Die Abtastungwird zunächst dadurch bewerkstelligt, dass man f(t) mit dem Impulszug

p(t) =∞∑

n=−∞δ(t− nTs)

multipliziert. Im vorigen Abschnitt wurde die Fourier Reihe des Impulszugshergeleitet:

p(t) = 1Ts

∞∑k=−∞

ejkωst, ωs = 2πTs.

Multipliziert man das zeitkontinuierliche Signal f(t) nun mit dem Impulszug,erhält man ein neues (immer noch kontinuierliches) Signal fp(t), das ebenfallsaus einer Folge von Impulsen besteht.

fp(t) = f(t)p(t)

= f(t)∞∑

n=−∞δ(t− nTs)

=∞∑

n=−∞f(t)δ(t− nTs)

=∞∑

n=−∞f(nTs)δ(t− nTs)

Wie erwartet spielen also nur noch die die Funktionswerte von f zu den Abtast-zeitpunkten t = nTs eine Rolle. Diese Abtastwerte können nun in Form einerFolge

fn = f(nTs)

verarbeitet werden.


2.3 AliasingWie spiegelt sich die Abtastung von f(t) im Frequenzbereich wider? Verwendetman die Fourier Reihe des Impulszugs, erhält man

fp(t) = f(t)p(t)

= f(t) 1Ts

∞∑k=−∞

ejkωst

= 1Ts

∞∑k=−∞

f(t)ejkωst.

Die Fourier Transformierte Fp(ω) von fp(t) erhält man aus der Fourier Trans-formierte F (ω) von f(t) und der Korrespondenz

f(t)ejω̂t c s F (ω − ω̂).

Mit ω̂ = kωs erhält man

f(t)ejkωst c s F (ω − kωs).

Aufgrund der Linearität der Fourier Transformation gilt somit

fp(t) c s 1Ts

∞∑k=−∞

F (ω − kωs)︸︷︷︸Fp(ω)

.

Wie lässt sich dieses Ergebnis interpretieren? Nun,

F (ω − kωs)

ist die Fourier Transformierte F (ω) der ursprünglichen Funktion f(t) um kωsverschoben. Die Summe

∞∑k=−∞

F (ω − kωs)

bedeutet, dass unendlich viele Kopien von F (ω) jeweils um ωs verschoben ne-beneinander gesetzt werden. Wenn sich die Kopien überlappen, wird im Über-lappungsbereich aufsummiert. Man kann dann F (ω) nicht mehr einfach durchAusschneiden entnehmen. Dieses Phänomen heißt Aliasing. Je größer die Abtast-frequenz ωs ist, d.h. je mehr Abtastwerte pro Sekunde man betrachtet, umsoweiter liegen die Kopien von F (ω) auseinander und umso unwahrscheinlichertritt Überlappung ein. Halten wir also fest:

Abtastung mit Ts c s Periodische Fortsetzung mit ωs


t

f(t)

fp(t)

fp(t)

ω

ω

ω

F (ω)

Fp(ω)

Fp(ω)

ω̂−ω̂

t

t

Ts

Ts

−ωs

2

−ωs −ωs

2

ωs

2

ωs−ωs ωs

2

ωs

Abbildung 2.1: Oben: Banbegrenztes Signal f(t) mit Grenzfrequenz ω̂ und Fou-rier Transformierte F (ω). Mitte: Abgetastetes Signal fp(t) = f(t)p(t). Die Ab-tastfrequenz ωs = 2π/Ts ist größer als 2ω̂, daher kein Aliasing. Die Kopien vonF (ω) überlappen sich nicht. Unten: Abtastfrequenz ωs ist kleiner als 2ω̂, dahertritt Aliasing ein. Die Kopien von F (ω) überlappen sich.


2.4 Bandbegrenzte SignaleEine Funktion f ∈ R→ R heißt bandbegrenzt mit Grenzfrequenz ω̂ wenn

F (ω) = 0 für alle ω mit |ω| ≥ ω̂.

Anschaulich bedeutet dies, dass f(t) keine Schwingungskomponenten enthält,deren Frequenz oberhalb von ω̂ ist.

Aliasing, d.h. eine Überlappung im Frequenzbereich nach Abtastung wirdalso vermieden, wenn die Kopien von F (ω) um mehr als 2ω̂ auseinander liegen.Die Bedingungen um Aliasing zu vermeiden sind somit:

• Das Signal f(t) ist bandbegrenzt mit einer Grenzfrequenz ω̂.

• Für die Abtastfrequenz ωs gilt

ωs > 2ω̂.


2.5 SignalrekonstruktionNachdem die Abtastwerte im Rechner digital verarbeitet wurden, soll nun ausden Abtastwerten eine zeitkontinuierliche Funktion rekonstruiert werden. DiesenSchritt nennt man auch digital-analog Wandlung. Wie oben gezeigt, bestehtdie Fourier Transformierte von fp(t) aus einer unendlichen Wiederholung vonKopien von F (ω) im Abstand ωs. Wenn Aliasing vermieden wurde, genügt eseine dieser Kopien auszuschneiden und mit der inversen Fourier Transformationin den Zeitbereich zurück zu transformieren. Hierzu verwendet man einen sog.idealen Tiefpass mit Verstärkungsfaktor Ts, der im Frequenzbereich folgendeDarstellung hat:

H(ω) ={Ts falls |ω| < ωs/20 sonst.

Im Frequenzbereich ergibt die Multiplikation von Fp(ω) und H(ω) die FourierTransformierte F (ω) der ursprünglichen Zeitfunktion f(ω):

Fp(ω)H(ω) =(

1Ts

∞∑k=−∞

F (ω − kωs))H(ω)

= F (ω).

Beim letzten Schritt war essentiell, dass F (ω) bandbegrenzt mit Grenzfrequenzωs/2 ist. Da im Rechner lediglich die Folge der Abtastwerte bzw. die Funkti-on fp(t) vorliegt, muss die Multiplikation mit H(ω) im Zeitbereich ausgeführtwerden. Mit dem Faltungstheorem gilt

(fp ∗ h)(t) c s F (ω)H(ω).

Die inverse Fourier Transformierte h(t) von H(ω) berechnet man wie folgt:

h(t) = 12π

∫ ∞−∞

H(ω)ejωtdω

= Ts2π

∫ ωs/2

−ωs/2ejωtdω

= Ts2πjt

[ejωt

]ωs/2−ωs/2

= Tsπt

12j

(ejωst/2 + e−jωst/2

)= Ts

πtim(ejωst/2

)= Ts

πtsin(πt

Ts

)da ωs = 2π

Ts

= si(πt

Ts

)= sinc(t/Ts).

wobeisi(x) = sin(x)

xund sinc(x) = si(πx).


Damit kann man aus den Abtastwerten f(nTs) die zeitkontinuierliche Funktionf(t) wie folgt rekonstruieren:

f(t) = (fp ∗ h)(t)

=( ∞∑n=−∞

f(nTs)δ(t− nTs))∗ h(t)

=∞∑

n=−∞f(nTs) (h(t) ∗ δ(t− nTs))

=∞∑

n=−∞f(nTs)

∫ ∞−∞

h(τ)δ(t− nTs − τ)dτ

=∞∑

n=−∞f(nTs)

∫ ∞−∞

h(t− nTs)δ(t− nTs − τ)dτ

=∞∑

n=−∞f(nTs)h(t− nTs)

∫ ∞−∞

δ(t− nTs − τ)dτ︸︷︷︸=1

=∞∑

n=−∞f(nTs)h(t− nTs)

=∞∑

n=−∞f(nTs) sinc

(t− nTsTs

)

=∞∑

n=−∞f(nTs) sinc (t/Ts − n) .

Theorem 2.1 (Abtasttheorem)Sei f(t) bandbegrenzt mit Grenzfrequenz ω̂ und seien

fn = f(nTs), n = −∞, . . . ,∞

die Abtastwerte von fn mit Abtastintervall Ts = 2π/ωs. Dann kann f(t)exakt aus den Abtastwerten fn rekonstruiert werden falls

ωs > 2ω̂.

Für die Rekonstruktion gilt

f(t) =∞∑

n=−∞fn sinc (t/Ts − n) .


t

f(t)

fp(t)

ω

ω

ω

F (ω)

ω̂−ω̂

t

t

Ts−ωs

2

ωs−ωs ωs

2

ωs

2−ωs

2

f(t)

Fp(ω)

Fs(ω)H(ω) = F (ω)

Abbildung 2.2: Oben: Banbegrenztes Signal f(t) mit Grenzfrequenz ω̂ und Fou-rier Transformierte F (ω). Mitte: Abgetastetes Signal fp(t) = f(t)p(t). Die Ab-tastfrequenz ωs = 2π/Ts ist größer als 2ω̂, daher kein Aliasing. Die Kopien vonF (ω) überlappen sich nicht. Unten: Durch Multiplikation von Fp(ω) und H(ω)entsteht F (ω). Rücktransformation in den Zeitbereich ergibt das Originalsignalf(t).


2.6 Tiefpass FilterMit der Theorie des letzten Kapitels wird nun gezeigt, wie man ein Signal f(t)Tiefpass filtern kann mit Cutoff Frequenz ωc. Im Frequenzbereich bedeutet dies,dass die Fourier Transformierte F (ω) für alle ω mit |ω| ≥ ωc Null gesetzt wird.Dies wird durch Multiplikation

F (ω)U(ω)

mit einer Übertragungsfunktion

U(ω) ={

1 falls |ω| < ωc0 sonst.

erreicht. Im Rechner ist das Signal f(t) nur duch Abtastwerte

fn = f(nTs)

gegeben. Der Impulszug p(t) bzw. seine Fourier Reihe wurden im vorigen Kapitelhergeleitet:

p(t) =∞∑

n=−∞δ(t− nTs) = 1

Ts

∞∑k=−∞

ejkωst

Für das abgetastete Signal fp(t) gilt damit

fp(t) = f(t)p(t)

= f(t) 1Ts

∞∑k=−∞

ejkωst

= 1Ts

∞∑k=−∞

f(t)ejkωst

c s 1Ts

∞∑k=−∞

F (ω − kωs)

= Fp(ω).

Es wird angenommen, dass die Voraussetzungen des Abtasttheorems erfülltsind, d.h. f(t) ist bandbegrenzt mit Grenzfrequenz ω̂ und ωs > 2ω̂. In diesemFall überlappen sich die um kωs verschoebenen Kopien F (ω − kωs) von F (ω)nicht und es gilt

F (ω) = TsFp(ω) für alle ω mit |ω| < ω̂.

Für die Tiefpass Filterung mit Cutoff Frequenz ωc < ω̂ gilt daher

F (ω)U(ω) = TsFp(ω)U(ω) für alle ω.

Die Multiplikation mit U(ω) bewirkt ja, dass beide Seiten Null sind falls |ω| ≥ ω̂.


Multiplikation mit Übertragungsfunktion U(ω) entspricht Faltung mit Im-pulsantwort u(t), die man durch inverse Fourier Transformation erhält:

u(t) = 12π

∫ ∞−∞

U(ω)ejωtdω

= 12π

∫ ωc

−ωc

ejωtdω

= 12πjt

(ejωct − e−jωct

)= 1

πtsin(ωct)

= ωcπ

si(ωct)

Die Multiplikation im Frequenzbereich

F (ω)U(ω) = TsFp(ω)U(ω)

wird nun im Zeitereich durch Faltung ausgeführt. Um die Notation zu vereinfa-chen, definieren wir

H(ω) = TsU(ω) bzw. h(t) = Tsu(t).

Damit gilt

(f ∗ u)(t) = Ts(fp ∗ u)(t)= (fp ∗ Tsu)(t)= (fp ∗ h)(t)

=( ∞∑n=−∞

fnδ(t− nTs))∗ h(t)

=∞∑

n=−∞(fnδ(t− nTs) ∗ h(t))

=∞∑

n=−∞fn (δ(t− nTs) ∗ h(t))

=∞∑

n=−∞fnh(t− nTs).

Von diesem Tiefpass gefilterten Signal soll nun der `-te Abtastwert berechnet


werden.

(f ∗ u)(`Ts) =∞∑

n=−∞fnh(`Ts − nTs)

=∞∑

n=−∞fnh((`− n)Ts)

=∞∑

n=−∞fnh`−n

= (f ∗ h)`.

Die Faltung in der letzten Zeile bezeichnet hierbei die diskrete Faltung der Ab-tastwerte

f` = f(`Ts) und h` = h(`Ts).

Die Koeffizienten des Tiefpass Filters sind somit

h` = h(`Ts)= Tsu(`Ts)

= Tsωcπ

si(ωc`Ts)

= 2ωcωs

si(ωc`Ts)

= 2ωcωs

si(

2πωcωs

`

)= αsinc(α`)

wobei

α = 2ωcωs

.

Da die Berechnung der unendlichen Faltungssumme praktisch nicht durch-führbar ist und die sinc-Funktion für betragsgroße Wert von ` abklingt, genügtes, endlich viele Summanden zu betrachten, d.h.

(f ∗ h)` =∞∑

n=−∞hnf`−n

≈N/2∑

n=−N/2

hnf`−n.

Es handelt sich hier um ein nicht kausales System, d.h. um den `-ten Abtast-wert von f ∗ h berechnen zu können, werden Abtastwerte von f zu zukünftigenZeitpunkten `−n mit n < 0 benötigt. Dies lässt sich beheben, indem man f ∗h


um N/2 Takte verzögert. Damit ergibt sich die Formel

g` = (f ∗ h)`−N/2

=N/2∑

n=−N/2

hnf`−N/2−n

=N∑n=0

hn−N/2f`−n

=N∑n=0

h′nf`−n

Die Koeffizienten des kausalen Tiefpassfilters h′ mitN/2 Takten Verzögerungsind somit

h′` = h`−N/2

= αsinc(α(`−N/2)), ` = 0, . . . , N.


2.7 FensterungIm letzten Abschnitt wurde zur praktischen Durchführug der Tiefpass Filterungdie unendliche Summe

∞∑n=−∞

hnf`−n

durch eine endliche SummeN/2∑

n=−N/2

hnf`−n

approximiert. Dies bedeutet, dass die Filterkoeffizienten hn bzw. un für |n| ≥N/2 Null gesetzt wurden. Was bedeutet dies für die Frequenzeigenschaften desFilters? Im zeitkontinuierlichen Bereich lässt sich das Nullsetzen eines Teils derImpulsantwort u(t) durch Multiplikation

u(t)w(t)

mit einer Fensterfunktion w(t) realisieren, wobei

w(t) ={

1 falls t < T̂0 sonst

und T̂ = N/2Ts die Fensterbreite ist. Durch die Approximation wird das Signalf(t) also nicht mit u(t) sondern mit u(t)w(t) gefaltet. Mit dem Faltungssatzfolgt

u(t)w(t) c s 12πU(ω) ∗W (ω)

und damit

f(t) ∗ (u(t)w(t)) c s F (ω) 12π (U(ω) ∗W (ω)).

Anstatt also wie beabsichtigt im Frequenzbereich mit U(ω) zu multiplizieren,wird mit

12πU(ω) ∗W (ω)

multipliziert. Durch Fourier Transformation erhält man

W (ω) =∫ ∞−∞

w(t)e−jωtdt

=∫ T̂

−T̂e−jωtdt

= − 1jω

[e−jωt

]T̂−T̂

= 1jω

(ejωT̂ − e−jωT̂

)= 2

ωsin(ωT̂ )

= 2T̂ si(ωT̂ ).


Wenn T̂ gegen unendlich geht, ist

W (ω) s c 1c s 2πδ(ω)

und damit

12πU(ω) ∗W (ω) = U(ω).

Für endliche Werte von T̂ ist die Berechnung der Faltung nicht geschlossenmöglich:

12πU(ω) ∗W (ω) = 1

2π

∫ ∞−∞

U(α)W (ω − α)dα

= T̂

π

∫ ωc

−ωc

si((ω − α)T̂ )dα

= 1π

(Si((ω + ωc)T̂ )− Si((ω − ωc)T̂ )

)wobei Si(x) eine Stammfunktion von si(x) ist.

Um jedoch einen Endruck zu gewinnen, was die Fensterung bewirkt, ist innachfolgenden Bildern die Tiefpassfilterung mit Cutoff Frequenz ωc = 1 undFensterbreite T̂ = 7 bzw. T̂ = 20 Sekunden dargestellt.


ω

ω

ω

U(ω)

W (ω)

1

2πU(ω) ∗W (ω)

ωc−ωc

ωc−ωc

Abbildung 2.3: Gefensterter Tiefpassfilter mit ωc = 1 und T̂ = 7. Durch dasrelativ kurze Fenster wird der Tiefpass stark verfälscht.


ω

ω

ω

U(ω)

W (ω)

1

2πU(ω) ∗W (ω)

ωc−ωc

ωc−ωc

Abbildung 2.4: Gefensterter Tiefpassfilter mit ωc = 1 und T̂ = 20. Durch dasrelativ lange Fenster nähert sich W (ω) einem Dirac Impuls und der Tiefpasswird nur geringfügig verfälscht.


2.8 Zeitdiskrete Fourier TransformationEs gibt übrigens noch eine zweite Möglichkeit, die Fourier Transformierte Fp(ω)von fp(t) zu berechnen. Ausgehend von

fp(t) =∞∑

n=−∞f(nTs)δ(t− nTs)

erhält man mit der Korrespondenz

δ(t− nTs) c s e−jnωTs .

die Fourier Transformierte

fp(t) c s ∞∑n=−∞

f(nTs)e−jnωTs

︸︷︷︸Fp(ω)

.

Man kann also Fp(ω) entweder direkt aus den Abtastwerten f(nTs) berechnenoder aus F (ω):

Fp(ω) =∞∑

k=−∞F (ω − kωs)

=∞∑

n=−∞f(nTs)e−jnωTs

Aus beiden Darstellungen sieht man sofort, dass Fp(ω) periodisch mit Perioden-dauer ωs ist, d.h.

Fp(ω + ωs) = Fp(ω) für alle ω.

Wir nehmen nun der Einfachheit halber an, dass das Abtastintervall Ts = 1und damit ωs = 2π ist. Mit der Folge von Abtastwerten

fn = f(nTs), n = 0, 1, 2, . . .

gilt daher

Fp(ω) =∞∑

n=−∞fne−jnω.

Diese Transformation einer Folge fn in den Frequenzbereich heißt zeitdiskreteFourier Transformation (DTFT).

Falls fn = 0 für n < 0 ist Fp(ω) nichts anderes als die z-Transformierte vonfn für z = ejω.

Man kann aus Fp(ω) durch inverse Fourier Transformation wieder denImpulszug fp(t) und daraus die Abtastwerte fn berechnen. Es gibt jedoch aucheinen direkteren Weg: Hierzu multipliziert man zunächst beide Seiten mit ejkω

Fp(ω)ejkω =∞∑

n=−∞fne−jnωejkω


und integriert dann für ω von 0 bis 2π:∫ 2π

0Fp(ω)ejkωdω =

∫ 2π

0

∞∑n=−∞

fne−jnωejkωdω

=∞∑

n=−∞fn

∫ 2π

0ej(k−n)ωdω

Da ∫ 2π

0ej(k−n)ωdω =

{2π falls k = n0 sonst

folgt ∫ 2π

0Fp(ω)ejkωdω = 2πfk

bzw.

fk = 12π

∫ 2π

0Fp(ω)ejkωdω.

Der Unterschied zur inversen Fourier Transformation von Fp(ω), bei der derImpulszug fp(t) herausgekommen wäre, besteht darin, dass nur von 0 bis 2πintegriert wurde und nicht von −∞ bis ∞.

Zusammenfassend ist die DTFT und ihre Inverse wie folgt definiert.Der Zusammenhang gilt auch dann, wenn die Voraussetzungen des Abtasttheo-rems nicht efüllt sind. Man kann aus Fp(ω) immer die Abtastwerte fk exaktrekontruieren, aber nicht f(t) falls zu langsam abgetastet wurde.

Definition 2.2 (Zeitdiskrete Fourier Transformation)Die zeitdiskrete Fourier Transformation (DTFT) der Folge fk ist definiertdurch

Fp(ω) =∞∑

k=−∞fke−jkω.

Damit gilt

fk = 12π

∫ 2π

0Fp(ω)ejkω.

3 DISKRETE FOURIER TRANSFORMATION 28

3 Diskrete Fourier Transformation3.1 Bandbegrenzte periodische SignaleSei f(t) ein T0-periodisches Signal mit Fourier Reihe

f(t) =∞∑

k=−∞zke

jkω0t, ω0 = 2π/T0.

Weiterhin wird angenommen, dass f(t) bandbegrenzt mit Grenzfrequenz ω̂ ist.Dies bedeutet, dass nur endlich viele Fourier Koeffizienten zk ungleich Null sind,wie nachfolgend gezeigt wird. Mit der Korrespondenz

ejkω0t c s 2πδ(ω − kω0)

lässt sich die Fourier Transformierte F (ω) von f(t) bestimmen.

F (ω) = 2π∞∑

k=−∞zkδ(ω − kω0).

Da f(t) bandbegrenzt ist, folgt F (ω) = 0 falls ω ≥ ω̂ und damit

zk = 0 falls kω0 ≥ ω̂ bzw. falls k ≥ ω̂

ω0.

Das Signal wird nun während einer Periode an n äquidistanten Stellen ab-getastet, d.h.

ωs = nω0.

Weiterhin wird angenommen, dass die Voraussetzungen des Abtasttheorems er-füllt sind, d.h.

ωs > 2ω̂.

Daraus folgt

n

2 >ω̂

ω0

und damit

zk = 0 falls k ≥ n

2 .

In der Fourier Reihe bleiben also nur endlich viele Summanden übrig und esgilt

f(t) =n/2−1∑

k=−n/2+1

zkejkω0t

=n/2−1∑

k=−n/2+1

zkejkωst/n.


Für die Abtastwerte f` = f(`Ts) gilt

f` =n/2−1∑

k=−n/2+1

zkejk`ωsTs/n

=n/2−1∑

k=−n/2+1

zke2πjk`/n.

Kosmetik. Um zu einer vektoriellen Schreibweise zu gelangen, muss die Sum-me

f` =n/2−1∑

k=−n/2+1

zke2πjk`/n

in eine Summe

f` =n−1∑k=0

. . .

umgeformt werden. Dazu definieren wir die Fourier Koeffizienten zk für k =n/2, . . . , n− 1, die ja in der Ausgangssumme gar nicht aufreten und bisher Nullwaren, wie folgt um:

zn/2 = 0zk = zk−n, k = n/2 + 1, . . . , n− 1,

siehe Bild 3.1. Für die negativen k-Summanden in der Ausgangssumme erhältman damit

−1∑k=−n/2+1

zke2πjk`/n =

n−1∑k=n/2+1

zk−ne2πj(k−n)`/n

=n−1∑

k=n/2+1

zke2πjk`/ne−2πjn`/n

=n−1∑

k=n/2+1

zke2πjk`/n e−2πj`︸︷︷︸

=1

=n−1∑

k=n/2+1

zke2πjk`/n.


Für die gesamte Summe gilt nun

f` =n/2−1∑

k=−n/2+1

zke2πjk`/n

=−1∑

k=−n/2+1

zke2πjk`/n +

n/2−1∑k=0

zke2πjk`/n

=n−1∑

k=n/2+1

zke2πjk`/n +

n/2−1∑k=0

zke2πjk`/n

=n−1∑k=0

zke2πjk`/n.

21 3−1−2−3

5 6 7

z1

z2

z3

z1

z2

z3

z1

z2

z3

z1

z2

z3

k

k

21 3 4

Abbildung 3.1: Beispiel für n = 8. Die Koeffizienten zk mit k = −1,−2,−3werden nach k = 7, 6, 5 verschoben.


3.2 Matrix NotationIm vorigen Abschnitt wurde eine Formel für die Abtastwerte eines T -periodischenSignals f(t) hergeleitet. Es wurde vorausgesetzt, dass das Signal bandbegrenztist und die Forderung des Abtasttheorems eingehalten wurde. Damit gilt

f` =n−1∑k=0

zke2πjk`/n.

Man kann diese Summe auch als Produkt eines Zeilen- und eines Spaltenvektorsinterpretieren:

f` =(e2πj0`/n e2πj1`/n . . . e2πj(n−1)`/n

)z0z1...

zn−1

.

Mitbk` = e2πjk`/n

erhält man

f` = (b0` b1` . . . bn−1,`)

z0z1...

zn−1

.

Schreibt man diese Formel für die n Abtastwerte f0, . . . , fn−1 einer Periodeuntereinander, ergibt sich eine Matrix Vektor Multiplikation

f0f1...

fn−1

︸︷︷︸

~f

=

b00 b10 . . . bn−1,0b01 b11 . . . bn−1,1...

.... . .

...b0,n−1 b1,n−1 . . . bn−1,n−1

︸︷︷︸

B

z0z1...

zn−1

︸︷︷︸

~z

.

bzw.~f = B~z.

Die Matrix B ist übrigens symmetrisch, da

bk` = e2πjk`/n = e2πj`k/n = b`k.

Man kann die Indizes von bk` also beliebig vertauschen. Um aus gegebenenAbtastwerten die zugehörigen Frequenzkomponenten zu berechnen, muss manB invertieren, d.h.

~z = B−1 ~f.

Die Berechnung von B−1 ist aber denkbar einfach, da die Spaltenvektoren vonB paarweise orthogonal sind und Norm

√n haben:


Theorem 3.1Seien

~bu =

bu0bu1...

bu,n−1

, ~bv =

bv0bv1...

bv,n−1

die u-te bzw. v-te Spalte von B. Dann gilt

~bu ◦~bv ={

0 falls u 6= vn sonst

Beweis. Seien ~bu und ~bv wie in Theorem 3.1 und

s = ~bu ◦~bv

=n−1∑k=0

bukbvk

=n−1∑k=0

e−2πjuk/ne2πjvk/n

=n−1∑k=0

e2πjk(v−u)/n.

• Ist u = v dann ist

e2πjk(v−u)/n = e0 = 1

und damit

s =n−1∑k=0

e2πjk(v−u)/n =n−1∑k=0

1 = n.

• Sei nun u 6= v. Dann ist

s =n−1∑k=0

e2πjk(v−u)/n

=n−1∑k=0

(e2πj(v−u)/n

)︸︷︷︸

a

k

=n−1∑k=0

ak

Multiplikation mit a ergibt

as = a

n−1∑k=0

ak =n∑k=1

ak


und damit

as− s =n∑k=1

ak −n−1∑k=0

ak = an − 1

s(a− 1) = an − 1s = (an − 1)/(a− 1).

Da aberan = e2πj(v−u) = 1

folgts = 0.

Damit gilt

B∗B =

n 0 . . . 00 n . . . 0...

.... . .

...0 0 . . . n

= nE

wobei E die n×n Einheitsmatrix ist und B∗ die adjungierte Matrix von B, d.h.die Matrix, die man erhält wenn man B transponiert und alle Komponentenkomplex konjugiert. Multiplikation mit B−1 von rechts und Division durch nergibt

1nB∗ = B−1.

Die Inversion von B ist mit dieser Formel sehr einfach und man erhält

~f = B~z

~z = 1nB∗ ~f.

Man kann also aus den Abtastwerten f` durch eine simple Matrix-Vektor Mul-tiplikation die Amplituden und Phasen zk der beteiligten Schwingungen erhal-ten. Diese Operation nennt man diskrete Fourier Transformation (DFT). DieUmkehroperation, d.h. die Berechnung der Abtastwerte f` aus den komplexenFourier Koeffizienten zk heißt inverse diskrete Fourier Transformation (IDFT).

Definition 3.2 (Diskrete Fourier Transformation)Sie diskrete Fourier Transformation DFT ∈ Cn → Cn ist definiert durch

DFT (~f) = 1nB∗ ~f.

Die inverse diskrete Fourier Transformation IDFT ∈ Cn → Cn ist defi-niert durch

IDFT (~z) = B~z.

Hierbei ist B ∈ Cn×n mit

bk` = e2πjk`/n, k, ` = 0, . . . , n− 1.


Komponentenweise sind die Formeln

f` =n−1∑k=0

zke2πjk`/n ` = 0, . . . , n− 1

zk = 1n

n−1∑`=0

fè−2πjk`/n k = 0, . . . , n− 1.


3.3 BeispieleBeispiel 3.3 In Bild 3.2 oben ist eine Periode der T0-periodischen Funktion

f(t) = cos(2ω0t+ π) + 0.2 cos(3ω0t) + 0.4 cos(6ω0t)

mit ω0 = 2π/T0 dargestellt. Es handelt sich also um eine Überlagerung vonSchwingungen mit doppelter, dreifacher und sechfacher Grundfrequenz.Das Signal wird während einer Periode an n = 16 äquidistanten Stellenabgetastet. Die Abtastfrequenz beträgt somit

ωs = 16ω0.

Da die höchste im Signal auftretende Frequenz nur 6ω0 und damit kleinerals ωs/2 = 8ω0 ist, sind die Voraussetzungen des Abtasttheorems erfüllt.Aus den Abtastwerten f`, ` = 0, . . . , 15 werden mit der DFT die FourierKoeffizienten zk berechnet. Aus

z0 = A0

zk = 12Ake

jϕk , k = 1, 2, . . . , 7

berechnen sich die Amplituden der k-ten Oberschwingung durch

A0 = |z0|Ak = 2|zk|,

siehe Bild 3.2 unten.


84 12

2 3 6

0.2

1

10 1413

Ak = 2|zk|

0.4

ℓ

k

fℓ

T0

cos(2ω0t+ π) + 0.2 cos(3ω0t) + 0.4 cos(6ω0t)

Abbildung 3.2: Diskrete Fourier Transformation für n = 16.


Beispiel 3.4 Das selbe Signal wie im vorigen Beispiel wird nun an doppeltso vielen Stellen abgetastet, d.h. die Abtastfrequenz ist nun

ωs = 32ω0,

siehe Bild 3.3 oben. Die diskrete Fourier Transformation liefert im Prinzipdie selben Werte (Bild 3.3 unten). Man sieht, dass hier noch viel mehrPlatz für höhere Frequenzen wäre als im vorigen Beispiel. In der Tat wärehier das Abtasttheorem noch erfüllt wenn Frequenzkomponenten bis zur15-fachen Grundfrequenz auftreten würden während das Limit vorher beider 7-fachen Grundfrequenz lag.

16

0.2

1

ℓ

Ak = 2|zk|

0.4

8 24

2 3 6 302926k

fℓ cos(2ω0t+ π) + 0.2 cos(3ω0t) + 0.4 cos(6ω0t)

T0



Beispiel 3.5 In einer Rechteckschwingung treten beliebig hohe Frequenzenauf. Sie ist daher mit Sicherheit nicht bandbegrenzt. Dennoch tasten wirein Rechtecksignal ab und berechnen die DFT der Abtastwerte, siehe Bild3.4. Rechnet man von den Fourier Koeffizienten zk wieder mittels derFormel

f(t) = A0 +n/2−1∑k=1

Ak cos(kωt+ ϕk)

z0 = A0

zk = 12Ake

jϕk , k = 1, 2, . . . , n/2− 1

auf das Ausgangssignal zurück, erhält man nur eine Approximation. DerGrund hierfür liegt in der Verletzung des Abtasttheorems. Alle Frequenzengrößer oder gleich der halben Abtastfrequenz wurden vernachlässigt. DieAbtastwerte f` können aber natürlich wieder exakt durch

~f = B~z

aus den Fourier Koeffizienten berechnet werden.


84 12ℓ

Ak = 2|zk|

ℓT0

k

f(t) =

{1 falls 0 ≤ t < T0/2

−1 falls T0/2 ≤ t < T0

T0

fℓ

f(t) = A0 +

7∑

k=1

Ak cos(kω0t+ ϕk)


4 SCHNELLE FOURIER TRANSFORMATION 40

4 Schnelle Fourier TransformationIn Definition 3.2 wurde die DFT eines Signalvektors ~f ∈ Rn definiert als

~z = 1nB∗ ~f.

Man kann von den Fourier Koeffizienten zk auf die ursprünglichen Abtastwertefk zurückrechnen mit

~f = B~z.

Diese Operation wird auch inverse diskrete Fourier Transformation (IDFT) ge-nannt. Die Matrix B hat die Einträge

bk` = e2πjk`/n, k, ` = 0, 1, . . . , n− 1.

Da bk` = b`k ist B symmetrisch und man braucht sich daher keine Gedankenzu machen welcher Index der Zeilen- bzw. Spaltenindex ist. Für n = 4 ist z.B.

B =

1 1 1 11 j −1 −j1 −1 1 −11 −j −1 j

.

Schaut man sich B zeilenweise an und stellt jeden Eintrag als komplexen Zeigerdar, sieht man dass sich der Zeiger

• in der ersten Zeile gar nicht dreht,

• in der zweiten Zeile mit 90◦ dreht,

• in der dritten Zeile mit 180◦ dreht,

• in der vierten Zeile mit 270◦ dreht

und zwar immer gegen den Uhrzeigersinn. Allgemein dreht sich der Zeiger inder k-ten Zeile mit 2πk/n Radian gegen den Uhrzeigersinn, siehe Bild 4.1 oben.Die Matrix B∗ ist gleich wie B, nur dass alle Komponenten konjugiert komplexsind. (Da B symmetrisch ist, hat die Transposition keinen Effekt.) In Bild 4.1unten erkennt man dies darin, dass sich die Zeiger nun im Uhrzeigersinn drehen.

Berechnet man die DFT durch Matrix Vektor Multiplikation, so kostetdies n2 komplexe Multiplikationen für die Multiplikation B∗ ~f . Da B∗ keine“zufällige” Matrix ist sondern eine sehr regelmäßige Struktur hat, kann man dieMultiplikation viel effizienter durchführen. Dies ist insbesondere dann der Fallwenn n eine Zweierpotenz ist. Der Algorithmus hierfür heißt schnelle FourierTransformation bzw. Fast Fourier Transform (FFT).


B =

B∗ =

Abbildung 4.1: Matrix B und B∗ für n = 8.


Vereinfachung. Um die Darstellung etwas einfacher zu machen, lassen wirden Faktor 1/n bei der Definition der DFT vorübergehend einfach weg. Die somodifizierte DFT eines n-stelligen Vektors ~f ∈ Rn ist also der Vektor ~z ∈ Cnmit

~z = B∗ ~f

bzw.

zk = (B∗ ~f)k =n−1∑`=0

f` e−2πjk`/n, k = 0, 1, . . . , n− 1.

Aufwandsberechnung. Die Idee der FFT besteht darin, eine DFT der Ord-nung n durch zwei DFT’s der Ordnung n/2 zu berechnen. Da der Aufwandfür die Matrix Vektor Multiplikation quadratisch ist, gewinnt man hierdurchRechenzeit:

• Aufwand für eine n-DFT:

n2 Multiplikationen.

• Aufwand für zwei n/2-DFTs’:

2(n/2)2 = n2/2 Multiplikationen.

Allerdings entsteht durch diese Zerlegung zusätzlicher Rechenaufwand von n/2Multiplikationen. Dennoch gewinnt man insgesamt Rechnzeit, da

n2/2 + n/2 < n2.

Natürlich kann man die beiden n/2-DFT’s wiederum durch jeweils zwei n/4-DFT’s berechnen usw. Falls n eine reine Zweierpotenz ist, lässt sich diese Zer-legung ld(n) Mal durchführen. Zuletzt ist man bei DFT’s der Ordnung 1 ange-langt, die keinen Rechenaufwand kosten. Bei jedem der ld(n) Schritte entstehtOverhead von n/2 Multiplikationen, so dass der Gesamtaufwand für die FFT

ld(n)n/2

Multiplikationen beträgt. Für n = 1024 erhält man

n2 ≈ 106, ld(n)n/2 ≈ 500,

d.h. die FFT ist um Faktor 200 schneller als die DFT.


Formeln. Die Summe zur Berechnung von zk wird zunächst in zwei Teilsum-men zerlegt, wobei in der ersten Teilsumme nur die geraden Abtastwerte von ~fauftreten und in der zweiten die ungeraden:

zk =n−1∑`=0

fè−2πjk`/n

=∑

`=0,2,4,...fè−2πjk`/n +

∑`=1,3,5,...

fè−2πjk`/n.

Die Summationsvariable ` kann durchgängig von 0 bis n/2 − 1 laufen, indemman in der ersten Summe ` durch 2` ersetzt und in der zweiten durch 2`+ 1:

zk =n/2−1∑`=0

f2è−2πjk2`/n +

n/2−1∑`=0

f2`+1e−2πjk(2`+1)/n

=n/2−1∑`=0

f(g)` e−2πjk2`/n +

n/2−1∑`=0

f(u)` e−2πjk(2`+1)/n

wobei

~f (g) =

f0f2f4...

∈ Rn/2, ~f (u) =

f1f3f5...

∈ Rn/2.

Durch Anwenden der Gesetze der e-Funktion und 2/n = 1/(n/2) erhält man

zk =n/2−1∑`=0

f(g)` e−2πjk`/(n/2) +

n/2−1∑`=0

f(u)` e−2πjk`/(n/2)e−2πjk/n

=n/2−1∑`=0

f(g)` e−2πjk`/(n/2)

︸︷︷︸ak

+(n/2−1∑`=0

f(u)` e−2πjk`/(n/2)

︸︷︷︸bk

)e−2πjk/n

= ak + bke−2πjk/n.

In der zweiten Summe konnte man den Faktor e−2πjk/n ausklammern, da ervon ` unabhängig ist.

Der entscheidende Punkt, durch den Rechenaufwand gespart werden kann,besteht darin, dass

ak = ak+n/2 und bk = bk+n/2.

Wenn man also für ein bestimmtes k den Wert von zk berechnen möchte unddazu ak und bk bestimmt hat, kann man ohne Zusatzaufwand auch gleich zk+n/2berechnen. Man bekommt also zwei Fourier Koeffizienten zum Preis von einem.


Dies sieht man wie folgt für ak (und analog für bk).

ak+n/2 =n/2−1∑`=0

f(g)` e−2πj(k+n/2)`/(n/2)

=n/2−1∑`=0

f(g)` e−2πjk`/(n/2)e−2πj(n/2)`/(n/2)

=n/2−1∑`=0

f(g)` e−2πjk`/(n/2) e−2πj`︸︷︷︸

=1= ak

Damit gilt

zk+n/2 = ak+n/2 + bk+n/2e−2πj(k+n/2)/n

= ak + bke−2πjk/ne−2πj(n/2)/n

= ak + bke−2πjk/n e−πj︸︷︷︸

=−1

= ak − bke−2πjk/n.

Zu Berechnen ist somit für k = 0, . . . , n/2− 1:

ak =n/2−1∑`=0

f(g)` e−2πjk`/(n/2)

bk =n/2−1∑`=0

f(u)` e−2πjk`/(n/2)

zk = ak + bke−2πjk/n

zk+n/2 = ak − bke−2πjk/n

Man kann nun die ak und bk, die man ja nur für k = 0, . . . , n/2− 1 berechnenmuss, zu Vektoren mit jeweils n/2 Komponenten zusammenfassen:

~a = B∗n/2~f (g)

~b = B∗n/2~f (u).

Dies sind die eingangs erwähnten beiden n/2-DFT’s, deren Berechnung n2/2Multiplikationen kosten. Zusätzlich hat man n/2 Multiplikationen für die Pro-dukte

bke−2πjk/n, k = 0, . . . , n/2− 1.

Der Gesamtaufwand beträgt somit

n2/2 + n/2 Multiplikationen.


z0

z1

z2

z3

z4

z5

z6

z7

(n2

)2 Multiplikationen a0

a1

a2

a3

b0

b1

b3

b2

f0

f2

f4

f6

f1

f3

f5

f7

n/2 Multiplikationen

(n2

)2 Multiplikationen

akbk

akbk

zk

zk+n/2

zk = ak + bke−2πjk/n

zk+n/2 = ak − bke−2πjk/n

n/2-DFT

n/2-DFT

Abbildung 4.2: Reduktion einer DFT der Dimension n = 8 auf zwei DFT’s derOrdnung n/2 = 4.


Rekursion. Der selbe Trick wird nun angewandt um die DFTs der Ordnungn/2 auf jeweils 2 DFTs der Ordnung n/4 zu reduzieren, siehe Bild 4.3. VierDFTs der Ordnung n/4 kosten

4×(n

4

)2= n2

4

Multiplikationen. Hinzu kommen noch n/2 Multiplikationen um die Ergebnisseder DFTs der Dimension n/4 zu kombinieren und n/2 Multiplikationen um dieErgebnisse der DFTs der Dimension n/2 zu kombinieren. Der Gesamtaufwandbeträgt also n2/4 + n.

Diesen Prozess kann man so lange weiterführen bis man bei DFT’s derOrdnung 1 angelangt ist, was nach ld(n) Schritten der Fall ist. Da eine DFT derOrdnung 1 gar nichts kostet, bleiben nur in jedem Schritt n/2 Multiplikationen,d.h. insgesamt

12nld(n)

Multiplikationen.


z0

z1

z2

z3

z4

z5

z6

z7

DFT

DFT

DFT

DFT

f0

f4

f2

f6

f1

f5

f3

f7

4(n4

)2 Mult. n/2 Mult. n/2 Mult.

Abbildung 4.3: Reduktion einer DFT der Dimension n = 8 auf vier DFT’s derOrdnung n/4 = 2.

z0

z1

z2

z3

z4

z5

z6

z7

f0

f4

f2

f6

f1

f5

f3

f7

n/2 Mult. n/2 Mult. n/2 Mult.

Abbildung 4.4: FFT der Dimension n = 8. Es sind 12nld(n) komplexe Multipli-

kationen erforderlich.


Bitumkehr. Wie man in Bild 4.3 sieht, werden die Komponenten des Einga-bevekors ~f zuerst umsortiert, bevor sie in die DFT Kette eingespeist werden.Für n = 8 ist die Reihenfolge

f0, f4, f2, f6, f1, f5, f3, f7.

Das allgemeine Prinzip hinter dieser Umsortierung wird klar, wenn man dieIndizes binär darstellt und mit der normalen Reihenfolge vergleicht:

0 4 2 6 1 5 3 7000 100 010 110 001 101 011 111000 001 010 011 100 101 110 1110 1 2 3 4 5 6 7

Die Reihenfolge, in der die ~f -Komponenten eingespeist werden müssen, erhältman also dadurch, dass man die Zahlen 0, . . . , n − 1 binär codiert, die Bitfol-gen umkehrt und ins Dezimalsystem zurückrechnet. Für n = 16 erhält mandementsprechend folgende Reihenfolge:

0 1 2 3 4 5 . . . 14 150000 0001 0010 0011 0100 0101 . . . 1110 11110000 1000 0100 1100 0010 1010 . . . 0111 11110 8 4 12 2 10 . . . 7 15

Beispiel 4.1 Berechnet man eine DFT für n = 1024, was in der Signalverar-beitung durchaus realistisch ist, so wären mit einer Matrix Multiplikationca. 1 Million Multiplikation erforderlich, mit dem oben beschriebenen Ver-fahren jedoch nur ca. 5 000 Multiplikationen. Man hat also einen Faktor200 an Rechenaufwand gespart.

5 EIGENSCHAFTEN DER DFT 49

5 Eigenschaften der DFTIm Folgenden sei ~f ∈ Rn ein Vektor, dessen n Komponenten aus den Abtast-werten eines Signals bestehen. Die Komponenten von ~f werden von 0 bis n− 1indiziert. Die DFT von ~f wird mit ~F bezeichnet, d.h.

~F = DFT(~f).

Mit der Definition der DFT auf Seite 33 gilt

~F = 1nB∗ ~f

bzw.

Fk = 1n

n−1∑`=0

fè−2πjk`/n.

Wie von der Fourier Transformation her bekannt, wird hierfür auch die Notation

~f c s ~F

bzw.

f` c s Fk

verwendet.

Modulo Funktion Für jede ganze Zahl ` ∈ Z ist `modn, gelesen ` modulon, definiert durch

`modn = `+ qn

wobei q ∈ Z so gewählt ist, dass

0 ≤ `+ qn < n.

Hierzu ein paar Beispiele:

7 mod 3 = 19 mod 3 = 0−5 mod 3 = 1−1 mod 3 = 2

0 mod 3 = 0.

Für positive ` ist `modn einfach der Rest der ganzzahligen Division von ` durchn. Allgemein gilt für jedes n ∈ N

`modn = ` für ` = 0, 1, . . . , n− 1nmodn = 0−1 modn = n− 1.


5.1 Zyklische VerschiebungSei ~g ∈ Rn der Vektor, der durch zyklische Verschiebung der Komponenten von~f ∈ Rn um eine Stelle entsteht, d.h.

g` = f`−1 für ` = 1, 2, . . . , n− 1

und

g0 = fn−1.

Mit der Modulo Funktion lässt sich dies wie folgt in einer Formel schreiben:

g` = f(`−1) modn, ` = 0, 1, . . . , n− 1.

Wie in Bild 5.1 dargestellt, kann man sich die zyklische Verschiebung so vor-stellen, dass alle Abtastwerte von f um eine Position nach rechts wandern undder letzte Abtastwert bei Position Null eingefügt wird.

0 n− 1

gℓ = f(ℓ−1)modn

ℓ

0 n− 1

fℓ

ℓ

Abbildung 5.1: Zyklische Verschiebung

Theorem 5.1 (Zyklische Verschiebung)

f(`−1) modn c s e−2πjk/nFk

Dies lässt sich wie folgt herleiten:


f(`−1) modn c s 1n

n−1∑`=0

f(`−1) modn e−2πjk`/n

= e−2πjk/n 1n

n−1∑`=0

f(`−1) modn e−2πjk(`−1)/n

= e−2πjk/n 1n

n−2∑`=−1

f`modn e−2πjk`/n

= e−2πjk/n 1n

(n−2∑`=0

f` e−2πjk`/n + fn−1e

−2πjk(−1)/n

)

= e−2πjk/n 1n

(n−2∑`=0

f` e−2πjk`/n + fn−1e

−2πjk(n−1)/n

)

= e−2πjk/n 1n

n−1∑`=0

f` e−2πjk`/n

= e−2πjk/nFk

Hieraus folgt allgemein für eine beliebige zyklische Verschiebung um m Stel-len

f(`−m) modn c s e−2πjkm/nFk


5.2 Zyklische Faltung

Definition 5.2 (Zyklische Faltung)Die zyklische Faltung ⊗ ∈ Rn × Rn → Rn ist definiert durch

(~f ⊗ ~h)` =n−1∑m=0

hmf(`−m) modn.

Für die zyklische Faltung gelten die gleichen Rechengesetze wie für die kon-tinuierliche Faltung, also z.B.

~f ⊗ ~h = ~h⊗ ~f

(c~f)⊗ ~h = c(~f ⊗ ~h)(~f + ~g)⊗ ~h = (~f ⊗ ~h) + (~g ⊗ ~h).

Von besonderer Wichtigkeit ist für uns jedoch der Zusammenhang zwischender zyklischen Faltung und der DFT.

Theorem 5.3 (Zyklische Faltung)Die zyklische Faltung entspricht im Frequenzbereich der Multiplikation,d.h.

1n

(~f ⊗ ~h)` c s FkHk.

Theorem 5.3 lässt sich vektoriell schreiben als1n

(~f ⊗ ~h) c s ~F ~H

wobei die Multiplikation auf der rechten Seite komponentenweise durchzuführenist.

Aufwandsberechnung. Das o.g. Theorem ist wichtig, weil damit der Re-chenaufwand für die zyklische Faltung reduziert werden kann.

• Die Berechnung von

(~f ⊗ ~h)` =n−1∑m=0

hmf(`−m) modn

kostet n Multiplikationen. Die Berechnung von

~f ⊗ ~h

kostet folglich n2 Multiplikationen.

• Man kann die zyklische Faltung viel schneller via FFT durchführen. Hierzumultipliziert man beide Seiten mit n2 und erhält

n(~f ⊗ ~h) c s (n~F )(n ~H).


Die Berechung von n~F und n ~H kostet mit der FFT insgesamt

nld(n)

Multiplikationen. Die komponentenweise Multiplikation ~G = ~F ~H kostetn Multiplikationen. Damit hat man

n(~f ⊗ ~h) c s n2 ~G

bzw.

1n

(~f ⊗ ~h) c s ~G.

Die inverse Fourier Transformation von ~G kostet nochmal

12nld(n)

Multiplikationen. Zum Schluss muss man noch jede Komponente mit nMultiplizieren um auf ~f ⊗~h zu kommen, was nochmal n Multiplikationenkostet. Der Gesamtaufwand ist somit

nld(n) + n+ 12nld(n) + n = n

(32 ld(n) + 2

).

Für n = 256 würde die Faltung im Zeitbereich 65 536 Multiplikationen kosten,der Weg über den Frequenzbereich mit FFT jedoch nur 3 584.


Und nun noch die Herleitung von Theorem 5.3:

FkHk = Fk1n

n−1∑m=0

hm e−2πjkm/n

︸︷︷︸Hk

= 1n

n−1∑m=0

Fkhm e−2πjkm/n

= 1n

n−1∑m=0

1n

n−1∑`=0

f` e−2πjk`/n

︸︷︷︸Fk

hm e−2πjkm/n

= 1n2

n−1∑m=0

n−1∑`=0

hmf` e−2πjk(`+m)/n

= 1n2

n−1∑m=0

m+n−1∑`=m

hmf`−m e−2πjk`/n

= 1n2

n−1∑m=0

(n−1∑`=m

hmf`−m e−2πjk`/n +

m+n−1∑`=n

hmf`−m e−2πjk`/n

)

= 1n2

n−1∑m=0

(n−1∑`=m

hmf`−m e−2πjk`/n +

m−1∑`=0

hmf(`−m) modn e−2πjk(`+n)/n

)

= 1n2

n−1∑m=0

n−1∑`=0

hmf(`−m) modn e−2πjk`/n

= 1n2

n−1∑`=0

n−1∑m=0

hmf(`−m) modn︸︷︷︸(~f⊗~h)`

e−2πjk`/n

= 1n2

n−1∑`=0

(~f ⊗ ~h)` e−2πjk`/n

s c 1n

(~f ⊗ ~h)`.


Beispiel 5.4 Analog zum kontinuierlichen Fall kann man auch im diskretenFall einen Einheitsimpuls definieren durch

~δ ∈ Rn, δ` ={

1 falls ` = 00 sonst.

Wie erwartet gilt

~f = ~f ⊗ ~δ.

Aus der Definition der zyklischen Faltung

(~f ⊗ ~δ)` =n−1∑m=0

δmf(`−m) modn.

In dieser Summe ist jeder Summand außer der für m = 0 Null. Folglich ist

n−1∑m=0

δmh(`−m) modn = f`.

Das gleiche Resultat erhält man auch unter Verwendung der DFT. Fürdie DFT des Einheitsimpulses gilt

δ` c s 1n

n−1∑`=0

δè−2πjk`/n

= 1ne−2πjk0/n

= 1/n.

Mit Theorem 5.3 gilt folglich

1n

(~f ⊗ ~δ)` c s Fk1n

und damit

(~f ⊗ ~δ)` c s Fk.

Da auch

f` c s Fk

folgt

(~f ⊗ ~δ)` = f`.


Beispiel 5.5 Sei h` der um eins verschobene Einheitsimpuls, d.h.

~h ∈ Rn, h` ={

1 falls ` = 10 sonst.

Für die zyklische Faltung von ~f und ~h gilt nun

(~f ⊗ ~h)` =n−1∑m=0

hmf(`−m) modn.

In dieser Summe ist jeder Summand außer dem für m = 1 Null. Daher gilt

n−1∑m=0

hmf(`−m) modn = f(`−1) modn.

Folglich ist

(~f ⊗ ~h)` = f(`−1) modn,

d.h. der Effekt der zyklische Faltung von ~f mit ~h ist eine zyklische Ver-schiebung von f um eine Stelle.Zum gleichen Ergebnis kommt man auch unter Verwendung von Theorem5.3. Die DFT von ~h ist

Hk = 1n

n−1∑`=0

hè−2πjk`/n

= 1ne−2πjk/n.

Folglich gilt

1n

(~f ⊗ ~h)` c s Fk1ne−2πjk/n

bzw.

(~f ⊗ ~h)` c s e−2πjk/nFk.

Nach Theorem 5.1 gilt aber auch

f(`−1) modn c s e−2πjk/nFk

und damit folgt

(~f ⊗ ~h)` = f(`−1) modn.

6 SCHNELLE FALTUNG MIT FFT 57

6 Schnelle Faltung mit FFTNachdem gezeigt wurde, dass man die zyklische Faltung sehr effizient mit Hilfeder FFT berechnen kann, geht es nun darum die lineare Faltung durch zykli-sche Faltungen zu realisieren. Damit kann auch die für die Signalverarbeitungwichtige lineare Faltung sehr effizient durch FFT’s berechnet werden.

Die diskrete Faltung zweier Signale f und h ist definiert durch

(f ∗ h)` =∞∑

m=−∞hmf`−m.

In vielen Anwendungen ist h die Impulsantwort eines FIR Filters und damit nurin einem Intervall ` = 0, . . . ,H − 1 ungleich Null, d.h.

h` = 0 für ` 6∈ [0, H − 1].

Damit gilt

g` = (f ∗ h)` =H−1∑m=0

hmf`−m.

Die Berechnung von g` kann also durch ein Skalarprodukt zweier Vektoren mitjeweils H Komponenten realisiert werden.

Faltung eines Signalblocks. Zunächst wird vereinfachend angenommen,dass auch das zu filternde Signal f` nur in einem Intervall ` = 0, . . . , F − 1mit F ≥ H ungleich Null ist, d.h.

f` = 0 für ` 6∈ [0, F − 1].

In Bild 6.1 ist dies dargestellt für H = 4 und F = 9. In den gestrichelt darge-stellten Bereichen sind die Abtastwerte Null.

Seien ~h, ~f ∈ RF Vektoren, deren Komponenten gleich den ersten F Ab-tastwerten von h bzw. f sind. Die lineare Faltung f ∗h ist natürlich nicht gleichder zyklischen Faltung ~f ⊗ ~h, das Ergebnis ist aber für bestimmte Werte von `gleich. In Bild 6.2 ist die zyklische Faltung für H = 4 und F = 9 dargestellt.Das Ergebnis der linearen und der zyklischen Faltung stimmt für ` = 3, . . . , 8überein. Allgemein gilt

(~f ⊗ ~h)` = (f ∗ h)` für ` = H − 1, . . . , F − 1.

Dies sollte durch einen Vergleich von Bild 6.1 und Bild 6.2 ersichtlich sein undkann wie folgt nachgerechnet werden. Sei also H − 1 ≤ ` ≤ F − 1. Dann gilt

(~f ⊗ ~h)` =F−1∑m=0

hmf(`−m) modF

=H−1∑m=0

hmf(`−m) modF da hm = 0 für m ≥ H

=H−1∑m=0

hmf`−m da ` ≥ H − 1

= (f ∗ h)`.


m

fℓ

hℓ

gℓ

H − 1

F − 1

F +H − 2

0

m

fℓ

hℓ

gℓ

H − 1

F − 1

m

Fall ℓ = 5

Fall ℓ = F +H − 2

0

m

m

fℓ

hℓ

gℓ

H − 1

F − 1

F +H − 2

ℓ

ℓ

ℓ

ℓ

Fall ℓ = 1

ℓ

ℓ

m

Abbildung 6.1: Diskrete Faltung g` = (f ∗ h)` für H = 4 und F = 9


~f

~h

~g

~f

~h

~g

~f

~h

~g

m

H − 1

F − 1

0

m

H − 1

F − 1

Fall ℓ = 5

0

m

m

H − 1

F − 1ℓ

ℓ

m

ℓ

ℓ

0

Fall ℓ = 1

m

ℓ

ℓ

Fall ℓ = 3

m

zyklisch6= linear

Abbildung 6.2: Zyklische Faltung ~g = ~f ⊗ ~h für H = 4 und F = 9.


Faltung eines unbegrenzten Signals. Wenn f ein zeitlich unbegrenztesoder sehr langes Signal ist, greift man sukzessive einen Block der Länge F ausf heraus und faltet zyklisch mit h. Die ersten H − 1 Werte des Ergebnisses sindwie oben gesehen unbrauchbar, die übrigen F −H + 1 Werte sind gleich wie beieiner linearen Faltung. Wenn sich die aus f herausgegriffenen Blöcke also immerum H − 1 Werte überlappen, kann man das gesamte Signal f ∗ h berechnen.Bei jeder zyklischen Faltung werden F − H + 1 Werte des Signals g = f ∗ hberechnet, siehe Bild 6.3.

Die exakte Berechnung der Indizes ist etwas mühsam, muss aber für dieImplementierung in einem Computerprogramm durchgeführt werden: Der ersteBlock enthält die Abtastwerte

f−H+1 bis fF−H

und liefert nach zyklischer Faltung mit h und Elimination der ersten H − 1Komponenten

g0 bis gF−H .

In jeder weiteren Operation verschieben sich alle Indizes um um

∆ = F −H + 1.

Der i-te Block enthält für i = 0, 1, 2, . . . somit die F Abtastwerte

f−H+1+i∆ bis fF−H+i∆.

Nach der zyklischen Faltung mit h werden vom Ergebnis die ersten H−1 Werteverworfen. Die übrigen F −H + 1 Koeffizienten sind

gi∆ bis gF−H+i∆.


0

hℓ

falsch

f−3 . . . f5

g0 . . . g5

hℓ

falsch

f9 . . . f17

g12 . . . g17

hℓ

falsch

f3 . . . f11

g6 . . . g11

fℓ

Abbildung 6.3: Faltung g = f ∗ h für H = 4 und F = 9.

A ANHANG 62

A AnhangA.1 Die wichtigsten Fourier Transformationspaare

ejω̂t c s 2πδ(ω − ω̂)cos(ω̂t) c s π(δ(ω − ω̂) + δ(ω + ω̂))sin(ω̂t) c s −jπ(δ(ω − ω̂)− δ(ω + ω̂))

δ(t) c s 11 c s 2πδ(ω){

1 falls −T < t < T0 sonst

c s 2T si(ωT ){1 falls 0 ≤ t < T0 sonst

c s 1jω

(1− e−jωT )

p(t) =∞∑

n=−∞δ(t− nTs) c s ωs

∞∑n=−∞

δ(ω − kωs), ωs = 2πTs

A ANHANG 63

A.2 Rechengesetze für die Fourier TransformationSymmetrie

f(t) reell, gerade c s F (ω) reell, geradef(t) reell, ungerade c s F (ω) imaginär, ungerade

Linearität

a1f1(t) + a2f2(t) c s a1F1(ω) + a2F2(ω)

Zeitverschiebung

f(t− t̂) c s e−jωt̂F (ω)

Frequenzverschiebung

f(t)ejω̂t c s F (ω − ω̂)

Frequenzmodulation

f(t) cos(ω̂t) c s 12(F (ω − ω̂) + F (ω + ω̂))

Zeitumkehr

f(−t) c s F (−ω) = F (ω)

Zeitdehnung

f(at) c s 1|a|F(ωa

)Ableitung im Zeitbereich

f ′(t) c s (jω)F (ω)f ′′(t) c s (jω)2F (ω)

Integration im Zeitbereich∫ t

−∞f(u)du c s 1

jωF (ω)

Ableitung im Frequenzbereich

(−jt)f(t) c s F ′(ω)(−jt)2f(t) c s F ′′(ω)

Faltung im Zeitbereich

(f ∗ g)(t) c s F (ω)G(ω)

Faltung im Frequenzbereich

f(t)g(t) c s 12π (F ∗G)(ω)

Literatur[1] McClellan, J. H. ; Schafer, R. W. ; Yoder, M. A.: Signal Processing

First. Pearson, 2003

[2] Oppenheim, A. V. ; Schafer, R. W.: Discrete-Time Signal Processing.Prentice Hall, 1989

64

Documents

Signalverarbeitung 1mitarbeiter.hs-heilbronn.de/~vstahl/signalverarbeitung1/skript.pdf · Signalverarbeitung 1 Skript zur Vorlesung an der Hochschule Heilbronn 1 (Stand: 24. Juni