이곳은 개발을 위한 베타 사이트 입니다.기여내역은 언제든 초기화될 수 있으며, 예기치 못한 오류가 발생할 수 있습니다.문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 이산 푸리에 변환 (문서 편집) [include(틀:상위 문서, top1=푸리에 변환)] [include(틀:관련 문서, top1=이산 코사인 변환)] [include(틀:다른 뜻1, other1=DFT는 이곳으로 넘어옵니다. 양자물리학의 밀도범함수 이론(Density Functional Theory), rd1=밀도범함수 이론)] [include(틀:이산수학)] [목차] == 개요 == 이산 푸리에 변환(Discrete Fourier Transform, DFT)은 이산적인 데이터 집합의 푸리에 변환이다. 기본적인 푸리에 변환이 정의역이 연속적인 함수에 사용되는 것에 비해, 이산 푸리에 변환은 어떤 함수를 완벽하게 변환하는 데에 있지 않고, 이산적인 특정한 데이터에 대한 푸리에 변환값을 계산하는 데에 있으므로, 주로 전해석함수가 아닌 함수[* 전해석함수(entire function)란 모든 구간에서 적분이 가능한 함수이다.]에 푸리에 변환을 적용하고 싶을 때 사용한다. == 상세 == 이산 푸리에 변환은 다음과 같은 식으로써 정의된다. 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})]가 된다. == 선형성 정의 == [[푸리에 해석]]은 지수 함수와 함수 공간간에 선형결합이 정의된 해석이다. 그러므로, 이산 부분의 집합에서도 마찬가지로 푸리에 해석을 적용하면, 내적인 직교화 과정은 각 지점에서 계산된 곱의 합이 영이되게 함으로써, 고유함수가 직교화 간격의 공간 지점과 동일한 이산 집합에서 직교화가 된다는 특징이 존재한다. ||\displaystyle \langle f, g\rangle = \int_{x_0}^{x_0+P} f(x) \overline{g(x)} dx || 자연수 집합 N에 대한 [math(x_k)]를 [math(\displaystyle x_k=\dfrac{2\pi k}{N})] [* 단, [math((k=0,1,2,....,N-1))] ]로 정의하고, 임의의 정수 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(\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 || 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 || 크로네커 델타를 이용한 무한합은 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) || 0과 N-1사이 범위에서 n과 m의 값을 제한할수 있다. 그러므로 직교화 관계가 다음과 같이 정의된다. ||\displaystyle \langle \phi_n, \phi_m\rangle =N\delta_{mn} || === 이산 시간 푸리에 변환 === 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는 변환 결과물이 주기적이며 연속적이라는 특징이 있다. 즉 시간 영역에서는 이산적이지만 주파수 영역에서 연속적이다. 다만 컴퓨터 상에서는 잘 사용되지 않는데, 그 이유는 변환이 함수형이고, 무한급수를 해석해야 하고, 역변환이 인테그럴이기 때문에 통상적인 프로그래밍[* 컴퓨터 대수학 시스템 같은 인공지능 수준에서나 가능하다.]의 범주를 벗어나기 때문이다. === 고속 푸리에 변환 === ||[youtube(eKSmEPAEr2U)]|| 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 알고리즘 등이 존재한다. ==== 쿨리-튜키 알고리즘 ==== Cooley-Tukey algorithm 이 알고리즘은 이미 이전에 여러 번 다른 수학자들에 의해 독립적으로 발견되었다가 잊혀져 왔으며, 거슬러 올라가면 [[카를 프리드리히 가우스|가우스]]조차도 유사한 방법을 개발하여 사용하였다고 한다. 참고로 분할 정복시 입력값을 둘이 아닌 다른 수로 똑같이 나눠 계산하는 방법도 존재하지만, 둘로 나누는 편이 더 간단하다.[* 아예 이렇게 둘로만 나누는 쿨리-튜키 알고리즘을 "FFT 알고리즘"이라고 부를 때가 많다.] 따라서 입력값을 둘로만 나누면 되게 데이터 개수 [math(n)]를 2의 거듭제곱(64, 128, 256, ...)으로 두는 경우가 흔하다. 그럼 만약에 데이터 개수가 2의 거듭제곱이 아니면 어떻게 되느냐는 질문이 나올 수 있는데, 이럴 경우 "데이터 개수보다 크면서 가장 가까운 2의 거듭제곱"을 기준으로 잡고, 나머지 데이터는 0으로 채우는 제로패딩을 하면 된다. 예를 들어 121개의 데이터가 입력되었으면 이보다 큰 2의 거듭제곱에서 121과 가장 가까운 2^^7^^ = 128을 선택하고, 나머지 7개는 제로패딩을 넣는 식이다. ===== 상세 ===== 길이가 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번째 값과 같음을 알 수 있다.[* DFT[math(\{c_0, c_2\} = \{)] [br] [math(e^{\frac{0}{2} \times 2 \pi i} c_0 + e^{\frac{0}{4} \times 2 \pi i}c_2,)] [br] [math(e^{\frac{0}{4} \times 2 \pi i} c_0 + e^{\frac{2}{4} \times 2 \pi i}c_2)] [br] [math(\})]] [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번째 값임을 알 수 있다. {{{#!folding [ 펼치기 • 접기 ] [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)]이 추가로 곱해진 것을 알 수 있다. {{{#!folding [ 펼치기 • 접기 ] [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 #include #include using namespace std; const double PI = acos(-1); typedef complex cd; void fft(vector &input_seq) { int n = input_seq.size(); if (n == 1) return; cd w(cos(2 * PI / n), sin(2 * PI / n)); vector odd_elements(n/2), even_elements(n/2); for (int i=0; i저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기