Chirp Z-transformace - Chirp Z-transform

Chirp Z-transformace ( CZT ) je zobecněním diskrétní Fourierovy transformace . Zatímco vzorků DFT Z roviny v rovnoměrně rozmístěných bodech podél kruhu jednotky se chirp Z-transformace vzorků podél spirálové oblouky v Z-rovině, odpovídající rovné čáry v S rovině . DFT, skutečný DFT a zoom DFT lze vypočítat jako speciální případy CZT.

Konkrétně chirp Z transformace vypočítá Z transformaci v konečném počtu bodů z _k podél logaritmického spirálového obrysu, definovaného jako:

${\ displaystyle X_ {k} = \ součet _ {n = 0} ^ {N-1} x (n) z_ {k} ^ {- n}}$

${\ displaystyle z_ {k} = A \ cdot W ^ {- k}, k = 0,1, \ tečky, M-1}$

kde A je komplexní výchozí bod, W je komplexní poměr mezi body a M je počet bodů k výpočtu.

Bluesteinův algoritmus

Bluesteinův algoritmus vyjadřuje CZT jako konvoluci a efektivně ji implementuje pomocí FFT / IFFT.

Protože DFT je zvláštním případem CZT, umožňuje to efektivní výpočet diskrétní Fourierovy transformace (DFT) libovolných velikostí, včetně hlavních velikostí. (Další algoritmus pro FFT hlavních velikostí, Raderův algoritmus , funguje také přepsáním DFT jako konvoluce.) Byl vytvořen v roce 1968 Leem Bluesteinem . Bluesteinův algoritmus lze použít k výpočtu obecnějších transformací než DFT na základě (jednostranné) z-transformace (Rabiner et al. , 1969).

Připomeňme, že DFT je definován vzorcem

${\ displaystyle X_ {k} = \ suma _ {n = 0} ^ {N-1} x_ {n} e ^ {- {\ frac {2 \ pi i} {N}} nk} \ qquad k = 0 , \ tečky, N-1.}$

Pokud nahradíme produkt nk v exponentu identitou

${\ displaystyle nk = {\ frac {- (kn) ^ {2}} {2}} + {\ frac {n ^ {2}} {2}} + {\ frac {k ^ {2}} {2 }}}$

tak získáváme:

${\ displaystyle X_ {k} = e ^ {- {\ frac {\ pi i} {N}} k ^ {2}} \ součet _ {n = 0} ^ {N-1} \ vlevo (x_ {n } e ^ {- {\ frac {\ pi i} {N}} n ^ {2}} \ vpravo) e ^ {{\ frac {\ pi i} {N}} (kn) ^ {2}} \ qquad k = 0, \ dots, N-1.}$

Tento součet je přesně konvoluce dvou sekvencí a _n a b _n definovaných:

${\ displaystyle a_ {n} = x_ {n} e ^ {- {\ frac {\ pi i} {N}} n ^ {2}}}$

${\ displaystyle b_ {n} = e ^ {{\ frac {\ pi i} {N}} n ^ {2}},}$

s výstupem konvoluce vynásobeným N fázovými faktory b _k ^* . To je:

${\ displaystyle X_ {k} = b_ {k} ^ {*} \ součet _ {n = 0} ^ {N-1} a_ {n} b_ {kn} \ qquad k = 0, \ tečky, N-1 .}$

Tuto konvoluci lze zase provést pomocí dvojice FFT (plus předem vypočítaného FFT komplexního chirp b _n ) prostřednictvím konvoluční věty . Klíčovým bodem je, že tyto FFT nemají stejnou délku N : takovou konvoluci lze vypočítat přesně z FFT pouze jeho nulovým polstrováním na délku větší nebo rovnou 2 N –1. Zejména lze pad na sílu dvou nebo jiné vysoce složené velikosti, pro kterou lze FFT efektivně provádět např. Algoritmem Cooley – Tukey v čase O ( N log N ). Bluesteinův algoritmus tedy poskytuje způsob O ( N log N ) pro výpočet DFT primární velikosti, i když několikrát pomalejší než algoritmus Cooley – Tukey pro kompozitní velikosti.

