Jörg Wollnack

Allgemeine Fourier-Reihen, Orthogonale und Unitäre

Transformationen

0 .40 .2

00 .2

0 .4

0 .4

0 .2

0

0 .2

0 .4

1

0 .5

0

0 .5

( , )= (1 ,0 )m n

0 .40 .2

00 .2

0 .4

0 .4

0 .2

0

0 .2

0 .4

0 .5

0

0 .5

1

x

yz

( , )= (1 ,1 )m n

0 .40 .2

00 .2

0 .4

0 .4

0 .2

0

0 .2

0 .4

0

0 .5

1

( , )= (2 ,2 )m n

0 .40 .2

00 .2

0 .4

0 .4

0 .2

0

0 .2

0 .4

1

0 .5

0

0 .5

( , )= (2 ,1 )m n

Copyright 1980 Jörg Wollnackzweite, wesentlich überarbeite Fassung 2001

- I -

Dr. Jörg Wollnack

Inhaltsverzeichnis(Im Aufbau befindliches Manuskript)

1 Allgemeine Fourier-Reihen, Orthogonale und Unitäre Transformationen ......... 1

1.1 Approximationstheorie............................................................................................ 1

1.2 Entwicklung nach orthogonalen und orthonormalen Funktionen ........................... 2

1.3 Vollständiges System orthonormaler Funktionen ................................................... 3

1.4 Beispiele vollständiger orthonormaler Funktionensysteme .................................... 7

1.4.1 Trigonometrische Funktionen in komplexer Darstellung ................................ 7

1.4.2 Walsh-Funktionen ............................................................................................ 8

1.4.3 Laguerresche Polynome ................................................................................... 8

1.4.4 Spaltfunktionen ................................................................................................ 8

1.4.5 Weitere Systeme............................................................................................... 9

1.5 Komplexe Fourier-Reihe......................................................................................... 9

1.5.1 Konvergenzverhalten der Fourier-Reihe, Periodische Fortsetzung undWeierstraßscher Approximationssatz............................................................. 12

1.5.2 Faltung und Kreuzkorrelation periodischer Funktionen ................................ 17

1.5.3 Vollständigkeit der komplexen Fourier-Reihe............................................... 19

1.5.4 Finite Darstellungen und Diskretisierung in Technik und Theorie................ 19

1.5.5 Zur Idee der diskreten Fourier-Transformation ............................................. 20

2 Diskrete Ansätze und Unitäre Transformationen................................................. 21

2.1 Reeller diskreter Ansatz (Motivation)................................................................... 21

2.2 Unitäre und orthonormale Transformationen........................................................ 23

2.3 Diskrete Fourier-Transformation .......................................................................... 26

2.3.1 Diskrete Fourier-Transformation und Unitaritätsrelation .............................. 26

2.3.2 Diskrete Fourier-Teilsumme .......................................................................... 27

2.3.3 Diskrete Fourier-Transformation in reeller Darstellung ................................ 27

2.3.4 Diskrete zyklische Faltung und Korrelationen............................................... 29

2.3.5 Diskrete Parsevalsche Gleichung ................................................................... 30

2.3.6 Fast-Fourier-Transform.................................................................................. 31

2.3.6.1 Die Idee zur schnelle Fourier-Transformation........................................ 31

2.3.6.2 Vorüberlegungen zum Cooley Tukey Algorithmus ................................ 33

2.3.6.3 Cooley Tukey C++-Algorithmus ............................................................ 36

- II -

Dr. Jörg Wollnack

3 Höherdimensionale Räume (Schwerpunkt auf 2D) .................................................. 1

3.1 Die zweidimensionale allgemeine komplexe Fourier-Reihe................................... 1

3.1.1 Separable Kerne ............................................................................................... 4

3.1.2 Zweidimensionale trigonometrische Fourier-Transformation inkomplexer Darstellung ..................................................................................... 5

3.1.2.1 Zyklische Faltung und Korrelation ........................................................... 7

3.1.2.2 Differentiation und Integration ................................................................. 7

3.2 Die Mehrdimensionale allgemeine komplexe Fourier-Reihe ................................. 7

3.3 Unitäre und orthonormale Transformationen.......................................................... 9

3.3.1 Separable Kerne ............................................................................................. 11

3.3.2 Diskrete trigonometrischen Fourier-Transformation in komplexerDarstellung ..................................................................................................... 11

3.3.2.1 Zyklische Faltung und Korrelation ......................................................... 11

3.3.2.2 Differentiation und Integration ............................................................... 11

3.3.3 Schnelle Transformationen ............................................................................ 11

3.3.3.1 Fast-Fourier-Transform........................................................................... 11

3.3.3.2 Fast Walsh-Transform............................................................................. 11

3.4 Die vektorielle mehrdimensionale unitäre Fourier-Reihe..................................... 11

4 Formelsammlung

5 Korrespondenzen

6 Anhang

7 Literaturverzeichnis

- III -

Dr. Jörg Wollnack

Vorwort

Zu Beginn des 19. Jahrhunderts hatte der französische Mathematiker J. B. J. Fourier1 bei demStudium der Wärmeleitungsphänomene die bemerkenswerte Entdeckung gemacht, daß gewis-se trigonometrische Reihen, die später nach ihm benannt wurden, zur Lösung der Wärme-leitungsgleichungen genutzt werden können. Seit dieser Zeit wurden die Fourier-Reihen undVerallgemeinerungen auf die Fourier-Integrale und orthogonalen Reihen bedeutsame Werk-zeuge von Naturwissenschaftlern, Ingenieuren und Mathematikern. Aufbauend auf diesenGrundlagen entwickelten sich weitere Integral-Transformationen, wie z.B. die Laplace2- undHilbert3-Transformation. Auch diese stellen zusammen mit der Fourier-Transformation einleistungsfähiges Werkzeug zur Untersuchung von linearen, zeitinvarianten Differential-gleichungen und Systemen dar.

Mit der Systemtheorie, bei der die Gesetze von der speziellen Natur der Systeme gelöst wer-den, steht ein mathematisches Werkzeug zur Verfügung, das die Behandlung verschiedenerSysteme der Nachrichten- oder Energietechnik, des Maschinenbaus, der Verfahrenstechniksowie der Ökonomie ermöglicht. Die hier diskutierten Methoden sind ein Repertoire derSystemtheorie.

Häufig wird die Laplace-, Fourier- und Hilbert-Transformation in den Naturwissenschaftenper Definition eingeführt, so daß der Zusammenhang zwischen den Transformationen nichtunmittelbar sichtbar wird. Um die Zusammenhänge deutlich zu machen, wird ausgehend vonden Fourier-Reihen periodischer Funktionen das Fourier-Integral durch einen Grenzübergangin heuristischer Weise motiviert. Typische Konvergenzproblemen der Fourier-Transformationlassen sich mit einem Dämpfungsterm entschärfen. Dieser Ansatz führt dann unmittelbar zumLaplace-Integral. Die Verallgemeinerung der Integraltransformation führt zur FredholmschenIntegralgleichung erster Art. Mit Hilfe der Fredholmschen Integralgleichung werden unterVerwendung einer speziellen Kernfunktion einige Gesetzmäßigkeiten der Integraltrans-formationen zusammengetragen. Die Bedeutung der Integraltransformation für die derDifferential- und Integralrechnung kann bereits auf dieser Stufe illustriert werden.

Anschließend werden spezielle Gesetzmäßigkeiten der Laplace- und Fourier-Transformationdiskutiert. Diese führen zur Parsevalschen Gleichung und Hilbert-Transformation. DieParsevalsche Gleichung ermöglicht eine Energiebeschreibung reeller Funktionen. DieHilbert-Transformation ordnet wechselseitig Real- und Imaginärteil kausaler4 Zeitfunktionenüber eine Integraltransformation einander eindeutig zu. Eine Systemklassifizierung führt zueiner notwendigen und hinreichenden Bedingung für die Anwendbarkeit des Faltungssatzes.

1 Fourier [Jean-Baptiste] Joseph Baron de (ab 1808), *�Auxerre 21.3.1768, †�Paris 16.5.1830, frz. Mathematiker undPhysiker. Die von F. im Rahmen seiner Arbeiten über die Theorie der Wärmeausbreitung eingeführte Methode der Ent-wicklung von Funktionen in Fourier-Reihen (Reihen zur Darstellung einer period. Funktion) erwies sich für die theoret.Physik als außerordentlich fruchtbar.2 Laplace, Pierre Simon Marquis de (seit 1804), *�Beaumont-en-Auge bei Lisieux 28. 3.1749, †�Paris 5.3.1827, frz.Mathematiker und Astronom. Arbeitete v.�a. über Kosmogonie, Potentialtheorie, Schwingungs- und Wärmelehre und Wahr-scheinlichkeitsrechnung.3 Hílbert, David, *�Königsberg 23.1.1862, †�Göttingen 14.2.1943, dt. Mathematiker. 1892–95 Prof. in Königsberg, dann inGöttingen. Grundlegende Arbeiten insbes. zur Invariantentheorie, zur Theorie der algebraischen Zahlkörper, zur Theorie derIntegralgleichungen und zur mathemat. Physik.4 kausal [lat.]: ursächlich, das Verhältnis Ursache-Wirkung betreffend, dem Kausalgesetz entsprechend.

- IV -

Dr. Jörg Wollnack

Die Prinzipien der inversen Integraltransformationen bauen auf einem kleinen Exkurs durchdie komplexe Funktionentheorie auf und führen zu dem Residuensatz. Auf die Methode derPartialbruchzerlegung wird dabei im Zusammenhang mit der Laurent-Reihe eingegangen.

Der Leser sollte Kenntnisse zur Differential- und Integralrechnung besitzen und die kom-plexen Zahl sollten ihm bekannt sein. Dabei ist die Kenntnis der komplexen Differentiationund Integration keine notwendige Voraussetzung für das Verständnis. Weiterhin sollte demLeser die Approximation periodischer Funktionen mittels Fourier-Reihen geläufig sein, davon hier aus das Fourier-Integral anschaulich entwickelt werden wird. In einigen Beispielenwerden in der Darstellung die Methoden der Matrizenrechnung genutzt. Diese können aberauch klassisch, durch Lösung von linearen Gleichungen mit mehreren Unbekannten, bearbei-tet werden. Die am Ende einzelner Abschnitte gestellten Übungsaufgaben können in derRegel mit dem Wissen aus den vorherigen Kapiteln bearbeitet werden.

- 1 - Dr. Jörg Wollnack

1 Allgemeine Fourier-Reihen, Orthogonale undUnitäre Transformationen

1.1 Approximationstheorie

Die Approximationstheorie beschäftigt sich mit der Fragestellung, wie man eine Zuordnung

f x D y f x W D a b a bf f f: ( ) , , , ,∈ ⊆ → = ∈ ⊆ ≡ ∈� � � (1-1)

durch eine nicht leere Menge

S ≡ ∈ ∈g x kk ( ) � �� � , mit D D D D Df g g g gk⊆ ≡ ∩ ∩ ∩ ∩

1 2� � (1-2)

approximieren kann. Um zu entscheiden, ob eine Approximation besser als eine andere ist,benötigt man einen Abstandsbegriff, der in geeigneten Funktionsmengen durch eine Norm gewonnen werden kann. Im folgenden soll die Approximationstheorie nicht in allerAllgemeinheit, sondern auf die für die Ingenieurwissenschaften wichtige Funktionsklasseorthogonaler Funktionen beschränkt werden.

Die Approximation eines Funktionals, eine eindeutigen Abbildung entsprechend der Aus-sage (1-1), soll mit der nicht leeren Menge (1-2) durch die allgemeine Fourier-Reihendar-stellung1

g x a g x ak kk

K

k( ) ( ) ,= ∈=∑

1

� (1-3)

vollzogen werden. Hierzu nimmt man an, daß sowohl f als auch ∀ k g xk ( ) abschnittsweisestetig bzw. Riemann-integrierbar sind. Die Güte der Approximation wird mit der Integral-norm (Methode der Gaußschen Fehlerquadrate)

Fx x

f x g x x x x D x xx

x

f2

2 1

2

1 2 2 1

1

1

2

=−

− ∈ >� ( ) ( ) , , ,� � d 2 (1-4)

beschrieben. Setzt man die Reihendarstellung (1-3) hierin ein, so erhält man:

Fx x

f x a g x xk kk

K

x

x2

2 1 1

21

1

2

=−

−���

�=

∑� ( ) ( ) d . (1-5)

Betrachtet man diese Gleichung, so wird klar, daß man für die Minimierung des Fehlers F2

lediglich die als verallgemeinerten Fourier-Koeffizienten bezeichneten Gewichtsfaktoren ak

1 Später wird der Grenzprozeß K →∞ vollzogen. Hierfür ist dann zusätzlich die gleichmäßige Konvergenz derFourier-Reihe anzunehmen.2 x x1 2≠ wäre zunächst ausreichend.

- 2 - Dr. Jörg Wollnack

frei wählen kann. Notwendig für ein Minimum ist, daß die partiellen Ableitungen

∀ ∈ ∂∂

i Ka

Fi

{ , , , }1 2 2� verschwinden. Damit erhält man:

∀ ∈ ∂∂

−���

� =

=∑�i K

af x a g x x

ik k

k

K

x

x

{ , , , } ( ) ( )1 2 01

2

1

2

� d . (1-6)

Nach Vertauschung der Reihenfolge von Differentiation und Integration sowie Anwendungder Kettenregel erhält man weiter:

∀ ∈ −���

�∂∂

−���

� =

= =∑ ∑�i K f x a g x

af x a g x xk k

k

K

ik k

k

K

x

x

{ , , , } ( ) ( ) ( ) ( )1 2 2 01 1

1

2

� d . (1-7)

Da ∀ ∂∂

=iia

f x( ) 0 und ∀ ∂∂

���

� ==

∑ii

k kk

K

iaa g x g x( ) ( )

1

ist, folgt:

∀ ∈ −���

� =

=∑�i K f x a g x g x xk kk

K

i

x

x

{ , , , } ( ) ( ) ( )1 2 01

1

2

� d , (1-8)

was äquivalent mit der Gleichung

∀ ∈ =� �∑=

i K f x g x x a g x g x xi

x

x

k k i

x

x

k

K

{ , , , } ( ) ( ) ( ) ( )1 21

2

1

2

1

� d d (1-9)

ist. In der Notation des Matrizenkalküls erhält man sodann die transparente Darstellung:

g x x g x g x x

g x g x x g x x

a

a

f x g x x

f x g x x

x

x

K

x

x

K

x

x

K

x

x

K

x

x

K

x

x

12

1

12

11

1

2

1

2

1

2

1

2

1

2

1

2

( ) ( ) ( )

( ) ( ) ( )

( ) ( )

( ) ( )

� �

� �

�

�

�

�

������

������

⋅

�

�

�����

�����=

�

�

������

������

d d

d d

d

d

�

� � �

�

� � . (1-10)

Es liegen somit K lineare Gleichungssysteme bezüglich der K Gewichtsfaktoren vor. EineLösung dieses linearen Gleichungssystems ist unabhängig von S immer möglich, wenn dieReihen der Matrix linear unabhängig sind. Anderenfalls kann man sich der Pseudoinversenoder Singulärwertzerlegung bedienen.

Aus der Struktur der Matrix in (1-10) ist zu erkennen, daß man bei dem Übergang auf eineSumme mit (K+1) Termen im allgemeinen sämtliche Gewichtsfaktoren neu berechnen muß.Es stellt sich die Frage, wie man diese Eigenschaft beseitigen kann? Dies führt im folgendenKapitel zu den orthogonalen bzw. orthonormalen erzeugenden Systemen.

1.2 Entwicklung nach orthogonalen und orthonormalen Funk-tionen

Betrachtet man die Struktur der Gleichung (1-10) und fordert, daß bei der Hinzunahme einerweiteren Erzeugenden K+1 nur der Gewichtsfaktor aK+1 neu zu berechnen ist, so kommt manzu der Forderung:

- 3 - Dr. Jörg Wollnack

∀ ∈ ==

� �

��� �p q K g x g x x

g x x p qp q

x

xp

x

x

, { , , , } ( ) ( )( )

1 2

01

2

1

2

2

� dd für

sonst

. (1-11)

In diesem Fall lassen sich die Gewichtsfaktoren voneinander unabhängig durch die Gleichung

∀ ∈ =��

k K a

f x g x x

g x xk

k

x

x

k

x

x{ , , , }

( ) ( )

( )

1 2 1

2

1

2

2

�

d

d

(1-12)

berechnen. Damit diese Gleichung Sinn macht, muß man ferner fordern, daß gilt:

∀ ∈ = >�k K C g x xk k

x

x

{ , , , } ( )1 2 02

1

2

� d , (1-13)

da ansonsten ein oder mehrere Koeffizienten undefiniert wären. Durch Normierung einesorthogonalen erzeugenden Systems läßt sich stets ein orthonormales System

′ ≡ ∈ ∈ ≡ ∈ ∈� ���

�����

S φkk

k

x kg x

Ck( )

( )� � � �� � . (1-14)

konstruieren. In diesem System erhält man die als Orthonormalitätsrelation

∀ ∈ =�p q K x x xp q

x

x

pq, { , , , } ( ) ( )1 21

2

� φ φ δd 3. (1-15)

bezeichnete Aussage. Man spricht dann von der Klasse der orthonormalen Funktionen ′S .

1.3 Vollständiges System orthonormaler Funktionen

Die Approximation über orthonormale Funktionensysteme erlaubt eine praktikableBerechnung der Gewichtsfaktoren der verallgemeinerten Fourier-Reihe. Das Fehlermaß wirdzwar ein Minimum aufweisen, jedoch würde man eine beliebige Erzeugende z.B. g3 aus demSystem eliminieren, so hätte man strukturell die gleiche Beschreibung vorliegen. Mann kannsomit nicht erkennen, ob eine gewisse Funktion gk

* im System fehlt. Insofern ist der bisherigeZustand der Beschreibung orthonormaler Systeme unbefriedigend, weshalb man den Begriffder Vollständigkeit eines erzeugenden Systems benötigt.

Betrachtet man das Fehlermaß

3 Kronecker-Symbol: δ pq

p q=

=� �1

0

für

sonst.

- 4 - Dr. Jörg Wollnack

F F f x a g x xk kk

