Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2014 / Codierungstheorie / Material / Skript Teil 5


Inhaltsbereich

Skript Teil 5

Plain Text icon skript5.txt — Plain Text, 8 KB (8660 bytes)

Dateiinhalt

Anmerkung: "Folien" bezieht sich auf die auf der Homepage verlinkten Folien aus "Effiziente Algorithmen". 


Fourierreihen, DFT und FFT
--------------------------

Fourierreihen: 
------------- 

Es sei eine stueckweise stetig differenzierbare Funktion f : R -> R
mit Periode 1 gegeben, also f(t+1)=f(t), aufgefasst als periodisches
Signal, z.B. ein Tonsignal. An Unstetigkeitsstellen sei f(x) jeweils 
das arithmetische Mittel von f(x+0) und f(x-0). 

Offensichtlich genuegt es, f im Bereich [0..1] zu kennen. 

Wir wollen f als Ueberlagerung von Sinus- und Kosinusfunktionen
darstellen, also

f(t) = sum_{k=0}^oo alpha_k * cos(2*pi*k*t) + beta_k * sin(2*pi*k*t) 

Beachte: cos(2*pi*t) hat Periode 1 und Frequenz 1. cos(2*pi*k*t) hat
Periode 1/k und entsprechend Frequenz k. Analoges gilt fuer die
Sinusfunktionen.

In der obigen Darstellung wird also versucht, eine periodische
Funktion einer bestimmten Grundfrequenz, hier der Einfachheit halber
1, als Ueberlagerungen von Sinus- und Kosinusschwingungen mit
ganzzahligen Vielfachen dieser Grundfrequenz darzustellen.


Fouriers Motivation: Differentialgleichung "Schwingende Saite" 
--------------------------------------------------------------
Der urspruengliche Zweck dieser Darstellung war die Loesung der
partiellen DGL "Schwingende Saite": Ist die Auslenkung einer Saite der
Laenge 1 zur Zeit t=0 bekannt, so gilt fuer die Auslenkung der Saite
fuer t>=0 unter vereinfachenden Bedingungen: u(0,t)=u(1,t)=0, c^2 *
(d_x)^2 u(x,t) = (d_t)^2 u(x,t). Hier ist d_x die zweite Ableitung
nach x, ebenso fuer t. Ist die Anfangsauslenkung eine sinusfoermige
Funktion, so kann man die Loesung explizit angeben. Ist die
Anfangsauslenkung Ueberlagerung von Sinusfunktionen, so ist die
Loesung die entsprechende Ueberlagerung der Sinusloesungen.


Orthogonalitaet:
----------------

Fuer k,l:N\{0} gelten die folgenden Orthogonalitaetsbeziehungen: 

int_{t=0}^1 sin(2*pi*k*t)*cos(2*pi*l*t) dt = 0 
int_{t=0}^1 cos(2*pi*k*t)*cos(2*pi*l*t) dt = if k=l then 1/2 else 0 
int_{t=0}^1 sin(2*pi*k*t)*sin(2*pi*l*t) dt = if k=l then 1/2 else 0 
                                             
Wenn es also eine Darstellung wie oben gibt (und man kann zeigen, dass
das der Fall ist), so muss gelten:

alpha_0 = int_{t=0}^1 f(t) dt 
alpha_k = 2*int_{t=0}^1 f(t)*cos(2*pi*l*t) dt 
beta_k = 2*int_{t=0}^1 f(t)*sin(2*pi*l*t) dt 

Man nennt die alpha_k und beta_k die Fourierkoeffizienten von f und
die obige Darstellung die Fourierreihe von f.

Beispiel: Ist f auf [0,1] durch f(t)=if x<1/2 then 1 else if x=1/2
then 0 else -1 gegeben (Rechteckschwingung), so ist alpha_k = 0 und
beta_k = 4/(pi*k), falls k ungerade, 0 sonst.

Die beta_k sind genau dann 0, wenn f zusaetzlich die Gleichung
f(x)=f(1-x) erfuellt (symmetrisch mit Achse x=1/2), man hat dann eine
reine Kosinusreihe. Die alpha_k sind genau dann 0, wenn f zusaetzlich
die Gleichung f(x)=-f(1-x) erfuellt (punktsymmetrisch um (1/2,0)), man
hat dann eine reine Sinusreihe.

