소인수 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 알고리즘
- 2.1. 색인 재지정(re-indexing)
  - 2.1.1. 굿스 매핑(Good's mapping)
  - 2.1.2. CRT 매핑(CRT mapping)
- 2.2. 재표현(re-expression)
3. 예제
참조

1. 개요

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

2. 알고리즘

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

: $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 }\qquadk = 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) \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)

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

2. 1. 2. CRT 매핑(CRT mapping)

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

:

k \equiv k_0 \bmod r  \qquad(0 \leq k_0 \leq r -1)

:

k \equiv k_1 \bmod s  \qquad(0 \leq k_1 \leq s -1) \qquad \qquad \qquad (3)

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

:

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)

''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) \bmod N [s( s^{-1} \bmod r)  k_0 +  r( r^{-1} \bmod s) k_1]  \bmod N}

회전자 자체가 ''mod N''의 성질을 가지므로 지수(exponent)에 나타나는 ''mod N''은 생략할 수 있다. 또한, 어떤 임의의 수 m에 대해

W_{rs}^{mrs} = 1

이므로 윗 식 지수항의 두 번째, 세 번째 항은 생략할 수 있다. r과 s는 '서로 소'이므로 각각의 역수

r^{-1}, s^{-1}

이 존재하며

ss^{-1} \equiv 1 \bmod r , \quad rr^{-1} \equiv 1 \bmod s

이기 때문에, 최종적으로 회전자는 다음과 같이 정리된다.

:

W_r^{n_0 k_0} W_s^{ n_1 k_1}

\qquad\qquad(5)

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

:

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)

이 식은 고속 푸리에 변환의 혼합 기수(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) \equiv ( 4 n_0+3 n_1) \bmod 12 \qquad(0 \leq n_0 \leq 2, \quad 0 \leq n_1 \leq 3)$

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

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

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

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

: $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)$

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

(식 6)은 다음과 같다.

: $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}$

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

1차원 신호 데이터 원본
n	0	1	2	3	4	5	6	7	8	9	10	11
x_n	x₀	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁

Good's mapping
x(n₁,n₀)		n₀
x(n₁,n₀)		0	1	2
n₁	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)

CRT mapping
f(k₁,k₀)		k₀
f(k₁,k₀)		0	1	2
k₁	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)

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

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com