FFT
-
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*..
-
FFT를 이용한 PDE 풀이Math♾️/Fourier Analysis 2022. 9. 21. 00:13
Heat Equation (1D) 위의 방정식은 1차원에서의 시간과 위치(x)에 따른 열분포의 변화를 나타내는 편미분방정식이다. 온도 $u$가 시간 $t$와 공간 $t$에 대하여 변화하므로 두가지 변수에 대한 변화를 동시에 고려해야하므로 해를 구하기가 어렵다. 이때 공간 $x$에 대하여 푸리에 변환을 취하게 되면 $x$를 $k$로 상수의 형태로 바뀌므로 시간과 공간에 대한 편미분 방정식이 오로지 시간에만 대한 상미분 방정식으로 바뀌게 된다. 따라서 해를 구하기에 용이해진다. 미분 텀에 대하여 푸리에 변환을 하게 되면 아래와 같은 형태로 나타난다. 따라서 편미분 방정식을 푸리에 변환하게 되면 다음과 같이 바뀌게 된다. 이산적인 데이터에 대하여 FFT를 이용하여 계산할 때는 공간 term에 대한 푸리에 변환..
-
FFT를 이용한 미분값 계산Math♾️/Fourier Analysis 2022. 9. 19. 11:14
푸리에 변환과 미분 $f(t)$의 미분형을 푸리에 변환하게 되면 위와 같이 $iw$ 텀과 $f(t)$의 푸리에 변환으로 나타나는 것을 알 수 있다. 즉 $f(t)$를 푸리에 변환한 이후 $iw$을 곱한것을 푸리에 역변환하게 되면 $f(t)$의 미분형을 얻을 수 있다. 푸리에 변환시 미분 특징을 FFT에 이용 FFT는 DFT 연산을 빠르게 하는 방법으로 이산적인 데이터에 대하여 푸리에 변환을 가능하게 한다. 푸리에 변환시 미분의 특징을 이산적인 데이터에 적용하면 다음과 같이 나타난다. 그림에서 $k$는 $w$와 동일한 역할을 한다. - $w$는 시간 텀에 대하여 미분하였을 때 사용하며 temporl frequency라고 한다. - $k$는 공간 텀에 대하여 미분하였을 때 사용하며 spatial freque..
-
FFT를 이용한 noise 제거하기Math♾️/Fourier Analysis 2022. 9. 17. 22:59
nosie 제거 방법 신호를 측정시 신호에는 측정 대상이 되는 신호이외의 여러 noise들이 끼어 들어오게 된다. 이는 원래의 신호를 분석하는데 noise들이 방해가 되므로 이들을 제거해야한다. 신호를 측정시 측정된 신호간에는 측정기기로 인한 term이 생겨 이산적인 데이터를 얻게 되므로 이를 푸리에 변환하기 위해서는 DFT를 이용해하지만 해당 방법은 연산에 드는 자원이 많이 든다. DFT와 같이 이산적 데이터들을 푸리에 변환하면서 연산의 횟수를 줄이는 방법인 FFT를 사용한다. 데이터들을 FFT하여 시간 domain에서 진동수 domain으로 바꾸면 각 데이터점들이 어떠한 진동수들을 가지고 있는지 알 수 있다. 이때 측정하려는 신호는 일정한 진동수들의 조합으로 되어있으므로 각 데이터들점들은 해당 진동수..
-
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는 데이터의 개수가 조금만 ..