離散フーリエ変換を高速化する

京都⼤大学⼯工学部物理理⼯工学科
⼯工業数学F2（フーリエ解析）
工業数学Ｆ２
#11 離散フーリエ変換を高速化する
京都大学　加納　学
京都大学大学院情報学研究科システム科学専攻
Human Systems Lab., Dept. of Systems Science
Graduate School of Informatics, Kyoto University
前回の宿題
2
1.  次の参考資料を読んで理解する．
n  金谷健一，これなら分かる応用数学教室，
共立出版，2003
「第4章　離散フーリエ解析」
n  高速フーリエ変換や離散コサイン変換も理解すること．
n  参考資料と講義スライドでは，離散フーリエ変換の定義
（1/N をどちらの式に書くか）に加えて，いくつかの記号が
異なるので注意すること．
2.  「高速フーリエ変換」の概要をレポートにまとめて提出する．
n  A4紙２頁以内にまとめること．
Copyright © 2012-2015 Manabu Kano.
All rights reserved.
1
京都⼤大学⼯工学部物理理⼯工学科
⼯工業数学F2（フーリエ解析）
復習：離散フーリエ変換
3
周期 2π の周期関数 f (x) について，
１周期を N 分割したサンプル点 xn でのサンプル値を fn とする．
離散フーリエ変換
Outline
4
l  1の原始N乗根
l  高速フーリエ変換
l  宿題
Copyright © 2012-2015 Manabu Kano.
All rights reserved.
2
京都⼤大学⼯工学部物理理⼯工学科
⼯工業数学F2（フーリエ解析）
1の原始N 乗根
5
1の原始N乗根（N乗して初めて1になる数）
オイラーの公式
レオンハルト・オイラー（Leonhard Euler）
（1707-1783 ）
1の原始N 乗根
6
1の原始N乗根
Nが偶数のとき
Copyright © 2012-2015 Manabu Kano.
All rights reserved.
3
京都⼤大学⼯工学部物理理⼯工学科
⼯工業数学F2（フーリエ解析）
7
1の原始N 乗根　：　回転因子
1の原始N乗根（回転因子）
Im
Nが偶数のとき
0
1
Re
後半は前半 N/2 点の符号を反転させたもの
Outline
8
l  1の原始N乗根
l  高速フーリエ変換
l  宿題
Copyright © 2012-2015 Manabu Kano.
All rights reserved.
4
京都⼤大学⼯工学部物理理⼯工学科
⼯工業数学F2（フーリエ解析）
高速フーリエ変換
9
l  高速フーリエ変換（Fast Fourier Transform; FFT）
n  離散フーリエ変換を高速化するアルゴリズム．
n  1805年頃，カール・ガウス（Johann Carl Friedrich
Gauss, 1777-1855）によってアルゴリズムが開発された
が，この業績は広く知られなかった．
n  1965年に，ジェイムズ・クーリー（James W. Cooley）と
ジョン・テューキー（John W. Tukey）が独自に導出したア
ルゴリズムと計算機への実装方法を発表したことにより，
FFTは脚光を浴びた．
n  Cooley-Tukey型アルゴリズムの他にも，
複数のアルゴリズムがある．
カール・ガウス（Johann Carl Friedrich Gauss）
（1777-1855）
離散フーリエ変換の行列表現
10
離散フーリエ変換
Copyright © 2012-2015 Manabu Kano.
All rights reserved.
5
京都⼤大学⼯工学部物理理⼯工学科
⼯工業数学F2（フーリエ解析）
バタフライの導出
バタフライの導出
11
12
計算量半減
Copyright © 2012-2015 Manabu Kano.
All rights reserved.
6
京都⼤大学⼯工学部物理理⼯工学科
⼯工業数学F2（フーリエ解析）
13
バタフライ（N =2）
FFT2
バタフライ
f0
FFT1
F0
f1
FFT1
F1
FFT1
14
バタフライ（N =4）
FFT2
FFT2
Copyright © 2012-2015 Manabu Kano.
All rights reserved.
f0
FFT1
F0
f1
FFT1
F1
7
京都⼤大学⼯工学部物理理⼯工学科
⼯工業数学F2（フーリエ解析）
15
バタフライ（N =4）
FFT4
f0
f1
f2
f3
F0
FFT2
FFT2
FFT2
F1
f0
FFT1
F0
F2
f1
FFT1
F1
F3
バタフライ（N=4）
バタフライ（N=2）
16
バタフライ（N =8）
FFT8
f0
f1
f2
f3
F0
FFT4
F1
F2
F3
f4
F4
f5
F5
f6
f7
FFT4
Copyright © 2012-2015 Manabu Kano.
All rights reserved.
F6
F7
FFT4
f0
f2
f4
f6
FFT2
FFT2
F0’
F1’
F2’
F3’
FFT2
f0
FFT1
F0’’
f4
FFT1
F1’’
8
京都⼤大学⼯工学部物理理⼯工学科
⼯工業数学F2（フーリエ解析）
Outline
17
l  1の原始N乗根
l  高速フーリエ変換
l  宿題
宿題
18
1.  「高速フーリエ変換（FFT）」の応用例を１つ選択し，
レポートにまとめて提出する．
n  A4紙２頁以内にまとめること．
n  応用例の概要（その技術の目的や装置構成など）を分か
り易く述べること．
n  応用例において，どのようにFFTが活用されているかを明
確に述べること．
Copyright © 2012-2015 Manabu Kano.
All rights reserved.
9

Download Report