고속푸리에변환
-
FFT가 빠른 이유Math♾️/Fourier Analysis 2023. 6. 22. 15:58
다항식 A(x)와 B(x)의 곱을 C(x)라고 하자. 이때 다항식 C(x)의 각 항의 계수들은 다음과 같이 각 항을 차례대로 곱하는 분배법칙을 통해서 구할 수 있다. 다항식 간의 곱 연산 시 계산되는 요소는 각 항의 계수이므로 다음과 같이 다항식의 각 항의 계수들만 배열의 형태로 나타내는 방법을 Coefficient Representation이라고 한다. Coefficient Representation을 이용해 각 항을 곱해나가며 계산을 할 경우 A(x)의 각 항은 B(x)의 모든 항과 한 번씩 곱연산을 수행해야 한다. 따라서 A(x), B(x)를 최고차항이 d라고 하면 A(x)의 하나의 항당 B(x)의 모든 d개의 항에 대해서 곱연산을 하며 이를 A(x)의 모든 d개 항에 실시하므로 기본적으로 총 d*..
-
Fast Fourier Transform (FFT)Math♾️/Fourier Analysis 2022. 9. 17. 00:35
FFT 이산 푸리에 변환은 데이터들이 이산적인 형태로 주어졌을 때 이를 벡터로 나타내어 각 데이터점이 어떠한 진동수들로 구성되어 있는지 푸리에 변환을 통해 쪼개고 같은 진동수끼리 합하여 전체 데이터들이 어떠한 진동수를 가지고 있는지 푸리에 domain에서 나타내는 방법이다. 이산 푸리에 변환(DFT)를 이용할 경우에는 $n$개의 $f_n$이 $w^{jk}$ 행렬의 각 행에서 $n$번 곱을 수행하며 이런한 연산을 모든 $n$개의 행에 대해서 반복적으로 수행하므로 빅오 표기법으로 나타내면 DFT 알고리즘의 계산 복잡도는 $O(N^2)$이다. $O(N^2)$의 경우 주어진 데이터의 개수가 늘어날 때 연산 횟수가 제곱에 비례하여 늘어나므로 연산에 필요한 자원이 엄청나다. 따라서 DFT는 데이터의 개수가 조금만 ..