Chirp Z-transform

Chirp Z-transformen ( CZT ) är en generalisering av den diskreta Fouriertransformen (DFT). Medan DFT samplar Z-planet vid likformigt åtskilda punkter längs enhetscirkeln, så transformerar chirp-Z-omvandlingsproverna längs spiralbågar i Z-planet, motsvarande raka linjer i S- planet . DFT, riktig DFT och zoom DFT kan beräknas som specialfall av CZT.

Specifikt beräknar chirp Z-transformen Z-transformen vid ett ändligt antal punkter zk _längs en logaritmisk spiralkontur , definierad som:

$X_{k}=\summa _{n=0}^{N-1}x(n)z_{k}^{- n}$

$z_{k}=A\cdot W^{-k},k=0,1,\dots ,M -1$

där A är den komplexa utgångspunkten, W är det komplexa förhållandet mellan punkter och M är antalet punkter som ska beräknas.

Liksom DFT kan chirp Z-transformen beräknas i O( n log n ) operationer där $n=\max(M,N)$ . En O( N log N )-algoritm för den inversa chirp Z-transformen (ICZT) beskrevs 2003 och 2019.

Bluesteins algoritm

Bluesteins algoritm uttrycker CZT som en faltning och implementerar den effektivt med FFT /IFFT.

Eftersom DFT är ett specialfall av CZT, tillåter detta effektiv beräkning av diskret Fouriertransform (DFT) av godtyckliga storlekar, inklusive primstorlekar . (Den andra algoritmen för FFTs av primära storlekar, Raders algoritm , fungerar också genom att skriva om DFT som en faltning.) Den skapades 1968 av Leo Bluestein. Bluesteins algoritm kan användas för att beräkna mer allmänna transformationer än DFT, baserat på den (ensidiga) z-transformen (Rabiner et al. , 1969).

Kom ihåg att DFT definieras av formeln

$X_{k}=\summa _{n=0}^{N-1} x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.$

Om vi ​​ersätter produkten nk i exponenten med identiteten

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

vi får alltså:

$X_ {k}=e^{-{\frac {\pi i}{N}}k^{2}}\sum _{n=0}^{N-1}\left(x_{n}e^{ -{\frac {\pi i}{N}}n^{2}}\right)e^{{\frac {\pi i}{N}}(kn)^{2}}\qquad k=0 ,\dots ,N-1.$

Denna summering är exakt en faltning av de två sekvenserna a _n och b _n definierade av:

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

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

med utsignalen från faltningen multiplicerad med N fasfaktorer b _k ^* . Det är:

$X_{k}=b_{k}^{*}\left(\summa _{n=0}^{N-1}a_{n}b_{kn}\right)\qquad k=0,\dots ,N-1.$

Denna faltning kan i sin tur utföras med ett par FFT:er (plus den förberäknade FFT för komplex chirp b _n ) via faltningssatsen . Nyckelpunkten är att dessa FFT:er inte är av samma längd N : en sådan faltning kan beräknas exakt från FFT:er endast genom att nollutfylla den till en längd som är större än eller lika med 2 N -1. I synnerhet kan man paddla till en potens av två eller någon annan mycket sammansatt storlek, för vilken FFT effektivt kan utföras av t.ex. Cooley-Tukey-algoritmen i O( N log N ) tid. Således tillhandahåller Bluesteins algoritm ett O( N log N ) sätt att beräkna prime-size DFTs, om än flera gånger långsammare än Cooley-Tukey-algoritmen för sammansatta storlekar.

₀₀ Användningen av nollutfyllnad för faltningen i Bluesteins algoritm förtjänar ytterligare en kommentar. Antag att vi nollställer till en längd M ≥ 2 N –1. Detta betyder att a _n utökas till en matris A _n med längden M , där A _n = a _n för 0 ≤ n < N och An = 0 annars – den vanliga betydelsen av "nollutfyllnad" _. På grund av termen b _{k – n} i faltningen krävs dock både positiva och negativa värden på n för b _n (notera att b _{– n} = b _n ). De periodiska gränserna som antyds av DFT för den nollutfyllda matrisen betyder att – n är ekvivalent med M – n . Således utökas bn _till en matris Bn med längden M _{, - n} där B = b _, Bn = BM _{n =} bn för 0 < n < N , och Bn = _n = 0 otherwise. A and B are then FFTed, multiplied pointwise, and inverse FFTed to obtain the convolution of a and b, according to the usual convolution theorem.

