信号解析論
Signal Processing

第１２回講義資料
Lecture notes 12

離散フーリエ変換
Discrete Fourier transform

豊橋技術科学大学
Toyohashi University of Technology

電気・電子情報工学系
Department of Electrical and Electronic Information Engineering

准教授 竹内啓悟
Associate Professor

Keigo Takeuchi1復習と今日の目標(Review and today’s goal)
時間領域信号

周波数領域信号

変換の種類

Time-doman signals

Frequency-domain signals

Transformsℝ上で連続時間ℝ上で連続周波数フーリエ変換

Continuous time on ℝ

周期的かつ連続時間
Periodic and continuous time

離散（加算無限）Discrete (countably infinite)

Continuous on ℝ

Fourier transform

離散（加算無限）フーリエ級数

Discrete (countably infinite)

Fourier series

周期的かつ連続周波数 離散時間フーリエ変換
Periodic and continuous（フーリエ級数）
frequency

Discrete-time Fourier transform(Fourier series)

周期的かつ離散周期的かつ離散離散フーリエ変換

Periodic and discrete

Periodic and discrete

Discrete Fourier transform※離散時間フーリエ変換は、フーリエ級数で時間領域と周波数領域の役割を入れ替えたもの
Discrete-time Fourier transform means the Fourier series for which time and frequency
domains are swapped.

時間・周波数領域で離散的な信号の取り扱いを学習する。
Learn the treatment of discrete signals in time and frequency domains.
2フーリエ変換の復習(Review of the Fourier transform)
フーリエ変換(Fourier transform)𝑥𝑥(𝑡𝑡)を無限区間 ℝ上の絶対可積分な連続時間信号とする。

Let 𝑥𝑥(𝑡𝑡) denote an absolutely integrable and continuous-time signal on the infinite interval ℝ.

∞

𝑋𝑋� 𝑓𝑓 = � 𝑥𝑥 𝑡𝑡 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋 𝑑𝑑𝑑𝑑 ,−∞∞ディラックのデルタ関数(Dirac delta function)

𝑥𝑥 𝑡𝑡 = � 𝑋𝑋� 𝑓𝑓 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋 𝑑𝑑𝑑𝑑−∞

任意の関数𝑓𝑓(𝑡𝑡)に対して、(For any function 𝑓𝑓(𝑡𝑡),)∞� 𝛿𝛿 𝑡𝑡 − 𝜏𝜏 𝑓𝑓 𝜏𝜏 𝑑𝑑𝑑𝑑 = 𝑓𝑓(𝑡𝑡)−∞デルタ関数のフーリエ変換(Fourier transform of the delta function)∞� 𝛿𝛿 𝑡𝑡 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋 𝑑𝑑𝑑𝑑 = 1,−∞∞

� 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋 𝑑𝑑𝑑𝑑 = 𝛿𝛿(𝑡𝑡)−∞3フーリエ級数の復習(Review of the Fourier series)
複素フーリエ級数(Complex Fourier series)𝑥𝑥(𝑡𝑡)を周期𝑇𝑇の２乗可積分な連続時間信号とする。

Let 𝑥𝑥(𝑡𝑡) denote a square-integrable and continuous-time signal of period 𝑇𝑇.

∞1� 𝑋𝑋 𝑘𝑘 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑇𝑇 ,𝑥𝑥 𝑡𝑡 =𝑇𝑇𝑘𝑘=−∞

𝑋𝑋 𝑘𝑘 = �𝑇𝑇−𝜖𝜖−𝜖𝜖直交性(Orthogonality)

𝑇𝑇−𝜖𝜖

整数𝑛𝑛 ∈ ℤに対して、 1 � 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑇𝑇 𝑑𝑑𝑑𝑑 = 𝛿𝛿 ,𝑛𝑛,0𝑇𝑇
For any integer 𝑛𝑛 ∈ ℤ ,−𝜖𝜖𝑥𝑥 𝑡𝑡 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑇𝑇 𝑑𝑑𝑑𝑑
0 < 𝜖𝜖 ≪ 1𝛿𝛿𝑛𝑛,0 = �

