信号処理とフーリエ変換第 8 回

(1)

信号処理とフーリエ変換第 8 回

〜離散Fourier^変換(1)^〜

かつらだ

桂田祐史^{まさし}

2020

年

11

月

18

日

かつらだ桂田

まさし

祐史信号処理とフーリエ変換第8回 2020年11月18日 1 / 19

(2)

本日の内容・連絡事項

これから

3

^回、離散Fourier変換を説明する。今回は離散

Fourier

^係数を説明する。周期関数をサンプリングしたデータから

Fourier

係数を近似的に求めたものが、離散

Fourier

係数で、それを求めるのが離

散

Fourier

変換とみなせる。離散フーリエ係数の基本的な性質と、

Fourier

係数に関するサンプリング定理を紹介する。講義ノート

[1]

の§3.1まで。

かつらだ桂田

まさし

(4)

3 離散 Fourier 変換

これから説明する離散Fourier変換は、

Fourier

級数の話の離散化とみなすことができる。

実際にデータ処理する場合はサンプリングした離散データを扱わざるを得ず、離散

Fourier

変換の応用上の重要性はとても高い。一方、離散

Fourier

変換は、周期数列についての

Fourier

^{変換であり、}

Fourier

級数の近似理論にとどまらない意味を持っている。

§2 (普通の

Fourier

^変換

)

もそうであったが、複素指数関数のみで説明す

る

(

あまり時間に余裕がなく、式を短く書きたいので、三角関数バージョンの説明はサボる

)

。

かつらだ桂田

まさし

(5)

3 離散 Fourier 変換

Fourier

級数の話の離散化とみなすことができる。実際にデータ処理する場合はサンプリングした離散データを扱わざるを得ず、離散

Fourier

変換の応用上の重要性はとても高い。

一方、離散

Fourier

^{変換であり、}

Fourier

§2 (普通の

Fourier

^変換

)

る

(

)

。

かつらだ桂田

まさし

(6)

3 離散 Fourier 変換

Fourier

一方、離散

Fourier

変換であり、

Fourier

§2 (普通の

Fourier

^変換

)

る

(

)

。

かつらだ桂田

まさし

(7)

3 離散 Fourier 変換

Fourier

一方、離散

Fourier

変換であり、

Fourier

§2 (普通の

Fourier

^変換

)

る

(

)

。

かつらだ桂田

まさし

(8)

3.1 離散 Fourier 係数サンプリング

f:R→C^は周期T とする。f がある程度滑らかならば¹、次式が成り立つ。

f(x) =

∑∞ n=−∞

cneⁱⁿ^2π^T^x (x ∈R), (1)

cn:= 1 T

∫ _T

0

f(x)e⁻ⁱⁿ^2π^T^x dx (n∈Z).

(2)

次式で{xj},{fj}^{を定める。}x0,x1,· · ·,xN は[0,T]のN等分点となる。

(3) h:=T

N, xj=jh, fj:=f(xj) (j∈Z). f が周期T であることから(xj+N=xj+T なので)

(4) fj+N=fj (j∈Z).

すなわち{fj}j∈Zは周期Nの周期数列である。

信号処理では、f を(連続)信号、xjを標本点、hをサンプリング周期(標本化周期, sampling period)、1/hをサンプリング周波数(標本化周波数, sample rate, sampling rate)と呼ぶ。また、信号を測定して{fj}を得ることをサンプリング(標本化)と呼ぶ。

1これまでは原点について対称な区間での積分cn=_T¹∫T/2

−T/2f(x)e⁻ⁱⁿ^2π^T^xdx で表していた。

かつらだ桂田

まさし

(9)

3.1 離散 Fourier 係数サンプリング

f(x) =

∑∞ n=−∞

cn:= 1 T

∫ _T

0

(2)

(3) h:=T

N, xj=jh, fj:=f(xj) (j∈Z).

f が周期T であることから(xj+N=xj+T なので)

(4) fj+N=fj (j∈Z).

すなわち{fj}j∈Zは周期Nの周期数列である。

かつらだ桂田

まさし

(10)

3.1 離散 Fourier 係数サンプリング

f(x) =

∑∞ n=−∞

cn:= 1 T

∫ _T

0

(2)

(3) h:=T

(4) fj+N=fj (j∈Z).

すなわち{fj}j∈Zは周期N の周期数列である。

かつらだ桂田

まさし

(11)

3.1 離散 Fourier 係数サンプリング

f(x) =

∑∞ n=−∞

cn:= 1 T

∫ _T

0

(2)

(3) h:=T

(4) fj+N=fj (j∈Z).

すなわち{fj}j∈Zは周期N の周期数列である。