Låt oss också vara mer exakta om vilken typ av faltning som krävs i Bluesteins algoritm för DFT. Om sekvensen bn var periodisk i n med period N , så skulle det vara en cyklisk faltning av längden N , och nollutfyllningen skulle endast vara för beräkningsbekvämlighet _. Detta är dock inte generellt fallet:

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

Därför är även faltningen för N cyklisk, men i det här fallet är N sammansatt och man skulle normalt använda en mer effektiv FFT-algoritm som Cooley–Tukey. För N udda är dock b _n antiperiodisk och vi har tekniskt sett en negacyklisk faltning av längden N . Sådana distinktioner försvinner dock när man nollställer a _n till en längd av minst 2 N −1 som beskrivits ovan. Det är därför kanske lättast att tänka på det som en delmängd av utdata från en enkel linjär faltning (dvs inga konceptuella "utvidgningar" av data, periodiska eller på annat sätt).

z-transformeras

Bluesteins algoritm kan också användas för att beräkna en mer allmän transformation baserad på den (ensidiga) z-transformen (Rabiner et al., 1969). I synnerhet kan den beräkna vilken transformation som helst av formen:

$X_{k}=\summa _{n=0}^{N-1}x_{n}z ^{nk}\qquad k=0,\dots ,M-1,$

för ett godtyckligt komplext tal z och för olika tal N och M för ingångar och utgångar. Med tanke på Bluesteins algoritm kan en sådan transformering användas, till exempel, för att erhålla en finare interpolation av någon del av spektrumet (även om frekvensupplösningen fortfarande är begränsad av den totala samplingstiden, liknande en Zoom FFT), förbättra godtyckligt poler i överföringsfunktionsanalyser m.m.

Algoritmen kallades chirp z-transform-algoritmen eftersom, för Fourier-transform-fallet (| z | = 1), sekvensen b _n ovanifrån är en komplex sinusoid med linjärt ökande frekvens, som kallas en (linjär) chirp i radarsystem .

Se även

• Fraktionell Fouriertransform

Allmän

• Leo I. Bluestein, "En linjär filtreringsmetod för beräkningen av den diskreta Fouriertransformen," Northeast Electronics Research and Engineering Meeting Record 10 , 218-219 (1968).
• Lawrence R. Rabiner, Ronald W. Schafer och Charles M. Rader, " The chirp z-transform algorithm and its application," Bell Syst. Tech. J. 48 , 1249-1292 (1969). Även publicerad i: Rabiner, Shafer och Rader, " The chirp z-transform algorithm", IEEE Trans. Audio Electroacoustics 17 (2), 86–92 (1969).
• DH Bailey och PN Swarztrauber, "The fraktional Fourier transform and applications," SIAM Review 33 , 389-404 (1991). (Observera att denna terminologi för z-transformen är icke-standard: en bråkdel Fourier-transform hänvisar konventionellt till en helt annan, kontinuerlig transformation.)
• Lawrence Rabiner, "The chirp z-transform algorithm - a lesson in serendipity," IEEE Signal Processing Magazine 21 , 118-119 (mars 2004). (Historisk kommentar.)
• Vladimir Sukhoy och Alexander Stoytchev: "Generalisera den omvända FFT från enhetscirkeln", (okt 2019). # Fri tillgång.
• Vladimir Sukhoy och Alexander Stoytchev: "Numerisk felanalys av ICZT-algoritmen för chirp-konturer på enhetscirkeln", Sci Rep 10, 4852 (2020).

externa länkar

• En DSP-algoritm för frekvensanalys - Chirp-Z Transform (CZT)
• Att lösa ett 50-årigt pussel i signalbehandling, del två