이산 푸리에 변환

1. 개요

이산 푸리에 변환(Discrete Fourier Transform, DFT)은 이산적인 데이터 집합의 푸리에 변환이다. 기본적인 푸리에 변환이 정의역이 연속적인 함수에 사용되는 것에 비해, 이산 푸리에 변환은 어떤 함수를 완벽하게 변환하는 데에 있지 않고, 이산적인 특정한 데이터에 대한 푸리에 변환값을 계산하는 데에 있으므로, 주로 전해석함수가 아닌 함수[1]에 푸리에 변환을 적용하고 싶을 때 사용한다.

2. 상세

이산 푸리에 변환은 다음과 같은 식으로써 정의된다.

Discrete Fourier Transform (DFT)

[math(\displaystyle X[k]= \sum_{n=0}^{N-1} x[n] e^{-i\frac{2 \pi k n}{N}} \quad \quad )]

Inverse Discrete Fourier Transform (IDFT)

[math(\displaystyle x[n]=\dfrac{1}{N} \sum_{k=0}^{N-1} X[k] e^{i\frac{2 \pi k n}{N}} \quad \quad )]

이산 푸리에 변환은 변환의 목적이 전해석 함수의 완벽한 변환이 아닌 특정적인 이산적 데이터의 변환을 추구하므로, 적분 기호 [math(\int)]대신, 합 기호 [math(\sum)]를 쓴다. 또한 영점으로부터 변환을 하는 범위가 유한하므로 추상적인 [math(\infty)] 대신 유한한 임의의 정수 N-1을 범위로 설정한다.

이산 푸리에 변환을 통해 시간영역의 신호를 주파수영역의 분포로 나타내는 파워스펙트럼(power spectrum) 또는 파워 스펙트럼 밀도(power spectral density)로 나타낼 수 있으며, 이 때 주파수 해상도를 식으로 나타내면 [math(\displaystyle \Delta f = \dfrac{f_s (샘플링 주파수)}{N (이산 데이터 수)} {Hz})]가 된다.

3. 선형성 정의

푸리에 해석은 지수 함수와 함수 공간간에 선형결합이 정의된 해석이다. 그러므로, 이산 부분의 집합에서도 마찬가지로 푸리에 해석을 적용하면, 내적인 직교화 과정은 각 지점에서 계산된 곱의 합이 영이되게 함으로써, 고유함수가 직교화 간격의 공간 지점과 동일한 이산 집합에서 직교화가 된다는 특징이 존재한다.

\displaystyle \langle f, g\rangle = \int_{x_0}^{x_0+P} f(x) \overline{g(x)} dx </math>

자연수 집합 N에 대한 [math(x_k)]를 [math(\displaystyle x_k=\dfrac{2\pi k}{N})] [2]로 정의하고, 임의의 정수 n과 [math(x_k)]로 정의되는 함수 [math(\phi_n(x))]와 지수함수 [math(e^{inx})]가 같다고 가정하자. 그러므로 선형결합으로 정의된 푸리에 해석을 적용하면, 이산 집합에서의 푸리에 변환도 다음과 같이 정의된다.

\displaystyle \langle \phi_n, \phi_m\rangle = \sum_{k=0}^{N-1} \overline{\phi_n(x_k)} \phi_m(x_k) </math>

여기서 [math(\displaystyle x_k=\dfrac{2\pi k}{N})]임을 다시한번 상기하면,

\displaystyle \langle \phi_n, \phi_m\rangle = \sum_{k=0}^{N-1} e^{\frac{2\pi ik(n-m)}{N}} = \sum_{k=0}^{N-1} r^k </math>

r=1일때, 위 식은 N값을 가지게되거나, [math(\sum)]의 유한 합 공식 [math(\frac{1-r^{N}}{1-r})]이라는 유한한 기하급수이다. 하지만, [math(r^{N}=e^{2\pi i(n-m)})]이고, n과 m은 제한된 정수 값이기 때문에, n과 m이 서로 같거나 다를때 [math(r^N=1)]이 정의된다. 그러므로 크로네커 델타의 정의를 이용하면,

\displaystyle \langle \phi_n, \phi_m\rangle =N \sum_{n=-\infty}^{\infty} \delta_{m-n},nN</math>

크로네커 델타를 이용한 무한합은 0이 아니지만, m-n이 N의 배수가 아니라면 위 식의 모든 무한합은 0이다. 하지만 함수 [math(\phi_n)]가 N 지점에서 정의되어, N이 유일하게 선형 비의존적이기때문에 위의 식은 복잡한 편이다. 그러므로,

\phi_{n+N}(x_k)=e^{\frac{2\pi i(n+N)k}{N}}=e^{\frac{2\pi ink}{N}}=\phi_n(x_k) </math>

0과 N-1사이 범위에서 n과 m의 값을 제한할수 있다. 그러므로 직교화 관계가 다음과 같이 정의된다.

\displaystyle \langle \phi_n, \phi_m\rangle =N\delta_{mn}</math>

3.1. 이산 시간 푸리에 변환

Discrete Time Fourier Transform (DTFT)

[math(\displaystyle X(\omega) = \sum_{n=-\infty}^{\infty} x\left[n\right] \,e^{-i \omega n})]

DTFT는 디지털과 같은 이산적인 데이터의 집합에 푸리에 변환을 적용하는 것이다. 여기서 [math(\omega)]는 디지털 각 주파수라 불리기도 하는데, 단위는 라디안/샘플이다. 푸리에 변환과 DTFT와의 관계는 라플라스 변환과 Z-변환의 관계와 유사하다고 볼 수 있다.

DTFT는 변환 결과물이 주기적이며 연속적이라는 특징이 있다. 즉 시간 영역에서는 이산적이지만 주파수 영역에서 연속적이다.
다만 컴퓨터 상에서는 잘 사용되지 않는데, 그 이유는 변환이 함수형이고, 무한급수를 해석해야 하고, 역변환이 인테그럴이기 때문에 통상적인 프로그래밍[3]의 범주를 벗어나기 때문이다.

