Fast Fourier Transformation
- Ref
- 이산 푸리에변환과 그 역변환을 빠르게 수행하는 효율적인 알고리즘을 일컫는 말이다
- 기존 이산 푸리에변환이 O(N2) 의 연산이 필요한 것에 반해 FFT는 O(NlogN) 으로 필요한 연산량이 상대적으로 매우 적음을 알 수 있다
- 연속적 신호에 대한 푸리에 변환은 다음과 같이 정의된다
- X(w)=∫−∞∞x(t)exp[−iwt]dt
- 이산 푸리에 변환은 무한적분을 유한합으로 대체한다
- X(wk)=n=0∑N−1x(tn)exp[−2πiNkn]=n=0∑N−1x(tn)exp[−T2πi⋅Nk⋅nT]
- 해석
- T2πi 는 주기 T 초동안 2π 만큼의 위상이 변하는데, 변수가 시간 t 이므로 곱해주게 되는 비례 계수coefficient 이다
- Nk 에서 k=N 이라면 exp[−2πin] 이 되어, 각 샘플 간격사이의 위상차가 2π 로 되고, k=1 이라면 n=0일때 exp[0] ,n=N 일때 exp[−2πi] 로 전체 샘플링 범위 사이의 위상차가 2π 가 된다
- 용어들
- k=0,1,⋯,N−1
- X(wk) : 주파수 wk 에서의 x 의 스펙트럼
- x(tn) : 시간 tn 에서의 입력 신호의 진폭
- tn=nT : n 번째 샘플링
- wk=kΩ=T2πNk : k번째 주파수 샘플
- Ω:NT2π : 주파수 샘플링 간격
- T : 샘플링 간격
- N : 시간 샘플 수 또는 주파수 샘플 수 number of samples
- 이산 푸리에 변환 행렬표기
- X(wk)=n=0∑N−1x(tn)exp[−2πiNkn]
- wN=exp[N−2πi] 로 표기하면 X(wk)=n=0∑N−1x(tn)wNnk
- ⎣⎢⎢⎢⎢⎢⎡X(w0)X(w1)X(w2)⋯X(wN−1)⎦⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎢⎡wN0wN0wN0⋯wN0wN0wN1(wN2)1(wNN−1)1⋯⋯⋯⋯wN0wNN−1(wN2)N−1(wNN−1)N−1⎦⎥⎥⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎡x(t0)x(t1)x(t2)⋯x(tN−1)⎦⎥⎥⎥⎥⎥⎤
- X(wj) 를 계산하는데 O(N) 이 요구되고 총 변환되는 수가 N 개이므로, 연산에 총 O(N2) 만큼이 소요된다
- wN=exp[−N2πi] 의 성질
- 주기성
- wNnk=exp[−N2πikn]=exp[−N2πi(kn+Nm)] m∈Z 인 임의의 정수
- wNnk=wNnkmod(N) 이다 (mmod(N)=m%n , m=aN+c 라면 mmod(N)=c)
- 만약 N=4,n=2,k=3 이라면
- w46=w42
- 대칭성
- wNk(N−n)=wN−kn
- wNk(2n)=wN/2kn
- wNk+N/2=exp[−N2πi(k+N/2)]=exp[−πi]wNk=−wNk
- 다항함수를 우함수와 기함수의 합으로 구하듯이, 짝수n 을 갖는 wNnk 와 홀수 n 을 갖는 wNnk 항들로 분리시킬 수 있다
- N=2p 이라 가정하자
- X[wk]=n=0∑N−1x(tn)wNkn=n=even∑X[tn]wNkn+n=odd∑X(tn)wNkn
- X[wk]=r=0∑2N−1x(t2r)wN2kr+r=0∑N/2−1x(t2r+1)wN(2r+1)k
- =r=0∑N/2−1x(t2r)(wN2)kr+wNkr=0∑N/2−1x(t2r+1)(wN2)kr
- =r=0∑N/2−1x(t2r)wN/2kr+wNkr=0∑N/2−1x(t2r+1)wN/2kr (wN2=wN/2)
- 이를 각각 짝수번째 샘플과 홀수번째 샘플에 대한 DFT로 Xe,Xo 로 표기하자
- X[wk]=Xe(wk)+wNkXo(wk)
- 즉 하나의 이산 푸리에변환은 2개의 이산 푸리에 변환 합으로 표현된다.
- 2N,4N,⋯,2pN=1 이 될 때까지 푸리의 변환을 잘게 쪼개자.
- 연산 비용
- 1번 쪼개기: 2(2N)2+N=2N2+N
- 2번 쪼개기 2(2(4N)2+2N)+N=4N2+2N
- 3번 쪼개기: 2[2(2(23N)2+22N)+2N]+N
- ...
- p=log2N 번 쪼개기: 2(2(⋯(2(2pN)2+2p−1N)+2p−2N)+⋯))+N=2pN+pN=2log2NN2+pN=N+Nlog2N
- 논리
1. Xe(wk)=r=0∑N/2−1x(t2r)wN/2kr 인데 k′=2N+k 라면 wN/2(N/2+k)r=wN/2(N/2)r⋅wN/2kr=wN/2kr 로 주기성을 갖고 있다. 그러므로 Xo(wj) series 하나를 연산하는데 N/2 텀을 계산
2. Xo(wj) 를 각 주파수 wj,for all j∈{0,1,⋯,N−1} 을 계산하는데, 주기성 덕분에 N/2 번 계산
3. Xe 도 동일한 순서로 계산하므로 곱하기 2
4. 계산된 Xo,Xe 들을 합하는데 N 번 계산하여 도합 (2N)2+N 이 계산된다
- Ref
References
Ref1. Uniqueness of interpolating polynomial
- 조건
- {(x0,y0),(x1,y1),⋯,(xn−1,yn−1)} , n 개 point-value쌍 집합이 있다고 하자. 이 xi 가 모두 다른값을 갖는다고 하자
- 정리
- 그런경우 유일한 다항식 p(xi)=yi (for all i∈{1,2,⋯,n}) 가 존재한다
- 증명
- ⎣⎢⎢⎢⎡11⋯1x0x1xn−1x02x12xn−12⋯⋯⋯x0n−2x1n−2xn−1n−2x0n−1x1n−1xn−1n−1⎦⎥⎥⎥⎤⎣⎢⎢⎢⎡p0p1⋯pn−1⎦⎥⎥⎥⎤=⎣⎢⎢⎢⎡y0y1⋯yn−1⎦⎥⎥⎥⎤
- 만약 좌측 첫번째 행렬이 invertible하다면, [p0p1⋯pn−1]T 는 유일하게 결정된다.
- 증명이 너무 길어 레퍼런스 링크 Ref
Ref2. Complex Roots of Unity
- complex root of unity의 정의
- wn=1
- wn=exp[n2πi] 로 unity의 principal n−th root 이다
- Summation Lemma
- 임의의 정수 n≥1 과 nonzero 정수 k 가 있을때, 다음과 같은 식이 성립한다 (단 wnk=1)
- j=0∑n−1(wnk)j=0
- 증명
- j=0∑n−1(wnk)j=wnk−1(wnk)n−1=wnk−1exp[n2πi⋅k⋅n]−1=wnk−11−1=0
- Halving Lemma
- (wnk)2=wn2kwnn=(wnk+n/2)2
Ref3. coefficient 표현과 point-value 표현사이의 전환
- 용어
- coefficient representation
- p(x)=i=0∑naixi∈Pn(R) 을 β={xn,xn−1,⋯,x1,1} 라 두고, [p]β=[an,an−1,⋯,a0] 로 표현하는 다항식의 표현방법이다
- point-valued representation
- p(x)=i=0∑naixi∈Pn(R) 을 {x0,x1,x2,⋯,xn}⊂R 에 대하여 p(x0),p(x1),⋯,p(xn) 의 값을 갖고 있어 다항식을 결졍하는, 다항식의 표현방법이다
- 주어진 p(x)∈Pn(F) 가 coefficient representation일 때, 이를 point-value representation으로 변환하는 과정을 evaluation 이라 부른다