K

x

x2

1

2

1

2

≡ = −���

�=

∑�C d( ) ( )

= − +���

�= =

∑ ∑� f x f x a g x a g x xk kk

K

k kk

K

x

x2

1 1

2

21

2

( ) ( ) ( ) ( ) d

= − +� ∑� ∑∑�= ==

f x x f x a g x x a a g x g x xx

x

k kk

K

x

x

p q p qq

K

p

K

x

x2

1 111

2

1

2

1

2

2( ) ( ) ( ) ( ) ( )d d d , (1-16)

so kann man die Reihenfolgen von Integration und Summation vertauschen und erhält:

F f x x f x a g x x a a g x g x xx

x

k k

x

x

k

K

p q p q

x

x

q

K

p

K

C d d d= − +� �∑ �∑∑= ==

2

1 111

2

1

2

1

2

2( ) ( ) ( ) ( ) ( ) . (1-17)

Wegen der Orthogonalität der Erzeugenden erhält man mit

b f x g x xk k

x

x

= �def

d( ) ( )1

2

(1-18)

weiter die Gleichung:

F f x x a b ax

x

k kk

K

kk

K

C d= − +� ∑ ∑= =

2

1

2

11

2

2( ) . (1-19)

Mit der binomischer Erweiterung

a a b b b a b bk k k k k k k k2 2 2 2 22− + − = − −� � (1-20)

läßt sich das Fehlermaß zu

F f x x a b bx

x

k kk

K

kk

K

C d= + − −� ∑ ∑= =

2 2

1

2

11

2

( ) � � (1-21)

interpretieren. Dieser mittlere quadratische Fehler ist minimal, wenn die Koeffizienten ak

gleich den verallgemeinerten Fourier-Koeffizienten bk sind. Damit gilt die Aussage:

∀ = ⇒ − ==∑k a b a bk k k kk

K

� �2

1

0 . (1-22)

Diese Bedingung reicht aus, um das Minimum des Fehlers F zu gewährleisten, wobei dieserdurch

F x x f x x bx

x

kk

K

C d2 12 2

11

2

− = −� ∑=

� � ( ) (1-23)

berechnet wird. Da der Fehler FC größer gleich null ist, kann man diese Aussage auch durchdie Besselsche Ungleichung

∀ ≥ > ≤=∑ �K x x b f x xkk

K

x

x

1 2 12

1

2

1

2

, ( ) d (1-24)

- 5 - Dr. Jörg Wollnack

ersetzen. Diese Abschätzung ist hilfreich, da man mit ihr die Konvergenz der allgemeinen

Fourier-Reihe für K →∞ aus der Existenz des Integrals ∀ > < ∞�x x f x xx

x

2 12

1

2

( ) d ableiten

kann. Funktionen f dieser Klasse werden als quadratisch Integrabel bezeichnet. Für die

Konvergenz der Reihe bkk

2

1=

∞

∑ ist es notwendig, daß lim lim ( ) ( )k

kk

k

x

x

b f x g x x→∞ →∞

= =� d1

2

0 ist.

Bemerkungen zum Konvergenzbeweis:

Wegen der Dreiecksungleichung der Betragsnorm und der Schwarzschen Ungleichung erhältman die Abschätzung

b g x b g x b g xk kk

k kk

k kk

( ) ( ) ( )=

∞

=

∞

=

∞

∑ ∑ ∑≤ =1

22

1

2 2

1

, (1-25)

woraus mit der Beschränktheit

∀ ∈ ∈ ≤ ∈ +k x D g x Af k{ , , }, ( )1 22 2

� � (1-26)

der erzeugenden Funktionen folgt:

01

2

2 2

1

≤ ≤=

∞

=

∞

∑ ∑b g x A bk kk

kk

( ) . (1-27)

Mit der Besselschen Ungleichung (1-24) erhält man sodann:

01

2

2 2

1

2

≤ ≤ < ∞=

∞

∑ �b g x A f x xk kk x

x

( ) ( ) d . (1-28)

Dies sichert die Konvergenz der allgemeinen Fourier-Reihe. Die quadratische Integrabilitätstellt somit eine hinreichende Bedingung dar.

Satz 1-1:

Eine Funktion f(x), die zumindestens im uneigentlichen Sinn qua-

dratisch Integrabel ∀ > < ∞�x x f x xx

x

2 12

1

2

( ) d ist, kann mit dem ortho-

normalen System erzeugender Funktionen

′ ≡ ∈ = ∈� ���

�����

�S dg x g x g x x k Kk p q

x

x

pq( ) ( ) ( ) , { , , , }�

1

2

1 2δ �

durch die verallgemeinerte Fourier-Reihe g x b g x Kk kk

K

( ) ( ) ,= ∈=∑

1

�

und deren verallgemeinerten Fourier-Koeffizienten

b f x g x xk k

x

x

= � ( ) ( ) d1

2

approximiert werden. Der mittlere quadratische

Fehler 1

2 1

2

1

2

x xf x g x x

x

x

−−� ( ) ( )� � d ist dann minimal und es gilt die

- 6 - Dr. Jörg Wollnack

Besselsche Ungleichung b f x xkk

K

x

x2

1

2

1

2

=∑ �≤ ( ) d . Für K →∞ gilt die not-

wendige Bedingung limk

kb→∞

= 0 .

Ausgehend von diesem Sachverhalt läßt sich die Vollständigkeit von ′S definieren:

Def. 1-1 Vollständigkeit:

Das orthonormale Funktionensystem der Erzeugenden ′S ist voll-ständig, wenn für jede quadratisch integrable Funktion ein K N> ( )εexistiert, so daß das Fehlermaß der verallgemeinerte Fourier-ReiheF < ε ist.

Diese Definition ist äquivalent mit dem Grenzwertbegriff, so daß gelten limK

F→∞

= 0 soll.

Wegen der Gleichung (1-23) geht die Besselsche Ungleichung (1-24) dann in dieParsevalsche Gleichung oder Vollständigkeitsrelation

b f x xkk x

x2

1

2

1

2

=

∞

∑ �= ( ) d (1-29)

über. Für das Verschwinden des Fehlers F ist die Vollständigkeitsrelation sowohl hinreichendals auch notwendig.

Die Bijektivität der Fourier-Reihendarstellung vollständiger orthonormaler Erzeugenden läßtsich indirekt Beweisen:

a) Eindeutigkeit der Fourier-Koeffizienten

Hierzu nimmt man an, daß zwei unterschiedliche, nicht überall verschwindende Funktionenf(x) und h(x) mit identischen Fourier-Koeffizienten bk existieren, so daß gilt:

∀ − = − =� �k b b f x g x x h x g x xf k hk k

x

x

k

x

x

( ) ( ) ( ) ( )d d1

2

1

2

0 . (1-30)

Aufgrund der Linearität des Fourier-Koeffizienten-Integrals erhält man auch:

∀ = −�k b f x h x g x xk k

x

x

( ) ( ) ( )� � d1

2

. (1-31)

Die Vollständigkeitsrelation (1-29) zeigt, daß dann gilt:

∀ = − =�k b f x h x xk

x

x

( ) ( )� �2

1

2

0d (1-32)

Woraus hinreichend und notwendig folgt, daß ∀ ∈ =x x x f x h x[ , ] ( ) ( )1 2 ist. Was im Wider-spruch zur Annahme steht.

b) Eindeutigkeit der Fourier-Summe

Geht man umgekehrt von zwei unterschiedlichen, nicht verschwindenen Sätzen von Fourier-Koeffizienten ∃ ≠ ≠k b bf k h k 0 aus, die die gleichen Fourier-Summen

- 7 - Dr. Jörg Wollnack

∀ ∈ =x x x f x h x[ , ] ( ) ( )1 2 , mit f x b g xf k kk

( ) ( )==

∞

∑1

und h x b g xhk kk

( ) ( )==

∞

∑1

(1-33)

produzieren, so erhält man wegen der Linearität der Fourier-Summen ferner:

∀ ∈ − = −=

∞

∑x x x f x h x b b g xf k h k kk

[ , ] ( ) ( ) ( )1 21

� � . (1-34)

Mit der Vollständigkeitsrelation (1-29) erhält man weiter:

b b f x h x xf k hkk x

x

− = −=

∞

∑ �� � � �2

11

2

( ) ( ) d . (1-35)

Das Integral der rechten Seite der Vollständigkeitsrelation verschwindet wegen der angenom-men Identität der Fourier-Summen. Da nach Voraussetzung mindestens ein nicht ver-schwindendes Paar von Fourier-Koeffizienten existiert, erhält man den Widerspruch zurAnnahme.

Mit a) und b) gilt der Satz:

Satz 1-2 Bijektivität der verallgemeinerten Fourier-Reihen vollständiger ortho-normaler Systeme:

Die Zuordnung von verallgemeinerten Fourier-Koeffizienten voll-ständiger, orthonormaler erzeugender Systeme ′S und Fourier-Sum-menfunktion ist für quadratisch integrable Funktionen bijektiv.

1.4 Beispiele vollständiger orthonormaler Funktionensysteme

1.4.1 Trigonometrische Funktionen in komplexer Darstellung

Das orthonormale Funktionensystem der trigonometrischen Funktionen in komplexer Dar-stellung findet hauptsächlich Verwendung bei periodischen und periodisch fortgesetztenFunktionen f x f x X( ) ( )= + 0 .

Dieses System hat folgende Eigenschaften:

Definitionsbereich:

D X X Xf ≡ + ≡ ∩[ , ]0 0 02π . (1-36.1)

Erzeugendes System:

g x e kkj k x( ) , { , , , , , , }= ∈ − −1

22 1 0 1 2

π� � . (1-36.2)

Komplexer Fourier-Koeffizient:

C f x e xkj k x= −

∩�1

2 2π π

( ) d . (1-36.3)

Komplexe Fourier-Reihe:

- 8 - Dr. Jörg Wollnack

f x f xC ek

j k x

k

( ) ( )− +

=−∞

∞+ = ∑2 . (1-36.3)

1.4.2 Walsh-Funktionen

Die Walsh-Funktionen sind wegen ihres Wertevorrats wal ≡ − +{ , }1 1 besonders für diedigitalen Systeme bzw. digitale Signalverarbeitung geeignet. Die Zweiwertigkeit derErzeugenden ermöglicht eine einfache Übersetzung der algebraischen Verhältnisse in dieSchaltungstechnik digitaler Systeme.

Dieses System hat folgende Eigenschaften:

Definitionsbereich:

D b bf ≡ ∈[ , ] ,0 � . (1-37.1)

Erzeugendes System:

g x kx

bk ( ) =���

�2

2Sal , mit Sal Wal( , ) ( , )v x v x n n n= − =2 1

1 2φ φ φ

µ� und

2 1 2 2 21 21 2v n n nn n n− = + + + > > >� �

µµ, (1-37.2)

Hierbei sind φ πnn x= sign sin 2� �� � die orthogonalen Rademacher-Funktionen und Wal bzw.

Sal die Walsh-Funktionen.

1.4.3 Laguerresche Polynome

Die Laguerreschen Polynome sind für die Systemtheorie von Bedeutung, da ihre Laplace-Transformierte rationale Bildfunktionen darstellen.

Dieses System hat folgende Eigenschaften:

Definitionsbereich:

Df ≡ ∞[ , ]0 . (1-38.1)

Erzeugendes System:

g x ek

s

x

skk

xs

s

s

k

( ) ( )!

, { , , , }= − ∈−

=∑2

0

1 0 1 2 � . (1-38.2)

1.4.4 Spaltfunktionen

Die Entwicklung nach Spaltfunktionen findet Anwendung auf reguläre Signale, derenFrequenzspektren vom Grad ω ω≤ B im Sinne der Gleichung

f z F j e z t jj z( ) ( ) , ( )= = +−�1

2πω ω τω

ω

ω

B dB

B

(1-39)

sind. Bedeutsam ist ferner die Tatsache, daß die zu approximierenden Funktionen nicht not-wendiger Weise quadratisch integrabel zu sein brauchen, wenn die Abtastrate T0 nach der Un-

- 9 - Dr. Jörg Wollnack

gleichung T0 ≤πωB

gewählt wird. Die Relation zwischen dem Frequenzspektrum und der Ab-

tastrate nennt man das Shannonsche Abtasttheorem bandbegrenzter Signale

F jF j

B ( )( )

ωω ω ω

=≤�

�

für

0 sonstB . (1-40)

Diese Relationen sind einzuhalten, wenn sichergestellt sein soll, daß die abgetasteten Signaleim Sinne von (1-39) zu rekonstruieren sind.

Dieses System hat folgende Eigenschaften:

Definitionsbereich:

Df ≡ −∞ ∞[ , ] . (1-41.1)

Erzeugendes System:

g xT T

x k T kk ( ) , { , , , }= −���

� ∈1

0 1 20 0

0siπ � � � , mit

siπ

π

πTx k T

Tx k T

Tx k T0

00

0

00

−���

� =

−���

�

−� �

� �

� �

sin

. (1-41.2)

1.4.5 Weitere Systeme

Sind z.B. die Hermiteschen Polynome, die Besselschen Zylinderfunktionen undLegendreschen Kugelfunktionen. Für Einzelheiten hierzu sei auf [???] verweisen.

1.5 Komplexe Fourier-Reihe

Die gesonderte Betrachtung der komplexen Fourier-Reihe wird vorgenommen, weil dieseeine große Bedeutung in den Natur- und Ingenieurwissenschaften erlangt hat. HarmonischeFunktionen sind z.B. Lösungen linearer, zeitinvarianter Differentialgleichungen zweiterOrdnung. Diese Systeme spielen eine bedeutsame Rolle in der Technik, woraus sich erklärt,daß viele praktische Meß- und Signalverarbeitungsmethoden bis hin zur schnellen Fourier-Transformation (FFT) auf der Bestimmung Harmonischer beruhen. Die auch als Trans-formation zu interpretierende Zuordnung von Originalfunktion f(x) und Transformiertea k Ck( ) ≡ kann durch Erweiterung des Definitionsbereiches auf Df ≡ −∞ ∞[ , ] in der Form

abgewandelt werden, daß auch nicht periodische Funktionen zu approximieren sind. Dieseskizzierte Erweiterung verdeutlicht den Ideengang der zum Fourier-Integral bzw. zur Fourier-Transformation führt. Die Fourier-Transformation wiederum läßt sich für kausale Funktionenderart modifizieren, daß man die Laplace-Transformation erhält.

Wesentlicher als das bisher Gesagte ist aber, daß diese Transformationen Operationen bzw.Operatoren des Originalbereiches im Bildbereich einfacher gestalten. Dies sind z.B. dieFaltungs-, Korrelations-, Differential- und Integraloperatoren.

- 10 - Dr. Jörg Wollnack

Geht man von komplexen, periodischen Funktionen

∀ ∈ ∃ ∈ → =x y x y f x� � ( ) , mit ∀ ∈ = + ∈x f x f x X X� �( ) ( ) ,0 0 (1-42)

aus und verwendet das System der Erzeugenden der X0-periodischen komplexen Fourier-Reihe

′ ≡ ∈ ∈ ∈� ���

�����

S e k x Xj k

x

X2

00

π� � �, , , (1-43)

so ist für die Abstandsbeschreibung zwischen der komplexen Fourier-Reihe

g x C ek

j kx

X

k K

K

( ) ==−∑

20

π , (1-44)

das Betragsquadrat einer komplexen Zahl z z z2 = * im Sinne von

Fx

f x g x f x g x xx

2

0

1

0

= − −∩� ( ) ( ) ( ) ( )

*� � � � d (1-45)

heranzuziehen. Mit der Identitätsaussage

