使い方

５離散フーリェ変換
岐阜大学大学院工学研究科応用情報学専攻
1
時間軸，周波数軸の標本化定理
 時間軸の標本化定理とは逆に周波数の標本化定理がある．
 スペクトルX(ω)を標本間隔ζで標本化したものからX (ω)復元する
にはx(t)が時間幅2π/ζ未満に局在していなくはいけない．
 一般的なアナログ信号x(t)とそのスペクトルX(ω)の関係．
2
時間軸，周波数軸の標本化定理
 時間軸で標本化すると，
 周波数軸で標本化すると， (実は，フーリェ級数)
3
時間軸，周波数軸の標本化定理
 時間軸と周波数軸でともに標本化すると，
 信号x(t)とそのフーリェ変換X(ω)がともにそれぞれの軸
で局在しているならば，x(t)とX(ω)のそれぞれの標本化
信号の間は，フーリェ変換で結ばれる．
4
時間軸，周波数軸の標本化定理
 時間軸，および周波数軸の基本区間の標本点の間を関
係づけるフーリェ変換が離散フーリェ変換である．
5
離散フーリェ変換の導出過程
 信号x(t)を間隔2π/ζごとに繰り返した周期信号 ~
x (t ) とし，
スペクトルX(ω)を間隔ごとに繰り返した周期スペクトルを
ωsとする．
~
x(t) 
∞
2π
(4.1)
∑x (t   m)　m∞
~
X () 
∞
(4.2)
∑X(   ) s
 ∞
~
 基本区間の長さが2π/ζである x (t ) は，
∞
2
π
imt
~
x(t ) 
X
(
m

)
e
(4.3)
∑
 m∞
6
離散フーリェ変換の導出過程
∞
N -1
∞
 さらに，m=k+rNとおけば， ∑ は ∑∑ とかける．
k =0 r =∞
∞
 t=nτ，n ∈Z とすると，式(4.3)は，
N 1 ∞

~
x (nτ) 
X((k  rN) )e i ( k  rN ) n
∑∑
2 k  0 r  ∞
i 2  (  nr )
1 N 1 ∞

X(k  ωr )e N
∑∑
N k 0 r  ∞
 上式は，複素指数関数の周期性 (ei 2(nk N+n) = ei 2(nk N), n, k ∈Z)
nk
を利用し，式(4.2)を代入する．
N-1
i
1
~
~
x (n) 
X(k)e
∑
N k 0
2 nk
N
(4.5)
7
離散フーリェ変換の導出過程
 WN  e
i
2
N
とおけば，式(4.5)は，
1
~
x (n ) 
N
N 1
~
 nk
(4.7)
 X (k )WN k 0
~
~
 周期信号 x (t ) の間隔τ毎の値は，周期信号 X()の間隔
ζ毎の値を用いて表現できることを意味している．
n
 WNは回転因子と呼ばれており， WN , n  Z は，複素平
面において原点を中心とする単位円の演習をN当分し
た点を表す．
8
回転因子
N=8の回転因子の例
 n, m  Zに対して次の性質をもつ
WNn  mN  WNn
(4.9)
1 N 1 mn 1, for　m  0 WN  

N n 0
0, for　m  0
9
離散フーリェ変換
 式(4.7)の両辺に WN を乗じてn=0，・・・，N-1で総和をとると，
mn
N 1
~
x (n )W
mn
N
n 0
N 1
1
 [
n 0 N
N 1
~
 kn
mn
X
(
k

)
W
]

W

N
N
k 0
N 1
1
~
  [ X (k )
N
n 0
N 1
W
k 0
( mk ) n
N
]
となり，式(4.9)の性質を利用すると，
N 1
~
mn
~
  x (n )WN  X (m ) (4.10)
n 0
となる．
~
 上式は，式(4.7)とは逆に，X()の間隔ζ毎の値は，~
x (t ) の間隔τ
毎の値，すなわち
~
x(n) を用いて表されることを意味する．
10
離散フーリェ変換
 式(4.7)において
~
x

 n x (n)

~
X  1 X
(
k

)
k


とおけば，周期をもつ標本化信号の時間軸と周波数軸は，
N 1
X k   x n WNkn (4.11)
n 0
1 N 1
x n   X k WNkn (4.12)
N k 0
で結ばれる．式(4.11)を離散フーリェ変換(DFT)，式(4.12)を
逆フーリェ変換(IDFT)という
11
離散フーリェ変換
 離散フーリェ変換，逆フーリェ変換をそれぞれXk=DFT[xn]，
