Fast Fourier Transformation

Fast Fourier Transformation

Fast Fourier Transformation

• Ref
• 이산 푸리에변환과 그 역변환을 빠르게 수행하는 효율적인 알고리즘을 일컫는 말이다
• 기존 이산 푸리에변환이 $O(N ^{2})$ 의 연산이 필요한 것에 반해 FFT는 $O(N \log_{}{N})$ 으로 필요한 연산량이 상대적으로 매우 적음을 알 수 있다

이산 푸리에 변환 Discrete Fourier Transformation

• 연속적 신호에 대한 푸리에 변환은 다음과 같이 정의된다
  - $X(w)= \displaystyle\int_{-\infty }^{\infty }{x(t)exp[-i w t]d t}$
• 이산 푸리에 변환은 무한적분을 유한합으로 대체한다
  - $X(w _{k})=\displaystyle\sum_{n=0}^{N-1}{x(t _{n})exp[-2 \pi i\displaystyle\frac{ k }{N}n]}=\displaystyle\sum_{n=0}^{N-1}{x(t _{n})exp[-\displaystyle\frac{2 \pi i}{T}\cdot \displaystyle\frac{k}{N}\cdot nT]}$
• 해석
  - $\displaystyle\frac{2 \pi i }{T}$ 는 주기 $T$ 초동안 $2\pi$ 만큼의 위상이 변하는데, 변수가 시간 $t$ 이므로 곱해주게 되는 비례 계수coefficient 이다
  - $\displaystyle\frac{k}{N}$ 에서 $k=N$ 이라면 $exp[-2 \pi i n]$ 이 되어, 각 샘플 간격사이의 위상차가 $2\pi$ 로 되고, $k=1$ 이라면 $n=0$일때 $exp[0]$ ,$n=N$ 일때 $exp[-2 \pi i]$ 로 전체 샘플링 범위 사이의 위상차가 $2 \pi$ 가 된다
• 용어들
  - $k=0,1,\cdots, N-1$
  - $X(w _{k})$ : 주파수 $w _{k}$ 에서의 $x$ 의 스펙트럼
  - $x(t _{n})$ : 시간 $t _{n}$ 에서의 입력 신호의 진폭
  - $t _{n}=nT$ : $n$ 번째 샘플링
  - $w _{k} =k \Omega=\displaystyle\frac{2 \pi }{T}\displaystyle\frac{k}{N}$ : $k$번째 주파수 샘플
  - $\Omega:\displaystyle\frac{2 \pi}{NT}$ : 주파수 샘플링 간격
  - $T$ : 샘플링 간격
  - $N$ : 시간 샘플 수 또는 주파수 샘플 수 number of samples

Fast Fourier Transform의 정의

• 이산 푸리에 변환 행렬표기
  - $X(\boldsymbol{w}_{k})=\displaystyle\sum_{n=0}^{N-1}{x(t _{n})exp[-2 \pi i\displaystyle\frac{ k }{N}n]}$
  - $w _{N}= exp[\displaystyle\frac{-2 \pi i }{N}]$ 로 표기하면 $X(w _{k})=\displaystyle\sum_{n=0}^{N-1}x({t _{n}}) w _{N} ^{nk}$
  - $\begin{bmatrix} X(w _{0})\\ X(w _{1}) \\ X(w _{2}) \\ \cdots \\ X(w _{N-1}) \end{bmatrix}=\begin{bmatrix} w _{N} ^{0} & w _{N} ^{0} & \cdots & w _{N} ^{0} \\ w _{N} ^{0} & w _{N} ^{1} & \cdots & w _{N} ^{N-1} \\ w _{N} ^{0} & (w _{N} ^{2}) ^{1} & \cdots & (w _{N} ^{2}) ^{N-1} \\ \cdots \\ w _{N} ^{0} & (w _{N} ^{N-1}) ^{1} & \cdots & (w _{N} ^{N-1}) ^{N-1} \end{bmatrix}\begin{bmatrix} x(t _{0}) \\ x(t _{1}) \\ x(t _{2}) \\ \cdots \\ x(t _{N-1}) \end{bmatrix}$
  - $X(w _{j})$ 를 계산하는데 $\mathcal{O}(N)$ 이 요구되고 총 변환되는 수가 $N$ 개이므로, 연산에 총 $\mathcal{O}(N ^{2})$ 만큼이 소요된다