f x g x f x g x f x g x f x g x( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * *− − = − −� � � � � � � �

= − − +f x f x f x g x f x g x g x g x( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * * (1-46)

erhält man sodann:

X F f x f x x f x g x x f x g x x g x g x xx X X X

02

0 0 0 0

= − − +∩ ∩ ∩ ∩� � � �( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * *d d d d .(1-47)

Ersetzt man g(x) durch (1-44), so ergibt sich weiter:

X F f x x f x C e xX

k

j kx

X

k K

K

X

02 2 2

0

0

0

= −∩ =−∩� ∑�( ) ( )*d d

π

− +−

=−∩ =−

−

=−∩∑� ∑ ∑�f x C e x C e C e xk

j kx

X

k K

K

X

k

j kx

X

k K

K

l

j lx

X

l K

K

X

( ) * *2 2 2

0

0

0 0

0

π π πd d . (1-48)

Integration und Summation sind kommutativ, so daß

X F f x x C f x e xX

k

j kx

X

Xk K

K

02 2 2

0

0

0

= −∩ ∩=−� �∑( ) ( )*d d

π

− +−

∩=−

−

∩=−=−�∑ �∑∑C f x e x C C e e xk

j kx

X

Xk K

K

p q

j px

Xj q

x

X

Xq K

K

p K

K* *( )

2 2 20

0

0 0

0

π π πd d (1-49)

gilt. Aufgrund der Orthonormalitätsrelation

1

0

2 20 0

0X

e e xj p

x

Xj q

x

X

X

pq

π πδ

−

∩� =d (1-50)

ergibt sich

- 11 - Dr. Jörg Wollnack

FX

f x x C D C D C CX

k kk K

K

k kk K

K

k kk K

K2

0

21

0

= − − +∩ =− =− =−� ∑ ∑ ∑( ) * * *d ,

mit D f x e xk

j kx

X

X

=∩� ( )

20

0

πd (1-51)

und da ∀ ∈ − + = − − − = − − − −a b ab a b a b a a bb a b a b a a bb, * * * * * * * * *� � � � � � �� � ist, ge-

winnt man ferner die Gleichung:

FX

f x x C D C D C C D D C CX

k k k k k k k k k kk K

K2

0

21

0

= − − − − − +∩ =−� ∑( )

* * * *d � �� �� �

= − − − −∩ =−� ∑1

0

2

0x

f x x C D C D D DX

k k k k k kk K

K

( )* *d � �� �� � . (1-52)

Die rechte Seite dieser Gleichung ist genau dann minimal, wenn ∀ =k C Dk k ist, so daß man

012

0

2 2

0

≤ = −∩ =−� ∑F

Xf x x C

x

kk K

K

( ) d (1-53)

bzw. Besselsche Ungleichung

CX

f x xkk K

K

X

2

0

21

0=− ∩∑ �≤ ( ) d (1-54)

erhält. Der Begriff quadratisch integrabler Funktionen

1

0

2

0x

f x xX

( )∩� < ∞d (1-55)

und der Begriff der Vollständigkeit des erzeugenden Systems werden analog zum reellendefiniert, so daß

lim ( ) ( )K

k kk K

K

XXf x C g x x

→∞=−∩

− =∑�10

0

2

0

d 4 (1-56)

gilt. Damit muß sowohl die Parsevalsche Gleichung oder Vollständigkeitsrelation

1

0

2 2

0X

f x x CX

kk K

K

( )∩ =−� ∑=d (1-57)

als auch die notwendige Bedingung

limk

kC→∞

= 0 (1-58)

erfüllt sein.

4 Die gleichmäßige Konvergenz der komplexen Fourier-Reihe wird analog zum reellen Fall durch die qua-dratische Integrabilität gesichert.

- 12 - Dr. Jörg Wollnack

1.5.1 Konvergenzverhalten der Fourier-Reihe, Periodische Fortsetzung undWeierstraßscher Approximationssatz

Die vorherigen Beweisführungen bauen auf dem Riemannschen Integralbegriff auf. DieIdentitäts- und Eindeutigkeitsaussagen können sich daher nur auf Riemann-meßbare Funk-tionen beziehen. Stellt man sich eine uneigentliche Funktion (lim

α→0)

p c x xc x x x

c x xp p( , , , )/ /

, , , ,αα α

α=− ≤ ≤ +�

�

∈für

sonstp p2 2

0� (1-59)

vor und integriert diese über x unter anschließender Ausführung des Grenzprozesses limα→0

, so

zeigt sich, daß diese nicht Riemann-meßbar5 ist. Daher sind die Aussagen nur eindeutig bisauf eine Superposition einer endlichen Anzahl von Punktmengen der obigen Art. Die ab-schnittsweise stetigen, Riemann-integrierbaren Funktionen können an den Intervallgrenzender Abschnitte endliche Sprünge besitzen. Da die Terme der verallgemeinerten Fourier-Sum-men abschnittsweise stetig sind, stellt sich die Frage, welches Verhalten an den Sprungstellenvorliegt. Bei endlichen verallgemeinerten Fourier-Summen n < ∞ 6 müssen diese in denabschnittsweise steigen Intervallen der erzeugenden Funktionen ihrerseits stetig sein. DieFrage wird also nur dann zu untersuchen sein, wenn n→∞ strebt. Als notwendige Bedingungfür die Konvergenz der Fourier-Reihe gilt dann lim

nnC

→∞= 0.

Die Betrachtungen, die zu dieser Bedingungen führen, liefern jedoch keine Information überdie Art und Weise des Konvergenzverhaltens. Diese Frage beantwortet der Satz von Feyer7:

Geht man von der reellen Darstellungsform der Partialsumme der Fourier-Reihe trigono-metrischer Funktionen

sa

a k x b k xn k kk

n

= + +=∑0

12cos sin , mit (1-60.1)

a f x k x xk =−�1

π π

π

( )cos d (1-60.2)

b f x k x xk =−�1

π π

π

( )sin d (1-60.3)

aus und setzt die Gleichungen (1-60.2) und (1-60.3) in Gleichung (1-60.1) ein, so erhält mandie Gleichung:

5 ∀ ∈ = = + − − =� −

+x x x p c x x x c x c x x cp p

x

x

x

x

p pp

p[ , ] ( , , , ) / //

/

1 2 2

2

1

2

2 2α α α αα

αd � �� �

6 n = K7 Da Riemann-Integrale Punktmengen nicht messen, könnte man an einer endlichen Anzahl von belieben Stellenderartige Punkte überlagern, ohne den Integralwert zu verändern. Infolgedessen ließe sich der Wert an derSprungstelle beliebig per Definition festlegen. Für die Berechnung der Fourier-Koeffizienten hätte dies keinenEinfluß. Jedoch wird sich zeigen, daß die unendliche Fourier-Summe ein wohldefiniertes Verhalten an diesenStellen besitzt. Man wird dann per Definition ein derartigen Verhalten an den Sprungstellen definieren, so daßdann die Identitätsaussagen der Fourier-Summen auch an den Sprungstellen gelten. Letztlich wird derBijektivitätssatz (1-2) von diesem Verhalten tangiert. Eineindeutig kann also nur bis auf eine endliche Anzahlvon überlagerten Punktmengen vorliegen.

- 13 - Dr. Jörg Wollnack

s f x xn =∩�1

2π π

( ) d

+���

�

+���

�∩ ∩=

� �∑1

2 21π π π

f u k u u k x f u k u u k xk

n

( ) cos cos ( )sin sind d . (1-61)

Wegen der Kommutativität von Integration und Summation erhält unter Anwendung derAdditionstheoreme trigonometrischer Funktionen die Gleichung:

s f u k x u unk

n

= + −���

�

� �

���=∩

∑�1 1

2 12π π

( ) cos � �� � d . (1-62)

Für das arithmetische Mittel

Sn

sn

f u k x u un ll

n

k

n

l

n

= = + −���

�

� �

���

����

�� =

−

=∩=

−

∑ ∑�∑1 1 1 1

20

1

120

1

π π

( ) cos � �� � d

= + −���

�

� �

���=∩=

−

∑�∑1 1

2 120

1

nf u k x u u

k

n

l

n

π π

( ) cos � �� � d (1-63)

erhält man mit den Identitätsaussagen

1

2

12

21

+ − =+�

� −�

���

−=∑ cos

sin

sink x u

n x u

x uk

n

� �� �� �

� � und (1-64)

sinsin

sinl x u

n x u

x ul

n

+��

−�

��� =

−���

�

−��

=

−

∑ 1

22

20

12

� �� �

(1-65)

die Gleichung:

Sn

f u

n x u

x uun =

−���

�

−��

∩

�1

22

2

2

22π π

( )sin

sin

� �d . (1-66)

Ist ∀ ∈ =x D f xf ( ) 1, so folgt daraus, daß a k a bk k0 2 1 0= ∧ ∀ ≥ = = bzw. s Sn n= =1 ist.

Daher gilt dann ferner die Gleichung:

1

22

2

1

2

22n

n x u

x uu

π π

sin

sin

−���

�

−��

=∩�

� �d . (1-67)

Nimmt man an, daß f(x) in jedem Punkt einen rechtsseitigen und linksseitigen Grenzwertf x( )+ und f x( )− besitzt und bis auf eine endliche Anzahl von endlichen Sprüngen stetig ist,so läßt sich die Gleichung (1-67) nutzen, indem man 2 f x f x( ) ( )+ −+� � mit dieser Gleichungmultipliziert. Man erhält sodann die Gleichung:

- 14 - Dr. Jörg Wollnack

1

21

1

2 22

2

1

2

22

f x f xn

f x f xn x u

x uu( ) ( )

( ) ( )sin

sin+ −

+ −

∩

+ ⋅ = +��

−���

�

−��

=�� �� �

π π

d . (1-68)

Subtrahiert man nun Gleichung (1-68) von (1-66), so erhält man die Gleichung:

Sf x f x

nf u

f x f xn x u

x uun −

+= − +�

�

−���

�

−��

+ − + −

∩�( ) ( )

( )( ) ( )

sin

sin

� �� �

2

1

2 22

2

2

22π π

d . (1-69)

Wählt man die Integration über eine Periode derart, daß man über das Intervall x x− +π π,integriert, so läßt sich das Integral in zwei Teilintegrale zerlegen. Man integriert erstens über

x x−π, und zweitens über x x, +π und erhält damit die Zerlegung:

Sf x f x

n −++ −( ) ( )� �2

= − +��

−���

�

−��

+ −

−�1

2 22

2

2

2nf u

f x f xn x u

x uu

x

x

π π

( )( ) ( )

sin

sin

� �d

+ − +��

−���

�

−��

+ −+

�1

2 22

2

2

2nf u

f x f xn x u

x uu

x

x

π

π

( )( ) ( )

sin

sin

� �d . (1-70)

Substituiert man im ersten Integral mit u x v= −2 und im zweiten Integral mit u x v= +2 undvollzieht die Variablentransformation

vx u

vu= − ⇒ =

2 2d

d und

vu x

vu= − ⇒ =

2 2d

d , (1-71)

so erhält man nach einigen Umformungen die Gleichung:

Sf x f x

n −++ −( ) ( )� �2

= − − − +��

+ −�1

22

22

2

22

0

nf x v

f x f x n v

vv

π π

( )( ) ( ) sin

sin/

� �� � d

+ + − +��

+ −�1

22

22

2

20

2

nf x v

f x f x n v

vv

π

π

( )( ) ( ) sin

sin

/ � �� � d . (1-72)

Dies läßt sich zu

∆ ≡ −++ −S

f x f xn

( ) ( )� �2

= + + − + −+ −�12 2

2

20

2

nf x v f x v f x f x

n v

vv

π

π

( ) ( ) ( ) ( )sin

sin

/

� � � �� � d (1-73)

- 15 - Dr. Jörg Wollnack

zusammenfassen. Zur Abkürzung läßt sich

φ( ) ( ) ( ) ( ) ( )v f x v f x v f x f x= + + − + −+ −2 2 (1-74)

einführen. Diese gerade Funktion ist an der Stelle v stetig, da für jede Folge von v, die gegennull konvergiert, gilt:

lim ( ) ( )vv

f x v f x→>

++ =0

0

2 und lim ( ) ( )vv

f x v f x→>

−− =0

0

2 bzw.

lim ( ) ( )vv

f x v f x→<

+− =0

0

2 und lim ( ) ( )vv

f x v f x→<

−+ =0

0

2 . (1-75)

Damit gilt φ ε( )v < für v < <η π2

. Zerlegt man das Integral (1-73) in die Intervalle 0,η

und η π, 2 , so erhält man die Gleichung:

∆ = +�

��

�

��� �

1 2

20

2

2

2

nv

n v

vv v

n v

vv

πφ φ

η

η

π

( )sin

sin( )

sin

sin

/� �

� �

d d . (1-76)

Eine Abschätzung über die Betragsnorm mit

φ ε( )v = und Max Maxdef

φ( ) ( )v f x M � �≤ =4 4 (1-77)

ergibt die Ungleichung:

Sf x f x

n

n v

vv

M

n

n v

vvn −

+< ++ − � �

( ) ( ) sin

sin

sin

sin

/� � �

� � 2

42

20

2

2

2επ π

η

η

π

d d . (1-78)

Mit Gleichung (1-67) läßt sich die Ungleichung

επ

εη

n

n v

vv

sin

sin

2

20

� �

d� < (1-79)

formulieren. Das zweite Integral kann wegen 0 12≤ ≤sin n v� und sin sinv ≥ η durch die Un-gleichung

4 4 12

2

2

2

2M

n

n v

vv

M

nv

π π ηη

π

η

πsin

sin sin

/ /� �

d d� �< = −4 22

M

nππ η

η/

sin(1-80)

abgeschätzt werden. Damit gilt für hinreichend große n:

Sf x f x M

nn −+

< + <+ −( ) ( )

sin

� 2

2 12

2ε

ηε .

Der Satz von Feyer besagt nun, daß für jedein 2π periodische integrierbare Funktion f(x),die einen links- und rechtsseitigen Grenzwertan der Stelle x hat, im Sinne des arith-metischen Mittel Sn für jedes x gegen

f x f x( ) ( )+ −+� 2 konvergiert.

Die Untersuchung der Reihen und arith-metischen Mittel lehrt einige wichtige Zu-

u

1

0 .5

0 .5

1

� �/2

���� ��

Abb. 1-1: Sinusfunktion

- 16 - Dr. Jörg Wollnack

sammenhänge, die in dem Hardyschen Satz ausgedrückt werden:

Satz 1-3 Hardyscher Satz:

Konvergiert die Folge der arithmetischen Mittel gegen Sn

sn

kk

n

=→∞

=∑lim

1

1

und gilt für die Glieder der Reihe s uk ll

k

==∑

1

die Ungleichung uA

ll <

mit festem A > 0, so konvergiert die Reihe limk

ll

k

u→∞

=∑

1

und es gilt

lim limk

ll

k

nk

k

n

un

s→∞

=→∞

=∑ ∑=

1 1

1.

Die dann vorliegende Gleichheit der Grenzwerte kann dazu genutzt werden, die Aussage desSatzes von Feyer, nach Überprüfung der Voraussetzungen des Satzes von Hardy, auf dieFourier-Reihe zu vererben. Damit erhält man den Satz von Jordan:

Satz 1-4 Jordanscher Satz:

Die Fourier-Reihe einer in 2π periodischen Funktion von beschränk-ter Variation konvergiert in jedem abgeschlossenen Intervall gleich-mäßig gegen die Summe f x f x( ) ( )+ −+� � 2 .

Aufgrund dieses Sachverhaltes hat sich die Notation

f x f x aa k x b k x

nk k

k

n( ) ( )lim cos sin+ −

→∞=

+ = + +∑2 22 20

1

π π (1-82)

eingebürgert, die diese Eigenschaft zum Ausdruck bringen soll.

• Periodische Fortsetzung

Die Fourier-Reihenentwicklung werden im allgemeinen auf periodische Funktionen ange-wendet. Die vorherigen Betrachtungen können jedoch ohne Beschränkung der Allgemeinheitauf nicht periodische Funktionen des Intervalls −π π, übertragen werden. Die Aussagen gel-ten dann nur für das Intervall −π π, . Setzt man die Funktion außerhalb dieses Intervalls perDefinition so fort, daß sie der Periodizitätsbedingung genügt, so spricht man von periodischerFortsetzung und die Konvergenzsätze gelten sodann außerhalb des Intervalls −π π, .

• Weierstraßscher Approximationssatz

Der Weierstraßsche Approximationssatz ist nahezu eine unmittelbare Folge des FeyerschenSatzes. Dieser Satz besagt, daß jede in einem abgeschlossenen Intervall a b, stetige Funktiongleichmäßig durch Polynome approximiert werden kann. Fordert man ferner die Differenzier-barkeit der Funktion an der Stelle x0, so sichert die Existenz des Differentials die Stetigkeitvon f an der Stelle x0. Die Stetigkeit ihrerseits setzt die Äquivalenz von rechts- und links-seitigem Grenzwert voraus, womit die Fourier-Summen von f gegen den Wert f(x0) konver-gieren. Die Güte der Approximation wird dabei von lokalen Eigenschaften von f bestimmt.Unter lokal versteht man in diesem Zusammenhang eine ε-Umgebung an der Stelle x0.

- 17 - Dr. Jörg Wollnack

1.5.2 Faltung und Kreuzkorrelation periodischer Funktionen

Faltungs- und Korrelationsoperationen haben in der Technik eine große Bedeutung erlangt.Der Faltungssatz stellt eine hinreichende und notwendige Bedingung für lineare, zeit-invariante Systeme dar, so daß die Faltung als Systemoperator Ein- und Ausgangssignale ver-knüpft. Die Korrelation hat sich als am besten angepaßtes Filter (matched Filter) für einenlineares, zeitinvariantes System mit additiven stationärem weißen Rauschen als Störsignalherausgestellt. Faltung und Korrelation wiederum sind auf einfache Weise miteinander ver-knüpft.

a) Zyklische Faltung

Betrachten man das Faltungsintegral

f u g u x f x gx

x

x

x

( ) * ( ) ( ) ( ) ( )� �1

2

1

2

= −� τ τ τd , (1-83)

mit den in X0-periodischen Funktionen f x f x k X k( ) ( ) ,= + ∈0 � undg x g x k X k( ) ( ) ,= + ∈0 � , so ist zu vermuten, daß die Faltung ihrerseits X0-periodischf u g u x f u g u x k X k( ) * ( ) ( ) ( ) * ( ) ( ) ,� � � �= + ∈0 � ist. Deshalb muß die Aussage

f x g f x x gx

x

x

x

( ) ( ) ( ) ( )!

− = + −� �τ τ τ τ τ τd d1

2

1

2

0 (1-84)

wahr sein. Da die Faltung kommutativ bezüglich f und g sein soll, muß ebenso die Aussage

g x f g x X fx

x

x

x

( ) ( ) ( ) ( )!

− = + −� �τ τ τ τ τ τd d1

2

1

2

0 (1-85)

wahr sein. Was wegen der Eindeutigkeit des Riemannschen Integrals und der Periodizität vonf und g erfüllt ist. Wegen den Periodizität des Integranden ist lediglich die Integration übereine Periode ∩ X 0 vorzunehmen (Lageinvarianz des Periodenintervalls). Deshalb definiertman im Zusammenhang mit X0-periodischen Funktionen die periodische Faltung zu:

f u g u xx

f x gX

( ) * ( ) ( ) ( ) ( )� � = −∩�1

0 0

τ τ τd . (1-86)

Die Normierung der Faltung auf X0 ist nicht allgemein üblich. Diese Darstellung hat jedochden Vorteil, die bei der Berechnung der Fourier-Koeffizienten der Faltung dieser Faktor nichtin Erscheinung tritt. Wegen der Periodizität der Faltung nennt man diese auch zyklischeFaltung.

Die Fourier-Koeffizienten f k Cf k^ ( ) ≡ der zyklischen Faltung berechnen sich zu:

f u g u kX X

f x g e xX

j kx

X

X

( ) * ( ) ( ) ( ) ( )^� � = −

���

�∩

−

∩��1 1

0 0

2

0

0

0

τ τ τπ

d d . (1-87)

Da die Integrationsgrenzen unabhängig von den Integrationsvariablen sind, ist die Reihen-folge der Integration kommutativ, so daß ferner gilt:

f u g u kX x

f x e x gj k

x

X

Xx

( ) * ( ) ( ) ( ) ( )^� � = −

���

�

−

∩∩��1 1

0 0

20

00

τ τ τπ

d d . (1-88)

- 18 - Dr. Jörg Wollnack

Durch die Substitution v x v x x v= − ⇒ = ∧ = +τ τd d ergibt sich ferner für den Fourier-Koeffizient:

f u g u kX X

f v e x gj k

v

X

Xx

( ) * ( ) ( ) ( ) ( )^� � =

���

�

− +

∩∩��1 1

0 0

20

00

π τ

τ τd d

=���

�

−

∩

−

∩��1 1

0 0

2 20

0

0

0X x

f v e x e gj k

v

X

X

j kX

X

( ) ( )π π τ

τ τd d . (1-89)

Durch Strukturvergleich mit der Berechnungsvorschrift der Fourier-Koeffizienten erhält mansodann die Gleichung:

f u g u k f k g k( ) * ( ) ( ) ( ) ( )^ ^ ^� � = . (1-90)

Die Faltungsoperator führt im Bildbereich der Fourier-Reihe zu einer algebraischenOperation, der Multiplikation der Fourier-Koeffizienten. Wenn diese Beziehung ohne weitereEinschränkungen gelten soll, so muß gezeigt werden, daß aus der quadratischen Integrabilitätvon f und g auf die Existenz der Darstellung

f u g u x f u g u k ek

j kx

X( ) * ( ) ( ) ( ) * ( ) ( )^� � � �=∑

20

π(1-91)

geschlossen werden kann. Mit der Besselschen Ungleichung

f kX

f x xk X

^ ( ) ( )2

0

21

0

∑ �≤ < ∞∩

d (1-92)

folgt, daß für jede quadratisch integrable Funktion die gleichmäßige Konvergenz der Fourier-

Reihe vorliegt. Aufgrund der Schwarzschen Ungleichung x y x x y y, , ,� � � �� �2≤ ergibt sich

weiter:

f k g k f k g kk k k

^ ^ ^ ^( ) ( ) ( ) ( )∑ ∑ ∑≤2 2

, (1-93)

so daß man mit der Besselschen Ungleichung die Relation

f k g kX

f k xX

g k xk X X

^ ^ ^ ^( ) ( ) ( ) ( )∑ � �≤∩ ∩

1 1

0

2

0

2

0 0

d d (1-94)

erhält. Damit kann man aus der quadratischen Integrabilität von f und g auf die gleichmäßigeKonvergenz der Fourier-Reihe (1-91) schließen. Zusammen mit dem Bijektivitätssatz (1-2)sichert man den Sinn der Aussage. Was zu beweisen war.

a) Zyklische Kreuzkorrelation

Die zyklische Kreuzkorrelation

f u g u xX

f x gX

( ) ( ) ( ) ( ) ( )*�� � = +

∩�1

0 0

τ τ τd . (1-95)

zweier X0-periodischer Funktionen f und g erhält man analog:

• Antikommutativität f u g u x g u f u x( ) ( ) ( ) ( ) ( ) ( )*

� �� � � �= − (1-96)

- 19 - Dr. Jörg Wollnack

• Periodizitätsrelation f u g u x f u g u x X( ) ( ) ( ) ( ) ( ) ( )� �� � � �= + 0 (1-97)

• Fourier-Koeffizient f u g u k f k g k( ) ( ) ( ) ( ) ( )^ ^ ^

�� � = (1-98)

Die Autokorrelation geht aus der Kreuzkorrelation für f = g hervor.

1.5.3 Vollständigkeit der komplexen Fourier-Reihe

Mit Hilfe der zyklischen Faltung läßt sich die Vollständigkeit des komplexen Fourier-Reihe

beweisen. Setzt man in den Faltungssatz g fdef

( ) ( )*τ τ= − ein, so ergibt sich

1

0 0X

f x fX

( ) ( )*− −∩� τ τ τd , welches zur Äquivalenzaussage

1

0

2

0

0

Xf x f f k f k e

X

j kx

X

k

( ) ( ) ( ) ( )* ^ ^*− − =∩� ∑τ τ τ

πd (1-99)

führt. An der Stelle x = 0 erhält man mit Substitution u = −τ und unter Nutzung derEigenschaft eines periodischen Integranden die Parsevalsche Gleichung bzw. Vollständig-keitsrelation:

1

0 0X

f f f k f kX k

( ) ( ) ( ) ( )* ^ ^*τ τ τd∩� ∑= . (1-100)

Diese Beziehung ließe sich analog auch über den Korrelationssatz entwickeln.

1.5.4 Finite Darstellungen und Diskretisierung in Technik und Theorie

Die Infinitesimalrechnung baut auf Grenzprozessen und Kontinua reeller Zahlen auf. Dietechnische Realisierung dieser Begriffe ist auf einer elektronischen Datenverarbeitungsanlagebzw. einem digitale Rechner wegen der notwendigen endlichen Rechenzeit und der be-grenzten Speicherressourcen technisch letztlich unmöglich8. Der endliche Automat verlangteine Mathematik, die einen finiten Charakter hat. Hierzu kann man sich z.B. der Ursprüngeder infiniten Begriffe bedienen:

Das Differential kann über einen Differenzenquotienten

∂∂

= + − −f

xx

f x h f x

h

R x h

hf( )

( ) ( ) ( , ) , mit

lim ( , )h

fR x h→

=0

0 von höherer Ordnung als h, (1-101)

das Integral über eine Summe

f x xb a

Mf k

b a

Ma R a b M

a

b

k

M

Sf( ) ( , , )d� ∑= − − +���

� +=

−

0

1

, mit lim ( , , )M

SfR a b M→∞

= 0 (1-102)

8 Letztlich wird aber auch die nur endlich zur Verfügung stehende Energie zum limitierenden Faktor, da manbeim Einschalten des Rechnersystems die Speicherzellen der Zahlen in einen definierten Zustand bringen muß.Diese Erhöhung der Systemordnung benötigt Energie, weshalb eine infinite Zahlendarstellung bereits hierdurchausgeschlossen werden muß. Die reellen Zahlen und damit die Kontinuumsmathematik bleiben damit allerWahrscheinlichkeit nach auf den menschlichen Geist beschränkt.

- 20 - Dr. Jörg Wollnack

und die reelle Zahl über eine endliche Polyadische Zahl

∀ ∈ ∃ ∈ ∧ ∈ < <x x x x x x� � � �\ 1 2 1 2 (1-103)

näherungsweise dargestellt werden. Die Wandlung der reellen Zahl in eine duale, polyadischeZahl wird technisch durch den Analog / Digitalwandler vollzogen.

Es entstehen ferner diskrete Systembeschreibungen durch X0-periodische Abtastung der kon-tinuierlichen Funktionsverläufe bzw. Signale im Sinne von:

f k f k X a k K( ) ( ) , { , , , , }≡ + ∈ −0 0 1 2 1� ,

Xb a

Kb a K K0 1

1= −−

∈ > ∈, , , ,� � . (1-104)

Dabei stellt sich die Frage, ob und unter welchen Voraussetzungen man von den diskreten aufdie kontinuierlichen Formen schließen kann bzw. welche Zusammenhänge zwischen denkontinuierlichen und diskreten Formen existieren. In den ersten beiden Fällen ist dasShannonsche Abtasttheorem von zentraler Bedeutung (siehe auch bandbegrenzte Signa-le Kapitel 1.4.4). Bei der Zahlendarstellung wird die Wandlung vom Diskreten zumKontinuierlichen mit Hilfe eines Digital / Analogwandlers vollzogen.

Man könnte sich nun sicherlich fragen, warum man nicht gleich ein Studium der finitenMathematik vollzieht, welches den digitalen Rechnersystemen von vornherein besser ange-paßt ist. Die Kontinuumsmathematik liefert jedoch strukturelle Einblicke und mathematischeSätze, die wahrscheinlich in der finiten Mathematik nur schwer zu erkennen wären. Vermut-lich gilt auch die Umkehrung des Gesagten. So ist wohl die Entdeckung des Cooley TukeyAlgorithmus auf die Betrachtung der strukturellen Eigenschaften der finiten Mathematik zu-rückzuführen. Hieraus erklärt sich, daß in den letzten Jahren zusammen mit der Entwicklungder Datenverarbeitung, Mikroelektronik und Rechnertechnik die numerische Mathematik anBedeutung gewonnen hat.

1.5.5 Zur Idee der diskreten Fourier-Transformation

Approximiert man ein Integral gemäß (1-102), so ergibt sich bei X0-periodischen Funktionendie als Rechteckregel bekannte Formel:

f x x h f k h R hX

k

M

Sf( ) ( ) ( )d0 0

10

� ∑= +=

−

, mit hX

M=

−0

1 . (1-105)

Existieren für die Funktion f die partiellen Ableitungen ∂∂

∈2

21 2

k

k

f

xx k n( ) , { , , , }� an der

Stelle 0 und X0 und sind diese identisch, so hat die Integralapproximation einen Fehler in derGrößenordnung h n2 . Hinsichtlich der Konvergenzeigenschaften ist die Quadraturformel opti-mal, da keine noch so komplizierte Quadraturformel ein besseres asymptotisches Verhaltenaufweist.

Für den komplexen Fourier-Koeffizienten ergibt sich dann der diskrete, komplexe Fourier-Koeffizient zu:

- 21 - Dr. Jörg Wollnack

f kX

X

Mf

m X

Me R hM

m

M j km X

M XSf

^ ( ) ( )= ���

� +

=

− −

∑1

0

0 0

0

1 2 0

0

π , mit h

X

M= 0

= ���

� +

=

− −

∑1 0

0

1 2

Mf

m X

Me R h

m

M j km

MSf

π( ) . (1-106)

Um die Zahl der Stützstellen, über die der diskrete, komplexe Fourier-Koeffizient berechnetwird, im Symbol mit aufzunehmen, wird die Notation von Niederdrenk [???] übernommen.Im Grenzprozeß M →∞ konvergiert der diskrete komplexe Fourier-Koeffizient gegen denkomplexen Fourier-Koeffizienten.

Dieser diskrete komplexe Fourier-Koeffizient ist M-periodisch, da gilt:

f k MM

fm X

MeM

m

M j k Mm

M^ ( )+ = ���

�=

− − +

∑1 0

0

1 2π� �

= ���

�=

− − −∑1 0

0

1 2 2

Mf

m X

Me e

m

M j km

M j k mπ π

= ���

�=

− −

∑1 0

0

1 2

Mf

m X

Me

m

M j km

Mπ

. (1-107)

Um die Fourier-Reihe an die Erfordernisse der numerischen Datenverarbeitung anzupassen,ist eine weitere Verfolgung des eingeschlagenen Weges nicht sinnvoll. Diese Vorüber-legungen dienen lediglich zur Motivation. Mit der Methode der kleinsten Quadrate läßt sichein zum kontinuierlichen Fall analoger diskreter Ansatz verfolgen, der zu den unitären- undorthogonalen diskreten Transformationen führt und unmittelbar endliche Summen aufgreift.Dieser Ansatz kann durchsichtig mit dem Matrizenkalkül dargestellt werden. Lediglich dieverwendeten Zahlen sind weiterhin infinit.

2 Diskrete Ansätze und Unitäre Transformationen

2.1 Reeller diskreter Ansatz (Motivation)

Geht man von diskreten Abbildungen

f m M y f m Wm f: { , , } ( )∈ ⊆ → = ∈ ⊆1� � � (1-108)

aus und eine nicht leere Menge diskreter erzeugender Funktionen

S ≡ ∈ ∈ ∈g x m M k Kk m( ) { , , } , { , , }� 1 1� �� � , (1-109)

die zur Approximation der diskreten Abbildung im Sinne der verallgemeinerten diskretenFourier-Reihe

g x a g x am k k mk

K

k( ) ( ) ,= ∈=∑

1

� (1-110)

verwendet werden, so kann man die Fehlerquadrate

F y a g xm k k mk

K

m

M2 2

11

= −==∑∑ ( )� � (1-111)

- 22 - Dr. Jörg Wollnack

bestimmen. Notwendig für das Minimum ist, daß die partiellen Ableitungen verschwinden:

∂∂

= ∂∂

− ===∑∑a

Fa

y a g xp p

m k k mk

K

m

M2 2

11

0( )� � . (1-112)

Nach Anwendung der Kettenregel ergibt sich:

y a g xa

y a g xm k k mp

m k k mk

K

m

M

− ∂∂

− ===∑∑ ( ) ( )� � � �

11

0

⇒ ∀ ∈ − ===∑∑p K g x y a g xp m m k k mk

K

m

M

{ , , } ( ) ( )1 011

� � � . (1-113)

Wegen des großen Umordnungssatzes gilt auch:

y a g x g xm k k m p mm

M

k

K

− ===∑∑ ( ) ( )� �

11

0 bzw. (1-114)

∀ ∈ − === =∑∑ ∑p K a g x g x y g xk k m p mm

M

k

K

m p mm

M

{ , , } ( ) ( ) ( )1 011 1

� . (1-115)

Diese in ak linearen M-Gleichungssysteme lassen sich übersichtlich in der Matrixnotation dar-stellen, somit erhält man:

g x g x g x g x

g x g x

g x g x g x g x

a

a

a

y g xm mm

M

k

K

m K mm

M

k

K

i m j mm

M

k

K

M m mm

M

k

K

M m K mm

M

k

K

i

K

m m1 111

111

11

111 11

11( ) ( ) ( ) ( )

( ) ( )

( ) ( ) ( ) ( )

(== ==

==

== ==

∑∑ ∑∑

∑∑

∑∑ ∑∑

�

�

��������

��������

⋅

�

�

�����

�����=

� � �

� � � � �

� � � �

� � � � �

� � �

�

�

)

( )

( )

m

M

m i mm

M

m M mm

M

y g x

y g x

=

=

=

∑

∑

∑

�

�

��������

��������

1

1

1

�

�

.

(1-116)

Die Gewichtsfaktoren können für nicht quadratische Formen mit der Pseudoinversen oderSingulärwertzerlegung bestimmt werden. Ist die Anzahl der Proben gleich der Anzahl Ge-wichtsfaktoren (M = K), so liegt die quadratische Form vor, die bei linearer Unabhängigkeitdes erzeugenden System eindeutig lösbar ist.

Liegt ein orthogonales System erzeugender Funktionen

g x g xg x p q

p m q mm

Mp m

m

M

( ) ( )( )

==∑ ∑=

=� �

��1

2

1

0

für

sonst

(1-117)

vor, so vereinfacht sich die Bestimmung der Gewichtsfaktoren in analoger Weise zu:

ay g x

g xk

m k mm

M

k mm

M= =

=

∑

∑

( )

( )

1

2

1

. (1-118)

Analog zum kontinuierlichen Ansatz läßt sich jedes diskrete orthonormale System

orthonormalisieren, indem man die erzeugenden Funktionen auf g xk mm

M2

1

( )=∑ normiert.

- 23 - Dr. Jörg Wollnack

Es zeigt sich, daß man im diskreten Fall analoge Beziehungen erhält, so daß auch nichtorthonormale erzeugende Systeme verwendet werden können. Der eingeschlagene Weg dientauch hier zur Motivation des folgenden Abschnitts.

2.2 Unitäre und orthonormale Transformationen

Es ist sinnvoll, zunächst die Unitären Transformationen zu betrachtet, da die orthonormalenals ein Spezialfall gedeutet werden können.

a) Unitäre Systeme

