Goertzelův algoritmus - Goertzel algorithm

Goertzelův Algoritmus je postup v digitálního zpracování signálu (DSP) pro efektivní zhodnocení jednotlivých jde o diskrétní Fourierova transformace (DFT). Je to užitečné v některých praktických aplikacích, jako je rozpoznávání tónů duálních vícefrekvenčních signálů (DTMF) produkovaných tlačítky klávesnice tradičního analogového telefonu . Algoritmus poprvé popsal Gerald Goertzel v roce 1958.

Stejně jako DFT analyzuje Goertzelův algoritmus jednu volitelnou frekvenční složku z diskrétního signálu . Na rozdíl od přímých výpočtů DFT používá Goertzelův algoritmus při každé iteraci jeden skutečný koeficient s využitím reálné aritmetiky pro vstupní sekvence se skutečnou hodnotou. Pro pokrytí celého spektra má Goertzelův algoritmus vyšší řád složitosti než algoritmy rychlé Fourierovy transformace (FFT), ale pro výpočet malého počtu vybraných frekvenčních složek je numericky efektivnější. Díky jednoduché struktuře Goertzelova algoritmu se dobře hodí pro malé procesory a vestavěné aplikace.

Goertzelův algoritmus lze také použít „obráceně“ jako funkci syntézy sinusoid, která vyžaduje pouze 1 násobení a 1 odčítání na vygenerovaný vzorek.

Algoritmus

Hlavní výpočet v Goertzelově algoritmu má formu digitálního filtru , a proto se algoritmu často říká Goertzelův filtr . Filtr pracuje na vstupní sekvenci v kaskádě dvou stupňů s parametrem , což dává analyzovanou frekvenci, normalizovanou na radiány na vzorek.

První stupeň vypočítá mezilehlou sekvenci :

 

 

 

 

(1)

Druhá fáze použije následující filtr , čímž vytvoří výstupní sekvenci :

 

 

 

 

(2)

První stupeň filtru lze pozorovat jako IIR filtr druhého řádu se strukturou přímého tvaru . Tato konkrétní struktura má vlastnost, že její vnitřní stavové proměnné se rovnají minulým výstupním hodnotám z této fáze. Předpokládá se, že vstupní hodnoty pro jsou všechny rovny 0. K vytvoření počátečního stavu filtru, aby mohlo začít vyhodnocení u vzorku , jsou stavům filtru přiřazeny počáteční hodnoty . Aby se zabránilo nebezpečí aliasingu , frekvence je často omezena na rozsah 0 až π (viz Nyquist – Shannonova vzorkovací věta ); použití hodnoty mimo tento rozsah není bezvýznamné, ale je ekvivalentní použití aliasované frekvence uvnitř tohoto rozsahu, protože exponenciální funkce je periodická s periodou 2π v .

Filtr druhého stupně lze považovat za filtr FIR , protože jeho výpočty nevyužívají žádný ze svých minulých výstupů.

Ke studiu vlastností filtrační kaskády lze použít metody Z-transformace . Z transformace prvního stupně filtru uvedená v rovnici (1) je

 

 

 

 

(3)

Z transformace druhého stupně filtru uvedená v rovnici (2) je

 

 

 

 

(4)

Pak je kombinovaná přenosová funkce kaskády dvou filtračních stupňů

 

 

 

 

(5)

To lze transformovat zpět na ekvivalentní sekvenci v časové doméně a termíny se odvíjejí zpět na první vstupní termín v indexu :

 

 

 

 

(6)

Numerická stabilita

Je možné pozorovat, že póly transformace Z filtru jsou umístěny na a v kruhu poloměru jednotky se středem na počátku komplexní roviny Z-transformace. Tato vlastnost označuje, že proces filtru je okrajově stabilní a zranitelný akumulací numerických chyb při výpočtu pomocí aritmetiky s nízkou přesností a dlouhých vstupních sekvencí. Numericky stabilní verzi navrhl Christian Reinsch.

DFT výpočty

Pro důležitý případ výpočtu termínu DFT platí následující speciální omezení.

  • Filtrování končí indexem , kde je počet termínů ve vstupní sekvenci DFT.
  • Frekvence zvolená pro Goertzelovu analýzu jsou omezeny na speciální formu

 

 

 

 

(7)

  • Indexové číslo označující „kmitočtový koš“ DFT je vybráno ze sady indexových čísel

 

 

 

 

(8)

Provedení těchto substitucí do rovnice (6) a pozorování, že výraz , rovnice (6) má následující podobu:

 

 

 

 