• $w _{N}=exp[-\displaystyle\frac{2\pi i }{N}]$ 의 성질
  - 주기성
  - $w _{N} ^{nk}=exp\left[-\displaystyle\frac{2 \pi i k n}{N}\right]= exp\left[-\displaystyle\frac{2 \pi i (k n+Nm)}{N}\right]$ $m \in \mathbb{Z}$ 인 임의의 정수
  - $w _{N} ^{nk}=w _{N} ^{nk \,\,mod(N)}$ 이다 ($m \,\,mod (N)=m\%n$ , $m=aN+c$ 라면 $m \,\,mod(N)=c$)
  - 만약 $N=4 , n=2, k=3$ 이라면
  - $w _{4} ^{6}=w _{4} ^{2}$
  - 대칭성
  - $w _{N} ^{k(N-n)}=w _{N} ^{-kn}$
  - $w _{N} ^{k(2n)}=w _{N/2} ^{kn}$
  - $w _{N} ^{k+N/2}=exp[- \displaystyle\frac{2 \pi i (k+N/2)}{N}]=exp[-\pi i ]w _{N} ^{k}=- w _{N} ^{k}$
• 다항함수를 우함수와 기함수의 합으로 구하듯이, 짝수$n$ 을 갖는 $w _{N} ^{nk}$ 와 홀수 $n$ 을 갖는 $w _{N} ^{nk}$ 항들로 분리시킬 수 있다
  - $N= 2 ^{p}$ 이라 가정하자
  - $X[w _{k}]=\displaystyle\sum_{n=0}^{N-1}{x(t _{n})w _{N} ^{kn}}=\displaystyle\sum_{n=even}^{}{X[t _{n}]w _{N} ^{kn}}+\displaystyle\sum_{n=odd}^{}{X(t _{n})w _{N} ^{kn}}$
  - $X[w _{k}]=\displaystyle\sum_{r=0}^{\frac{N}{2}-1}{x(t _{2r})w _{N} ^{2kr}}+\displaystyle\sum_{r=0}^{N/2-1}{x(t _{2r+1})w _{N} ^{(2r+1)k}}$
  - $=\displaystyle\sum_{r=0}^{N/2-1}{x(t _{2r})(w _{N} ^{2}) ^{kr}}+w _{N} ^{k}\displaystyle\sum_{r=0}^{N/2-1}{x(t _{2r+1})(w _{N} ^{2}) ^{kr}}$
  - $=\displaystyle\sum_{r=0}^{N/2-1}{x(t _{2r})w _{N/2} ^{kr}}+w _{N} ^{k}\displaystyle\sum_{r=0}^{N/2-1}{x(t _{2r+1})w _{N/2} ^{kr}}$ $(w _{N} ^{2}=w _{N/2})$
  - 이를 각각 짝수번째 샘플과 홀수번째 샘플에 대한 DFT로 $X _{e},X _{o}$ 로 표기하자
  - $X[w _{k}]=X _{e}(w _{k})+w _{N} ^{k}X _{o}(w _{k})$
  - 즉 하나의 이산 푸리에변환은 2개의 이산 푸리에 변환 합으로 표현된다.
  - $\displaystyle\frac{N}{2},\displaystyle\frac{N}{4},\cdots,\displaystyle\frac{N}{2 ^{p}}=1$ 이 될 때까지 푸리의 변환을 잘게 쪼개자.
• 연산 비용
  - 1번 쪼개기: $2(\displaystyle\frac{N}{2}) ^{2}+N=\displaystyle\frac{N ^{2}}{2}+N$
  - 2번 쪼개기 $2(2(\displaystyle\frac{N}{4}) ^{2}+\displaystyle\frac{N}{2})+N=\displaystyle\frac{N ^{2}}{4}+2N$
  - 3번 쪼개기: $2[2(2(\displaystyle\frac{N}{2 ^{3}}) ^{2}+\displaystyle\frac{N}{2 ^{2}})+\displaystyle\frac{N}{2}]+N$
  - ...
  - $p=\log_{2}{N}$ 번 쪼개기: $2(2(\cdots(2 (\displaystyle\frac{N}{2 ^{p}}) ^{2}+\displaystyle\frac{N}{2 ^{p-1}})+\displaystyle\frac{N}{2 ^{p-2}})+\cdots))+N=\displaystyle\frac{N}{2 ^{p}}+pN=\displaystyle\frac{N ^{2}}{2 ^{\log_{2}{N}}}+pN=N+N \log_{2}{N}$