Die alpha_k und beta_k bilden das Spektrum der Funktion f. Aus den
Koeffizienten alpha_k und beta_k gehen Amplitude und Phasenlage der
k-ten Oberschwingung hervor.

NB: sin(t+p) = cos(p)*sin(t) + sin(p)*cos(t) Also: a*sin(t) + b*cos(t)
= c*sin(t+p), wobei c=sqrt(a2+b2) und p=atan2(b,a)


Wdh Komplexe Zahlen
-------------------

Folien 6 und 7 


Exponentielle Fourierreihe
--------------------------

Anstelle der Sinus- und Kosinusreihe kann man stattdessen f auch als
Ueberlagerung komplexer Exponentialfunktionen schreiben, also in der
Form

f(t) = sum_{k=-oo}^oo gamma_k * exp(2*pi*i*k*t)

Wegen exp(i*z) = cos(z) + i*sin(z) und cos(z) = 1/2(exp(i*z)+exp(-iz))
und sin(z) = 1/2(exp(i*z)-exp(-iz)) lassen sich die gamma_k aus den
alpha_k und beta_k berechnen und umgekehrt. Es gilt:

alpha_k = 1/2*(gamma_k + gamma_(-k))
beta_k = 1/(2i)*(gamma_k - gamma_(-k))

Auch die Exponentialfunktion erfuellt eine Orthogonalitaetsbeziehung: es gilt 

fuer k,l:Z 

int_{x=0}^1 exp(2*pi*i*k*x)*exp(-2*pi*i*l*x) dx = if k=l then 1 else 0 

Es folgt also wie vorher

gamma_k = int_{t=0}^1 f(t) * exp(-2*i*pi*k*t) dt 

Man kann mit den Exponentialfunktionen leichter rechnen, als mit Sinus
und Kosinus, daher wird haeufig die komplexe Form vorgezogen. Beide
Formen funktionieren im uebrigen auch fuer komplexwertige Funktionen
f.

Die Fourierkoeffizienten (alpha_k, beta_k), bzw. gamma_k, bilden eine
alternative Repraesentation der Funktionen f. Viele Eigenschaften und
Operationen auf solchen Funktionen koennen auf der Ebene der
Fourierkoeffizienten leichter verstanden und berechnet werden. 

Zum Beispiel entspricht ein Tiefpassfilter einer Bevorzugung der
tiefen Frequenzen; die Fourierkoeffizienten gamma_k einer gegebenen
Funktion werden dann zu gamma'_k = r(k)*gamma_k abgeaendert, wobei
r(k) mit wachsendem |k| kleiner wird, z.B. r(k) = 1/(k^2+1). Analog
fuer Hoch- und Bandpassfilter.

Ausserdem gilt, dass die wichtige Operation der Faltung im
Frequenzbereich, d.h. auf der Ebene der Fourierkoeffizienten, der
einfachen Multiplikation entspricht:



Faltung und Impulsantwort
-------------------------

Seien f, g, zwei Funktionen mit Periode 1. Die Faltung von f und g ist
gegeben durch