3.2. 고속 푸리에 변환

Fast Fourier Transform (FFT)

이산적인 [math( n )]개의 데이터가 주어질 때 DFT는 [math( \mathcal{\Theta}(n^2) )]에 돌아가기 때문에 n이 커지면 사용하기 곤란한데, FFT는 이를 [math( \mathcal{\Theta}(n \log n) )]의 연산량만으로 계산하는 알고리즘이다. 주로 분할 정복법을 이용한다.

1965년에 쿨리와 튜키가 개발한 쿨리-튜키 알고리즘이 많이 사용되며, 이 이외에도 Good-Thomas, Bruun's, Rader's, Bluestein's FFT 알고리즘 등이 존재한다.

3.2.1. 쿨리-튜키 알고리즘

Cooley-Tukey algorithm

이 알고리즘은 이미 이전에 여러 번 다른 수학자들에 의해 독립적으로 발견되었다가 잊혀져 왔으며, 거슬러 올라가면 가우스조차도 유사한 방법을 개발하여 사용하였다고 한다.

참고로 분할 정복시 입력값을 둘이 아닌 다른 수로 똑같이 나눠 계산하는 방법도 존재하지만, 둘로 나누는 편이 더 간단하다.[4] 따라서 입력값을 둘로만 나누면 되게 데이터 개수 [math(n)]를 2의 거듭제곱(64, 128, 256, ...)으로 두는 경우가 흔하다.

그럼 만약에 데이터 개수가 2의 거듭제곱이 아니면 어떻게 되느냐는 질문이 나올 수 있는데, 이럴 경우 "데이터 개수보다 크면서 가장 가까운 2의 거듭제곱"을 기준으로 잡고, 나머지 데이터는 0으로 채우는 제로패딩을 하면 된다. 예를 들어 121개의 데이터가 입력되었으면 이보다 큰 2의 거듭제곱에서 121과 가장 가까운 2⁷ = 128을 선택하고, 나머지 7개는 제로패딩을 넣는 식이다.

3.2.1.1. 상세

길이가 1인 수열 [math(x=\{c_0\})]를 DFT한 결과는 [math(X=\{c_0\})]이다.

이번엔 길이가 2인 수열 [math(x=\{c_0, c_1\})]을 DFT해보자. 그 결과는 다음과 같다:

[math(X[0] = e^{\frac{0}{2} \times 2 \pi i} c_0 + e^{\frac{0}{2} \times 2 \pi i}c_1)]
[math(X[1] = e^{\frac{0}{2} \times 2 \pi i} c_0 + e^{\frac{1}{2} \times 2 \pi i}c_1)]

이번엔 길이가 4인 수열 [math(x=\{c_0, c_1, c_2, c_3\})]을 DFT해보자. 그 결과는 다음과 같다:

[math(X[0] = e^{\frac{0}{4} \times 2 \pi i} c_0 + e^{\frac{0}{4} \times 2 \pi i}c_1 + e^{\frac{0}{4} \times 2 \pi i}c_2 + e^{\frac{0}{4} \times 2 \pi i}c_3)]
[math(X[1] = e^{\frac{0}{4} \times 2 \pi i} c_0 + e^{\frac{1}{4} \times 2 \pi i}c_1 + e^{\frac{2}{4} \times 2 \pi i}c_2 + e^{\frac{3}{4} \times 2 \pi i}c_3)]
[math(X[2] = e^{\frac{0}{4} \times 2 \pi i} c_0 + e^{\frac{2}{4} \times 2 \pi i}c_1 + e^{\frac{4}{4} \times 2 \pi i}c_2 + e^{\frac{6}{4} \times 2 \pi i}c_3)]
[math(X[3] = e^{\frac{0}{4} \times 2 \pi i} c_0 + e^{\frac{3}{4} \times 2 \pi i}c_1 + e^{\frac{6}{4} \times 2 \pi i}c_2 + e^{\frac{9}{4} \times 2 \pi i}c_3)]

이것을 유심히 살펴보면 흥미로운 패턴을 발견할 수 있다. 위의 일련의 식들의 짝수번째 항들부터 살펴보자. 보면 빨간색으로 색칠된 부분과 파란 색으로 색칠된 부분이 각각 DFT([math(\{c_0, c_2\})])의 0번째와 1번째 값과 같음을 알 수 있다.[5]
[math(X[0] = {\color{red} e^{\frac{0}{4} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{0}{4} \times 2 \pi i}c_1} + {\color{red} e^{\frac{0}{4} \times 2 \pi i}c_2} + {\color{grey} e^{\frac{0}{4} \times 2 \pi i}c_3})]
[math(X[1] = {\color{blue} e^{\frac{0}{4} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{1}{4} \times 2 \pi i}c_1} + {\color{blue} e^{\frac{2}{4} \times 2 \pi i}c_2} + {\color{grey} e^{\frac{3}{4} \times 2 \pi i}c_3})]
[math(X[2] = {\color{red} e^{\frac{0}{4} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{2}{4} \times 2 \pi i}c_1} + {\color{red} e^{\frac{4}{4} \times 2 \pi i}c_2} + {\color{grey} e^{\frac{6}{4} \times 2 \pi i}c_3})]
[math(X[3] = {\color{blue} e^{\frac{0}{4} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{3}{4} \times 2 \pi i}c_1} + {\color{blue} e^{\frac{6}{4} \times 2 \pi i}c_2} + {\color{grey} e^{\frac{9}{4} \times 2 \pi i}c_3})]

