소인수 알고리즘

1. 개요

소인수 알고리즘은 이산 푸리에 변환(DFT)을 계산하는 알고리즘으로, 신호의 길이가 서로소인 두 정수의 곱으로 표현될 때 입력과 출력을 재색인화하여 다차원 DFT로 변환한다. 굿스 매핑과 CRT 매핑을 사용하여 DFT의 입력 및 출력 색인을 재지정하며, 이를 통해 회전자(twiddle factor)를 단순화하여 계산 효율성을 높인다. 최종적으로 2차원 DFT로 재표현되며, 고속 푸리에 변환(FFT)과 비교하여 회전자가 생략되는 특징을 가진다.

2. 알고리즘

신호의 길이가 N일 때 이산 푸리에 변환(DFT)은 다음과 같이 정의된다.

:$f\_k\; =\; \backslash sum\_\{n=0\}^\{N-1\}\; x\_n\; e^\{-\backslash frac\{2\backslash pi\; i\}\{N\}\; nk\; \}\; =\; \backslash sum\_\{n=0\}^\{N-1\}\; x\_n\; W\_N^\{\; nk\; \}$
\qquad
k = 0,\dots,N-2,N-1 \qquad \qquad \qquad (1)

N이 서로소인 두 정수 r과 s의 곱(N = rs)으로 표현될 때, DFT를 r X s 크기의 2차원 DFT로 변환할 수 있다. 이를 다중차원 사상(multi-dimensional mapping)이라고 한다. 입력 및 출력은 재색인화(re-indexing)하여 변환하며, 정수론을 이용하여 DFT의 입력 및 출력 색인을 재지정하는 방법으로는 굿스 매핑(Good's mapping)과 중국인의 나머지 정리를 이용한 CRT 매핑(CRT mapping)이 있다. 굿스 매핑은 입력 색인 n을, CRT 매핑은 출력 색인 k를 재지정하는 데 사용된다.

2.1. 색인 재지정(re-indexing)

정수론의 이론을 이용하여 이산 푸리에 변환(DFT)의 입력 및 출력 색인을 재지정하는 두 가지 방법은 다음과 같다.

* [[굿-토마스 소인수 분해 알고리즘|굿스 매핑(Good's mapping)]]: DFT의 입력 쪽 색인 n을 나타내는 방법이다.
* CRT 매핑(CRT mapping): DFT의 출력 쪽 색인 k를 중국인의 나머지 정리를 통해 나타내는 방법이다.

r 과 s 가 '서로 소'이기 때문에, DFT의 입력 n과 출력 k를 위와 같이 나타낼 수 있다. 또한, 입력 n을 CRT 매핑하고 출력 k를 굿스 매핑하는 것도 가능하다.

2.1.1. 굿스 매핑(Good's mapping)

굿스 매핑은 DFT의 입력 쪽 색인 n을 나타내는 방법이다.

:$n\; =\; (n\_1,\; n\_0)\; \backslash equiv\; (\; s\; n\_0+r\; n\_1)\; \backslash bmod\; N\; \backslash qquad(0\; \backslash leq\; n\_0\; \backslash leq\; r\; -1,\; \backslash quad\; 0\; \backslash leq\; n\_1\; \backslash leq\; s\; -1)\; \backslash qquad\; \backslash qquad\; \backslash qquad\; (2)$

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

2.1.2. CRT 매핑(CRT mapping)

중국인의 나머지 정리(CRT)에 따르면 모든 쌍 (k₁, k₂)에 대해 다음 두 방정식을 만족하는 0과 N-1 사이에 고유한 k가 존재한다.

:$k\; \backslash equiv\; k\_0\; \backslash bmod\; r\; \backslash qquad(0\; \backslash leq\; k\_0\; \backslash leq\; r\; -1)$
:$k\; \backslash equiv\; k\_1\; \backslash bmod\; s\; \backslash qquad(0\; \backslash leq\; k\_1\; \backslash leq\; s\; -1)\; \backslash qquad\; \backslash qquad\; \backslash qquad\; (3)$

이를 CRT 매핑이라고 하며, (식 3)을 표현하는 또 다른 방법은 다음과 같다.

:$k\; =\; (k\_1,\; k\_0)\; \backslash equiv\; [\; s(\; s^\{-1\}\; \backslash bmod\; r)\; k\_0\; +\; r(\; r^\{-1\}\; \backslash bmod\; s)\; k\_1\; ]\; \backslash bmod\; N\; \backslash qquad\; \backslash qquad\; \backslash qquad\; (4)$

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

2.2. 재표현(re-expression)

신호의 길이가 N = r s이고, r과 s가 서로소인 두 정수일 때, 입력과 출력을 재색인화(re-indexing)하여 이산 푸리에 변환(DFT) 공식을 2차원 형태로 변환할 수 있다. 이를 다중차원 사상(multi-dimensional mapping)이라고 한다.

재지정된 색인을 DFT 공식에 대입하면 회전자(twiddle factor)는 다음과 같은 형태를 가진다.

:$W\_\{rs\}^\{(\; s\; n\_0+r\; n\_1)\; \backslash bmod\; N\; [s(\; s^\{-1\}\; \backslash bmod\; r)\; k\_0\; +\; r(\; r^\{-1\}\; \backslash bmod\; s)\; k\_1]\; \backslash bmod\; N\}$

회전자 자체가 mod N의 성질을 가지므로 지수(exponent)에 나타나는 mod N은 생략할 수 있다. 또한, 어떤 임의의 수 m에 대해 $W\_\{rs\}^\{mrs\}\; =\; 1$이므로 윗 식 지수항의 두 번째, 세 번째 항은 생략할 수 있다. r과 s는 '서로 소'이므로 각각의 역수 $r^\{-1\},\; s^\{-1\}$이 존재하며 $ss^\{-1\}\; \backslash equiv\; 1\; \backslash bmod\; r\; ,\; \backslash quad\; rr^\{-1\}\; \backslash equiv\; 1\; \backslash bmod\; s$ 이기 때문에, 최종적으로 회전자는 다음과 같이 정리된다.

:$W\_r^\{n\_0\; k\_0\}\; W\_s^\{\; n\_1\; k\_1\}$ $\backslash qquad\backslash qquad(5)$

결과적으로 DFT는 다음과 같이 2차원으로 재표현된다.

:$f(k\_1,\; k\_0)=\backslash sum\_\{n\_1=0\}^\{s-1\}\; \backslash sum\_\{n\_0=0\}^\{r-1\}\; x(n\_1,n\_0)W\_r^\{n\_0\; k\_0\}\; W\_s^\{\; n\_1\; k\_1\}\backslash qquad\backslash qquad(6)$

이 식은 고속 푸리에 변환의 혼합 기수(mixed-radix) FFT 식과 비교했을 때, 혼합 기수 FFT 식에서 보이는 회전자 $W\_\{N\_1N\_2\}^\{k\_1n\_2\}$가 생략된 형태임을 알 수 있다.

3. 예제

r=3, s=4 인 신호에 소인수 FFT를 적용하는 예제를 살펴보자. 이 경우, 1차원 신호 데이터 x(n)은 다음과 같이 2차원 배열 x(n₁, n₀)으로 변환된다.

:$n\; =\; (n\_1,\; n\_0)\; \backslash equiv\; (\; 4\; n\_0+3\; n\_1)\; \backslash bmod\; 12\; \backslash qquad(0\; \backslash leq\; n\_0\; \backslash leq\; 2,\; \backslash quad\; 0\; \backslash leq\; n\_1\; \backslash leq\; 3)$

여기서 n₀는 0부터 2까지, n₁은 0부터 3까지의 값을 가진다.

그리고 다음 식이 성립한다.

:$(r\; r^\{-1\}\; \backslash bmod\; s)\; =(\; 3\; 3^\{-1\}\; \backslash bmod\; 4)\; =\; 9,\; \backslash qquad\; (s\; s^\{-1\}\; \backslash bmod\; r)\; =(4\; 4^\{-1\}\backslash bmod\; 3\; )=\; 4$

따라서 k는 다음과 같이 계산된다.

:$k\; =\; (k\_1,\; k\_0)\; \backslash equiv\; (\; 4\; k\_0\; +\; 9\; k\_1\; )\; \backslash bmod\; 12\; \backslash qquad(0\; \backslash leq\; k\_0\; \backslash leq\; 2,\; \backslash quad\; 0\; \backslash leq\; k\_1\; \backslash leq\; 3)$

여기서 k₀는 0부터 2까지, k₁은 0부터 3까지의 값을 가진다.

(식 6)은 다음과 같다.

:$f(k\_1,\; k\_0)=\backslash sum\_\{n\_1=0\}^\{3\}\backslash sum\_\{n\_0=0\}^\{2\}\; x(n\_1,n\_0)W\_3^\{n\_0\; k\_0\}\; W\_4^\{\; n\_1\; k\_1\}$

이제, 1차원 신호 데이터가 Good's mapping을 통해 어떻게 2차원 배열로 변환되는지, 그리고 CRT mapping을 통해 주파수 영역의 데이터 f(k)가 어떻게 계산되는지 표를 통해 알아보자.

위 표들은 1차원 신호 데이터가 2차원 배열로 변환되고, 주파수 영역에서 다시 1차원 데이터로 재배열되는 과정을 보여준다. Good's mapping은 데이터를 2차원 배열로 변환하고, CRT mapping은 주파수 영역에서 데이터를 재배열하는 데 사용된다.