디지털 신호처리를 들으며 퓨리에 변환에 대해 다시 배우는데,
대학 시절 이를 처음 배우고 재밌어서 들떴던 기억이 새록새록 난다.
고마운 사람이 공유해 준 비디오를 보며 적은 노트를 기록하고자 한다.
출처 - https://youtu.be/h7apO7q16V0
FFT 적용
* Wireless communication, GPS 등 신호를 처리하는 모든 기술에 적용
FFT를 표현하는 다양한 방법
* FFT Circuit (그래프로 표현)
* Discrete Fourier Transform (행렬로 표현)
* Time Domain (시간 영역 함수로 표현)
* Frequency Domain (주파수 영역 함수로 표현)
FFT가 어떤 것인 지, 실제로 문제를 맞닥뜨리며 살펴보자
다항식을 어떻게 표현하면 좋을까요?
1. 계수로 표현
* 컴퓨터에선 다항식과 이들의 곱을 계수를 통해 표현할 수 있을 것이다
=> Coefficient Representation
* 각 다항식의 차수를 d라고 가정하면, 이의 시간 복잡도는 O(d^2)가 된다.
=> O(d^2)다 더 빠른 방법이 있을까?
2. 값으로 표현
* 1차 방정식 y = ax + b는 a와 b의 값으로도 표현할 수 있지만 (계수 표현),
* 두 개의 점을 지나는 직선으로도 표현할 수 있다. (값 표현)
* 즉, 차수가 d인 다항식을 유일하게 표현할 수 있는 점들의 최소 갯수는 (d+1)이다.
* 즉 {(x0, P(x0)), (x1, P(x1)), ..., (xd, P(xd))}의 쌍으로도 다항식을 나타낼 수 있다는 뜻.
=> 이런 방식을 값으로 표현 - Value Representation -이라 한다!
=> 장점
: 다항식의 곱이 훨씬 쉬워진다.
: 각 다항식 그래프가 지나는 (임의의 x, y) 점들을
: (차수 + 1)개 만큼씩 구해
: 서로 곱하여
: 다항식의 곱 그래프가 지나는 점들을 구한다.
=> 시간복잡도는 O(d)가 된다.
3. 결론 - 다항식의 곱을 구하는 가장 효율적인 방법은?
(1) 다항식을 계수 => 값 표현으로 변환 [Coeff => Value]
: "Evaluation"
(2) 값 표현된 다항식들을 곱함
(3) 그 결과를 값 => 계수 표현으로 바꿈 [Value => Coeff]
: "Interpolation"
Coeff -> Value (FFT), 혹은 Evaluation 과정
다시 한 번, d차수의 다항식을 '유일하게 정의'할 수 있으려면 (d+1)개 이상의 점들이 필요하다
* (d+1)개 이상의 n개 점으로 표현했을 때,
* (n, P(n))을 계산하는 것은 d 시간이 들고,
* (1, P(1))부터 (n, P(n))까지 계산하는 것은 n 시간이 드니
* 총 시간 복잡도는 O(nd), 혹은 O(d^2)가 된다. => 더 빠를 수 있지 않겠어?
* 여기서 odd함수 (P(x) = -P(-x))나 even함수 (P(x) = -P(x))의 성질을 이용하면, 필요한 점의 갯수를 반으로 줄일 수 있다.
* 즉, 어떠한 n차 다항식이 있을 때, 이의
: 홀수 (odd) 함수의 합을 Po(x^3) = xPo(x^2),
: 짝수 (even) 함수의 합을 Pe(x^2) 라고 하자.
: 그렇다면 위의 이미지와 같이, n차 다항식을 (n/2 - 1)차 다항식의 합으로 표현할 수 있게 되는 것이다!
: 그리고 초록 박스 안의 부분은 같은 논리로 재귀적으로 쪼갤 수 있다 => (n/2)개의 점을 계산하면 해결
* 따라서 전체 해결과정은 위와 같이 되고, 이의 시간 복잡도는 O(n * log n) 이 되는 것이다.
: n차수를 반씩 쪼개 (log n) 재귀적으로 해결.
복소수 도입
* 다만 여기서 문제가 있는데, odd함수나 even함수의 성질을 이용하기 위해서, x가 + / - 의 "쌍"을 이루어야한다는 점이다.
* 세 번째 단계에서는 이것이 불가능하다. 모든 x가 제곱되어 + 만 존재하기 때문.
* 이를 해결해주기 위해서, x^2 < 0가 가능하도록, 복소수를 도입한다. (cf. i * i = -1)
* 결국 문젠,
d차 다항식이 있을 때, n >= (d + 1)을 만족하는 n = 2^k (k는 정수)를 구하고,
점들은 1의 n제곱근을 구하는 문제가 된다.
1의 n제곱근의 극좌표계 표현
* 1의 n제곱근 <=> z^n = 1과 상통.
* 가로축은 실수, 세로축은 허수부를 나타내며, e^(iθ) = cos(θ) + isin(θ)로 나타내지는 극좌표계를 생각해보자.
* 극좌표계에서 (1, 0), (-1, 0), (0, 1i,), (0, -1i)를 지나는 원의 원주를 n으로 나누면,
각 지점과 원점 (0, 0)을 연결하는 직선의 각은 2π / n이 된다.
* w = e^(2πi/n)임을 이용하면,
각 점들은 (w^0 = 1), (w^1 = e^(2π(1)i/n)), ..., (w^(n-1) = e^(2π(n-1)i/n) )과 같이 표현될 수 있다!
* 결국 문제는 P(x)를 [1, w^1, w^2, ..., w^n]에 대하여 'evaluate'하는 문제로 치환될 수 있음.
* 극좌표계에서 1의 n제곱근들은 항상 + / - 쌍으로 이루어져있기에, 재귀적 풀이에서도 문제가 일어나지 않는다.
FFT의 코드 표현
Value -> Coefficient (IFFT), 혹은 Interpolation 과정
* Coefficient -> Value를 어떻게 하는 지 봤으니, 반대의 Value -> Coefficient는 어떻게 수행하는 지 보자.
* 다항식을 행렬로 표현했을 때, xk = w^k, w = 2^(2πi/n)을 이용, Discrete Fourier Transform (DFT) Matrix를 구한다.
* DFT Matrix의 인버젼 이용하여 계산하는 과정이 interpolation이 되겠다.
* 여기서 중요한 점은, DFT의 인버젼은 아름답게도 w가 (1/n)*w^(-1)로 치환된 꼴을 띄며,
* IFFT는 w을 (1/n)*e^(-2πi/n)로 치환한 꼴의 FFT 풀이와 같다는 뜻이 된다!
정리
결국 퓨리에 변환은
1. 다항식 곱을 값으로 표현 (Value Representation)
2. Evaluation을 +/- 쌍에 대해 수행
3. Evaluation을 1의 n제곱근에 대해 수행 -> FFT
4. Interpolation또한 FFT에서 한 값만 변화해서 수행
의 아름다운 아이디어로 복잡한 수식을 간단하고 재귀적으로 풀게 해주는 알고리즘이다.
'학점은행제' 카테고리의 다른 글
| [네트워크] 학습복습 - 통신의 개념, 컴퓨터 네트워크 역사, OSI7계층 (0) | 2021.05.24 |
|---|---|
| [컴퓨터시스템] 학습복습 - 유닉스/리눅스, 커널, 시스템 호출 (0) | 2021.05.22 |
| [C언어 I] 학습복습 - 포인터, 포인터 연산 및 배열, 다중 포인터, 배열 포인터, 함수 포인터, 스트림, EOF, 문자열 입출력 함수 및 버퍼 (0) | 2021.05.22 |
| [C 언어 I] 학습복습 - printf, scanf함수, 반복문, 조건식, 함수, 지역변수, 전역변수, register, 재귀함수, 배열 (0) | 2021.05.22 |
| [C 언어 I] 학습복습 - C언어 개론, 변수, 연산자, 데이터 표현, 기본 자료형 (0) | 2021.05.20 |
댓글