홀수 번째 항들도 살펴보자. 빨간 색으로 되어 있는 부분과 파란 색으로 되어 있는 부분이 각각 DFT([math(\{c_1, c_3\})])의 0번째와 1번째 값과 같은데, [math(X[2], X[3])]에서는 이에 [math(e^{\pi i} = -1)]이 추가로 곱해졌으며, [math(X[1]과 X[3])]에서는 [math(e^{\frac{1}{4} \times 2\pi i})]가 추가로 곱해진 것을 확인할 수 있다.
[math(X[0] = {\color{grey} e^{\frac{0}{4} \times 2 \pi i} c_0} + {\color{red} e^{\frac{0}{4} \times 2 \pi i}c_1} + {\color{grey} e^{\frac{0}{4} \times 2 \pi i}c_2} + {\color{red}e^{\frac{0}{4} \times 2 \pi i}c_3})]
[math(X[1] = {\color{grey} e^{\frac{0}{4} \times 2 \pi i} c_0} + e^{\frac{1}{4} \times 2\pi i}{\color{blue} e^{\frac{0}{4} \times 2 \pi i}c_1} + {\color{grey} e^{\frac{2}{4} \times 2 \pi i}c_2} + e^{\frac{1}{4} \times 2\pi i} {\color{blue}e^{\frac{2}{4} \times 2 \pi i}c_3})]
[math(X[2] = {\color{grey} e^{\frac{0}{4} \times 2 \pi i} c_0} + e^{ \pi i}{\color{red} e^{\frac{0}{4} \times 2 \pi i}c_1} + {\color{grey} e^{\frac{4}{4} \times 2 \pi i}c_2} + e^{\pi i}{\color{red} e^{\frac{4}{4} \times 2 \pi i}c_3})]
[math(X[3] = {\color{grey} e^{\frac{0}{4} \times 2 \pi i} c_0} + e^{\pi i}e^{\frac{1}{4} \times 2 \pi i}{\color{blue} e^{\frac{0}{4} \times 2 \pi i}c_1} + {\color{grey} e^{\frac{6}{4} \times 2 \pi i}c_2} + e^{\pi i}e^{\frac{1}{4} \times 2 \pi i}{\color{blue} e^{\frac{6}{4} \times 2 \pi i}c_3})]

그러니까, [math(\{c_0, c_2\})]와 [math(\{c_1, c_3\})]의 DFT를 구하면, 이것들을 이용해 [math(x=\{c_0, c_1, c_2, c_3\})]의 DFT를 구할 수 있다.

이번엔 [math(x=\{c_0, c_1, c_2, c_3, c_4, c_5, c_6, c_7\})]을 DFT해보자. 짝수번째 항들부터 살펴보면, 빨간색, 주황색, 초록색, 파란색이 각각 DFT([math(\{c_0, c_2, c_4, c_6\})])의 0번째, 1번째, 2번째, 3번째 값임을 알 수 있다.