xn=DFT[Xk]と書く．
 離散フーリェ変換されたXk，|Xk|，|Xk|2，argXkは，それぞれフーリ
ェスペクトル，パワースペクトル，位相スペクトルと呼ばれる．
 離散フーリェ変換を行う際には，時間軸，周波数軸ともに周期的
な系列であることが暗黙の仮定となっている．
 周期性と回転因子の性質より，任意に定義されたXnの基本区間
を利用する事ができ，式(4.11)は次のようにも書ける．
N 1
X k   x n WNkn
n 2
 同様に，式(4.12)に対しても，任意の定義されたXkの基本区間を
利用できる．
12
高速フーリェ変換
 式(4.11)から分かるように，標本点数Nに対しN2回の複素
数の積算が必要である．
 高速フーリェ変換(FFT)アルゴリズムを用いると，Nlog2N
積算回数で離散フーリェ変換を行うことができる．
 高速フーリェ変換アルゴリズムには，以下の2つの方法が
ある．
 時間間引きアルゴリズム
 周波数間引きアルゴリズム
13
時間間引きアルゴリズム
 離散フーリェ変換
N 1
X k   x n WNkn
n 0
において，Nが偶数であるとして，nが偶数，奇数の場合に分け，それ
ぞれ2n，2n+1として表現すれば，
Xk 
N / 2 1
N / 2 1
n 0
n 0
2 nk
x
W
 2x N 
( 2 n 1) k
x
W
 2x 1 N
と書け，回転因子の性質より， WN2nk  WNnk/ 2 なので，
Xk 
N / 2 1
N / 21
n 0
n 0
2 nk
k
x
W

W
 2n N / 2 N
nk
x
W
(4.15)
 2x1 N / 2 となる．
14
時間間引きアルゴリズム
 ここで，kを前半と後半に分けると，前半k=0，1，・・・，N/2-1につい
ては式(4.15)のまま，後半k=N/2，・・・，N-1については，kをk+N/2
とおいて，
N / 2 1
N / 21
XkN / 2 
n ( k  N / 2)
k
x
W

W
 2n N / 2
N
n 0
n ( k  N / 2)
x
W
 2n1 N / 2 ,
n 0
k  0,1,, N / 2  1
であるが，回転因子の性質 WNnN/ 2/ 2  1, WNk N / 2  WNk を利用す
れば，
N / 2 1
N / 21
XkN / 2 
nk
k
x
W

W
 2n N / 2 N
n 0
nk
x
W
(4.17)
 2n 1 N / 2 n 0
となる．
15
時間間引きアルゴリズム
 ここで，
Hk 
N / 21
nk
x
W
k  0,1,, N / 2  1
 2n 1 N / 2 , n 0
は，いずれもN/2点の離散フーリェ変換を意味している．上式を式
(4.15)，(4.17)に代入すると，
X k  G k  WNk H k , k  0,1,, N / 2  1
X k  N / 2  G k  WNk H k , k  0,1,, N / 2  1
となる．つまり，標本点数Nの離散フーリェ変換は，標本点数N/2
の離散フーリェ変換を2回とN/2回の積算で実現できることになる．
16
時間間引きアルゴリズムの例
 N=8の場合
17
時間間引きアルゴリズム(N/2が偶数の場合)
 標本点数N/4の離散フーリェ変換を4回とN/2+2・N/4の
積算で実現できる．
 Kを正の整数として標本点数がN=2Kであるならば，こう
した分割を繰り返すことによって標本点数1の離散フーリ
ェ変換をN回と（N/2）log2N回の積算で実現できる．
 標本点数1の離散フーリェ変換では，1を乗ずるだけであ
るから，もはや計算の必要はなく，積算の問題は
(N/2)log2Nとなる．
 例えば，標本点数N=1024の場合の離散フーリェ変換は
，高速フーリェ変換を利用することによって約200分の1
ほどの計算量になる．
18
時間間引きアルゴリズムの例
 N=8の場合
19
周波数間引きアルゴリズム
 標本系列xnの標本点数Nが偶数の場合，式(4.11)におい
て，xnの前半と後半に等分すると離散フーリェ変換は，
Xk 
N / 2 1
 xnW 
n 0
N / 2 1
kn
N
  x n WNkn 
n 0
N / 2 1
N 1
kn
x
W
 n N
nN / 2
N / 2 1
x
n 0
kN
2
N
  (x n  W x
n 0
n
k(n
N
n
2
WN
N
)
2
kn
)
W
k  0,1, , N  1
N
N , 2
と表わされる．
20
周波数間引きアルゴリズム
 Xkをkが偶数の場合と奇数の場合に分けて考える．
 Kが偶数の場合，k→2kとし， WNkN  1, WNkn/ 2 を利用すると，