(f#g)(t) = int_{y=0}^1 f(y)*g(t-y) dy

Sind gamma_k und delta_k die Fourierkoeffizienten von f und g, so sind
die Fourierkoeffizienten theta_k von f#g durch die Formel theta_k =
gamma_k*delta_k gegeben.

Begruendung: 

Es ist ja (f#g)(t) = sum_l sum_k gamma_l*delta_k 
int_{y=0}^1 exp(2*pi*i*l*y)* exp(2*pi*i*k*(t-y)) dy = 
 sum_l sum_k gamma_l*delta_k*exp(2*pi*i*k*t) *
int_{y=0}^1  exp(2*pi*i*(l-k)*y) dy = 
 sum_l sum_k gamma_l*delta_k*exp(2*pi*i*k*t) * (if l=k then 0 else 1) = 
 sum_k gamma_k*delta_k*exp(2*pi*i*k*t)

Oftmals werden Signale durch eine lineare Operation
weiterverarbeitet. Aus einer Funktion f wird so eine neue Funktion
F(f), wobei gilt F(lambda*f+mu*g)=lambda*F(f)+mu*F(g). Die bereits
angesprochenen Filter bilden Beispiele solcher linearer Operationen.

Man kann unter recht weitgefassten Bedingungen solch eine Operation F
immer in der Form

F(f) = f#g

schreiben fuer eine bestimmte Funktion g, die nur von F abhaengt. Man
nennt g die *Impulsantwort* von F, da man g als Ausgabe von F erhaelt,
wenn man als Eingabe einen sehr scharfen Nadelimpuls bei x=0
anbietet. Sei intuitiv delta(x) so ein Nadelimpuls, also delta(x)=0,
ausser wenn x=0 und delta(0) = "oo", aber so, dass int_x=0^1 delta(x)
dx = 1. Dann kann man intuitiv schreiben

f(x) = int_{y=0}^1 f(y) * delta(x-y) dy 

also f als Ueberlagerung von solchen entsprechend gewichteten
Nadelimpulsen schreiben. Es ist dann wegen der Linearitaet von F

F(f)(x) = int_{y=0}^1 f(y) * F(delta)(x-y) dy = (f#g)(x)

wobei g=F(delta). 

Kennt man also die Fourierkoeffizienten der Impulsantwort F(delta), so
koennen die Fourierkoeffizienten von F(f) durch Multiplikation der
Fourierkoeffizienten von f mit denen der Impulsantwort erhalten
werden. Wichtiger noch kann die Anwendung von F rueckgaengig gemacht
werden, indem man entsprechend durch die Fourierkoeffizienten der
Impulsantwort teilt. 


Diskrete Fouriertransformation (DFT)
------------------------------------

Oft liegt das Signal f nicht als echte Funktion sondern in Form von N
Abtastwerten x_j = f(j * h) fuer h = 1/N vor. Man kann dann
naeherungsweise die Fourierkoeffizienten berechnen, indem man das
Integral

gamma_k = int_{x=0}^T f(x) * exp(-2*i*pi*k/T*x) dx 

durch eine Summe ersetzt

gamma_k =~= sum_{j=0}^{n-1} x_j * exp(-2*i*pi*k*j/n) * 1/n 

wobei x_j = f(j/n)

Fuer einen beliebigen Vektor komplexer Zahlen a_0,..,a_{n-1} definiert
man die diskrete Fouriertransformation (DFT) als komplexen Vektor
y_0,..,y_{n-1} wobei

y_k = sum_{j=0}^{n-1} x_j * exp(2*i*pi*k*j/n)

NB: das Minuszeichen im Exponenten faellt weg. 

Wegen exp(-2 i pi k j/n) = exp(2 i pi k (n-j)/n hat man aber fuer k=0..n-1

gamma_k =~= 1/n * y_k 

fuer die Setzung a_k = f((n-j)/n.

Fuer k<0 und k>=n, koennen die gamma_k aus den vorhandenen Werten
berechnet werden. Sie enthalten keine neue Information.

Neben der Tatsache, dass sie zur naeherungsweisen Berechnung der
Fourierkoeffizienten verwendet werden kann, bildet die DFT eine
grundlegende Rechenoperation mit einer Reihe von Anwendungen in
Signalverarbeitung, Codierungstheorie, Computeralgebra,
Quantencomputer, etc.

Es sei w_n die n-te Einheitswurzel (Folie 8), d.h. w_n =
exp(2*pi*i/n). Dann ergibt sich fuer die DFT:

y_k = sum_{j=0}^{n-1}a_j * w_n^{jk}

Man kann die DFT daher als Wertetabelle des Polynoms

A(x) = sum_{j=0}^{n-1}a_j * x^j

ansehen fuer die Stuetzstellen w_n^0 , w_n^1, ... w_n^{n-1} (Folie 9).

Rechenregeln fuer die DFT, Zusammenhang mit Polynomen, schnelle
Fouriertransformation (FFT): Folien 10-28.


Artikelaktionen


Funktionsleiste