Geht man von diskreten komplexen Funktionen

∀ ∈ ∃ ∈ → =m y m y f mm� � ( ) (1-119)

aus und verwendet das unitäre erzeugende System

′ ≡ ∈ ∈ ∈ = =� ����=

∑S g m m M k K K M g m g mk p qm

M

pq( ) { , , } , { , , } , , ( ) ( )*� 1 1

1

� � δ ,

(1-120)

so ist für die Abstandsbeschreibung zwischen der verallgemeinerten diskreten komplexenFourier-Reihe

g m C g mk kk

K

( ) ( )==∑

1

(1-121)

und dem Funktional f das Betragsquadrat einer komplexen Zahl z z z2 = * im Sinne von

F f m g m f m g mm

M2

1

= − −=∑ ( ) ( ) ( ) ( )

*� � � � (1-122)

heranzuziehen. Mit der Identitätsaussage

f m g m f m g m f m g m f m g m( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * *− − = − −� � � � � � � �

= − − +f m f m f m g m f m g m g m g m( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * * (1-123)

erhält man sodann:

F f m f m f m g m f m g m g m g mm

M

m

M

m

M

m

M2

1 1 1 1

= − − += = = =∑ ∑ ∑ ∑( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * * . (1-124)

Ersetzt man g(m) durch (1-121), so ergibt sich weiter:

F f m f m C g mm

M

k kk

K

m

M2 2

1 11

= −= ==∑ ∑∑( ) ( ) ( )*

− +=−= = ==∑∑ ∑ ∑∑f m C g m C g m C g mk k

k K

K

m

M

k kk

K

l kl

K

m

M

( ) ( ) ( ) ( )* * * *

1 1 11

. (1-125)

Nach dem großen Umordnungssatz der Summen gilt ferner:

- 24 - Dr. Jörg Wollnack

F f m C f m g mm

M

k km

M

k

K2 2

1 11

= −= ==∑ ∑∑( ) ( ) ( )*

− +== ===∑∑ ∑∑∑C f m g m C C g m g mk km

M

k

K

p q p qm

M

q

K

p

K* * * *( ) ( ) ( ) ( )

11 111

. (1-126)

Aufgrund der Unitaritätsrelation

g m g mp qm

M

pq( ) ( )*

=∑ =

1

δ (1-127)

ergibt sich

F f m C D C D C Cm

M

k kk

K

k kk

K

k kk

K2 2

1 1 1 1

= − − += = = =∑ ∑ ∑ ∑( ) * * * ,

mit D f m g mk km

M

==∑ ( ) ( )*

1

(1-128)

und da ∀ ∈ − + = − − − = − − − −a b ab a b a b a a bb a b a b a a bb, * * * * * * * * *� � � � � � �� � ist, ge-

winnt man ferner die Gleichung:

F f m C D C D C C D D C Cm

M

k k k k k k k k k kk

K2 2

1 1

= − − − − − += =∑ ∑( )

* * * *� �� �� �

= − − − −= =∑ ∑f m C D C D D Dm

M

k k k k k kk

K

( )* *2

1 1

� �� �� � . (1-129)

Die rechte Seite dieser Gleichung ist genau dann minimal, wenn ∀ =k C Dk k ist, so daß man

0 2 2

1

2

1

≤ = −= =∑ ∑F f m Cm

M

kk

K

( ) (1-130)

bzw. die diskrete Besselsche Ungleichung

C f mkk

K

m

M2

1

2

1= =∑ ∑≤ ( ) (1-131)

erhält. Der Begriff quadratisch integrabler Funktionen kann im diskreten durch die Bedingung

∀ < ∞m f m( )2

(1-132)

ersetzt werden. Die Vollständigkeit des erzeugenden Systems werden analog zum kontinuier-lichen Fall definiert, so daß

f m C g mk kk

K

m

M

( ) ( )− ===∑∑

1

2

1

0 (1-133)

gilt. Damit muß sowohl die Parsevalsche Gleichung oder Vollständigkeitsrelation

f m Cm

M

kk

K

( )2

1

2

1= =∑ ∑= (1-134)

als auch die notwendige Bedingung

∀ < ∞k Ck (1-135)

erfüllt sein.

- 25 - Dr. Jörg Wollnack

Interpretiert man die Darstellung eines Funktionals f mittels der verallgemeinerten diskretenkomplexen Fourier-Reihe als Transformation zwischen den Vektoren f f M M( ) , , ( )1 �� �t ∈ �und C CM

M1 , ,�� �t ∈ � , so erhält man in der Matrizenschreibweise:

b Ta= , mit T =�

����

���∈ ×

g g M

g j

g g Mi

M M

M M1 11

1

* *

*

* *

( ) ( )

( )

( ) ( )

�

� �

�

� . (1-136)

Die inverse Transformation entspricht der verallgemeinerten diskreten komplexen Fourier-Reihendarstellung:

a T b= −1 , mit T− ×=�

����

���∈1

1

1

1 1g g

g i

g M g M

M

j

M

M M

( ) ( )

( )

( ) ( )

�

� �

�

� . (1-137)

Bildet man das Produkt aus

T T− =�

����

���⋅�

����

���

11

1

1 11 1 1

1

g g

g i

g M g M

g g M

g j

g g M

M

j

M

i

M M

( ) ( )

( )

( ) ( )

( ) ( )

( )

( ) ( )

* *

*

* *

�

� �

�

�

� �

�

, (1-138)

so gilt mit der Unitaritätsrelation:

E T T= = ���

�

���

� =

−

=∑1

1

g m g mi jm

M

i j( ) ( )* δ� �� � . (1-139)

Was zu beweisen war.

Für unitäre Matrizen gilt ferner die Unitaritätsrelation:

T T− =1 t* . (1-140)

Man bezeichnet diese Transformation als unitäre Transformation. Im diskreten Fall sind diequadratischen Formen (M = K) zugleich vollständig, so daß eine bijektive Abbildungzwischen den Räumen besteht.

b) Orthonormale Systeme

Die diskreten orthonormalen erzeugenden Systeme

′ ≡ ∈ ∈ ∈ = =� ����=

∑S g m m M k K K M g m g mk p qm

M

pq( ) { , , } , { , , } , , ( ) ( )� 1 11

� � δ (1-141)

können als Spezialfall der unitären Systeme gedeutet werden. Sie definieren die orthonor-malen Transformationen. Da jedes orthogonale System durch Normierung in ein orthonor-males System überführt werden kann, gelten die Aussagen in gleicher Weise für orthogonaleSysteme.

- 26 - Dr. Jörg Wollnack

2.3 Diskrete Fourier-Transformation

2.3.1 Diskrete Fourier-Transformation und Unitaritätsrelation

Die diskrete Fourier-Transformation gehört zu der Klasse der unitären Transformationen:

Erzeugendes System:

′ ≡ ∈ ∈ − =� ���

�����

−

=

−

∑S1

0 112 2 2 2

0

1

Me k m M

Me e

j km

Mj p

m

Mj q

m

M

m

M

pq

π π πδ� , { , , } ,� (1-142.1)

Diskreter Fourier-Koeffizient:

C f m g mk kk

M

==

−

∑ ( ) ( )*

0

1

, (1-142.2)

Diskrete Fourier-Summe:

g m C g mk kk

M

( ) ( )==

−

∑0

1

, (1-142.3)

Im Zusammenhang mit der Fast-Fourier-Transform (FFT) muß die Zahl der Stützstellen Meine Potenz von 2 sein. Diese Transformation ermöglicht, wie sich später zeigen wird, eineSpeicherplatzeffiziente (In Place) und schnelle, nicht von quadratischer Ordnung wachsendeBerechnung der diskreten Fourier-Transformation. Aus diesem Grunde soll im folgenden stetseine gerade Anzahl von Stützstellen, die der Bedingung M kk= ∈2 , � genügen, gewähltwerden.

Damit gilt zu zeigen, daß

1 2 2

0

1

Me e

j pm

Mj q

m

M

m

M

pq

π πδ

−

=

−

∑ = (1-143)

ist. Für p = q gilt:

1 1 11 1

2 2

0

1 2

0

1

0

1

Me e

Me

M

j km

Mj k

m

M

m

M j k km

M

m

M

m

Mπ π π−

=

− −

=

−

=

−

∑ ∑ ∑= = =� �

. (1-144)

Für p q≠ kann man mit

1 12

0

1

0

1 2

Me

Mq q e

jm

Mp q

m

Mm

m

M jp q

Mπ π−

=

−

=

− −

∑ ∑= =� �

, (1-145)

ansetzen. Mit der Summenformel

S qq

qqn

mn

m

n

= = −−

≠+

=∑ 1

11

1

0

, (1-146)

der geometrischen Reihe erhält man weiter:

∀ ∈ − ≠ = −

−

−

−p q M p q SM

e

en

jp q

MM

jp q

M

, { , , , }0 1 11 1

1

2

2�

π

π . (1-147)

- 27 - Dr. Jörg Wollnack

Da e j2 1π = ist, erhält man wegen der Periodizität e ej u ju+ =2π� � , für die obige Summe

∀ ∈ − ≠ = −

−=−p q M p q S

en

jp q

M

, { , , , }0 1 11 1

1

02

�π

.

Was zu beweisen war.

2.3.2 Diskrete Fourier-Teilsumme

Die diskrete Fourier-Teilsumme ist zu

DF f x f k eM M

j kx

X

k D

( )( ) ( )^=∈∑

20

π

I

, mit

DM M M

M M MI

für geraden Zahlen

{ / , , / } für ungeraden Zahlen ≡

− − ∈− − − ∈

� �{ / , , / }2 2 1

1 2 1 2

�

�� � � � (1-148.1)

und dem diskreten Fourier-Koeffizienten

f kM

f x e xm X

MM m

j kx

X

k Dm

^ ( ) ( ) ,= =∈∑1 2

00

π

I

(1-148.2)

definiert. Die diskrete Fourier-Teilsumme kann zur Interpolation der Zwischenverläufe heran-gezogen werden. An den Stellen xp sind die Funktionswerte DF f xM p( )( ) wegen der

Unitaritätsrelation der erzeugenden Funktionen gleich den Stützstellen f(xp). Wegen derPeriodizität der erzeugenden Funktionen interpoliert die diskrete Fourier-Teilsumme denFunktionsverlauf auch über die Primitivperiode X0 hinaus. Dabei wird allerdingsvorausgesetzt, daß f X0-periodisch ist. Anderenfalls kann man sich die Funktion per Defini-tion als periodisch fortgesetzt vorstellen oder aber den Wertevorrat vom m auf {0,1,...,M-1}beschränken.

Diese symmetrische Darstellung der diskreten Fourier-Teilsumme kann wegen derPeriodizität der Terme in eine unsymmetrische Form überführt werden. Diese gleichwertigenDarstellungsformen haben jeweils spezifische Vor- und Nachteile. Bei der symmetrischenForm läßt sich einfacher der Zusammenhang zur reellen Darstellung herstellen und es könnenhier einfacher Symmetriebeziehungen zwischen den diskreten Fourier-Koeffizienten erkanntund beschrieben werden. Die unsymmetrische Form benötigt keine Fallunterscheidunghinsichtlich gerader und ungerader Anzahl von Proben M. Mit ihr läßt sich auch das Prinzipder FFT klarer entwickeln. Aus diesem Grunde wird diese Darstellung im Zusammenhang mitalgorithmischen Beschreibungen bevorzugt.

2.3.3 Diskrete Fourier-Transformation in reeller Darstellung

Die komplexe Darstellung der diskreten Fourier-Reihe kann über die Euleridentität in einenach Sinus- und Cosinustermen geordnete Darstellung überführt werden. Hierzu geht manvon

DF f x f f k e f M eM M M

j kx

X

k M MM

jM x

X( )( ) ( ) ( ) ( / )^ ^

{ / , , / }\

^= + + −∈ − + −

−

∑0 22

2 1 2 1 0

220 0

π π

�

,

M ∈ geraden Zahlen (1-149)

aus und ordnet dies unter Anwendung der Euleridentität zu:

- 28 - Dr. Jörg Wollnack

DF f x f f MM x

Xj

M x

XM M M( )( ) ( ) ( / ) cos sin^ ^= + −���

� −

���

�

���

�

0 2 22

220 0

π π

+ + −���

�=

−

∑ f k f k kx

XM Mk

M^ ^

/

( ) ( ) cos� � 201

2 1

π

+ − −���

�=

−

∑ f k f k kx

XM Mk

M^ ^

/

( ) ( ) sin� � 201

2 1

π . (1-150)

Da für reelle Funktionen f f k f kM M^ ^*( ) ( )− = ist, erhält man weiter:

DF f x f f MM x

Xj

M x

XM M M( )( ) ( ) ( / ) cos sin^ ^= + −���

� −

���

�

���

�

0 2 22

220 0

π π

+���

�=

−

∑2 201

2 1

Re ( ) cos^/

f k kx

XMk

M

� � π

−���

�=

−

∑2 201

2 1

Im ( ) sin^/

f k kx

XMk

M

� � π . (1-151)

Betrachtet man den Term f MM x

Xj

M x

XM^ ( / ) cos sin−

���

� −

���

�

���

�

2 22

220 0

π π an den Interpola-

tionspunkten9, so erhält man dort die Werte f MM

m^ ( / )− −2 1� � , so daß man diesen per

Definition durch f MM x

XM^ ( / ) cos−

���

�2 2

2 0

π ersetzen kann. Man eliminiert hierdurch den

komplexen Anteil. Für ungerade M ist dies ohne Bedeutung, jedoch für gerade M erhält manzwischen den Interpolationspunkten komplexe Werte, obwohl die zu approximierendeFunktion rein reell war. Für die praktische Verwendung ist dies jedoch kein Problem, da manlediglich den Realteil der Fourier-Teilsumme zu nehmen braucht.

Wegen der Periodizitätseigenschaft ∀ ∈ − = − + =M f M f M M f MM M M�^ ^ ^( / ) ( / ) ( )2 2 der

diskreten Fourier-Koeffizienten erhält man diskrete Fourier-Transformation in reeller Dar-stellung zu:

DF f x a a MM x

XM M M( )( ) ( ) ( / ) cos^ ^= +���

�0 2 2

2 0

π

+���

� +

���

�=

−

∑ a k kx

Xb k k

x

XMk

M

M^

/^( ) cos ( ) sin2 2

01

2 1

0

π π , mit

a k f kM

f x km

MM M mm

M^ ^( ) Re ( ) ( ) cos= = �

���=

−

∑� � 12

0

1

π ,

b k f kM

f x km

MM M mm

M^ ^( ) Im ( ) ( ) sin=− = �

���=

−

∑� � 12

0

1

π und

f x M( ) ,∈ ∈� � . (1-152)

9 Damit wird der Funktionsverlauf zwischen den Interpolationsstellen ungleich ausfallen.

- 29 - Dr. Jörg Wollnack

2.3.4 Diskrete zyklische Faltung und Korrelationen

a) Faltung

Die diskrete zyklische Faltung M-periodischer10 Funktionen entsteht aus der kontinuierlichenzyklischen Faltung (1-83) durch Anwendung der Rechteckregel (1-102):

D f g xM

f xk X

Mg

k X

Mk

m

* ( )� � = −���

�

���

�=

∑1 0

0

0 . (1-153)

Um die Kommutativität von f und g zu gewährleisten, berechnet man die Faltung nur an den

Stellen xm X

Mm = 0 , womit man

D f g xM

fm X

M

k X

Mg

k X

Mmk

m

* ( )� � = −���

�

���

�=

∑1 0 0

0

0

= −=∑1

0Mf x g xm k

k

m

k� � � � (1-154)

erhält. Die Kommutativität der diskreten Faltung läßt sich beweisen, indem von derGleichung

D g f xM

g x f xm m kk

m

k* ( )� � � � � �= −=∑1

0

(1-155)

durch Transformation der Summationsindizes ′ = − ⇒ = − ′k m k k m k auf die Gleichung

D g f xM

g x f xm m m kk m

m k* ( ) ( )� � � � � �= − − ′′ =

− ′∑1 0

= ′′=

− ′∑1 0

Mg x f xk

k mm k� � � � (1-156)

schließt. Wegen der Kommutativität der Summation und des komplexen Produkts erhält man:

D g f x D f g xm m* ( ) * ( )� � � �= . (1-157)

Der diskrete Fourier-Koeffizient der Faltung berechnet sich zu:

D g f kM M

f x g x eM m p p

p

j km

M

m

* ( ) ( ) ( )^� � =

���

�−

−

∑∑1 1 2π . (1-158)

Da e e ej k

m p

Mj k

p

Mj k

m

M− −

=2 2 2π π π

ist, erhält man mit dem großen Umordnungssatz:

D g f kM

f x g x e eM m p p

m

j km p

Mj k

p

M

p

* ( ) ( ) ( )^� � = −

− − −

∑∑12

2 2π π

=−

−

− −

∑∑1 12 2

Mg x e

Mf x ep

j kp

Mm p

m

j km p

M

p

( ) ( )π π

. (1-159)

Wegen der Periodizität stellt der innere rechte Summenterm den diskreten Fourier-Koef-fizienten f kM

^ ( ) dar, so daß gilt:

10 M-periodisch und X0-periodisch sind in diesem Zusammenhang synonym.

- 30 - Dr. Jörg Wollnack

D g f k f kM

g x eM M p

j kp

M

p

* ( ) ( ) ( )^ ^� � =

−

∑1 2π . (1-160)

Der verbleibende Summenterm stellt den diskreten Fourier-Koeffizienten g kM^ ( ) dar, so daß

man die Gleichung

D g f k f k g kM M M* ( ) ( ) ( )^ ^ ^� � = (1-161)

erhält. Die diskrete zyklische Faltung M-periodischer Funktionen f und g geht im Transforma-tionsbereich der diskreten Fourier-Transformation in eine Multiplikation der diskretenFourier-Koeffizienten über. Um die Überlegungen zu vervollständigen, mußte man zeigen,daß die Bedingung der Beschränktheit der Werte von f und g hinreichend dafür ist, daß( * )f g beschränkt ist, um dann mit dem Bijektivitätssatz der diskreten Fourier-Trans-formation den Sinn der Gleichung zu sichern. Dies ist für endliche Summen nichtproblematisch.

a) Kreuzkorrelation