[ 펼치기 • 접기 ]: [math(X[0] = {\color{red} e^{\frac{0}{8} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_1} + {\color{red} e^{\frac{0}{8} \times 2 \pi i} c_2} + {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_3} + {\color{red} e^{\frac{0}{8} \times 2 \pi i} c_4} + {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_5} + {\color{red} e^{\frac{0}{8} \times 2 \pi i} c_6} + {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_7})]
[math(X[1] = {\color{orange} e^{\frac{0}{8} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{1}{8} \times 2 \pi i} c_1} + {\color{orange} e^{\frac{2}{8} \times 2 \pi i} c_2} + {\color{grey} e^{\frac{3}{8} \times 2 \pi i} c_3} + {\color{orange} e^{\frac{4}{8} \times 2 \pi i} c_4} + {\color{grey} e^{\frac{5}{8} \times 2 \pi i} c_5} + {\color{orange} e^{\frac{6}{8} \times 2 \pi i} c_6} + {\color{grey} e^{\frac{7}{8} \times 2 \pi i} c_7})]
[math(X[2] = {\color{green} e^{\frac{0}{8} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{2}{8} \times 2 \pi i} c_1} + {\color{green} e^{\frac{4}{8} \times 2 \pi i} c_2} + {\color{grey} e^{\frac{6}{8} \times 2 \pi i} c_3} + {\color{green} e^{\frac{8}{8} \times 2 \pi i} c_4} + {\color{grey} e^{\frac{10}{8} \times 2 \pi i} c_5} + {\color{green} e^{\frac{12}{8} \times 2 \pi i} c_6} + {\color{grey} e^{\frac{14}{8} \times 2 \pi i} c_7})]
[math(X[3] = {\color{blue} e^{\frac{0}{8} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{3}{8} \times 2 \pi i} c_1} + {\color{blue} e^{\frac{6}{8} \times 2 \pi i} c_2} + {\color{grey} e^{\frac{9}{8} \times 2 \pi i} c_3} + {\color{blue} e^{\frac{12}{8} \times 2 \pi i} c_4} + {\color{grey} e^{\frac{15}{8} \times 2 \pi i} c_5} + {\color{blue} e^{\frac{18}{8} \times 2 \pi i} c_6} + {\color{grey} e^{\frac{21}{8} \times 2 \pi i} c_7})]
[math(X[4] = {\color{red} e^{\frac{0}{8} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{4}{8} \times 2 \pi i} c_1} + {\color{red} e^{\frac{8}{8} \times 2 \pi i} c_2} + {\color{grey} e^{\frac{12}{8} \times 2 \pi i} c_3} + {\color{red} e^{\frac{16}{8} \times 2 \pi i} c_4} + {\color{grey} e^{\frac{20}{8} \times 2 \pi i} c_5} + {\color{red} e^{\frac{24}{8} \times 2 \pi i} c_6} + {\color{grey} e^{\frac{28}{8} \times 2 \pi i} c_7})]
[math(X[5] = {\color{orange} e^{\frac{0}{8} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{5}{8} \times 2 \pi i} c_1} + {\color{orange} e^{\frac{10}{8} \times 2 \pi i} c_2} + {\color{grey} e^{\frac{15}{8} \times 2 \pi i} c_3} + {\color{orange} e^{\frac{20}{8} \times 2 \pi i} c_4} + {\color{grey} e^{\frac{25}{8} \times 2 \pi i} c_5} + {\color{orange} e^{\frac{30}{8} \times 2 \pi i} c_6} + {\color{grey} e^{\frac{35}{8} \times 2 \pi i} c_7})]
[math(X[6] = {\color{green} e^{\frac{0}{8} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{6}{8} \times 2 \pi i} c_1} + {\color{green} e^{\frac{12}{8} \times 2 \pi i} c_2} + {\color{grey} e^{\frac{18}{8} \times 2 \pi i} c_3} + {\color{green} e^{\frac{24}{8} \times 2 \pi i} c_4} + {\color{grey} e^{\frac{30}{8} \times 2 \pi i} c_5} + {\color{green} e^{\frac{36}{8} \times 2 \pi i} c_6} + {\color{grey} e^{\frac{42}{8} \times 2 \pi i} c_7})]
[math(X[7] = {\color{blue} e^{\frac{0}{8} \times 2 \pi i} c_0} + {\color{grey} e^{\frac{7}{8} \times 2 \pi i} c_1} + {\color{blue} e^{\frac{14}{8} \times 2 \pi i} c_2} + {\color{grey} e^{\frac{21}{8} \times 2 \pi i} c_3} + {\color{blue} e^{\frac{28}{8} \times 2 \pi i} c_4} + {\color{grey} e^{\frac{35}{8} \times 2 \pi i} c_5} + {\color{blue} e^{\frac{42}{8} \times 2 \pi i} c_6} + {\color{grey} e^{\frac{49}{8} \times 2 \pi i} c_7})]

홀수 번째 항들도 살펴 보면, 빨간색, 주황색, 초록색, 파란색이 각각 DFT([math(\{c_1, c_3, c_5, c_7\})])의 0, 1, 2, 3번째 값과 같음을 알 수 있으며, 이들에 각각 [math(e^{\frac{0}{8} \times 2 \pi i})], [math(e^{\frac{1}{8} \times 2 \pi i})], [math(e^{\frac{2}{8} \times 2 \pi i})], [math(e^{\frac{3}{8} \times 2 \pi i})]이 곱해진 것을 알 수 있고, [math(X[4])], [math(X[5])], [math(X[6])], [math(X[7])]에서는 [math(e^{\pi i} = -1)]이 추가로 곱해진 것을 알 수 있다.

[ 펼치기 • 접기 ]: [math(X[0] = {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_0} + {\color{red} e^{\frac{0}{8} \times 2 \pi i} c_1} + {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_2} + {\color{red} e^{\frac{0}{8} \times 2 \pi i} c_3} + {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_4} + {\color{red} e^{\frac{0}{8} \times 2 \pi i} c_5} + {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_6} + {\color{red} e^{\frac{0}{8} \times 2 \pi i} c_7})]
[math(X[1] = {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_0} + e^{\frac{1}{8} \times 2 \pi i} {\color{orange} e^{\frac{0}{8} \times 2 \pi i} c_1} + {\color{grey} e^{\frac{2}{8} \times 2 \pi i} c_2} + e^{\frac{1}{8} \times 2 \pi i} {\color{orange} e^{\frac{2}{8} \times 2 \pi i} c_3} + {\color{grey} e^{\frac{4}{8} \times 2 \pi i} c_4} + e^{\frac{1}{8} \times 2 \pi i} {\color{orange} e^{\frac{4}{8} \times 2 \pi i} c_5} + {\color{grey} e^{\frac{6}{8} \times 2 \pi i} c_6} + e^{\frac{1}{8} \times 2 \pi i} {\color{orange} e^{\frac{6}{8} \times 2 \pi i} c_7})]
[math(X[2] = {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_0} + e^{\frac{2}{8} \times 2 \pi i} {\color{green} e^{\frac{0}{8} \times 2 \pi i} c_1} + {\color{grey} e^{\frac{4}{8} \times 2 \pi i} c_2} + e^{\frac{2}{8} \times 2 \pi i} {\color{green} e^{\frac{4}{8} \times 2 \pi i} c_3} + {\color{grey} e^{\frac{8}{8} \times 2 \pi i} c_4} + e^{\frac{2}{8} \times 2 \pi i} {\color{green} e^{\frac{8}{8} \times 2 \pi i} c_5} + {\color{grey} e^{\frac{12}{8} \times 2 \pi i} c_6} + e^{\frac{2}{8} \times 2 \pi i} {\color{green} e^{\frac{12}{8} \times 2 \pi i} c_7})]
[math(X[3] = {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_0} + e^{\frac{3}{8} \times 2 \pi i} {\color{blue} e^{\frac{0}{8} \times 2 \pi i} c_1} + {\color{grey} e^{\frac{6}{8} \times 2 \pi i} c_2} + e^{\frac{3}{8} \times 2 \pi i} {\color{blue} e^{\frac{6}{8} \times 2 \pi i} c_3} + {\color{grey} e^{\frac{12}{8} \times 2 \pi i} c_4} + e^{\frac{3}{8} \times 2 \pi i} {\color{blue} e^{\frac{12}{8} \times 2 \pi i} c_5} + {\color{grey} e^{\frac{18}{8} \times 2 \pi i} c_6} + e^{\frac{3}{8} \times 2 \pi i} {\color{blue} e^{\frac{18}{8} \times 2 \pi i} c_7})]
[math(X[4] = {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_0} + e^{\pi i} {\color{red} e^{\frac{0}{8} \times 2 \pi i} c_1} + {\color{grey} e^{\frac{8}{8} \times 2 \pi i} c_2} + e^{\pi i} {\color{red} e^{\frac{8}{8} \times 2 \pi i} c_3} + {\color{grey} e^{\frac{16}{8} \times 2 \pi i} c_4} + e^{\pi i} {\color{red} e^{\frac{16}{8} \times 2 \pi i} c_5} + {\color{grey} e^{\frac{24}{8} \times 2 \pi i} c_6} + e^{\pi i} {\color{red} e^{\frac{24}{8} \times 2 \pi i} c_7})]
[math(X[5] = {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_0} + e^{\pi i} e^{\frac{1}{8} \times 2 \pi i} {\color{orange} e^{\frac{0}{8} \times 2 \pi i} c_1} + {\color{grey} e^{\frac{10}{8} \times 2 \pi i} c_2} + e^{\pi i} e^{\frac{1}{8} \times 2 \pi i} {\color{orange} e^{\frac{10}{8} \times 2 \pi i} c_3} + {\color{grey} e^{\frac{20}{8} \times 2 \pi i} c_4} + e^{\pi i} e^{\frac{1}{8} \times 2 \pi i} {\color{orange} e^{\frac{20}{8} \times 2 \pi i} c_5} + {\color{grey} e^{\frac{30}{8} \times 2 \pi i} c_6} + e^{\pi i} e^{\frac{1}{8} \times 2 \pi i} {\color{orange} e^{\frac{30}{8} \times 2 \pi i} c_7})]
[math(X[6] = {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_0} + e^{\pi i} e^{\frac{2}{8} \times 2 \pi i} {\color{green} e^{\frac{0}{8} \times 2 \pi i} c_1} + {\color{grey} e^{\frac{12}{8} \times 2 \pi i} c_2} + e^{\pi i} e^{\frac{2}{8} \times 2 \pi i} {\color{green} e^{\frac{12}{8} \times 2 \pi i} c_3} + {\color{grey} e^{\frac{24}{8} \times 2 \pi i} c_4} + e^{\pi i} e^{\frac{2}{8} \times 2 \pi i} {\color{green} e^{\frac{24}{8} \times 2 \pi i} c_5} + {\color{grey} e^{\frac{36}{8} \times 2 \pi i} c_6} + e^{\pi i} e^{\frac{2}{8} \times 2 \pi i} {\color{green} e^{\frac{36}{8} \times 2 \pi i} c_7})]
[math(X[7] = {\color{grey} e^{\frac{0}{8} \times 2 \pi i} c_0} + e^{\pi i} e^{\frac{3}{8} \times 2 \pi i} {\color{blue} e^{\frac{0}{8} \times 2 \pi i} c_1} + {\color{grey} e^{\frac{14}{8} \times 2 \pi i} c_2} + e^{\pi i} e^{\frac{3}{8} \times 2 \pi i} {\color{blue} e^{\frac{14}{8} \times 2 \pi i} c_3} + {\color{grey} e^{\frac{28}{8} \times 2 \pi i} c_4} + e^{\pi i} e^{\frac{3}{8} \times 2 \pi i} {\color{blue} e^{\frac{28}{8} \times 2 \pi i} c_5} + {\color{grey} e^{\frac{42}{8} \times 2 \pi i} c_6} + e^{\pi i} e^{\frac{3}{8} \times 2 \pi i} {\color{blue} e^{\frac{42}{8} \times 2 \pi i} c_7})]

따라서 길이가 8인 수열의 DFT 역시 짝수번째 항들의 DFT와 홀수번째 원소들의 DFT, 즉 길이가 4인 수열 두 개의 DFT를 이용해 구할 수 있다. 그런데 위에서 봤듯 길이가 4인 홀수와 짝수번째 항들의 DFT역시, 홀수번째 항들과 짝수번째 항들의 DFT를 이용해 구할 수 있다. 따라서 다음과 같은 재귀적인 알고리즘으로 DFT를 구할 수 있을 것이다:

복소수의 배열 input_seq를 입력받는다. input_seq의 길이는 2의 거듭제곱이어야 하며, DFT의 최종 결과값들은 별도의 결과값 배열이 아닌 input_seq에 담길 것이다.
input_seq의 길이를 나타내는 정수 n을 정의한다.
n의 값이1이면, 아무것도 하지 않고 종료한다.
그렇지 않다면, 길이가 n/2인 두 배열 odd_elements와 even_elements를 만들고, input_seq의 홀수 번째 항들은 odd_elements에, 짝수번째 항들은 even_elements에 순서대로 넣는다. 또한 복소수 w=[math(e^{\frac{1}{n} \times 2 \pi i} = \cos{\frac{2 \pi}{n}} + i\sin{\frac{2 \pi}{n}})]을 정의해 둔다.
odd_elements와 even_elements를 현재 설명하고 있는 이 알고리즘으로 DFT한다.
i = 0이 n/2-1이 될 때까지 1씩 증가시키며, 다음을 반복한다:

input_seq의 i번째 원소는 even_elements[i] + odd_elements * w ^ i로, n/2+i번째 원소는 even_elements[i] - odd_elements * w ^ i의 값으로 채워 넣는다.

#!syntax cpp

#include <vector>
#include <cmath>
#include <complex>

using namespace std;
const double PI = acos(-1);
typedef complex<double> cd;

void fft(vector<cd> &input_seq) {
    int n = input_seq.size();
    if (n == 1) return;

    cd w(cos(2 * PI / n), sin(2 * PI / n));
    vector<cd> odd_elements(n/2), even_elements(n/2);
    for (int i=0; i<n/2; i++) {
        even_elements[i] = input_seq[i * 2];
        odd_elements[i] = input_seq[i * 2 + 1];
    }
    fft(odd_elements);
    fft(even_elements);
    
    cd ws_power(1, 0);
    for (int i=0; i<n/2; i++) {
        input_seq[i] = even_elements[i] + odd_elements[i] * ws_power;
        input_seq[i + n/2] = even_elements[i] - odd_elements[i] * ws_power;
        ws_power *= w;
    }
}

이 알고리즘의 시간 복잡도에 대해 알아보자. 위 재귀함수 내에 입력된 배열의 길이에 비례하는 시간이 걸리는 for문이 존재한다([math(\mathcal{O}(n) )]). 재귀 깊이가 1만큼 깊어질 때마다, 입력되는 배열의 길이는 절반으로, 해당 깊이에서 함수가 호출되는 횟수는 두 배로 늘어나므로, 시간 복잡도가 [math(\mathcal{O}(n) )]씩 늘어나게 된다. 재귀의 최대 깊이는 log(n)이므로, 이 알고리즘의 전체 시간 복잡도는 [math(\mathcal{O}(n\log n) )]이 된다.

3.3. 단시간 푸리에 변환

Short-Time Fourier Transform (STFT)

DFT나 FFT는 "해당 신호의 전체 구간"에 대한 주파수 분석을 수행하므로, 만약 해당 신호의 주파수가 시간에 따라 계속 변한다면 [6] 해당 변화를 제대로 반영하기 어렵다는 단점이 있다. 즉 시간 해상도가 매우 낮다.

이러한 한계를 극복하기 위한 것이 STFT로, DFT나 FFT를 수행한 신호에 일정한 시간 간격으로 "창함수 (window)"를 줌으로서, 해당 창함수 내에서는 신호의 주파수가 거의 일정(quasi-stationary)하다는 가정하에 창함수를 계속 옮겨가면서 주파수 분석을 함으로서, 시간에 따라 변하는 신호의 주파수 정보를 분석하는 것이다. 이것을 시각화한 것이 바로 스펙트로그램이다.

창함수는 사각형, 삼각형, 한, 해밍, 블랙맨, 카이저 등 다양한 종류가 있으며, 창함수에 따라 주파수 분석의 정밀도도 달라진다. 일례로 가장 기본적인 사각형 (박스카로도 부른다) 창함수는 DFT/FFT 상수에 1을 곱하는 임펄스 트레인, 그러니까 DFT를 그대로 가져가는 창함수이다.

불확정성의 원리에 의해 창함수를 시간축으로 넓게 가져가면 주파수 해상도가 좋아지지만, 대신 시간 해상도는 낮아진다. 반면 창함수를 시간축으로 짧게 분석하면 시간 해상도가 좋아지지만, 반대로 주파수 해상도가 낮아진다는 단점이 있다. 참고로 창의 주파수 해상도는 직사각형 창일 때 [math(\displaystyle \Delta f = \dfrac{f_s (신호의 샘플링 주파수)}{L (창함수 너비)} {Hz})]이며, 창함수의 종류에 따라 좀 다르다. 신호의 전체 구간 대신 창함수만큼의 DFT 개수만을 가져가니, 상술했던 식에서 N을 L로 바꾸면 된다.

사각형을 제외한 다른 창함수의 경우는 기본적으로 창함수를 50% 간격으로 중첩(overlap)시킨다.

STFT를 이용한 스펙트로그램은 음향기기, 음성학이나 ARG 등 다양한 분야에 응용되고 있다.

4. 활용

푸리에 변환이라는 특성이 그렇듯이 이산범위의 푸리에 변환도 전자공학에서도 많이 사용된다. 소리 등의 신호처리나 통신 시스템 등 많은 분야에 DFT의 원리가 적용되어 있다. 신호를 분석하고 가공, 처리하는데 있어 푸리에 변환의 중요도는 매우 높은데, 디지털 도메인에서 계산을 수행해야 하기 때문에 이산적인 데이터를 푸리에 변환하는 DFT를 사용해야 하기 때문이다. 다만 DFT 수식을 컴퓨터로 바로 계산하면 계산량이 매우 많기 때문에 상술한 FFT(고속 푸리에 변환)를 사용해서 DFT를 계산한다.

MP3 같은 음악 압축 알고리즘에서도 사용된다. MP3 의 압축 기법중에는 FFT 변환해서 사람이 듣기 힘든 고음역이나 저음역을 날려 버려서 데이터 양을 줄이는 방법이 포함되어 있다.

DFT와 친척뻘인 개념으로 이산 코사인 변환(DCT) 등이 있다.

양자 알고리즘에 사용되는 양자푸리에변환(QFT)도 이 DFT식을 바탕으로 한다.

[math(\displaystyle U_\text{QFT}(|y\rangle)=\sum_{x=0}^{Q-1} e^{-i\frac{2\pi x y}{Q}}|x\rangle \quad \quad )]
[math(\displaystyle U_\text{IQFT}(|x\rangle)=\frac{1}{\sqrt{Q}}\sum_{y=0}^{Q-1} e^{i\frac{2\pi x y}{Q}}|y\rangle \quad \quad )]

양자 컴퓨팅에서 QFT대신 IQFT를 양자 알고리즘의 레지스터로써 쓴다.

푸리에 해석이라는게 그렇듯이 DFT의 개념 자체는 굉장히 쉽지만, 독학하려고 한다면 약간 까다롭다. 푸리에 해석은 디리클레 수렴 조건과 파르세발 정리를 만족하는 특정 함수의 주기성을 추상적인 범위에서 다루는 공리이다. 그래서 푸리에 해석을 설명하고자 할때 중요한 주기부분이 변수인 임의의 수식이고, 그에따라 고유 함수의 부호와 계수가 임의로 지정될수 있기 때문이다. 그래서 인터넷에 검색해보면 식이 다 제각각이다.

4.1. 다항식의 곱셈과 합성곱

최고차항의 차수가 같은 같은 두 다항식 [math(f(x) = a_0 + a_1x + a_2x^2 + a_3x^3, g(x) = b_0 + b_1x + b_2x^2 + b_3x^3)]의 곱 [math(h(x) = f \times g)]는 다음과 같다:
[math(h(x) = a_0b_0 + (a_1b_0 + a_0b_1)x + (a_2b_0 + a_1b_1 + a_0b_2)x^2 + (a_3b_0 + a_2b_1 + a_1b_2 + a_0b_3)x^3 + (a_3b_1 + a_2b_2 + a_1b_3)x^4 + (a_3b_2 + a_2b_3) x^5 + a_3b_3x^6)]

이 곱해진 다항식의 계수들을 구하는 방법 중엔, 이중 반복문을 돌며 일일이 하나씩 곱해서 더하는 [math(\mathcal{O}(n^2) )]짜리 방법도 있지만, 후술할 DFT를 이용해서 구하는 방법도 있다.

[math(\{a_0, a_1, a_2, a_3, 0, 0, 0, 0\})]와 [math(\{b_0, b_1, b_2, b_3, 0, 0, 0, 0\})]의 DFT를 구해 보자.

[ 펼치기 • 접기 ]: [math(F[0] = f(e^{\frac{0}{8} \times 2 \pi i}) = a_0 e^{\frac{0}{8} \times 2 \pi i} + a_1 e^{\frac{0}{8} \times 2 \pi i} + a_2 e^{\frac{0}{8} \times 2 \pi i} + a_3 e^{\frac{0}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{0}{8} \times 2 \pi i} + 0 e^{\frac{0}{8} \times 2 \pi i} + 0 e^{\frac{0}{8} \times 2 \pi i} + 0 e^{\frac{0}{8} \times 2 \pi i}})]
[math(F[1] = f(e^{\frac{1}{8} \times 2 \pi i}) = a_0 e^{\frac{0}{8} \times 2 \pi i} + a_1 e^{\frac{1}{8} \times 2 \pi i} + a_2 e^{\frac{2}{8} \times 2 \pi i} + a_3 e^{\frac{3}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{4}{8} \times 2 \pi i} + 0 e^{\frac{5}{8} \times 2 \pi i} + 0 e^{\frac{6}{8} \times 2 \pi i} + 0 e^{\frac{7}{8} \times 2 \pi i}})]
[math(F[2] = f(e^{\frac{2}{8} \times 2 \pi i}) = a_0 e^{\frac{0}{8} \times 2 \pi i} + a_1 e^{\frac{2}{8} \times 2 \pi i} + a_2 e^{\frac{4}{8} \times 2 \pi i} + a_3 e^{\frac{6}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{8}{8} \times 2 \pi i} + 0 e^{\frac{10}{8} \times 2 \pi i} + 0 e^{\frac{12}{8} \times 2 \pi i} + 0 e^{\frac{14}{8} \times 2 \pi i}})]
[math(F[3] = f(e^{\frac{3}{8} \times 2 \pi i}) = a_0 e^{\frac{0}{8} \times 2 \pi i} + a_1 e^{\frac{3}{8} \times 2 \pi i} + a_2 e^{\frac{6}{8} \times 2 \pi i} + a_3 e^{\frac{9}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{12}{8} \times 2 \pi i} + 0 e^{\frac{15}{8} \times 2 \pi i} + 0 e^{\frac{18}{8} \times 2 \pi i} + 0 e^{\frac{21}{8} \times 2 \pi i}})]
[math(F[4] = f(e^{\frac{4}{8} \times 2 \pi i}) = a_0 e^{\frac{0}{8} \times 2 \pi i} + a_1 e^{\frac{4}{8} \times 2 \pi i} + a_2 e^{\frac{8}{8} \times 2 \pi i} + a_3 e^{\frac{12}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{16}{8} \times 2 \pi i} + 0 e^{\frac{20}{8} \times 2 \pi i} + 0 e^{\frac{24}{8} \times 2 \pi i} + 0 e^{\frac{28}{8} \times 2 \pi i}})]
[math(F[5] = f(e^{\frac{5}{8} \times 2 \pi i}) = a_0 e^{\frac{0}{8} \times 2 \pi i} + a_1 e^{\frac{5}{8} \times 2 \pi i} + a_2 e^{\frac{10}{8} \times 2 \pi i} + a_3 e^{\frac{15}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{20}{8} \times 2 \pi i} + 0 e^{\frac{25}{8} \times 2 \pi i} + 0 e^{\frac{30}{8} \times 2 \pi i} + 0 e^{\frac{35}{8} \times 2 \pi i}})]
[math(F[6] = f(e^{\frac{6}{8} \times 2 \pi i}) = a_0 e^{\frac{0}{8} \times 2 \pi i} + a_1 e^{\frac{6}{8} \times 2 \pi i} + a_2 e^{\frac{12}{8} \times 2 \pi i} + a_3 e^{\frac{18}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{24}{8} \times 2 \pi i} + 0 e^{\frac{30}{8} \times 2 \pi i} + 0 e^{\frac{36}{8} \times 2 \pi i} + 0 e^{\frac{42}{8} \times 2 \pi i}})]
[math(F[7] = f(e^{\frac{7}{8} \times 2 \pi i}) = a_0 e^{\frac{0}{8} \times 2 \pi i} + a_1 e^{\frac{7}{8} \times 2 \pi i} + a_2 e^{\frac{14}{8} \times 2 \pi i} + a_3 e^{\frac{21}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{28}{8} \times 2 \pi i} + 0 e^{\frac{35}{8} \times 2 \pi i} + 0 e^{\frac{42}{8} \times 2 \pi i} + 0 e^{\frac{49}{8} \times 2 \pi i}})]