10for 𝑛𝑛 = 0,otherwise

クロネッカーのデルタ(Kronecker delta)

確認(Confirmation)
�𝑇𝑇−𝜖𝜖−𝜖𝜖𝑥𝑥 𝑡𝑡 𝑒𝑒= 𝑋𝑋[𝑘𝑘]−2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑇𝑇∞′𝑇𝑇−𝜖𝜖∞𝑋𝑋 𝑘𝑘′ −𝑘𝑘 𝑡𝑡/𝑇𝑇
2𝜋𝜋𝜋𝜋𝑘𝑘� 𝑒𝑒
𝑑𝑑𝑑𝑑 = �𝑑𝑑𝑑𝑑 = � 𝑋𝑋 𝑘𝑘 ′ 𝛿𝛿𝑘𝑘 ′ −𝑘𝑘,0𝑇𝑇 −𝜖𝜖′′𝑘𝑘 =−∞𝑘𝑘 =−∞

4周期信号のフーリエ変換(Fourier transform of period signals)
フーリエ変換(Fourier transform)
�
周期𝑇𝑇を持つ連続時間信号𝑥𝑥(𝑡𝑡)のフーリエ変換𝑋𝑋(𝑓𝑓)は以下で与えられる。
�The Fourier transform 𝑋𝑋(𝑓𝑓)of a continuous-time signal 𝑥𝑥(𝑡𝑡) with period 𝑇𝑇 is given by∞1𝑘𝑘�� 𝑋𝑋 𝑘𝑘 𝛿𝛿− 𝑓𝑓 ,𝑋𝑋 𝑓𝑓 =𝑇𝑇𝑇𝑇

証明(Proof)𝑘𝑘=−∞

𝑋𝑋 𝑘𝑘 = �𝑇𝑇−𝜖𝜖−𝜖𝜖𝑥𝑥 𝑡𝑡 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑇𝑇 𝑑𝑑𝑑𝑑𝑥𝑥(𝑡𝑡)は複素フーリエ級数展開できる。(𝑥𝑥(𝑡𝑡) has the complex Fourier series.)∞1
� 𝑋𝑋 𝑘𝑘 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑇𝑇
𝑥𝑥 𝑡𝑡 =
𝑇𝑇𝑘𝑘=−∞

デルタ関数のフーリエ変換公式を使って、両辺をフーリエ変換すると、Evaluate the Fourier transform of both sides by using the Fourier transform formula of the delta function.

𝑋𝑋� 𝑓𝑓 =

∞

∞

∞

11𝑘𝑘
� 𝑋𝑋 𝑘𝑘 � 𝑒𝑒 2𝜋𝜋𝜋𝜋 𝑘𝑘/𝑇𝑇−𝑓𝑓 𝑡𝑡 𝑑𝑑𝑑𝑑 =� 𝑋𝑋 𝑘𝑘 𝛿𝛿− 𝑓𝑓𝑇𝑇𝑇𝑇𝑇𝑇−∞
𝑘𝑘=−∞

𝑘𝑘=−∞

∎5離散時間フーリエ変換(Discrete-time Fourier transform)
離散時間フーリエ変換(Discrete-time Fourier transform)
𝑋𝑋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 を周期𝑓𝑓s の２乗可積分な連続周波数信号とする。

Let 𝑋𝑋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 denote a square-integrable and continuous-frequency signal of period 𝑓𝑓s .
∞𝑓𝑓s −𝜖𝜖12𝜋𝜋𝜋𝜋𝜋𝜋−2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑓𝑓s2𝜋𝜋𝜋𝜋𝜋𝜋

𝑋𝑋 𝑒𝑒

=𝑓𝑓s

� 𝑥𝑥 𝑛𝑛 𝑒𝑒

𝑛𝑛=−∞

,

𝑥𝑥 𝑛𝑛 = �−𝜖𝜖𝑋𝑋 𝑒𝑒

𝑋𝑋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 を信号{𝑥𝑥 𝑛𝑛 }の離散時間フーリエ変換と呼ぶ。

𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑓𝑓s 𝑑𝑑𝑑𝑑

𝑋𝑋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 is called discrete-time Fourier transform of {𝑥𝑥 𝑛𝑛 }.

注意Remarks

𝑓𝑓s = 1の場合、離散時間フーリエ変換は{𝑥𝑥 𝑛𝑛 }の周波数応答に等しい。
The discrete-time Fourier transform is equivalent to the frequency response of {𝑥𝑥 𝑛𝑛 } for 𝑓𝑓s = 1.

サンプリング周期を𝑇𝑇s = 1/𝑓𝑓s として、𝑥𝑥 𝑛𝑛𝑇𝑇s = 𝑥𝑥[𝑛𝑛]と定義すると、For sampling period 𝑇𝑇s = 1/𝑓𝑓s , define 𝑥𝑥 𝑛𝑛𝑇𝑇s = 𝑥𝑥[𝑛𝑛].
∞∞𝑋𝑋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 = 𝑇𝑇s � 𝑥𝑥(𝑛𝑛𝑇𝑇s )𝑒𝑒 −2𝜋𝜋𝜋𝜋(𝑛𝑛𝑇𝑇s )𝑓𝑓 → � 𝑥𝑥 𝑡𝑡 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋 𝑑𝑑𝑑𝑑 (𝑓𝑓s → ∞)
𝑛𝑛=−∞

−∞

連続時間信号𝑥𝑥(𝑡𝑡)を周期𝑇𝑇s でサンプルしたときのフーリエ変換に相当する。

Corresponds to the Fourier transform computed via sampling of a continuous-time signal 𝑥𝑥(𝑡𝑡) with period 𝑇𝑇s .
6離散時間フーリエ変換の畳み込み(Convolution of the Discrete-time Fourier transforms)
定理１２.１𝑥𝑥 𝑛𝑛 、{𝑦𝑦 𝑛𝑛 }、{𝑧𝑧 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 𝑦𝑦[𝑛𝑛]}の離散時間フーリエ変換をそれぞれ𝑋𝑋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 、𝑌𝑌 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 、𝑍𝑍 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 とすると、Theorem 12.1

Let 𝑋𝑋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 , 𝑌𝑌 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 , and 𝑍𝑍 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 denote the discrete-time Fourier transforms of{𝑥𝑥 𝑛𝑛 }, {𝑦𝑦 𝑛𝑛 }, and {𝑧𝑧 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 𝑦𝑦 𝑛𝑛 }, respectively. Then,

証明
Proof𝑧𝑧 𝑛𝑛 = �=�

𝑓𝑓s −𝜖𝜖−𝜖𝜖=�

𝑓𝑓s −𝜖𝜖−𝜖𝜖=�

𝑓𝑓s −𝜖𝜖−𝜖𝜖𝑍𝑍 𝑒𝑒

𝑓𝑓s −𝜖𝜖−𝜖𝜖𝑋𝑋 𝑒𝑒2𝜋𝜋𝜋𝜋𝜋𝜋

�2𝜋𝜋𝜋𝜋𝑓𝑓′′𝑓𝑓s −𝜖𝜖−𝜖𝜖𝑑𝑑𝑓𝑓=�𝑓𝑓s −𝜖𝜖−𝜖𝜖𝑋𝑋 𝑒𝑒′𝑋𝑋 𝑒𝑒𝑒𝑒

𝑌𝑌 𝑒𝑒

𝑋𝑋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝑓𝑓 𝑌𝑌 𝑒𝑒 2𝜋𝜋𝜋𝜋 𝑓𝑓−𝑓𝑓′�

𝑓𝑓s −𝜖𝜖−𝜖𝜖′𝑌𝑌 𝑒𝑒 2𝜋𝜋𝜋𝜋 𝑓𝑓−𝑓𝑓

𝑋𝑋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝑓𝑓 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝑓𝑓 /𝑓𝑓s 𝑑𝑑𝑓𝑓 ′ �2𝜋𝜋𝜋𝜋𝑓𝑓′

2𝜋𝜋𝜋𝜋𝑓𝑓′

