チャープZ変換

チャープZ変換（CZT ）は、離散フーリエ変換（DFT）の一般化です。DFTがZ平面を単位円上の等間隔の点でサンプリングするのに対し、チャープZ変換はZ平面上の螺旋状の弧（ S平面上の直線に対応）に沿ってサンプリングします。[ 1 ] [ 2 ] DFT、実数DFT、ズームDFTはCZTの特殊なケースとして計算できます。

具体的には、チャープZ変換は、次のように定義される対数螺旋輪郭に沿った有限個の点z kにおけるZ変換を計算する。 [ 1 ] [ 3 ]

Xけ＝∑n＝0北−1×（n）zけ−n{\displaystyle X_{k}=\sum _{n=0}^{N-1}x(n)z_{k}^{-n}}
zけ＝あ⋅W−け、け＝0、1、…、M−1{\displaystyle z_{k}=A\cdot W^{-k},k=0,1,\dots ,M-1}

ここで、Aは複素開始点、Wは点間の複素比、Mは計算す​​る点の数です。

DFTと同様に、チャープZ変換はO(nlogn)回の演算で計算できます。逆チャープZ変換(ICZT)のO(NlogN )アルゴリズムは2003年[ 4 ] [ 5 ]と2019年[ 6 ]に発表されました。n＝最大（M、北）n=\max(M,N)

ブルースタインのアルゴリズム

ブルースタインのアルゴリズム[ 7 ] [ 8 ]はCZTを畳み込みとして表現し、 FFT /IFFTを使用して効率的に実装します。

DFTはCZTの特殊なケースであるため、素数サイズを含む任意のサイズの離散フーリエ変換（DFT）を効率的に計算できます。（素数サイズのFFT用のもう1つのアルゴリズムであるRaderのアルゴリズムも、DFTを畳み込みとして書き換えることで機能します。）これは1968年にLeo Bluesteinによって考案されました。[ 7 ] Bluesteinのアルゴリズムは、（片側） Z変換に基づいて、DFTよりも一般的な変換を計算するために使用できます（Rabinerら、1969年）。

DFTは次の式で定義される。

Xけ＝∑n＝0北−1×ne−2π私北nけけ＝0、…、北−1.{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.}

指数の積nkを恒等式に 置き換えると

nけ＝−（け−n）22+n22+け22{\displaystyle nk={\frac {-(kn)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2}}}

したがって次のようになります:

Xけ＝e−π私北け2∑n＝0北−1（×ne−π私北n2）eπ私北（け−n）2け＝0、…、北−1.{\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,\dots ,N-1.}

この合計は、次のように定義される 2 つのシーケンスa nとb nの畳み込みです。

1つのn＝×ne−π私北n2{\displaystyle a_{n}=x_{n}e^{-{\frac {\pi i}{N}}n^{2}}}
bn＝eπ私北n2、{\displaystyle b_{n}=e^{{\frac {\pi i}{N}}n^{2}},}

畳み込みの出力にN個の位相係数b k *を乗じたもの。つまり、

Xけ＝bけ∗（∑n＝0北−11つのnbけ−n）け＝0、…、北−1.{\displaystyle X_{k}=b_{k}^{*}\left(\sum _{n=0}^{N-1}a_{n}b_{kn}\right)\qquad k=0,\dots ,N-1.}

この畳み込みは、畳み込み定理により、FFT のペア (および事前に計算された複素チャープb nの FFT )で実行できます。重要な点は、これらの FFT の長さNが同じではないことです。このような畳み込みは、2 N –1以上の長さにゼロパディングすることによってのみ、FFT から正確に計算できます。特に、2 のべき乗またはその他の高度に合成されたサイズにパディングすることができ、その場合の FFT は、例えばCooley–Tukey アルゴリズムによってO( N log N ) 時間で効率的に実行できます。したがって、Bluestein のアルゴリズムは、合成サイズに対して Cooley–Tukey アルゴリズムよりも数倍遅くなるものの、素数サイズの DFT を O( N log N ) で計算する方法を提供します。