信号処理では、f ^を(^連続)^信号、xjを標本点、h^{をサンプリング周期}(^{標本化周期}, sampling period)、1/hをサンプリング周波数(標本化周波数, sample rate, sampling rate)と呼ぶ。また、信号を測定して{fj}を得ることをサンプリング(標本化)と呼ぶ。

かつらだ桂田

まさし

(12)

3.1 離散 Fourier 係数周期積分は台形公式で計算すべし

Fourier係数c_n を知りたいとき、{f_j}^Nj=0⁻¹を用いて近似値を計算することを考える。

どのように計算するのが良いか。

結論を天下りに述べると

周期関数の1周期区間における積分の計算には台形則がベスト (正しい意味でベスト。しばしば驚異的な高精度が達成される。) (これは数値解析の常識であるが、説明は省略する。)

かつらだ桂田

まさし

(13)

3.1 離散 Fourier 係数周期積分は台形公式で計算すべし

Fourier係数c_n を知りたいとき、{f_j}^Nj=0⁻¹を用いて近似値を計算することを考える。

どのように計算するのが良いか。結論を天下りに述べると

周期関数の1周期区間における積分の計算には台形則がベスト (正しい意味でベスト。しばしば驚異的な高精度が達成される。) (これは数値解析の常識であるが、説明は省略する。)

かつらだ桂田

まさし

(14)

3.1 離散 Fourier 係数数値積分の台形公式

F: [a,b]→Cの定積分

I =

∫ b a

F(x)dx に対して

(5) I_N :=h

∑N j=1

(F(x_j₋₁) +F(x_j) 2

)

=h



F₀ 2 +

N∑−1 j=1

F_j+F_N 2





をその近似値として採用するのが(複合)台形公式である。ただし (6) h:= b−a

N , xj :=a+jh, Fj:=F(xj) (j= 0,1,· · · ,N).

F が周期b−a であれば、F(a) =F(b)であるからF₀=F_N. ゆえに次式が成り立つ:

(7) I_N=h

N∑−1 j=0

F_j =h

∑N j=1

F_j.

かつらだ桂田

まさし

(15)

3.1 離散 Fourier 係数数値積分の台形公式

I =

∫ b a

F(x)dx に対して

(5) IN :=h

∑N j=1

(F(x_j₋₁) +F(x_j) 2

)

=h



F₀ 2 +

N∑−1 j=1

Fj+F_N 2





N , xj :=a+jh, Fj:=F(xj) (j= 0,1,· · · ,N).

(7) I_N=h

N∑−1 j=0

F_j =h

∑N j=1

F_j.

かつらだ桂田

まさし

(16)

3.1 離散 Fourier 係数数値積分の台形公式

I =

∫ b a

F(x)dx に対して

(5) IN :=h

∑N j=1

(F(x_j₋₁) +F(x_j) 2

)

=h



F₀ 2 +

N∑−1 j=1

Fj+F_N 2





N , xj :=a+jh, Fj:=F(xj) (j= 0,1,· · · ,N).

(7) I_N=h

N∑−1 j=0

F_j =h

∑N j=1

F_j.

かつらだ桂田

まさし

(17)

3.1 離散 Fourier 係数離散 Fourier 係数の導入

F

(x) :=

_T¹f

(x)e

⁻ⁱⁿ^2π^T^x の積分に台形則を適用して、c_nを近似計算したものを Cn

(

^{大文字表記}

)

^とする

:

(8)

C_n

:= 1

T ·h

N∑−1 j=0

f_je⁻ⁱⁿ^2π^T^x^j.

(9)

ω

:=

eⁱ^2π^T^h

=

e^2πi^N

(

∵ h T

= 1

T ·T N

= 1

N

)

とおくと

e⁻ⁱⁿ^2π^T^x^j

=

e⁻ⁱⁿ^2π^T^·^jh

=

e⁻^inj^2π^N

=

ω⁻^nj. ゆえに

(10)

Cn

= 1

N

N∑−1

j=0

fjω⁻^nj. この C_n をf の離散Fourier係数と呼ぶ。

かつらだ桂田

まさし

(18)

3.1 離散 Fourier 係数離散 Fourier 係数の導入

F

(x) :=

_T¹f

(x)e

⁻ⁱⁿ^2π^T^x の積分に台形則を適用して、c_nを近似計算したものを Cn

(

^{大文字表記}

)

^とする

:

(8)

C_n

:= 1

T ·h

N∑−1 j=0

f_je⁻ⁱⁿ^2π^T^x^j.

(9)

ω

:=

eⁱ^2π^T^h

=

e^2πi^N

(

∵ h T

= 1

T ·T N

= 1

N

)

とおくと

e⁻ⁱⁿ^2π^T^x^j

=

e⁻ⁱⁿ^2π^T^·^jh

=

e⁻^inj^2π^N

=

ω⁻^nj. ゆえに