Die diskrete zyklische Kreuzkorrelation erhält man analog zu:

D g f x f x g xm m k kk

M

�� �( ) ( ) ( )*= +=

−

∑0

1

, mit x mX

Mm = 0 . (1-162)

Geht man analog zum Faltungssatz vor, so erhält man für den diskreten Fourier-Koeffizientender diskreten zyklischen Kreuzkorrelation die Gleichung:

D f g k f k g kM M M�� �^ ^ ^*( ) ( ) ( )= . (1-163)

Für die zyklische Kreuzkorrelation zweier M-periodischer Funktionen f und g gelten zu-sammenfassend folgende Eigenschaften:

• Antikommutativität D f u g u x D g u f u xm m( ) ( ) ( ) ( ) ( ) ( )*

� �� � � �= − (1-164)

• Periodizitätsrelation D f u g u x f u g u xm m M( ) ( ) ( ) ( ) ( ) ( )� �� � � �= + (1-165)

• Fourier-Koeffizient f u g u k f k g kM M M( ) ( ) ( ) ( ) ( )^ ^ ^

�� � = (1-166)

b) Autokorrelation

Die Autokorrelation geht aus der Kreuzkorrelation für f = g hervor.

2.3.5 Diskrete Parsevalsche Gleichung

Die diskrete Fourier-Reihe der diskreten zyklischen Autokorrelation

DF f x f k f k eM M M

j kx

X

k D

( )( ) ( ) ( )^ ^*=∈∑

20

π

I

(1-167)

nimmt wegen ihrer Interpolationseigenschaft an den Stellen xm die Werte der diskretenzyklischen Korrelation an, so daß die Gleichung

1

0

12

Mf x f x f k f k em k k

k

M

M Mj k m

k D

( ) ( ) ( ) ( )* ^ ^*+

=

−

∈∑ ∑= π

I

(1-168)

- 31 - Dr. Jörg Wollnack

gilt. An der Stelle m = 0 ergibt sich die diskrete Parsevalsche oder Vollständigkeitsrelationzu:

1

0

1

Mf x f x f k f km k k

k

M

M Mk D

( ) ( ) ( ) ( )* ^ ^*+

=

−

∈∑ ∑=

I

. (1-169)

2.3.6 Fast-Fourier-Transform

Die Diskretisierung der Fourier-Reihen führte zur diskreten Fourier-Transformation. DieseForm der Darstellung ist den Gegebenheiten der numerischen Daten- und Signalverarbeitungbesser angepaßt. Jedoch weist die diskrete Fourier-Transformation hinsichtlich ihres Spei-cherplatzbedarfs und der Anzahl der komplexen Multiplikationen ein quadratisches Wachs-tum auf. Bei einer Verdoppelung der Anzahl der Abtastproben wurde sich somit dertechnische Aufwand vervierfachen. Dies hätte relativ lange Rechenzeiten zur Folge. EineRealzeitdatenverarbeitung (Realtime) im Sinne des Shannonschen Abtasttheorems wäre nurfür entsprechend träge Systeme oder bei geringer Datenzahl möglich. Dies würde den Ein-satzbereich der Fourier-Transformation stark einschränken, wenn nicht ein Verfahren zurVerfügung stünde, welches die Rechenzeiten auf ein angemessenes Maß reduziert.