[math(G[0] = g(e^{\frac{0}{8} \times 2 \pi i}) = b_0 e^{\frac{0}{8} \times 2 \pi i} + b_1 e^{\frac{0}{8} \times 2 \pi i} + b_2 e^{\frac{0}{8} \times 2 \pi i} + b_3 e^{\frac{0}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{0}{8} \times 2 \pi i} + 0 e^{\frac{0}{8} \times 2 \pi i} + 0 e^{\frac{0}{8} \times 2 \pi i} + 0 e^{\frac{0}{8} \times 2 \pi i}})]
[math(G[1] = g(e^{\frac{1}{8} \times 2 \pi i}) = b_0 e^{\frac{0}{8} \times 2 \pi i} + b_1 e^{\frac{1}{8} \times 2 \pi i} + b_2 e^{\frac{2}{8} \times 2 \pi i} + b_3 e^{\frac{3}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{4}{8} \times 2 \pi i} + 0 e^{\frac{5}{8} \times 2 \pi i} + 0 e^{\frac{6}{8} \times 2 \pi i} + 0 e^{\frac{7}{8} \times 2 \pi i}})]
[math(G[2] = g(e^{\frac{2}{8} \times 2 \pi i}) = b_0 e^{\frac{0}{8} \times 2 \pi i} + b_1 e^{\frac{2}{8} \times 2 \pi i} + b_2 e^{\frac{4}{8} \times 2 \pi i} + b_3 e^{\frac{6}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{8}{8} \times 2 \pi i} + 0 e^{\frac{10}{8} \times 2 \pi i} + 0 e^{\frac{12}{8} \times 2 \pi i} + 0 e^{\frac{14}{8} \times 2 \pi i}})]
[math(G[3] = g(e^{\frac{3}{8} \times 2 \pi i}) = b_0 e^{\frac{0}{8} \times 2 \pi i} + b_1 e^{\frac{3}{8} \times 2 \pi i} + b_2 e^{\frac{6}{8} \times 2 \pi i} + b_3 e^{\frac{9}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{12}{8} \times 2 \pi i} + 0 e^{\frac{15}{8} \times 2 \pi i} + 0 e^{\frac{18}{8} \times 2 \pi i} + 0 e^{\frac{21}{8} \times 2 \pi i}})]
[math(G[4] = g(e^{\frac{4}{8} \times 2 \pi i}) = b_0 e^{\frac{0}{8} \times 2 \pi i} + b_1 e^{\frac{4}{8} \times 2 \pi i} + b_2 e^{\frac{8}{8} \times 2 \pi i} + b_3 e^{\frac{12}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{16}{8} \times 2 \pi i} + 0 e^{\frac{20}{8} \times 2 \pi i} + 0 e^{\frac{24}{8} \times 2 \pi i} + 0 e^{\frac{28}{8} \times 2 \pi i}})]
[math(G[5] = g(e^{\frac{5}{8} \times 2 \pi i}) = b_0 e^{\frac{0}{8} \times 2 \pi i} + b_1 e^{\frac{5}{8} \times 2 \pi i} + b_2 e^{\frac{10}{8} \times 2 \pi i} + b_3 e^{\frac{15}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{20}{8} \times 2 \pi i} + 0 e^{\frac{25}{8} \times 2 \pi i} + 0 e^{\frac{30}{8} \times 2 \pi i} + 0 e^{\frac{35}{8} \times 2 \pi i}})]
[math(G[6] = g(e^{\frac{6}{8} \times 2 \pi i}) = b_0 e^{\frac{0}{8} \times 2 \pi i} + b_1 e^{\frac{6}{8} \times 2 \pi i} + b_2 e^{\frac{12}{8} \times 2 \pi i} + b_3 e^{\frac{18}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{24}{8} \times 2 \pi i} + 0 e^{\frac{30}{8} \times 2 \pi i} + 0 e^{\frac{36}{8} \times 2 \pi i} + 0 e^{\frac{42}{8} \times 2 \pi i}})]
[math(G[7] = g(e^{\frac{7}{8} \times 2 \pi i}) = b_0 e^{\frac{0}{8} \times 2 \pi i} + b_1 e^{\frac{7}{8} \times 2 \pi i} + b_2 e^{\frac{14}{8} \times 2 \pi i} + b_3 e^{\frac{21}{8} \times 2 \pi i}{\color{grey} + 0 e^{\frac{28}{8} \times 2 \pi i} + 0 e^{\frac{35}{8} \times 2 \pi i} + 0 e^{\frac{42}{8} \times 2 \pi i} + 0 e^{\frac{49}{8} \times 2 \pi i}})]

