고속 푸리에 변환
공통인수 FFT(Common-Factor FFT) > 이론

식(5)에서 DFT는 푸리에 행렬 T와 벡터 x, f 로서 표현됨을 알았다. 즉
f=Tx
T의 행렬요소는  t_{jk}=e^{(i2\pi jk/n)}이다.
신호수가 합성수 N이며, 다음과 같은 m개의 인수로 분해(decomposition)될 때
N=\prod _{i=1}^{m}N_{i}
이고, N X N 행렬 T 는 다음과 같이 행렬곱으로 표현된다.
T=PF_{m}F_{m-1}F....F_{2}F_{1}
여기서, P는 치환행렬(permutation matrix), Fi는 n의 계수 ni에 해당하는 변환 단계(transform step) 행렬이다.
행렬 Fi는 각 행과 열에 ni개의 0이 아닌 요소만 있고 차원 ni의 n/ni 개의 square 부분행렬(submatrix)들로 분할될 수 있다. FFT 알고리즘의 기초가 되는 것이 바로 이 분할과 그에 따른 곱셈의 감소이다. 행렬 Fi는 다음과 같이 더 분해될 수 있다.
F_{i}=R_{i}T_{i}
여기서 Ri는 회전자의 대각행렬이고 Ti는 ni 개의 동일한 square 부분행렬로 분할될 수 있으며 각 행렬은 차원 ni의 복소 푸리에 변환이다.
신호의 길이가 합성수 N=N1N2 이라고 하자.  두 수의 곱으로 표현되므로 m=2 인 경우에 해당한다. 이 신호의 DFT는 식(2)로부터
f_{k}=\sum _{n=0}^{N_{1}N_{2}-1}x_{n}W_{N_{1}N_{2}}^{kn}\qquad \qquad k=0,\dots ,N-1\qquad \qquad \qquad (16)
신호 x 를 N1 x N2  이차원 배열로 재배치하는 것을 생각해 볼 수 있다.
N1 =3, N2 =8 인 신호를 고려하자.
h={\begin{bmatrix}x_{0}&x_{1}&x_{2}&x_{3}&x_{4}&x_{5}&x_{6}&x_{7}\\x_{8}&x_{9}&x_{10}&x_{11}&x_{12}&x_{13}&x_{14}&x_{15}\\x_{16}&x_{17}&x_{18}&x_{19}&x_{20}&x_{21}&x_{22}&x_{23}\\\end{bmatrix}}\qquad \qquad \qquad (17)
으로 간주한다.  n_{1},n_{2} 를 각각 위 (17)식 h의 행 번호, 열 번호,  k_{1},k_{2} 를 각각 아래 (18)식 H의 행 번호, 열 번호이라 할 때,
 n=n_{1}N_{2}+n_{2},\quad k=k_{2}N_{1}+k_{1} 이라 하자. 그러면, 위의 이차원 배열을
