---
# System prepended metadata

title: ディジタル信号処理 6/23
tags: [ディジタル信号処理]

---

## 先週の解答

> 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}
$$

-->