imported>Hybridrix: /* Aufwandsabschätzung */Tippfehler korrigiert, Link zu Kammeyer

2025-08-22T16:01:06Z

Aufwandsabschätzung: Tippfehler korrigiert, Link zu Kammeyer

Neue Seite

Der '''Goertzel-Algorithmus''' ist ein Verfahren aus der [[digitale Signalverarbeitung|digitalen Signalverarbeitung]] und stellt eine besondere Form der [[Diskrete Fourier-Transformation|diskreten Fourier-Transformation]] (DFT) dar. Im Gegensatz zu den verschiedenen schnellen Berechnungsmethoden bei der diskreten schnellen Fourier-Transformation [[Schnelle_Fourier-Transformation|(FFT)]], die immer alle diskreten [[Frequenzspektrum|Spektral]]<nowiki/>komponenten in einem Block berechnen, ist es mit dem Goertzel-Algorithmus möglich, nur einzelne diskrete Spektralanteile zu berechnen. Entwickelt wurde der Algorithmus 1958 von [[Gerald Goertzel]] (1919–2002).

== Funktion ==
Der Algorithmus basiert auf einer Struktur bestehend aus einem [[digitales Filter|digitalen Filter]], das um eine Zustandssteuerung erweitert ist. Die Zustände unterteilen die Berechnung in den Rückwärtszweig, in dem die im Zeitbereich abgetasteten Eingangswerte geladen werden, und in einen Vorwärtszweig, der das Ausgangssignal liefert. Die Rückwärtsschleife wird bei jedem digitalen [[Abtastung (Signalverarbeitung)|Abtastwert]] ({{enS|sample}}) durchlaufen und ist als ein [[Filter mit unendlicher Impulsantwort|rekursives digitales Filter]] mit zwei Zustandsspeichern und einem Akkumulator aufgebaut. Der Vorwärtszweig wird erst nach <math>N</math> Abtastwerten einmalig durchlaufen und liefert aus den Zustandsspeichern den berechneten [[Komplexe Zahl|komplexen]] Ausgangswert – nämlich die spektrale Komponente nach [[Betragsfunktion|Betrag]] und [[Komplexe Zahl#Darstellung von komplexen Zahlen in der komplexen Zahlenebene|Phase]].

Durch die Wahl der dabei eingesetzten Filterkoeffizienten lässt sich die Frequenzselektivität einstellen. Durch die Wahl der Anzahl der Abtastwerte <math>N</math> lässt sich der [[Gütefaktor]] beeinflussen. <math>N</math> kann beliebige [[Natürliche Zahl|natürliche]] Werte annehmen.

Pro Spektralkomponente ist allerdings eine eigenständige Goertzel-Struktur notwendig. Daher ist dieser Algorithmus vor allem dann vorteilhaft und mit geringerem Rechenaufwand anwendbar, wenn nicht das komplette Spektrum berechnet werden soll, sondern nur einzelne Spektralkomponenten daraus.

Ausführliche mathematische Herleitungen des Algorithmus finden sich in den unten angegebenen Literaturquellen.

== Algorithmus ==
Von einem [[Digitalsignal|diskreten Signal]] <math>s_i (i=0, ..., N)</math> wird der Realteil <math>C</math> und der Imaginärteil <math>S</math> einer Spektralkomponente <math>\omega</math> über einen [[Rekursion|rekursiven]] [[Algorithmus]] bestimmt.<ref>{{Literatur |Autor=Gerald Goertzel |Titel=An Algorithm for the Evaluation of Finite Trigonometric Series |Sammelwerk=The American Mathematical Monthly |Band=Vol. 65 |Nummer=No. 1 |Ort=Nuclear Development Corporation of Americ,White Plains, N. Y. |Datum=1958-01 |DOI=10.2307/2310304 |Seiten=34-35 |Online=https://courses.cs.washington.edu/courses/cse466/12au/calendar/Goertzel-original.pdf}}</ref> Die Startbedingungen sind:

:<math>U_{N+2} = U_{N+1} = 0</math>

Über

:<math>U_k = s_k + 2 \cdot U_{k+1} \cdot \cos \omega - U_{k+2}</math>   für <math>k = N, N-1, \dotsc, 1</math>

ergibt sich:

:<math>C = s_0 + U_1 \cdot \cos \omega - U_2</math>
:<math>S = U_1 \cdot \sin \omega</math>

Auf die [[Trigonometrische Funktion|Winkelfunktionen]] <math>\cos \omega</math> und <math>\sin\omega</math> muss dabei nur je einmal zugegriffen werden.


== Aufwandsabschätzung ==
Pro Berechnung einer Spektralkomponente sind beim Goertzel-Algorithmus <math>2N+2</math> Additionen/Subtraktionen und <math>N+2</math> Multiplikationen notwendig.<ref>{{Literatur|Autor=[[Karl-Dirk Kammeyer]], Kristian Kroschel|Titel=Digitale Signalverarbeitung: Filterung und Spektralanalyse mit MATLAB-Übungen|Hrsg=|Sammelwerk=|Band=|Nummer=|Auflage=|Verlag=Springer-Verlag|Ort=|Datum=2009|Seiten=274|ISBN=9783834806109|Online=https://books.google.de/books?id=hmC20iKv8CsC&pg=PA272&dq=goertzel+algorithmus&hl=de&sa=X&ved=0ahUKEwjwzJK3odbUAhVJEVAKHQIwDFQQ6AEIKTAA#v=onepage&q=goertzel%20algorithmus&f=false|Abruf=2017-06-24}}</ref> Vergleicht man diesen Aufwand mit dem Berechnungsaufwand bei der [[schnelle Fourier-Transformation|schnellen Fourier-Transformation]] (FFT), ist der Goertzel-Algorithmus immer dann effizienter, wenn weniger als <math>\tfrac{5}{6} \cdot \log_2 N</math> Spektralkomponenten berechnet werden sollen. Denn pro Spektralkomponente (bin) ist eine weitere Goertzelstruktur notwendig, während bei der schnellen Fourier-Transformation der Berechnungsaufwand nur mit <math>N \cdot \log_2 N</math> ansteigt.

Der Algorithmus kann effizient in [[Digitaler Signalprozessor|digitalen Signalprozessoren]] implementiert werden.

== Anwendungen ==
Die Anwendungen liegen in der Erkennung einzelner Frequenzen (''Tonerkennung'') in einem [[Signal#Signal in der Nachrichtentechnik|Signal]] wie beispielsweise bei der Erkennung der Signalisierungsfrequenzen bei dem im [[Telefon]]bereich eingesetzten [[Mehrfrequenzwahlverfahren]]. In diesem Fall muss nur der Betrag der Spektralkomponente ausgewertet werden, was weitere Vereinfachungen in der Berechnung gestattet.

== Literatur ==
* Gerald Goertzel: [https://courses.cs.washington.edu/courses/cse466/12au/calendar/Goertzel-original.pdf ''An Algorithm for the Evaluation of Finite Trigonometric Series.''] In: ''American Math. Monthly.'' Vol 65. 1958, S. 34–35.
* Alan V. Oppenheim: ''Zeitdiskrete Signalverarbeitung.'' Oldenbourg Verlag, München 1999, ISBN 3-486-24145-1 (deutsche Übersetzung von ''Discrete-Time Signal Processing'', Prentice Hall Inc. 1989)

== Weblinks ==
* [https://www.mathworks.com/help/toolbox/signal/ref/goertzel.html Goertzel-Algorithmus] – Funktionsaufruf in [[MATLAB]] (englisch)

== Einzelnachweise ==
<references />

[[Kategorie:Digitale Signalverarbeitung]]
[[Kategorie:Algorithmus]]

Goertzel-Algorithmus - Versionsgeschichte

imported>Hybridrix: /* Aufwandsabschätzung */Tippfehler korrigiert, Link zu Kammeyer