chirp z-transform

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /chirp-z-transform#noredirect を利用してください。
name
chirp z-transform
short description
chirp z-transform は、有限列の z-transform を等比数列を成す点で評価した値を計算するアルゴリズムの一つ。 長さが $2$ の冪でない離散フーリエ変換の計算などに使用できる。 時間計算量/空間計算量は、$\mathrm{M}(M, N)$ を長さ $M, N$ の列の畳み込みに必要な計算量として、$\mathrm{M}(n, n + m - 1) + \Theta(n + m)$ である。
input
体 $\mathbb{K}$ 上の長さ $n$ の列 $x$、$a \in \mathbb{K}, w \in \mathbb{K}$、整数 $m$
output
各 $0 \leq k \lt m$ に対し、$X _ {k} = \sum _ {i = 0} ^ {n - 1} x _ {i} (a ^ {- 1} w ^ {k}) ^ {i}$
time complexity
$\mathrm{M}(n, n + m - 1) + \Theta(n + m)$
space complexity
$\mathrm{M}(n, n + m - 1) + \Theta(n + m)$

概要

chirp z-transform は、有限列の Z 変換を等比数列を成す点で評価した値を計算するアルゴリズムの一つ。 長さが $2$ の冪でない離散フーリエ変換の計算などに使用できる。 時間計算量/空間計算量は、$\mathrm{M}(M, N)$ を長さ $M, N$ の列の畳み込みに必要な計算量として、$\mathrm{M}(n, n + m - 1) + \Theta(n + m)$ である。

$a$ が $- 1$ 乗されているのは Z 変換に由来するもので、取り除けば多項式の多点評価と解釈できる ($a ^ {- 1}$ を $a$ と定義し直せば相互に変換可能である)。

詳細

$w = 0$ の場合は自明であるから、以降 $w \neq 0$ とする。

三角数を $t _ {i} \coloneqq \frac{i(i - 1)}{2}$ と書くことにすると、以下の等式が成り立つ。 \(ki = t _ {k + i} - t _ {k} - t _ {i}\)

これを用いて $X _ {k}$ を変形すると以下のようになる。 \(\begin{align*} X _ {k} &= \sum _ {i = 0} ^ {n - 1} x _ {i} (a ^ {- 1} w ^ {k}) ^ {i} \cr &= \sum _ {i = 0} ^ {n - 1} x _ {i} a ^ {- i} w ^ {ki} \cr &= \sum _ {i = 0} ^ {n - 1} x _ {i} a ^ {- i} w ^ {t _ {k + i}} w ^ {- t _ {k}} w ^ {- t _ {i}} \cr &= w ^ {- t _ {k}} \sum _ {i = 0} ^ {n - 1} (x _ {i} a ^ {- i} w ^ {- t _ {i}}) w ^ {t _ {k + i}} \end{align*}\) 最後の式は畳み込みの形になっている。 実際、長さ $n$ の列 $y$ と長さ $n + m - 1$ の列 $v$ を \(\begin{aligned} y _ {i} &\coloneqq x _ {i} a ^ {- i} w ^ {- t _ {i}} \cr v _ {i} &\coloneqq w ^ {t _ {i}} \end{aligned}\) と定義すれば \(\begin{align*} X _ {k} &= w ^ {- t _ {k}} \sum _ {i = 0} ^ {n - 1} y _ {i} v _ {k + i} \cr &= w ^ {- t _ {k}} \sum _ {i + j = n - 1 + k} y _ {n - 1 - i} v _ {j} \end{align*}\) となる。

関係式 $w ^ {t _ {i + 1}} = w ^ {t _ {i}} w ^ {i}$ を用いることで $y, v$ は $\Theta(n + m)$ で計算できる。 よって全体の計算量は、これに畳み込みに掛かる時間計算量を加えた $\mathrm{M}(n, n + m - 1) + \Theta(n + m)$ となる。

畳み込みの結果のうち第 $n - 1$ 項から第 $n + m - 2$ 項までを使用するため、畳み込みは長さ $n + m - 1$ 以上の巡回畳み込みでも問題ない。 $\mathbb{K} = \mathbb{C}$ や $\mathbb{K} = \mathbb{F} _ {p}$ の場合は離散フーリエ変換を用いた巡回畳み込みが効率的に行えるため、定数倍高速化が見込める。

その他

参考文献

  1. Rabiner, L., Schafer, R. W., & Rader, C. (1969). The chirp z-transform algorithm. IEEE transactions on audio and electroacoustics, 17(2), 86-92.
    • chirp z-transform が提案された論文
  2. Crandall, R., & Pomerance, C. B. (2006). Prime numbers: a computational perspective (Vol. 182). Springer Science & Business Media.
    • 参考文献 1 のアルゴリズムにおいて三角数を用いて $w ^ {1 / 2}$ の計算を不要にする方法が説明されている
  3. Bostan, A., & Schost, É. (2005). Polynomial evaluation and interpolation on special sets of points. Journal of Complexity, 21(4), 420-446.
    • 参考文献 2 のアルゴリズムにおいて三角数の使い方を少しだけ変えている。 本ページはこのアルゴリズムを説明している。
  4. Bostan, A., Lecerf, G., & Schost, É. (2003, August). Tellegen's principle into practice. In Proceedings of the 2003 international symposium on Symbolic and algebraic computation (pp. 37-44).
    • 離散フーリエ変換を用いた畳み込みを転置するアルゴリズムの導出についての記述がある