Transformacja Z Chirpa

Chirp Z-transform ( CZT ) jest uogólnieniem dyskretnej transformaty Fouriera (DFT). Podczas gdy DFT próbkuje płaszczyznę Z w równomiernie rozmieszczonych punktach wzdłuż okręgu jednostkowego, chirp Z przekształca próbki wzdłuż łuków spiralnych w płaszczyźnie Z, odpowiadających liniom prostym w płaszczyźnie S. DFT, rzeczywisty DFT i zoom DFT można obliczyć jako specjalne przypadki CZT.

Konkretnie, transformacja chirp Z oblicza transformatę Z w skończonej liczbie punktów zk _wzdłuż konturu spirali logarytmicznej , zdefiniowanej jako:

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

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

gdzie A to złożony punkt początkowy, W to złożony stosunek punktów, a M to liczba punktów do obliczenia.

Podobnie jak DFT, transformatę chirp Z można obliczyć w operacjach O( n log n ), gdzie $n=\max(M,N)$ . Algorytm O ( N log N ) dla odwrotnej transformacji chirp Z (ICZT) został opisany w 2003 i 2019 roku.

Algorytm Bluesteina

Algorytm Bluesteina wyraża CZT jako splot i skutecznie go implementuje za pomocą FFT /IFFT.

Ponieważ DFT jest szczególnym przypadkiem CZT, pozwala to na wydajne obliczenie dyskretnej transformaty Fouriera (DFT) dowolnych rozmiarów, w tym rozmiarów pierwszych . (Inny algorytm FFT o rozmiarach pierwszych, algorytm Radera , również działa poprzez przepisanie DFT jako splot). Został wymyślony w 1968 roku przez Leo Bluesteina. Algorytm Bluesteina może być użyty do obliczenia bardziej ogólnych przekształceń niż DFT, w oparciu o (jednostronną) transformację z (Rabiner i in. , 1969).

Przypomnijmy, że DFT jest zdefiniowany przez formułę

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

Jeśli zastąpimy iloczyn nk w wykładniku przez tożsamość

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

otrzymujemy w ten sposób:

${\ Displaystyle 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 ,\kropki ,N-1.}$

Sumowanie to jest dokładnie splotem dwóch ciągów a _n i b _n zdefiniowanych przez:

${\ Displaystyle a_ {n} = x_ {n} e ^ {- {\ Frac {\ pi ja} {N}} n ^ {2}}}$

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

z wyjściem splotu pomnożonym przez N współczynników fazowych b _k ^* . To jest:

${\ Displaystyle X_ {k} = b_ {k} ^ {*} \ lewo (\ suma _{n=0}^{N-1}a_{n}b_{kn}\right)\qquad k=0,\kropki ,N-1.}$

Ten splot z kolei można wykonać za pomocą pary FFT (plus wstępnie obliczona FFT złożonego chirp b _n ) za pomocą twierdzenia o splotach . Kluczową kwestią jest to, że te FFT nie mają tej samej długości N : taki splot można obliczyć dokładnie z FFT tylko przez wypełnienie go zerami do długości większej lub równej 2 N –1. W szczególności można dopasowywać do potęgi dwóch lub innego wysoce złożonego rozmiaru, dla którego FFT można skutecznie wykonać np. algorytmem Cooleya-Tukeya w czasie O ( N log N ). Zatem algorytm Bluesteina zapewnia sposób O ( N log N ) obliczania DFT w rozmiarze pierwszym, aczkolwiek kilka razy wolniejszy niż algorytm Cooleya-Tukeya dla rozmiarów złożonych.

₀₀ Użycie dopełnienia zerami dla splotu w algorytmie Bluesteina zasługuje na dodatkowy komentarz. Załóżmy, że zerujemy do długości M ≥ 2 N –1. Oznacza to, że a _n jest rozszerzone do tablicy A _n o długości M , gdzie A _n = a _n dla 0 ≤ n < N i A _n = 0 w przeciwnym razie — zwykłe znaczenie „dopełniania zerami”. Jednak ze względu na b _{k – n} w splocie, dla b _n wymagane są zarówno dodatnie, jak i ujemne wartości n (zauważ, że b _{– n} = b _n ). Okresowe granice implikowane przez DFT tablicy wypełnionej zerami oznaczają, że – n jest równoważne M – n . Zatem b _n jest rozszerzone do tablicy B _n o długości M , gdzie B = b , B _n = B _{M – n} = b _n dla 0 < n < N , a B _n = 0 w przeciwnym razie. A i B są następnie poddawane FFT, mnożone punktowo i odwrotne FFT w celu uzyskania splotu aib , zgodnie ze zwykłym twierdzeniem o splotach.

