극한도 수렴 문제도 없는 C N \mathbb{C}^N C N
4.1 푸리에 기저
길이 N N N x [ n ] x[n] x [ n ] n = 0 , 1 , … , N − 1 n = 0, 1, \ldots, N - 1 n = 0 , 1 , … , N − 1 C N \mathbb{C}^N C N
정의 4.1. k = 0 , 1 , … , N − 1 k = 0, 1, \ldots, N - 1 k = 0 , 1 , … , N − 1 u k ∈ C N \mathbf{u}_k \in \mathbb{C}^N u k ∈ C N
u k [ n ] = e j 2 π k n / N , n = 0 , 1 , … , N − 1 \mathbf{u}_k[n] = e^{j2\pi kn/N}, \qquad n = 0, 1, \ldots, N - 1 u k [ n ] = e j 2 π k n / N , n = 0 , 1 , … , N − 1 로 정의합니다. 이들을 C N \mathbb{C}^N C N 푸리에 기저 라 합니다.
u k \mathbf{u}_k u k e j θ e^{j\theta} e j θ 2 π k / N 2\pi k/N 2 π k / N N N N n n n N N N k k k u 0 = ( 1 , 1 , … , 1 ) \mathbf{u}_0 = (1, 1, \ldots, 1) u 0 = ( 1 , 1 , … , 1 ) u 1 \mathbf{u}_1 u 1 N N N u 2 \mathbf{u}_2 u 2
그림 4.1. N = 8 N = 8 N = 8 u k [ n ] = e j 2 π k n / 8 \mathbf{u}_k[n] = e^{j2\pi kn/8} u k [ n ] = e j 2 π k n /8 k = 5 , 6 , 7 k = 5, 6, 7 k = 5 , 6 , 7 k = 3 , 2 , 1 k = 3, 2, 1 k = 3 , 2 , 1
정리 4.2 (푸리에 기저의 직교성).
⟨ u k , u m ⟩ = ∑ n = 0 N − 1 e j 2 π k n / N e − j 2 π m n / N = N δ k m ( 0 ≤ k , m ≤ N − 1 ) \langle \mathbf{u}_k, \mathbf{u}_m \rangle = \sum_{n=0}^{N-1} e^{j2\pi kn/N} e^{-j2\pi mn/N} = N\delta_{km} \qquad (0 \le k, m \le N - 1) ⟨ u k , u m ⟩ = n = 0 ∑ N − 1 e j 2 π k n / N e − j 2 π mn / N = N δ k m ( 0 ≤ k , m ≤ N − 1 ) 증명. r = e j 2 π ( k − m ) / N r = e^{j2\pi(k - m)/N} r = e j 2 π ( k − m ) / N ∑ n = 0 N − 1 r n \sum_{n=0}^{N-1} r^n ∑ n = 0 N − 1 r n k = m k = m k = m r = 1 r = 1 r = 1 N N N k ≠ m k \ne m k = m 0 < ∣ k − m ∣ < N 0 < |k - m| < N 0 < ∣ k − m ∣ < N ( k − m ) / N (k - m)/N ( k − m ) / N r ≠ 1 r \ne 1 r = 1 정리 1.17 )에서 ∑ n = 0 N − 1 r n = 1 − r N 1 − r \sum_{n=0}^{N-1} r^n = \frac{1 - r^N}{1 - r} ∑ n = 0 N − 1 r n = 1 − r 1 − r N r N = e j 2 π ( k − m ) = 1 r^N = e^{j2\pi(k - m)} = 1 r N = e j 2 π ( k − m ) = 1 ■ \blacksquare ■
기하학적으로는 2장 정리 2.9 와 같은 그림입니다. r n r^n r n N N N
영이 아닌 직교 벡터 N N N 정리 3.20 에 의해 { u k } \{\mathbf{u}_k\} { u k } C N \mathbb{C}^N C N ∥ u k ∥ = N \lVert\mathbf{u}_k\rVert = \sqrt{N} ∥ u k ∥ = N u k / N \mathbf{u}_k/\sqrt{N} u k / N
4.2 DFT와 역 DFT
직교기저의 좌표 공식(3장 따름정리 3.18 )을 그대로 적용합니다. 모든 x ∈ C N \mathbf{x} \in \mathbb{C}^N x ∈ C N x = ∑ k c k u k \mathbf{x} = \sum_k c_k\mathbf{u}_k x = ∑ k c k u k c k = ⟨ x , u k ⟩ / N c_k = \langle \mathbf{x}, \mathbf{u}_k \rangle / N c k = ⟨ x , u k ⟩ / N N N N
정의 4.3 (이산 푸리에 변환).
DFT (분석): X [ k ] = ⟨ x , u k ⟩ = ∑ n = 0 N − 1 x [ n ] e − j 2 π k n / N , k = 0 , … , N − 1 역 DFT (합성): x [ n ] = 1 N ∑ k = 0 N − 1 X [ k ] e j 2 π k n / N , n = 0 , … , N − 1 \begin{aligned}
\text{DFT (분석):}\quad & X[k] = \langle \mathbf{x}, \mathbf{u}_k \rangle = \sum_{n=0}^{N-1} x[n]\, e^{-j2\pi kn/N}, && k = 0, \ldots, N - 1 \\
\text{역 DFT (합성):}\quad & x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k]\, e^{j2\pi kn/N}, && n = 0, \ldots, N - 1
\end{aligned} DFT ( 분석 ): 역 DFT ( 합성 ): X [ k ] = ⟨ x , u k ⟩ = n = 0 ∑ N − 1 x [ n ] e − j 2 π k n / N , x [ n ] = N 1 k = 0 ∑ N − 1 X [ k ] e j 2 π k n / N , k = 0 , … , N − 1 n = 0 , … , N − 1 역변환 공식은 따로 증명할 것이 없습니다. 좌표 공식 그 자체입니다. 그래도 직접 확인해 보면 구조가 잘 보입니다.
1 N ∑ k X [ k ] e j 2 π k n / N = 1 N ∑ k ∑ m x [ m ] e − j 2 π k m / N e j 2 π k n / N = ∑ m x [ m ] 1 N ∑ k e j 2 π k ( n − m ) / N ⏟ δ n m = x [ n ] \frac{1}{N}\sum_k X[k]e^{j2\pi kn/N} = \frac{1}{N}\sum_k\sum_m x[m]e^{-j2\pi km/N}e^{j2\pi kn/N} = \sum_m x[m]\underbrace{\frac{1}{N}\sum_k e^{j2\pi k(n - m)/N}}_{\delta_{nm}} = x[n] N 1 k ∑ X [ k ] e j 2 π k n / N = N 1 k ∑ m ∑ x [ m ] e − j 2 π k m / N e j 2 π k n / N = m ∑ x [ m ] δ nm N 1 k ∑ e j 2 π k ( n − m ) / N = x [ n ] DFT의 지수에 있는 음부호는 내적의 둘째 자리에 붙는 켤레에서 온 것입니다.
참고 4.4 (정규화 관례). 1 / N 1/N 1/ N 1 / N 1/N 1/ N 1 / N 1/\sqrt{N} 1/ N
행렬로 쓰면 F k n = e − j 2 π k n / N F_{kn} = e^{-j2\pi kn/N} F k n = e − j 2 π k n / N N × N N \times N N × N X = F x X = F\mathbf{x} X = F x x = 1 N F H X \mathbf{x} = \frac{1}{N}F^HX x = N 1 F H X F F F k k k u k H \mathbf{u}_k^H u k H F F H = N I FF^H = NI F F H = N I F / N F/\sqrt{N} F / N
예제 4.5. N = 4 N = 4 N = 4 e − j 2 π / 4 = − j e^{-j2\pi/4} = -j e − j 2 π /4 = − j
F = ( 1 1 1 1 1 − j − 1 j 1 − 1 1 − 1 1 j − 1 − j ) F = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{pmatrix} F = 1 1 1 1 1 − j − 1 j 1 − 1 1 − 1 1 j − 1 − j 입니다. x = ( 1 , 2 , 3 , 4 ) \mathbf{x} = (1, 2, 3, 4) x = ( 1 , 2 , 3 , 4 )
X [ 0 ] = 1 + 2 + 3 + 4 = 10 X [ 1 ] = 1 + 2 ( − j ) + 3 ( − 1 ) + 4 ( j ) = − 2 + 2 j X [ 2 ] = 1 − 2 + 3 − 4 = − 2 X [ 3 ] = 1 + 2 ( j ) + 3 ( − 1 ) + 4 ( − j ) = − 2 − 2 j \begin{aligned}
X[0] &= 1 + 2 + 3 + 4 = 10 \\
X[1] &= 1 + 2(-j) + 3(-1) + 4(j) = -2 + 2j \\
X[2] &= 1 - 2 + 3 - 4 = -2 \\
X[3] &= 1 + 2(j) + 3(-1) + 4(-j) = -2 - 2j
\end{aligned} X [ 0 ] X [ 1 ] X [ 2 ] X [ 3 ] = 1 + 2 + 3 + 4 = 10 = 1 + 2 ( − j ) + 3 ( − 1 ) + 4 ( j ) = − 2 + 2 j = 1 − 2 + 3 − 4 = − 2 = 1 + 2 ( j ) + 3 ( − 1 ) + 4 ( − j ) = − 2 − 2 j 역변환의 n = 0 n = 0 n = 0 1 4 ( 10 − 2 + 2 j − 2 − 2 − 2 j ) = 1 \frac{1}{4}(10 - 2 + 2j - 2 - 2 - 2j) = 1 4 1 ( 10 − 2 + 2 j − 2 − 2 − 2 j ) = 1 X [ 0 ] / N = 2.5 X[0]/N = 2.5 X [ 0 ] / N = 2.5 X [ 3 ] = X [ 1 ] ∗ X[3] = X[1]^* X [ 3 ] = X [ 1 ] ∗ 정리 4.6 ).
4.3 주파수 색인 k의 해석
주기성. e j 2 π ( k + N ) n / N = e j 2 π k n / N e j 2 π n = e j 2 π k n / N e^{j2\pi(k + N)n/N} = e^{j2\pi kn/N}e^{j2\pi n} = e^{j2\pi kn/N} e j 2 π ( k + N ) n / N = e j 2 π k n / N e j 2 π n = e j 2 π k n / N u k + N = u k \mathbf{u}_{k+N} = \mathbf{u}_k u k + N = u k k k k N N N N N N k k k X [ k + N ] = X [ k ] X[k + N] = X[k] X [ k + N ] = X [ k ] n n n x [ n + N ] = x [ n ] x[n + N] = x[n] x [ n + N ] = x [ n ] x x x N N N N N N
음의 주파수. u N − k = u − k = u k ∗ \mathbf{u}_{N-k} = \mathbf{u}_{-k} = \mathbf{u}_k^* u N − k = u − k = u k ∗ k = N − 1 k = N - 1 k = N − 1 k = − 1 k = -1 k = − 1
N N N k = 0 k = 0 k = 0 k = 1 , … , N / 2 − 1 k = 1, \ldots, N/2 - 1 k = 1 , … , N /2 − 1 k = N / 2 k = N/2 k = N /2 ( + 1 , − 1 , + 1 , … ) (+1, -1, +1, \ldots) ( + 1 , − 1 , + 1 , … ) k = N / 2 + 1 , … , N − 1 k = N/2 + 1, \ldots, N - 1 k = N /2 + 1 , … , N − 1 − ( N / 2 − 1 ) , … , − 1 -(N/2 - 1), \ldots, -1 − ( N /2 − 1 ) , … , − 1
이산 신호에서 가장 빠른 진동은 한 표본마다 부호가 바뀌는 것이고 그보다 빠른 것은 없습니다. 이것이 표본화 정리(11장)의 유한차원 판입니다.
정리 4.6 (실수 신호의 켤레 대칭). x [ n ] x[n] x [ n ] X [ N − k ] = X [ k ] ∗ X[N - k] = X[k]^* X [ N − k ] = X [ k ] ∗
증명. X [ N − k ] = ∑ n x [ n ] e − j 2 π ( N − k ) n / N = ∑ n x [ n ] e j 2 π k n / N = ( ∑ n x [ n ] e − j 2 π k n / N ) ∗ X[N - k] = \sum_n x[n]e^{-j2\pi(N - k)n/N} = \sum_n x[n]e^{j2\pi kn/N} = \left(\sum_n x[n]e^{-j2\pi kn/N}\right)^* X [ N − k ] = ∑ n x [ n ] e − j 2 π ( N − k ) n / N = ∑ n x [ n ] e j 2 π k n / N = ( ∑ n x [ n ] e − j 2 π k n / N ) ∗ x [ n ] x[n] x [ n ] ■ \blacksquare ■
따라서 실수 신호의 DFT는 k = 0 , … , N / 2 k = 0, \ldots, N/2 k = 0 , … , N /2 k k k N − k N - k N − k X [ k ] u k [ n ] + X [ k ] ∗ u k [ n ] ∗ = 2 Re { X [ k ] e j 2 π k n / N } = 2 ∣ X [ k ] ∣ cos ( 2 π k n / N + ∠ X [ k ] ) X[k]\mathbf{u}_k[n] + X[k]^*\mathbf{u}_k[n]^* = 2\operatorname{Re}\{X[k]e^{j2\pi kn/N}\} = 2|X[k]|\cos(2\pi kn/N + \angle X[k]) X [ k ] u k [ n ] + X [ k ] ∗ u k [ n ] ∗ = 2 Re { X [ k ] e j 2 π k n / N } = 2∣ X [ k ] ∣ cos ( 2 π k n / N + ∠ X [ k ]) N N N
x [ n ] = 1 N [ X [ 0 ] + 2 ∑ k = 1 N / 2 − 1 ∣ X [ k ] ∣ cos ( 2 π k n N + ∠ X [ k ] ) + X [ N / 2 ] ( − 1 ) n ] ( 4.1 ) x[n] = \frac{1}{N}\left[X[0] + 2\sum_{k=1}^{N/2-1}|X[k]|\cos\left(\frac{2\pi kn}{N} + \angle X[k]\right) + X[N/2](-1)^n\right] \qquad (4.1) x [ n ] = N 1 X [ 0 ] + 2 k = 1 ∑ N /2 − 1 ∣ X [ k ] ∣ cos ( N 2 π k n + ∠ X [ k ] ) + X [ N /2 ] ( − 1 ) n ( 4.1 ) 입니다. ∣ X [ k ] ∣ |X[k]| ∣ X [ k ] ∣ k k k N / 2 N/2 N /2 ∠ X [ k ] \angle X[k] ∠ X [ k ]
예제 4.7. x [ n ] = A cos ( 2 π k 0 n / N + ϕ ) x[n] = A\cos(2\pi k_0 n/N + \phi) x [ n ] = A cos ( 2 π k 0 n / N + ϕ ) 0 < k 0 < N / 2 0 < k_0 < N/2 0 < k 0 < N /2 x = A 2 e j ϕ u k 0 + A 2 e − j ϕ u N − k 0 \mathbf{x} = \frac{A}{2}e^{j\phi}\mathbf{u}_{k_0} + \frac{A}{2}e^{-j\phi}\mathbf{u}_{N-k_0} x = 2 A e j ϕ u k 0 + 2 A e − j ϕ u N − k 0 X [ k 0 ] = N A 2 e j ϕ X[k_0] = \frac{NA}{2}e^{j\phi} X [ k 0 ] = 2 N A e j ϕ X [ N − k 0 ] = N A 2 e − j ϕ X[N - k_0] = \frac{NA}{2}e^{-j\phi} X [ N − k 0 ] = 2 N A e − j ϕ
성분의 주파수, 진폭, 위상을 바꾸면 신호 x[n]과 0이 아닌 DFT 칸이 바뀝니다 이 위젯은 JavaScript가 필요합니다
4.4 파세발 등식
정리 4.8.
∑ n = 0 N − 1 x [ n ] y [ n ] ∗ = 1 N ∑ k = 0 N − 1 X [ k ] Y [ k ] ∗ , ∑ n = 0 N − 1 ∣ x [ n ] ∣ 2 = 1 N ∑ k = 0 N − 1 ∣ X [ k ] ∣ 2 \sum_{n=0}^{N-1} x[n]\, y[n]^* = \frac{1}{N}\sum_{k=0}^{N-1} X[k]\, Y[k]^*, \qquad \sum_{n=0}^{N-1}|x[n]|^2 = \frac{1}{N}\sum_{k=0}^{N-1}|X[k]|^2 n = 0 ∑ N − 1 x [ n ] y [ n ] ∗ = N 1 k = 0 ∑ N − 1 X [ k ] Y [ k ] ∗ , n = 0 ∑ N − 1 ∣ x [ n ] ∣ 2 = N 1 k = 0 ∑ N − 1 ∣ X [ k ] ∣ 2 증명. 정규직교기저 u k / N \mathbf{u}_k/\sqrt{N} u k / N x \mathbf{x} x ⟨ x , u k / N ⟩ = X [ k ] / N \langle \mathbf{x}, \mathbf{u}_k/\sqrt{N} \rangle = X[k]/\sqrt{N} ⟨ x , u k / N ⟩ = X [ k ] / N 정리 3.21 을 적용합니다. ■ \blacksquare ■
예제 4.5에서 확인하면 1 + 4 + 9 + 16 = 30 1 + 4 + 9 + 16 = 30 1 + 4 + 9 + 16 = 30 1 4 ( 100 + 8 + 4 + 8 ) = 30 \frac{1}{4}(100 + 8 + 4 + 8) = 30 4 1 ( 100 + 8 + 4 + 8 ) = 30
4.5 이동, 고유벡터, 합성곱
이제 “왜 하필 이 기저인가”에 답합니다.
정의 4.9. 순환 이동 연산자 S S S ( S x ) [ n ] = x [ ( n − 1 ) m o d N ] (S\mathbf{x})[n] = x[(n - 1) \bmod N] ( S x ) [ n ] = x [( n − 1 ) mod N ]
정리 4.10. 푸리에 기저 벡터는 순환 이동의 고유벡터입니다:
S u k = e − j 2 π k / N u k S\mathbf{u}_k = e^{-j2\pi k/N}\mathbf{u}_k S u k = e − j 2 π k / N u k 고윳값 e − j 2 π k / N e^{-j2\pi k/N} e − j 2 π k / N k = 0 , … , N − 1 k = 0, \ldots, N - 1 k = 0 , … , N − 1
증명. u k [ n ] \mathbf{u}_k[n] u k [ n ] N N N ( S u k ) [ n ] = e j 2 π k ( n − 1 ) / N = e − j 2 π k / N e j 2 π k n / N (S\mathbf{u}_k)[n] = e^{j2\pi k(n - 1)/N} = e^{-j2\pi k/N}e^{j2\pi kn/N} ( S u k ) [ n ] = e j 2 π k ( n − 1 ) / N = e − j 2 π k / N e j 2 π k n / N ■ \blacksquare ■
복소지수함수를 시간 이동하면 모양은 그대로이고 위상 인자만 곱해집니다. e a + b = e a e b e^{a+b} = e^ae^b e a + b = e a e b
따름정리 4.11 (이동 정리). y [ n ] = x [ ( n − m ) m o d N ] y[n] = x[(n - m) \bmod N] y [ n ] = x [( n − m ) mod N ] Y [ k ] = e − j 2 π k m / N X [ k ] Y[k] = e^{-j2\pi km/N}X[k] Y [ k ] = e − j 2 π k m / N X [ k ]
증명. y = S m x = S m 1 N ∑ k X [ k ] u k = 1 N ∑ k e − j 2 π k m / N X [ k ] u k \mathbf{y} = S^m\mathbf{x} = S^m\frac{1}{N}\sum_k X[k]\mathbf{u}_k = \frac{1}{N}\sum_k e^{-j2\pi km/N}X[k]\mathbf{u}_k y = S m x = S m N 1 ∑ k X [ k ] u k = N 1 ∑ k e − j 2 π k m / N X [ k ] u k ■ \blacksquare ■
시간 이동은 크기 ∣ X [ k ] ∣ |X[k]| ∣ X [ k ] ∣
정의 4.12. x , h ∈ C N \mathbf{x}, \mathbf{h} \in \mathbb{C}^N x , h ∈ C N 순환 합성곱 (circular convolution)은
( x ⊛ h ) [ n ] = ∑ m = 0 N − 1 x [ m ] h [ ( n − m ) m o d N ] (\mathbf{x} \circledast \mathbf{h})[n] = \sum_{m=0}^{N-1} x[m]\, h[(n - m) \bmod N] ( x ⊛ h ) [ n ] = m = 0 ∑ N − 1 x [ m ] h [( n − m ) mod N ] 입니다. x ⊛ h = ∑ m x [ m ] S m h \mathbf{x} \circledast \mathbf{h} = \sum_m x[m]S^m\mathbf{h} x ⊛ h = ∑ m x [ m ] S m h h \mathbf{h} h m m m x [ m ] x[m] x [ m ]
정리 4.13 (합성곱 정리). y = x ⊛ h \mathbf{y} = \mathbf{x} \circledast \mathbf{h} y = x ⊛ h
Y [ k ] = X [ k ] H [ k ] Y[k] = X[k]\, H[k] Y [ k ] = X [ k ] H [ k ] 입니다.
증명.
Y [ k ] = ∑ n ∑ m x [ m ] h [ ( n − m ) m o d N ] e − j 2 π k n / N = ∑ m x [ m ] e − j 2 π k m / N ∑ n h [ ( n − m ) m o d N ] e − j 2 π k ( n − m ) / N \begin{aligned}
Y[k] &= \sum_n\sum_m x[m]\, h[(n - m) \bmod N]\, e^{-j2\pi kn/N} \\
&= \sum_m x[m]e^{-j2\pi km/N}\sum_n h[(n - m) \bmod N]\, e^{-j2\pi k(n - m)/N}
\end{aligned} Y [ k ] = n ∑ m ∑ x [ m ] h [( n − m ) mod N ] e − j 2 π k n / N = m ∑ x [ m ] e − j 2 π k m / N n ∑ h [( n − m ) mod N ] e − j 2 π k ( n − m ) / N 입니다. 안쪽 합에서 n n n ( n − m ) m o d N (n - m) \bmod N ( n − m ) mod N 0 , … , N − 1 0, \ldots, N - 1 0 , … , N − 1 m m m H [ k ] H[k] H [ k ] X [ k ] X[k] X [ k ] ■ \blacksquare ■
예제 4.14. h = ( 1 2 , 1 2 , 0 , 0 ) \mathbf{h} = (\frac{1}{2}, \frac{1}{2}, 0, 0) h = ( 2 1 , 2 1 , 0 , 0 ) y [ n ] = 1 2 ( x [ n ] + x [ n − 1 ] ) y[n] = \frac{1}{2}(x[n] + x[n - 1]) y [ n ] = 2 1 ( x [ n ] + x [ n − 1 ]) H [ k ] = 1 2 ( 1 + e − j 2 π k / 4 ) H[k] = \frac{1}{2}(1 + e^{-j2\pi k/4}) H [ k ] = 2 1 ( 1 + e − j 2 π k /4 ) H [ 0 ] = 1 H[0] = 1 H [ 0 ] = 1 H [ 1 ] = 1 − j 2 H[1] = \frac{1 - j}{2} H [ 1 ] = 2 1 − j H [ 2 ] = 0 H[2] = 0 H [ 2 ] = 0 H [ 3 ] = 1 + j 2 H[3] = \frac{1 + j}{2} H [ 3 ] = 2 1 + j k = 0 k = 0 k = 0 k = 2 k = 2 k = 2 ( 1 , − 1 , 1 , − 1 ) (1, -1, 1, -1) ( 1 , − 1 , 1 , − 1 ) 저역통과 필터 (low-pass filter)다.
이 절이 말하는 것
고정된 h \mathbf{h} h x ↦ x ⊛ h \mathbf{x} \mapsto \mathbf{x} \circledast \mathbf{h} x ↦ x ⊛ h S ( x ⊛ h ) = ( S x ) ⊛ h S(\mathbf{x} \circledast \mathbf{h}) = (S\mathbf{x}) \circledast \mathbf{h} S ( x ⊛ h ) = ( S x ) ⊛ h C N \mathbb{C}^N C N A A A h \mathbf{h} h δ = ( 1 , 0 , … , 0 ) \boldsymbol{\delta} = (1, 0, \ldots, 0) δ = ( 1 , 0 , … , 0 ) h = A δ \mathbf{h} = A\boldsymbol{\delta} h = A δ x = ∑ m x [ m ] S m δ \mathbf{x} = \sum_m x[m]S^m\boldsymbol{\delta} x = ∑ m x [ m ] S m δ A x = ∑ m x [ m ] S m A δ = x ⊛ h A\mathbf{x} = \sum_m x[m]S^mA\boldsymbol{\delta} = \mathbf{x} \circledast \mathbf{h} A x = ∑ m x [ m ] S m A δ = x ⊛ h k k k H [ k ] H[k] H [ k ] 정리 3.29 가 예고한 그대로입니다.
푸리에 변환이 하는 일 (유한차원 판)
푸리에 기저는 직교기저입니다. 그래서 좌표를 내적 하나로 구합니다(DFT).
푸리에 기저는 이동의 고유벡터입니다. 그래서 이동과 교환하는 모든 선형 연산(합성곱, 필터)이 좌표별 곱셈이 됩니다.
변환은 (상수를 빼면) 유니터리입니다. 그래서 에너지와 내적이 보존됩니다(파세발).
남은 일은 N → ∞ N \to \infty N → ∞
쓰이는 곳. 디지털 오디오의 주파수 분석, 이미지의 2차원 DFT, 수치적으로 미분방정식을 푸는 스펙트럴 방법, 큰 수의 곱셈 알고리즘이 DFT를 씁니다. 순환행렬이 DFT로 대각화된다는 사실은 합성곱 신경망을 빠르게 계산하는 데 쓰입니다.
연습문제
문제 1 · 확인 문제
4.1. N = 4 N = 4 N = 4 ( 1 , 0 , 0 , 0 ) (1, 0, 0, 0) ( 1 , 0 , 0 , 0 ) ( 0 , 1 , 0 , 0 ) (0, 1, 0, 0) ( 0 , 1 , 0 , 0 ) ( 1 , 1 , 0 , 0 ) (1, 1, 0, 0) ( 1 , 1 , 0 , 0 ) ( 1 , 1 , 0 , 0 ) (1, 1, 0, 0) ( 1 , 1 , 0 , 0 )
k k k Re X [ k ] \operatorname{Re} X[k] Re X [ k ] Im X [ k ] \operatorname{Im} X[k] Im X [ k ]
0
[?]
[?]
1
[?]
[?]
2
[?]
[?]
3
[?]
[?]
힌트 1 DFT는 선형입니다. 앞의 두 신호의 DFT를 더하면 됩니다.
정답 풀이 ( 1 , 0 , 0 , 0 ) → ( 1 , 1 , 1 , 1 ) (1, 0, 0, 0) \to (1, 1, 1, 1) ( 1 , 0 , 0 , 0 ) → ( 1 , 1 , 1 , 1 ) ( 0 , 1 , 0 , 0 ) → ( 1 , − j , − 1 , j ) (0, 1, 0, 0) \to (1, -j, -1, j) ( 0 , 1 , 0 , 0 ) → ( 1 , − j , − 1 , j ) e − j 2 π k / 4 = ( − j ) k e^{-j2\pi k/4} = (-j)^k e − j 2 π k /4 = ( − j ) k ( 1 , 1 , 0 , 0 ) (1, 1, 0, 0) ( 1 , 1 , 0 , 0 ) ( 2 , 1 − j , 0 , 1 + j ) (2, 1 - j, 0, 1 + j) ( 2 , 1 − j , 0 , 1 + j ) 1 + 1 = 2 1 + 1 = 2 1 + 1 = 2 1 4 ( 4 + 2 + 0 + 2 ) = 2 \frac{1}{4}(4 + 2 + 0 + 2) = 2 4 1 ( 4 + 2 + 0 + 2 ) = 2
문제 2 · 확인 문제
4.2. N = 8 N = 8 N = 8 x [ n ] = 3 + 2 cos ( π n 2 + π 3 ) x[n] = 3 + 2\cos(\frac{\pi n}{2} + \frac{\pi}{3}) x [ n ] = 3 + 2 cos ( 2 π n + 3 π )
칸
크기
위상 (도)
X [ 0 ] X[0] X [ 0 ] [?]
[?]
X [ 2 ] X[2] X [ 2 ] [?]
[?]
X [ 6 ] X[6] X [ 6 ] [?]
[?]
힌트 1 cos ( π n 2 + π 3 ) = cos ( 2 π ⋅ 2 n / 8 + π 3 ) \cos(\frac{\pi n}{2} + \frac{\pi}{3}) = \cos(2\pi \cdot 2n/8 + \frac{\pi}{3}) cos ( 2 π n + 3 π ) = cos ( 2 π ⋅ 2 n /8 + 3 π ) k 0 = 2 k_0 = 2 k 0 = 2
정답 풀이 cos ( π n 2 + π 3 ) = cos ( 2 π ⋅ 2 n / 8 + π 3 ) \cos(\frac{\pi n}{2} + \frac{\pi}{3}) = \cos(2\pi \cdot 2n/8 + \frac{\pi}{3}) cos ( 2 π n + 3 π ) = cos ( 2 π ⋅ 2 n /8 + 3 π ) k 0 = 2 k_0 = 2 k 0 = 2 X [ 2 ] = 8 ⋅ 2 2 e j π / 3 = 8 e j π / 3 X[2] = \frac{8 \cdot 2}{2}e^{j\pi/3} = 8e^{j\pi/3} X [ 2 ] = 2 8 ⋅ 2 e j π /3 = 8 e j π /3 X [ 6 ] = 8 e − j π / 3 X[6] = 8e^{-j\pi/3} X [ 6 ] = 8 e − j π /3 X [ 0 ] = 24 X[0] = 24 X [ 0 ] = 24
문제 3 · 확인 문제
4.3. x = ( 1 , 2 , 3 , 4 ) \mathbf{x} = (1, 2, 3, 4) x = ( 1 , 2 , 3 , 4 ) h = ( 1 , 0 , 0 , 1 ) \mathbf{h} = (1, 0, 0, 1) h = ( 1 , 0 , 0 , 1 ) y \mathbf{y} y
n n n 0
1
2
3
y [ n ] y[n] y [ n ] [?]
[?]
[?]
[?]
힌트 1 h h h n = 0 n = 0 n = 0 n = 3 n = 3 n = 3 y [ n ] = x [ n ] h [ 0 ] + x [ ( n − 3 ) m o d 4 ] h [ 3 ] y[n] = x[n]h[0] + x[(n - 3) \bmod 4]h[3] y [ n ] = x [ n ] h [ 0 ] + x [( n − 3 ) mod 4 ] h [ 3 ]
정답 풀이 (a) y [ n ] = x [ n ] h [ 0 ] + x [ ( n − 3 ) m o d 4 ] h [ 3 ] = x [ n ] + x [ ( n + 1 ) m o d 4 ] y[n] = x[n]h[0] + x[(n - 3) \bmod 4]h[3] = x[n] + x[(n + 1) \bmod 4] y [ n ] = x [ n ] h [ 0 ] + x [( n − 3 ) mod 4 ] h [ 3 ] = x [ n ] + x [( n + 1 ) mod 4 ] y = ( 3 , 5 , 7 , 5 ) \mathbf{y} = (3, 5, 7, 5) y = ( 3 , 5 , 7 , 5 )
(b) H [ k ] = 1 + e − j 2 π ⋅ 3 k / 4 = 1 + j k H[k] = 1 + e^{-j2\pi \cdot 3k/4} = 1 + j^k H [ k ] = 1 + e − j 2 π ⋅ 3 k /4 = 1 + j k H = ( 2 , 1 + j , 0 , 1 − j ) H = (2, 1 + j, 0, 1 - j) H = ( 2 , 1 + j , 0 , 1 − j ) X = ( 10 , − 2 + 2 j , − 2 , − 2 − 2 j ) X = (10, -2 + 2j, -2, -2 - 2j) X = ( 10 , − 2 + 2 j , − 2 , − 2 − 2 j ) Y = ( 20 , − 4 , 0 , − 4 ) Y = (20, -4, 0, -4) Y = ( 20 , − 4 , 0 , − 4 ) y [ 0 ] = 1 4 ( 20 − 4 − 4 ) = 3 y[0] = \frac{1}{4}(20 - 4 - 4) = 3 y [ 0 ] = 4 1 ( 20 − 4 − 4 ) = 3 y [ 1 ] = 1 4 ( 20 − 4 j + 4 j ) = 5 y[1] = \frac{1}{4}(20 - 4j + 4j) = 5 y [ 1 ] = 4 1 ( 20 − 4 j + 4 j ) = 5 y [ 2 ] = 1 4 ( 20 + 4 + 4 ) = 7 y[2] = \frac{1}{4}(20 + 4 + 4) = 7 y [ 2 ] = 4 1 ( 20 + 4 + 4 ) = 7 y [ 3 ] = 5 y[3] = 5 y [ 3 ] = 5
문제 4
4.4. x [ n ] x[n] x [ n ] x [ N − n ] = x [ n ] x[N - n] = x[n] x [ N − n ] = x [ n ] X [ k ] X[k] X [ k ]
힌트 1 X [ k ] ∗ X[k]^* X [ k ] ∗ m = N − n m = N - n m = N − n
풀이 X [ k ] ∗ = ∑ n x [ n ] e j 2 π k n / N X[k]^* = \sum_n x[n]e^{j2\pi kn/N} X [ k ] ∗ = ∑ n x [ n ] e j 2 π k n / N m = N − n m = N - n m = N − n ∑ m x [ N − m ] e − j 2 π k m / N e j 2 π k = ∑ m x [ m ] e − j 2 π k m / N = X [ k ] \sum_m x[N - m]e^{-j2\pi km/N}e^{j2\pi k} = \sum_m x[m]e^{-j2\pi km/N} = X[k] ∑ m x [ N − m ] e − j 2 π k m / N e j 2 π k = ∑ m x [ m ] e − j 2 π k m / N = X [ k ] X [ k ] ∗ = X [ k ] X[k]^* = X[k] X [ k ] ∗ = X [ k ] X [ k ] X[k] X [ k ]
문제 5 · 확인 문제
x = ( 2 , − 1 , 0 , 3 ) \mathbf{x} = (2, -1, 0, 3) x = ( 2 , − 1 , 0 , 3 ) ∑ k = 0 3 ∣ X [ k ] ∣ 2 \sum_{k=0}^{3}|X[k]|^2 ∑ k = 0 3 ∣ X [ k ] ∣ 2
힌트 1 파세발 등식에서 ∑ k ∣ X [ k ] ∣ 2 = N ∑ n ∣ x [ n ] ∣ 2 \sum_k |X[k]|^2 = N\sum_n |x[n]|^2 ∑ k ∣ X [ k ] ∣ 2 = N ∑ n ∣ x [ n ] ∣ 2
정답 풀이 ∑ n ∣ x [ n ] ∣ 2 = 4 + 1 + 0 + 9 = 14 \sum_n |x[n]|^2 = 4 + 1 + 0 + 9 = 14 ∑ n ∣ x [ n ] ∣ 2 = 4 + 1 + 0 + 9 = 14 ∑ k ∣ X [ k ] ∣ 2 = 4 ⋅ 14 = 56 \sum_k |X[k]|^2 = 4 \cdot 14 = 56 ∑ k ∣ X [ k ] ∣ 2 = 4 ⋅ 14 = 56