(9)

Můžeme pozorovat, že pravá strana rovnice (9) je extrémně podobná definujícímu vzorci pro DFT termín , DFT termín pro číslo indexu , ale ne úplně stejný. Součet zobrazený v rovnici (9) vyžaduje vstupní výrazy, ale při hodnocení DFT jsou k dispozici pouze vstupní výrazy. Jednoduchým, ale neelegantním prostředkem je rozšíření vstupní sekvence o další umělou hodnotu . Z rovnice (9) vidíme, že matematický účinek na konečný výsledek je stejný jako odstranění členu ze součtu, čímž se získá zamýšlená hodnota DFT.

Existuje však elegantnější přístup, který se vyhne dalšímu průchodu filtrem. Z rovnice (1) si můžeme povšimnout, že když se v posledním kroku použije rozšířený vstupní člen,

 

 

 

 

(10)

Algoritmus lze tedy dokončit následujícím způsobem:

  • po zpracování vstupního termínu ukončit filtr IIR ,
  • aplikovat rovnici (10) na konstrukci z předchozích výstupů a ,
  • aplikujte rovnici (2) s vypočítanou hodnotou a s výsledkem konečného přímého výpočtu filtru.

Poslední dvě matematické operace jsou zjednodušeny jejich kombinací algebraicky:

 

 

 

 

(11)

Uvědomte si, že zastavení aktualizací filtru v termínu a okamžité použití rovnice (2) namísto rovnice (11) zmešká konečné aktualizace stavu filtru, což povede k výsledku s nesprávnou fází.

Konkrétní filtrační struktura zvolená pro Goertzelův algoritmus je klíčem k jeho efektivním výpočtům DFT. Můžeme pozorovat, že pro výpočet DFT se používá pouze jedna výstupní hodnota , takže jsou vynechány výpočty pro všechny ostatní výstupní výrazy. Vzhledem k tomu, že se filtr FIR nevypočítává, lze výpočty fáze IIR atd. Zahodit ihned po aktualizaci interního stavu první fáze.

Zdá se, že to zanechává paradox: k dokončení algoritmu musí být fáze filtru FIR vyhodnocena jednou pomocí posledních dvou výstupů z fáze filtru IIR, zatímco pro výpočetní účinnost iterace filtru IIR zahodí své výstupní hodnoty. To je místo, kde jsou použity vlastnosti struktury přímého filtru. Dvě interní stavové proměnné filtru IIR poskytují poslední dvě hodnoty výstupu filtru IIR, což jsou termíny požadované pro vyhodnocení stupně filtru FIR.

Aplikace

Termíny výkonového spektra

Při zkoumání rovnice (6) použije konečné předání filtru IIR k výpočtu termínu pomocí doplňkové vstupní hodnoty komplexní multiplikátor velikosti 1 na předchozí člen . V důsledku toho, a představují ekvivalentní výkonu signálu. Stejně tak platí použít rovnici (11) a vypočítat výkon signálu z členu nebo použít rovnici (2) a vypočítat výkon signálu z členu . Oba případy vedou k následujícímu výrazu pro sílu signálu představovanou výrazem DFT :

 

 

 

 

(12)

V níže uvedeném pseudokódu proměnné spreva sprev2dočasně ukládají historii výstupu z filtru IIR, zatímco x[n]je indexovaným prvkem pole x , které ukládá vstup.

Nterms defined here
Kterm selected here
ω = 2 × π × Kterm / Nterms;
cr := cos(ω)
ci := sin(ω)
coeff := 2 × cr

sprev := 0
sprev2 := 0
for each index n in range 0 to Nterms-1 do
    s := x[n] + coeff × sprev - sprev2
    sprev2 := sprev
    sprev := s
end

power := sprev2 × sprev2 + sprev × sprev - coeff × sprev × sprev2

Je možné uspořádat výpočty tak, aby příchozí vzorky byly dodávány jednotlivě do softwarového objektu, který udržuje stav filtru mezi aktualizacemi, s konečným výsledkem napájení po přístupu k dalšímu zpracování.

Jeden termín DFT s aritmetikou se skutečnou hodnotou

Případ skutečných hodnot vstupních dat vzniká často, zejména ve vestavěných systémech, kde jsou vstupní toky výsledkem přímých měření fyzických procesů. Ve srovnání s ilustrací v předchozí části, když jsou vstupní data reálná, jsou proměnné interního stavu filtru spreva sprev2lze pozorovat, že jsou také reálné, v důsledku toho není v první fázi IIR vyžadována žádná složitá aritmetika. Optimalizace pro aritmetiku se skutečnou hodnotou je obvykle tak jednoduchá jako použití vhodných datových typů se skutečnou hodnotou pro proměnné.

