うさぎでもわかる信号処理・制御工学 第13羽 離散フーリエ変換(DFT)
ここで周期が \( N \) なので、和の記号の範囲に含まれる整数 \( n \) の数も \( N \) 個になるようにしましょう。そのため、和の記号の範囲は \( 0 \leqq n \leqq N \) ではなく、\( 0 \leqq n \leqq N-1 \) となります [1] \( 0 \leqq n \leqq N \) とすると、範囲内に含まれる \( n \) の数が \( N + 1 \) 個になってしまい、周期も \( N + 1 \) になってしまうから。 。
(4) 複素フーリエ級数 → 逆離散フーリエ変換の導出逆離散フーリエ変換の式（\( F(k) \) から \( f(n) \) への変換式）も考えましょう。
まず、(3)の離散フーリエ変換のときと同じように、複素フーリエ係数 \( c_k \) を \( k \) の関数 \( F(k) \) とみます。
すると、\( F(k) \) から \( f(t) \) への変換式っぽいものが出てきますね。
次に、連続的な変数 \( t \), \( T \) を離散的な変数 \( n \), \( N \) に置き換えます。
さらに、(3)の離散フーリエ変換の時と同じように、和の記号の範囲に含まれる整数 \( k \) の数が \( N \) 個になるようにしましょう。
(5) 色んな離散フーリエ変換・離散逆フーリエ変換の定義の仕方(3), (4)で離散フーリエ変換、逆離散フーリエ変換の定義を紹介しましたが、実は教科書によっては変換、逆変換式が別の式で定義されていることがあります [2] 離散フーリエ変換、逆離散フーリエ変換の対応付けが正しければ(3), … Continue reading 。よく見かける3例を紹介しましょう。
※ 本ブログでは 赤色の変換式 で説明します。
離散フーリエ変換離散逆フーリエ変換\[ F(k) = \frac \sum^_ f(n) e^ n > \]\[f(n) = \sum^_ F(k) e^ n >\] \[ F(k) = \sum^_ f(n) e^ n > \] \[f(n) = \frac \sum^_ F(k) e^ n >\] \[ F(k) = \frac \sum^_ f(n) e^ n > \]\[f(n) = \frac \sum^_ F(k) e^ n >\] (i) 1番目の式 → 2番目の式の導出このとき、 青部分を離散フーリエ変換 、 赤線部分を逆離散フーリエ変換 とすることで2番目の離散フーリエ変換、逆離散フーリエ変換を導くことができます。
なお、教科書では (i)の組み合わせで離散フーリエ変換、逆離散フーリエ変換が定義されていることが多い です。そのため、本記事では、離散フーリエ変換、離散逆フーリエ変換を2番目の式\[\beginF(k) & = \sum^_ f(n) e^ n > \\f(n) & = \frac \sum^_ F(k) e^ n > \end\]で定義したいと思います。
(ii) 1番目の式 → 3番目の式の導出ここで、 青部分を離散フーリエ変換 、 赤線部分を逆離散フーリエ変換 とすることで3番目の離散フーリエ変換、逆離散フーリエ変換を導くことができます。
(ii)のパターンの場合、係数に \( \frac> \) が含まれるため、実際に計算する際に少しややこしく計算が必要になりますが、この形にすることで得られる理論的なメリットもあります。
2. 離散フーリエ変換と行列
まず、離散フーリエ変換は、下のように \( N \) 個 (有限) の実数値をまとめてフーリエ変換するもの、ということができますね。
そこでまず、\( N \) 個の実数値を集めたベクトル \( \vec \) を下のように定義しましょう。\[\vec = \left( \begin f(0) \\ f(1) \\ \vdots \\ f(N-1) \end \right) \]
同じように、フーリエ変換を適用したあとの答えとなるベクトル \( \vec \) も定義しましょう。\[\vec = \left( \begin F(0) \\ F(1) \\ \vdots \\ F(N-1) \end \right) \]
ここで、線形変換とは、あるベクトル \( \vec \) からあるベクトル \( \vec \) への変換を正方行列 \( A \) を用いて、\[ \vec = A \vec \]と表せる変換のことでしたね。
また、1回線形変換を適用したベクトル \( \vec \) を元のベクトル \( \vec \) へ戻すような変換（逆変換）は、元の変換行列 \( A \) の逆行列 \( A^ \) で表せますね。
そこで、3章以降では離散フーリエ変換を線形変換 \( \vec = A \vec \) で表す方法を見ていきたいと思います！
3. [具体例] N=2の離散フーリエ変換
とはいってもいきなり \( N \) 次のときに試すのはちょっとむずかしいですね。
そこで、まずは \( N = 2 \) の離散フーリエ変換で見ていきましょう。
(i) N=2の離散フーリエ変換この離散フーリエ変換の \( F( \textcolor ) \), \( F( \textcolor ) \) の値は下の式で求めることができますね。
この2つの式をまとめて書くと、 \[ \left. \begin F(0) & = f(0) + f(1) \\ F(1) & = f(0) - f(1) \end \right. \]となりますね。
これは、まさしく線形変換 \( \vec = A \vec \) の形ですね！
よって、\( N = 2 \) のときに離散フーリエ変換を行列で表すことに成功しました。今回は \( N = 2 \) の離散フーリエ変換なので、この行列を \( W_2 \) と定義しましょうか。。
(ii) N=2 の逆離散フーリエ変換(i)と同じように、逆離散フーリエ変換の変換行列 \( W_2' \) も出してみましょう。
この逆離散フーリエ変換の \( f( \textcolor ) \), \( f( \textcolor ) \) の値は下の式で求めることができますね。
この2つの式をまとめて書くと、 \[ \left. \begin f(0) & = \frac F(0) + \frac F(1) \\ f(1) & = \frac F(0) - \frac F(1) \end \right. \]となりますね。
確かに逆変換 \( \vec = A^ \vec \) の形になっていますね。
そこで、本当に \( W_2' \) が離散フーリエ変換の変換行列の逆行列 \( W_2^ \) となっているかを、実際に逆行列を計算することで確かめましょう。\[\begin| W_2 | & = \left| \begin 1 & 1 \\ 1 & -1 \end \right|\\ & = -1 - 1\\ & = -2\end\]より、\[\beginW_2^ & = \frac \left( \begin -1 & -1 \\ -1 & 1 \end \right)\\ & = \frac \left( \begin -1 & -1 \\ -1 & 1 \end \right)\\ & = \frac \left( \begin 1 & 1 \\ 1 & -1 \end \right)\end\]
確かに \( W_2' = W_2^ \) となり、一致していますね。
よって、\( N = 2 \) のときの離散逆フーリエ変換は、元の離散フーリエ変換の変換行列がわかってしまえば簡単に求められることがわかりました。
4. 式を簡単にする救世主：回転因子
今度は、\( N = 2 \) と限定せず、一般化していきましょう。
しかし、\( N \) の数が増えて複雑になればなるほど、式に \( e^ n > \) や \(e^< i \frac k > \) が沢山出てきて、見るだけでも嫌な数式になりそうですね。
そこで、\( w = e^ i > \) とおきましょう。すると、\( w^a \) は単位円（半径1の円）に現れます。
例えば、\( N = 8 \) であれば \( w = e^ ai> \) となるため、\( w^a \) は時計回りに45°進むごとに登場します。
このように、\( w^a \) は半径1の円上に一定間隔に回転しながら現れているので、\( w = e^ i > \) のことを 回転因子 と呼びます。
回転因子 \( N = 2, 4, 8 \) の例と変形できます [3] 逆変換に出てくる \( w^ \) は、もちろん \( w^ \) でもOKです。 。
離散フーリエ変換を簡潔に示すために \( w = e^ i > \) のことを回転因子と呼ぶ。
5. 離散フーリエ変換とDFT行列
では実際に回転因子 \( w \) を使うことで式\[F(k) = \sum^_ f(n) w^\]を行列で表してみましょう。
まずは、\( F(0) \), \( F(1) \), \( F(2) \) , …, \( F(N-1) \) をそれぞれ \( f(0) \), \( f(1) \), …, \( f(N-1) \) の線形結合（和）で表します。
[4] 1vw - 3.2px) * 0.109), 15px);">次に、この式を行列で表します。\[\left( \begin F(\textcolor) \\ F(\textcolor) \\ F(\textcolor) \\ \vdots … Continue reading → 複素共役行列を転値させた行列が随伴行列）
8. [例題] N = 4 の離散フーリエ変換・逆変換
ある実変数\[\vec = \left( \begin 1 \\ 0 \\ 1 \\ 1 \end \right)\]を離散フーリエ変換したい。
(1) \( N = 4 \) のとき、離散フーリエ変換の変換行列（DFT行列）を求めなさい。(2) \( \vec \) を4点離散フーリエ変換しなさい。(3) 逆離散フーリエ変換の変換行列（逆DFT行列）を求めなさい。(4) \( \vec \) に逆離散フーリエ変換を適用することで \( \vec \) に戻るかを確認しなさい。
\\ & = \left( \begin 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i\end \right)\end\]※ 途中の変形で \( w^4 = 1 \) を利用しています。
\( \vec = W_4 \vec \) を計算すればOK。
\[\begin\vec & = \left( \begin 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end \right) \left( \begin 1 \\ 0 \\ 1 \\ 0 \end \right)\\ & = \left( \begin 1+1+1 \\ 1-1+i \\ 1+1-i \\ 1-i-i \end \right)\\ & = \left( \begin 3 \\ i \\ 1 \\ -i \end \right)\end\]
逆DFT行列は、DFT行列の要素全体の共役複素数を取り、\( \frac \) 倍すればOK。
確認するだけ。\[\begin\vec & = W_4^ \vec\\ & = \frac \left( \begin 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end \right) \left( \begin 3 \\ i \\ 1 \\ -i \end \right)\\ & = \frac \left( \begin 3+i+1-i \\ 3+i^2-1+i^2 \\ 3-i+1+i \\ 3-i^2-1-i^2 \end \right)\\ & = \frac \left( \begin 4 \\ 0 \\ 4 \\ 4 \end \right)\\ & = \left( \begin 1 \\ 0 \\ 1 \\ 1 \end \right)\end\]
9. [練習問題] N = 8 の離散フーリエ変換にチャレンジ！
最後に、\( N = 8 \) の離散フーリエ変換にもチャレンジしてみましょう！
ある実変数\[\vec = \left( \begin 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \end \right)\]を離散フーリエ変換したい。
(1) \( N = 8 \) のとき、離散フーリエ変換の変換行列（DFT行列）を求めなさい。(2) \( \vec \) を8点離散フーリエ変換しなさい。
\\ & = \left( \begin w^ < 0 >& w^ < 0 >& w^ < 0 >& w^ < 0 >& w^ < 0 >& w^ < 0 >& w^ < 0 >& w^< 0 >\\ w^ < 0 >& w^ < 1 >& w^ < 2 >& w^ < 3 >& w^ < 4 >& w^ < 5 >& w^ < 6 >& w^ < 7 >\\ w^ < 0 >& w^ < 2 >& w^ < 4 >& w^ < 6 >& w^ < 8 >& w^ < 2 >w^ & w^ < 4 >w^ & w^ < 6 >w^ \\ w^ < 0 >& w^ < 3 >& w^ < 6 >& w^ < 1 >w^ & w^ < 4 >w^ & w^ < 7 >w^ & w^ < 2 >\left( w^ \right)^2 & w^ < 5 >\left( w^ \right)^2\\ w^ < 0 >& w^ < 4 >& w^ < 8 >& w^ < 4 >w^8 & \left( w^ \right)^2 & w^ < 4 >\left( w^ \right)^2 & \left( w^ \right)^3 & w^ < 4 >\left( w^ \right)^3\\ w^ < 0 >& w^ < 5 >& w^ < 2 >w^ & w^ < 7 >w^ & w^ < 4 >\left( w^ \right)^2 & w^ < 1 >\left( w^ \right)^3 & w^ < 6 >\left( w^ \right)^2 & w^ \left( w^ \right)^4 \\ w^ < 0 >& w^ < 6 >& w^ < 4 >w^8 & w^ < 2 >\left( w^ \right)^2 & \left( w^ \right)^3 & w^ < 6 >\left( w^ \right)^3 & w^ < 4 >\left( w^ \right)^4 & w^ < 2 >\left( w^ \right)^5 \\ w^ < 0 >& w^ < 7 >& w^ < 6 >w^8 & w^ \left( w^ \right)^2 & w^ < 3 >\left( w^ \right)^3 & w^ < 3 >\left( w^ \right)^4 & w^ < 2 >\left( w^ \right)^5 & w^ < 1 >\left( w^ \right)^6 \end \right)
\[\beginW_8 & = \left( \begin w^ < 0 >& w^ < 0 >& w^ < 0 >& w^ < 0 >& w^ < 0 >& w^ < 0 >& w^ < 0 >& w^< 0 >\\ w^ < 0 >& w^ < 1 >& w^ < 2 >& w^ < 3 >& w^ < 4 >& w^ < 5 >& w^ < 6 >& w^ < 7 >\\ w^ < 0 >& w^ < 2 >& w^ < 4 >& w^ < 6 >& w^ < 0 >& w^ < 2 >& w^ < 4 >& w^ < 6 >\\ w^ < 0 >& w^ < 3 >& w^ < 6 >& w^ < 1 >& w^ < 4 >& w^ < 7 >& w^ & w^ < 5 >\\ w^ < 0 >& w^ < 4 >& w^ < 0 >& w^ < 4 >& w^ < 0 >& w^ < 4 >& w^ < 0 >& w^< 4 >\\ w^ < 0 >& w^ < 5 >& w^ < 2 >& w^ < 7 >& w^ < 4 >& w^ < 1 >& w^ < 6 >& w^ < 3 >\\ w^ < 0 >& w^ < 6 >& w^ < 4 >& w^ < 2 >& w^ < 0 >& w^ < 6 >& w^ < 4 >& w^ < 2 >\\ w^ < 0 >& w^ < 7 >& w^ < 6 >& w^ < 5 >& w^ < 4 >& w^ < 3 >& w^ < 2 >& w^ < 1 >\end \right)\\ & = \frac \left( \begin 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2\\ 2 & \sqrt - \sqrt i & -2i & - \sqrt - \sqrt i & -2 & - \sqrt + \sqrt i & 2i & \sqrt + \sqrt i \\ 2 & -2i & -2 & 2i & 2 & -2i & -2 & 2i\\ 2 & - \sqrt - \sqrt i & 2i & \sqrt - \sqrt i & -2 & \sqrt + \sqrt i & -2i & - \sqrt + \sqrt i \\ 2 & -2 & 2 & -2 & 2 & -2 & 2 & -2\\ 2 & - \sqrt + \sqrt i & -2i & \sqrt + \sqrt i& -2 & \sqrt - \sqrt i & 2i & - \sqrt - \sqrt i\\ 2 & 2i & -2 & -2i & 2 & 2i & -2 & -2i\\ 2 & \sqrt + \sqrt i & 2i & - \sqrt + \sqrt i & -2 & - \sqrt - \sqrt i & -2i & \sqrt - \sqrt i \end \right)\end\]
※ 特に指示がない場合を除き、\( w \) のままで答えることを強くおすすめします。
\[\begin\vec & = W_8 \vec\\ & = \left( \begin \textcolor < w^< 0 >> & w^ < 0 >& w^ < 0 >& \textcolor < w^< 0 >> & w^ < 0 >& w^ < 0 >& w^ < 0 >& \textcolor < w^< 0 >>\\ \textcolor < w^< 0 >> & w^ < 1 >& w^ < 2 >& \textcolor < w^< 3 >> & w^ < 4 >& w^ < 5 >& w^ < 6 >& \textcolor < w^< 7 >>\\ \textcolor < w^< 0 >> & w^ < 2 >& w^ < 4 >& \textcolor < w^< 6 >> & w^ < 0 >& w^ < 2 >& w^ < 4 >& \textcolor < w^< 6 >> \\ \textcolor < w^< 0 >> & w^ < 3 >& w^ < 6 >& \textcolor < w^< 1 >> & w^ < 4 >& w^ < 7 >& w^ & \textcolor < w^< 5 >> \\ \textcolor < w^< 0 >> & w^ < 4 >& w^ < 0 >& \textcolor < w^< 4 >> & w^ < 0 >& w^ < 4 >& w^ < 0 >& \textcolor < w^< 4 >>\\ \textcolor < w^< 0 >> & w^ < 5 >& w^ < 2 >& \textcolor < w^< 7 >> & w^ < 4 >& w^ < 1 >& w^ < 6 >& \textcolor < w^< 3 >>\\ \textcolor < w^< 0 >> & w^ < 6 >& w^ < 4 >& \textcolor < w^< 2 >> & w^ < 0 >& w^ < 6 >& w^ < 4 >& \textcolor < w^< 2 >>\\ \textcolor < w^< 0 >> & w^ < 7 >& w^ < 6 >& \textcolor < w^< 5 >> & w^ < 4 >& w^ < 3 >& w^ < 2 >& \textcolor < w^< 1 >>\end \right) \left( \begin \textcolor \\ 0 \\ 0 \\ \textcolor \\ 0 \\ 0 \\ 0 \\ \textcolor \end \right)\\ & = \left( \begin w^0 + w^0 + w^0 \\ w^0 + w^3 + w^7 \\ w^0 + w^6 + w^6 \\ w^0 + w^1 + w^5 \\ w^0 + w^4 + w^4 \\ w^0 + w^7 + w^3 \\ w^0 + w^2 + w^2 \\ w^0 + w^5 + w^1 \end \right) = \left( \begin 3 w^0 \\ w^0 + w^3 + w^3 w^4 \\ w^0 + 2 w^6 \\ w^0 + w^1 + w^1 w^4 \\ w^0 + 2 w^4 \\ w^0 + w^3 w^4 + w^3 \\ w^0 + 2w^2\\ w^0 + w^1 w^4 + w^1 \end \right)\\ & = \left( \begin 3 w^0 \\ w^0 + w^3 - w^3 \\ w^0 + 2 w^6 \\ w^0 + w^1 - w^1 \\ w^0 + 2 w^4 \\ w^0 - w^3 + w^3 \\ w^0 + 2w^2\\ w^0 + w^1 w^4 + w^1 \end \right)= \left( \begin 3 \\ 1 \\ 1 + 2i \\ 1 \\ -1 \\ 1 \\ 1 - 2i \\ 1 \end \right)\end\]
※ \( w^4 = -1 \) を使うと若干計算が楽になります。
10. さいごに
注釈 ↑ 1 \( 0 \leqq n \leqq N \) とすると、範囲内に含まれる \( n \) の数が \( N + 1 \) 個になってしまい、周期も \( N + 1 \) になってしまうから。 ↑ 2 離散フーリエ変換、逆離散フーリエ変換の対応付けが正しければ(3), (4)の変換式で定義しなくてもOKです。具体的には、「離散フーリエ変換の正規化係数×逆離散フーリエ変換の正規化係数＝1/N」と、「離散フーリエ変換、離散逆フーリエ変換の指数部の符号が異なっている」ことを満たしていればOKです。 ↑ 3 逆変換に出てくる \( w^ \) は、もちろん \( w^ \) でもOKです。 ↑ 4 1vw - 3.2px) * 0.109), 15px);">次に、この式を行列で表します。\[\left( \begin F(\textcolor) \\ F(\textcolor) \\ F(\textcolor) \\ \vdots \\ F( \textcolor ) \end \right) =
よって、実変数ベクトル \( \vec \) からフーリエ変数ベクトル \( \vec \) の線形変換式\[\vec = W_N \vec\]が完成しましたね。
この変換行列 \( W_N \) のことを DFT行列 と呼びます。
離散フーリエ変換とDFT行列6. 離散逆フーリエ変換と逆DFT行列
5章の離散フーリエ変換と同じように、逆離散フーリエ変換\[f(n) = \frac \sum^_ w^\]の変換行列（逆DFT行列）も求めてみましょう。
つぎに \( f(0) \), \( f(1) \), \( f(2) \) , …, \( f(N-1) \) をそれぞれ \( F(0) \), \( F(1) \), …, \( F(N-1) \) の線形結合（和）で表します。
よって、フーリエ変数ベクトル \( \vec \) から実ベクトル \( \vec \) への線形変換式\[\vec = W_N^ \vec\]を導出することができましたね。
この変換行列 \( W_N^ \) のことを逆DFT行列と呼ぶことにしましょう。
逆離散フーリエ変換と逆DFT行列7. 逆DFT行列からDFT行列を求める方法
DFT行列、逆DFT行列をいちいち導出するのはめんどくさいですね。かと言って、\( W_N \) の逆行列を計算するのはさらにしんどいです。
そこで、DFT行列 \( W_N \) から逆DFT行列 \( W_N^ \) を出す方法を見ていきましょう。
すると、DFT行列 \( W_N \) に出てくる \( w^a \) の指数部分の正負を入れ替え(共役複素数をとり) 、\( w^ \) としてから \( \frac \) 倍した ものが逆DFT行列になっていることがわかりますね！
- 出てくる \( w^a \) の正負を入れ替え （ 共役複素数を取る ）
- 全体を \( \frac\) 倍 する
離散フーリエ変換の変換行列 (DFT行列) が \( W_N \) とわかっている場合、離散逆フーリエ変換の変換行列 (逆DFT行列) \( W_N^ \) は、下のように求められる。\[W_N^ = \frac \overline\]
※ \( \overline \) は複素共役行列→ 行列内の全要素に対して共役複素数を取った行列→ \( w^a \) の共役複素数は \( w^ \)
公開日： 2022年1月30日 更新日： 2022年5月6日 この記事を書いた人 コメント一覧 コメントはありません。 関連記事 うさぎでもわかる解析（高校数学・数3） Part10 特殊な積分 sqrt(x^2+a^2) が含まれたタイプ 指数関数・対数関数・多項式の発散速度について うさぎでもわかる解析 Part20 2変数関数の極値 うさぎでもわかる微分方程式 Part03 1階線形微分方程式とベルヌーイの微分方程式 1週間で完成！ うさぎでもわかる確率分布と統計的な推測 2日目 二項分布 うさぎでもわかる確率・統計 累積分布関数のいろは うさぎでもわかる微分方程式 Part07 オイラーの微分方程式 うさぎでもわかる微分方程式 Part04 完全微分方程式と積分因子 うさぎでもわかる制御工学 第08羽 動的システム(後編) 周波数特性とボード線図 4時間で復習！ 1年後期解析学総まとめ 前編カテゴリー
各種便利ツール・問い合わせ- 【完全無料】離散数学演習ツール・計算機まとめ
- 【離散数学】べき集合 2^A・P(A) 自動計算＆全列挙ツール
- 【離散数学】真理値表 自動作成ツール（途中式あり）
- 【離散数学】集合の「∈・⊆」真偽チェッカー（答え合わせ用）
- 【離散数学テスト対策】真理値表の穴埋めガチ演習ツール
- 【離散数学テスト対策】集合の「∈・⊆」ガチ演習！ 弱点分析つき○×ドリル
目次
- 1. 離散フーリエ変換(DFT)へ
- (1) 離散時間フーリエ変換
- (2) 離散フーリエ変換と複素フーリエ級数
- (3) 複素フーリエ級数 → 離散フーリエ変換の導出
- (4) 複素フーリエ級数 → 逆離散フーリエ変換の導出
- (5) 色んな離散フーリエ変換・離散逆フーリエ変換の定義の仕方
- (i) 1番目の式 → 2番目の式の導出
- (ii) 1番目の式 → 3番目の式の導出
- (i) N=2の離散フーリエ変換
- (ii) N=2 の逆離散フーリエ変換
工業大学生ももやまのうさぎ塾 (Momousagi Academy)
コンピュータグラフィックス コンピュータビジョン- 1. 離散フーリエ変換(DFT)へ
- (1) 離散時間フーリエ変換
- (2) 離散フーリエ変換と複素フーリエ級数
- (3) 複素フーリエ級数 → 離散フーリエ変換の導出
- (4) 複素フーリエ級数 → 逆離散フーリエ変換の導出
- (5) 色んな離散フーリエ変換・離散逆フーリエ変換の定義の仕方
- (i) 1番目の式 → 2番目の式の導出
- (ii) 1番目の式 → 3番目の式の導出
- (i) N=2の離散フーリエ変換
- (ii) N=2 の逆離散フーリエ変換