Goertzeli algoritm

Autovoni klahvistikel kasutati DTFM-signaali, mille tuvastamiseks saab kasutada Goertzeli algoritmi

Goertzeli algoritmi (ka Goertzeli filter, inglise keeles Goertzel algorithm) kasutatakse digitaalses signaalitöötluses (DSP) diskreetse Fourier' pöörde (DFT) üksikute komponentide tõhusaks määramiseks. Algoritmi leiutas Gerald Goertzel aastal 1958 ning seda algoritmi kasutatakse näiteks multisageduslikul kakstoonvalimisel.^[1]

Goertzeli algoritm analüüsib üksikut sageduskomponenti digitaalsignaalist, kuid erinevalt tavalisest DFT arvutusest, rakendab Goertzeli algoritm igal iteratsioonil üht reaalarvulist koefitsienti, kasutades reaalarvulistel sisenditel reaalarvulist aritmeetikat.^[2][3][4] Goertzeli algoritmi saab kasutada ka tagurpidi (sinusoidi sünteesimiseks), kusjuures iga sämpli arvutamiseks tuleb teha üks korrutus- ning üks lahutamistehe. Lisaks ei pea Goertzeli algoritmis kasutatav akna suurus olema arvu 2 aste (erinevalt DFT-st) ning algoritm ei vaja nii palju mälu, kui DFT. Kuigi Goertzeli algoritm on kiirem, kui DFT, ei ole selle arvutamine oluliselt keerulisem ning tulemuse saamiseks on vaja teha vaid mõned arvutustehted. Samas ei ole Goertzeli algoritmi tulemus keerulisemate signaalide puhul nii täpne, kui DFT-l, seega tuleks mõnedel juhtudel (kui täpsus on olulisem kui kiirus) eelistada siiski DFT-d.

Täieliku spektri katmisel (diskreetse sisendandmete hulga korral) on Goertzeli algoritmi keerukus suurem, kui Fourier' kiirteisendusel (FFT), kuid väikese arvu sageduskomponentide arvutamisel on see efektiivsem, kui FFT - seetõttu ei vaja algoritmi kasutamine suurt arvutusvõimsust. Kuna Goertzeli algoritm on optimeeritud väikeste sagedusvahemike jaoks, ei ole seda mõistlik kasutada kogu spektri uurimiseks. On olemas ka Goertzeli algoritmi optimeeritud versioon, mis on veelgi efektiivsem, kuid ei anna nii täpseid tulemusi.^[5] Goertzeli algoritmi kasutatakse näiteks helitöötluses üksiku tooni tuvastamiseks^[6], energeetikas signaalide analüüsimiseks^[7] ning arhitektuuris hoonete struktuurikahjustuste tuvastamiseks^[8].

Algoritm

Goertzeli algoritmi rakendamiseks on vaja kaht hulka: sisendandmete hulk X ning tulemuste hulk Y. Iga elemendi arvutamiseks tuleb kasutada kaht eelnevat tulemust ning üht eelnevalt välja arvutatud koosinust. ^[5] Algoritmi üldine matemaatiline kuju:

${\displaystyle Y(z)=(1-e^{-j*2*\pi *k/N}*z^{-1})/(1-\cos(2*\pi *k/N)*z^{-1}+z^{-2})}$^[9], kus ${\displaystyle Y}$ on tulemuste hulk, ${\displaystyle z}$ on vaadeldava sageduse indeks, ${\displaystyle z^{-1}}$ on eelmine element ning ${\displaystyle z^{-2}}$ üle-eelmine element hulgas ${\displaystyle Y}$. Ülejäänud muutujad on täpsemalt kirjeldatud allpool.

Enne Goertzeli algoritmi kasutamist tuleb teha järgnevad sammud:

1. Valida diskreetimissagedus (inglise keeles Sample rate);
2. Valida ploki suurus N ehk uuritava sagedusvahemiku suurus.

Diskreetimissagedus määratakse enamasti rakenduse järgi (näiteks helisignaali puhul kasutatakse tavaliselt 44,1 kHz sagedust ehk diskreeditakse signaali 44100 korda sekundis^[10]), kuid seda saab leida ka näiteks Nyquisti teoreemi abil, mille alusel peab diskreetimissagedus olema vähemalt kaks korda suurem sisendsignaali suurimast sagedusest.^[11] Ploki suuruse valimisel tuleb arvestada, et mida suurem on N, seda suurem on sageduse resolutsioon, kuid seda pikem on algoritmi tööks kuluv aeg.

