Goertzel-Algorithmus

Goertzel-Algorithmus

Der Goertzel-Algorithmus ist ein Verfahren aus der digitalen Signalverarbeitung und stellt eine besondere Form der diskreten Fourier-Transformation (DFT) dar. Im Gegensatz zu den verschiedenen schnellen Berechnungsmethoden bei der diskreten Fouriertransformation (FFT), welche immer alle diskreten Spektralkomponenten 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.

Inhaltsverzeichnis

Funktion

Der Algorithmus basiert auf einer Struktur bestehend aus einem 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 Abtastwert (engl. sample) durchlaufen und ist als ein rekursives digitales Filter mit zwei Zustandsspeichern und einem Akkumulator aufgebaut. Der Vorwärtszweig wird erst nach N Abtastwerten einmalig durchlaufen und liefert aus den Zustandsspeichern den berechneten komplexen Ausgangswert, die spektrale Komponente nach Betrag und Phase.

Durch die Wahl der dabei eingesetzten Filterkoeffizienten lässt sich die Frequenzselektivität einstellen. Durch die Wahl der Anzahl der Abtastwerte N lässt sich der Gütefaktor beeinflussen. N kann beliebige positive ganzzahlige Werte annehmen.

Pro Spektralkomponente ist allerdings eine eigenständige Goertzel-Struktur notwendig. Daher ist dieser Algorithmus vor allem dann vorteilhaft und mit geringerem Rechnenaufwand anzuwenden, 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.

Aufwandsabschätzung

Pro Berechnung einer Spektralkomponente sind bei dem Goertzel-Algorithmus 4N Additionen und 4N Multiplikationen notwendig. Vergleicht man diesen Aufwand mit dem Berechnungsaufwand bei der schnellen Fourier-Transformation ist der Goertzel-Algorithmus immer dann effizienter, wenn weniger als 5/6 log2(N) Spektralkomponenten berechnet werden sollen. Denn pro Spektralkomponente (bin) ist eine weitere Goertzelstruktur notwendig, während bei der schnellen Fourier-Transformation der Berechnungsaufwand nur mit Nlog2N ansteigt.

Der Algorithmus kann effizient in digitalen Signalprozessoren implementiert werden.

Anwendungen

Die Anwendungen liegen in der Erkennung einzelner Frequenzen (Tonerkennung) in einem Signal wie beispielsweise bei der Erkennung der Signalisierungsfrequenzen bei dem im Telefonbereich eingesetzten Mehrfrequenzwahlverfahren. In diesem Fall muss nur der Betrag der Spektralkomponente ausgewertet werden, was weitere Vereinfachungen in der Berechnung gestattet.

Literatur

  • Gerald Goertzel: 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


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Fast-Fourier-Transformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… …   Deutsch Wikipedia

  • Fast Fourier-Transformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… …   Deutsch Wikipedia

  • Schnelle Fouriertransformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… …   Deutsch Wikipedia

  • Schnelle Fourier-Transformation — Eine schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei solchen Algorithmen handelt es sich… …   Deutsch Wikipedia

  • Diskrete Fouriertransformation — Die Diskrete Fourier Transformation oder DFT ist die Fourier Transformation eines zeitdiskreten periodischen Signals. Dabei wird das periodische Signal als Superposition eines Gleichanteils, einer Grundschwingung und ihrer Oberschwingungen in ein …   Deutsch Wikipedia

  • Diskrete Fourier-Transformation — Die Diskrete Fourier Transformation oder DFT ist eine Transformation aus dem Bereich der Fourier Analysis. Sie bildet ein zeitdiskretes, endliches Signal, welches periodisch fortgesetzt wird, auf ein diskretes, periodisches Frequenzspektrum ab,… …   Deutsch Wikipedia

  • Frequency Shift Keying — Bildung eines binären FSK Signals. Oben: Quelldaten als eine Folge von logisch 1 und logisch 0. Mitte: Unmodulierte Trägerfrequenz Unten: Moduliertes FSK Signal. Die Frequenzumtastung (englisch Frequency Shift Keying, FSK) ist eine… …   Deutsch Wikipedia

  • Frequenz-Shift-Keying — Bildung eines binären FSK Signals. Oben: Quelldaten als eine Folge von logisch 1 und logisch 0. Mitte: Unmodulierte Trägerfrequenz Unten: Moduliertes FSK Signal. Die Frequenzumtastung (englisch Frequency Shift Keying, FSK) ist eine… …   Deutsch Wikipedia

  • GMSK — Bildung eines binären FSK Signals. Oben: Quelldaten als eine Folge von logisch 1 und logisch 0. Mitte: Unmodulierte Trägerfrequenz Unten: Moduliertes FSK Signal. Die Frequenzumtastung (englisch Frequency Shift Keying, FSK) ist eine… …   Deutsch Wikipedia

  • Minimum Shift Keying — Bildung eines binären FSK Signals. Oben: Quelldaten als eine Folge von logisch 1 und logisch 0. Mitte: Unmodulierte Trägerfrequenz Unten: Moduliertes FSK Signal. Die Frequenzumtastung (englisch Frequency Shift Keying, FSK) ist eine… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”