소인수 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
'''소인수 FFT 알고리즘(Prime-factor FFT algorithm)'''이라고도 칭하며, 발견자의 이름을 사용해 '''Good–Thomas algorithm'''(1958/1963)으로도 불리는 '''소인수 알고리즘(Prime-factor Algorithm, PFA)'''은 [[중국인의 나머지 정리]](Chinese Reminder Theorem, CRT)를 활용한 [[고속 푸리에 변환]](FFT) 알고리즘이다. 이 알고리즘은 크기 ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub>인 신호를 2차원 [[이산 푸리에 변환]](DFT) ''N'' = ''N''<sub>1</sub>'' X N''<sub>2</sub> 로 재표현(re-expression)한다. 다만, 여기서 ''N''<sub>1</sub>과 ''N''<sub>2</sub>는 [[서로소 아이디얼|서로소]](relatively prime), 즉 gcd(''N''<sub>1</sub>, ''N''<sub>2</sub>)=1이어야 한다.

이 알고리즘의 장점은 
# 회전자(twiddle factor)에 의한 곱셈 연산(multiplication)이 불필요하다. 따라서, 처리 속도가 빠르다.
# 변환의 in-place, in-order version을 구현하는 것이 가능하다. 즉, 변환된 값들은 메모리에서 입력값들을 바꾼다. 그리고 입력값들이 시간순서일때 출력은 주파수 순서이다.
단점은
# 앞서 언급한 것처럼 ''N''<sub>1</sub>과 ''N''<sub>2</sub>는 '서로 소'이어야한다.
# 중국인의 나머지 정리(CRT)를 사용하기때문에 더 복잡한 색인 재지정(re-indexing)을 수행해야한다.


소인수 알고리즘은 쿨리-튜키 알고리즘의 일반적 형태인 혼합기수(mixed-radix)알고리즘과 결합하여 사용할 수 있어서, 위에서 언급한 특별한 경우만이 아닌 임의의 크기 N 에도 적용할 수 있다. 데이터 크기 N=1000인 경우에 처리 예를 다음 그림에서 보여준다.
[[파일:Combination of CT FFT and GT FFT algorithms.png|대체글=Combination of FFT algorithms using Good-Thomas algorithm and mixed-radix Cooley-Tukey algorithm.|섬네일|318x318픽셀|Good-Thomas 알고리즘과 혼합기수 Cooley-Tukey 알고리즘을 이용한 데이터 수 N=1000의 FFT 처리 방식.]]

== 알고리즘 ==

신호의 길이가 ''N''일 때 [[이산 푸리에 변환]](DFT)은 

:<math>f_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk } = \sum_{n=0}^{N-1} x_n W_N^{ nk }
\qquad
k = 0,\dots,N-2,N-1  \qquad \qquad \qquad (1) </math>

신호의 길이가 ''N'' = ''r s''인 경우를 생각해 봅니다. ''r'' 과 ''s''는 [[서로소 아이디얼|서로소]]인 두 정수이다(위에서 언급한 ''N''<sub>1</sub>'', N''<sub>2</sub>에 해당).
입력과 출력을 재색인화(re-indexing)하고 이를 DFT 공식에 대입하여 크기가 ''r'' X ''s''인 2차원 DFT로 변환해 보자. 
이와같이 일차원 DFT를 다차원으로 변환하는 것을 다중차원 사상(multi-dimensional mapping) 이라고 한다.

=== 색인 재지정(re-indexing) ===
정수론의 이론을 이용하여 (식 1) DFT의 입력 쪽 색인 ''n''과 출력 쪽 색인 ''k''를 다음과 같이 나타낼 수 있다.