Lisaks tuleb arvutada välja järgnevad konstandid:

${\displaystyle k=(0.5+{\frac {N*f}{diskreetimissagedus}})}$, kus ${\displaystyle f}$ on otsitav sagedus (inglise keeles target frequency)

${\displaystyle W=(2*\pi /N)*k}$

Seejärel saab rakendada Goertzeli algoritmi, kasutades sisendandmete hulka X ning väljundandmete hulka Y (n-ndal kohal asuv element vastavalt x[n] või y[n]). Esimese kahe väärtuse arvutamiseks tuleb y[n-1] ja y[n-2] väärtustada nulliga.

Iga sämpli peal tuleb teostada järgnevad tehted:

${\displaystyle y[n]=2*\cos(W)*y[n-1]-y[n-2]+x[n]}$, kus ${\displaystyle x[n]}$ on vaadeldav sämpel

${\displaystyle y[n-2]=y[n-1]}$

${\displaystyle y[n-1]=y[n]}$

Pärast tehete teostamist igal N sämplil, saame muutujate lõppväärtusi kasutades leida sagedusploki magnituudi reaal- ja imaginaarosa:

${\displaystyle real=(y[N-1]-y[N-2]*\cos(W))}$

${\displaystyle imag=(y[N-2]*\sin(W))}$

Selleks et leida magnituudi väärtust, võtame ruutjuure reaalosa ja imaginaarosa ruutude summast:

${\displaystyle magnituud={\sqrt {real^{2}+imag^{2}}}}$

Optimeeritud Goertzeli algoritm

Optimeeritud Goertzeli algoritm erineb tavalisest Goertzeli algoritmist vaid selle poolest, et algoritmi viimases faasis ei arvutata välja magnituudi reaal- ja imaginaarosa, vaid leitakse magnituud järgneva valemi abil:

${\displaystyle magnituud={\sqrt {(y[N-1])^{2}+(y[N-2])^{2}-y[N-1]*y[N-2]*2*\cos(W)}}}$

Kusjuures sämplite töötlemine toimub samamoodi, nagu tavalises Goertzeli algoritmis. Algoritmi optimeeritud versioon on rohkem levinud, kuna see on efektiivsem. ^[5]

Viited

1. Goertzel, G. (jaanuar 1958). "An Algorithm for the Evaluation of Finite Trigonometric Series". American Mathematical Monthly. 65 (1): 34–35. DOI:10.2307/2310304. JSTOR 2310304.
2. Mock, P. (21. märts 1985). "Add DTMF Generation and Decoding to DSP-μP Designs" (PDF). EDN. ISSN 0012-7515.
3. Chen, Chiouguey J. (juuni 1996). "Modified Goertzel Algorithm in DTMF Detection Using the TMS320C80 DSP" (PDF). Application report, Texas Instruments, SPRA066.
4. Shmer, Gunter (mai 2000). "DTMF Tone Generation and Detection: An Implementation Using the TMS320C54x" (PDF). Application Report, Texas Instruments, SPRA066.
5. Staff, Embedded (28. august 2002). "The Goertzel Algorithm". Embedded.com (Ameerika inglise). Vaadatud 26. märtsil 2023.
6. "Single tone detection with the Goertzel algorithm". embedded.com. 19. november 2012. Vaadatud 2. mail 2023.
7. Kim, Jae-Hyung; Lee, Suwon; Lee, S.; Lee, T.; Won, C. (2009). "Power quality control using the Goertzel algorithm for grid-connected system". INTELEC 2009 - 31st International Telecommunications Energy Conference (inglise).
8. Bocca, Maurizio; Toivola, Janne; Eriksson, Lasse M.; Hollmén, Jaakko; Koivo, Heikki (aprill 2011). "Structural Health Monitoring in Wireless Sensor Networks by the Embedded Goertzel Algorithm". 2011 IEEE/ACM Second International Conference on Cyber-Physical Systems: 206–214. DOI:10.1109/ICCPS.2011.19.
9. "L10: Frequency Synthesis and Detection — Real Time Digital Signal Processing B Term 2020 documentation". schaumont.dyn.wpi.edu. Vaadatud 1. mail 2023.
10. "Sample Rates - Audacity Manual". manual.audacityteam.org. Vaadatud 26. märtsil 2023.
11. "What is the Nyquist theorem?". WhatIs.com (inglise). Vaadatud 26. märtsil 2023.