Dies Verfahren, so erschien es zunächst, ließ auf sich warten, bis schließlich Cooley undTukey 1965 ihren mathematischen Algorithmus veröffentlichten, der als Fast-Fourier-Transform (FFT, Schnelle Fourier-Transformation) bekannt geworden ist. Dieses Verfahrenverkürzt die Rechenzeiten auf eine Zeitspanne die proportional zu M Mlog2 ist. Dieser signi-fikante Anstieg der Verarbeitungsgeschwindigkeit im Zusammenhang mit der rasanten Ent-wicklung der Mikroelektronik hat seitdem viele neue Anwendungs- und Forschungsbereichefür die FFT und erschlossen.

Historische Forschungen legen die Vermutung nahe, daß der breite Einsatz der Datenver-arbeitung einen Nährboden für die erneute Entdeckung und Weiterentwicklung der schnellenTransformationen geschaffen hat. Cooley und Tukey haben in ihrem Artikel “An Algorithmfor the Machine Calculation of Complex Fourier Series“ gewissermaßen das Verfahren zuneuem Leben erweckt [199]. Für das vertiefende Studium der FFT sei auf [144, 200, 201]verwiesen.

2.3.6.1 Die Idee zur schnelle Fourier-Transformation

Für die Entwicklung des FFT-Algorithmus der diskreten Fourier-Transformation (1-142) istes vorteilhaft, die natürlichen Zahlen in einem polyadischen Zahlensystem der Basis B = 2darzustellen. Um den Ideengang durchsichtiger zu gestalten, wird zunächst M = 4 gewählt.Die eineindeutige Abbildung zwischen den Zahlensystemen ist durch

k k10 2

0

1

2

3

00

01

10

11

=

�

�

����

����↔ =

�

�

����

����

11 (1-170)

definiert. Jede polyadische Zahl in der Ziffernschreibweise

11 Der tiefgestellte Index gibt hier die Basis des polyadischen Zahlensystems an

- 32 - Dr. Jörg Wollnack

z z z z zB n m B= − −{ , }� �0 1 (1-171)

läßt sich mit Hilfe des Algorithmus

z B z z Bkk

k m

n

k10 10 10 10 1010 100 1 1= ∈ −

=−∑ , { , , , ( ) }� (1-172)

in das hierzu isomorphe Dezimalsystem überführen. Nutzt man diesen Sachverhalt, so lassensich k und m durch die Notation12

k k k= +2 1 0 und m m m= +2 1 0 , mit k k m m0 1 0 1 0 1, , , { , }∈ (1-173)

darstellen. Damit erhält man für den diskreten Fourier-Koeffizienten auch:

x k k x m m W k k m m

mm

( , ) ( , )1 0 0 1 02 2

0

1

0

11 0 1 0

10

= + +

==∑∑ � �� � , mit

ej

M=− 2π

, k k m m0 1 0 1 0 1, , , { , }∈ . (1-174)

Die Haupteigenschaft W Wa b a b+ = der Potenzfunktion nutzend, ergibt sich für den Twiddle-Faktor:

W W W W Wm m k k k m k m k m k m k m k m k m k m2 2 4 2 2 4 2 21 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0+ + + + += =� �� � � � . (1-175)

Wegen der Eigenschaften des Twiddle-Faktors gelten die Beziehungen:

W W ek m k mj

4 42

41 11 1= ∧ =

−� �

π

= ∧ =− −e ej k m j2 21 11π π� �

= =1 11 1k m . (1-176)

Damit läßt sich die diskrete Fourier-Transformation wie folgt notieren:

x k k x m m W Wm k

m

m k k

m

( , ) ( , )1 0 0 1 02

0

12

0

10 1

1

1 0 0

0

=���

�=

+

=∑∑ � � . (1-177)

Diese Beziehung bildet die Basis des FFT-Algorithmus. Beachtet man, daß m m0 1 0 1, { , }∈ ist,so kann man sämtliche Kombinationen (ohne Wiederholung) des inneren Terms

x m k x m m W m k

m1 0 0 0 1 0

2

0

10 1

1

( , ) ( , )==∑ in der Matrizenschreibweise wie folgt darstellen:

x

x

x

x

W

W

W

W

x

x

x

x

1

1

1

1

0

0

2

2

0

0

0

0

0 0

0 1

1 0

11

1 0 0

0 1 0

1 0 0

0 1 0

0 0

0 1

1 0

11

( , )

( , )

( , )

( , )

( , )

( , )

( , )

( , )

�

�

����

����=

�

�

����

����⋅

�

�

����

����

. (1-178)

Geht man analog für die äußere Summe x k k x m k W m k k

m2 0 1 1 0 0

2

0

11 0 0

0

( , ) ( , )= +

=∑ � � vor, so erhält

man in der Matrizenschreibweise für alle Paare k k0 1,� �:

12 Konsequenterweise mußte man mit der Basis B = 2 indizieren. Zur Vereinfachung der Schreibweise wirdhierauf verzichtet.

- 33 - Dr. Jörg Wollnack

x

x

x

x

W

W

W

W

x

x

x

x

2

2

2

2

0

2

1

3

1

1

1

1

0 0

0 1

1 0

11

1 0 0

1 0 0

0 0 1

0 0 1

0 0

0 1

1 0

11

( , )

( , )

( , )

( , )

( , )

( , )

( , )

( , )

�

�

����

����=

�

�

����

����⋅

�

�

����

����

. (1-179)

Betrachtet man dieses Ergebnis, so erkennt man, daß verglichen mit dem ursprünglichenBerechnungsverfahren die Bit-Umkehrreihenfolge bei der Berechnung vonx k k x k k( , ) ( , )1 0 2 0 1= auftritt. Zusammenfassend kann man somit für M = 4 notieren:

x x m k x m m W m k

m0 1 0 0 0 1 0

2

0

1

00

01

10

11

0 1

1

�

�

����

����→ =

=∑( , ) ( , )

x x k k x m k W m k k

m1 2 0 1 1 0 0

2

0

1

00

01

10

11

1 0 0

0

�

�

����

����→ = +

=∑( , ) ( , ) � �

x k k x k k( , ) ( , )1 0 2 0 1= . (1-180)

Diese Überlegungen stellen die Grundlage für die Entwicklung des Cooley Tukey Algo-rithmus dar, der in seiner allgemeinen Form weniger durchsichtig ist.

2.3.6.2 Vorüberlegungen zum Cooley Tukey Algorithmus

Die im vorherigen Kapitel vollzogenen Überlegungen führen in allgemeiner Form zumCooley Tukey Algorithmus. Hierbei wird die Anzahl der Stützstellen M wegen der Basis B =2 des Dualzahlensystems durch die Gleichung

M = ∈2δ δ, � (1-181)

eingeschränkt. Hiermit wird sichergestellt, daß die Dezimalzahlen mit einer endlichen Anzahlvon Dualziffern dargestellt werden können. Damit lassen sich die Indizes m und keineindeutig durch endliche Polyadische Zahlen

m m m m mnn

n

= ≡=

−

−∑20

1

1 1 0

δ

δ �� � und k k k k kll

l

= ≡=

−

−∑20

1

1 1 0

δ

δ �� � (1-182)

darstellen. Nutzt man diesen Sachverhalt, so kann man die diskrete Fourier-Transformationdurch die Gleichung

x k k k( )2 211 1 0

δδ

−− + + + =�

� �x m m m W p

mmm0

11 1 0

0

1

0

1

0

1

2 2110

( )δδ

δ

−−

===

+ + +−

∑∑∑ , mit

p k k k m m m= + + + + + +−−

−−2 2 2 21

1 1 01

1 1 0δ

δδ

δ� �� �� � (1-183)

beschreiben. Betrachtet man das Produkt für p, so kann man dies sukzessive abbauen:

Für den 1. Term gilt:

- 34 - Dr. Jörg Wollnack

p k k k m11

1 1 01

12 2 2= + + +−−

−−

δδ

δδ�� �

= + + + + +−− −

− +− − −

−−2 2 2 2 2 2 2 22

1 11

10

1 11

0 1δ δ

δ δδ δ

δ δδ

δδ

δk m k m k m k mii� �

� �� � (1-184)

Die Haupteigenschaft der Exponentialfunktion nutzend gilt:

W W W e W ea b a bj

M

j

= ∧ = ⇒ = =+ − −22 2

22 2

2 1δπ δ π δ

δ . (1-185)

Damit erhält man ∀ ∈ +i { , , }1 1� δ die Identitätsaussagei

ik m2 2 11 1

δ δδ δ

− +− − =

� �� � , (1-186)

so daß man weiter

Wp k m11

0 12=−

−δ

δ� �

(1-187)

erhält.

Der 2., 3. und weitere Terme des Produkts (1-183) lassen sich analog bearbeiten. Für den j-tenTerm erhält man die Gleichung:

p k k k mjj

j= + + +−−

−−2 2 21

1 1 0δ

δδ

δ�� �= + + + +− +

− −− +

− −−

−2 2 2 2 2 211 0

δ δδ δ

δ δδ δ

δδ

jj

i ji j

jjk m k m k m� � � �� �� � . (1-188)

Für alle i, die die Bedingung δ − + ≥( )j i 0 genügen, ist j i2 2 1

δ δ− +

=� �

, so daß sich die Termemit i j> −δ bzw. für i j∈ − +{ , , }δ δ1 � aufheben. Infolgedessen kann pj zu

p k k k k mjj

jj

jj

j≡ + + + + +−−

− −− −

− − +− − +

−−2 2 2 21

11

1 0δ

δδ δ

δ δδ δ

δ δδ

δ� �� �

� �� �

� �� �� �≡ −

−= −∑2 2

1

0δ

δj

jl

ll j

m k 13 (1-189)

vereinfacht werden. Diese Summe ist für alle j ∈ { , , }1� δ identisch mit q, da∀ ∈i m ki i, { , }0 1 ist und die Twiddle-Faktoren identisch gleich 1 sind. Damit gilt:

W Wqq

q

i

ii i=∑

==

���

�

=∏1

1

δδ

=∑−

−= −

=∏W

ii

ll

l i

m k

i

2 2

1

1

0δ

δδ � � . (1-190)

Für den diskreten Fourier-Koeffizienten erhält man sodann:

x k k k( )2 211 1 0

δδ

−− + + + =�

� �x m m m Wi

il

ll i

m k

immm0

11 1 0

2 2

10

1

0

1

0

1

2 2 1

0

110

( )δδ

δ δδ

δ

−−

====

+ + +∑−

−= −

−

∏∑∑∑� �

. (1-191)

bzw.

13 Der Äquivalenzbegriff wird benutzt, weil die Aussagen ungleich sind und erst im Zusammenhang mit p j

liegt die Identität vor.

- 35 - Dr. Jörg Wollnack

x k k k( )2 211 1 0

δδ

−− + + + =�

� � � �x m m m W Wmmmm

m k m k k

j

01

1 1 00

1

0

1

0

1

0

12 2 2

2 2110

11 0

22 1 0( )δ

δδ

δδ

δδ−

−====

++ + +� ���

� ���

� ���

� ��� −

−−

−−∑∑∑∑ � � � �� �! !

� �� �

W Wj

jj

jm k k k m k k k2 2 2 2 211 1 0 0

11 1 0

δδ

δδ

−−

−−

−−+ + + + + +���

���� �� � � �! . (1-192)

Durch Einführung von Hilfsgrößen kann man die verknüpften δ - Summationen auf einenSatz von δ - Einzelsummen zurückführen. Damit erhält man für den diskreten Fourier-Koeffi-zienten:

x k m m x m m m Wm

m k

1 0 2 0 01

1 1 00

12

2 21

11 0( , , , ) ( )δ

δδ

δ

δδ

−−

−=

= + + +−

−−∑� �

def � �

x k k m m x k m m Wm

m k k

2 0 1 3 0 2 0 2 00

12 2

2

22 1 0( , , , , ) ( , , , )δ δ

δ

δδ

− −=

+=−

−−∑� �

def � �� �

�

x k k m m x k k m m Wi i i i i im

m k k kii

ii

+ − + + −=

+ + +=

−

− +− +∑1 0 1 0 0 1 0

0

12 2 2

2

11 1 0( , , , , , ) ( , , , , , )� � � �

�

δ δδ

δδ

� �� �� �� �

� �def

�

x k k x k k m Wm

m k k k

δ δ δ δ

δδ( , , ) ( , , , )0 1 1 0 2 0

0

12 2

0

01

1 1 0� �

�

− − −=

+ + += ∑−

−def � �

x k k x k k( , , ) ( , , )δ δ δ− −=1 0 0 1� � . (1-193)

Für die Herleitung des Cooley Tukey Algorithmus, der zudem eine effiziente Nutzung desDatenspeichers verwirklicht, nutzt man die Interpolationseigenschaft der diskrete Fourier-Teilsumme aus. Hierbei tritt ebenfalls die Bit-Umkehrfunktion zu Tage. Hierdurch können dieberechneten Zwischenwerte in nicht mehr benötigten Datenspeichern abgelegt werden. DieseIn-Place-Operationen führen dazu, daß man über den Speicherplatzbedarf der Daten hinaus,keinen zusätzlichen Speicher benötigt.

Aufgrund des engen Zusammenhanges zwischen der diskreten Fourier-Transformation undihrer inversen Transformation kann der gleiche Algorithmus bei der inversen Transformationeingesetzt werden. Lediglich die Twiddle-Faktoren zwischen der Vorwärts- und Rückwärts-transformation sind konjugiert komplex zueinander: z zmk mk

F R= * . Der Faktor 1/M der Rück-transformation wird im allgemeinen dem Twiddle-Faktor zugeordnet.

- 36 - Dr. Jörg Wollnack

2.3.6.3 Cooley Tukey C++-Algorithmus

Der folgende Cooley Tukey Algorithmus wurde in C++ als Template codiert. Das Daten-objekt Vektor<T> repräsentiert eine Vektorklasse, die analog zu den Matlab-Konventionenaufgebaut ist. Dieses Datenobjekt ist als referiertes Objekt codiert, um bei großen Daten-mengen lediglich die Adressen zu übergeben, was zu schnellen Algorithmen führt. DerDatentyp T ist mit Complex anzulegen. Hierunter verbirgt sich eine Klassenimplementationder komplexen Zahlen. Auf eine detaillierte Darstellung dieser Klassen wird verzichtet.

Für die Berechnung der Einheitswurzeln und FFT sollte folgendes beachtet werden:

Bedingt durch die endlichen polyadischen Rechnerzahlen

z zB kk

k N

M

10 1010 10==−∑ , , M N B M N≠ ∈, , , � (1-194)

wird z.B. bei der Fixpunktdarstellung (M = 0)

z zEXP kk

k N10 10

0

10 10, ,Q ==−∑ (1-195)

ein maximaler absoluter Fehler

∆ ≤ −10EXP N (1-196)

gegenüber der infiniten Darstellung

z zEXP kk

k10 10

0

10 10R ==−∞∑ , (1-197)

auftreten können. Bei einfacher Genauigkeit ist N ≈ 7 und bei doppelter Genauigkeit istN ≈ 16.

Die Transzendenz von π und e j x impliziert bei der finiten Darstellung Fehler von prin-zipieller Natur in der o.g. Größenordnung. Die rekursive Berechnung der Einheitswurzelnführt für große M zu einer Fehlerakkumulation. Aus diesem Grunde kann eine Genauigkeits-steigerung allein durch eine doppelt genaue Berechnung der Einheitswurzeln erreicht werden.

Die Berechnung der komplexen Produkte auf der Maschinenebene wird auf die Gleichung

a jb c jd ac bd j bc ad+ + = − + +� �� � � � (1-198)

zurückgeführt. Die hierbei zu bildende Differenz ac bd− ist bezüglich der relativen Fehler-fortpflanzung im Falle annähernder Gleichheit der Produkte a c und b d im besonderen Maßefür Fehler empfindlich. Die kleinste Differenz ohne null ist bei der Maschinenzahlz EXP N

Q = −10 . Analoge Überlegungen gelten für weitere elementare algebraische

Operationen.

- 37 - Dr. Jörg Wollnack

C++-FFT-Programm:/*-------------------------------------------------------------------*/template <class T> int fft1d(Vektor<T>& d, char ir)/*-------------------------------------------------------------------*//*--------------------------------------------------------------------

Dieses Programm bestimmt mit der schnellen Fourier-Transformation(FFT1D) zu m=2**tau gegebenen reellen oder komplexen Funktionswerten

d[0],....,d[m-1]die diskreten Fourier-Koeffizienten

d^[-m/2],.....,d^[m/2-1]der zugehörigen Fourier-Teilsumme oder führt die Umkehrtransformationdurch.

Parameter:

d - Vektorklasse enthält die zu transformierenden Daten

ir='f' - Bestimmung der diskreten Fourier-Koeffizienten:

Das komplexe Feldd

wird mit den Funktionswerten belegt übergeben und ist nach Ablauf des Programms mit den diskreten Fourier-Koeffizienten in folgender Weise überspeichert:

d^[k]=d[k+m] , k=-m/2,..., -1 d^[k]=d[k] , k= 0,...,m/2-1

ir='r' - Das komplexe Feld d wird mit den Fourier-Koeffizienten in folgender Weise belegt

d[k]=d^[k] , k=0 ,...,m/2-1 d[k]=d^[k-m] , k=m/2,.. ,m-1

übergeben und ist nach Ausführung des Programms mit den Funktionswerten überspeichert.

----------------------------------------------------------------------*/

{ T ew, /* Einheitswurzel */ w, /* Twiddelfaktor */ eps, /* */ u; /* Hilfsspeicher */

int iErrNr,tau,j,k,l,m,mm,n,n2,sigma;

long double x,pi;

m = d.DimV(); /* Ordnung des Datenvektors */ pi = acosl(-1.0); /* Kreiszahl Pi */ x = (long double)1.0/(long double)m; /* Normierungsfaktor */ tau = tauFxT(&iErrNr,m);

- 38 - Dr. Jörg Wollnack

/* Berechnung der Einheitswurzel */

ew = exp(T(0.0,-(long double)2.0*pi*x));

switch(ir) { case 'r': /* Für Rückwärtstransformation Maßstabsfaktor anpassen */ /* und Einheitswurzel konjugieren */

x = (long double)1.0; ew = conj(ew);

case 'f': /* FFT-Transformation ausführen */

for(j=0;j<=m-1;j++) /* Umspeicherung mit der Bitumkehrfunktion */ {

k =j; sigma=0; n2 =m/2; n =1;

for(l=0;l<=tau-1;l++) { if(k>=n2) { sigma+=n; k -=n2; } n +=n; n2 /=2; }

if(sigma>=j) { u = d[j]*x; d[j] = d[sigma]*x; d[sigma] = u; } }

- 39 - Dr. Jörg Wollnack

/* Durchführung der Transformation

mm = 2**(n-1) ew = Einheitswurzel w = ew**(2**tau-n)) eps = ew**(l*2**)tau-n)) */

mm=1;

for(n=1;n<=tau;n++) /* FFT - Transformation ausführen */ { w = ew; if(!(n==tau)) { for(k=1;k<=tau-n;k++) { w = w*w; } } eps = T(1.0,0);

for(l=0;l<=mm-1;l++) { for(j=0;j<=m-mm-mm;j+=(mm+mm)) { u = d[j+l+mm] * eps; d[j+l+mm] = d[j+l] - u; d[j+l] += u; } eps = eps*w; } mm+=mm; }

break;

default: return(-2);

} /* end of switch */

return(0);} /* end of fft1d */