h(n_{1},n_{2})=x(n_{1}N_{2}+n_{2})=x_{n}\qquad (0\leq n_{1}\leq N_{1}-1,\quad 0\leq n_{2}\leq N_{2}-1)
와 같이 쓸 수 있다.  배열 h 에 대응하는 DFT는
H(k_{1},k_{2})=f(k_{2}N_{1}+k_{1})=f_{k}\qquad (0\leq k_{1}\leq N_{1}-1,\quad 0\leq k_{2}\leq N_{2}-1)
을 생각할 수 있다.  위의 DFT를 이차원 배열로 나타내면
H={\begin{bmatrix}f_{0}&f_{3}&f_{6}&f_{9}&f_{12}&f_{15}&f_{18}&f_{21}\\f_{1}&f_{4}&f_{7}&f_{10}&f_{13}&f_{16}&f_{19}&f_{22}\\f_{2}&f_{5}&f_{8}&f_{11}&f_{14}&f_{17}&f_{20}&f_{23}\\\end{bmatrix}}\qquad \qquad \qquad (18)
두 이차원 배열을 구성한 순서가 (17)식은 행우선순서(row-major order), 출력에 해당하는 (18)식은 열우선순서(column-major order)로 다름을 알 수 있고 이를 전치(transpose)되었다고 한다.
이러한 모든 전치의 최종 결과는 입력(DIF) 또는 출력(DIT) 인덱스의 비트 반전에 해당한다. 그 이유는 잠시 뒤 명확해 질 것이다.
그 전에 위에 언급한  n_{1},n_{2}의 범위로부터 (16)식과 같이  n의 범위가   0\leq n\leq N_{1}N_{2}-1 이 되는 지 확인해 보자.
<증명>
n=n_{1}N_{2}+n_{2} 이라할 때
n의 최소값은  n_{1}=n_{2}=0 일 때   n=0이며,
n의 최대값은  n_{1}=N_{1}-1\quad and\quad n_{2}=N_{2}-1 일 때 이므로
n=n_{1}N_{2}+n_{2}=(N_{1}-1)N_{2}+(N_{2}-1)=N_{1}N_{2}-1\quad 이다.
따라서  0\leq n\leq N_{1}N_{2}-1이다.  <증명 끝>
이제 원래의 DFT (16)식을 다음과 같이 쓸 수 있다.
H(k_{1},k_{2})=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}h(n_{1},n_{2})W_{N_{1}N_{2}}^{(k_{2}N_{1}+k_{1})(n_{1}N_{2}+n_{2})}
=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}h(n_{1},n_{2})W_{N_{1}N_{2}}^{k_{2}n_{1}N_{1}N_{2}}W_{N_{1}}^{k_{1}n_{1}}W_{N_{2}}^{k_{2}n_{2}}W_{N_{1}N_{2}}^{k_{1}n_{2}}
=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}h(n_{1},n_{2})W_{N_{1}}^{k_{1}n_{1}}W_{N_{2}}^{k_{2}n_{2}}W_{N_{1}N_{2}}^{k_{1}n_{2}}\quad (\because \ \ W_{N_{1}N_{2}}^{k_{2}n_{1}N_{1}N_{2}}=e^{-2\pi i(k_{2}n_{1})}=1)\qquad (19)
윗 식 세 개의 회전자 곱에서 처음 두 회전자들 때문에 이차원 DFT를 연상하게 한다. 마지막 회전자는 이들 전체 이차원 DFT에 대한 일종의 회전자이다.   이 사실은 조금 전에 두 이차원 배열을 구성한 순서를 다르게 한 즉, 전치(transpose)를 만든 이유이다.
윗 식을 다시 쓰면
H(k_{1},k_{2})=\sum _{n_{1}=0}^{N_{1}-1}W_{N_{1}N_{2}}^{k_{1}n_{2}}{\Biggl [}\sum _{n_{2}=0}^{N_{2}-1}h(n_{1},n_{2})W_{N_{2}}^{k_{2}n_{2}}{\Biggr ]}W_{N_{1}}^{k_{1}n_{1}}
괄호 안은 배열의 신호수  N_{2} 개의 각 열(column)에 대한 DFT이며, 이를  h^{'}(n_{1},n_{2}) 라 하자. 그러면,
H(k_{1},k_{2})=\sum _{n_{1}=0}^{N_{1}-1}W_{N_{1}N_{2}}^{k_{1}n_{2}}h^{'}(n_{1},n_{2})W_{N_{1}}^{k_{1}n_{1}}\qquad \qquad (20)
이는 먼저 회전자를 곱한 후에 계산한 신호수  N_{1} 개의 행들에 대한 DFT 식이다.  이것과 이차원 DFT와의 유일한 차이점은 회전자에 의한 추가적인 곱셈이 있다는 것이다.
만약 합성수였던 원래 신호의 길이 N=N1N2에서 N1 이나 N2가 다시 합성수라면, 분해(decomposition)의 기본 아이디어를 재귀적으로 적용한다. 이는 앞에서와 같이   N=\prod _{i=1}^{m}N_{i}=N_{1}N_{2}N_{3}....N_{m}으로의 일반화를 요구한다.
예)  N=N_{1}N_{2}\quad  →  \quad N=N_{1}N_{2}N_{3} 으로 변경된다면
이다.
지금까지의 과정을 단계별로 정리하면 다음과 같다.
1. N2 크기의 N1 DFT를 수행한다.
2. 회전자를 곱한다.
3. N1 크기의 N2 DFT를 수행한다.
일반적으로 N1 또는 N2는 기수이다. N1이 기수이면 DIT(Decimation in Time) 알고리즘이라고 하고, N2가 기수이면 DIF(Sande-Tukey 알고리즘이라고도 함)라고 한다.
과정의 역변환을 만드는 것은 그리 어렵지않다. 각 행의 IDFT(역이산 푸리에 변환)을 구한 다음, 결과 배열에 회전자의 공액(conjugate)을 곱한다. 마지막으로 각 열의 IDFT를 구한다.
예)  위 (16)식에서 본 길이 N=24인 신호의 이산 푸리에 변환을 생각해 보자.
f_{p}=\sum _{k=0}^{23}f(k)e^{{-i2\pi p \over 24}k}=\sum _{k=0}^{N-1}f(k)W_{24}^{pk}\qquad (0\leq p\leq 23)
위의 식을 다음과 같이 두 개의 12 point data blocks 으로 쓸 수 있다.
f_{p}=\sum _{m=0}^{1}\sum _{n=0}^{11}f(2n+m)W_{24}^{(2n+m)p}
또한 위의  12 point block을 두 개의 6 point  data blocks 으로 쓸 수 있다.
f_{p}=\sum _{s=0}^{1}\sum _{m=0}^{1}\sum _{n=0}^{5}f(4n+2m+s)W_{24}^{(4n+2m+s)p}
마지막으로 6 point block은 두 개의 3 point data blocks 으로 쓸 수 있다.
f_{p}=\sum _{t=0}^{1}\sum _{s=0}^{1}\sum _{m=0}^{1}\sum _{n=0}^{2}f(8n+4m+2s+t)W_{24}^{(8n+4m+2s+t)p}
위의 DFT가 바로 길이 24인 신호의 혼합 기수 FFT 알고리즘을 위한 식이다.  한 단계(stage)의 기수3 DFT와 세 단계의 기수2 DFT를 볼 수 있다.