• 논리
  1. $X _{e}(w _{k})=\displaystyle\sum_{r=0}^{N/2-1}{x(t _{2r})w _{N/2} ^{kr}}$ 인데 $k'=\displaystyle\frac{N}{2}+k$ 라면 $w _{N/2} ^{(N/2+k)r}=w _{N/2} ^{(N/2)r}\cdot w _{N/2} ^{kr}=w _{N/2} ^{kr}$ 로 주기성을 갖고 있다. 그러므로 $X _{o}(w _{j})$ series 하나를 연산하는데 $N/2$ 텀을 계산
  2. $X _{o}(w _{j})$ 를 각 주파수 $w _{j},\text{for all }{j} \in \{0,1,\cdots,N-1\}$ 을 계산하는데, 주기성 덕분에 $N/2$ 번 계산
  3. $X _{e}$ 도 동일한 순서로 계산하므로 곱하기 2
  4. 계산된 $X _{o},X _{e}$ 들을 합하는데 $N$ 번 계산하여 도합 $(\displaystyle\frac{N}{2}) ^{2}+N$ 이 계산된다
• Ref

References

Ref1. Uniqueness of interpolating polynomial

• 조건
  - $\{ (x _{0},y _{0}),(x _{1},y _{1}),\cdots,(x _{n-1},y _{n-1}) \}$ , $n$ 개 point-value쌍 집합이 있다고 하자. 이 $x _{i}$ 가 모두 다른값을 갖는다고 하자
• 정리
  - 그런경우 유일한 다항식 $p(x _{i})=y _{i}$ $(\text{for all }{i} \in \{1,2,\cdots,n\})$ 가 존재한다
• 증명
  - $\begin{bmatrix} 1 & x _{0} & x _{0} ^{2} & \cdots & x _{0} ^{n-2} & x _{0} ^{n-1} \\ 1 & x _{1} & x _{1} ^{2} & \cdots & x _{1} ^{n-2} & x _{1} ^{n-1} \\ \cdots \\ 1 & x _{n-1} & x _{n-1} ^{2} & \cdots & x _{n-1} ^{n-2} & x _{n-1} ^{n-1} \end{bmatrix} \begin{bmatrix} p _{0} \\ p _{1} \\ \cdots \\ p _{n-1} \end{bmatrix}=\begin{bmatrix} y _{0} \\ y _{1} \\ \cdots \\ y _{n-1} \end{bmatrix}$
  - 만약 좌측 첫번째 행렬이 invertible하다면, $\begin{bmatrix} p _{0} & p _{1} & \cdots & p _{n-1} \end{bmatrix}^{\mathsf{T}}$ 는 유일하게 결정된다.
  - 증명이 너무 길어 레퍼런스 링크 Ref

Ref2. Complex Roots of Unity

• complex root of unity의 정의
  - $w ^{n}=1$
  - $w _{n}= exp[\displaystyle\frac{2 \pi i }{n}]$ 로 unity의 principal $n-th$ root 이다
• Summation Lemma
  - 임의의 정수 $n \ge 1$ 과 nonzero 정수 $k$ 가 있을때, 다음과 같은 식이 성립한다 (단 $w _{n} ^{k} \neq 1$)
  - $\displaystyle\sum_{j=0}^{n-1}{(w _{n} ^{k}) ^{j}=0}$
  - 증명
  - $\displaystyle\sum_{j=0}^{n-1}{(w _{n} ^{k}) ^{j}}=\displaystyle\frac{(w _{n} ^{k}) ^{n}-1}{w _{n} ^{k}-1}=\displaystyle\frac{exp[\displaystyle\frac{2 \pi i }{n}\cdot k\cdot n]-1}{w _{n} ^{k}-1}=\displaystyle\frac{1-1}{w _{n} ^{k}-1}=0$
• Halving Lemma
  - $(w _{n} ^{k}) ^{2}=w _{n} ^{2k}w _{n} ^{n}=(w _{n} ^{k+n/2}) ^{2}$
  

Ref3. coefficient 표현과 point-value 표현사이의 전환

• 용어
  - coefficient representation
  - $p(x)=\displaystyle\sum_{i=0}^{n}{a _{i}x ^{i}} \in \mathcal{P} _{n}(\mathbb{R})$ 을 $\beta=\{ x ^{n},x ^{n-1},\cdots,x _{1},1 \}$ 라 두고, $[p]_{\beta}=[a _{n},a _{n-1},\cdots,a _{0}]$ 로 표현하는 다항식의 표현방법이다
  - point-valued representation
  - $p(x)=\displaystyle\sum_{i=0}^{n}{a _{i}x ^{i}} \in \mathcal{P} _{n}(\mathbb{R})$ 을 $\{ x _{0},x _{1}, x _{2},\cdots,x _{n} \}\subset \mathbb{R}$ 에 대하여 ${p(x _{0}),p(x _{1}),\cdots,p(x _{n})}$ 의 값을 갖고 있어 다항식을 결졍하는, 다항식의 표현방법이다
• 주어진 $p(x)\in \mathcal{P}_{n}(\mathbb{F})$ 가 coefficient representation일 때, 이를 point-value representation으로 변환하는 과정을 evaluation 이라 부른다