맨위로가기

이산 푸리에 변환

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

이산 푸리에 변환(DFT)은 유한한 개수의 복소수 신호를 다른 복소수 값으로 변환하는 선형 변환으로, 푸리에 변환의 이산적인 형태이다. DFT는 선형성, 시간 및 주파수 반전, 시간 켤레 등의 성질을 가지며, 파르세발 정리와 플랑쉐렐 정리와 같은 유니터리 조건을 만족한다. DFT는 스펙트럼 분석, 광학, 필터 뱅크, 데이터 압축, 편미분 방정식 풀이, 다항식 곱셈, 큰 정수 곱셈, 합성곱 계산 등 다양한 분야에 응용된다. DFT는 고속 푸리에 변환(FFT) 알고리즘을 통해 효율적으로 계산될 수 있으며, 웨이블릿 변환과 같은 대안적인 변환 방법도 존재한다.

2. 정의

이산 푸리에 변환(DFT, Discrete Fourier Transform)은 N개의 복소수 신호 x_0, x_1, ..., x_{N-1}를 복소수 값 X_0, X_1, ..., X_{N-1}으로 변환하는 선형 변환이다. 변환식은 다음과 같이 정의된다.[11]

:X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n},\qquad k = 0, \cdots, N-1

역변환(Inverse Discrete Fourier Transform, IDFT)은 다음과 같이 정의된다.

:x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k e^{\frac{2\pi i}{N} k n},\qquad n = 0,\cdots,N-1

이 변환은 때때로 \mathcal{F} 기호로 표현되기도 하며, \mathbf{X} = \mathcal{F} \left \{ \mathbf{x} \right \} 또는 \mathcal{F} \left ( \mathbf{x} \right ) 또는 \mathcal{F} \mathbf{x}와 같이 나타낼 수 있다. X_k는 k \in [0,N-1] 영역 외부에서도 계산될 수 있으며, 확장된 수열은 N-주기적이다. x_n 또한 N-주기적이다(색인 n에서). 각 X_k는 복소수이며, 그 극좌표는 함수 x_n의 복소 정현파 성분 \left(e^{i 2 \pi \tfrac{k}{N}n}\right)의 진폭과 위상이다. (이산 푸리에 급수 참조) 정현파의 주파수는 N개의 표본당 k 사이클이다.

DFT와 IDFT에 곱해지는 정규화 계수(여기서는 1과 \tfrac{1}{N})와 지수의 부호는 가장 일반적인 규칙이다. 이러한 규칙에 대한 유일한 실제 요구 사항은 DFT와 IDFT가 반대 부호의 지수를 가지며, 그 정규화 계수의 곱이 \tfrac{1}{N}이라는 것이다.

이산 푸리에 변환에서는 유한 개의 표본점만 사용하기 때문에, 어떤 함수를 이산 푸리에 변환하고 그것을 역변환했을 때, 표본점 이외에서는 원래 함수와 일치한다고는 할 수 없다. 즉, 복소 함수 f에 대해,

:F(t)= \sum_{x=0}^{N-1} f(x) \exp\left(-i\frac{2 \pi t x}{N}\right)

에 의해 이산 푸리에 변환을 하고, 그것을 역변환한 것을 g라고 하면

:f(x)=g(x) \quad x = 0,\dots,N-1

은 말할 수 있지만, 그 외의 점에서 f(x)=g(x)라고 말할 수 있는 것은 아니다. 이것을 고주파 문제 또는 앨리어싱(aliasing)이라고 한다.

이산 푸리에 변환을 F_n=\dfrac{1}{N} \sum^{N-1}_{k=0}f_k e^{-i \dfrac{2n \pi}{N}k}, 이산 푸리에 역변환을 f_k=\sum^{N-1}_{n=0} F_n e^{i \dfrac{2n \pi}{N} k}으로 정의하는 경우도 있다.

3. 성질

이산 푸리에 변환(DFT)은 푸리에 변환과 유사한 성질을 갖는다. 주요 성질은 다음과 같다.

W=e^{-i\frac{2\pi}{N}}라고 할 때, 시간 영역과 주파수 영역에서의 관계는 아래 표와 같다.

