고속 푸리에 변환(FFT, Fast Fourier Transform)이란, 푸리에 변환을 빠르게 수행할 수 있는 알고리즘이다. 일반적으로 이산 푸리에 변환(Discrete Fourier Transform)을 빠르게 수행하기 위해 사용하는데, DFT는 n개의 샘플에 대해 O(n^2)의 계산이 필요하지만 FFT는 O(nlogn)의 계산만 하면 된다. FFT의 핵심은 "쪼개어 생각하기"이다. 총 2N개의 샘플이 있을 때, 이를 짝수 인덱스와 홀수 인덱스로 분리하여 나타내는 것이다. 다니엘슨 - 란초스 보조정리 (D-L Lemma) 아래와 같은 DFT가 있다고 하자. 이때, x_n은 복소수열이며 이의 DFT인 f_k도 복소수열이다. 아래와 같이 Twiddle Factor W_n을 정의할 때, 복소평면에서 이는 ..

군(group) 이항연산 집합 S에 대하여, S의 이항연산(binary operation)이란 S x S에서 S로 mapping 하는 연산을 말한다. 즉, 이항연산 f는 S x S -> S의 map이다. 어떤 이항연산 *에 대하여 *(a, b) = (a*b)로 표기하도록 한다. 이항연산은 다음과 같은 두 가지 특징을 가질 수 있다. 결합법칙(associative) : S의 임의의 원소 x, y, z에 대해, (x*y)*z = x*(y*z) 교환법칙(communicative): S의 임의의 원소 x, y에 대해, x*y = y*z 항등원과 역원 항등원(identity): 이항연산 *: S x S-> S에 대해, 모든 S의 원소 a에 대하여 a*e = e*a = a인 S의 원소 e가 존재하면 e를 항등원이라..