Po ukončení výpočtů pomocí vstupního výrazu a iterací filtrů je nutné k vyhodnocení termínu DFT použít rovnici (11). Konečný výpočet používá aritmetiku se složitou hodnotou, ale lze ji převést na aritmetiku se skutečnou hodnotou oddělením reálných a imaginárních výrazů:

 

 

 

 

(13)

Ve srovnání s aplikací výkonového spektra je jediným rozdílem výpočet použitý k dokončení:

(Same IIR filter calculations as in the signal power implementation)
XKreal = sprev * cr - sprev2;
XKimag = sprev * ci;

Fázová detekce

Tato aplikace vyžaduje stejné vyhodnocení DFT termínu , jak je popsáno v předchozí části, pomocí vstupního proudu se skutečnou hodnotou nebo s komplexní hodnotou. Pak lze fázi signálu vyhodnotit jako

 

 

 

 

(14)

přijímání vhodných opatření pro singularity, kvadrant atd. při výpočtu funkce inverzní tangenty.

Složité signály ve skutečné aritmetice

Protože složité signály se lineárně rozkládají na reálné a imaginární části, lze Goertzelův algoritmus vypočítat v reálné aritmetice samostatně přes posloupnost skutečných částí, čímž se získá , a přes posloupnost imaginárních částí, čímž se získá . Poté lze znovu zkombinovat dva dílčí výsledky s komplexní hodnotou:

 

 

 

 

(15)

Výpočetní složitost

  • Podle výpočetní složitosti teorie , výpočetní sadu DFT výrazy pomocí aplikace algoritmu Goertzelův na souboru dat s hodnotami s „náklady na provoz“ na má složitost .
Chcete-li vypočítat jeden DFT bin pro komplexní vstupní sekvenci délky , Goertzelův algoritmus vyžaduje multiplikace a sčítání / odčítání v rámci smyčky, stejně jako 4 multiplikace a 4 finální sčítání / odčítání, pro celkem multiplikací a sčítání / odčítání. To se opakuje pro každou z frekvencí.
  • Naproti tomu použití FFT na datové sadě s hodnotami má složitost .
To je těžší přímo aplikovat, protože to závisí na použitém algoritmu FFT, ale typickým příkladem je radix-2 FFT, který vyžaduje násobení a sčítání / odčítání na DFT bin pro každý z košů.

Ve výrazech pořadí složitosti, když je počet vypočítaných členů menší než , je výhoda Goertzelova algoritmu jasná. Ale protože je kód FFT poměrně složitý, je faktor „cena za jednotku práce“ pro FFT často větší a praktická výhoda upřednostňuje Goertzelův algoritmus dokonce i několikanásobně větší než .

Jako obecné pravidlo pro určení, zda je radix-2 FFT nebo Goertzelův algoritmus efektivnější, upravte počet termínů v datové sadě vzhůru na nejbližší přesnou mocninu 2, volání tohoto , a Goertzelův algoritmus je pravděpodobný být rychlejší, pokud

Implementace FFT a platformy pro zpracování mají významný dopad na relativní výkon. Některé implementace FFT provádějí interní výpočty komplexních čísel, aby generovaly průběžné koeficienty, což významně zvyšuje jejich „cenu K na jednotku práce“. Algoritmy FFT a DFT mohou používat tabulky předem vypočítaných hodnot koeficientů pro lepší numerickou účinnost, ale to vyžaduje více přístupů k hodnotám koeficientů uložených v externí paměti, což může vést ke zvýšenému tvrzení o mezipaměti, které vyvažuje některé numerické výhody.

Oba algoritmy získávají přibližně dvojnásobnou účinnost při použití vstupních dat se skutečnou hodnotou než se složitou hodnotou. Tyto zisky jsou však pro Goertzelův algoritmus přirozené, ale pro FFT jich nebude dosaženo bez použití určitých variant algoritmu specializovaných na transformaci dat se skutečnou hodnotou .

Viz také

Reference

Další čtení

  • Proakis, JG; Manolakis, DG (1996), Digital Signal Processing: Principles, Algorithms, and Applications , Upper Saddle River, NJ: Prentice Hall, pp. 480–481, Bibcode : 1996dspp.book ..... P

externí odkazy