이를 이용해 [math(H = \{F[0]G[0], F[1]G[1] ... F[7]G[7]\} = \{h(e^{\frac{0}{8} \times 2 \pi i}), h(e^{\frac{1}{8} \times 2 \pi i}), ... h(e^{\frac{7}{8} \times 2 \pi i})\})]를 구할 수 있으며, 이를 역변환하면 h의 계수들을 얻을 수 있다.

상술한 고속 푸리에 변환 알고리즘을 이용하여 DFT와 역변환을 [math(\mathcal{O}(n\log n) )]만에 구하면, 전체 과정의 시간 복잡도 역시 [math(\mathcal{O}(n\log n) )]이 된다.

이렇게 다항식의 곱셈을 [math(\mathcal{O}(n\log n) )]만에 해낼 수 있다는 사실은, 어떤 이산시간 도메인 상의 두 데이터의 합성곱을 구할 때 빛을 발한다. 두 배열이 다항식의 계수들을 나열한 것들이라 생각하고, 위의 방법을 적용하여 두 다항식의 곱의 계수들을 빠르게 얻으면, 그것이 곧 해당 데이터들의 합성곱이다.

5. 참고 문헌

G. B. Arfken, et al., Mathematical Method for Physicists : A Comprehensive Guide

6. 여담