2𝜋𝜋𝜋𝜋𝜋𝜋𝑓𝑓′ /𝑓𝑓s𝑑𝑑𝑓𝑓

𝑓𝑓s −𝜖𝜖−𝑓𝑓′−𝜖𝜖−𝑓𝑓′′�′

𝑓𝑓s −𝜖𝜖−𝜖𝜖′2𝜋𝜋𝜋𝜋 𝑓𝑓−𝑓𝑓′𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑓𝑓 ′ 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑓𝑓s 𝑑𝑑𝑑𝑑

𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑓𝑓s 𝑑𝑑𝑑𝑑

𝑌𝑌 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑓𝑓s 𝑑𝑑𝑑𝑑

𝑌𝑌 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑓𝑓s 𝑑𝑑𝑑𝑑 = 𝑥𝑥 𝑛𝑛 𝑦𝑦[𝑛𝑛]∵ 𝑌𝑌 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑓𝑓s は周期𝑓𝑓s (The period of 𝑌𝑌 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑓𝑓s is 𝑓𝑓s .)∎7

離散フーリエ変換の導出(Derivation of the discrete Fourier transform)
周期的な連続時間信号のサンプリング(Sampling of a periodic and continuous-time signal)�
周期𝑇𝑇の連続時間信号𝑥𝑥(𝑡𝑡)のフーリエ変換𝑋𝑋(𝑓𝑓)は、以下で書ける。
�The Fourier transform 𝑋𝑋(𝑓𝑓)of a continuous-time signal 𝑥𝑥(𝑡𝑡) with period 𝑇𝑇 can be represented as∞𝑇𝑇−𝜖𝜖1𝑘𝑘−2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑇𝑇
�𝑋𝑋 𝑓𝑓 =𝑇𝑇

� 𝑋𝑋 𝑘𝑘 𝛿𝛿

𝑘𝑘=−∞

𝑇𝑇𝑋𝑋 𝑘𝑘 = �− 𝑓𝑓 ,−𝜖𝜖𝑥𝑥 𝑡𝑡 𝑒𝑒

𝑑𝑑𝑑𝑑𝑥𝑥(𝑡𝑡)をサンプリング周期𝑇𝑇s で量子化した𝑥𝑥 𝑛𝑛 = 𝑥𝑥(𝑛𝑛𝑇𝑇s )から𝑋𝑋[𝑘𝑘]を近似する。
Approximate 𝑋𝑋[𝑘𝑘] from the quantization 𝑥𝑥 𝑛𝑛 = 𝑥𝑥(𝑛𝑛𝑇𝑇s ) of 𝑥𝑥(𝑡𝑡) with sampling period 𝑇𝑇s .

𝑇𝑇/𝑇𝑇s −1

𝑋𝑋 𝑘𝑘 ≈ � 𝑥𝑥 𝑛𝑛𝑇𝑇s 𝑒𝑒
𝑛𝑛=0−2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝑇𝑇s /𝑇𝑇𝑁𝑁−1

𝑇𝑇s = 𝑇𝑇s � 𝑥𝑥 𝑛𝑛 𝑒𝑒𝑛𝑛=0−2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁

�
一方、𝑋𝑋(𝑓𝑓)を{𝑥𝑥𝑛𝑛 }の離散時間フーリエ変換とみなすと、

�On the other hand, regard 𝑋𝑋(𝑓𝑓)as the discrete-time Fourier transform of {𝑥𝑥 𝑛𝑛 }.
∞𝑓𝑓s −𝜖𝜖𝑓𝑓s −𝜖𝜖1𝑘𝑘2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑓𝑓s�

𝑥𝑥 𝑛𝑛 ≈ �−𝜖𝜖𝑋𝑋 𝑓𝑓 𝑒𝑒𝑇𝑇𝑓𝑓s −1𝑑𝑑𝑑𝑑 =𝑇𝑇

� 𝑋𝑋 𝑘𝑘 �

𝑘𝑘=−∞𝑁𝑁−1−𝜖𝜖𝛿𝛿𝑇𝑇

112𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/(𝑇𝑇𝑓𝑓s )� 𝑋𝑋 𝑘𝑘 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁= � 𝑋𝑋 𝑘𝑘 𝑒𝑒=𝑇𝑇𝑇𝑇𝑠𝑠 𝑁𝑁
𝑘𝑘=0𝑘𝑘=0,𝑇𝑇
𝑁𝑁 =𝑇𝑇s− 𝑓𝑓 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑓𝑓s 𝑑𝑑𝑑𝑑8離散フーリエ変換(Discrete Fourier transform)
正規化周波数(Normalized frequency)
𝑓𝑓s = 1/𝑇𝑇s = 1とする。

𝐹𝐹 = 𝑓𝑓/𝑓𝑓s とし、周波数の単位を無次元化する。

Set 𝑓𝑓s = 1/𝑇𝑇s = 1.

Nondimensionalize the unit of frequency by letting 𝐹𝐹 = 𝑓𝑓/𝑓𝑓s .

離散フーリエ変換(Discrete Fourier transform)
𝑁𝑁−1

𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒
𝑛𝑛=0−2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁

,

𝑁𝑁−1

1𝑥𝑥 𝑛𝑛 = � 𝑋𝑋 𝑘𝑘 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁
𝑁𝑁
𝑘𝑘=0

一対一対応の確認(Confirmation of the one-to-one correspondence)
𝑁𝑁−1

𝑁𝑁−1 𝑁𝑁−1

𝑘𝑘=0

𝑘𝑘=0 𝑛𝑛 =0112𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁
2𝜋𝜋𝜋𝜋 𝑛𝑛−𝑛𝑛′ 𝑘𝑘/𝑁𝑁
� 𝑋𝑋 𝑘𝑘 𝑒𝑒= � � 𝑥𝑥 𝑛𝑛′ 𝑒𝑒
𝑁𝑁𝑁𝑁′=

𝑁𝑁−1

𝑁𝑁−1

𝑛𝑛 =0

𝑘𝑘=0

𝑁𝑁−11′
� 𝑥𝑥 𝑛𝑛𝑛 � 𝑒𝑒 2𝜋𝜋𝜋𝜋 𝑛𝑛−𝑛𝑛 𝑘𝑘/𝑁𝑁 = � 𝑥𝑥 𝑛𝑛𝑛 𝛿𝛿𝑛𝑛−𝑛𝑛′ ,0 = 𝑥𝑥[𝑛𝑛]
𝑁𝑁 ′′
𝑛𝑛 =0

∵ 次ページの補題１２.１(Due to Lemma 12.1 in the next page)∎9

補題(Lemma)
補題１２.１(Lemma 12.1)
整数𝑛𝑛 ∈ ℤに対して、 1
For any integer 𝑛𝑛 ∈ ℤ,証明(Proof)
𝑛𝑛 = 0の場合、
For 𝑛𝑛 = 0,

𝑁𝑁

𝑁𝑁−1

� 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁 = 𝛿𝛿𝑛𝑛,0

𝑘𝑘=0

𝑁𝑁−1

𝑁𝑁−1

𝑘𝑘=0

𝑘𝑘=0

112𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁
� 𝑒𝑒= �1=1
𝑁𝑁𝑁𝑁

𝑛𝑛 ≠ 0の場合、等比級数の公式から
For 𝑛𝑛′ ≠ 0, the geometric series formula implies

𝑁𝑁−1𝑁𝑁−1𝑘𝑘=0𝑘𝑘=02𝜋𝜋𝜋𝜋𝜋𝜋1111−𝑒𝑒𝑘𝑘
� 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁 = � 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁 ==0𝑁𝑁
𝑁𝑁
𝑁𝑁 1 − 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁∎10周期的な離散時間信号の畳み込み(Convolution of periodic and discrete-time signals)
畳み込み(Convolution){𝑦𝑦 𝑛𝑛 }を周期𝑁𝑁の離散時間信号として、

Let {𝑦𝑦 𝑛𝑛 } denote discrete-time signals with period 𝑁𝑁.

