안녕 일붕이들아! 시작하기에 앞서, 재밌는 공식 하나를 들고왔어. '오일러의 공식'이라는 건데, 들어본 일붕이도 있을거야.

증명은 테일러 급수를 사용할 수도 있고 복소해석적인 접근도 가능한데, 전자는 sin, cos, exp의 테일러 급수가 복소 범위에서 수렴하는지를 추가로 증명해야 하고 후자는 복소 함수의 적분이 들어가니... 아무튼 궁금하면 알아서 찾아봐.

이번에 할 일은 푸리에 급수에서 범위를 무한대로 늘리고 삼각함수 대신 지수함수를 사용하는거라고 했는데, 이때 바로 저 오일러 공식이 사용돼. 저 공식을 잘봐. 지수함수와 삼각함수가 i를 매개로 이어져있지? 뭔가 감이 오지 않아? 지난번의 푸리에 급수와 오일러의 공식을 잘 엮으면 어떻게 될 것 같지?

푸리에 변환:

푸리에 역변환:

응 유도과정 귀찮아~ 안알랴줌^^ 농담이고 동네 도서관 가서 공업수학 책 빌려보면 나와. 나보다는 책이 더 엄밀하게 유도해줄거야. 그리고 f에 곱하는게 이게 아니라 좀 다른거고 역변환 앞에 1 / 2pi가 붙어있고 뭐 그런 버전들도 있는데, 걔들도 다 같은소리임.

암튼 이 과정을 통해 우리는 어떤 함수, 즉 신호에서 각 주파수의 성분이 얼마나 포함되어 있는지를 알 수 있어. 푸리에 급수에서는 주파수들이 불연속적이었지만, 이번에는 연속적이라구.

그런데 이걸 바로 응용해서 EQ를 만들거나, 앰프 시뮬을 만들거나 할 수는 없어. 잘 알고있듯 컴퓨터는 이산적인 신호만 다룰 수 있기 때문이지. 그래서 나온게 이산 푸리에 변환이야.

주기가 N인 복소주기수열 { an }과 { bn }에 대해 내적을

로 정의하자(위에 작대기 그은건 켤레복소수라는 뜻). 그러면

에 대해

는 정규직교기저를 이뤄. 이를 사용해 이산 푸리에 변환과 이산 푸리에 역변환을 정의할 수 있지.

유도는 쉬우니까 생략할게~ 이제 컴퓨터로 푸리에 변환을 수행할 수 있게 됐어.

그런데 문제가 있어. 이걸 곧이곧대로 계산하기는 너무 느리다는거야. 얘를 수식 그대로 계산하는 것은 O(N ^ 2)의 시간복잡도를 가져. 쉽게 말하자면, 계산하는 데 걸리는 시간을 N에 대한 함수로 표현할 때 가장 빠르게 증가하는 항이 N ^ 2에 대한 항이라는 거지. O(N ^ 2)는 별거 아닌 것처럼 보일 수 있는데, 사실 알고리즘의 세계에서 이건 엄청 느린거야.

그래서 발명된게 고속 푸리에 변환이야. 대표적인 분할정복 알고리즘이지. 계산 과정을 짝수와 홀수로 쪼개면 반만 계산해도 나머지 반은 날먹할 수 있다는 아이디어를 사용해. O(N log N)의 시간복잡도를 가지지.

여기서 왼쪽 시그마가 짝수항 DFT, 오른쪽 시그마가 홀수항 DFT야. 여기서 A(n) 계산을 앞 반쪽과 뒤 반쪽으로 나누자.

짠! 공통되는 부분이 보이니까 한번만 계산해 주면 되겠지? 그리고 이 방법을 추가적인 메모리 할당없이 수행하기 위해 인덱스의 비트를 뒤집... 이건 고속 푸리에 변환을 직접 구현하는데 관심있는 일붕이들만 찾아봐. 아래에 내 구현 링크 달아놓을게.

https://wandbox.org/permlink/NWbe7O9UrquPSJKp

아무튼, 이제 컴퓨터는 이산적인 소리 신호를 받아서, 이로부터 각 주파수 성분을 뽑아낼 수 있게 됐어. 이걸로 EQ도 만들고, 앰프 시뮬도 만들고... 하는거야. ir에도 물론 사용되지.

이 이외에도 고속 푸리에 변환은 영상처리에 사용되기도 해. 예를 들어 어떤 사진을 푸리에 변환한 후 노이즈에 해당하는 주파수의 성분을 잘라내고 다시 푸리에 역변환하면 노이즈가 없어지겠지? 말은 간단하지만...ㅠ

또, 고속 푸리에 변환을 사용하면 컨벌루젼(합성곱)을 빠르게 계산할 수 있어. 푸리에 변환과 컨벌루젼의 관계 덕분인데, 이건 비교적 쉬우니까 시간이 남으면 찾아보라구. 컨벌루젼은 인공신경망 등에도 사용되니까 유익할거야.

2차원의 닫힌 곡선을 시간 t에 대한 복소함수라고 생각하면 이런짓도 가능하지. 그리고 싶은 곡선의 각 점의 좌표를 따서, 푸리에 역변환시킨 후, 지수함수의 계수로 던져주기만 하면 돼. 이것도 Processing 언어로 만든거야.

세 파트로 나눠서 푸리에 변환에 대해 알아봤는데 어때? 솔직히 바로 이해하는건 무리라고 생각해. 하지만 차근차근 다시 읽다보면 어느 순간 이해할 수 있을거야. 마지막으로 푸리에 변환을 다룬 유튜브 동영상을 하나 놓고갈게. 나랑은 조금 다른 관점에서 프리에 변환을 바라본 영상이야. 결과적으로는 같은 말이지만... 수학에 관심있는 일붕이라면 이미 구독해뒀을 수도 있어. 좋은 채널이야.

질문은 댓글로 남겨주면 내가 아는 범위 내에서 설명해줄게. 자신은 없지만... 앞으로도 유익한 글로 찾아올게. 안녕!

념글 가고싶어요...