(10)

Cn

= 1

N

N∑−1

j=0

fjω⁻^nj.

この C_n をf の離散Fourier係数と呼ぶ。

かつらだ桂田

まさし

(19)

3.1 離散 Fourier 係数準備 : 1 の原始 N 乗根 ω の性質

補題

7.1 (1

の

N

乗根の性質

)

N∈N^に対してω:=e^2πi/N ^{とおくとき、次の}(1), (2)^{が成り立つ。}

(1) 1≤m≤N−1ならばω^m̸= 1,ω^N= 1 (ωは1の原始N乗根). (ゆえにm≡0 (modN)ならばω^m= 1,そうでないならばω^m̸= 1.)

(2) 任意のm∈Z^に対して

N−1

∑

j=0

ω^mj=

{ N (m≡0 (modN)) 0 (それ以外).

証明.

(1) (常識的だけれど一応)θ:=^2π_N とおくと、ω=eîθ,ω^m=eîmθ. 1≤m≤N−1ならば0<mθ <2πであるから、ω^m=eîmθ̸= 1. ω^N=eîNθ=e^2πi= 1.

(2) m≡0 (modN)であれば、ω^m= 1であるから

N−1

∑

j=0

ω^mj=

N−1

∑

j=0

1 =N. (続く)

かつらだ桂田

まさし

(20)

3.1 離散 Fourier 係数準備 : 1 の原始 N 乗根 ω の性質

補題

7.1 (1

の

N

乗根の性質

)

(1) 1≤m≤N−1ならばω^m̸= 1,ω^N= 1 (ωは1の原始N乗根).

(ゆえにm≡0 (modN)ならばω^m= 1,そうでないならばω^m̸= 1.)

N−1

∑

j=0

ω^mj=

{ N (m≡0 (modN)) 0 (それ以外).

証明.

N−1

∑

j=0

ω^mj=

N−1

∑

j=0

1 =N. (続く)

かつらだ桂田

まさし

(21)

3.1 離散 Fourier 係数準備 : 1 の原始 N 乗根 ω の性質

補題

7.1 (1

の

N

乗根の性質

)

N∑−1 j=0

ω^mj=

{ N (m≡0 (modN)) 0 (それ以外).

証明.

N−1

∑

j=0

ω^mj=

N−1

∑

j=0

1 =N. (続く)

かつらだ桂田

まさし

(22)

3.1 離散 Fourier 係数準備 : 1 の原始 N 乗根 ω の性質

補題

7.1 (1

の

N

乗根の性質

)

N∑−1 j=0

ω^mj=

{ N (m≡0 (modN)) 0 (それ以外).

証明.

(1) (^{常識的だけれど一応})θ:=^2π_N ^{とおくと、}ω=eîθ,ω^m=eîmθ. 1≤m≤N−1^ならば0<mθ <2π^{であるから、}ω^m=eîmθ̸= 1. ω^N=eîNθ=e^2πi= 1.

N−1

∑

j=0

ω^mj=

N−1

∑

j=0

1 =N. (続く)

かつらだ桂田

まさし

(23)

3.1 離散 Fourier 係数準備 : 1 の原始 N 乗根 ω の性質

補題

7.1 (1

の

N

乗根の性質

)

N∑−1 j=0

ω^mj=

{ N (m≡0 (modN)) 0 (それ以外).

証明.

(1) (^{常識的だけれど一応})θ:=^2π_N ^{とおくと、}ω=eîθ,ω^m=eîmθ. 1≤m≤N−1^ならば0<mθ <2π^{であるから、}ω^m=eîmθ̸= 1. ω^N=eîNθ=e^2πi= 1.

N−1

∑

j=0

ω^mj=

N−1

∑

j=0

1 =N. (続く)

かつらだ桂田

まさし

(24)

3.1 離散 Fourier 係数準備 : 1 の原始 N 乗根 ω の性質

証明

(

続き

).

m≡0 (modN)でなければ、ω^m̸= 1. ^初項1,公比ω^mの等比級数の和であるから

N−1∑

j=0

ω^mj= 1·1−( ω^mN)

1−ω^m =1−( ω^N)m

1−ω^m = 1−1 1−ω^m = 0.

かつらだ桂田

まさし

(25)

3.1 離散 Fourier 係数離散 Fourier 係数の性質

定理

7.2 (離散 Fourier

係数の性質)

周期T の周期関数f:R→C^とN∈N^に対して

h:=T

N, ω:=e^2πi/N, xj:=jh, fj:=f(xj) (j∈Z), Cn:= 1

N

N−1

∑

j=0

fjω⁻^nj (n∈Z)

により{Cn}n∈Zを定めるとき、次の(1), (2)が成り立つ。

(1) {Cn}nは周期N ^{の周期数列である}: Cn+N=Cn (n∈Z).

(2) f ^の複素Fourier^係数cnが

∑∞ n=−∞

|cn|<∞を満たすならば、任意のn∈Z^に対して

(11) Cn=∑

m≡n

cm

(

=

∑∞ p=−∞

cn+pN

) .

∑

m≡n

は、m≡n (modN)を満たすすべてのmについての和を意味する。

かつらだ桂田

まさし

(26)

3.1 離散 Fourier 係数離散 Fourier 係数の性質

定理

7.2 (離散 Fourier

係数の性質)

h:=T

N

N−1

∑

j=0

∑∞ n=−∞

(11) Cn=∑

m≡n

cm

(

=

∑∞ p=−∞

cn+pN

) .

∑

m≡n

かつらだ桂田

まさし

(27)

3.1 離散 Fourier 係数離散 Fourier 係数の性質

定理

7.2 (離散 Fourier

係数の性質)

h:=T

N

N−1

∑

j=0

∑∞ n=−∞

(11) Cn=∑

m≡n

cm

(

=

∑∞ p=−∞

cn+pN

) .

∑

m≡n

かつらだ桂田

まさし

(28)

3.1 離散 Fourier 係数離散 Fourier 係数の性質

∑∞ n=−∞

|cn|<∞^{という条件は、例えば}f が連続で区分的にC¹級であれば満たされる。

証明.

(1) ω⁻^(n+N)j=ω⁻^njω⁻^Nj =ω⁻^nj であるからCn+N=Cn.

(2) f(x) =

∑∞ n=−∞

cneⁱⁿ^2π^T^x であるから

(12) fj=f(xj) =

∑∞ n=−∞

cneⁱⁿ^2π^T^x^j =

∑∞ n=−∞

cneⁱⁿ^2π^T^j^T^N =

∑∞ n=−∞

cnω^nj.

ゆえに(絶対収束することに注意して)

Cn= 1 N

N∑−1 j=1

fjω⁻^nj= 1 N

N−1

∑

j=0

( ω⁻^nj

∑∞ m=−∞

cmω^mj )

= 1 N

∑∞ m=−∞

cm N−1∑

j=0

ω^(m⁻^n)j= 1 N

∑

m≡n

cmN=∑

m≡n

cm.

かつらだ桂田

まさし

(29)

3.1 離散 Fourier 係数離散 Fourier 係数の性質

∑∞ n=−∞

証明.

(2) f(x) =

∑∞ n=−∞

(12) fj=f(xj) =

∑∞ n=−∞

cnω^nj.

Cn= 1 N

N∑−1 j=1

fjω⁻^nj= 1 N

N−1

∑

j=0

( ω⁻^nj

∑∞ m=−∞

cmω^mj )

= 1 N

∑∞ m=−∞

cm N−1∑

j=0

ω^(m⁻^n)j= 1 N

∑

m≡n

cmN=∑

m≡n

cm.

かつらだ桂田

まさし

(30)

3.1 離散 Fourier 係数離散 Fourier 係数の性質

∑∞ n=−∞

証明.

(2) f(x) =

∑∞ n=−∞

(12) fj=f(xj) =

∑∞ n=−∞

cnω^nj.

Cn= 1 N

N∑−1 j=1

fjω⁻^nj= 1 N

N−1

∑

j=0

( ω⁻^nj

∑∞ m=−∞

cmω^mj )

= 1 N

∑∞ m=−∞

cm N−1∑

j=0

ω^(m⁻^n)j= 1 N

∑

m≡n

cmN=∑

m≡n

cm.

かつらだ桂田

まさし

(31)

3.1 離散 Fourier 係数離散 Fourier 係数の性質

∑∞ n=−∞

証明.

(2) f(x) =

∑∞ n=−∞

(12) fj=f(xj) =

∑∞ n=−∞

cnω^nj.

Cn= 1 N

N∑−1 j=1

fjω⁻^nj= 1 N

N−1

∑

j=0

( ω⁻^nj

∑∞ m=−∞

cmω^mj )

= 1 N

∑∞ m=−∞

cm N−1∑

j=0

ω^(m⁻^n)j= 1 N

∑

m≡n

cmN=∑

m≡n

cm.

かつらだ桂田

まさし

(32)

3.1 離散 Fourier 係数離散 Fourier 係数の性質

定理7.2の(1)から、{Cn}n∈Zを求めよ、と要求されたとき、連続したN項、例えば





 C0

C1

.. . C_N−1







を計算すれば十分である。

“入力”{fj}j∈Zについても同様で、例えば





 f0

f1

.. . fN−1







があれば十分である。

問題の舞台はC^N ^{ということになる。}

かつらだ桂田

まさし

信号処理とフーリエ変換第 8 回