𝑁𝑁−1𝑥𝑥 ⊗ 𝑦𝑦 𝑛𝑛 = � 𝑥𝑥 𝑚𝑚 𝑦𝑦[𝑛𝑛 − 𝑚𝑚]定理１２.２(Theorem 12.2)𝑚𝑚=0{𝑥𝑥 𝑛𝑛 }と{𝑦𝑦 𝑛𝑛 }の離散フーリエ変換をそれぞれ𝑋𝑋[𝑘𝑘]と𝑌𝑌[𝑘𝑘]とする。
畳み込み{ 𝑥𝑥 ⊗ 𝑦𝑦 𝑛𝑛 }の離散フーリエ変換は、𝑋𝑋 𝑘𝑘 𝑌𝑌[𝑘𝑘]に等しい。

Let 𝑋𝑋[𝑘𝑘] and 𝑌𝑌[𝑘𝑘] denote the discrete Fourier transforms of {𝑥𝑥 𝑛𝑛 } and {𝑦𝑦 𝑛𝑛 }, respectively. Then,the discrete Fourier transform of the convolution { 𝑥𝑥 ⊗ 𝑦𝑦 𝑛𝑛 } is equal to 𝑋𝑋 𝑘𝑘 𝑌𝑌[𝑘𝑘].

注意(Remark)定理１２.２は直交周波数分割多重(OFDM)方式の実装に応用された。
Theorem 12.2 was applied to the implementation of orthogonal frequency-division multiplexing (OFDM).

11

定理１２.２の証明(Proof of Theorem 12.2)
畳み込み { 𝑥𝑥 ⊗ 𝑦𝑦 𝑛𝑛 } の離散フーリエ変換を評価する。
Evaluate the discrete Fourier transform of the convolution { 𝑥𝑥 ⊗ 𝑦𝑦 𝑛𝑛 }.

𝑁𝑁−1

𝑁𝑁−1 𝑁𝑁−1𝑛𝑛=0𝑛𝑛=0 𝑚𝑚=0

� 𝑥𝑥 ⊗ 𝑦𝑦 𝑛𝑛 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁 = � � 𝑥𝑥 𝑚𝑚 𝑦𝑦[𝑛𝑛 − 𝑚𝑚] 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁

𝑁𝑁−1

𝑁𝑁−1𝑚𝑚=0𝑛𝑛=0= � 𝑥𝑥 𝑚𝑚 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁 � 𝑦𝑦 𝑛𝑛 − 𝑚𝑚 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋(𝑛𝑛−𝑚𝑚)/𝑁𝑁
𝑁𝑁−1

𝑁𝑁−1𝑚𝑚=0𝑛𝑛=0= � 𝑥𝑥 𝑚𝑚 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁 � 𝑦𝑦 𝑛𝑛 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁 = 𝑋𝑋 𝑘𝑘 𝑌𝑌[𝑘𝑘]∵ 𝑦𝑦 𝑛𝑛 − 𝑚𝑚 = 𝑦𝑦[𝑁𝑁 + 𝑛𝑛 − 𝑚𝑚]𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋 𝑛𝑛−𝑚𝑚 /𝑁𝑁 = 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋 𝑁𝑁+𝑛𝑛−𝑚𝑚 /𝑁𝑁∎12

パーセバルの定理(Parseval’s theorem)
定理１２.３(Theorem 12.3)
離散時間信号 𝑥𝑥 𝑛𝑛

𝑁𝑁−1
𝑛𝑛=0 とその離散フーリエ変換𝑋𝑋[𝑘𝑘]に対して、

For discrete-time signals 𝑥𝑥 𝑛𝑛

𝑁𝑁−1

証明(Proof)

𝑁𝑁−1
𝑛𝑛=0 and the corresponding discrete Fourier transform 𝑋𝑋[𝑘𝑘],� 𝑥𝑥 𝑛𝑛

𝑁𝑁−1

𝑛𝑛=02

𝑁𝑁−1

1= � 𝑋𝑋 𝑘𝑘 2
𝑁𝑁
𝑘𝑘=0

𝑁𝑁−1 𝑁𝑁−1

𝑁𝑁−1

