うさぎでもわかる信号処理・制御工学 第14羽 高速フーリエ変換(FFT)
\[\begin\left( \begin F_8(0) \\ F_8(2) \\ F_8(4) \\ F_8(6) \end \right) & = \left( \begin f_8(0) + f_8(4) \\ f_8(1) + f_8(5) \\ f_8(2) + f_8(6) \\ f_8(3) + f_8(7) \end \right)\\ & = \left( \begin 1 \\ 0 \\ 0 \\ 2 \end \right)\\ & = \left( \begin f_4 (0) \\ f_4(1) \\ f_4(2) \\ f_4(3) \end \right)\end\]
[奇数行に対して]
[偶数行→偶数行]
\[\begin\left( \begin F_8(0) \\ F_8(4) \end \right) & = \left( \begin f_4(0) + f_4(2) \\ f_4(1) + f_4(3) \end \right)\\ & = \left( \begin 1 \\ 2 \end \right)\\ & = \left( \begin f_2 (0) \\ f_2(1) \end \right)\end\]
[偶数行→奇数行]
[奇数行→偶数行]
\[\begin\left( \begin F_8(1) \\ F_8(5) \end \right) & = \left( \begin f_4(4) + f_4(6) \\ f_4(5) + f_4(7) \end \right)\\ & = \left( \begin 1 \\ 0 \end \right)\\ & = \left( \begin f_2 (4) \\ f_2(5) \end \right)\end\]
[奇数行→奇数行]
[偶数行→偶数行]
[偶数行→奇数行]
[奇数行→偶数行]
[奇数行→奇数行]
よって、高速フーリエ変換した結果は\[\left( \begin F_8(0) \\ F_8(1) \\ F_8(2) \\ F_8(3) \\ F_8(4) \\ F_8(5) \\ F_8(6) \\ F_8(7) \end \right) = \left( \begin 3 \\ 1 \\ 1+2i \\ 1 \\ -1 \\ 1 \\ 1-2i \\ 1 \end \right)\]と求められる。
4. バタフライ演算（計算の可視化）
(1) バタフライ演算の読み方 (a) 足し算 (b) 引き算※ -1 は、- とだけ書かれることもあります。
(c) 掛け算（定数倍） (2) バタフライ演算の例（2点離散フーリエ変換）例えば、2点離散フーリエ変換を高速フーリエ変換を用いた際の計算過程\[\left\< \begin f_2(0)+f_2(1) = F_2(0) \\ f_2(0) - f_2(1) = F_2(1) \end \right.\]をバタフライ演算で表すと、下のように書くことができます。
(3) バタフライ演算を読む練習次の図は、4点離散フーリエ変換を高速フーリエ変換した際の計算過程の一部をバタフライ演算で示したものである。[ ア ] 〜 [ エ ] の計算結果を、\( f_4 (k) \), \( w_4 \) を用いて表しなさい。（※ \( k \) には0〜3の数字が入る）
[解答]
\( f_4 (2) \), \( f_4(3) \) のラインは、引き算をしたあとに定数倍として \( w_4^0 \), \( w_4^1 \) が入るのがポイントです。
(4) バタフライ演算を美しく見せる技法（ビットリバース） (i) 入力と出力の順番が違う!?例えば、\( N = 4 \) 点離散フーリエ変換を高速フーリエ変換を用いたときの計算過程は次のように書くことができます。
(ii) 出力順序とビットリバース先に結論を言うと、バタフライ演算の出力は、 入力順をビットリバースしたものを出力順する ことできます [4] 多くの参考書やスライドでは出力順は入力順のビットリバースとだけ書かれていることが多いです。 。
- 元の入力順を2進数に直す（桁数は \( \log_2 N \) 桁）
- 2進数を右から読む（ビット反転）
- 右から読んだものを10進数に直す
下に、例として \(N = 4 \), \( N = 8 \) のときに入力順をビットリバースしたもの（出力順）を載せています。
[補足] なぜビットリバースするだけできれいになるか
例えば、\( N = 4 \to N = 2 \) の変換を見てみると、偶数行への分解処理は上2行、奇数行への分解処理は下2行になっていますよね。
- \( f_4 (0) \) → [ 00 ] ( 偶数行 → 偶数行 )
- \( f_4 (1) \) → [ 0 1 ] ( 偶数行 → 奇数行 )
- \( f_4 (2) \) → [ 1 0 ] ( 奇数行 → 偶数行 )
- \( f_4 (3) \) → [ 11 ] ( 奇数行 → 奇数行 )
と「左から順に偶数行(0)、奇数行(1)のどちらを適用したか」を表していますね。
- \( F_4 (0) \) → [ 00 ] ( 偶数行 → 偶数行 )
- \( F_4 (2) \) → [ 1 0 ] ( 偶数行 → 奇数行 )
- \( F_4 (1) \) → [ 0 1 ] ( 奇数行 → 偶数行 )
- \( F_4 (3) \) → [ 11 ] ( 奇数行 → 奇数行 )
と、「右から順に偶数行(0)、奇数行(1)のどちらを適用したか」を表されていることがわかります。
そのため、「左から順に 偶奇を表している入力順のビットリバース （し、右から順に変更）をする」ことできれいなバタフライ演算の図が描ける！
ビット反転と偶奇による分岐（\( N = 8 \)）
(iii) N = 8 の高速フーリエ変換のバタフライ演算最後に \( N = 8 \) の高速フーリエ変換の計算過程を、バタフライ演算で見てみましょう。
5. プログラム
※1 再帰を使っています。※2 Pythonは複素数がj、MATLABは複素数がiなので要注意！
Python要素数を2で割る際に n / 2 ではなく、n // 2 としているのは、n / 2 の計算結果を整数型で出してもらうためです [5] 配列の添字が整数型でない場合、エラーが発生する。 。
import math # math.pi を使うため import numpy as np # 行列, ベクトル計算をするため def myFFT(realVec,n): if n == 1: return realVec # N = 1 のときは入力 = 出力 else: fourierVec = np.zeros(n, dtype=np.complex128) # 成分が複素数のため # 偶数行成分 nextEvenInput = realVec[0:n//2] + realVec[n//2:n] fourierVec[0:n:2] = myFFT(nextEvenInput,n//2) # 奇数行成分 exp_part = -1 * np.array(np.array(range(n//2))) * 2 / n * math.pi * 1j w_factor = np.exp(exp_part) nextOddInput = w_factor * (realVec[0:n//2] - realVec[n//2:n]) fourierVec[1:n:2] = myFFT(nextOddInput,n//2) return fourierVec realVec = np.array([1,0,0,1,0,0,0,1]) # 入力(実変数のベクトル) fourierVec = myFFT(realVec,8) # 出力(フーリエの変数ベクトル) print(fourierVec) MATLAB realVec = [1,0,0,1,0,0,0,1]; % 入力(実変数のベクトル) fourierVec = myFFT(realVec,numel(realVec)) % 出力(フーリエ変数のベクトル) function [res] = myFFT(rVec,n) if n == 1 res = rVec; % N = 1のときは入力 = 出力 else res = zeros(n,1); % 偶数行成分 nextEvenInput = rVec(1:n/2) + rVec(n/2+1:n); res(1:2:n) = myFFT(nextEvenInput,n/2); % 奇数行成分 exp_part = -1 * (0:(n/2-1)) * 2 / n * pi * i; w_factor = exp(exp_part).'; nextOddInput = w_factor .* (rVec(1:n/2) - rVec(n/2+1:n)); res(2:2:n) = myFFT(nextOddInput,n/2); end end 実行結果 Python [ 3.+0.j 1.+0.j 1.+2.j 1.+0.j -1.+0.j 1.+0.j 1.-2.j 1.+0.j] MATLAB ans = 1 列から 5 列 3.0000 + 0.0000i 1.0000 + 0.0000i 1.0000 + 2.0000i 1.0000 + 0.0000i -1.0000 + 0.0000i 6 列から 8 列 1.0000 + 0.0000i 1.0000 - 2.0000i 1.0000 + 0.0000i 公開日： 2022年5月7日 更新日： 2023年5月30日 この記事を書いた人 コメント一覧 コメントはありません。 関連記事 うさぎでもわかる複素解析 Part3 複素べき級数の収束半径・複素べき級数の総和 うさぎでもわかる制御工学 第06羽 動的システム(前編) 伝達関数と様々な応答 90分で復習！ うさぎドリル線形代数編 第05羽 逆行列の計算 うさぎでもわかる離散数学 第5羽 順序関係とハッセ図・重要な8つの性質 4時間で復習！ 1年後期線形代数総まとめ 後編 確率統計分野で頻出な確率分布 離散型確率分布編 うさぎでもわかる信号処理 第04羽 ディジタルシステムの極・零点と安定性 うさぎでもわかる微分方程式 Part05 2階線形微分方程式の基礎（解の構造・ロンスキアン） 必見！ 理系大学生のための就活のしおり（理想的な就活スケジュール） うさぎでもわかる信号処理 第04羽 ディジタルシステムの極・零点と安定性カテゴリー
各種便利ツール・問い合わせ- 【完全無料】離散数学演習ツール・計算機まとめ
- 【離散数学】ハッセ図の述語論理（∀・∃）真偽判定ツール
- 【離散数学】べき集合 2^A・P(A) 自動計算＆全列挙ツール
- 【離散数学】上界/下界・最大元/最小元・極大元/極小元・上限(最小上界)/下限(最大下界) 判定ツール
- 【離散数学】真理値表 自動作成ツール（途中式あり）
- 【離散数学】集合の「∈・⊆」真偽チェッカー（答え合わせ用）
- 【離散数学テスト対策】真理値表の穴埋めガチ演習ツール
- 【離散数学テスト対策】集合の「∈・⊆」ガチ演習！ 弱点分析つき○×ドリル
目次
- 1. 離散フーリエ変換と行列 [復習]
- 2. 高速フーリエ変換(FFT)の仕組み
- FFTをする前の下準備
- 高速フーリエ変換は分割統治法！
- 具体例で高速フーリエ変換のアルゴリズムを確認
- \( N = 8 \) → \( N = 4 \) への分割
- \( N = 4 \) → \( N = 2 \) への分割
- \( N = 2 \) → \( N = 1 \) への分割
- (1) バタフライ演算の読み方
- (a) 足し算
- (b) 引き算
- (c) 掛け算（定数倍）
- (i) 入力と出力の順番が違う!?
- (ii) 出力順序とビットリバース
- (iii) N = 8 の高速フーリエ変換のバタフライ演算
- Python
- MATLAB
- 実行結果
- Python
- MATLAB
工業大学生ももやまのうさぎ塾 (Momousagi Academy)
コンピュータグラフィックス コンピュータビジョン- 1. 離散フーリエ変換と行列 [復習]
- 2. 高速フーリエ変換(FFT)の仕組み
- FFTをする前の下準備
- 高速フーリエ変換は分割統治法！
- 具体例で高速フーリエ変換のアルゴリズムを確認
- \( N = 8 \) → \( N = 4 \) への分割
- \( N = 4 \) → \( N = 2 \) への分割
- \( N = 2 \) → \( N = 1 \) への分割
- (1) バタフライ演算の読み方
- (a) 足し算
- (b) 引き算
- (c) 掛け算（定数倍）
- (i) 入力と出力の順番が違う!?
- (ii) 出力順序とビットリバース
- (iii) N = 8 の高速フーリエ変換のバタフライ演算
- Python
- MATLAB
- 実行結果
- Python
- MATLAB