시간 영역주파수 영역비고
f(x)=\frac{1}{N}\sum_{k=0}^{N-1}F(k)W^{-kx}F(t)=\sum_{n=0}^{N-1}f(n) W^{tn}IDFT, DFT의 W를 이용한 정의
f(x)F(t)정의
g(x)G(t)정의
af(x)+bg(x)aF(t)+bG(t)선형성
f(x){e^{i\frac{2\pi{mx}}{N}}}F(t-m)시간축 변조, 주파수축 이동
f(x-a)W^{at}F(t)시간축 이동 (양)
f(x+a)W^{-at}F(t)시간축 이동 (음)
\sum_{m=0}^{N-1}f(m)g(x-m)F(t)G(t)시간축 컨벌루션, 주파수축 곱
f(x)g(x){\frac{1}{N}}\sum_{m=0}^{N-1}F(m)G(t-m)시간축 곱, 주파수축 컨벌루션
\overline{f(x)}\overline{F(N-t)}시간축 공액, 주파수축 반전
\overline{f(N-x)}\overline{F(t)}시간축 반전, 주파수축 공액
Re(f(x))\frac{1}{2}(F(t)+\overline{F(N-t)})시간축 실수부, 주파수축 우함수
Im(f(x))\frac{1}{2i}(F(t)-\overline{F(N-t)})시간축 허수부, 주파수축 기함수
\frac{1}{2}(f(x)+\overline{f(N-x)})Re(F(t))시간축 우함수, 주파수축 실수부
\frac{1}{2i}(f(x)-\overline{f(N-x)})Im(F(t))시간축 기함수, 주파수축 허수부
a^x\,\frac{1-a^N{W}^{tx}}{1-{a}W^t}멱승


  • 직교성: 벡터 u_k = \left[\left. e^{ \frac{i 2\pi}{N} kn} \;\right|\; n=0,1,\ldots,N-1 \right]^\mathsf{T}는 N차원 복소 벡터 집합에 대한 직교 기저를 형성한다.[1]
  • 플란케렐 정리와 파세발 정리: X_k와 Y_k가 각각 x_n와 y_n의 DFT라면, 파르세발의 정리는 \(\sum_{n=0}^{N-1} x_n y^*_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k Y^*_k\)이다. 플랑쉐렐 정리는 \(\sum_{n=0}^{N-1} |x_n|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X_k|^2\)이다.
  • 주기성: DFT는 \(X_{k+N} = X_k\)로 표현되는 주기성을 갖는다.
  • 이동 정리: 정수 ''m''에 대해 x_n에 선형 위상 e^{\frac{i 2\pi}{N} nm}을 곱하면 출력 X_k는 순환 시프트되어 X_{k-m}이 된다.
  • 원형 합성곱 정리 및 상호 상관 정리: 두 함수 f(x)와 g(x)의 컨벌루션은 \((f*g)(x) = \sum_{n=0}^{N-1} f(n) g(x-n)\)로 정의된다. 주기 함수의 컨벌루션을 DFT하면 각각의 DFT의 곱이 된다.
  • 합성곱 정리의 이중성: 시간 영역의 곱은 주파수 영역에서의 원형 합성곱으로 표현 가능하다.
  • 삼각 보간 다항식: DFT 계수 ''X''''k''는 삼각 보간 다항식을 만드는 데 사용된다.
  • 유니타리 DFT: DFT는 유니타리 행렬로 정의된 유니터리 변환이 될 수 있다.
  • 역 DFT를 DFT로 표현하기: 역 DFT는 입력과 출력의 켤레 복소수를 취하는 등의 방법으로 DFT로 표현할 수 있다.
  • 고유값과 고유벡터: DFT 행렬의 고유값은 단순하지만, 고유벡터는 복잡하고 유일하지 않다.
  • 불확정성 원리: 하이젠베르크의 불확정성 원리와 유사한 불확정성 원리가 DFT에도 적용된다.
  • 실수 및 순수 허수 신호의 DFT: 입력 신호가 실수이면 DFT는 짝대칭을, 순허수이면 홀대칭을 갖는다.

3. 1. 선형성 (Linearity)

DFT는 선형 변환이다. 즉, ${\mathcal {F}}(\{x_{n}\})_{k}=X_{k}$이고 ${\mathcal {F}}(\{y_{n}\})_{k}=Y_{k}$라면, 임의의 복소수 $a,b$에 대해 다음이 성립한다.

:${\mathcal {F}}(\{ax_{n}+by_{n}\})_{k}=aX_{k}+bY_{k}$

3. 2. 시간 및 주파수 반전 (Time and Frequency Reversal)

시간을 반전(즉, n을 N-n으로 대체)시키는 것은 주파수를 반전(즉, k를 N-k로 대체)시키는 것과 같다.[12] 수학적으로, 만약 xn영어이 벡터 '''x'''를 나타낸다면,

  • 만약 \mathcal{F}(\{x_n\})_k=X_k라면,
  • \mathcal{F}(\{ x_{N-n} \})_k=X_{N-k}이다.

3. 3. 시간 켤레 (Conjugation in Time)

만약 \mathcal{F}(\{x_n\})_k = X_k이면 \mathcal{F}(\{ x_n^* \})_k = X_{N-k}^*이다.[12]

3. 4. 실수부와 허수부 (Real and Imaginary Part)

x_n주파수 영역
X_k시간 영역의 실수 부분\operatorname{Re}{\left(x_n\right)}\frac{1}{2}\left(X_k + X^*_{N-k}\right)시간 영역의 허수 부분\operatorname{Im}{\left(x_n\right)}\frac{1}{2i}\left(X_k - X^*_{N-k}\right)주파수 영역의 실수 부분\frac{1}{2}\left(x_n + x^*_{N-n}\right)\operatorname{Re}{\left(X_k\right)}주파수 영역의 허수 부분\frac{1}{2i}\left(x_n - x^*_{N-n}\right)\operatorname{Im}{\left(X_k\right)}


3. 5. 직교성 (Orthogonality)

벡터 u_k = \left[\left. e^{ \frac{i 2\pi}{N} kn} \;\right|\; n=0,1,\ldots,N-1 \right]^\mathsf{T}는 N차원 복소 벡터 집합에 대한 직교 기저를 형성한다.[1]

:u^\mathsf{T}_k u_{k'}^*

= \sum_{n=0}^{N-1} \left(e^{ \frac{i 2\pi}{N} kn}\right) \left(e^{\frac{i 2\pi}{N} (-k')n}\right)

= \sum_{n=0}^{N-1} e^{ \frac{i 2\pi}{N} (k-k') n}

= N~\delta_{kk'}



여기서 \delta_{kk'}는 크로네커 델타이다. (마지막 단계에서, k=k'이면 합은 자명하며 1 + 1 + ⋯ = ''N'' 이고, 그렇지 않으면 명시적으로 합을 구하여 0을 얻을 수 있는 등비수열이다.)[1] 이 직교 조건은 DFT의 정의로부터 IDFT의 공식을 유도하는 데 사용될 수 있으며, 아래의 유니터리 성질과 동등하다.

h(t,x)=\exp(i2\pi t x/N)는 내적

:(f,g)=\sum_{n=0}^{N-1} {f(n)}^{*} g(n)

에 관하여, t,t'가 정수일 때 직교 기저이다.[2]

:(h(t,x),h(t',x))=\sum_{n=0}^{N-1}

\exp \left(-i2\pi\frac{tn}{N}\right)

\exp \left(i2\pi\frac{t'n}{N}\right)

=N~\delta_{tt'}

\delta_{tt'}는 크로네커의 델타.[2]

3. 6. 플란케렐 정리와 파세발 정리 (The Plancherel Theorem and Parseval's Theorem)

X_k와 Y_k가 각각 x_n와 y_n의 이산 푸리에 변환(DFT)이라면, 파르세발의 정리는 다음과 같이 나타낼 수 있다.

:\sum_{n=0}^{N-1} x_n y^*_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k Y^*_k

여기서 별표(*)는 켤레 복소수를 나타낸다. 플랑쉐렐 정리는 파르세발 정리의 특수한 경우이며 다음과 같다.

:\sum_{n=0}^{N-1} |x_n|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X_k|^2.

이러한 정리는 아래의 유니터리 조건과도 동등하다.

3. 7. 주기성 (Periodicity)

DFT는 다음 정의에서 직접적으로 주기성을 확인할 수 있다.

:X_{k+N} \ \triangleq \ \sum_{n=0}^{N-1} x_n e^{-\frac{i 2\pi}{N} (k+N) n} = \sum_{n=0}^{N-1} x_n e^{-\frac{i 2\pi}{N} k n} \underbrace{e^{-i 2 \pi n}}_{1} = \sum_{n=0}^{N-1} x_n e^{-\frac{i 2\pi}{N} k n} = X_k.

마찬가지로, 역이산 푸리에 변환(IDFT) 공식이 주기적 확장으로 이어짐을 보일 수 있다.

이산 푸리에 변환에서는 유한 개의 표본점만 사용하기 때문에, 어떤 함수를 이산 푸리에 변환하고 그것을 역변환했을 때, 표본점 이외에서는 원래 함수와 일치한다고는 할 수 없다.

즉, 복소 함수 f에 대해,

:F(t)= \sum_{x=0}^{N-1} f(x) \exp\left(-i\frac{2 \pi t x}{N}\right)

에 의해 이산 푸리에 변환을 하고, 그것을 역변환한 것을 g라고 하면

:f(x)=g(x) \quad x = 0,\dots,N-1

은 말할 수 있지만, 그 외의 점에서 f(x)=g(x)라고 말할 수 있는 것은 아니다. 이것을 고주파 문제 또는 앨리어싱이라고 한다.

3. 8. 이동 정리 (Shift Theorem)

어떤 정수 ''m''에 대해 x_n에 선형 위상 e^{\frac{i 2\pi}{N} nm}을 곱하는 것은 출력 X_k의 순환 시프트에 해당한다. X_k는 X_{k-m}으로 대체되며, 여기서 아래첨자는 모듈로 ''N''(즉, 주기적으로) 해석된다. 마찬가지로, 입력 x_n의 순환 시프트는 출력 X_k에 선형 위상을 곱하는 것에 해당한다. 수학적으로, \{x_n\}이 벡터 '''x'''를 나타낸다면:

만약 \mathcal{F}(\{x_n\})_k=X_k 이라면,

그러면 \mathcal{F}\left(\left\{ x_n \cdot e^{\frac{i 2\pi}{N}n m} \right\}\right)_k=X_{k-m} 이고,

그리고 \mathcal{F}\left(\left\{x_{n-m}\right\}\right)_k=X_k \cdot e^{-\frac{i 2\pi}{N}k m}이다.

3. 9. 원형 합성곱 정리 및 상호 상관 정리 (Circular Convolution Theorem and Cross-Correlation Theorem)

Circular convolution theorem and cross-correlation theorem영어

이산 시간 푸리에 변환(DTFT)에 대한 컨벌루션 정리는 두 수열의 컨벌루션을 각 변환의 곱의 역변환으로 얻을 수 있음을 나타낸다. 하나의 수열이 N-주기적일 때, y_{_N}로 표시되는 중요한 단순화가 발생한다. \scriptstyle \text{DTFT} \displaystyle \{y_{_N}\}는 이산 주파수에서만 0이 아니기 때문이다. 따라서 연속 함수 \scriptstyle \text{DTFT} \displaystyle \{x\}와의 곱도 마찬가지이다. 이는 역변환을 상당히 단순화한다.

:x * y_{_N}\ =\ \scriptstyle{\rm DTFT}^{-1} \displaystyle \left[\scriptstyle{\rm DTFT} \displaystyle \{x\}\cdot \scriptstyle{\rm DTFT} \displaystyle \{y_{_N}\}\right]\ =\ \scriptstyle{\rm DFT}^{-1} \displaystyle \left[\scriptstyle{\rm DFT} \displaystyle \{x_{_N}\}\cdot \scriptstyle{\rm DFT} \displaystyle \{y_{_N}\}\right],

여기서 x_{_N}는 x 수열의 주기적 합이다.

일반적으로 DFT와 역 DFT 합산은 영역 [0,N-1]에서 이루어진다. 이러한 DFT를 X와 Y로 정의하면 결과는 다음과 같다.

:

(x * y_{_N})_n \triangleq \sum_{\ell=-\infty}^{\infty}x_\ell \cdot (y_{_N})_{n-\ell} = \underbrace{\mathcal{F}^{-1}}_{\rm DFT^{-1}} \left \{ X\cdot Y \right \}_n.

x 수열은 일반적으로 길이가 ''N'' 이하이며, y_{_N}는 N 길이의 y 수열의 주기적 확장이며, 이는 ''원형 함수''로도 표현될 수 있다.

:(y_{_N})_n = \sum_{p=-\infty}^\infty y_{(n-pN)} = y_{(n\operatorname{mod}N)}, \quad n\in\mathbb{Z}.

그러면 컨벌루션은 다음과 같이 쓸 수 있다.

:

\mathcal{F}^{-1} \left \{ X\cdot Y \right \}_n = \sum_{\ell=0}^{N-1}x_\ell \cdot y_{_{(n-\ell)\operatorname{mod}N}}



이는 x와 y의 ''원형'' 컨벌루션으로 해석된다.[13][14] 이는 선형 컨벌루션을 효율적으로 계산하는 데 자주 사용된다.

마찬가지로, x와 y_{_N}의 상호상관은 다음과 같이 주어진다.

:(x \star y_{_N})_n \triangleq \sum_{\ell=-\infty}^{\infty} x_\ell^* \cdot (y_{_N})_{n+\ell} = \mathcal{F}^{-1} \left \{ X^* \cdot Y \right \}_n.

두 개의 (일반적으로는 복소수 값의) 함수 f(x)와 g(x)의 컨벌루션(convolution) f*g는 다음과 같이 정의된다.

:(f*g)(x) = \sum_{n=0}^{N-1} f(n) g(x-n)

단, f와 g는 다음과 같은 주기성을 갖는다고 가정한다.

:\begin{align}

f(x+N)&=f(x) \\

g(x+N)&=g(x)

\end{align}

주기 함수의 컨벌루션을 이산 푸리에 변환(DFT)하면 각각의 이산 푸리에 변환의 곱이 된다(컨벌루션 정리). 즉,

:\mathcal{F}_N(f*g)=\mathcal{F}_N(f)\mathcal{F}_N(g)

컨벌루션 합을 직접 정의식을 사용하여 계산하면 O(N²)의 계산량이 소요된다. 하지만, 위 식에 따라 DFT를 한 후 곱셈을 하고, IDFT로 되돌리는 방법도 있다. DFT의 고속 알고리즘인 FFT를 통해 이렇게 계산하면 O(N log N)의 계산량으로 처리할 수 있다.

또한, 두 개의 (일반적으로는 복소수 값의) 함수 f(x)와 g(x)의 상호 상관 함수(cross-correlation) f\star g는 다음과 같이 정의된다.

:h(x)=(f\star g)(x)= \sum_{n=0}^{N-1}f(n)g(x+n)

f,g가 위의 주기성을 가지면,

:(\mathcal{F}_Nh)(u)=(\mathcal{F}_N(f\star g))(u)=\mathcal{F}_N(f)(-u)\mathcal{F}_N(g)(u)

또한 f의 함수값이 실수라면, \mathcal{F}_N(f)(-u)=\overline{\mathcal{F}_N(f)(u)}가 된다. 여기서 위에 밑줄 친 \bar{z}는 z의 복소수 공액을 나타낸다.

3. 10. 합성곱 정리의 이중성 (Convolution Theorem Duality)

위에서 보았듯이, 이산 푸리에 변환(Discrete Fourier Transform, DFT)은 합성곱을 성분곱으로 변환하는 기본적인 성질을 가지고 있다. 이러한 능력을 가진 변환이 DFT뿐인지에 대한 질문이 있을 수 있는데, 합성곱을 점별 곱으로 바꾸는 모든 선형 변환은 계수의 순열을 제외하고는 DFT임이 증명되었다.[2][20] n개 원소의 순열의 수는 n!이므로, 합성곱에 대해 DFT와 같은 기본적인 성질을 가진 선형적이고 가역적인 사상은 정확히 n!개 존재한다.

시간 영역의 곱은 주파수 영역에서의 원형 합성곱으로 표현 가능하다.

:\mathcal{F} \left \{ \mathbf{x\cdot y} \right \}_k \ \triangleq

\sum_{n=0}^{N-1} x_n \cdot y_n \cdot e^{-i \frac{2\pi}{N} k n}

:=\frac{1}{N} (\mathbf{X * Y_N})_k, 여기서 \mathbf{X}와 \mathbf{Y}는 원형 합성곱이다.

3. 11. 삼각 보간 다항식 (Trigonometric Interpolation Polynomial)

DFT 계수 ''X''''k''는 다음 식과 같이 ''x''''n''의 DFT로 주어지는 삼각 보간 다항식을 만드는 데 사용될 수 있다. (n = 0, \ldots, N-1에 대해 p(n/N) = x_n이 성립한다.)

:p(t) = \begin{cases}

\displaystyle\frac{1}{N}

\left[ \begin{alignat}{3}

X_0 + X_1 e^{i 2\pi t} + \cdots

&+ X_{\frac{N}{2}-1} e^{i 2\pi\big(\!\frac{N}{2}-1\!\big) t} &\\

&+ X_{\frac{N}{2}} \cos(N\pi t) &\\

&+ X_{\frac{N}{2}+1} e^{-i 2\pi\big(\!\frac{N}{2}-1\!\big) t} &+ \cdots + X_{N-1} e^{-i 2\pi t}

\end{alignat} \right]

& N\text{ 짝수} \\

\displaystyle\frac{1}{N}

\left[ \begin{alignat}{3}

X_0 + X_1 e^{i 2\pi t} + \cdots

&+ X_{\frac{N-1}{2}} e^{i 2\pi\frac{N-1}{2} t} &\\

&+ X_{\frac{N+1}{2}} e^{-i 2\pi\frac{N-1}{2} t} &+ \cdots + X_{N-1} e^{-i 2\pi t}

\end{alignat} \right]

& N\text{ 홀수}

\end{cases}

짝수 ''N''의 경우, 나이퀴스트 성분 \frac{X_{N/2}}{N} \cos(N\pi t)는 특별히 처리된다.

이 보간은 유일하지 않다. 에일리어싱은 복소 사인파 주파수에 ''N''을 더할 수 있다는 것을 의미한다. (예: e^{-it}를 e^{i(N-1)t}로 변경) 보간 속성을 변경하지 않으면서 x_n 점 사이에 다른 값을 제공한다. 그러나 위의 보간은 최소 가능한 크기를 갖는 사인파로 구성되어 대역 제한된다는 점과 x_n이 실수이면 p(t)도 실수라는 두 가지 유용한 속성을 가지고 있어 일반적이다.

반대로, 주파수 범위가 0부터 N-1까지인 삼각 보간 다항식은 역 DFT 공식과 유사하며, 기울기를 최소화하지 않고 실수 x_n에 대해 일반적으로 실수값이 아니므로 주의해야 한다.

이산 푸리에 변환은 유한 개의 표본점만 사용하기 때문에, 어떤 함수를 이산 푸리에 변환하고 역변환했을 때, 표본점 이외에서는 원래 함수와 일치하지 않을 수 있다. 이를 고주파 문제 또는 앨리어싱이라고 한다.

3. 12. 유니타리 DFT (The Unitary DFT)

DFT는 DFT 행렬(반데르몽드 행렬)로 표현될 수 있다. 이 행렬은 1867년 실베스터(Sylvester)가 소개하였다.

:\mathbf{F} =

\begin{bmatrix}

\omega_N^{0 \cdot 0} & \omega_N^{0 \cdot 1} & \cdots & \omega_N^{0 \cdot (N-1)} \\

\omega_N^{1 \cdot 0} & \omega_N^{1 \cdot 1} & \cdots & \omega_N^{1 \cdot (N-1)} \\

\vdots & \vdots & \ddots & \vdots \\

\omega_N^{(N-1) \cdot 0} & \omega_N^{(N-1) \cdot 1} & \cdots & \omega_N^{(N-1) \cdot (N-1)} \\

\end{bmatrix}



여기서 \omega_N = e^{-i 2 \pi/N}는 원시 N차 단위근이다.

역변환은 위 행렬의 역행렬로 주어지는데, 다음과 같다.

:\mathbf{F}^{-1}=\frac{1}{N}\mathbf{F}^*

유니터리 정규화 상수 1/\sqrt{N}를 사용하면, DFT는 유니터리 행렬로 정의된 유니터리 변환이 된다.

:\begin{align}

\mathbf{U} &= \frac{1}{\sqrt{N}}\mathbf{F} \\

\mathbf{U}^{-1} &= \mathbf{U}^* \\

\left|\det(\mathbf{U})\right| &= 1

\end{align}

여기서 \det()는 행렬식 함수이다. 행렬식은 고유값들의 곱이며, 항상 \pm 1 또는 \pm i이다. 실수 벡터 공간에서 유니터리 변환은 좌표계의 강체 회전으로 간주될 수 있으며, 강체 회전의 모든 속성은 유니터리 DFT에서 발견될 수 있다.

DFT의 직교성은 직교정규 조건으로 표현된다.

:\sum_{m=0}^{N-1}U_{km}U_{mn}^* = \delta_{kn}

만약 '''X'''가 벡터 '''x'''의 유니터리 DFT로 정의된다면, 다음과 같다.

:X_k = \sum_{n=0}^{N-1} U_{kn} x_n

그리고, 파르세발 정리는 다음과 같이 표현된다.

:\sum_{n=0}^{N-1}x_n y_n^* = \sum_{k=0}^{N-1}X_k Y_k^*

DFT를 단순히 새로운 좌표계에서 벡터의 성분을 지정하는 좌표 변환으로 본다면, 위 식은 유니터리 DFT 변환하에서 두 벡터의 내적이 보존된다는 것을 의미한다. 특수한 경우 \mathbf{x} = \mathbf{y}에 대해, 이것은 벡터의 길이도 보존됨을 의미한다. 이것은 바로 플랑쉐렐 정리이다.

:\sum_{n=0}^{N-1} |x_n|^2 = \sum_{k=0}^{N-1} |X_k|^2

3. 13. 역 DFT를 DFT로 표현하기 (Expressing the Inverse DFT in Terms of the DFT)

DFT의 유용한 성질 중 하나는 역 DFT를 (순방향) DFT로 쉽게 표현할 수 있다는 점이다. (예를 들어, 계산에서는 종종 한 변환 방향에 해당하는 고속 푸리에 변환만 구현한 다음 다른 변환 방향을 첫 번째 변환 방향에서 얻는 것이 편리하다.)

첫째, 모든 입력 중 하나를 제외하고 역순으로 하여 역 DFT를 계산할 수 있다.

:\mathcal{F}^{-1}(\{x_n\}) = \frac{1}{N}\mathcal{F}(\{x_{N - n}\})

(일반적으로, 아래첨자는 모듈로 ''N''으로 해석된다. 따라서, n = 0에 대해 x_{N-0} = x_0이다.)

둘째, 입력과 출력의 켤레 복소수를 취할 수도 있다.

:\mathcal{F}^{-1}(\mathbf{x}) = \frac{1}{N}\mathcal{F}\left(\mathbf{x}^*\right)^*

셋째, 데이터 값을 수정할 필요가 없다는 점에서 때때로 더 선호되는 이 켤레 복소수를 이용한 방법의 변형은 실수부와 허수부를 바꾸는 것을 포함한다 (이는 컴퓨터에서 포인터를 수정하는 것만으로 간단하게 수행할 수 있다). \operatorname{swap}(x_n)을 실수부와 허수부가 바뀐 x_n으로 정의한다. 즉, x_n = a + b i이면 \operatorname{swap}(x_n)은 b + a i이다. 마찬가지로, \operatorname{swap}(x_n)은 i x_n^*와 같다. 그러면

:\mathcal{F}^{-1}(\mathbf{x}) = \frac{1}{N}\operatorname{swap}(\mathcal{F}(\operatorname{swap}(\mathbf{x})))

즉, 역변환은 입력과 출력 모두에 대해 실수부와 허수부가 바뀐 순방향 변환과 정규화를 제외하고 동일하다.

3. 14. 고유치와 고유벡터 (Eigenvalues and Eigenvectors)

이산 푸리에 변환(DFT) 행렬의 고유값은 단순하고 잘 알려져 있지만, 고유벡터는 복잡하고 유일하지 않아 지속적인 연구 대상이다. 상당한 수론을 사용하여 명시적인 공식이 제시된다.[3]

길이가 N인 DFT에 대해 유니터리 형태의 행렬 U는 다음과 같이 정의된다.

:\mathbf{U}_{m,n} = \frac 1{\sqrt{N}}\omega_N^{(m-1)(n-1)} = \frac 1{\sqrt{N}}e^{-\frac{i 2\pi}N (m-1)(n-1)}.

이 행렬은 다음의 행렬 다항식 방정식을 만족한다.

:\mathbf{U}^4 = \mathbf{I}.

이는 U를 두 번 연산하면 원래 데이터가 역순으로 나오고, 네 번 연산하면 원래 데이터가 나오므로 항등 행렬이 된다는 역변환 특성에서 기인한다. 따라서 고유값 λ는 다음 방정식을 만족한다.

:\lambda^4 = 1.

결과적으로 U의 고유값은 4차 일의 근인 +1, −1, +i, 또는 −i이다.

이 N\times N 행렬은 네 개의 고유값만 가지므로, 각 고유값은 중복도를 갖는다. 중복도는 각 고유값에 해당하는 일차 독립인 고유벡터의 수를 의미한다. (N개의 독립적인 고유벡터가 존재하며, 유니터리 행렬은 결함 행렬이 아니다.)

중복도 문제는 McClellan과 Parks (1972)에 의해 해결되었으나, 이후 가우스가 해결한 문제와 동일하다는 것이 밝혀졌다 (Dickinson과 Steiglitz, 1982). 중복도는 N을 4로 나눈 나머지에 따라 달라지며, 아래 표와 같다.

유니터리 DFT 행렬 '''U'''의 고유값 λ의 중복도는 변환 크기 ''N''(정수 ''m''으로 표현)의 함수이다.
크기 Nλ = +1λ = −1λ = −iλ = +i
4mm + 1mmm − 1
4m + 1m + 1mmm
4m + 2m + 1m + 1mm
4m + 3m + 1m + 1m + 1m



달리 표현하면, U의 특성 다항식은 다음과 같다.

:\det (\lambda I - \mathbf{U})=

(\lambda-1)^{\left\lfloor \tfrac {N+4}{4}\right\rfloor}

(\lambda+1)^{\left\lfloor \tfrac {N+2}{4}\right\rfloor}

(\lambda+i)^{\left\lfloor \tfrac {N+1}{4}\right\rfloor}

(\lambda-i)^{\left\lfloor \tfrac {N-1}{4}\right\rfloor}.

일반적인 고유벡터에 대한 간단한 해석적 공식은 알려져 있지 않다. 또한, 같은 고유값을 갖는 고유벡터들의 임의의 선형 결합도 그 고유값에 대한 고유벡터가 되므로 고유벡터는 유일하지 않다. 여러 연구자들이 직교성과 "단순한" 형태 (예: McClellan과 Parks, 1972; Dickinson과 Steiglitz, 1982; Grünbaum, 1982; Atakishiyev와 Wolf, 1997; Candan 등, 2000; Hanna 등, 2004; Gurevich와 Hadani, 2008) 등 유용한 특성을 갖도록 선택된 고유벡터의 다양한 선택을 제안했다.

고유값 λ에 대한 DFT 고유벡터를 구성하는 한 가지 방법은 연산자의 선형 결합을 이용하는 것이다.[4][5][6]

\mathcal{P}_\lambda=\frac{1}{4}\left( \mathbf{I}+\lambda^{-1}\mathbf{U}+\lambda^{-2}\mathbf{U}^2+\lambda^{-3} \mathbf{U}^3\right)

임의의 벡터 v에 대해, \mathbf{u}(\lambda)=\mathcal{P}_{\lambda}\mathbf{v}는 다음을 만족한다.

\textbf{U}\mathbf{u}(\lambda)=\lambda \mathbf{u}(\lambda)

따라서 \mathbf{u}(\lambda)는 DFT 행렬 U의 고유벡터이다. 연산자 \mathcal{P}_{\lambda} 는 각 λ 값에 대해 직교하는 부분 공간에 벡터를 투영한다.[5] 즉, 두 고유벡터 \mathbf{u}(\lambda)=\mathcal{P}_{\lambda}\mathbf{v}와 \mathbf{u}'(\lambda')=\mathcal{P}_{\lambda'}\mathbf{v}'에 대해 다음이 성립한다.

\mathbf{u}^\dagger(\lambda) \mathbf{u}'(\lambda')= \delta_{\lambda\lambda'}\mathbf{u}^\dagger(\lambda) \mathbf{v}'

그러나 투영 연산자 방법은 일반적으로 하나의 부분 공간 내에서 직교하는 고유벡터를 생성하지 않는다.[6] 연산자 \mathcal{P}_{\lambda}는 열이 U의 고유벡터인 행렬로 볼 수 있지만, 직교하지는 않는다. N_{\lambda}차원 공간(여기서 N_{\lambda}는 고유값 λ의 중복도)을 펼치는 벡터 집합 \{\mathbf{v}_n\}_{n=1,\dots,N_{\lambda}}를 선택하여 고유값 λ에 대한 고유벡터 집합 \{\mathbf{u}_n(\lambda)=\mathcal{P}_{\lambda}\mathbf{v}_n\}_{n=1,\dots,N_{\lambda}}를 생성하면, \mathbf{u}_n(\lambda)의 상호 직교성은 보장되지 않는다. 그람-슈미트 과정과 같은 직교화 알고리즘을 \{\mathbf{u}_n(\lambda)\}_{n=1,\dots,N_{\lambda}} 집합에 추가로 적용하여 직교 집합을 얻을 수 있다.[7]

DFT 고유벡터를 얻는 간단한 방법은 연속 푸리에 변환의 고유함수를 이산화하는 것이다. 가장 유명한 것은 가우스 함수이다. 함수의 주기적 합은 주파수 스펙트럼을 이산화하고, 이산화는 스펙트럼의 주기적 합을 의미하므로, 이산화되고 주기적으로 합산된 가우스 함수는 이산 변환의 고유벡터를 생성한다.


  • F(m) = \sum_{k\in\mathbb{Z}} \exp\left(-\frac{\pi\cdot(m+N\cdot k)^2}{N}\right).


급수에 대한 닫힌 형식 표현은 야코비 세타 함수로 표현할 수 있다.

  • F(m) = \frac1{\sqrt{N}}\vartheta_3\left(\frac{\pi m}N, \exp\left(-\frac{\pi}N \right)\right).


특수 DFT 주기 N에 대한 몇 가지 간단한 닫힌 형식 해석적 고유벡터도 발견되었다 (Kong, 2008 및 Casper-Yakimov, 2024).

DFT 주기 N = 2L + 1 = 4K + 1 (K는 정수)인 경우, 다음은 DFT의 고유벡터이다.

  • F(m) = \prod_{s=K+1}^L \left[\cos\left(\frac{2\pi}{N}m\right) - \cos\left(\frac{2\pi}{N}s\right)\right]


DFT 주기 N = 2L = 4K (K는 정수)인 경우, 다음은 DFT의 고유벡터이다.

  • F(m) = \sin\left(\frac{2\pi}{N}m\right) \prod_{s=K+1}^{L-1}\left[\cos\left(\frac{2\pi}{N}m\right)- \cos\left(\frac{2\pi}{N}s\right)\right]
  • F(m) = \cos\left(\frac{\pi}{N}m\right)\prod_{s=K+1}^{3K-1} \sin\left(\frac{\pi(s-m)}{N}\right)


DFT 주기 N = 4K - 1 (K는 정수)인 경우, 다음은 DFT의 고유벡터이다.

  • F(m) = \sin\left(\frac{2\pi}{N}m\right)\prod_{s=K+1}^{3K-2} \sin\left(\frac{\pi(s-m)}{N}\right)
  • F(m) = \left(\cos\left(\frac{2\pi}{N}m\right)-\cos\left(\frac{2\pi}{N}K\right)\pm\sin\left(\frac{2\pi}{N}K\right)\right)\prod_{s=K+1}^{3K-2} \sin\left(\frac{\pi(s-m)}{N}\right)


DFT 행렬의 고유벡터 선택은 분수 푸리에 변환의 이산적 유사체를 정의하는 데 중요해졌다. DFT 행렬을 분수 거듭제곱으로 취하기 위해 고유값을 지수화할 수 있다(예: Rubio와 Santhanam, 2005). 연속 푸리에 변환의 경우, 자연스러운 직교 고유함수는 에르미트 함수이므로, 크라프추크 다항식(Atakishiyev와 Wolf, 1997)과 같이 이러한 함수의 다양한 이산적 유사체가 DFT의 고유벡터로 사용되었다. 그러나 분수 이산 푸리에 변환을 정의하기 위한 "최적의" 고유벡터 선택은 여전히 해결되지 않은 문제이다.

3. 15. 불확정성 원리 (Uncertainty Principles)

하이젠베르크의 불확정성 원리는 연속 함수 P(x)와 Q(k)에 대해 다음과 같이 표현된다.[15]

:D_0(X)D_0(x)\ge\frac{1}{16\pi^2}

여기서 D_0(X)와 D_0(x)는 각각 |X|^2와 |x|^2의 분산이며, 적절히 정규화된 가우스 분포의 경우 등식이 성립한다. 그러나 이산 푸리에 변환(DFT)에서는 분산이 이동 불변이 아니기 때문에 이와 유사한 불확정성 원리는 유용하지 않다. 그럼에도 불구하고, Massar와 Spindel에 의해 의미 있는 불확정성 원리가 소개되었다.[15]

Hirschman 엔트로피 불확정성은 DFT에서 유용한 유추를 가진다.[16] Hirschman 불확정성 원리는 두 확률 함수의 섀넌 엔트로피로 표현된다. 이산적인 경우, 섀넌 엔트로피는 다음과 같이 정의된다.

:H(X)=-\sum_{n=0}^{N-1} P_n\ln P_n

:H(x)=-\sum_{m=0}^{N-1} Q_m\ln Q_m ,

이에 따라 엔트로피 불확정성 원리는 다음과 같다.[16]

:H(X)+H(x) \ge \ln(N) .

위 식에서 등식은 P_n이 주기 A를 갖는 적절히 정규화된 크로네커 콤의 병진과 변조와 같을 때 성립한다. 여기서 A는 N의 정확한 정수 약수이다. 이때 확률 질량 함수 Q_m는 주기 B=N/A를 갖는 적절히 병진된 크로네커 콤에 비례한다.[16]

시간 및 주파수 시퀀스 x_0,x_1,\ldots,x_{N-1}와 X_0,X_1,\ldots,X_{N-1}의 0이 아닌 원소의 개수를 각각 \left\|x\right\|_0와 \left\|X\right\|_0라 할 때, 신호의 스파스성(sparse)을 이용한 결정적 불확정성 원리는 다음과 같다.[17]

:N \leq \left\|x\right\|_0 \cdot \left\|X\right\|_0.

산술 기하 평균의 부등식에 따라, 2\sqrt{N} \leq \left\|x\right\|_0 + \left\|X\right\|_0도 성립한다. 두 불확정성 원리는 특별히 선택된 "픽켓 펜스"(picket-fence) 시퀀스(이산 임펄스 열)에 대해 정확하며, 신호 복구에 사용된다.[17]

3. 16. 실수 및 순수 허수 신호의 DFT (DFT of Real and Purely Imaginary Signals)


  • 입력 신호 \(x_0, \ldots, x_{N-1}\)가 실수일 경우(실제 응용에서 흔히 그러함), 이산 푸리에 변환(DFT) \(X_0, \ldots, X_{N-1}\)는 짝대칭을 갖는다.


:x_n \in \mathbb{R} \quad \forall n \in \{0,\ldots,N-1 \} \implies X_k = X_{-k \mod N}^* \quad \forall k \in \{0,\ldots,N-1 \}, 여기서 \(X^*\)는 켤레 복소수를 나타낸다.

따라서, 짝수 \(N\)에 대해 \(X_0\)와 \(X_{N/2}\)는 실수값을 가지며, 나머지 DFT는 단지 \(N/2-1\)개의 복소수로 완전히 결정된다.

  • 입력 신호 \(x_0, \ldots, x_{N-1}\)가 순허수일 경우, DFT \(X_0, \ldots, X_{N-1}\)는 홀대칭을 갖는다.


:x_n \in i \mathbb{R} \quad \forall n \in \{0,\ldots,N-1 \} \implies X_k = -X_{-k \mod N}^* \quad \forall k \in \{0,\ldots,N-1 \}, 여기서 \(X^*\)는 켤레 복소수를 나타낸다.

4. 일반화

일반화된 DFT (Generalized DFT)는 시간 및/또는 주파수 영역에서 실수 값의 이동량 ''a''와 ''b''만큼 변환 샘플링을 이동시키는 것을 말하며, 때때로 이동 DFT (shifted DFT) 또는 오프셋 DFT (offset DFT)라고도 불린다. 일반화된 DFT는 다음과 같이 표현된다.

:X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{i 2 \pi}{N} (k+b) (n+a)} \quad \quad k = 0, \dots, N-1.

대부분의 경우, 샘플의 절반(1/2)만큼의 이동이 사용된다. 일반 DFT는 시간 및 주파수 영역 모두에서 주기적인 신호에 해당하지만, a=1/2는 주파수 영역에서 반주기적인 신호(X_{k+N} = - X_k)를 생성하며, b=1/2의 경우에는 그 반대이다. a = b = 1/2인 특수한 경우는 ''홀수 시간 홀수 주파수'' 이산 푸리에 변환(O2 DFT)으로 알려져 있다. 이러한 이동 변환은 대칭 데이터에 가장 많이 사용되며, 서로 다른 경계 대칭을 나타내고, 실수 대칭 데이터의 경우에는 코사인 변환과 사인 변환의 여러 형태에 해당한다.

a=b=-(N-1)/2인 경우는 '''중심화된 DFT'''(CDFT)라고 하며, ''N''이 4의 배수일 때, 그 고유값 네 개가 모두 같은 중복도를 갖는다는 유용한 특성을 가지고 있다.[18]

GDFT라는 용어는 DFT의 비선형 위상 확장에도 사용된다. GDFT는 원래의 선형 위상 함수에 적절히 설계된 위상 성형 함수(일반적으로 비선형)를 추가하여 기존 DFT의 시간 및 주파수 영역 특성(예: 자동/상호 상관)을 개선하는 프레임워크이다.[19]

시간 및 공간에 포함된 이산 변환.


== 다차원 DFT ==

일반 DFT가 1차원 배열 x_n을 변환하는 것과 달리, 다차원 DFT는 ''d''개의 이산 변수 n_\ell = 0, 1, \dots, N_\ell-1 (\ell은 1, 2, \dots, d에 있음)의 함수인 다차원 배열 x_{n_1, n_2, \dots, n_d}을 변환하며, 다음과 같이 정의된다.

:X_{k_1, k_2, \dots, k_d} = \sum_{n_1=0}^{N_1-1} \left(\omega_{N_1}^{~k_1 n_1} \sum_{n_2=0}^{N_2-1} \left( \omega_{N_2}^{~k_2 n_2} \cdots \sum_{n_d=0}^{N_d-1} \omega_{N_d}^{~k_d n_d}\cdot x_{n_1, n_2, \dots, n_d} \right) \right) ,

여기서 \omega_{N_\ell} = \exp(-i 2\pi/N_\ell)이고, ''d''개의 출력 색인은 k_\ell = 0, 1, \dots, N_\ell-1에서 실행된다. 벡터 표기법을 사용하면 더 간결하게 표현할 수 있다.

:X_\mathbf{k} = \sum_{\mathbf{n}=\mathbf{0}}^{\mathbf{N}-1} e^{-i 2\pi \mathbf{k} \cdot (\mathbf{n} / \mathbf{N})} x_\mathbf{n} \, ,

여기서 나눗셈 \mathbf{n} / \mathbf{N}는 요소별로 수행되고, 합은 위의 중첩 합의 집합을 나타낸다.

다차원 DFT의 역변환은 다음과 같다.

:x_\mathbf{n} = \frac{1}{\prod_{\ell=1}^d N_\ell} \sum_{\mathbf{k}=\mathbf{0}}^{\mathbf{N}-1} e^{i 2\pi \mathbf{n} \cdot (\mathbf{k} / \mathbf{N})} X_\mathbf{k} \, .

다차원 DFT는 입력을 평면파 또는 다차원 정현파의 중첩으로 표현한다. 공간에서의 진동 방향은 \mathbf{k} / \mathbf{N}이고, 진폭은 X_\mathbf{k}이다. 이 분해는 디지털 영상 처리(2차원)부터 편미분 방정식 해결에 이르기까지 모든 것에 매우 중요하다.

다차원 DFT는 각 차원을 따라 1차원 DFT의 연속적인 합성을 통해 계산할 수 있다. (''행-열'' 알고리즘)

실수로 구성된 입력 데이터 x_{n_1, n_2, \dots, n_d}의 경우, DFT 출력은 복소수 공액 대칭을 갖는다.

:X_{k_1, k_2, \dots, k_d} = X_{N_1 - k_1, N_2 - k_2, \dots, N_d - k_d}^* ,

여기서 별표(*)는 복소 공액을 나타내며, \ell번째 첨자는 N_\ell을 법(modulo)으로 해석된다.

DFT는 유한 순환군의 복소수 값 표현으로 해석될 수 있다. n개의 복소수로 이루어진 수열은 n차원 복소 공간 \mathbb{C}^n의 원소 또는 함수 f, 즉 \mathbb{Z}_n \mapsto \mathbb{C}로 생각할 수 있다. f는 유한 순환군의 류 함수이며, 따라서 이 군의 기약 지표(이는 1의 근이다)의 선형 결합으로 표현될 수 있다.

이 관점에서 DFT는 일반적으로 표현론으로, 또는 더 좁게는 유한군의 표현론으로 일반화할 수 있다.

목표(복소수가 아닌 다른 체에서 값을 취함) 또는 정의역(유한 순환군이 아닌 다른 군)을 변경하여 DFT를 일반화할 수 있다.

DFT의 많은 성질들은 e^{-\frac{i 2 \pi}{N}}이 일의미 원근(때때로 \omega_N 또는 W_N으로 표기)이라는 사실에만 의존한다. 이러한 이유로, 이산 푸리에 변환은 복소수가 아닌 체에서 일의미 원근을 사용하여 정의할 수 있으며, 이러한 일반화는 유한체의 경우 일반적으로 ''수론적 변환''(NTT)이라고 한다.

표준 DFT는 함수 {0, 1, ..., ''N'' − 1} → '''C'''로 볼 수 있다. 다차원 DFT는 함수

: \{0, 1, \ldots, N_1-1\} \times \cdots \times \{0, 1, \ldots, N_d-1\} \to \mathbb{C}.

로 볼 수 있다. 이것은 임의의 유한군에서의 푸리에 변환으로의 일반화를 시사한다. 이 틀에서 표준 DFT는 순환군에서의 푸리에 변환으로, 다차원 DFT는 순환군의 직합에서의 푸리에 변환으로 간주된다.

또한, 푸리에 변환은 군의 부분군에 대해 적용될 수 있다.

5. 응용

이산 푸리에 변환(DFT)은 고속 푸리에 변환(FFT) 알고리즘 덕분에 다양한 분야에서 널리 활용된다.[1] 주요 응용 분야는 다음과 같다:


  • 스펙트럼 분석: 신호의 주파수 성분을 분석하여 어떤 주파수가 얼마나 포함되어 있는지 파악한다. 앨리어싱 및 스펙트럼 누출과 같은 왜곡을 최소화하기 위해 적절한 표본화 속도와 부분 수열 길이를 선택해야 한다.[1]
  • 데이터 압축: JPEG와 같은 이미지 압축 기술은 이산 코사인 변환(DCT)을 사용하여 이미지 정보를 효율적으로 압축한다.[1][2]
  • 편미분 방정식: 편미분 방정식을 풀 때 DFT를 푸리에 급수의 근사값으로 사용하여 계산을 단순화하는 스펙트럼 방법이 있다.[1]
  • 다항식 곱셈 및 큰 정수의 곱셈: 쇼엔하겐-슈트라센 알고리즘과 같이 DFT를 사용하여 다항식 곱셈 및 큰 정수 곱셈을 빠르게 수행할 수 있다.[1]
  • 합성곱: 컨벌루션 정리를 이용하여 두 신호의 컨벌루션을 효율적으로 계산할 수 있다.[13][14]

5. 1. 스펙트럼 분석 (Spectral Analysis)

이산 푸리에 변환(DFT)은 신호의 주파수 성분을 분석하는 데 사용된다.[1] Spectral Analysis영어는 신호에 어떤 주파수 성분이 얼마나 포함되어 있는지 파악하는 기법이다.[1]

\{x_n\} 수열은 일반적으로 신호 x(t)의 균일한 간격으로 구성된 유한한 시간 표본 집합을 나타낸다. 여기서 t는 시간을 의미한다. 연속 시간에서 표본(이산 시간)으로 변환하면 x(t)의 푸리에 변환이 이산 시간 푸리에 변환(DTFT)으로 바뀌는데, 이는 앨리어싱이라는 왜곡을 일으킨다. 이러한 왜곡을 최소화하려면 적절한 표본화 속도(나이퀴스트 레이트 참조)를 선택해야 한다.[1]

마찬가지로, 매우 긴(또는 무한한) 수열을 관리 가능한 크기로 변환하면 누출이라는 왜곡이 발생하며, 이는 DTFT에서 세부 정보 손실(해상도 저하)로 나타난다. 적절한 부분 수열 길이를 선택하면 이 효과를 최소화할 수 있다.[1]

원하는 주파수 해상도를 달성하는 데 필요한 것보다 사용 가능한 데이터(및 처리 시간)가 더 많은 경우, 여러 개의 DFT를 수행하여 스펙트로그램을 생성하는 것이 일반적인 방법이다. 원하는 결과가 전력 스펙트럼이고 데이터에 잡음이나 임의성이 있는 경우, 여러 DFT의 크기 구성 요소를 평균화하면 스펙트럼의 분산을 줄일 수 있다. 이를 주기 도표라고도 한다.[1] 이러한 기법의 예로는 웰치 방법과 바틀릿 방법이 있으며, 잡음이 있는 신호의 전력 스펙트럼을 추정하는 것을 스펙트럼 추정이라고 한다.[1]

DFT 자체는 연속 주파수 영역의 함수인 DTFT의 이산 샘플링이기 때문에 최종적인 왜곡(또는 착시)이 발생한다. 이는 DFT의 해상도를 높여 완화할 수 있다.[1] 이 절차는 때때로 제로 패딩이라고 불리며, 고속 푸리에 변환(FFT) 알고리즘과 함께 사용되는 특정 구현이다. 제로 값을 갖는 "샘플"을 사용하여 곱셈과 덧셈을 수행하는 비효율성은 FFT의 고유한 효율성에 의해 상쇄된다.[1] 누출은 DTFT의 고유한 해상도에 한계를 주므로, 미세한 DFT로 얻을 수 있는 이점에는 실질적인 한계가 있다.[1]

오디오 신호의 스펙트럼 분석은 다음과 같은 단계를 거친다.[1]

1. 오디오 신호 녹음 및 사전 처리: 말하는 암호, 음악, 소리 등 오디오 신호를 녹음한다. 녹음된 오디오 신호는 x[n]으로 표시하며, 여기서 n은 이산 시간 지수를 나타낸다. 스펙트럼 분석의 정확성을 높이기 위해 필터링 기법을 사용하여 원치 않는 잡음을 줄인다.[1]

2. 원래 시간 영역 신호 플롯: 잡음 감소 후, 오디오 신호를 시간 영역에서 플롯하여 시간에 따른 특성을 시각화한다. 이를 통해 시간의 함수로서 신호의 진폭 변화를 이해하고, 신호 동작에 대한 초기 통찰력을 얻는다.[1]

3. 시간 영역에서 주파수 영역으로 신호 변환: 이산 푸리에 변환(DFT)을 사용하여 오디오 신호를 시간 영역에서 주파수 영역으로 변환한다. DFT는 다음과 같이 정의된다.[1]

:X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j \frac{2 \pi}{N}kn}

:여기서 N은 총 샘플 수, k는 주파수 지수, X[k]는 신호의 복소수 값 주파수 스펙트럼이다. DFT를 사용하면 신호를 구성 주파수 성분으로 분해하여 어떤 주파수가 존재하고 각각의 크기가 무엇인지 알 수 있다.[1]

4. 크기 스펙트럼 플롯: 주파수 영역 표현 X[k]의 크기를 플롯하여 스펙트럼 내용을 분석한다. 크기 스펙트럼은 신호의 에너지가 다른 주파수에 걸쳐 어떻게 분포되어 있는지 보여주며, 두드러진 주파수 성분을 식별하는 데 유용하다. 이는 다음과 같이 계산된다.[1]

:|X[k]| = \sqrt{\text{Re}(X[k])^2 + \text{Im}(X[k])^2}

이산 시간 오디오 신호의 주파수 성분을 식별하기 위해 DFT를 사용하여 주파수 영역에서 분석한다. 예를 들어 다음과 같은 간단한 이산 시간 오디오 신호를 생각해보자.[1]

:x[n] = \{ 1, 0.5, -0.5, -1 \}

여기서 n은 신호의 이산 시간 샘플을 나타낸다. 주어진 시간 영역 신호는 다음과 같다.[1]

:x[0] = 1, \quad x[1] = 0.5, \quad x[2] = -0.5, \quad x[3] = -1



디지털 영상처리에서는 2차원 변환이 영상의 주파수 성분을 분석하는 데 사용된다. 2차원 DFT는 다음과 같이 정의된다.[1]

:F(u, v) = \sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) e^{- 2 \pi i \left(\frac{u x}{M} +\frac{v y}{N} \right) }

그리고 역변환은 다음과 같다.[1]

:f(x, y) = \frac{1}{M N} \sum_{u=0}^{M-1} \sum_{v=0}^{N-1} F(u, v) e^{2 \pi i \left(\frac{u x}{M} +\frac{v y}{N} \right) }

여기서,[1]

  • f(x, y)는 2차원 신호(예: 영상)이며, f의 x열 y행 성분이다.
  • F(u, v)는 f(x, y)의 2차원 주파수 스펙트럼이다. 여기서 u는 x성분의 주파수, v는 y성분의 주파수이다.


2차원 DFT는 행렬을 이용하여 간단하게 표현할 수 있다.[1]

:F = W f^T W

여기서,[1]

  • F = \begin{bmatrix}

F(0, 0) & F(1, 0) & \ldots & F(M-1, 0) \\

F(0, 1) & F(1, 1) & \ldots & F(M-1, 1) \\

\vdots & \vdots & \ddots & \vdots \\

F(0, N-1) & F(1, N-1) & \ldots & F(M-1, N-1)

\end{bmatrix}

  • W = \begin{bmatrix}

\omega_n^{0 \cdot 0} & \omega_n^{0 \cdot 1} & \ldots & \omega_n^{0 \cdot (N-1)} \\

\omega_n^{1 \cdot 0} & \omega_n^{1 \cdot 1} & \ldots & \omega_n^{1 \cdot (N-1)} \\

\vdots & \vdots & \ddots & \vdots \\

\omega_n^{(N-1) \cdot 0} & \omega_n^{(N-1) \cdot 1} & \ldots & \omega_n^{(N-1) \cdot (N-1)} \\

\end{bmatrix} (유니터리 행렬)

  • f = \begin{bmatrix}

f(0, 0) & f(1, 0) & \ldots & f(M-1, 0) \\

f(0, 1) & f(1, 1) & \ldots & f(M-1, 1) \\

\vdots & \vdots & \ddots & \vdots \\

f(0, N-1) & f(1, N-1) & \ldots & f(M-1, N-1)

\end{bmatrix}

신호 x(t)를 분석할 때, t는 시간이며 [0, T] 범위를 갖는다고 가정한다. 예를 들어, 음성 신호의 경우 x(t)는 시간 t에서의 공기의 압력을 나타낸다.[1]

이 신호는 N개의 등간격 점에서 표본화되어 x0, x1, x2, ..., xN−1의 실수열이 된다. 표본화 간격을 Δx ( = T/ N )라고 하면 xk = x(k Δx)이다. 이것의 DFT인 f0, ..., fN−1은 FFT로 계산할 수 있다. 그러나 표본화 정리에 따라 이것의 절반(N이 짝수라고 하면, fN/2 + 1, ..., fN−1)은 중복되므로 버리거나 무시한다.[1]

DFT에서 얻어지는 |fk|/ N은 신호의 주파수 j/ T 성분의 진폭의 절반 값이며, 진폭 스펙트럼이라고 한다. 또한, 이 편각인 arg(fj)는 이 주파수 성분의 위상을 나타낸다. |fk|2는 파워 스펙트럼이라고 불리며, 이 주파수 성분의 에너지를 나타낸다.[1]

fk는 신호 x(t)의 푸리에 급수의 계수에 해당하는 것으로 생각할 수 있다. 따라서, 무한히 넓은 푸리에 급수 계산을 유한한 샘플 점에 대한 DFT를 사용하여 근사하는 형태가 된다. 연속 신호의 경우 이것을 스펙트럼 추정(spectral estimation)이라고 하며, 다양한 추정 방법이 있다. 예를 들어, DFT가 유한 샘플 점을 다루는 데 기인하는 스펙트럼 누출의 폐해를 다소 완화하기 위해 창 함수(창)을 사용하는 것이 일반적이다.[1]

5. 2. 광학, 회절, 단층 촬영 (Optics, Diffraction, and Tomography)

이산 푸리에 변환은 빛, 전자 및 기타 탐침이 광학 시스템을 통과하고 2차원 및 3차원 물체에서 산란하는 방식을 모델링할 때 공간 주파수와 함께 널리 사용된다. 3차원 물체의 이중(직접/상호) 벡터 공간은 투명한 물체 그림자를 통해(푸리에 슬라이스 정리(Fourier slice theorem)를 통해) 구성되는 3차원 상호 격자를 추가로 제공하며, 이는 현대 의학 등 광범위한 응용 분야에서 3차원 물체의 단층 촬영 재구성을 가능하게 한다.

5. 3. 필터 뱅크 (Filter Bank)

FFT 필터 뱅크 및 DTFT 샘플링를 참조하십시오.

5. 4. 데이터 압축 (Data Compression)

디지털 신호 처리 분야는 주파수 영역에서의 연산, 즉 푸리에 변환에 크게 의존한다. 여러 손실 압축 이미지 및 음향 압축 방법은 이산 푸리에 변환을 사용한다.[1] 신호는 짧은 세그먼트로 나뉘고 각각 변환된 다음, 눈에 띄지 않는다고 가정되는 고주파의 푸리에 계수가 버려진다. 압축 해제 프로그램은 이 감소된 수의 푸리에 계수를 기반으로 역변환을 계산한다.[1]

신호 처리 분야에서는 주파수 영역(푸리에 변환)에서 처리하는 경우가 적지 않다. 예를 들어, 영상의 비가역 압축이나 음성 압축 기술 등에서는 이산 푸리에 변환의 개념이 사용된다. 신호에 대해 DFT(구현 상으로는 FFT)를 수행하고, 사람이 인지하기 어려운 주파수 성분의 정보를 제거함으로써 순 정보량을 감소(압축)시킨다. 가장 단순한 방법으로는 IDFT 시에 그 제거한 주파수 정보(푸리에 계수)를 0으로 함으로써, 일반적인 IDFT를 구현한다.[2]

JPEG는 구현의 단순화(계산의 효율화)를 위해 실수 연산만으로 가능한 이산 코사인 변환을 사용하여 2차원 정보를 압축한 예이다.[1][2] 그러나 일부 최근의 압축 알고리즘은 웨이블릿 변환을 사용하는데, 이는 데이터를 세그먼트로 잘라 각 세그먼트를 변환하는 것보다 시간 및 주파수 영역 간에 더 균일한 절충안을 제공한다. JPEG 2000의 경우, 이는 원본 JPEG로 이미지를 고압축할 때 나타나는 잘못된 이미지 특징을 방지한다.[1]

5. 5. 편미분 방정식 (Partial Differential Equations)

이산 푸리에 변환은 편미분 방정식을 풀 때 종종 사용되는데, 이때 DFT는 푸리에 급수의 근사값으로 사용된다. 이 방법의 장점은 신호를 미분의 고유함수인 복소 지수 함수 e^{inx}로 전개한다는 것이다. {\text{d} \big( e^{inx} \big) }/\text{d}x = in e^{inx}이므로, 푸리에 표현에서 미분은 간단하게 in을 곱하는 것으로 계산된다. 하지만, 에일리어싱 때문에 n의 선택이 고유하지 않다. 방법이 수렴하려면 삼각 보간 섹션과 유사한 선택을 사용해야 한다. 상수 계수를 갖는 선형 미분 방정식은 쉽게 풀 수 있는 대수 방정식으로 변환된다. 그런 다음 역 DFT를 사용하여 결과를 일반 공간 표현으로 다시 변환한다. 이러한 접근 방식을 스펙트럼 방법이라고 한다.[1]

5. 6. 다항식 곱셈 (Polynomial Multiplication)

다항식 ''c''(''x'') = ''a''(''x'') · ''b''(''x'')를 계산한다고 가정하자. ''c''의 계수에 대한 일반적인 곱셈 표현은 선형(비순환) 합성곱을 포함하며, 여기서 인덱스는 순환하지 않는다. 상수항을 먼저 갖는 ''a''(''x'')와 ''b''(''x'')의 계수 벡터를 취한 다음, 결과 계수 벡터 '''a'''와 '''b'''의 차원이 되도록 0을 추가하여 이를 순환 합성곱으로 다시 쓸 수 있다. 그러면,

:'''c''' = '''a''' * '''b'''

여기서 '''c'''는 ''c''(''x'')의 계수 벡터이고, 합성곱 연산자 *는 다음과 같이 정의된다.

:''c''''n'' = ∑''m''=0''d''-1 ''a''''m''''b''''n''-''m'' mod ''d'', ''n''=0,1,...,''d''-1

하지만 이산 푸리에 변환(DFT) 하에서 합성곱은 곱셈이 된다.

:ℱ('''c''') = ℱ('''a''')ℱ('''b''')

여기서 벡터 곱은 원소별로 계산된다. 따라서 곱셈 다항식 ''c''(''x'')의 계수는 계수 벡터의 0, ..., deg(''a''(''x'')) + deg(''b''(''x'')) 항이다.

:'''c''' = ℱ-1(ℱ('''a''')ℱ('''b''')).

고속 푸리에 변환을 사용하면 결과 알고리즘은 ''O''(''N'' log ''N'')의 산술 연산을 수행한다. 단순성과 속도 때문에, 합성수 크기로 제한되는 쿨리-터키 FFT 알고리즘이 변환 연산에 자주 선택된다. 이 경우, ''d''는 입력 다항식 차수의 합보다 큰 가장 작은 정수로 선택되어야 하며, 작은 소수(예: FFT 구현에 따라 2, 3, 5)로 인수분해 가능해야 한다.

큰 수나 다항식의 곱셈 알고리즘에서 DFT를 사용하는 고속 알고리즘으로 1971년에 쇼엔하겐-슈트라센 알고리즘이 발견되었다. 숫자나 다항식의 계수열을 컨볼루션 연산의 대상 벡터로 간주한다. 그러면 각 벡터의 DFT를 생성하고, 그 결과끼리 벡터를 요소별로 곱한 새로운 벡터를 만들어 역변환함으로써 곱셈 계산 결과를 얻을 수 있다(즉, 컨볼루션 정리를 사용한다). 2007년에는 이론적으로 쇼엔하겐-슈트라센 알고리즘보다 고속인 알고리즘이 발견되었다.

5. 7. 큰 정수의 곱셈 (Multiplication of Large Integers)

매우 큰 정수의 곱셈을 위한 가장 빠른 알고리즘들은 위에서 설명한 다항식 곱셈 방법을 사용한다. 정수는 특정 기수에서 평가된 다항식의 값으로 취급될 수 있으며, 다항식의 계수는 그 기수에서의 자릿수에 해당한다(예: 123 = 1 · 102 + 2 · 101 + 3 · 100). 다항식 곱셈 후, 비교적 낮은 복잡도의 자리올림 전파 단계가 곱셈을 완료한다.

쇼엔하게-슈트라센 알고리즘은 큰 수나 다항식의 곱셈 알고리즘에서 DFT를 사용하는 고속 알고리즘으로 1971년에 발견되었다. 숫자나 다항식의 계수열을 컨볼루션 연산의 대상 벡터로 간주한다. 각 벡터의 DFT를 생성하고, 그 결과끼리 벡터를 요소별로 곱한 새로운 벡터를 만들어 역변환함으로써 곱셈 계산 결과를 얻을 수 있다(즉, 컨볼루션 정리를 사용한다). 2007년에는 이론적으로 쇼엔하게-슈트라센 알고리즘보다 고속인 알고리즘이 발견되었다.

5. 8. 합성곱 (Convolution)

이산 시간 푸리에 변환(DTFT)에 대한 컨벌루션 정리는 두 수열의 컨벌루션을 각 변환의 곱의 역변환으로 얻을 수 있음을 나타낸다. 하나의 수열이 N-주기적일 때, y_{_N}로 표시되는 중요한 단순화가 발생한다. \scriptstyle \text{DTFT} \displaystyle \{y_{_N}\}는 이산 주파수에서만 0이 아니기 때문이다. 따라서 연속 함수 \scriptstyle \text{DTFT} \displaystyle \{x\}와의 곱도 마찬가지이다. 이는 역변환을 상당히 단순화한다.

:x * y_{_N}\ =\ \scriptstyle{\rm DTFT}^{-1} \displaystyle \left[\scriptstyle{\rm DTFT} \displaystyle \{x\}\cdot \scriptstyle{\rm DTFT} \displaystyle \{y_{_N}\}\right]\ =\ \scriptstyle{\rm DFT}^{-1} \displaystyle \left[\scriptstyle{\rm DFT} \displaystyle \{x_{_N}\}\cdot \scriptstyle{\rm DFT} \displaystyle \{y_{_N}\}\right],

여기서 x_{_N}는 x 수열의 주기적 합이다.

일반적으로 DFT와 역 DFT 합산은 영역 [0,N-1]에서 이루어진다. 이러한 DFT를 X와 Y로 정의하면 결과는 다음과 같다.

:

(x * y_{_N})_n \triangleq \sum_{\ell=-\infty}^{\infty}x_\ell \cdot (y_{_N})_{n-\ell} = \underbrace{\mathcal{F}^{-1}}_{\rm DFT^{-1}} \left \{ X\cdot Y \right \}_n.

실제로 x 수열은 일반적으로 길이가 ''N'' 이하이며, y_{_N}는 N 길이의 y 수열의 주기적 확장이며, 이는 ''원형 함수''로도 표현될 수 있다.

:(y_{_N})_n = \sum_{p=-\infty}^\infty y_{(n-pN)} = y_{(n\operatorname{mod}N)}, \quad n\in\mathbb{Z}.

그러면 컨벌루션은 다음과 같이 쓸 수 있다.

:

\mathcal{F}^{-1} \left \{ X\cdot Y \right \}_n = \sum_{\ell=0}^{N-1}x_\ell \cdot y_{_{(n-\ell)\operatorname{mod}N}}



이는 x와 y의 ''원형'' 컨벌루션으로 해석된다.[13][14] 이는 선형 컨벌루션을 효율적으로 계산하는 데 자주 사용된다.

마찬가지로, x와 y_{_N}의 상호상관은 다음과 같이 주어진다.

:(x \star y_{_N})_n \triangleq \sum_{\ell=-\infty}^{\infty} x_\ell^* \cdot (y_{_N})_{n+\ell} = \mathcal{F}^{-1} \left \{ X^* \cdot Y \right \}_n.

데이터가 컨벌루션 연산을 통해 넓은 지지 영역을 갖는 함수와 합성곱될 때, 예를 들어 큰 샘플링 비율로 다운샘플링하는 경우, 컨벌루션 정리와 FFT 알고리즘 덕분에 데이터를 변환하고, 필터의 변환 결과와 점별 곱셈을 한 후 역변환하는 것이 더 빠를 수 있다.

두 함수 f(x)와 g(x)의 컨벌루션(convolution) f*g는 다음과 같이 정의된다.

:(f*g)(x) = \sum_{n=0}^{N-1} f(n) g(x-n)

단, f와 g는 다음과 같은 주기성을 갖는다고 가정한다.

:\begin{align}

f(x+N)&=f(x) \\

g(x+N)&=g(x)

\end{align}

주기 함수의 컨벌루션을 이산 푸리에 변환(DFT)하면 각각의 이산 푸리에 변환의 곱이 된다(컨벌루션 정리). 즉,

:\mathcal{F}_N(f*g)=\mathcal{F}_N(f)\mathcal{F}_N(g)

컨벌루션 합을 직접 정의식을 사용하여 계산하면 O(N²)의 계산량이 소요된다. 하지만, 위 식에 따라 일단 DFT를 한 후 곱셈을 하고, IDFT로 되돌리는 방법도 있다. DFT의 고속 알고리즘인 FFT를 통해 이렇게 계산하면 O(N log N)의 계산량으로 처리할 수 있다.

6. 대안

여러 응용 분야에서 이산 푸리에 변환(DFT)의 다양한 대안이 있으며, 그중에서도 두드러지는 것은 웨이블릿이다. DFT와 유사한 변환으로는 이산 웨이블릿 변환(DWT)이 있다. 시간-주파수 분석 관점에서 볼 때, 푸리에 변환의 주요 한계는 '주파수' 정보만 포함하고 '위치' 정보는 포함하지 않아 과도 현상을 나타내는 데 어려움이 있다는 것이다. 웨이블릿은 위치와 주파수를 모두 가지고 있으므로 주파수를 나타내는 데는 더 어려움이 있더라도 위치를 더 잘 나타낼 수 있다.

참조

[1] 웹사이트 Discrete Fourier Transform - Frequencies https://www.statlect[...] 2021
[2] 서적 Music through Fourier Space https://link.springe[...] Springer 2016
[3] 학술지 On the eigenvectors of Schur's matrix https://dx.doi.org/1[...] 1980
[4] 학술지 Eigenvectors and eigenvalues of 1-D and nD DFT matrices 2001
[5] 학술지 On the eigenstructure of DFT matrices 2011
[6] 학술지 Generalized commuting matrices and their eigenvectors for DFTs, offset DFTs, and other periodic operations 2008
[7] 학술지 An orthonormal class of exact and simple DFT eigenvectors with a high degree of symmetry 2003
[8] 학술지 Wavelets 1994-05
[9] 학술지 A Novel Windowing Technique for Efficient Computation of MFCC for Speaker Recognition 2013-02
[10] 학술지 The finite Fourier transform 1969
[11] 웹사이트 Shift zero-frequency component to center of spectrum – MATLAB fftshift http://www.mathworks[...] The MathWorks, Inc. 2014-03-10
[12] 서적 Digital Signal Processing: Principles, Algorithms and Applications https://archive.org/[...] Prentice-Hall International 1996
[13] 서적 Discrete-time signal processing https://archive.org/[...] Prentice Hall 1999
[14] 서적 Continuous and Discrete Signal and System Analysis Holt, Rinehart and Winston 1984
[15] 학술지 Uncertainty Relation for the Discrete Fourier Transform 2008
[16] 학술지 Entropy-Based Uncertainty Measures for L^2(\mathbb{R}^n),\ell^2(\mathbb{Z}), and \ell^2(\mathbb{Z}/N\mathbb{Z}) With a Hirschman Optimal Transform for \ell^2(\mathbb{Z}/N\mathbb{Z}) http://redwood.berke[...] 2005-08
[17] 학술지 Uncertainty principles and signal recovery 1989
[18] 학술지 Discrete Gauss-Hermite functions and eigenvectors of the centered discrete Fourier transform https://ieeexplore.i[...] 2007
[19] 학술지 Generalized Discrete Fourier Transform With Nonlinear Phase http://web.njit.edu/[...] 2010-09
[20] 학술지 Uniqueness of the discrete Fourier transform 2023
[21] 웹사이트 Digital Signal Processing https://assets.cambr[...]
[22] 문서 디지털 신호 처리 분야의 고전인 Oppenheim과 Schafer의 저서 '디지털 신호 처리'에서는 i 대신 j^2 = -1을 사용하고 있다.


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com