Bluestein のアルゴリズムにおける畳み込みのゼロ詰めの使用については、さらに説明しておく価値があります。長さM ≥ 2 N –1 にゼロ詰めするとします。これは、a nが長さMの配列A nに拡張されることを意味します。ここで、0 ≤ n < Nの場合はA n = a n、それ以外の場合はA n = 0 です (「ゼロ詰め」の通常の意味)。ただし、畳み込みのb k – n項があるため、 b nにはnの正と負の両方の値が必要です( b – n = b nであることに注意)。ゼロ詰めされた配列の DFT によって暗示される周期的境界は、 – nがM – nに等しいことを意味します。したがって、b nは長さMの配列B nに拡張されます。ここで、B 0 = b 0、0 < n < Nの場合はB n = B M – n = b n、それ以外の場合はB n = 0 です。 次に、 AとBを FFT し、点ごとに乗算し、逆 FFT して、通常の畳み込み定理に従って aとbの畳み込みを取得します。

ブルースタインのDFTアルゴリズムではどのような種類の畳み込みが必要なのか、より正確に説明しましょう。もし系列b n がnにおいて周期Nで周期的であれば、長さNの巡回畳み込みとなり、ゼロパディングは計算上の便宜のためだけに行われます。しかし、一般的にはそうではありません。

bn+北＝eπ私北（n+北）2＝bn[eπ私北（2北n+北2）]＝（−1）北bn。{\displaystyle 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}.}

したがって、Nが偶数の場合、畳み込みは巡回畳み込みとなりますが、この場合、Nは複合FFTアルゴリズムであるため、通常はCooley-Tukeyなどのより効率的なFFTアルゴリズムを使用します。一方、 Nが奇数の場合、b nは反周期的となり、技術的には長さNの負巡回畳み込みとなります。ただし、前述のようにa nをゼロパディングして少なくとも2 N −1の長さにすると、このような区別はなくなります。したがって、これを単純な線形畳み込みの出力のサブセット（つまり、周期的であろうとなかろうと、データの概念的な「拡張」がない）と考えるのがおそらく最も簡単です。

Z変換

ブルースタインのアルゴリズムは、（片側） Z変換（Rabiner et al. , 1969）に基づく、より一般的な変換を計算するためにも使用できます。特に、以下の形式の任意の変換を計算できます。

Xけ＝∑n＝0北−1×nznけけ＝0、…、M−1、{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}z^{nk}\qquad k=0,\dots ,M-1,}

任意の複素数zと、異なる入力数Nと出力数Mに対して、このような変換が行えます。ブルースタインのアルゴリズムを用いると、このような変換は、例えばスペクトルの一部をより細かく補間したり（ただし、周波数分解能はZoom FFTと同様に、総サンプリング時間によって制限されます）、伝達関数解析における任意の極を強調したりするために使用できます。

このアルゴリズムは、フーリエ変換の場合 (| z | = 1)、上記のシーケンスb n が線形に増加する周波数の複素正弦波であり、レーダーシステムでは (線形)チャープと呼ばれるため、チャープZ 変換アルゴリズムと呼ばれています。

参照

参考文献

  1. ^ a bチャープZ変換とその応用に関する研究- シリング、スティーブ・アラン
  2. ^ "Chirp Z変換 - MATLAB czt" . www.mathworks.com . 2016年9月22日閲覧。
  3. ^ Martin, Grant D. (2005年11月). 「MATLAB®によるチャープZ変換スペクトルズーム最適化」(PDF) .
  4. ^ボスタン、アリン (2003)。計算形式の基本的な操作を行うアルゴリズムの有効性(PDF) (PhD)。エコールポリテクニック。
  5. ^ Bostan, Alin; Schost, Éric (2005). 「多項式評価と特殊点集合上の補間」Journal of Complexity . 21 (4): 420– 446. doi : 10.1016/j.jco.2004.09.009 .
  6. ^エンジニアが信号処理における50年来の難問を解決 – 逆チャープZ変換、アイオワ州立大学、2019年10月10日
  7. ^ a b Bluestein, L. (1970-12-01). 「離散フーリエ変換の計算に対する線形フィルタリングアプローチ」. IEEE Transactions on Audio and Electroacoustics . 18 (4): 451– 455. doi : 10.1109/TAU.1970.1162132 . ISSN 0018-9278 . 
  8. ^ 「BluesteinのFFTアルゴリズム」 DSPRelated.com。

一般的な

「 https://en.wikipedia.org/w/index.php?title=Chirp_Z-transform&oldid=1304191291」から取得