/*-------------------------------------------------------------------*/

- 40 - Dr. Jörg Wollnack

/* Durchführung der Transformation

mm = 2**(n-1) ew = Einheitswurzel w = ew**(2**tau-n)) eps = ew**(l*2**)tau-n)) */

mm=1;

for(n=1;n<=tau;n++) /* FFT - Transformation ausführen */ { rw=rew; iw=iew;

if(!(n==tau)) { for(k=1;k<=tau-n;k++) { rwt = rw*rw - iw*iw; iw = rw*iw + rw*iw; rw = rwt;

} } reps=1.0; ieps=0.0;

for(l=0;l<=mm-1;l++) { for(j=0;j<=m-mm-mm;j+=(mm+mm)) { ru = rd[j+l+mm]*reps - id[j+l+mm]*ieps, iu = rd[j+l+mm]*ieps + id[j+l+mm]*reps;

rd[j+l+mm] = rd[j+l] - ru; id[j+l+mm] = id[j+l] - iu;

rd[j+l] += ru; id[j+l] += iu; } repst = reps*rw - ieps*iw, ieps = reps*iw + ieps*rw; reps = repst; } mm+=mm; }

break;

default:

printf("Falsche Parameterübergabe FFT1D");

} /* end of switch */

- 41 - Dr. Jörg Wollnack

} /* end of fft1d */

/*-------------------------------------------------------------------*/

/*-------------------------------------------------------------------*/

int power2(int n)

/* Potenzfunktion der Basis 2 y = 2**n , für n Element der natürlichen Zahlen*/

{ if(n>0) { return(2*power2(n-1)); } return(1);} /* end of power2(.) */

/*-------------------------------------------------------------------*/

- 1 - Dr. Jörg Wollnack

3 Höherdimensionale Räume (Schwerpunkt auf 2D)

In den Natur- und Ingenieurwissenschaften werden zur Verschreibung des Systemverhaltensmehrdimensionale Abbildungen der Art

f x y f xf f: ( ) , ,∈ ⊆ → = ∈ ⊆ ∈D W M NM N� � � (3-1)

benötigt. Da man die Vektorabbildung f elementweise betrachten kann, ist das Studium derAbbildungen

f D y f WfM

f: ( )x x∈ ⊆ → = ∈ ⊆� � (3-2)

zunächst ausreichend. Es werden hierbei von vornherein komplexe Abbilder betrachtet, weildie reellen Abbilder ein Spezialfall dieser darstellen. Für physikalisch reale Lösungen sind diereellen Formen zuständig.

An dem zweidimensionalen Fall, der insbesondere auch für die Bildverarbeitung von Be-deutung ist, lassen sich die wesentlichen Eigenschaften dieser Ansätze darstellen.

3.1 Die zweidimensionale allgemeine komplexe Fourier-Reihe

Zur Entwicklung der zweidimensionalen allgemeinen komplexen Fourier-Reihe beschreibtman den Abstand zwischen der Funktion und ihrer Reihenentwicklung analog zu:

F f x y a k l g x y f x y a k l g x y x yC k lk l D

k lk l DD I I

= −���

���

−���

���∈ ∈

∑ ∑�� ( , ) ( , ) ( , ) ( , ) ( , ) ( , ), ,

*

� � d d

R

, mit

D x x y y x x y yR ≡ × ⊆ > ∧ >[ , ] [ , ] ,1 2 1 22

2 1 2 1� und D K LI ≡ × ⊆{ , , } { , , }1 1 2

� � � . (3-3)

Das erzeugende unitäre zweidimensionale System erfülle die Unitaritätsrelation:

′ ≡ ∈ = ∈�� �

�����

��S d dR

g x y g x y g x y x y k l Dk l pr q s

D

pq r s I( , ) ( , ) ( , ) , ( , )*� δ δ , mit

D D D D Df g g g gk l⊆ ≡ ∩ ∩ ∩ ∩

11 12� � . (3-4)

Hieraus erhält man analog zum eindimensionalen Fall durch Auflösung des Produkts:

F f x y f x y f x y a k l g x y f x y a k l g x yC k lk l DD

k lk l DI I

= −���

−∈ ∈

∑�� ∑( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , )* * *

,

*

,� � R

+���

������

������∈ ∈

∑ ∑a k l g x y a r s g x y x yk lk l D

r sr s DI I

( , ) ( , ) ( , ) ( , ), ,� �

d d . (3-5)

Mit dem Superpositionssatz der Gebietsintegrale und wegen der Kommutativität von Inte-gration und Summation erhält man auch:

- 2 - Dr. Jörg Wollnack

F f x y f x y x yC

D

= �� ( , ) ( , )* d dR

− −∈ ∈

∑ �� ��∑a k l f x y g x y x y a k l f x y g x y x yk l D

k l

D

k l

Dk l DI I

*

,

* *

,

( , ) ( , ) ( , ) ( , ) ( , ) ( , )� � � �

d d d dR R

a k l a r s g x y g x y x yk l r s

Dk l r s D DI I

* *

, , ,

( , ) ( , ) ( , ) ( , ) d dR

��∑∈ ×� �

. (3-6)

Führt man zur Vereinfachung den Koeffizienten

C k l f x y g x y x yk l

D

( , ) ( , ) ( , )*= ��def

d dR

(3-7)

ein, so erhält man weiter

F f x y f x y x yC

D

= �� ( , ) ( , )* d dR

− − +∈ ∈ ∈

∑ ∑ ∑a k l C k l a k l C k l a k l a k lk l D k l D k l DI I I

*

,

*

,

*

,

( , ) ( , ) ( , ) ( , ) ( , ) ( , )� � � � � �

(3-8)

bzw. analog zum eindimensionalen Fall:

F f x y f x y x yC

D

= �� ( , ) ( , )* d dR

+ − − −∈ ∈

∑ ∑a k l C k l a k l C k l C k l C k lk l D k l DI I

( , ) ( , ) ( , ) ( , ) ( , ) ( , )*

,

*

,

� �� �� � � �

. (3-9)

Die rechte Seite dieser Gleichung ist genau dann minimal, wenn man

∀ ∈ =( , ) ( , ) ( , )k l D a k l C k lI (3-10)

wählt, so daß dann

F f x y f x y x y C k l C k lC

D k l DI

= −�� ∑∈

( , ) ( , ) ( , ) ( , )* *

,

d dR

� �(3-11)

gilt. Der positiven Definitheit des Fehlerbegriffs (FC ≥ 0) folgend, gilt dann ferner die zwei-dimensionale Besselsche Ungleichung

C k l C k l f x y f x y x yk l D DI

( , ) ( , ) ( , ) ( , )*

,

*

� �∈∑ ��≤ d d

R

, (3-12)

aus der sich die zweidimensionale Parsevalsche oder zweidimensionale Vollständigkeits-relation zu (K L→ ∞ → ∞, )

C k l C k l f x y f x y x yk l D

( , ) ( , ) ( , ) ( , )*

,

*

� �∈∑ ��=

�2

d dR

(3-13)

ergibt. Diese Bedingung ist ebenfalls hinreichend und notwendig für die Vollständigkeit deserzeugenden Systems.

Die Abschätzung (3-12) ist auch im höherdimensionalen Fall hilfreich, da man mit ihr dieKonvergenz der allgemeinen Fourier-Reihe für K L→ ∞ → ∞, aus der Existenz des

- 3 - Dr. Jörg Wollnack

Integrals f x y f x y x yD

( , ) ( , )* d dR

�� < ∞ ableiten kann. Funktionen f dieser Klasse werden

ebenfalls als quadratisch Integrabel bezeichnet. Für die Konvergenz der Reihe

C k l C k lk l

( , ) ( , )*

,� �∈∑

�2

ist es notwendig, daß lim ( , ) lim ( , )k l

C k l C k l→∞ →∞

= =2 20 ist. Die Bedingung

der quadratisch Integrabilität sichert den Sinn der vorherigen Aussagen.

Bemerkungen zum Konvergenzbeweis:

Wegen der Dreiecksungleichung der Norm und der Schwarzschen Ungleichung erhält mandie Abschätzung

C k l g x y C k l g x y C k l g x yk lk l D

k lk l D

k lk l DI I I

( , ) ( , ) ( , ) ( , ) ( , ) ( , ), , ,� � � � � �∈ ∈ ∈∑ ∑ ∑≤ =

2

2 2 2 , (3-14)

woraus mit der Beschränktheit

∀ ∈ ∈ ≤ ∈ +( , ) , ( , ) ( , )k l D x y D g x y AI k lR

2 2� (3-15)

der erzeugenden Funktionen folgt:

0

2

2 2≤ ≤∈ ∈

∑ ∑C k l g x y A C k lk lk l D k l DI I

( , ) ( , ) ( , ), ,� � � �

. (3-16)

Mit der Besselschen Ungleichung (3-12) erhält man sodann:

0

2

2 2≤ ≤ < ∞∈

∑ ��C k l g x y A f x y x yk lk l D DI

( , ) ( , ) ( , ),� �

d dR

. (3-17)

Dies sichert die Konvergenz der zweidimensionalen allgemeinen Fourier-Reihe. Diequadratische Integrabilität stellt somit eine hinreichende Bedingung dar.

Damit lassen sich die Sätze formulieren:

Satz 3-1 Fourier-Reihenentwicklung:

Eine Funktion f x y( , ) , die zumindestens im uneigentlichen Sinn qua-dratisch integrabel f x y x y

D

( , )2

d dR

�� , D x x y y x x y yR ≡ × ⊆ > ∧ >[ , ] [ , ] ,1 2 1 22

2 1 2 1�

ist, kann mit dem unitären System erzeugender Funktionen

′ ≡ ∈ = ∈�� �

�����

��SR

g x y g x y g x y k l Dk l pr q s

D

pq r s I( , ) ( , ) ( , ) , ( , )*� δ δ ,

D K LI ≡ × ⊆{ , , } { , , }1 1 2� � �

durch die verallgemeinerte Fourier-Reihe C k l g x yk lk l DI

( , ) ( , ),� �∈∑ und

deren verallgemeinerten Fourier-Koeffizienten

- 4 - Dr. Jörg Wollnack

C k l f x y g x y x yk l

D

( , ) ( , ) ( , )*= �� d dR

approximiert werden. Der mittlere quadratische Fehler

F f x y a k l g x y x yk lk l DD I

2

2

~ ( , ) ( , ) ( , ),

−∈

∑��� �

d dR

ist dann minimal und es gilt die Besselsche Ungleichung

C k l C k l f x y f x y x yk l D DI

( , ) ( , ) ( , ) ( , )*

,

*

� �∈∑ ��≤ d d

R

sowie die notwendigen Bedingungen: lim ( , ) lim ( , )

k lC k l C k l

→∞ →∞= = 0 .

Satz 3-2: Vollständigkeitssatz:

Ist das erzeugende System vollständig, so verschwindet das Fehler-maß lim

K LF

→∞ →∞= 0, woraus hinreichend und notwendig die Voll-

ständigkeitsrelation C k l f x yk l D

( , ) ( , ),

2 2

2� �∈∑ ��=

�R

folgt.

Satz 3-3 Bijektivitätssatz1:

Die Transformation zwischen der Originalfunktion f(x,y) und demSatz der Fourier-Koeffizienten C(k,l) ist für vollständige Systemebijektiv.

3.1.1 Separable Kerne

Im vorherigen Kapitel wurden zweidimensionale allgemeine Fourier-Reihen unitärer Systemeeingeführt. Dabei wurde formell die zweidimensionale Unitaritätsrelation definiert. Für diepraktische Verwendung dieses Approximationsansatzes ist es jedoch von Interesse, zu klären,welche bekannten Funktionen dieser Bedingung genügen. Alternativ wäre ein Weg zu suchen,der es ermöglicht, die zweidimensionale Unitaritätsrelation auf die eindimensionale zurückzu-führen. Gelingt diese Reduktion, so lassen sich z.B. die im Kapitel 1.4 dargestellten Funk-tionen als Basis für die Erzeugung zweidimensionaler erzeugender Systeme verwenden.

Geht man von der eindimensionalen Unitaritätsrelation

g x g x xp q

a

b

pq( ) ( )* d� = δ (3-18)

aus und bildet das Produkt

g x g x x g y g y yp q

a

b

r s

a

b

pq r s( ) ( ) ( ) ( )* *d d� � = δ δ , (3-19)

so kann man wegen der hinsichtlich der Integrationsvariablen konstanten Integrationsgrenzendas Produkt zweier Integrale in ein Gebietsintegral überführen:

1 Läßt sich per Widerspruchsbeweis analog zum eindimensionalen Fall beweisen.

- 5 - Dr. Jörg Wollnack

g x g x g y g y xp q r s

a

b

a

b

pq r s( ) ( ) ( ) ( )* * d dy�� = δ δ . (3-20)

Die linke Seite dieser Aussage definiert das gesuchte Konstruktionsprinzip. Damit erschließsich die Klasse der eindimensionalen unitären Funktionen für zweidimensionale Ansätze. DieMenge der zweidimensionalen unitären Erzeugenden lassen sich somit über

′ ≡ ∈ = = ∈�� �

�����

�S dg x y g x y g x g y g u g u u k l Dk l k l k l p q pq I( , ) ( , ) ( ) ( ) , ( ) ( ) , ( , )*� δ (3-21)

konstruieren.

3.1.2 Zweidimensionale trigonometrische Fourier-Transformation in komplexerDarstellung

Eine zweidimensionale Funktion (3-2) (M = 2) ist X0,Y0-periodisch, wenn die Aussage

∀ ∈ ∧ + + ∈ = +

= +

( , ) ( , ) ( , ) ( , )

( , ) ( , )

x y D x X y Y D f x y f x X y

f x y f x y Y

f f0 0 0

0

(3-22)

gilt. Diese Funktionen sind vollständig erklärt, wenn sie in dem Gebiet

G ≡ + × + ∈ ⊆ ∈[ , ] [ , ] , , , ,a a X b b Y D a b X Yf0 02

0 0� � (3-23)

charakterisiert sind.

Das zweidimensionale Riemannsche Gebietsintegral hat eine zum eindimensionalen Fallanaloge Eigenschaft:

f x y x y f x y x y f x y x yX Y b

b Y

a

a X YX

( , ) ( , ) ( , )d d d d d d∩ ×

++

�� �� ��≡ =0 0

00 00

00

. (3-24)

Dies läßt sich durch Transformation der Variablen zusammen mit der Periodizitätseigenschaftvon f beweisen.

Damit läßt sich die zweidimensionale trigonometrische Fourier-Reihe in komplexerDarstellung für X0,Y0-periodische Funktionen beschreiben:

• Erzeugendes System

′ ≡ ∈ ∈ ∈�� �

�����

S1 1

0

2

0

22 2

0 00 0

Xe

Ye k l x y X Y

j kx

Xj l

y

Yπ π

( , ) , ( , ) , ,� � � (3-25.1)

• Fourier-Koeffizient

C k l f x y e x yj k

x

Xl

y

Y

X Y

( , ) ( , )=− +

���

���

∩ ×��

20 0

0 0

πd d (3-25.2)

• Fourier-Teilsumme

F x y C k l ef K L

j kx

Xl

y

Y

k l K L

K L

( , ) ( , ), ( , )

( , )

=+

���

���

= −∑

20 0

π

� �(3-25.3)

• Fourier-Reihe

- 6 - Dr. Jörg Wollnack

F x y C k l ef

j kx

Xl

y

Y

k l

( , ) ( , ), ( , )

( , )

=+

���

���

= −∞ −∞

∞ ∞

∑2

0 0

π

� �(3-25.4)

Ist die komplexe Funktion f nicht periodisch bzw. nicht per Definition periodisch fortgesetzt,so gelten die Aussagen nur auf dem Integrationsgebiet G X Y≡ ×0 0 .

Der Begriff des Kreisfrequenzspektrums wird analog zum eindimensionale Fall alsKreisfrequenztupel

ω =���

���

20 0

π k

X

l

Y,

t

(3-26)

definiert. In analoger Weise definiert man die Betrags- und Phasendarstellung deszweidimensionalen Spektrums zu:

C k l

C k l

C k l C k l

C k l C k l

( , )

arg ( , )

Re ( , ) Im ( , )

arctan Im ( , ) ,Re ( , )� �� � � �� � � �� �

���

���

=+�

���

�

���

2 2

22 . (3-27)

0 .40 .2

00 .2

0 .4

0 .4

0 .2

0

0 .2

0 .4

1

0 .5

0

0 .5

( , )= (1 ,0 )m n

0 .40 .2

00 .2

0 .4

0 .4

0 .2

0

0 .2

0 .4

0 .5

0

0 .5

1

x

yz

( , )= (1 ,1 )m n

0 .40 .2

00 .2

0 .4

0 .4

0 .2

0

0 .2

0 .4

0

0 .5

1

( , )= (2 ,2 )m n

0 .40 .2

00 .2

0 .4

0 .4

0 .2

0

0 .2

0 .4

1

0 .5

0

0 .5

( , )= (2 ,1 )m n

Abb. 3-1: 2D-Fourier-Kerne

- 7 - Dr. Jörg Wollnack

3.1.2.1 Zyklische Faltung und Korrelation

3.1.2.2 Differentiation und Integration

3.2 Die Mehrdimensionale allgemeine komplexe Fourier-Reihe