𝑘𝑘=0 𝑛𝑛=0𝑛𝑛 =011′2
� 𝑋𝑋 𝑘𝑘 = � � 𝑥𝑥 𝑛𝑛 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁 � 𝑥𝑥 𝑛𝑛′ 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋𝑛𝑛 /𝑁𝑁
𝑁𝑁
𝑁𝑁′𝑘𝑘=0

𝑁𝑁−1

𝑁𝑁−1

𝑛𝑛=0𝑛𝑛 =0

𝑁𝑁−11′= � 𝑥𝑥[𝑛𝑛] � 𝑥𝑥[𝑛𝑛𝑛] � 𝑒𝑒 2𝜋𝜋𝜋𝜋𝜋𝜋 𝑛𝑛 −𝑛𝑛 /𝑁𝑁
𝑁𝑁
′𝑁𝑁−1

𝑁𝑁−1

𝑛𝑛=0𝑛𝑛′ =0

𝑘𝑘=0

𝑁𝑁−1

= � 𝑥𝑥 𝑛𝑛 � 𝑥𝑥[𝑛𝑛𝑛] 𝛿𝛿𝑛𝑛′ −𝑛𝑛,0 = � 𝑥𝑥 𝑛𝑛 2𝑛𝑛=0∵ 補題１２.１
Lemma 12.1

∎13高速フーリエ変換(Fast Fourier transform)
定理１２.４(Theorem 12.4)
𝑁𝑁 = 2𝑀𝑀 とする。{𝑥𝑥 𝑛𝑛 }の離散フーリエ変換は、𝒪𝒪(𝑁𝑁 log 2 𝑁𝑁)時間で計算できる。
Let 𝑁𝑁 = 2𝑀𝑀 . The discrete Fourier transform of {𝑥𝑥 𝑛𝑛 } can be computed in 𝒪𝒪(𝑁𝑁 log 2 𝑁𝑁) time.

証明(Proof) 離散フーリエ変換を偶数番と奇数番に関する総和に分ける。

Decompose the discrete Fourier transform into two terms for even and odd indices.)
𝑁𝑁/2−1
𝑁𝑁/2−1

𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋(2𝑛𝑛)/𝑁𝑁 + � 𝑥𝑥 2𝑛𝑛 + 1 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋(2𝑛𝑛+1)/𝑁𝑁

𝑁𝑁/2−1𝑛𝑛=0

𝑛𝑛=0
𝑁𝑁/2−1= � 𝑥𝑥 2𝑛𝑛 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/(𝑁𝑁/2) + 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁 � 𝑥𝑥 2𝑛𝑛 + 1 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/(𝑁𝑁/2)
𝑥𝑥 2𝑛𝑛𝑛𝑛=0= 𝐸𝐸[𝑘𝑘]𝑁𝑁/2−1
𝑛𝑛=0 の離散フーリエ変換

Discrete Fourier transform of 𝑥𝑥 2𝑛𝑛

𝑋𝑋 𝑘𝑘

𝑁𝑁/2−1𝑛𝑛=0

𝑁𝑁/2−1
𝑘𝑘=0 は計算できる。( 𝑋𝑋 𝑘𝑘𝑛𝑛=0𝑥𝑥 2𝑛𝑛 + 1= 𝑂𝑂[𝑘𝑘]𝑁𝑁/2−1
𝑛𝑛=0 の離散フーリエ変換

Discrete Fourier transform of 𝑥𝑥 2𝑛𝑛 + 1

𝑁𝑁/2−1is computable.)𝑘𝑘=0

𝑁𝑁/2−1
𝑛𝑛=014

証明(Proof)
𝑋𝑋 𝑘𝑘

𝑋𝑋 𝑘𝑘

𝑁𝑁−1
𝑘𝑘=𝑁𝑁/2 も{𝐸𝐸 𝑘𝑘 }と{𝑂𝑂[𝑘𝑘]}から計算できる。

𝑁𝑁−1
𝑘𝑘=𝑁𝑁/2 are also computable from {𝐸𝐸 𝑘𝑘 } and {𝑂𝑂[𝑘𝑘]}.

