이산 푸리에 변환(일반)

Discrete Fourier transform (general)

수학에서 임의의 링 에 놓인 이산 푸리에 변환은 값이 복잡한 함수의 이산 푸리에 변환을 일반화한다.

정의

을(를) 임의의 링으로 하고 {1 {\ n 1을(를) 정수로 하고, α R {\in R}을(를) 통일의 주요 n번째 루트로 하며,[1] 다음과 같이 정의한다.

The discrete Fourier transform maps an n-tuple of elements of to another n-tuple of elements of according to the following formula:

관례상 튜플 ,, - 1) 시간 영역에 있다고 하며 j 시간이라고 한다. 튜플 ,… , - ) 주파수 영역에 있다고 하며 k 주파수라고 한다. tuple( 0, …, n - ){\의 스펙트럼이라고도 한다 ( ,… ,v - ) 이 용어는 신호 처리에서 푸리에 변환의 적용에서 유래한다.

(필드 포함) 통합 도메인인 경우, 조건 (1)을 같이 하는 원시 n번째 통합 루트로 {\displaystyle \alpha 을(를) 선택하는 것으로 충분하다.[1]

\cHB 1 k <

증명: = = 1< 1 k 왜냐하면 = n = 1\displaystypa 제공:

합이 (1)과 일치하는 경우. (는) 통합의 원시 루트인 0{\ 0이므로 (는) 통합 도메인이므로 합계는 0이어야 한다.

n이 2의 검정력인 경우 다른 간단한 조건이 적용된다. (1)은 /= - ^{로 대체될 수 있다[1]

반비례

이산 푸리에 변환의 역은 다음과 같이 주어진다.

/ n (는) 에서 의 승법 역이다(이 역이 존재하지 않으면 DFT를 반전할 수 없음).

증거: (2)를 (3)의 우측으로 대체하면, 우리는 다음을 얻는다.

This is exactly equal to , because when (by (1) with ), and 일 때 j = j }.

행렬식

이산 푸리에 변환은 선형 연산자이기 때문에 행렬 곱셈으로 설명할 수 있다. 행렬 표기법에서 이산 푸리에 변환은 다음과 같이 표현된다.

이 변환의 행렬을 DFT 행렬이라고 한다.

마찬가지로 역 푸리에 변환에 대한 행렬 표기법은 다음과 같다.

다항식식[2]

때때로 공식 다항식을 가진 -tuple 0,, - 1) 을 식별하는 것이 편리하다.

이산 푸리에 변환(2)의 정의에 합계를 적음으로써 우리는 다음을 얻는다.

즉, {\는 x = x 대한 다항식 ) 의 값일 뿐이다

따라서 푸리에 변환은 계수와 다항식의 을 연관시키는 것으로 볼 수 있다: 계수는 시간 영역에 있고 값은 주파수 영역에 있다. 물론 여기서 다항식은 displaystyle n} th 뿌리의 α {\의 힘인 통합의 n에서 평가되는 것이 중요하다

마찬가지로 역 푸리에 변환(3)의 정의도 다음과 같이 쓸 수 있다.

와 함께

라는 뜻이다

이를 다음과 같이 요약할 수 있다: ( ) 의 값이 ( x) 계수 경우, ( ) 은 스칼라 인자까지( ) p(의 계수인자를 다시 정렬한다.

특례

콤플렉스

= (가) 복잡한 숫자의 필드라면, 단위의 n 뿌리를 복합면단위에서 점으로 시각화할 수 있다. 이 경우 대개는 한 사람이 복용한다.

복잡한 이산 푸리에 변환에 대한 일반적인 공식을 산출한다.

복잡한 숫자에 걸쳐, DFT 공식에 에 1 {1을(를) 사용하는 것이 아니라 두 공식에 스칼라 계수 1 {을(를) 사용하여 DFT와 역DFT 공식의 정규화를 수행하는 것이 관례인 경우가 많다.se DFT. 이 정규화와 함께 DFT 매트릭스는 단일화된다. 은(는) 임의 필드에서 의미가 없다는 점에 유의하십시오.

유한장

= ( ) 이( q {\ q(가) 원시 troot의 존재는 원소의 승법 순서- 나누어야 하기 때문에 자동으로 함을 의미한다e size of the multiplicative group of , which is . This in particular ensures that is invertible, so that the notation in (3) 말이 된다.

( 에 대한 이산 푸리에 변환의 적용은 코딩 이론에서 Reed-Solomon 코드BCH 코드로 줄이는 것이다. 그러한 변환은 예를 들어 사이클로토믹 고속 푸리에 변환과 같은 적절한 고속 알고리즘을 사용하여 효율적으로 수행될 수 있다.

숫자-이론적 변환

숫자-이론적 변환(NTT)[3]은 이산 푸리에 변환을 = / F 정수 modulo a p로 전문화하여 얻는다. 이것은 유한한 분야로 p - 을 나눌 때마다 원시적인 n번째 의 뿌리가 존재하기 때문에, 는 p= n + 양의 정수인 p = + 있다 구체적으로는 {\}을를) p- ) {\root of unity }을를) = =\ 로 하면 n번째 루트를 찾을 수 있다.

예: = = 2 }

= 4 인 경우

숫자 이론적 변환은 계수 m이 primary가 아닐 때에도, 순서 n의 기본 루트가 존재한다면 에서 의미가 있을 수 있다. schnhage-Strassen 알고리즘에서 사용되는 페르마트 수 변환(m = 2k+1)이나 메르센 수 변환[4](mk = 2 - 1)과 같은 숫자 이론 변환의 특별한 경우는 복합 계수를 사용한다.

이산 가중 변환

이산형 가중 변환(DWT)은 임의의 링에 대한 이산형 푸리에 변환에 대한 변화로, 입력에 가중치를 부여한 후, 원소를 가중 벡터로 곱한 다음 결과를 다른 벡터로 가중시킨다.[5] 비합리적인 기저 이산형 가중 변환은 특별한 경우다.

특성.

역변환, 콘볼루션 정리, 가장 빠른 푸리에 변환(FFT) 알고리즘 등 복합 DFT의 중요한 속성 대부분은 변환의 커널이 통합의 주요 근원이라는 속성에만 의존한다. 또한 이러한 속성은 동일한 증명으로 임의의 링 위에 고정된다. 필드의 경우, 확장 F . 에 대한 대수로서 통일의 원시 n번째 루트를 가진 모든 필드를 고려하여, 이 비유를 하나의 원소로 필드에서 공식화할 수 있다.[clarification needed]

특히 NTT동서를 하기 위한 ( n ){\\log n 고속 푸리에 변환 알고리즘의 적용가능성은, 컨볼루션 정리(convolution organization)와 결합해, 숫자-이론적 변환이 정수의 정확한 경합을 계산하는 효율적인 방법을 제공한다는 것을 의미한다. 복합 DFT는 동일한 작업을 수행할 수 있지만, 유한정밀 부동소수점 산술에서는 반올림 오차에 취약하다. NTT는 정확히 나타낼 수 있는 고정 크기 정수를 순수하게 다루기 때문에 반올림하지 않는다.

빠른 알고리즘

"빠른" 알고리즘의 구현(FFTDFT를 계산하는 방법과 유사)의 경우, 변환 길이도 높은 복합성(예: 2의 검정력)이 바람직할 경우가 많다. 단, 왕, 주 알고리즘 등 유한분야에 특화된 고속 푸리에 변환 알고리즘이 있어 변환 길이 인자에 관계없이 효율적이다.[6]

참고 항목

참조

  1. ^ a b c 마틴 퓨러, "더 빠른 정수 곱하기", STOC 2007 Procedures, 페이지 57–66. 섹션 2: 이산 푸리에 변환.
  2. ^ R. Lidl과 G. Pilz. 응용 추상 대수학, 제2판. 1999년 와일리, 페이지 217–219.
  3. ^ 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.
  4. ^ 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.
  5. ^ Crandall, Richard; Fagin, Barry (1994), "Discrete weighted transforms and large-integer arithmetic" (PDF), Mathematics of Computation, 62 (205): 305–324, doi:10.2307/2153411
  6. ^ Yao Wang과 Xuelong Zoo, "유한 분야에 대한 푸리에 변환과 VLSI 구현을 위한 빠른 알고리즘", IEEE Journal on Selected Area in Communications 6(3)572–577, 1988년)

외부 링크