N / 2 1
 (x
X 2k 
n 0
n
 WNkN x
N / 2 1
  (x n  x
n 0
n
n
2 kn
)
W
N
N
2
kn
)
W
k  0,1,, N / 2  1　(4.22)
N
N / 2 , 2
 kが奇数である場合，k→2k+1とし， WNN / 2  1 を利用すると，
X 2 k 1 
N / 2 1
 (x
n 0
n
( 2 k 1) N
2
N
W
x
n
( 2 k 1) n
)
W
N
N
2
N / 2 1
  ( x n  WNN / 2 x
n 0
N / 2 1
  (x n  x
n 0
n
n
kn
n
)
W
W
N
N/2
N
2
n
kn
)
W
W
k  0,1,, N / 2  1　(4.23)
N
N
N / 2 , 2
21
周波数間引きアルゴリズム
 ここで，
G n  x n  x nN / 2
H n  x n  x nN / 2
とおくと，式(4.22)，(4.23)は，
X 2k 
N / 2 1
kn
G
W
, k  0,1,, N / 2  1
 n N/2　X 2 k 1 
n 0
N / 2 1
n
kn
(
H
W
)
W
 n N N / 2 , k  0,1,, N / 2  1
n 0
となる．つまり，標本点数Nの離散フーリェ変換は，標
本点N/2の離散フーリェ変換を2回とN/2回の積算で実現
できる．
22
周波数間引きアルゴリズムの例
 N=8の場合
23
周波数間引きアルゴリズム（N/2が偶数の場合）
 標本点数N/2の離散フーリェ変換を4回とN/2+N/2=N回
の積算で実現できる．
 Kを正の整数として標本点数がN=2Kであるならば，こう
した分割を繰り返すことによって標本点数1の離散フーリ
ェ変換をN回と(N/2)log2N回の積算で実現できる．
 標本点数1の離散フーリェ変換では，1を乗ずるだけであ
るから，もはや計算の必要はなく，積算の回数は
(N/2)log2Nとなる．
24
FFTの周波数間引きアルゴリズムの例
 N=8の場合
25
畳み込み演算
 標本系列に対する畳み込み積分は，積分記号∫を総和記号∑に
置き換えることによって定義される．
 xn，n=0，1，・・・，N-1，yn，n=0，1，・・・，N-1の畳み込み演算は，
z n   x k y n k , n  0,1,,2( N  1)
kZ
となる．xn，ynのn=0，1，・・・，N-1以外での値を使わなくてはいけ
ないが,一般的にはこれらの値を0とみなすことが多い．
 このような畳み込み演算を線状畳み込みという．
26
畳み込み演算
 xnとynのそれぞれの離散フーリェ変換Xk，Ykの積の逆フーリェ変
換は，周期信号であるxnとynの畳み込みである．
 この畳み込み演算を線状畳み込みと区別して，環状畳み込みと
いう．
 線形畳み込みと環状畳み込みは全く異なる結果を与えることがあ
る．
27
環状畳み込みによって線状畳み込みを行う方法
 xkとykの後ろにそれぞれN個の値ゼロの標本点があると
みなし，環状畳み込みを行う
→周期性は無視できるようになり，xkとykの線状畳み込
みを行ったことになる．
 畳み込み演算は多くの計算量を必要とするが，この方
法で離散フーリェ変換を高速フーリェ変換を利用して行
うと，計算量が大幅に削減される．
28
ゼロ詰め
サンプリング間隔
が短くなったから
といって，解像度
が高くなったわけ
ではない．
スペクトルのピー
クを見やすくする
ために，頻繁に用
いられる．
29
再標本化
 一般に，標本系列xn=x(nτ)が与えられ，xn=x(nτ’)，τ’≠τを得ること
を再標本化，リサンプリング，レート変換，標本化周波数の変換な
どという．
 τ>τ’の場合，補間もしくはアップサンプリング
 τ<τ’の場合，ダウンサンプリング
 ゼロ詰めと離散フーリェ変換，標本間引きを組み合わせることに
より，レート変換が行える．例えば，





離散フーリェ変換し，
（LPFをかけたのち）
3倍にゼロ詰めし，
逆離散フーリェ変換し，
2：1に標本間引き
を行えば，元のサンプリング周波数の1.5倍になる．
30
z変換
 標本系列を表現するためには，標本化信号に対するラプラス変