한편 가우스의 발명은 쿨리-튜키 알고리즘 이후에 발견되었는데, 사후에 3권에 라틴어로 쓰여진 비표준적인 방법으로 쓰였기 때문에 쉽사리 발견하기 어려웠다고 한다.

[1] 전해석함수(entire function)란 모든 구간에서 적분이 가능한 함수이다. [2] 단, [math((k=0,1,2,....,N-1))] [3] 컴퓨터 대수학 시스템 같은 인공지능 수준에서나 가능하다. [4] 아예 이렇게 둘로만 나누는 쿨리-튜키 알고리즘을 "FFT 알고리즘"이라고 부를 때가 많다. [5] DFT[math(\{c_0, c_2\} = \{)]
[math(e^{\frac{0}{2} \times 2 \pi i} c_0 + e^{\frac{0}{4} \times 2 \pi i}c_2,)]
[math(e^{\frac{0}{4} \times 2 \pi i} c_0 + e^{\frac{2}{4} \times 2 \pi i}c_2)]
[math(\})] [6] 일례로, 삼각함수(sinusoid)의 진폭은 일정하고 진동수만 계속 변하는 신호를 처프(chirp)라 부른다. 좀 더 복잡한 예로, 음성신호도 시간에 따라 주파수가 변하는 신호이다.

이산수학 Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all"	이론
<colbgcolor=#3CC> 기본 대상	수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열	등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합	경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프	수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타	P-NP 문제^미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설^미해결 · 콜라츠 추측^미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서	논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학	}}}}}}}}}