Goertzeli algoritm

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.
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. 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. Goertzeli algoritmi kasutatakse näiteks helitöötluses üksiku tooni tuvastamiseks, energeetikas signaalide analüüsimiseks ning arhitektuuris hoonete struktuurikahjustuste tuvastamiseks.
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. Algoritmi üldine matemaatiline kuju: 
formula_1, kus formula_2 on tulemuste hulk, formula_3 on vaadeldava sageduse indeks, formula_4 on eelmine element ning formula_5 üle-eelmine element hulgas formula_2. Ülejäänud muutujad on täpsemalt kirjeldatud allpool.
Enne Goertzeli algoritmi kasutamist tuleb teha järgnevad sammud:
Diskreetimissagedus määratakse enamasti rakenduse järgi (näiteks helisignaali puhul kasutatakse tavaliselt 44,1 kHz sagedust ehk diskreeditakse signaali 44100 korda sekundis), kuid seda saab leida ka näiteks Nyquisti teoreemi abil, mille alusel peab diskreetimissagedus olema vähemalt kaks korda suurem sisendsignaali suurimast sagedusest. 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:
formula_7, kus formula_8 on otsitav sagedus (inglise keeles "target frequency")
formula_9
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: 
formula_10, kus formula_11 on vaadeldav sämpel 
formula_12 
formula_13 
Pärast tehete teostamist igal N sämplil, saame muutujate lõppväärtusi kasutades leida sagedusploki magnituudi reaal- ja imaginaarosa: 
formula_14 
formula_15 
Selleks et leida magnituudi väärtust, võtame ruutjuure reaalosa ja imaginaarosa ruutude summast: 
formula_16
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:
formula_17
Kusjuures sämplite töötlemine toimub samamoodi, nagu tavalises Goertzeli algoritmis. Algoritmi optimeeritud versioon on rohkem levinud, kuna see on efektiivsem.