換であるz変換が有効である．
 負の時刻t<0でゼロの値をとるアナログ信号x(t)を考える．
 x(t)を標本間隔τで標本化した標本化信号は，


x  (t )   x(n)(t  n)
n 0

x
 ラプラス変換の性質を利用すれば，標本化信号  ( t )のラプラス変
換は，


L[ x  ( t )]  L[ x (n)( t  n)]
n 0

  x (n)L[( t  n)]
n 0

  x (n)e sn  (4.29)
n 0
となる．
31
片側z変換
s
 ここで，z  e なる複素変数zを導入し，xn  xn , X z   Lx t  e
とおけば，式(4.29)は次のよるになる．

s
z

X(z)   x n z n (4.30)
n 0
 zの級数となっており，級数が収束するとき，標本系列xn，n=0，1，
2，・・・からX(z)への変換をX(z)=Z[xn]と書き，これを片側z変換と
いう．
s
 変数変換 z  e は，s平面の虚軸をz平面の単位円上に，s平面
の左半分のすべての点をz平面の単位円内に，s平面の右半分の
すべての点をz平面の単位円外に移す変換である．
32
s平面からz平面への変換
s平面において辺b-dの虚部がωs/2，辺h-fの虚部が-ωs/2
であるとき，z平面で辺b-dと辺h-fは負の虚数軸上で重な
る．
s平面でσ+i(ω+nωs)，n  Z の点は，複素指数関数の周期
性より，z平面ではすべて同じ点に写像される．
→アナログ信号x(t)がs平面において，虚数部が-ωs/2からωs/2
に局在してなければ，標本化によって，標本化信号のz変換は，
z平面において重なりが生じる．
33
z変換と畳み込み演算
 xn，n  Z
を{x
0，x1，x2，0，0，・・・}，yn， n  Zを{y
0，y1，y2


，0，0，・・・}とする．
(0以上の整数からなる集合をZ+で表す)
 xnとynの畳み込みxn*ynは次式となる．
x 0 y 0,

 x y x y ,
0 1
1 0

x 0 y 2  x 1 y1  x 2 y 0,

x 1 y 2  x 2 y1,


x 2 y 2,


0,
n0
n 1
n2
n3
n4
n  5,6,
34
z変換と畳み込み演算
 xnとynのz変換は，それぞれ
X(z)  x 0  x 1 z 1  x 2 z 2
Y(z)  y 0  y1 z 1  y 2 z 2
となるので，それらの積は，
X(z)Y(z)  ( x 0  x 1 z 1  x 2 z  2 )(y 0  y1 z 1  y 2 z  2 )
 x 0 y 0  ( x 0 y1  x 1 y 0 )z 1  ( x 0 y 2  x 1 y1  x 2 y 0 )z  2 
( x 1 y 2  x 2 y1 ) z 3  x 2 y 2 z  4
 xnとynの畳み込みxn*ynのz変換に等しい．
 畳み込み演算は，多項式どうしの積として表わされる.
35
逆z変換
 X(z)から元の標本系列xn， n  Z  への逆変換は，収束領域内で原
点を含む閉路(積分路)cの複素積分
1
n 1
xn 
X
(
z
)
z
dz

2i c
により与えられる．これを逆z変換といい，xn=Z-1[X(z)]と記述する．
 この複素積分は，X(z)が有理多項式で表現されている場合，留数
定理などを利用して行う．
36
両側z変換
 式(4.30)で示した片側z変換に対し，xn，n<0も考慮した
X( z) 

z
x
z
(4.32)
 n n  
を両側z変換という．
 式(4.32)の級数は，複素関数論ではローラン級数と呼ばれており，
級数が収束するための十分条件は，

n
x
z
 n 
n - 
である．この級数の収束領域は，実定数r1，r2(0<r1<r2)を用いて，
r1  z  r2
と表現できる．
37
z変換と離散フーリェ変換の関係
 標本系列xn，n=0，1，・・・，N-1のz変換は，
N 1
X( z )   x n z  n
n 0
である．
 Z平面において，単位円周上に等間隔に配置されたN個の標本
点 z k  e i 2k / N ，k=0，1，・・・，N-1でのX(z)は，
N 1
X(z) z z   x n e i 2 kn / N , k  0,1,, N  1
k
n 0
となる．この式は，X k  Xz  z  zとおけば，xnの離散フーリェ変換に
一致する．
 Xn，n=0，1，・・・，N-1の離散フーリェ変換は，xnのz変換
X(z)=Z[xn]における単位円周上の等間隔なN個の標本点に他な
らない．
k
38

Download Report