𝐸𝐸 𝑘𝑘 +

𝑁𝑁/2−1

𝑁𝑁/2−1𝑛𝑛=0

𝑛𝑛=0

𝑁𝑁= � 𝑥𝑥 2𝑛𝑛 𝑒𝑒 −2𝜋𝜋𝜋𝜋(𝑘𝑘+𝑁𝑁/2)𝑛𝑛/(𝑁𝑁/2) = � 𝑥𝑥 2𝑛𝑛 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/(𝑁𝑁/2) 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋2

同様に、

𝑁𝑁/2−1= � 𝑥𝑥 2𝑛𝑛 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋/(𝑁𝑁/2) = 𝐸𝐸[𝑘𝑘]Similarly,

よって(Thus,)

𝑛𝑛=0

𝑁𝑁/2−1𝑁𝑁= � 𝑥𝑥 2𝑛𝑛 + 1 𝑒𝑒 −2𝜋𝜋𝜋𝜋(𝑘𝑘+𝑁𝑁/2)𝑛𝑛/(𝑁𝑁/2) = 𝑂𝑂[𝑘𝑘]𝑂𝑂 𝑘𝑘 +2𝑛𝑛=0

𝑁𝑁
𝑁𝑁
𝑁𝑁
−2𝜋𝜋𝜋𝜋(𝑘𝑘+𝑁𝑁/2)/𝑁𝑁= 𝐸𝐸 𝑘𝑘 ++ 𝑒𝑒= 𝐸𝐸 𝑘𝑘 − 𝑒𝑒 −2𝜋𝜋𝜋𝜋𝜋𝜋/𝑁𝑁 𝑂𝑂[𝑘𝑘]𝑋𝑋 𝑘𝑘 +𝑂𝑂 𝑘𝑘 +22215

証明(Proof)
2𝑚𝑚 点の離散フーリエ変換は、2𝑚𝑚−1 点の離散フーリエ変換を２回計算することで、計算可能であることを証明した。
We have proved that 2𝑚𝑚 -point discrete Fourier transform can be computed via two 2𝑚𝑚−1 -point
discrete Fourier transforms.

計算量(Complexity)
この分割処理を繰り返すことで、2𝑀𝑀 点の離散フーリエ変換を計算する。
Compute the 2𝑀𝑀 -point discrete Fourier transform via the repetition of this decomposition.

𝑐𝑐𝑚𝑚 を2𝑚𝑚 点の離散フーリエ変換の計算量とすると、𝐴𝐴 > 0を定数としてLet 𝑐𝑐𝑚𝑚 denote the complexity of the 2𝑚𝑚 -point discrete Fourier transform. For a constant 𝐴𝐴 > 0,𝑐𝑐𝑚𝑚 = 2𝑚𝑚 𝑐𝑐𝑚𝑚
̃ とおくと、Let 𝑐𝑐𝑚𝑚 = 2𝑚𝑚 𝑐𝑐𝑚𝑚
̃ .

よって(Thus,)

𝑐𝑐𝑚𝑚 = 2𝑐𝑐𝑚𝑚−1 + 𝐴𝐴2𝑚𝑚𝑐𝑐𝑚𝑚
̃ = 𝑐𝑐𝑚𝑚−1
̃+ 𝐴𝐴∴ 𝑐𝑐𝑚𝑚
̃ = 𝐴𝐴𝐴𝐴 + 𝑐𝑐0̃

𝑐𝑐𝑀𝑀 = 2𝑀𝑀 𝐴𝐴𝐴𝐴 + 𝑐𝑐0̃ = 𝒪𝒪 2𝑀𝑀 𝑀𝑀 = 𝒪𝒪(𝑁𝑁 log 2 𝑁𝑁)∎16

演習(Exercises)
次の離散時間信号の離散フーリエ変換を計算せよ。
Compute the discrete Fourier transform of the following discrete-time signals:

𝑥𝑥 𝑛𝑛 = 𝑎𝑎𝑛𝑛 for 𝑛𝑛 = 0, … , 𝑁𝑁 − 117