Digital Signal Processing Reference
In-Depth Information
4
Schnelle Fourier-Transformation
Ein wichtiges, manchmal sogar entscheidendes Kriterium für die Anwendung der digitalen Sig-
nalverarbeitung ist die Komplexität der eingesetzten Algorithmen. Sie wird meist durch die
Zahl der erforderlichen Rechenoperationen und den Bedarf an Speicherplätzen abgeschätzt.
Dies gilt besonders für die diskrete Fourier-Transformation (DFT). Für sie wird in diesem Ver-
such eine effiziente Implementierung vorgestellt: die schnelle Fourier-Transformation (FFT,
Fast Fourier Transform). Die FFT und verwandte Algorithmen haben einen erheblichen Anteil
daran, dass die digitale Signalverarbeitung in viele naturwissenschaftlich-technische Anwen-
dungen vordringen konnte.
Weil für den Versuch keine speziellen Vorkenntnisse vorausgesetzt werden, wird in der Vorbe-
reitung zunächst der FFT-Algorithmus erarbeitet. Die Entwicklung des Algorithmus ist typisch
für die digitale Signalverarbeitung und hat deshalb für sich selbst einen hohen Wert.
Schlüsselbegriffe
Echtzeitsignalverarbeitung, Komplexität, Radix-2-FFT, schnelle Fourier-Transformation,
Signalflussgraph
Lernziele
Nach Bearbeiten dieses Versuches können Sie
den Begriff Komplexität und seine Bedeutung in der digitalen Signalverarbeitung am Beispiel der
DFT und FFT erklären
den Radix-2-FFT-Algorithmus entwickeln und erläutern
den Radix-2-FFT-Algorithmus programmieren
4.1
Komplexität
Anfang der 1960er Jahre wurden durch den Fortschritt der Digitaltechnik begünstigt zuneh-
mend Verfahren der digitalen Signalverarbeitung eingesetzt. Bei der Spektralanalyse mit der
DFT zeigte sich jedoch, dass für eine gute Frequenzauflösung große Transformationslängen
benötigt werden. In vielen Fällen war damit zunächst eine
digitale Signalverarbeitung in
Echtzeit
nicht möglich, d. h. eine Signalverarbeitung, die Ausgangswerte mit mindestens der
gleichen Rate erzeugt, wie Eingangswerte zugeführt werden.
1965 schlugen Cooley und Tukey ein Verfahren vor, das speziell für große Transformations-
längen die Berechnung der DFT stark beschleunigte und ihr so ein breites Anwendungsfeld
eröffnete [CoTu65].
Unter dem Begriff
schnelle Fourier-Transformation
(FFT, Fast Fourier Transform) werden
heute verschiedene Verfahren zusammengefasst, deren Ansätze bis auf Gauß (1805) zurückrei-
chen. Je nach Anwendung, wobei auch Überlegungen zur verwendeten Hardware (Prozessor-
architektur, Speicherausstattung, usw.) einfließen, werden verschiedene Algorithmen der FFT
eingesetzt.
