Digital Signal Processing Reference
In-Depth Information
4
Schnelle Fourier-Transformation
4.1
Einführung
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
Versuch 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 An-
wendungen vordringen konnte.
Weil für den Versuch keine besonderen Vorkenntnisse vorausgesetzt werden, wird in der Vor-
bereitung 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.
Lernziele
Nach Bearbeiten dieses Versuches können Sie
x
den Begriff Komplexität und seine Bedeutung in der digitalen Signalverarbeitung am Beispiel der
DFT und FFT erklären
x
den Radix-2-FFT-Algorithmus entwickeln und erläutern
x
den Radix-2-FFT-Algorithmus programmieren
4.2
Komplexität
Anfang der sechziger 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 u. a. bis auf Gauß (1805)
zurückreichen. Je nach Anwendung, wobei auch Überlegungen zur verwendeten Hardware
(Prozessorarchitektur, Speicherausstattung, u. ä.) einfließen, werden verschiedene Algorithmen
der FFT eingesetzt.
In diesem Versuch wird der am häufigsten verwendete Algorithmus, die Radix-2-FFT behan-
delt. Anwendungen der FFT in der Kurzzeit-Spektralanalyse werden in den nächsten beiden
Versuchen vorgestellt.