Określmy też dokładniej, jaki typ splotu jest wymagany w algorytmie Bluesteina dla DFT. Gdyby sekwencja b _n była okresowa w n z okresem N , to byłby to cykliczny splot o długości N , a dopełnienie zerami byłoby tylko dla wygody obliczeniowej. Jednak na ogół tak nie jest:

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

Dlatego dla N nawet splot jest cykliczny, ale w tym przypadku N jest złożony i normalnie należałoby użyć bardziej wydajnego algorytmu FFT, takiego jak Cooley – Tukey. Jednak dla N nieparzystych b _n jest antyokresowe i technicznie mamy splot negacykliczny o długości N . Jednak takie rozróżnienia znikają, gdy jeden wstawia zera _n do długości co najmniej 2 N -1, jak opisano powyżej. Dlatego być może najłatwiej jest myśleć o tym jako o podzbiorze danych wyjściowych prostego splotu liniowego (tj. bez pojęciowych „rozszerzeń” danych, okresowych lub innych).

przekształcenia z

Algorytm Bluesteina może być również użyty do obliczenia bardziej ogólnej transformacji opartej na (jednostronnej) transformacji z (Rabiner i in. , 1969). W szczególności może obliczyć dowolne przekształcenie postaci:

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

dla dowolnej liczby zespolonej z oraz dla różnych liczb N i M wejść i wyjść. Biorąc pod uwagę algorytm Bluesteina, taka transformacja może być wykorzystana na przykład do uzyskania dokładniejszej interpolacji pewnej części widma (chociaż rozdzielczość częstotliwościowa jest nadal ograniczona całkowitym czasem próbkowania, podobnie jak w przypadku Zoom FFT), zwiększenia arbitralnej bieguny w analizach funkcji przenoszenia itp.

Algorytm został nazwany algorytmem chirp z-transform, ponieważ w przypadku transformacji Fouriera (| z | = 1) sekwencja b _n z góry jest złożoną sinusoidą o liniowo rosnącej częstotliwości, która jest nazywana (liniowym) chirp w systemy radarowe .

Zobacz też

• Ułamkowa transformata Fouriera

Ogólny

• Leo I. Bluestein, „Podejście z filtrowaniem liniowym do obliczeń dyskretnej transformaty Fouriera”, Northeast Electronics Research and Engineering Meeting Record 10 , 218-219 (1968).
• Lawrence R. Rabiner, Ronald W. Schafer i Charles M. Rader, „ Algorytm transformacji Z chirp i jego zastosowanie ”, Bell Syst. Technika J.48 1249-1292 (1969). Opublikowano także w: Rabiner, Shafer i Rader, „ The chirp z-transform Algorytm ”, IEEE Trans. Audio Electroacoustics 17 (2), 86–92 (1969).
• DH Bailey i PN Swarztrauber, „Ułamkowa transformata Fouriera i zastosowania”, SIAM Review 33 , 389-404 (1991). (Zauważ, że ta terminologia dotycząca transformacji z jest niestandardowa: ułamkowa transformata Fouriera konwencjonalnie odnosi się do zupełnie innej, ciągłej transformacji).
• Lawrence Rabiner, „Algorytm przekształcenia chirp z-transform — lekcja szczęścia”, IEEE Signal Processing Magazine 21 , 118-119 (marzec 2004). (Komentarz historyczny).
• Vladimir Sukhoy i Alexander Stoytchev: „Uogólnienie odwrotnej FFT poza okręgiem jednostkowym” (październik 2019). # Otwarty dostęp.
• Vladimir Sukhoy i Alexander Stoytchev: „Numeryczna analiza błędów algorytmu ICZT dla konturów chirp na okręgu jednostkowym” , Sci Rep 10, 4852 (2020).

Linki zewnętrzne

• Algorytm DSP do analizy częstotliwościowej – transformacja Chirp-Z (CZT)
• Rozwiązanie zagadki sprzed 50 lat w przetwarzaniu sygnałów, część druga