複素 ふくそ 関数 かんすう f (x )離散 りさん 変換 へんかん 複素 ふくそ 関数 かんすう F (t )以下 いか 定義 ていぎ
F
(
t
)
=
∑
x
=
0
N
−
1
f
(
x
)
exp
(
−
i
2
π ぱい t
x
N
)
.
{\displaystyle F(t)=\sum _{x=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi tx}{N}}\right).}
このとき、{x = 0, 1, 2, ..., N − 1} を標本 ひょうほん 点 てん 言 い
これを直接 ちょくせつ 計算 けいさん 時間 じかん 計算 けいさん 量 りょう ランダウの記号 きごう を用 もち 表現 ひょうげん O (N 2 )
高速 こうそく 変換 へんかん 結果 けっか 次数 じすう N が2の累乗 るいじょう O (N log N )計算 けいさん 量 りょう 得 え 一般 いっぱん 的 てき 次数 じすう N = ∏ ni 素因数 そいんすう 分解 ぶんかい O (N ∑n i 計算 けいさん 量 りょう 次数 じすう 2 の累乗 るいじょう 最 もっと 高速 こうそく 計算 けいさん 単純 たんじゅん 0 詰 つ 次数 じすう 調整 ちょうせい
高速 こうそく 変換 へんかん 使 つか 畳 たた 込 こ 積分 せきぶん 計算 けいさん 高速 こうそく 求 もと 計算 けいさん 量 りょう O (N 2 )O (N log N )落 お
現在 げんざい 初期 しょき 手法 しゅほう [1] 高速 こうそく 化 か 使用 しよう
逆 ぎゃく 変換 へんかん 正 せい 変換 へんかん 同 おな 考 かんが 良 よ 指数 しすう 符号 ふごう 逆 ぎゃく 係数 けいすう 1/N が掛 か
高速 こうそく 変換 へんかん 中 ちゅう 符号 ふごう 逆転 ぎゃくてん 一々 いちいち 分岐 ぶんき 分岐 ぶんき 判定 はんてい 時間 じかん 落 お 一方 いっぽう 正 せい 変換 へんかん 逆 ぎゃく 変換 へんかん 両方 りょうほう 用意 ようい 考 かんが 共通 きょうつう 部分 ぶぶん 多 おお 無駄 むだ 多 おお 複素 ふくそ 共役 きょうやく 使 つか 次 つぎ 方法 ほうほう 考 かんが
離散 りさん 変換 へんかん
F
(
t
)
=
∑
x
=
0
N
−
1
f
(
x
)
exp
(
−
i
2
π ぱい t
x
N
)
{\displaystyle F(t)=\sum _{x=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi tx}{N}}\right)}
で定義 ていぎ 逆 ぎゃく 変換 へんかん
f
(
x
)
=
1
N
∑
t
=
0
N
−
1
F
(
t
)
exp
(
i
2
π ぱい
t
x
N
)
=
1
N
∑
t
=
0
N
−
1
F
(
t
)
¯
exp
(
−
i
2
π ぱい t
x
N
)
¯
{\displaystyle f(x)={\frac {1}{N}}\sum _{t=0}^{N-1}F(t)\exp \left(i{\frac {2\pi {tx}}{N}}\right)={\frac {1}{N}}{\overline {\sum _{t=0}^{N-1}{\overline {F(t)}}\exp \left(-i{\frac {2\pi tx}{N}}\right)}}}
となる。
このため、F (t )離散 りさん 逆 ぎゃく 変換 へんかん 求 もと
(1) 複素 ふくそ 共役 きょうやく 取 と F (t )求 もと
(2) F (t )正 せい 変換 へんかん 離散 りさん 変換 へんかん 高速 こうそく 変換 へんかん 行 おこな
(3) その結果 けっか 複素 ふくそ 共役 きょうやく 取 と N で割 わ とすれば良 よ 正 せい 変換 へんかん 高速 こうそく 変換 へんかん 逆 ぎゃく 変換 へんかん 容易 ようい 作 つく
クーリー–テューキー型 がた 代表 だいひょう 的 てき 高速 こうそく 変換 へんかん
分割 ぶんかつ 統治 とうち 法 ほう 使 つか N = N 1 N 2 変換 へんかん 小 ちい N 1 N 2 変換 へんかん 分割 ぶんかつ 高速 こうそく 化 か 図 はか
最 もっと 知 し 型 がた 変換 へんかん N /2変換 へんかん 分割 ぶんかつ 2 の累乗 るいじょう 次数 じすう 限定 げんてい 一般 いっぱん 的 てき 次数 じすう 2 の累乗 るいじょう 素因数 そいんすう 偶数 ぐうすう 奇数 きすう 別々 べつべつ 分岐 ぶんき
伝統 でんとう 的 てき 処理 しょり 実装 じっそう 多 おお 再帰 さいき 的 てき 処理 しょり 系統 けいとう 再帰 さいき 実現 じつげん
クーリー–テューキー型 がた 変換 へんかん 小 ちい 変換 へんかん 分解 ぶんかい 後述 こうじゅつ 他 ほか 離散 りさん 係数 けいすう 任意 にんい 組 く 合 あ N ≤ 8分解 ぶんかい 固定 こてい 次数 じすう 高速 こうそく 切 き 替 か 多 おお
データ数 すう 離散 りさん 変換 へんかん 模 も 式 しき 図 ず 時計 とけい 模 も 図形 ずけい 乗 じょう 根 ね 一 ひと 表 あらわ 時計 とけい 針 はり 向 む 色 いろ 乗 じょう 根 ね 偏 へん 角 かく 表 あらわ 図 ず 表 あらわ 行列 ぎょうれつ 列 れつ 離散 りさん 変換 へんかん 得 え 上 うえ 図 ず 表 あらわ 列 れつ 並 なら 替 が 行 おこな 元 もと 行列 ぎょうれつ 数 すう 離散 りさん 変換 へんかん 分解 ぶんかい 繰 く 返 かえ 最終 さいしゅう 的 てき 数 すう 変換 へんかん 帰着 きちゃく データ数 すう 離散 りさん 変換 へんかん 模 も 式 しき 図 ず 色 いろ 乗 じょう 根 ね 偏 へん 角 かく 表 あらわ 演算 えんざん 元 もと 行列 ぎょうれつ 最終 さいしゅう 的 てき 数 すう 離散 りさん 変換 へんかん 分解 ぶんかい FFTのバタフライ演算 えんざん 離散 りさん 係数 けいすう 1 の原始 げんし N 乗 の 根 ね WN = e −2π ぱい N 使 つか 次 つぎ 表 あらわ
F
(
t
)
=
∑
x
=
0
N
−
1
f
(
x
)
W
N
t
x
.
{\displaystyle F(t)=\sum _{x=0}^{N-1}f(x)W_{N}^{tx}.}
例 たと N = 4
F
(
t
)
=
X
t
{\displaystyle F(t)=X_{t}}
f
(
k
)
=
x
k
{\displaystyle f(k)=x_{k}}
離散 りさん 係数 けいすう 行列 ぎょうれつ 用 もち 表現 ひょうげん W = W 4 略記 りゃっき
[
X
0
X
1
X
2
X
3
]
=
[
W
0
W
0
W
0
W
0
W
0
W
1
W
2
W
3
W
0
W
2
W
4
W
6
W
0
W
3
W
6
W
9
]
[
x
0
x
1
x
2
x
3
]
{\displaystyle {\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}={\begin{bmatrix}W^{0}&W^{0}&W^{0}&W^{0}\\W^{0}&W^{1}&W^{2}&W^{3}\\W^{0}&W^{2}&W^{4}&W^{6}\\W^{0}&W^{3}&W^{6}&W^{9}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\end{bmatrix}}}
となる。入力 にゅうりょく 列 れつ xk を添字 そえじ 分 わ 以下 いか 変形 へんけい
[
X
0
X
1
X
2
X
3
]
=
[
W
0
W
0
W
0
W
0
W
0
W
2
W
1
W
3
W
0
W
4
W
2
W
6
W
0
W
6
W
3
W
9
]
[
x
0
x
2
x
1
x
3
]
=
[
W
0
W
0
W
0
W
0
W
0
W
0
W
0
W
2
W
1
W
0
W
1
W
2
W
0
W
0
W
2
W
0
W
2
W
0
W
0
W
2
W
3
W
0
W
3
W
2
]
[
x
0
x
2
x
1
x
3
]
{\displaystyle {\begin{aligned}{\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}&={\begin{bmatrix}W^{0}&W^{0}&W^{0}&W^{0}\\W^{0}&W^{2}&W^{1}&W^{3}\\W^{0}&W^{4}&W^{2}&W^{6}\\W^{0}&W^{6}&W^{3}&W^{9}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}\\&={\begin{bmatrix}W^{0}&W^{0}&W^{0}W^{0}&W^{0}W^{0}\\W^{0}&W^{2}&W^{1}W^{0}&W^{1}W^{2}\\W^{0}&W^{0}&W^{2}W^{0}&W^{2}W^{0}\\W^{0}&W^{2}&W^{3}W^{0}&W^{3}W^{2}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}\end{aligned}}}
(
∵
W
k
+
N
=
W
k
{\displaystyle \because W^{k+N}=W^{k}}
すると、サイズ 2 のFFTの演算 えんざん 結果 けっか 用 もち 表現 ひょうげん 分割 ぶんかつ
[
X
0
X
1
X
2
X
3
]
=
[
1
0
W
0
0
0
1
0
W
1
1
0
W
2
0
0
1
0
W
3
]
[
W
2
0
W
2
0
0
0
W
2
0
W
2
1
0
0
0
0
W
2
0
W
2
0
0
0
W
2
0
W
2
1
]
[
x
0
x
2
x
1
x
3
]
{\displaystyle {\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}={\begin{bmatrix}1&0&W^{0}&0\\0&1&0&W^{1}\\1&0&W^{2}&0\\0&1&0&W^{3}\end{bmatrix}}\,{\begin{bmatrix}W_{2}^{0}&W_{2}^{0}&0&0\\W_{2}^{0}&W_{2}^{1}&0&0\\0&0&W_{2}^{0}&W_{2}^{0}\\0&0&W_{2}^{0}&W_{2}^{1}\end{bmatrix}}\,{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}}
また、この分割 ぶんかつ 手順 てじゅん 図 ず 蝶 ちょう 図 ず バタフライ演算 えんざん とも呼 よ
バタフライ演算 えんざん 計算 けいさん 機上 きじょう ビット反転 はんてん で実現 じつげん DSP の中 なか 演算 えんざん 容易 ようい 反転 はんてん アドレッシング を備 そな
FFTの原理 げんり N = PQ N 次 じ 離散 りさん 変換 へんかん P 次 じ 離散 りさん 変換 へんかん Q 次 じ 離散 りさん 変換 へんかん 分解 ぶんかい [2]
N 次 じ 離散 りさん 変換 へんかん
F
(
n
)
=
∑
k
=
0
N
−
1
f
(
k
)
exp
(
−
2
π ぱい i
n
k
N
)
{\displaystyle F(n)=\sum _{k=0}^{N-1}f(k)\exp \left(-2\pi i{\frac {nk}{N}}\right)}
を、n = 0, 1, ..., N − 1計算 けいさん 考 かんが n k 次 つぎ 書 か 換 か 0 ≤ n ≤ N − 1 また 0 ≤ k ≤ N − 1 である。
n
=
s
Q
+
r
0
≤
s
≤
P
−
1
,
0
≤
r
≤
Q
−
1
k
=
q
P
+
p
0
≤
p
≤
P
−
1
,
0
≤
q
≤
Q
−
1
{\displaystyle {\begin{aligned}n&=sQ+r\qquad 0\leq s\leq P-1,\,0\leq r\leq Q-1\\k&=qP+p\qquad 0\leq p\leq P-1,\;0\leq q\leq Q-1\end{aligned}}}
すると
F
(
n
)
=
F
(
s
Q
+
r
)
=
∑
p
=
0
P
−
1
∑
q
=
0
Q
−
1
f
(
q
P
+
p
)
exp
(
−
2
π ぱい i
(
q
P
+
p
)
(
s
Q
+
r
)
P
Q
)
=
∑
p
=
0
P
−
1
∑
q
=
0
Q
−
1
f
(
q
P
+
p
)
exp
(
−
2
π ぱい i
(
r
q
Q
+
s
p
P
+
p
r
P
Q
)
)
=
∑
p
=
0
P
−
1
[
exp
(
−
2
π ぱい i
(
s
p
P
+
p
r
P
Q
)
)
∑
q
=
0
Q
−
1
f
(
q
P
+
p
)
exp
(
−
2
π ぱい i
r
q
Q
)
]
{\displaystyle {\begin{aligned}F(n)&=F(sQ+r)=\sum _{p=0}^{P-1}\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {(qP+p)(sQ+r)}{PQ}}\right)\\&=\sum _{p=0}^{P-1}\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i\left({\frac {rq}{Q}}+{\frac {sp}{P}}+{\frac {pr}{PQ}}\right)\right)\\&=\sum _{p=0}^{P-1}\left[\exp \left(-2\pi i\left({\frac {sp}{P}}+{\frac {pr}{PQ}}\right)\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)\right]\end{aligned}}}
ここで、
f
1
(
p
,
r
)
=
exp
(
−
2
π ぱい i
p
r
P
Q
)
∑
q
=
0
Q
−
1
f
(
q
P
+
p
)
exp
(
−
2
π ぱい i
r
q
Q
)
{\displaystyle f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{PQ}}\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)}
と置 お
F
(
n
)
=
F
(
s
Q
+
r
)
=
∑
p
=
0
P
−
1
exp
(
−
2
π ぱい i
s
p
P
)
f
1
(
p
,
r
)
{\displaystyle F(n)=F(sQ+r)=\sum _{p=0}^{P-1}\exp \left(-2\pi i{\frac {sp}{P}}\right)f_{1}(p,r)}
となる。即 すなわ F (n ) = F (sQ + r )計算 けいさん 次 つぎ
ステップ1
p = 0, 1, ..., P − 1r = 0, 1, ..., Q − 1
f
1
(
p
,
r
)
=
exp
(
−
2
π ぱい i
p
r
P
Q
)
∑
q
=
0
Q
−
1
f
(
q
P
+
p
)
exp
(
−
2
π ぱい i
r
q
Q
)
{\displaystyle f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{PQ}}\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)}
を計算 けいさん Q 次 つぎ 離散 りさん 変換 へんかん
∑
q
=
0
Q
−
1
f
(
q
P
+
p
)
exp
(
−
2
π ぱい i
r
q
Q
)
{\displaystyle \sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)}
の実行 じっこう 回転 かいてん 因子 いんし exp(−2π ぱい PQ ) の掛 か 算 ざん 全 すべ p , r の組 くみ PQ = N 通 とお 対 たい 行 おこな 見 み ステップ2
s = 0, 1, ..., P − 1r = 0, 1, ..., Q − 1
F
(
s
Q
+
r
)
=
∑
p
=
0
P
−
1
exp
(
−
2
π ぱい i
s
p
P
)
f
1
(
p
,
r
)
{\displaystyle F(sQ+r)=\sum _{p=0}^{P-1}\exp \left(-2\pi i{\frac {sp}{P}}\right)f_{1}(p,r)}
を計算 けいさん 右辺 うへん r を固定 こてい P 次 つぎ 離散 りさん 変換 へんかん ステップ1、2は、N = PQ 次 つぎ 離散 りさん 変換 へんかん Q 次 つぎ 離散 りさん 変換 へんかん 回転 かいてん 因子 いんし 掛 か 算 ざん 実行 じっこう Q 組 くみ r = 0, 1, ..., Q − 1P 次 じ 離散 りさん 変換 へんかん 分解 ぶんかい 見 み
N 次 じ 離散 りさん 変換 へんかん 問題 もんだい Q 次 じ 離散 りさん 変換 へんかん 実施 じっし N /Q 次 じ 離散 りさん 変換 へんかん 問題 もんだい 帰着 きちゃく 特 とく Q が2 または4 の場合 ばあい Q 次 じ 離散 りさん 変換 へんかん 非常 ひじょう 簡単 かんたん 計算 けいさん
Q = 2場合 ばあい exp(−2π ぱい Q ) は 1 か −1 なので、Q 次 じ 離散 りさん 変換 へんかん 符号 ふごう 逆転 ぎゃくてん 足 た 算 ざん 計算 けいさん Q = 4場合 ばあい exp(−2π ぱい Q ) は 1 , −1 , i , −i のいずれかなので、Q 次 じ 離散 りさん 変換 へんかん 計算 けいさん 符号 ふごう 逆転 ぎゃくてん 実 み 部 ぶ 虚 きょ 部 ぶ 交換 こうかん 足 た 算 ざん 計算 けいさん Q = 2Q = 4場合 ばあい 部分 ぶぶん Q 次 じ 離散 りさん 変換 へんかん バタフライ演算 えんざん と言 い
また､N = Qk P = Q k − 1場合 ばあい 上 うえ 繰 く 返 かえ Q 次 つぎ 離散 りさん 変換 へんかん 回転 かいてん 因子 いんし 掛 か 算 ざん 繰 く 返 かえ 次数 じすう 下 さ 最終 さいしゅう 的 てき 次 じ 離散 りさん 変換 へんかん 何 なに 同 おな 下 さ F (t )求 もと 2 の累乗 るいじょう 4 の累乗 るいじょう 次 じ 離散 りさん 変換 へんかん 両方 りょうほう 性質 せいしつ 利用 りよう 非常 ひじょう 簡単 かんたん 計算 けいさん
また、Q = 2Q = 4場合 ばあい 計算 けいさん 終了 しゅうりょう 何 なん 回 かい 掛 か 算 ざん 必要 ひつよう 考 かんが 符号 ふごう 逆転 ぎゃくてん 実 み 部 ぶ 虚 きょ 部 ぶ 交換 こうかん 掛 か 算 ざん 数 かぞ 回転 かいてん 因子 いんし 掛 か 算 ざん 掛 か 算 ざん N = Qk 次数 じすう 落 お N 回 かい 掛 か 算 ざん 必要 ひつよう 次数 じすう k 0 に落 お k 回 かい 繰 く 返 かえ 必要 ひつよう 掛 か 算 ざん 数 かず Nk = N logQ N 高速 こうそく 変換 へんかん 計算 けいさん 時間 じかん 掛 か 算 ざん 部分 ぶぶん 高速 こうそく 変換 へんかん 計算 けいさん 速度 そくど O (N log N )根拠 こんきょ
上記 じょうき 説明 せつめい
N
=
Q
k
(
P
=
Q
k
−
1
)
{\displaystyle N=Q^{k}(P=Q^{k-1})}
場合 ばあい N = Qk 個 こ
f
(
q
Q
k
−
1
+
p
)
{\displaystyle f(qQ^{k-1}+p)}
N = Qk 個 こ 計算 けいさん 結果 けっか
f
1
(
p
,
r
)
=
exp
(
−
2
π ぱい i
p
r
Q
k
)
∑
q
=
0
Q
−
1
f
(
q
Q
k
−
1
+
p
)
exp
(
−
2
π ぱい i
r
q
Q
)
{\displaystyle f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{Q^{k}}}\right)\sum _{q=0}^{Q-1}f(qQ^{k-1}+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)}
を計算 けいさん 場合 ばあい 節約 せつやく 0 ≤ q ≤ Q − 1 と 0 ≤ r ≤ Q − 1 を利用 りよう 計算 けいさん 結果 けっか
f
1
(
p
,
r
)
{\displaystyle f_{1}(p,r)}
元 もと
f
(
r
Q
k
−
1
+
p
)
{\displaystyle f(rQ^{k-1}+p)}
場所 ばしょ 格納 かくのう 多 おお 次 つぎ 次数 じすう Q k − 1 でも繰 く 返 かえ
p
=
q
2
Q
k
−
2
+
p
2
{\displaystyle p=q_{2}Q^{k-2}+p_{2}}
次 つぎ 次数 じすう 計算 けいさん 結果 けっか
f
2
(
p
2
,
q
2
,
q
)
{\displaystyle f_{2}(p_{2},q_{2},q)}
f
(
q
Q
k
−
1
+
q
2
Q
k
−
2
+
p
2
)
{\displaystyle f(qQ^{k-1}+q_{2}Q^{k-2}+p_{2})}
場所 ばしょ 格納 かくのう 繰 く 返 かえ
t
=
q
1
Q
k
−
1
+
q
2
Q
k
−
2
+
⋯
+
q
k
{\displaystyle t=q_{1}Q^{k-1}+q_{2}Q^{k-2}+\cdots +q_{k}}
計算 けいさん 結果 けっか
f
k
(
p
k
,
q
k
,
q
k
−
1
,
…
,
q
2
,
q
1
)
{\displaystyle f_{k}(p_{k},q_{k},q_{k-1},\dots ,q_{2},q_{1})}
f
(
q
1
Q
k
−
1
+
q
2
Q
k
−
2
+
⋯
+
q
k
−
1
Q
+
p
k
)
{\displaystyle f(q_{1}Q^{k-1}+q_{2}Q^{k-2}+\cdots +q_{k-1}Q+p_{k})}
場所 ばしょ 格納 かくのう
一方 いっぽう
F
(
s
Q
+
r
)
=
∑
p
=
0
Q
k
−
1
−
1
exp
(
−
2
π ぱい i
s
p
Q
k
−
1
)
f
1
(
p
,
r
)
{\displaystyle F(sQ+r)=\sum _{p=0}^{Q^{k-1}-1}\exp \left(-2\pi i{\frac {sp}{Q^{k-1}}}\right)f_{1}(p,r)}
を、r を固定 こてい s を変数 へんすう Q k − 1 次 じ 離散 りさん 変換 へんかん 見 み
s
=
s
2
Q
+
r
2
{\displaystyle s=s_{2}Q+r_{2}}
F
(
s
2
Q
2
+
r
2
Q
+
r
)
=
∑
p
2
=
0
Q
k
−
2
−
1
exp
(
−
2
π ぱい i
s
2
p
2
Q
k
−
2
)
f
2
(
p
2
,
r
2
,
r
)
{\displaystyle F(s_{2}Q^{2}+r_{2}Q+r)=\sum _{p_{2}=0}^{Q^{k-2}-1}\exp \left(-2\pi i{\frac {s_{2}p_{2}}{Q^{k-2}}}\right)f_{2}(p_{2},r_{2},r)}
となる。繰 く 替 か
F
(
s
k
Q
k
+
r
k
Q
k
−
1
+
⋯
+
r
2
Q
+
r
1
)
=
∑
p
k
=
0
Q
k
−
k
−
1
exp
(
−
2
π ぱい i
s
k
p
k
Q
k
−
k
)
f
k
(
p
k
,
r
k
,
r
k
−
1
,
…
,
r
2
,
r
1
)
{\displaystyle F(s_{k}Q^{k}+r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})=\sum _{p_{k}=0}^{Q^{k-k}-1}\exp \left(-2\pi i{\frac {s_{k}p_{k}}{Q^{k-k}}}\right)f_{k}(p_{k},r_{k},r_{k-1},\dots ,r_{2},r_{1})}
となるが、左辺 さへん
s
k
Q
k
+
r
k
Q
k
−
1
+
⋯
+
r
2
Q
+
r
1
<
Q
k
{\displaystyle s_{k}Q^{k}+r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1}<Q^{k}}
より sk = 0右辺 うへん
Q
k
−
k
−
1
=
0
{\displaystyle Q^{k-k}-1=0}
より pk = 0
F
(
r
k
Q
k
−
1
+
⋯
+
r
2
Q
+
r
1
)
=
f
k
(
0
,
r
k
,
r
k
−
1
,
…
,
r
2
,
r
1
)
.
{\displaystyle F(r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})=f_{k}(0,r_{k},r_{k-1},\dots ,r_{2},r_{1}).}
これは
f
(
r
1
Q
k
−
1
+
r
2
Q
k
−
2
+
⋯
+
r
k
−
1
Q
+
r
k
)
{\displaystyle f(r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}Q+r_{k})}
場所 ばしょ 格納 かくのう
このように、求 もと 解 かい
F
(
r
k
Q
k
−
1
+
⋯
+
r
2
Q
+
r
1
)
{\displaystyle F(r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})}
f
(
r
1
Q
k
−
1
+
r
2
Q
k
−
2
+
⋯
+
r
k
−
1
Q
+
r
k
)
{\displaystyle f(r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}Q+r_{k})}
場所 ばしょ 格納 かくのう ビット反転 はんてん と言 い Q 進 すすむ 法 ほう 表示 ひょうじ 場合 ばあい
r
k
Q
k
−
1
+
⋯
+
r
2
Q
+
r
1
{\displaystyle r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1}}
(
r
k
r
k
−
1
…
r
2
r
1
)
Q
{\displaystyle (r_{k}r_{k-1}\dots r_{2}r_{1})_{Q}}
対 たい
r
1
Q
k
−
1
+
r
2
Q
k
−
2
+
⋯
+
r
k
−
1
+
r
k
{\displaystyle r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}+r_{k}}
逆 ぎゃく 読 よ
(
r
1
r
2
…
r
k
−
1
r
k
)
Q
{\displaystyle (r_{1}r_{2}\dots r_{k-1}r_{k})_{Q}}
以下 いか 高速 こうそく 変換 へんかん Q = 4場合 ばあい Microsoft Visual Basic の文法 ぶんぽう 用 もち 書 か 例 れい
Const pi As Double = 3.14159265358979 '円周 えんしゅう 率 りつ
Dim Ndeg As Long '4^deg
Dim Pdeg As Long '4^(deg-i)
Dim CR () As Double '入力 にゅうりょく 実数 じっすう 部 ぶ
Dim CI () As Double '入力 にゅうりょく 虚数 きょすう 部 ぶ
Dim FR () As Double '出力 しゅつりょく 実数 じっすう 部 ぶ
Dim FI () As Double '出力 しゅつりょく 虚数 きょすう 部 ぶ
deg = 5 '任意 にんい 設定 せってい 計算 けいさん
Ndeg = 4 ^ deg
ReDim CR ( Ndeg - 1 ) As Double '入力 にゅうりょく 実数 じっすう 部 ぶ
ReDim CI ( Ndeg - 1 ) As Double '入力 にゅうりょく 虚数 きょすう 部 ぶ
ReDim FR ( Ndeg - 1 ) As Double '出力 しゅつりょく 実数 じっすう 部 ぶ
ReDim FI ( Ndeg - 1 ) As Double '出力 しゅつりょく 虚数 きょすう 部 ぶ
'ここで、変換 へんかん 関数 かんすう 実 み 部 ぶ 虚 きょ 部 ぶ 入力 にゅうりょく
'フーリエ変換 へんかん
For i = 1 To deg
Pdeg = 4 ^ ( deg - i )
For j0 = 0 To 4 ^ ( i - 1 ) - 1
For j1 = 0 To Pdeg - 1
j = j1 + j0 * Pdeg * 4
'バタフライ演算 えんざん
w1 = CR ( j ) + CR ( j + Pdeg ) + CR ( j + 2 * Pdeg ) + CR ( j + 3 * Pdeg )
w2 = CI ( j ) + CI ( j + Pdeg ) + CI ( j + 2 * Pdeg ) + CI ( j + 3 * Pdeg )
w3 = CR ( j ) + CI ( j + Pdeg ) - CR ( j + 2 * Pdeg ) - CI ( j + 3 * Pdeg )
w4 = CI ( j ) - CR ( j + Pdeg ) - CI ( j + 2 * Pdeg ) + CR ( j + 3 * Pdeg )
w5 = CR ( j ) - CR ( j + Pdeg ) + CR ( j + 2 * Pdeg ) - CR ( j + 3 * Pdeg )
w6 = CI ( j ) - CI ( j + Pdeg ) + CI ( j + 2 * Pdeg ) - CI ( j + 3 * Pdeg )
w7 = CR ( j ) - CI ( j + Pdeg ) - CR ( j + 2 * Pdeg ) + CI ( j + 3 * Pdeg )
w8 = CI ( j ) + CR ( j + Pdeg ) - CI ( j + 2 * Pdeg ) - CR ( j + 3 * Pdeg )
CR ( j ) = w1
CI ( j ) = w2
CR ( j + Pdeg ) = w3
CI ( j + Pdeg ) = w4
CR ( j + 2 * Pdeg ) = w5
CI ( j + 2 * Pdeg ) = w6
CR ( j + 3 * Pdeg ) = w7
CI ( j + 3 * Pdeg ) = w8
'回転 かいてん 因子 いんし
For k = 0 To 3
w1 = Cos ( 2 * pi * j * k / Pdeg / 4 )
w2 = - Sin ( 2 * pi * j * k / Pdeg / 4 )
w3 = CR ( j + k * Pdeg ) * w1 - CI ( j + k * Pdeg ) * w2
w4 = CR ( j + k * Pdeg ) * w2 + CI ( j + k * Pdeg ) * w1
CR ( j + k * Pdeg ) = w3
CI ( j + k * Pdeg ) = w4
Next k
Next j1
Next j0
Next i
'ビット反転 はんてん
For i = 0 To Ndeg - 1
k = i
k1 = 0
For j = 1 To deg
k1 = k1 + ( k - Int ( k / 4 ) * 4 ) * 4 ^ ( deg - j )
k = Int ( k / 4 )
Next j
FR ( i ) = CR ( k1 )
FI ( i ) = CI ( k1 )
Next i
この例 れい 最深 さいしん 部 ぶ For k、Next k の間 あいだ 部分 ぶぶん 繰 く 返 かえ 回数 かいすう Ndeg log4 Ndeg となっている。
![{\displaystyle {\begin{aligned}F(n)&=F(sQ+r)=\sum _{p=0}^{P-1}\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {(qP+p)(sQ+r)}{PQ}}\right)\\&=\sum _{p=0}^{P-1}\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i\left({\frac {rq}{Q}}+{\frac {sp}{P}}+{\frac {pr}{PQ}}\right)\right)\\&=\sum _{p=0}^{P-1}\left[\exp \left(-2\pi i\left({\frac {sp}{P}}+{\frac {pr}{PQ}}\right)\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)\right]\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa19e1ea672b4d008b7df640340e2dab59ff0831)