Der mehrdimensionale Fall läßt sich analog zum eindimensionalen bzw. zweidimensionalenFall diskutieren. Zur Entwicklung der zweidimensionalen allgemeinen komplexen Fourier-Reihe beschreibt man den Abstand zwischen der Funktion und ihrer Reihenentwicklungwieder zu:

F f a g f a gCD DD I I

= −���

���

−���

���∈ ∈

∑ ∑� ( ) ( ) ( ) ( ) ( ) ( )

*

x k x x k x xkk

kk

dR

, mit

x k= ∈ = ⊆x x k kNN

NN

1 1, , , , ,� �� � � �t t� � ,

D a b a b b a b aN NN

N NR ≡ × × ⊆ > ∧ ∧ >[ , ] [ , ] ,1 1 1 1� �� und

D K KI NN≡ × × ⊆{ , , } { , , }1 11� � � � . (3-28)

Das erzeugende unitäre zweidimensionale System erfülle die Unitaritätsrelation:

′ ≡ ∈ = ∈�� �

�����

� ∏=

S dR

g g g DD

p qk

N

Ik kk p qx x x x p q( ) ( ) ( ) , ( , )*� δ δ

1

2 , mit

D Df g⊆ . (3-29)

Hieraus erhält man durch Auflösung des Produkts:

F f f f a g f a gCDDD II

= − −��� ∈∈

∑∑� ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * *x x x k x x k xk kkk

R

+���

������

������∈ ∈

∑ ∑a g a gD DI I

( ) ( ) ( ) ( )p x q x xkp

rq

d . (3-30)

Mit dem Superpositionssatz der Mehrfachintegrale und wegen der Kommutativität von Inte-gration und Summation erhält man auch:

F f f a f g a f gC

D DD DDI I

= − −� �∑ �∑∈ ∈

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * *x x x k x x x k x x xkk

kk

d d dR R R

a a g gDDI

* *

,

( ) ( ) ( ) ( )p q x x xp qp q

dR

�∑∈� 2

. (3-31)

Führt man zur Vereinfachung den Koeffizienten

C f gD

( ) ( ) ( )*k x x xk= �def

dR

(3-32)

ein, so erhält man weiter

F f f a C a C a aC

D D D DI I I

= − − +� ∑ ∑ ∑∈ ∈ ∈

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * *x x x k k k k k kk k k

dR

(3-33)

- 8 - Dr. Jörg Wollnack

bzw. analog zum eindimensionalen Fall:

F f f a C a C C CC

D D DI I

= + − − −� ∑ ∑∈ ∈

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * *x x x k k k k k kk k

dR

� � . (3-34)

Die rechte Seite dieser Gleichung ist genau dann minimal, wenn man

∀ ∈ =k k kD a CI ( ) ( ) (3-35)

wählt, so daß dann

F f f C CC

D DI

= −� ∑∈

( ) ( ) ( ) ( )* *x x x k kk

dR

(3-36)

gilt. Der positiven Definitheit des Fehlerbegriffs (FC ≥ 0) folgend, gilt dann ferner diemehrdimensionale Besselsche Ungleichung

C C f fD DI

( ) ( ) ( ) ( )* *k k x x xk∈∑ �≤ d

R

, (3-37)

aus der sich die mehrdimensionale Parsevalsche oder mehrdimensionale Vollständigkeits-relation zu (K KN1 → ∞ → ∞, ,� )

C C f fD DI

( ) ( ) ( ) ( )* *k k x x xk∈∑ ��= d

R

(3-38)

ergibt. Diese Bedingung ist ebenfalls hinreichend und notwendig für die Vollständigkeit deserzeugenden Systems.

Die Abschätzung (3-12) ist auch im höherdimensionalen Fall hilfreich, da man mit ihr dieKonvergenz der allgemeinen Fourier-Reihe für K KN1 → ∞ → ∞, ,� aus der Existenz des

Integrals f fD

( ) ( )*x x xdR

� < ∞ ableiten kann. Funktionen f dieser Klasse werden ebenfalls als

quadratisch Integrabel bezeichnet. Für die Konvergenz der Reihe C C( ) ( )*k kk∈∑�

2

ist es

notwendig, daß lim ( ) lim ( )k k

C CN1

2 20

→∞ →∞= = =k k� ist. Die Bedingung der quadratisch

Integrabilität sichert den Sinn der vorherigen Aussagen.

Bemerkungen zum Konvergenzbeweis:

Wegen der Dreiecksungleichung der Norm und der Schwarzschen Ungleichung erhält mandie Abschätzung

C g C g C gD D DI I I

( ) ( ) ( ) ( ) ( ) ( )k x k x k xkk

kk

kk∈ ∈ ∈

∑ ∑ ∑≤ =2

2 2 2 , (3-39)

woraus mit der Beschränktheit

∀ ∈ ∈ ≤ ∈ +k x xkD D g AI , ( )R

2 2� (3-40)

der erzeugenden Funktionen folgt:

- 9 - Dr. Jörg Wollnack

0

2

2 2≤ ≤∈ ∈∑ ∑C g A C

D DI I

( ) ( ) ( )k x kkk k

. (3-41)

Mit der Besselschen Ungleichung (3-12) erhält man sodann:

0

2

2 2≤ ≤ < ∞∈∑ �C g A f

D DI

( ) ( ) ( )k x x xkk

dR

. (3-42)

Dies sichert die Konvergenz der mehrdimensionalen allgemeinen Fourier-Reihe. Diequadratische Integrabilität stellt somit eine hinreichende Bedingung dar.

3.3 Unitäre und orthonormale Transformationen

Es ist auch hier analog zum eindimensionalen Fall sinnvoll, zunächst die Unitären Trans-formationen zu betrachten, da die orthonormalen als ein Spezialfall gedeutet werden können.

a) Unitäre Systeme

Geht man von diskreten komplexen Funktionen

∀ ∈ ∃ ∈ → =( , ) ( , ) ( , )m n y m n y f m nmn� �� (3-43)

aus und verwendet das unitäre erzeugende System

′ ≡ ∈ ∈ ×S g m n m n M Nk l ( , ) ( , ) { , , } { , , } ,� 1 1� �� ( , ) { , , } { , , } , ,k l K L K M N L∈ × = ∧ =1 1� �

g m n g m npr q sm n

M N

pq rs( , ) ( , )*

( , ) ( , )

( , )

=∑ =

1 1

δ δ , (3-44)

so ist für die Abstandsbeschreibung zwischen der verallgemeinerten diskreten komplexenFourier-Reihe

g m n C g m nk l k lk l

K L

( , ) ( , )( . ) ( , )

( , )

==∑

1 1

, (3-45)

und dem Funktional f das Betragsquadrat einer komplexen Zahl z z z2 = * im Sinne von

F f m n g m n f m n g m nm n

M N2

1

= − −=

∑ ( , ) ( , ) ( , ) ( , )*

( , )

( , )

� � � � (3-46)

heranzuziehen. Mit der Identitätsaussage

f g f g f g f g− − = − −� � � � � � � �* * * = − − +f f f g f g g g* * * * (3-47)

erhält man sodann:

F f m n f m n f m n g m nm n

M N

m n

M N2

1 1 1 1

= −= =

∑ ∑( , ) ( , ) ( , ) ( , )*

( , ) ( , )

( , )*

( , ) ( , )

( , )

− += =

∑ ∑f m n g m n g m n g m nm n

M N

m n

M N

( , ) ( , ) ( , ) ( , )*

( , ) ( , )

( , )*

( , ) ( , )

( , )

1 1 1 1

. (3-48)

Ersetzt man g(m,n) durch (3-45), so ergibt sich weiter:

- 10 - Dr. Jörg Wollnack

F f m n f m n C g m nm n

M N

k l k lk l

K L

m n

M N2 2

1 1 1 11 1

= −= ==

∑ ∑∑( , ) ( , ) ( , )( , ) ( , )

( , )*

( , ) ( , )

( , )

( , ) ( , )

( , )

−==∑∑ f m n C g m nk l k l

k l

K L

m n

M N

( , ) ( , )* *

( , ) ( , )

( , )

( , ) ( , )

( , )

1 11 1

+= ==

∑ ∑∑ C g m n C g m nk l k lk l

K L

r s r sr s

K L

m n

M N

( , ) ( , )( , ) ( , )

( , )* *

( , ) ( , )

( , )

( , ) ( , )

( , )

1 1 1 11 1

. (3-49)

Nach dem großen Umordnungssatz der Summen gilt ferner:

F f m n C f m n g m nm n

M N

k l k lm n

M n

k l

K L2 2

1 1 1 11 1

= −= ==

∑ ∑∑( , ) ( , ) ( , )( , ) ( , )

( , )*

( , ) ( , )

( , )

( . ) ( , )

( , )

−==

∑∑ C f m n g m nk l k lm n

M N

k l

K L* *

( , ) ( , )

( , )

( , ) ( , )

( , )

( , ) ( , )1 11 1

+===

∑∑∑ C C g m n g m npr q s pr q sm

M

q s

K L

p r

K L* *

( , ) ( , )

( , )

( , ) ( , )

( , )

( , ) ( , )11 11 1

. (3-50)

Aufgrund der Unitaritätsrelation

g m n g m npr q sm n

M N

pq rs( , ) ( , )*

( , ) ( , )

( , )

=∑ =

1 1

δ δ (3-51)

ergibt sich

F f m n C D C D C Cm n

M N

k l k lk l

K L

k l k lk l

K L

k l k lk l

K L2 2

1 1 1 1 1 1 1 1

= − − += = = =

∑ ∑ ∑ ∑( , )( , ) ( , )

( , )*

( , ) ( , )

( , )*

( , ) ( , )

( , )*

( , ) ( , )

( , )

,

mit D f m n g m nk l k lm n

M N

==

∑ ( , ) ( , )*

( , ) ( , )

( , )

1 1

(3-52)

und da ∀ ∈ − + = − − − = − − − −a b ab a b a b a a bb a b a b a a bb, * * * * * * * * *� � � � � � �� � ist, ge-

winnt man ferner die Gleichung:

F f m n C D C D C C D D C Cm n

M N

k l k l k l k l k l k l k l k l k l k lk l

K L2 2

1 1 1 1

= − − − − − +��

��

= =∑ ∑( , )

( , ) ( , )

( , ) * * * *

( , ) ( , )

( , )

� �� �

= − − − −��

��

= =∑ ∑f m n C D C D D D

m n

M N

k l k l k l k l k l k lk l

K L

( , )( , ) ( , )

( , ) * *

( , ) ( , )

( , )2

1 1 1 1

� �� � . (3-53)

Die rechte Seite dieser Gleichung ist genau dann minimal, wenn ∀ =( , )k l C Dk l k l ist, so daß

man

0 2 2

1 1

2

1 1

≤ = −= =

∑ ∑F f m n Cm n

M N

k lk l

K L

( , )( , ) ( , )

( , )

( , ) ( , )

( , )

(3-54)

bzw. die diskrete Besselsche Ungleichung

C f m nk lk l

K L

m n

M N2

1 1

2

1 1( , ) ( , )

( , )

( , ) ( , )

( , )

( , )= =

∑ ∑≤ (3-55)

erhält. Der Begriff quadratisch integrabler Funktionen kann im diskreten durch die Bedingung

∀ < ∞( , ) ( , )m n f m n2

(3-56)

- 11 - Dr. Jörg Wollnack

ersetzt werden. Die Vollständigkeit des erzeugenden Systems werden analog zum kontinuier-lichen Fall definiert, so daß

f m n C g m nk l k lk l

K L

m n

M N

( , ) ( , )( , ) ( , )

( , )

( , ) ( , )

( , )

− ===

∑∑1 1

2

1 1

0 (3-57)

gilt. Damit muß sowohl die Parsevalsche Gleichung oder Vollständigkeitsrelation

f m n Cm n

M N

k lk l

K L

( , )( , ) ( , )

( , )

( , ) ( , )

( , )2

1 1

2

1 1= =∑ ∑= (3-58)

als auch die notwendige Bedingung

∀ < ∞( , )k l Ck l (3-59)

erfüllt sein.

3.3.1 Separable Kerne

3.3.2 Diskrete trigonometrischen Fourier-Transformation in komplexer Darstellung

3.3.2.1 Zyklische Faltung und Korrelation

3.3.2.2 Differentiation und Integration

3.3.3 Schnelle Transformationen

3.3.3.1 Fast-Fourier-Transform

3.3.3.2 Fast Walsh-Transform

3.4 Die vektorielle mehrdimensionale unitäre Fourier-Reihe

Der vektorielle mehrdimensionale Fall läßt sich analog zum mehrdimensionalen (skalaren)Fall diskutieren. Zur Entwicklung des vektoriellen mehrdimensionalen unitären Fourier-Reihebeschreibt man den Abstand zwischen der Vektorfunktion und ihrer Vektorreihenent-wicklung. Als Norm läßt sich die Euklidische Norm, die mit dem Skalarprodukt zweierVektoren über die Gleichung v v v

Et= * beschrieben werden kann, verwenden. Sodann

erhält man:

- 12 - Dr. Jörg Wollnack

FC i iD

i iDD I I

= −���

���

���

���

−���

���

���

���∈ ∈

∑ ∑� f x a k g x f x a k g x xkk

kk

( ) ( ) ( ) ( ) ( ) ( )

*t

dR

, mit

f x k= = ∈ = ⊆f f x x k kM NN

NN

1 1 1, , , , , , , ,� � �� � � � � �t t t� � ,

D a b a b b a b aN NN

N NR ≡ × × ⊆ > ∧ ∧ >[ , ] [ , ] ,1 1 1 1� �� und

D K KI NN≡ × × ⊆{ , , } { , , }1 11� � � � . (3-60)

Das erzeugende unitäre zweidimensionale System erfülle die Unitaritätsrelation:

′ ≡ ∈ = ������ ∈

�� �

�����

� ∏=

S dR

g x g x g x x p qk p q( ) ( ) ( ) , ( , )*�

D

i p iqk

N

Ik kDδ δ

1

2 , mit

D Df g⊆ . (3-61)

Hieraus erhält man durch Auflösung des Produkts:

FC i iD

i iDD I I

= −���

���

−���

���

�

���

∈ ∈∑ ∑� f x f x f x a k g x f x a k g xk

kk

k

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * *t

t t

R

+���

������

����

���

∈ ∈∑ ∑a p x a q g x xk

pr

qi i

Di i

D

gI I

( ) ( ) ( ) ( )* *

t

d . (3-62)

Mit dem Superpositionssatz der Mehrfachintegrale und wegen der Kommutativität von Inte-gration und Summation erhält man auch:

F a f gC

D

i

DD DDI I

= − −� �∑ �∑∈ ∈

f x f x x a k f x g x x k x x xkk

kk

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * *t d d dR R R

a a g gDDI

* *

,

( ) ( ) ( ) ( )p q x x xp qp q

dR

�∑∈� 2

. (3-63)

Führt man zur Vereinfachung den Koeffizienten

C f gD

( ) ( ) ( )*k x x xk= �def

dR

(3-64)

ein, so erhält man weiter

F f f a C a C a aC

D D D DI I I

= − − +� ∑ ∑ ∑∈ ∈ ∈

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * *x x x k k k k k kk k k

dR

(3-65)

bzw. analog zum eindimensionalen Fall:

F f f a C a C C CC

D D DI I

= + − − −� ∑ ∑∈ ∈

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * *x x x k k k k k kk k

dR

� � . (3-66)

Die rechte Seite dieser Gleichung ist genau dann minimal, wenn man

∀ ∈ =k k kD a CI ( ) ( ) (3-67)

wählt, so daß dann

F f f C CC

D DI

= −� ∑∈

( ) ( ) ( ) ( )* *x x x k kk

dR

(3-68)

- 13 - Dr. Jörg Wollnack

gilt. Der positiven Definitheit des Fehlerbegriffs (FC ≥ 0) folgend, gilt dann ferner diemehrdimensionale Besselsche Ungleichung

C C f fD DI

( ) ( ) ( ) ( )* *k k x x xk∈∑ �≤ d

R

, (3-69)

aus der sich die mehrdimensionale Parsevalsche oder mehrdimensionale Vollständigkeits-relation zu (K KN1 → ∞ → ∞, ,� )

C C f fD DI

( ) ( ) ( ) ( )* *k k x x xk∈∑ ��= d

R

(3-70)

ergibt. Diese Bedingung ist ebenfalls hinreichend und notwendig für die Vollständigkeit deserzeugenden Systems.

Die Abschätzung (3-12) ist auch im höherdimensionalen Fall hilfreich, da man mit ihr dieKonvergenz der allgemeinen Fourier-Reihe für K KN1 → ∞ → ∞, ,� aus der Existenz des

Integrals f fD

( ) ( )*x x xdR

� < ∞ ableiten kann. Funktionen f dieser Klasse werden ebenfalls als

quadratisch Integrabel bezeichnet. Für die Konvergenz der Reihe C C( ) ( )*k kk∈∑�

2

ist es

notwendig, daß lim ( ) lim ( )k k

C CN1

2 20

→∞ →∞= = =k k� ist. Die Bedingung der quadratisch

Integrabilität sichert den Sinn der vorherigen Aussagen.

Bemerkungen zum Konvergenzbeweis:

Wegen der Dreiecksungleichung der Norm und der Schwarzschen Ungleichung erhält mandie Abschätzung

C g C g C gD D DI I I

( ) ( ) ( ) ( ) ( ) ( )k x k x k xkk

kk

kk∈ ∈ ∈

∑ ∑ ∑≤ =2

2 2 2 , (3-71)

woraus mit der Beschränktheit

∀ ∈ ∈ ≤ ∈ +k x xkD D g AI , ( )R

2 2� (3-72)

der erzeugenden Funktionen folgt:

0

2

2 2≤ ≤∈ ∈∑ ∑C g A C

D DI I

( ) ( ) ( )k x kkk k

. (3-73)

Mit der Besselschen Ungleichung (3-12) erhält man sodann:

0

2

2 2≤ ≤ < ∞∈∑ �C g A f

D DI

( ) ( ) ( )k x x xkk

dR

. (3-74)

Dies sichert die Konvergenz der mehrdimensionalen allgemeinen Fourier-Reihe. Diequadratische Integrabilität stellt somit eine hinreichende Bedingung dar.