이 기사는 한정된 필드 의 경우 일반적으로 숫자-테오틱 변환(NTT) 이라고 불리는 링 위 에 놓인 이산 푸리에 변환(DFT) 에 관한 것이다. 복잡한 숫자 에 대한 이산 푸리에 변환에 대한 자세한 내용은 이산 푸리에 변환 을 참조하십시오. 수학에서 임의의 링 위 에 놓인 이산 푸리에 변환 은 값이 복잡한 함수의 이산 푸리에 변환 을 일반화한다.
정의 R {\displaystyle R} 을(를) 임의 의 링으로 하고, n { 1 {\displaystyle n\geq 1} 을(를 ) 정수로 하고, α α \ R {\displaystyle \alpha \ in R}을(를) 통일의 주요 n번째 루트로 하며,[1] 다음과 같이 정의한다.
α n = 1 ∑ j = 0 n − 1 α j k = 0 을 위해 1 ≤ k < n ( 1 ) {\displaystyle {\regated}&#{n}=1\\&\sum _{j=0}^{n-1}\n-1}\cHB ^{jk}=0\text{{{{}}}{1}\leqk k<n\qquad(1)\end{arged}}}}}}}}}}}}}}}}}}}}}}}}}}}}" The discrete Fourier transform maps an n -tuple ( v 0 , … , v n − 1 ) {\displaystyle (v_{0},\ldots ,v_{n-1})} of elements of R {\displaystyle R} to another n -tuple ( f 0 , … , f n − 1 ) {\displaystyle (f_{0},\ldots ,f_{n-1})} of elements of R {\displaystyle R} according to the following formula:
f k = ∑ j = 0 n − 1 v j α j k . ( 2 ) {\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}\jput ^{jk}. \qquad (2)} 관례상 튜플(v 0 , … , v n - 1 ) {\displaystyle(v_{0},\ldots ,v_{n-1}) 은 시간 영역 에 있다고 하며 인덱스 j {\displaystyle j} 을 시간 이라고 한다. 튜플(f 0 , … , f n - 1 ) {\displaystyle(f_{0},\ldots,f_{n-1}}) 은 주파수 영역 에 있다고 하며 지수 k {\displaystyle k} 은 주파수 라고 한다. tuple (f 0 , … , f n - 1 ) {\displaystyle (f_{0},\ldots, f_ {n-1}) 의 스펙트럼이라고도 한다. (v 0 , … , v n - 1 ) {\displaystyle (v_{0},\ldots ,v_{n-1}. 이 용어는 신호 처리 에서 푸리에 변환의 적용에서 유래한다.
R {\displaystyle R} 이 (필드 포함) 통합 도메인 인 경우, 조건 (1)을 다음 과 같이 대체 하는 원시 n번째 통합 루트로 α {\displaystyle \alpha } 을(를) 선택하는 것으로 충분하다.[1]
αk ≠ 1 {\displaystyle \cHB \cHB ^{k}\neq 1}, 1 ≤ k <n {\ displaystyle 1\leq k<n} 증명: β = αk {\ displaystyle \beta =\alpha ^{k}, 1 αn = 1 1k <n {\displaystyle 1\\leq k<n }. 왜냐하면 αn = \ displaysty \ beta ^{n}= 1 }, β n = 1 \displaystypa \n} ^{k}=1 }, 제공:
β n − 1 = ( β − 1 ) ( ∑ j = 0 n − 1 β j ) = 0 {\displaystyle \property \{n1}-1=(\sum _{j=0}^{n-1}\properties ^{j}\right)=0} 합이 (1)과 일치하는 경우. α {\displaystyle \alpha } 은 (는) 통합의 원시 루트인 β - 1 0 0 {\displaystyle \beta -1\neq 0} 이므로, R {\displaystyle R} 은 (는) 통합 도메인이므로 합계는 0이어야 한다. ∎
n 이 2의 검정력인 경우 다른 간단한 조건이 적용된다. (1)은 αn / 2 = - 1 {\displaystyle \alpha ^{n/2}=-1} 로 대체될 수 있다. [1]
반비례 이산 푸리에 변환의 역은 다음과 같이 주어진다.
v j = 1 n ∑ k = 0 n − 1 f k α − j k . ( 3 ) {\displaystyle v_{j}={\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\cHB ^{-jk}. \qquad (3)} 여기 서 1 / n {\displaystyle 1/n} 은 (는) R {\displaystyle R} 에서 n {\displaystyle n} 의 승법 역이다( 이 역이 존재하지 않으면 DFT를 반전할 수 없음).
증거: (2)를 (3)의 우측으로 대체하면, 우리는 다음을 얻는다.
1 n ∑ k = 0 n − 1 f k α − j k = 1 n ∑ k = 0 n − 1 ∑ j ′ = 0 n − 1 v j ′ α j ′ k α − j k = 1 n ∑ j ′ = 0 n − 1 v j ′ ∑ k = 0 n − 1 α ( j ′ − j ) k . {\displaystyle {\begin{aligned}&{\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{k=0}^{n-1}\sum _{j'=0}^{n-1}v_{j'}\alpha ^{j'k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{j'=0}^{n-1}v_{j'}\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}. \end{정렬}}} This is exactly equal to v j {\displaystyle v_{j}} , because ∑ k = 0 n − 1 α ( j ′ − j ) k = 0 {\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=0} when j ′ ≠ j {\displaystyle j'\neq j} (by (1) with k = j ′ − j {\displaystyle k=j'-j} ), and ∑ k = 0 n − 1 α ( j ′ − j ) k = n {\dis 놀이 스타일 \sum _{k=0}^{n-1}\filename ^{(j'-j)k}=n} 일 때 j ′ = j {\displaystyle j'=j }. ∎
행렬식 이산 푸리에 변환은 선형 연산자 이기 때문에 행렬 곱셈 으로 설명할 수 있다. 행렬 표기법에서 이산 푸리에 변환은 다음과 같이 표현된다.
[ f 0 f 1 ⋮ f n − 1 ] = [ 1 1 1 ⋯ 1 1 α α 2 ⋯ α n − 1 1 α 2 α 4 ⋯ α 2 ( n − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 α n − 1 α 2 ( n − 1 ) ⋯ α ( n − 1 ) ( n − 1 ) ] [ v 0 v 1 ⋮ v n − 1 ] . {\displaystyle{\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}={\begin{bmatrix}1&, 1&, 1&, \cdots &, 1\\1&, \alpha&\alpha ^{2}&, \cdots &, \alpha ^{n-1}\\1&, \alpha ^{2}&, \alpha ^{4}&, \cdots, \alpha ^{2(n-1)}\\\vdots &, \vdots &, \vdots &, \ddots &, \vdots \\1& &, \alpha ^{n-1}&,\alpha ^{2(n-1).}&\cdots &, \alpha ^{(n-1)(n-1)}\\\end{bmatrix}}{\begin{bmatrix}v_{0}\\v_{ 1}\\\vdots \\\v_{n-1}\end{bmatrix}. } 이 변환의 행렬을 DFT 행렬 이라고 한다.
마찬가지로 역 푸리에 변환에 대한 행렬 표기법은 다음과 같다.
[ v 0 v 1 ⋮ v n − 1 ] = 1 n [ 1 1 1 ⋯ 1 1 α − 1 α − 2 ⋯ α − ( n − 1 ) 1 α − 2 α − 4 ⋯ α − 2 ( n − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 α − ( n − 1 ) α − 2 ( n − 1 ) ⋯ α − ( n − 1 ) ( n − 1 ) ] [ f 0 f 1 ⋮ f n − 1 ] . {\displaystyle{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}={\frac{1}{n}}{\begin{bmatrix}1&, 1&, 1&, \cdots &, 1\\1&, \alpha ^{)}&, \alpha ^{-2}&, \cdots &, \alpha ^{-(n-1)}\\1&, \alpha ^{-2}&, \alpha ^{-4가}&, \cdots, \alpha ^{-2(n-1)}\\\vdots, \vdots & &, \vdots &, \ddots &, \vdots \\1& &, \alpha. ^{-(n-1)}&, \alpha ^{-2(n-1)}&, \cdots &,\alpha ^{-(n-1)(n-1)}\end{bmatri x}{{{{bmatrix}f_{0}\\f_{1}\\\\vdots \\f_{n-1}\end{bmatrix}}. } 때때로 공식 다항식을 가진 n {\displaystyle n} -tuple(v 0 , … , v n - 1 ) {\displaystyle(v_{0},\ldots ,v_{n-1}) 을 식별하는 것이 편리하다.
p v ( x ) = v 0 + v 1 x + v 2 x 2 + ⋯ + v n − 1 x n − 1 . {\displaystyle p_{v}(x)=v_{0}+v_{1}x+v_{2 }x^{2}+\cdots +v_{n-1}x^{n-1}\,} 이산 푸리에 변환(2)의 정의에 합계를 적음으로써 우리는 다음을 얻는다.
f k = v 0 + v 1 α k + v 2 α 2 k + ⋯ + v n − 1 α ( n − 1 ) k . {\displaystyle f_{k}=v_{0}+v_{1}\n1}\cdots ^{2k}+v_{2}\cdots +v_{n-1}\cdots ^{{n-1)k}. \,} 즉, f k {\displaystyle f_{k}} 는 x = αk {\ displaystyle x=\alpha ^{k} 에 대한 다항식 p v (x ) {\displaystyp p_ {v}(x)} 의 값일 뿐이다.
f k = p v ( α k ) . {\displaystyle f_{k}=p_{v}(\cHB ^{k}). \,} 따라서 푸리에 변환은 계수 와 다항식의 값 을 연관시키는 것으로 볼 수 있다: 계수는 시간 영역에 있고 값은 주파수 영역에 있다. 물론 여기서 다항식은 α {\ displaystyle n} th 뿌리의 α {\displaystyle \alpha } 의 힘인 통합의 n {\displaystyle n} 에서 평가되는 것이 중요하다.
마찬가지로 역 푸리에 변환(3)의 정의도 다음과 같이 쓸 수 있다.
v j = 1 n ( f 0 + f 1 α − j + f 2 α − 2 j + ⋯ + f n − 1 α − ( n − 1 ) j ) . ( 5 ) {\displaystyle v_{j}={\frac {1}{n1}:{n}(f_{0}+f_{1}\n3}\cHB ^{-j}+f_{2}\cdots +{n-1}\cdots{f_{n-1}j}). \qquad (5)} 와 함께
p f ( x ) = f 0 + f 1 x + f 2 x 2 + ⋯ + f n − 1 x n − 1 , {\displaystyle p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1},} 라는 뜻이다
v j = 1 n p f ( α − j ) . {\displaystyle v_{j}={\frac {1}{n}p_{f}(\reason ^{-j}). } 이를 다음과 같이 요약할 수 있다: p ( x ) {\displaystyle p(x)} 의 값이 q ( x ) {\displaystyle q(x )} 의 계수 인 경우, q ( x ) {\displaystyle q(x)} 의 값 은 스칼라 인자까지 p ( x ) {\displaystylease p(x) 의 계수인자를 다시 정렬한다.
특례 콤플렉스 F = C {\ displaystyle F={\mathb{C}}}}}}}}} 이 (가) 복잡한 숫자의 필드라면, 단위 의 n {\displaystyle n} 뿌리를 복합면 의 단위 원 위 에서 점으로 시각화할 수 있다. 이 경우 대개는 한 사람이 복용한다.
α = e − 2 π i n , {\displaystyle \cHB =e^{\frac {-2\pi i}{n}},} 복잡한 이산 푸리에 변환 에 대한 일반적인 공식을 산출한다.
f k = ∑ j = 0 n − 1 v j e − 2 π i n j k . {\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}e^{\frac {-2\pi i}{n}jk}. } 복잡한 숫자에 걸쳐, DFT 공식에 1 {\displaystyle 1}, 공식 에 1 {\ displaystyle {1}{\sqrt{ n}} 을(를) 사용하는 것이 아니라 두 공식에 스칼라 계수 1 n {\displaystyle {n} 을(를) 사용하여 DFT와 역DFT 공식의 정규화를 수행하는 것이 관례인 경우가 많다. se DFT. 이 정규화와 함께 DFT 매트릭스는 단일화된다. n {\ displaystyle {\sqrt{n}} 은(는) 임의 필드에서 의미가 없다는 점에 유의하십시오.
유한장 F = G F ( q ) {\displaystyle q } 이(가 ) q {\displaystyle q} 이 (가) 원시 n {\ displaystyle n } troot의 존재는 각 원소의 승법 순서 가 q - 1 {\displaystyle q-1} 을 나누어야 하기 때문에 자동으로 함을 의미한다. e size of the multiplicative group of F {\displaystyle F} , which is q − 1 {\displaystyle q-1} . This in particular ensures that n = 1 + 1 + ⋯ + 1 ⏟ n t i m e s {\displaystyle n=\underbrace {1+1+\cdots +1} _{n\ {\rm {times}}}} is invertible, so that the notation 1 n {\displaystyle {\frac {1}{n}}} in (3) 말이 된다.
G F ( q ) {\displaystyle GF(q)} 에 대한 이산 푸리에 변환의 적용은 코딩 이론 에서 Reed-Solomon 코드 를 BCH 코드 로 줄이는 것이다. 그러한 변환은 예를 들어 사이클로토믹 고속 푸리에 변환 과 같은 적절한 고속 알고리즘을 사용하여 효율적으로 수행될 수 있다.
숫자-이론적 변환 숫자-이론적 변환( NTT) [3] 은 이산 푸리에 변환을 F = Z / p {\displaystyle F={\mathb {Z} }/p }, 정수 modulo a p 로 전문화하여 얻는다. 이것은 유한 한 분야로, n 이 p - 1 을 나눌 때마다 원시적인 n번째 통합 의 뿌리가 존재하기 때문에, 우리 는 p = + n + 1 을 양의 정수 인 p = ξ n + 1을 가지고 있다. 구체적으로는 Ω {\displaystyle \omega }을( 를) 원초적 ( p - 1 ) {\displaystyle(p-1) root of unity α {\displaystyle \alpha }을( 를) α = Ω {\ displaystystylepha =\xi } 로 하면 n번째 루트를 찾을 수 있다 .
예: p = 5 {\displaystyle p=5}, α = 2 {\displaystyle \cHB =2 }
2 1 = 2 ( 모드의 5 ) 2 2 = 4 ( 모드의 5 ) 2 3 = 3 ( 모드의 5 ) 2 4 = 1 ( 모드의 5 ) {\displaystyle {{\pmod{5}}{1}=2{\pmod{5}\\2^{2}=4}\pmod{5}\2^{3}&=3}{\pmod{5}\pmod{4}&=1}{pmod{5}}}}\pmod{5}}}}}\end}}}}}}}}}}}}. N = 4 {\displaystyle N=4} 인 경우
[ F ( 0 ) F ( 1 ) F ( 2 ) F ( 3 ) ] = [ 1 1 1 1 1 2 4 3 1 4 1 4 1 3 4 2 ] [ f ( 0 ) f ( 1 ) f ( 2 ) f ( 3 ) ] {\displaystyle {\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}} 숫자 이론적 변환은 계수 m 이 primary가 아닐 때에도, 순서 n 의 기본 루트가 존재한다면, 링 Z /m {\displaystyle \matcub {Z} /m} 에서 의미가 있을 수 있다. schnhage-Strassen 알고리즘 에서 사용되는 페르마트 수 변환(m = 2k +1 )이나 메르센 수 변환[4] (mk = 2 - 1 )과 같은 숫자 이론 변환의 특별한 경우는 복합 계수를 사용한다.
이산 가중 변환 이산형 가중 변환( DWT) 은 임의의 링에 대한 이산형 푸리에 변환에 대한 변화로, 입력에 가중치 를 부여한 후, 원소를 가중 벡터로 곱한 다음 결과를 다른 벡터로 가중시킨다.[5] 비합리적인 기저 이산형 가중 변환은 특별한 경우다.
특성. 역변환, 콘볼루션 정리 , 가장 빠른 푸리에 변환 (FFT) 알고리즘 등 복합 DFT 의 중요한 속성 대부분은 변환의 커널이 통합의 주요 근원이라는 속성에만 의존한다. 또한 이러한 속성은 동일한 증명으로 임의의 링 위에 고정된다. 필드의 경우, 확장 필드 F 1 n . {\displaystyle \mathbf {F} _{1^{n} 에 대한 대수로서 통일의 원시 n번째 루트를 가진 모든 필드를 고려하여, 이 비유를 하나의 원소로 필드 에서 공식화할 수 있다. } [clarification needed ]
특히, NTT동서를 계산 하기 위한 O (n log { n ){\displaystyle O(n \log n)} 고속 푸리에 변환 알고리즘의 적용가능성은, 컨볼루션 정리(convolution organization)와 결합해, 숫자-이론적 변환 이 정수의 정확한 경합 을 계산하는 효율적인 방법을 제공한다는 것을 의미한다. 복합 DFT는 동일한 작업을 수행할 수 있지만, 유한정밀 부동소수점 산술에서는 반올림 오차 에 취약하다. NTT는 정확히 나타낼 수 있는 고정 크기 정수를 순수하게 다루기 때문에 반올림하지 않는다.
빠른 알고리즘 "빠른" 알고리즘의 구현(FFT 가 DFT 를 계산하는 방법과 유사)의 경우, 변환 길이도 높은 복합성(예: 2 의 검정력)이 바람직할 경우가 많다. 단, 왕, 주 알고리즘 등 유한분야에 특화된 고속 푸리에 변환 알고리즘이 있어 변환 길이 인자에 관계없이 효율적이다.[6]
참고 항목
참조 ^ a b c 마틴 퓨러, "더 빠른 정수 곱하기 ", STOC 2007 Procedures, 페이지 57–66. 섹션 2: 이산 푸리에 변환. ^ R. Lidl과 G. Pilz. 응용 추상 대수학, 제2판. 1999년 와일리, 페이지 217–219. ^ Agarwal, R.; Burrus, C. (April 1974). "Fast Convolution using fermat number transforms with applications to digital filtering" . IEEE Transactions on Acoustics, Speech, and Signal Processing . 22 (2): 87–97. doi :10.1109/TASSP.1974.1162555 . ISSN 0096-3518 . ^ Rader, C.M. (December 1972). "Discrete Convolutions via Mersenne Transrorms" . IEEE Transactions on Computers . C-21 (12): 1269–1273. doi :10.1109/T-C.1972.223497 . ISSN 0018-9340 . ^ Crandall, Richard; Fagin, Barry (1994), "Discrete weighted transforms and large-integer arithmetic" (PDF) , Mathematics of Computation , 62 (205): 305–324, doi :10.2307/2153411 ^ Yao Wang 과 Xuelong Zoo, "유한 분야에 대한 푸리에 변환과 VLSI 구현을 위한 빠른 알고리즘", IEEE Journal on Selected Area in Communications 6(3)572–577, 1988년) 외부 링크