高速フーリエ変換 (fast Fourier transform)

高速フーリエ変換
(fast Fourier transform)
12月8日
第3回目発表
1
今回のテーマ


離散フーリエ変換
(discrete Fourier transform，略してDFT)
逆離散フーリエ変換
(inverse discrete Fourier transform，略して
IDFT)
フーリエ変換の基本的な考え方とは？
“すべての信号は，三角関数（正弦波）の和とし
て表現できる ”
2
フーリエ変換と離散フーリエ変換
 フーリエ変換と離散フーリエ変換の違いとは？
 フーリエ変換
 非周期信号を扱うために，積分範囲を無限大にする



数学的には連続信号を無限大の範囲で扱うことは可
能．しかし，コンピュータでは不可能
離散フーリエ変換
コンピュータで利用するために離散化されたデジタル
信号を対象にフーリエ変換をする．
3
離散フーリエ変換
DFTの公式は
n 1
y k   x j W kj (k  0,1,  , n  1)  ()
j 0
 x
k
2k
( n 1) k

x
W

x
W



x
W
0
1
2
n 1

である．
ここで，
Wは
W  e 2 i n , i   1  ( )
で定義する．
()で，各x jは一般に複素数である．
したがって各y k も複素数である．
4
Wは以下の 2つの条件を満たす．
① Wn  1
(W  e
n
2 i
 cos 2  sin 2  1)
n 1
②
kj
W
  0 (k  0,1,, n  1)
j 0
 n 1 kj
k
2k
( n 1) k 
  W  1 W  W  W

 j 0



kn
k
W 1 1 1


 k
 k
0
W 1 W 1


5
整数環Zm上でのDFT
DFTはある種の整数値 m( n )を法とする整数環Ζ m
上でも以下のように定義できる．ただし
gcd( n, m)  1．
W  Z mは，
gcd( W, m)  1を満たし，かつ条件
(Ⅰ) W  1
(Ⅱ) W n  1
n 1
(Ⅲ)
jk
W
  0 (k  0,1,, n  1)
j 0
を満たすとする．演算
はZ mの上で考える．
6
このとき
x 0 ,  , x n 1  Z mである列( x 0 ,  , x n 1 )
に対するDFTを()と同じ式で定義する．
 ()は，



n 1


kj
y

x
W
(
k

0
,
1
,

,
n

1
)
 k  j

j 0


そうすると
y k  Z m (k  0,1,  , n  1)
となる．また
n 1 modm  Z m , W 1 modm  Z m
であることに注意する．
7
( )で定義されるWは1の原始 n乗根であり，
上記の (Ⅰ)～(Ⅲ)を満たすWは
環Z mにおける1の原始 n乗根という．
8
逆離散フーリエ変換
()式で定義される列( y 0 , y1 ,, y n 1 )
に対する逆変換を
1 n 1
z k   y h W  kh (k  0,1,, n  1)
n h 0
で定義する． (  )
これを逆離散フーリエ変換 (IDFT)という．
Z m上の IDFTについても，同様に定義される．
9
標本点 x k (k  0,1,, n  1)を，縦ベクトル
 x0 


x  
x 
 n 1 
で表わす．
ベクトルy, zについても同様に定義する．
また行列Aを，その(i, j)要素 a ijについて，
a ij  W ijで定義する．
また同様に行列 Bを，その(i, j)要素 b ijについて，
1 ij
b ij  W で定義する．
n
10
つまり
 a 00

A 
a
 01
 W0
 0
 a 0( n 1)   W
 


   W0
 a ( n 1)( n 1)   
 0
W
W0
W1
W2

W n 1
W0
W2
W4

W 2( n 1)

W0 

n 1
 W

 W 2( n 1) 

 
( n 1) 2 
 W

 W0
W0
W0
 0
 b 00  b 0( n 1) 
W
W 1
W 2


 1
B  

   W0
W 2
W 4
n
b

 


 01  b ( n 1)( n 1) 
 0
 ( n 1)
 2 ( n 1)
W
W
W

すると，
(*)式は y  Ax，
(** *)はz  Byと表わされる．

W0 

 ( n 1)
 W

 W  2( n 1) 



 ( n 1) 2 
 W

11
定理
上記の x, y , zについて，x  zが成り立つ．すなわち，
1 n 1
x k   y h W  kh (k  0,1, , n  1)
n h 0
と書ける．
証明
y  Ax, z  By だからz  By  BAx．よって，
B  A 1，すなわちBはAの逆行列であることを言えばよい．
C  BAの(i, j)要素をcijとすると，
1 n 1 ( ji ) k
cij   W
n k 0
が成り立つ．
12
i  jのとき
W ( ji ) k  1 だから cij  1．
i  jのとき
n 1
n 1
k 0
k 0
lk
l
k
j  i  l とすると，
W

W
W

 0
したがってcij  0 となる．
これよりCは単位行列である．
よって，
BはAの逆行列となり証明終了．
13
まとめ



逆離散フーリエ変換は，その名の通り離散
フーリエ変換の逆変換となっている．
離散フーリエ変換の計算量はO(n2)となる．
以前やったように，高速フーリエ変換を用い
ることでO(n logn)時間で計算できる．
14

Download Report