1) 굿스 매핑(Good's mapping)
:<math>n = (n_1, n_0) \equiv s n_0+r n_1 (\bmod N)   \qquad(0 \leq n_0 \leq r -1, \quad 0 \leq n_1 \leq s -1) \qquad \qquad \qquad (2)</math>

최대공약수 표현 정리에 의하면 각 n에 대해 위 식을 만족하는 정수 ''n''<sub>1</sub>과 ''n''<sub>2</sub>가 있고, 합동이론에 따라 위의 식을 만족하고 위의 범위에 속하는 정수 ''n''<sub>1</sub>과 ''n''<sub>2</sub>가 유일하다는 것을 쉽게 알 수 있다. 이를 루리타니안 매핑(Ruritanian mapping) 또는 굿스 매핑(Good's mapping)이라 한다.

2) CRT 매핑(CRT mapping)
:<math>k \equiv k_0 (\bmod r)  \qquad(0 \leq k_0 \leq r -1)</math> 
:<math>k \equiv k_1 (\bmod s)  \qquad(0 \leq k_1 \leq s -1) \qquad \qquad \qquad (3)</math>
 
[[중국인의 나머지 정리]](CRT)에 따르면 모든 쌍 (k<sub>1</sub>, k<sub>2</sub>)에 대해  (식 3)의 두 방정식을 만족하는 ''0'' 과 ''N-1'' 사이에 고유한 k가 존재한다. 이를 CRT 매핑이라고 하며, 이를 수식으로 표현하면 다음과 같다.

:<math>k = (k_1, k_0) \equiv [s s^{-1} (\bmod r)  k_0 +  r r^{-1} (\bmod s) k_1] \bmod N  \qquad \qquad \qquad (4)</math>


''n''과 ''k''를 위와 같이 (식 3)과 (식 4)로 나타낼 수 있는 이유는''r'' 과 ''s'' 가 '서로 소'이기 때문이다. 위의 전개와는 반대로 입력 ''n''을 CRT 매핑하고 출력 ''k''를 Good's 매핑 할 수도 있다.

=== 재표현(re-expression) ===
위의 두 식 (식 2)와 (식 4)를  (식 1)에 대입하면 식의 회전자(twiddle factor)는 다음 (식 5)와 같은 형태를 가지게 된다.
 
:<big><math> W_{rs}^{ [s n_0+r n_1]\bmod N [s s^{-1} (\bmod r)  k_0 +  r r^{-1} (\bmod s) k_1] \bmod N }</math></big>
회전자 자체가 ''mod N'' 의 성질을 가지고 있으므로 지수(exponent)에 나타나는 ''mod N'' 은 생략할 수 있다. 즉, 
:<big><math>= W_{rs}^{[s n_0+r n_1][s s^{-1} (\bmod r) k_0 + r r^{-1}(\bmod s) k_1]}</math></big>
:<big><math>= W_{rs}^{ s n_0 s s^{-1} (\bmod r) k_0 + s n_0 r r^{-1} (\bmod s) k_1 + r n_1 s s^{-1} (\bmod r) k_0 + r n_1 r r^{-1} (\bmod s) k_1 } </math></big>
어떤 임의의 수 m에 대해 <math> W_{rs}^{mrs} = 1 </math> 이므로 윗 식 지수항의 두번째, 세번째 항은 생략 할 수 있다.
:<big><math>= W_{rs}^{ s n_0 s s^{-1} (\bmod r) k_0 + r n_1 r r^{-1} (\bmod s) k_1} </math> </big>
:<big><math>= W_r^{ n_0 s s^{-1} (\bmod r) k_0} W_s^{ n_1 r r^{-1} (\bmod s) k_1}  </math></big>
r과 s는 '서로 소'이므로 각각의 역수 <math> r^{-1}, s^{-1} </math> 이 존재하며 <math> ss^{-1} \equiv 1 \bmod r , \quad rr^{-1} \equiv 1 \bmod s </math> 이기 때문에, 윗식의 <math>  W_r^{s s^{-1} \bmod r } = W_r^{1}, \quad W_s^{ rr^{-1} \bmod s } =W_s^{1}</math></big> 이다. 따라서,
:<big><math>= W_r^{n_0 k_0} W_s^{ n_1 k_1} </math></big> <math> \qquad\qquad(5)   </math>   


(식 2),(식 4), (식 5)로부터 (식 1)의 이산 푸리에 변환(DFT)은 최종적으로 다음과 같이 2차원으로 재표현된다.
:<math>f(k_1, k_0)=\sum_{n_1=0}^{s-1} \sum_{n_0=0}^{r-1} x(n_1,n_0)W_r^{n_0 k_0} W_s^{ n_1 k_1}\qquad\qquad(6)</math>

[[고속 푸리에 변환]] 위키 페이지에서 볼 수 있는 혼합 기수(mixed-radix) FFT의 다음(식 20)의 회전자 <math>W_{N_1N_2}^{k_1n_2}</math>가 위의 (식 6)에서는 생략된 것을 확인할 수 있다. 
:<math>H(k_1, k_2)=\sum_{n_1=0}^{N_1-1}W_{N_1N_2}^{k_1n_2}\Biggl[ \sum_{n_2=0}^{N_2-1} h(n_1,n_2) W_{N_2}^{k_2n_2}\Biggr] W_{N_1}^{k_1n_1}</math>
:<math>=\sum_{n_1=0}^{N_1-1}W_{N_1N_2}^{k_1n_2} h^'(n_1,n_2) W_{N_1}^{k_1n_1}\qquad\qquad(20)</math>

== 예제 ==

''r=3, s=4'' 인 신호의   소인수 FFT 를 적용해보자. 이 경우 (식 2)는
:<math>n = (n_1, n_0) \equiv  4 n_0+3 n_1 (\bmod 12)   \qquad(0 \leq n_0 \leq 2, \quad 0 \leq n_1 \leq 3) </math>

이며, (식 4)에서 <math> r r^{-1} (\bmod s) = 3 3^{-1} (\bmod 4) = 9, \qquad s s^{-1} (\bmod r)  =4 4^{-1}(\bmod 3 )= 4 </math> 가 성립하므로 ''k'' 는
:<math>k = (k_1, k_0) \equiv  4  k_0 +  9 k_1 (\bmod 12)  \qquad(0 \leq k_0 \leq 2, \quad 0 \leq k_1 \leq 3) </math>

이 된다. (식 6)은 

:<math> f(k_1, k_0)=\sum_{n_1=0}^{3}\sum_{n_0=0}^{2} x(n_1,n_0)W_3^{n_0 k_0} W_4^{ n_1 k_1} </math>

그럼 <math> (n_1, n_0)</math>이 변함에 따라 <math>x(n)=x(n_1, n_0) </math>이 어떻게 2차원 도표로 변하는 지,  <math>(k_1, k_0)</math>에 따라 <math>f(k)=f(k_1, k_0)   </math> 는 어떻게 되는 지를 표로 만들어 보자.    

{| class="wikitable"
|+1차원 신호 데이터 원본
!n
!0
!1
!2
!3
!4
!5
!6
!7
!8
!9
!10
!11
|-
!x<sub>n</sub>
!x<sub>0</sub>
!x<sub>1</sub>
!x<sub>2</sub>
!x<sub>3</sub>
!x<sub>4</sub>
!x<sub>5</sub>
!x<sub>6</sub>
!x<sub>7</sub>
!x<sub>8</sub>
!x<sub>9</sub>
!x<sub>10</sub>
!x<sub>11</sub>
|}
{| class="wikitable"
|+Good's mapping
! colspan="2" rowspan="2" |x(n<sub>1</sub>,n<sub>0</sub>)
! colspan="3" |n<sub>0</sub>
|-
!0
!1
!2
|-
! rowspan="4" |n<sub>1</sub>
!0
!x(0)
!x(4)
!x(8)
|-
!1
!x(3)
!x(7)
!x(11)
|-
!2
!x(6)
!x(10)
!x(2)
|-
!3
!x(9)
!x(1)
!x(5)
|}
{| class="wikitable"
|+CRT mapping
! colspan="2" rowspan="2" |f(k<sub>1</sub>,k<sub>0</sub>)
! colspan="3" |k<sub>0</sub>
|-
!0
!1
!2
|-
! rowspan="4" |k<sub>1</sub>
!0
!f(0)
!f(4)
!f(8)
|-
!1
!f(9)
!f(1)
!f(5)
|-
!2
!f(6)
!f(10)
!f(2)
|-
!3
!f(3)
!f(7)
!f(11)
|}
[[분류:물리학]]
[[분류:이산수학]]
[[분류:디지털 신호 처리]]
[[분류:푸리에 해석학]]
[[분류:고속 푸리에 변환]]
[[분류:FFT]]