Použití nulové výplně pro konvoluci v Bluesteinově algoritmu si zaslouží další poznámku. Předpokládejme, že jsme nulový pad na délku M ≥ 2 N –1. To znamená, že a _n je rozšířeno na pole A _n délky M , kde A _n = a _n pro 0 ≤ n < N a A _n = 0 jinak - obvyklý význam „nulové výplně“. Nicméně, vzhledem k b _{k - n} termínu v konvoluce, jak pozitivní a negativní hodnoty n jsou potřebné pro b _n (poznamenat, že b _{- n} = b _n ). Periodické hranice implikované DFT pole s nulovým polstrováním znamenají, že - n je ekvivalentní M - n . Takže b _n je rozšířeno na pole B _n délky M , kde B ₀ = b ₀ , B _n = B _{M - n} = b _n pro 0 < n < N , a B _n = 0 jinak. A a B jsou poté FFTed, vynásobeny bodově a inverzní FFTed, aby se získala konvoluce a a b , podle obvyklé konvoluční věty.

Pojďme být také přesnější o tom, jaký typ konvoluce je vyžadován v Bluesteinově algoritmu pro DFT. Pokud by posloupnost b _n byla periodická v n s periodou N , pak by šlo o cyklickou konvoluci délky N a nulová výplň by byla pouze pro výpočetní pohodlí. To však obecně neplatí:

${\ displaystyle b_ {n + N} = e ^ {{\ frac {\ pi i} {N}} (n + N) ^ {2}} = b_ {n} e ^ {{\ frac {\ pi i } {N}} (2Nn + N ^ {2})} = (- 1) ^ {N} b_ {n}.}$

Proto je pro N i konvoluce cyklická, ale v tomto případě je N složená a normálně by se používal efektivnější FFT algoritmus, jako je Cooley – Tukey. Pro N zvláštní, nicméně, pak b _n je antiperiodic a my technicky mají negacyclic konvoluce délky N . Takové rozdíly však zmizí, když jedna nula vyloží a _n na délku alespoň 2 N −1, jak je popsáno výše. Možná je tedy nejjednodušší si to představit jako podmnožinu výstupů jednoduché lineární konvoluce (tj. Bez koncepčních „rozšíření“ dat, periodických či jiných).

z-transformace

Bluesteinův algoritmus lze také použít k výpočtu obecnější transformace založené na (jednostranné) z-transformaci (Rabiner et al. , 1969). Zejména může vypočítat jakoukoli transformaci formuláře:

${\ displaystyle X_ {k} = \ součet _ {n = 0} ^ {N-1} x_ {n} z ^ {nk} \ qquad k = 0, \ tečky, M-1,}$

pro libovolné komplexní číslo z a pro různá čísla N a M vstupů a výstupů. Vzhledem k Bluesteinovu algoritmu lze takovou transformaci použít například k získání jemněji rozmístěné interpolace určité části spektra (i když je frekvenční rozlišení stále omezeno celkovou dobou vzorkování, podobně jako u Zoom FFT), zvýšit libovolnost póly v analýze přenosové funkce atd.

Algoritmus byl nazván algoritmem chirp -transformace z, protože pro případ Fourierovy transformace (| z | = 1) je posloupnost b _n shora komplexním sinusoidem lineárně rostoucí frekvence, který se nazývá (lineární) chirp v radarové systémy.

Reference

Všeobecné

• Leo I. Bluestein, „Přístup lineárního filtrování k výpočtu diskrétní Fourierovy transformace,“ Northeast Electronics Research and Engineering Meeting Record 10 , 218-219 (1968).
• Lawrence R. Rabiner, Ronald W. Schafer a Charles M. Rader, „ Algoritmus chirp z-transformace a jeho aplikace ,“ Bell Syst. Tech. J. 48 , 1249-1292 (1969). Publikováno také v: Rabiner, Shafer a Rader, „ The chirp z-transform algorithm ,“ IEEE Trans. Audio Electroacoustics 17 (2), 86–92 (1969).
• DH Bailey a PN Swarztrauber, „Frakční Fourierova transformace a aplikace,“ SIAM Review 33 , 389-404 (1991). (Všimněte si, že tato terminologie pro z-transformaci je nestandardní: frakční Fourierova transformace obvykle označuje úplně jinou, spojitou transformaci.)
• Lawrence Rabiner, „Algoritmus cvrlikání z transformace - lekce serendipity,“ IEEE Signal Processing Magazine 21 , 118-119 (březen 2004). (Historický komentář.)

externí odkazy

• Algoritmus DSP pro frekvenční analýzu - Chirp-Z Transform (CZT)