## 先週の解答 > DFTする関数を自分で実装する > $$ > S(k) = \sum_{n=0}^{N-1} s(n) e^{-j \frac{2 \pi nk}{N}} > $$ ```python= import numpy as np import matplotlib.pyplot as plt def dft(s): N = len(s) S = np.zeros(N, dtype=np.complex128) for k in range(N): print(k) for n in range(N): S[k] += S[n] * np.e ** ((-1j * 2 * np.pi * n * k) / N) return S s = np.array([3, -1, 2, 0]) print(s) print(dft(s)) ``` *https://colab.research.google.com/drive/1r4qPQvWOOK1PaP5HqgX3TK4cq5dJnXES?usp=sharing* ## 今日の内容 ### 畳み込みとフーリエ変換 $$ \mathcal{F}(x(t) * y(t)) = \mathcal{F}(x(t)) \mathcal{F}(y(t)) = X(f) Y(f) $$ - ==**時間信号の畳み込み結果のスペクトル**== と ==**各時間信号のスペクトル同士の積**== が等しい #### 時間領域 $$ y(n) = x(n) * h(n) $$ <span style="text-align: center;">**IDFT** ↑ **DFT** ↓</span> #### 周波数領域 $$ Y(k) = X(k) \cdot H(k) $$ - 時間信号 $x(t), y(t)$ の長さがそれぞれ $N, M$ とすると - $x(t) * y(t)$ の長さは $N + M - 1$ - $\mathcal{F}(x(t) * y(t))$ の長さも $N + M - 1$ - $X(f)$ の長さは $N$、$Y(f)$ の長さは $M$ - $X(f) Y(f)$ の長さは $\max(N, M)$ ### 円状畳み込み - 各信号のスペクトル同士の積によって得られる畳み込みは **円状畳み込み** - はみ出た分が回り込む - *cf.* 直線上畳み込み - 具体例 - $x(n) = \{1, 1, 1, 1, 1\},\ y(n) = \{1, 0.75, 0.5, 0.25, 0\}$ - $\textrm{IDFT}[XY] = {2.5, 2.5, 2.5, 2.5, 2.5}$ - $x*y = \{1, 1.75, 2,25, 2.5, 2.5, 1.5, 0.75, 0.25, 0\}$ ### 円状畳み込みを直線上畳み込みと同じ結果にする - 時間信号にあらかじめ0埋めを行う - 各信号の長さが $N + M - 1$ になるまで - $x(n) = \{1, 1, 1, 1, 1\},\ y(n) = \{1, 0.75, 0.5, 0.25, 0\}$ - ↓ - $x(n) = \{1,1,1,1,1,0,0,0,0\},\ y(n) = \{1, 0.75, 0.5, 0.25, 0, 0, 0, 0, 0\}$ <!-- $$ \begin{align} \end{align} $$ -->