이산 푸리에 변환

푸리에 변환
연속 푸리에 변환 푸리에 시리즈 이산 시간 푸리에 변환 이산 푸리에 변환 링 위의 이산 푸리에 변환 유한 그룹의 푸리에 변환 푸리에 분석 관련 변환

수학에서 이산 푸리에 변환(DFT)은 함수의 균일한 간격의 표본의 유한 순서를 이산 시간 푸리에 변환(DTFT)의 균일한 간격의 표본의 같은 길이 순서로 변환하는데, 이것은 주파수의 복합 값 함수다. DTFT를 샘플링하는 간격은 입력 시퀀스 지속시간의 역수 값이다. 역 DFT는 푸리에 시리즈로, 해당 DTFT 주파수에서 DTFT 샘플을 복합 사인파 계수로 사용한다. 그것은 원래 입력 순서와 동일한 샘플 값을 가지고 있다. 따라서 DFT는 원래 입력 시퀀스의 주파수 영역 표현이라고 한다. 원래 시퀀스가 함수의 0이 아닌 모든 값에 걸쳐 있는 경우, 함수의 DTFT는 연속(및 주기적)이며, DFT는 한 사이클의 이산형 샘플을 제공한다. 원래 시퀀스가 주기 함수의 한 사이클인 경우, DFT는 한 DTFT 사이클의 모든 0이 아닌 값을 제공한다.

DFT는 가장 중요한 이산형 변환으로, 많은 실제 애플리케이션에서 푸리에 분석을 수행하는 데 사용된다.^[1] 디지털 신호 처리에서 함수는 음파, 무선 신호 또는 일일 온도 판독의 압력과 같이 시간에 따라 변화하는 모든 수량 또는 신호로, 한정된 시간 간격(흔히 윈도우 함수에^[2] 의해 정의됨)에 걸쳐 샘플링된다. 이미지 처리에서 샘플은 래스터 이미지의 행이나 열을 따라 픽셀 값이 될 수 있다. 또한 DFT는 부분 미분 방정식을 효율적으로 해결하고, 경련이나 큰 정수를 곱하는 등의 다른 작업을 수행하는 데도 사용된다.

한정된 양의 데이터를 다루기 때문에 수치 알고리즘이나 전용 하드웨어에 의해 컴퓨터에 구현될 수 있다. 이러한 구현은 대개 효율적인 빠른 FFT(Fast Fourier Transform) 알고리즘을 사용한다.^[3] 그래서 "FFT"와 "DFT"라는 용어는 종종 서로 바꾸어 사용된다. 현재 사용 이전에 "FFT" 초기주의는 "완료형 푸리에 변환"이라는 모호한 용어에 사용되었을 수도 있다.

정의

이산 푸리에 변환은 일련의 N 콤플렉스 숫자${\displaystyle }${ x ${\displaystyle n{\mathbf{}}_{}{}_{}}$ := ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle N_{}}$- ${\displaystyle 1_{}}$ ${\$\{$x_{n}}}$ \$right\}:$$=x_{0},x_{1},\ldots,x_{N-1}$을(를) 다른$$ 복잡한 숫자의 순서로, {${\displaystyle X{\mathbf{}}_{}}$ ${\displaystyle {k\mathbf{}}_{}}$ ${\displaystyle \}}$ : = X ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {X\mathrm{}}_{}}$ 1${\displaystyle }$,${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{N}}_{}}$- 1${\displaystyle {}_{}}$, ${\displaystyle \left\{\mathbf{X_{k}}}}$ \$right\}:$$=X_{0},X_{1},\ldots,X_{N-1}}($으$$)로 정의됨

여기서 오일러의 공식으로 첫 번째 표현부터 마지막 표현이 뒤따른다.

로 X에서)F{)}{\displaystyle \mathbf{X}={{F\mathcal}}\left\{\mathbf{)}\right\}}또는 F({\displaystyle{{F\mathcal}}\left(\mathbf{x}\right)}또는 F){\displaystyle{{F\mathcal}}\mathbf{)}}그 변환은 때때로 상징 F{\displaystyle{{F\mathcal}에 의해}}, 표시됩니다.[A]

Eq.1은 또한 도메인 $k{\displaystyle }$ ${\displaystyle \in }$[ ${\displaystyle 0,}$ N${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle k\in [0,N-1]}$을(를) 벗어나서 평가할 수 있으며$,$ 확장 시퀀스는 $N{\displaystyle }$ ${\displaystyle$ N$}$ - periodic이다. Accordingly, other sequences of ${\displaystyle N}$ indices are sometimes used, such as ${\textstyle \left[-{\frac {N}{2}},{\frac {N}{2}}-1\right]}$ (if ${\displaystyle N}$ is even) and ${\textstyle \left[-{\frac {N-1}{2}},{\frac {N-1}{2}}\right]}$ ($N{\displaystyle }$ ${\displaystyle N}$이(가) 홀수인 경우) 이는 변환 결과의 왼쪽과 오른쪽 절반을 스와핑하는 양이다.^[4]

Eq.1은 다음과 같이 다양한 방법으로 해석하거나 도출할 수 있다.

DFT와 IDFT를 곱한 정규화 $($여기서 $1$과 1 N ${\textstyle {\frac$ {1}{N$\})$과 지수의 부호는 규약일 뿐이며 일부 치료법에서는 차이가 있다. The only requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be ${\textstyle {\frac {1}{N}}}$. A normalization of ${\textstyle {\sqrt {\frac {1}{N}}}}$ for both the DFT and IDFT, for instance, makes the transforms unitary. 이산 임펄스, ${\displaystyle x_{}}$ n${\displaystyle {}_{}}$= ${\displaystyle 1}$ ${\displaystyle x_{n}=1},$ 그렇지 않으면 모든 k에 $대해$ X ${\displaystyle k_{}}$= ${\displaystyle 1}$ ${\displaystyle X_{k}=1}$로 변환될 수 있음(DFT의 경우 정규화 계수 1 및 IDFT의 $\frac{\mathrm{경우}}{}$ 1 ${\textstyle {\1}{$1}{$N}).$ A DC signal, ${\displaystyle X_{k}=1}$ at k = 0 and 0 otherwise; might inversely transform to ${\displaystyle x_{n}=1}$ for all ${\displaystyle n}$ (use ${\textstyle {\frac {1}{N}}}$ for DFT and 1 for IDFT) which is consistent with viewing DC as the mean average of the signal.

예

${\displaystyle \mathrm{N}}$${\displaystyle }$= 4 ${\displaystyle N=4}$ 및

${\displaystyle \mathbf {x} ={\pmatrix}x_{0}\\x_{1}\x_{2}\x_{3}\end{pmatrix}}={\\nd{pmatrix}1\\\2-i\-1+2i\end{pmatrix}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

$여기$서는 Eq.1을 사용하여$$ x ${\$의 DFT를 계산하는 방법을 설명한다.

${\displaystyle X_{0}=e^{-i2\pi 0\cdot 0/4}\cdot 1+e^{-i2\pi 0\cdot 1/4}\cdot (2-i)+e^{-i2\pi 0\cdot 2/4}\cdot (-i)+e^{-i2\pi 0\cdot 3/4}\cdot (-1+2i)=2}$

${\displaystyle X_{1}=e^{-i2\pi 1\cdot 0/4}\cdot 1+e^{-i2\pi 1\cdot 1/4}\cdot (2-i)+e^{-i2\pi 1\cdot 2/4}\cdot (-i)+e^{-i2\pi 1\cdot 3/4}\cdot (-1+2i)=-2-2i}$

${\displaystyle X_{2}=e^{-i2\pi 2\cdot 0/4}\cdot 1+e^{-i2\pi 2\cdot 1/4}\cdot (2-i)+e^{-i2\pi 2\cdot 2/4}\cdot (-i)+e^{-i2\pi 2\cdot 3/4}\cdot (-1+2i)=-2i}$

${\displaystyle X_{3}=e^{-i2\pi 3\cdot 0/4}\cdot 1+e^{-i2\pi 3\cdot 1/4}\cdot (2-i)+e^{-i2\pi 3\cdot 2/4}\cdot (-i)+e^{-i2\pi 3\cdot 3/4}\cdot (-1+2i)=4+4i}$

${\displaystyle \mathbf {X} ={\begin{pmatrix}X_{0}\\X_{1}\\X_{3}\end{pmatrix}}}={\begin{pmatrix}2\\-2i\-2i\-4i\i\i\}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

역변환

이산 푸리에 변환은 되돌릴 수 없는 선형 변환이다.

${\displaystyle {\mathcal{F}\colon \mathb {C} ^{N}\mathb {C} \mathb {C} ^{N}}}}}$

복잡한 숫자 집합을 나타내는$$ $C{\displaystyle \mathbb{}}$ ${\$ 포함$.$ 그것의 역은 역 이산 푸리에 변환(IDFT)으로 알려져 있다. 즉, > 0 ${\displaystyle N>0$에 대해 N 차원 복합 벡터는 DFT와 IDFT를 가지며, $이$는 N ${\displaystyle N}$ - 차원 복합$$ 벡터가 된다.

역 변환은 다음과 같이 주어진다.

성성.

선형성

The DFT is a linear transform, i.e. if ${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$ and ${\displaystyle {\mathcal {F}}(\{y_{n}\})_{k}=Y_{k}}$, then for any complex numbers ${\displaystyle a,b}$:

$mathcal {displaystyle {\cax_{n}+by_{n}\}}}}}{k}=aX_{k}+}+}+}+}+}BY_{k}}}}}$

도도 반반

$시간{\displaystyle {}_{}}$ 역방향($즉{\displaystyle }$, ${\displaystyle x_{}}$ ${\$$displaystyle$n}을(를) x {\$displaystyle x_{n}$에서 $N{\displaystyle }$- ${\displaystyle n}$ ${\displaystyle N-n$$\}$^[B]으로 교체하는 것은 주파수 역방향($즉{\displaystyle }$, k ${\displaystyle k}$ by$$ $N{\displaystyle }$- k$})$에 해당한다$$.$$^{[5]: p.421} 수학적으로${\displaystyle }${ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \{x_{n}\}}}$이(가) 벡터 x를 나타내면$$ 다음이 된다.

$if{\displaystyle \mathcal{}}$ F${\displaystyle }$(${\displaystyle }${ ${\displaystyle x_{}}$ n${\displaystyle {}_{}{}_{}}$ )${\displaystyle {}_{}{k}_{}}$ = ${\displaystyle X_{}}$ k ${\${\$mathcal {F}(\{x_{n}\})_{k}=X_{k}}}}$

$그{\displaystyle \mathcal{}}$ 다음 F${\displaystyle }$(${\displaystyle }${ x${\displaystyle N_{}}$ - n${\displaystyle {}_{}{}_{}}$ )${\displaystyle {}_{}{k}_{}}$ = ${\displaystyle {}_N}$ - ${\displaystyle k_{}}${\$displaystyle {\mathcal {F}(\{x_{N-n}\})_{k}=X_{N-k}}}}}$

결 합 합 conju

If ${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$ then ${\displaystyle {\mathcal {F}}(\{x_{n}^{*}\})_{k}=X_{N-k}^{*}}$.^{[5]: p.423}

실물과 상상의 부분

이 표는 시간 영역의$$ x ${\displaystyle n_{}}$ ${\$에 대한 일부 수학 연산 및 주파수 영역의$$ DFT $X{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$에 대한 해당 효과를 보여준다.

속성	시간 영역 $displaystyle x_{n}}}$	주파수 영역 $displaystyle X_{k}}}$
실제 시시 시간	$){\displaystyle \Re(x_{n}\오른쪽$	${1displaystyle {\\\\frac{1}:{1}:{1}:{1}:{1}}}}\displaystystyle(X_{{{k}+X}}}}}}}}}}\mprollowpa)}\pa)}\pa)}\propaffaffairpairpairpairpairpa$
상상의 시간 부분	$){\displaystyle \Im {\property(x_{n}\property$	${11}{displaystyle {\\prac {1}{1}{1}}\n-k}^{*}\n-properique)}}}}}$
실제 주파수 부분	${11}{displaystyle {\\\\frac {1}:{1}:{1}:{1}:{1}:{1}}}}\displaystystyledaystyledown(x_{{{{{{{{{n-n-n-n-n})})}}}$	$){\displaystyle \Re(X_{k}\오른$
주파수의 가상 부품	$1}{displaystyle {\\\frac {1}{1}{1}{1}{1}{2i}\n-n}^{*}\nmproperi)}}}}}}}}}}$	$오른쪽){\displaystyle \Im {\property(X_{k}\property$

ality성성성

벡터 ${\displaystyle u_{}}$ k${\displaystyle {}_{}}$=${\displaystyle {}^{}}$[ ${\displaystyle {e{}^{}}^{}}$ ${\displaystyle {{i\frac{}{}}^{}}^{}}$ ${\displaystyle {{\frac{2}{}}^{}}^{}}$ ${\displaystyle {{\frac{\pi }{}}^{}}^{}}$ N ${\displaystyle {k^{}}^{}}$ ${\displaystyle {n{}^{}}^{}}$= ${\displaystyle {0,}^{}}$ ${\displaystyle 1^{}}$,${\displaystyle {}^{}}$… ,${\displaystyle N^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {]}^{}}$ ${\displaystyle {\mathsf{}}^{}}$ ${\$$^{{\frac {i2\pi }{N}kn\;\right \;n=0,1$,\ldots$,N-1$\right$]^{\mathsf{T}}}$는 N차원 복합 벡터 집합에 걸쳐 직교 기준을 형성한다$$.

${\displaystyle u_{k}^{\mathsf {T}}u_{k'}^{*}=\sum _{n=0}^{N-1}\left(e^{{\frac {i2\pi }{N}}kn}\right)\left(e^{{\frac {i2\pi }{N}}(-k')n}\right)=\sum _{n=0}^{{N-1}e^{\frac {i2\pi }{{N}(k-k')n}=N~\delta _{kk'}}}}}}$

여기서 $\Delta {\displaystyle {}_{}}$ $′{\$은 크론커 델타다. (마지막 단계에서 합계는 ${\displaystyle {}^{}}$= k ${\displaystyle {\prime }^{}}$ ${\$ 여기서 1 + 1 + ⋯ = N이고, 그렇지 않으면 명시적으로 합계가 0을 얻을 수 있는 기하계열이라면 사소한 것이다.) 이 직교성 조건은 DFT의 정의에서 IDFT에 대한 공식을 도출하는 데 사용할 수 있으며, 아래의 단위성 속성과 동등하다.

플랑쉐렐 정리 및 파르세발 정리

$X{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$와 ${\displaystyle Y_{}}$ $k{\displaystyle {}_{}}$ ${\$의 DFT가 각각$$$$ $x{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$와 y$$ ${\displaystyle n_{}}$ ${\$인 경우 파르세발의 정리에는 다음과 같이 명시되어 있다.

${\displaystyle \sum _{n=0}^{N-1}x_{n}y_{n}^{*={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}}}Y_{k}^{*}}}}}}}$

여기서 별은 복잡한 결합을 나타낸다. 플랑쉐렐 정리는 파르세발 정리의 특수한 경우로서 다음과 같이 서술한다.

${\displaystyle \sum _{n=0}^{N-1} x_{n}^{2}={\frac {1}{{n1}{n1}{n1}{n1}N}\sum _{k=0}^{{N-1}X_{k}^{2}.}$

이 이론들은 또한 아래의 단일 조건과 동등하다.

주전자

주기성은 다음 정의에서 직접 확인할 수 있다.

${\displaystyle X_{k+N}\ \triangleq \ \sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}(k+N)n}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}kn}\underbrace {e^{-i2\pi n}} _{1}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}kn}=X_{k}.}$

마찬가지로, IDFT 공식은 주기적인 확장으로 이어진다는 것을 보여줄 수 있다.

시프트 정리

Multiplying ${\displaystyle x_{n}}$ by a linear phase ${\displaystyle e^{{\frac {i2\pi (n-1)}{N}}m}}$ for some integer m corresponds to a circular shift of the output ${\displaystyle X_{k}}$: ${\displaystyle X_{k}}$ is replaced by ${\displaystyle X_{k-m$$\}\},$ 첨자가 모듈로 N(즉, 주기적으로) 해석되는 경우. 마찬가지로 입력 $x{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$의 원형 이동은 출력 ${\displaystyle X_{}}$ k ${\$에 선형 위상을 곱하는 것에 해당한다$$. 수학적으로${\displaystyle }${ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \{x_{n}\}}}$이(가) 벡터 x를 나타내면$$ 다음이 된다.

$if{\displaystyle \mathcal{}}$ F${\displaystyle }$(${\displaystyle }${ ${\displaystyle x_{}}$ n${\displaystyle {}_{}{}_{}}$ )${\displaystyle {}_{}{k}_{}}$ = ${\displaystyle X_{}}$ k ${\${\$mathcal {F}(\{x_{n}\})_{k}=X_{k}}}}$

그 다음 $F{\displaystyle \mathcal{}{(\{{xn}_{}}_{}}$ ${\displaystyle {{}_{}}_{}}$ ${\displaystyle {{}^{}}_{}}$ i ${\displaystyle {{\frac{2}{}}^{}}_{}}$ ${\displaystyle {{\frac{\pi }{}}^{}}_{}}$ N ${\displaystyle {n^{}}_{}}$ ${\displaystyle {m^{}\}}_{}}$ )${\displaystyle {}_{}}$ = ${\displaystyle X_{}}$ ${\displaystyle {}_{}}$- ${\displaystyle m_{}}${\$displaystyle${\$f}\좌측(\\x_{n}\cdot$ e$^{\frac{i2\pi }{N}}}}\우측)$$_{k}=X_{k-m}}}$

${\displaystyle {}_{}}$ $F{\displaystyle \mathcal{}({}_{}}${ ${\displaystyle {x_{}}_{}}$ ${\displaystyle {n_{}}_{}}$- m ${\displaystyle {{}_{}}_{}}$) k${\displaystyle {}_{}}$= ${\displaystyle {}^{}}$ ${\displaystyle k_{}}$ ${\displaystyle {}_{}}$ e${\displaystyle {}^{}}$- i ${\displaystyle {\frac{2}{}}^{}}$ ${\displaystyle {\frac{\pi }{}}^{}}$ N ${\displaystyle k^{}}$ ${\displaystyle m^{}}$ ${\$$_{k}=X_{k}\cdot e^{-{\frac {i2\pi }{N}}}}}}}}$

원형경련정리 및 교차상관정리

이산 시간 푸리에 변환(DTFT)에 대한 콘볼루션 정리는 두 시퀀스의 콘볼루션을 개별 변환물의 곱의 역변환으로 얻을 수 있음을 나타낸다. 중요한 단순화는 ${\displaystyle {\displaystyle {}_{}}}$ ${\displaystyle \{{\displaystyle }}$${\displaystyle {{}_{}}_{}{{}_{}}_{}}$$}$ {\$displaystyle$ \$scriptstyle$ {\$text{D$$}$이($)$ 여기에$$ 표시된 N-주기적 시퀀스일 때 발생한다.$TFT}}\displaystyle \{y_{N}\}}$은(는) 이산 주파수에서만 0이 아니므로$$(DTFT § 주기적 데이터 참조). 따라서 연속 기능 ${\displaystyle \text{DTFT}{\displaystyle }}${ ${\displaystyle {\displaystyle x\}.}}${\$displaystyle \scriptstyle{$d}을$(으$)로 한 제품도 그렇다.$TFT}\디스플레이 스타일 \{x\}.$$}$ 그렇게 되면$$ 역변형이 상당히 단순화된다.

${\displaystyle x*y_{_{N}}\ =\ \scriptstyle {\rm {DTFT}}^{-1}\displaystyle \left[\scriptstyle {\rm {DTFT}}\displaystyle \{x\}\cdot \scriptstyle {\rm {DTFT}}\displaystyle \{y_{_{N}}\}\right]\ =\ \scriptstyle {\rm {DFT}}^{-1}\displaystyle \left[\scriptstyle {\rm {DFT}}\displaystyle \{x_{_{N}}\}\cdot \scriptstyle {\rm {DFT}}\displaystyle \{y_{_{N}}\}\right,}$

where ${\displaystyle x_{_{N}}}$ is a periodic summation of the ${\displaystyle x}$ sequence: ${\displaystyle (x_{_{N}})_{n}\ \triangleq \sum _{m=-\infty }^{\infty }x_{(n-mN)}.$$}$

일반적으로 DFT와 역 DFT 합계는 도메인${\displaystyle }$[${\displaystyle 0,}$ ${\displaystyle N}$- ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle [0,N-1]$을 대체한다$.$ 이러한 DFT를 $X{\displaystyle }$ ${\displaystyle X}$ $및$ Y ${\displaystyle Y}$로 정의하면 다음과 같은 결과가 나온다.

${\displaystyle (x*y_{_{N}})_{n}\triangleq \sum _{\ell =-\infty }^{\infty }x_{\ell }\cdot (y_{_{N}})_{n-\ell }=\underbrace {{\mathcal {F}}^{-1}} _{\rm {DFT^{-1}}}\left\{X\cdot Y\right\}_{n}.}$

실제로 $x{\displaystyle }$ ${\displaystyle x}$ 시퀀스는$$ 일반적으로 길이 N 이하이며, ${\displaystyle {{}_{}}_{}}$ ${\$는 N-길이 $y{\displaystyle }$ ${\displaystyle y}$ -sequence의$$ 주기적인 확장이며, 다음과 같은 순환 함수로도 표현할 수 있다.

${\displaystyle (y_{_{N})_{n}=\sum _{p=-\nflt }^{\n-pN)}=y_{n\(n\operatorname {mod}N)}=y_{{n\mathb {Z}}}}}}},\quad n\in \mathb.$

그러면 수녀원은 다음과 같이 쓸 수 있다.

$이$는 x$${\$displaystyle x}$ $및$ y .$${\$displaystyle y.}$의 원형 경련으로 해석되는 경우가$$^[6][7] 많다. (Circular Convolution, Fast Convolution 알고리즘 및 중복 저장 참조)

$마찬가지$로 x ${\displaystyle x}$ 및$$ y ${\displaystyle {{}_{}}_{}}$ ${\$의 교차 상관관계는 다음과 같이 지정된다.

${\displaystyle (x\star y_{_{N}})_{n}\triangleq \sum _{\ell =-\infty }^{\infty }x_{\ell }^{*}\cdot (y_{_{N}})_{n+\ell }={\mathcal {F}}^{-1}\left\{X^{*}\cdot Y\right\}_{n}.}$

콘볼루션 정리 이중성

또한 다음과 같은 것을 보여줄 수 있다.

${\displaystyle {\mathcal {F}\f}\{\mathbf {x\cdot y}\riangleq \sum _{n=0}^{n-1}x_{n}\cdot y_{n}\cdot e^{-i{\fr}{2\pi}}}}}}{{{NKNKNKNKNKNKNKNKNKNKNKNKN}}}}}}}}}}}}}}}}}}}}}}}}$

${\displaystyle =}$ ${\displaystyle \frac{\mathrm{1N}}{}(X\mathbf{}}$ ${\displaystyle \mathbf{\ast }}$ ${\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {N\mathbf{}}_{}{}_{}}$) ${\displaystyle k_{}}$, ${\displaystyle ={\frac {1}{{N}}(\mathbf {X*Y_{N}){{k}}},$ $X{\displaystyle \mathbf{}}$ ${\$및$$ $Y{\displaystyle \mathbf{}}$ ${\$의 원형 콘볼루션이다$.$

삼각 보간 다항식

삼각 보간 다항식

${\displaystyle p(t)={\begin{cases}{\frac {1}{N}}\left[X_{0}+X_{1}e^{i2\pi t}+\cdots +X_{N/2-1}e^{i2\pi (N/2-1)t}+X_{N/2}\cos(N\pi t)+X_{N/2+1}e^{-i2\pi (N/2-1)t}+\cdots +X_{N-1}e^{-i2\pi t}\right]&N{\text{ even}}\\{\frac {1}{N}}\left[X_{0}+X_{1}e^{i2\pi t}+\cdots +X_{(N-1)/2}e^{i\pi (N-1)t}+X_{(N+1)/2}e^{-i\pi (N-1)t}+\cdots +X_{N-1}e^{-i2\pi t}\right]&N{\text{홀수}\end{case}}$

위의 x의_k DFT에_n 의해 계수 X가 주어지는 경우, n${\displaystyle }$= ${\displaystyle 0,}$…에 ${\displaystyle {}_{}}$ 보간 속성 $p{\displaystyle (n}$/ N${\displaystyle }$)${\displaystyle }$= ${\displaystyle x_{}}$ ${\$${\displaystyle N}$ -${\displaystyle 1}$ ${\displaysty n=0,\ldots,N-1}$을 만족한다$.$

N의 경우에도 Nyquist 구성 $요소\frac{{}_{}}{}$ $\frac{X_{}}{}$ $\frac{{N\mathrm{}}_{}}{}$/ $\frac{{}_{}}{}$ N $\cos$ $($ ($N$ $)$ $t$ $){\textstyle${\$frac$ {$X_{N/$2}}:{$N}}\cos(N\pi$ t$)}$가 특별히 처리된다는 점에 유의하십시오$$.

이 보간법은 고유하지 않다: 앨리어싱은 보간 특성을 변경하지 않고 $복합{\displaystyle {}_{}}$ 시누소이드 주파수($예{\displaystyle {}^{}}$: ${\displaystyle e^{}}$${\displaystyle {}^{}}$-${\displaystyle {}^{}}$${\displaystyle i^{}}$ ${\displaystyle t^{}}$ ${\$ e$^{-it$${\displaystyle {\})}^{}}$를 $e{\displaystyle {}^{}}$ i (N - 1 ) t$${\$displaysty$ $e^{i(N-1)t$로 ${\displaystyle N_{}}$을 추가할 수 있음을 암시한다$.$$x_{n}}$점$$. 그러나 위의 선택은 두 가지 유용한 속성을 가지고 있기 때문에 전형적이다. 첫째, 주파수가 가능한 가장 작은 크기를 갖는 사인파(Synusoid)로 구성된다. 즉 보간이 밴드 제한적이다. 둘째, x ${\displaystyle n_{}}$ ${\$이 실제$$ 숫자라면 p (${\displaystyle t}$) ${\displaystyle p(t)}$도 역시 실제 숫자다$$.

대조적으로 가장 명백한 삼각 보간 다항식은 주파수 범위가 0에서 N${\displaystyle }$- $1까지$인 ${\displaystyle 주파수\mathrm{}}$$($위처럼 ${\displaystyle \mathrm{대략}}$$$${\displaystyle }$- N${\displaystyle }$/ 2 ${\displaystyle -N/2$} ~${\displaystyle }$+ ${\displaystyle N}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle +N/2})$이며 역 DFT 공식과 유사하다. 이 보간법은 경사를 최소화하지 않으며, 실제 x ${\displaystyle n_{}}$ ${\$에 대해 일반적으로 실제 값을 매기지 않는다$.$ 그 용도는 일반적인 실수다.

.

DFT를 바라보는 또 다른 방법은 위의 논의에서 DFT는 실베스터가 1867년에 도입한 Vandermonde 매트릭스인 DFT 매트릭스로 표현될 수 있다는 점에 주목하는 것이다.

${\displaystyle \mathbf{F}={\begin{bmatrix}\omega _{N}^{0\cdot 0}&,\omega _{N}^{0\cdot 1}&, \cdots,\omega _{N}^{0\cdot(N-1)}\\\omega _{N}^{1\cdot 0}&,\omega _{N}^{1\cdot 1}&, \cdots,\omega _{N}^{1\cdot(N-1)}\\\vdots 및 &, \vdots &, \ddots &, \vdots \\\omega _{N}^{(N-1)\cdot 0}& &,\omega _{N}^{(N-1)\cdot 1}&, \cdots 및.;\omega _{N}^{(N-1)\cdot(N-1)}\\\end{bmatrix}}}{\displaystyle \mathbf{F}={\begin{bmatrix}\omega _{N}^{0\cdot 0}&,\omega _{N}^{0\cdot 1}&, \cdots,\omega _{N}^{0\cdot(N-1)}\\\omega _{N}^{1\cdot 0}&,\omega _{N}^{1\cdot 1}&, \cdots,\omega _{N}^{1\cdot(N-1)}\\\vdots 및 &, \vdots &, \ddots &, \vdots \\\omega _{N}^{(N-1)\cdot 0}& &,\omega _{N}^{(N-1)\cdot 1}&, \cdots 및.;\omega _{N}^{{N-1)\cdot(N-1)}\\\end{bmatrix}}}}$

여기서 $\Omega {\displaystyle {}_{}}$ ${\displaystyle N_{}}$= ${\displaystyle {}^{}}$- ${\displaystyle i^{}}$ ${\displaystyle 2^{}}$ ${\displaystyle {\pi }^{}}$/ ${\displaystyle N^{}}$ ${\$는 원초적인 N번째 통합 루트다.

역 변환은 위의 행렬의 역행렬에 의해 주어진다.

$displaystyle \ {F}{1}={\frac {1}\mathbf {F}{*}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

단일 정규화 상수 $1\mathrm{}$/ $N\sqrt{}$ ${\$을 사용하여 DFT는 단일 정규화 행렬에 의해 정의된 단일 변환이 된다$.$

${\displaystyle{\begin{정렬}\mathbf{U}&={\frac{1}{\sqrt{N}}}\mathbf{F}\\\mathbf{U}^{)}&, =\mathbf{U}^{*}\\\left \det(\mathbf{U})\right&=1\end{정렬}}}{\displaystyle{\begin{정렬}\mathbf{U}&={\frac{1}{\sqrt{N}}}\mathbf{F}\\\mathbf{U}^{)}&, =\mathbf{U}^{*}\\\left \det(\mathbf{U})\right&=1\end{알.}}igned}$

여기서 ${\displaystyle det}$ (${\displaystyle }$) ${\displaystyle \det()}$은(는) 결정요인함수다. 결정 인자는 고유값의 산물로, 아래 설명과 같이$$ ${\displaystyle \mathrm{항상}}{\displaystyle }$± 1$[\displaystyle \pm 1}$${\displaystyle }$또는$$ ± $[\displaystyle \pm$ i$}$이다. 실제 벡터 공간에서 단일 변환은 단순히 좌표계의 경직된 회전이라고 생각할 수 있으며, 강성 회전의 모든 특성은 단일 벡터 공간에서는 찾을 수 있다.

DFT의 직교성(직교성)은 현재 직교성 조건(통합의 뿌리에서 설명되는 수학의 많은 영역에서 발생한다)으로 표현된다.

$km\delta_n-1}^{m-1}U_{mn}^{*=\delta_{kna}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

X가 벡터 x의 단일 DFT로 정의되면

$n1}{displaystyle X_{k}=\sum _{n=0}^{N-1}U_{kn}x_{n}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

그리고 파르세발의 정리는 다음과 같이 표현된다.

${\displaystyle \sum _{n=0}^{N-1}x_{n}y_{n}^{*}=\sum _{k=0}^{N-1}X_{k}}}Y_{k}^{*}}}}}}}$

만약 DFT를 단순히 새로운 좌표계의 벡터 구성요소를 지정하는 좌표 변환으로 본다면, 위의 내용은 두 벡터의 도트 산출물이 단일 DFT 변환 하에서 보존된다는 설명에 불과하다. 특수 사례 $x{\displaystyle \mathbf{}}$= ${\displaystyle y\mathbf{}}$ ${\$의 경우, 이는 벡터의 길이도 보존됨을 의미하며, 이는 단지 Planchrel 정리일 뿐이다.

${\displaystyle \sum _{n=0}^{{N-1} x_{n}^{2}=\sum _{k=0}^{N-1}X_{k}^{2}}$

원형 콘볼루션 정리의 결과는 DFT 매트릭스 F가 모든 순환 매트릭스를 대각선화한다는 것이다.

를 DFT로

DFT의 유용한 특성은 역 DFT는 잘 알려진 여러 "트릭"을 통해 (앞으로) DFT의 관점에서 쉽게 표현될 수 있다는 것이다(예를 들어, 계산에서, 한 변환 방향에 해당하는 빠른 푸리에 변환만 구현한 다음 다른 변환 방향을 첫 번째 변환에서 얻는 것이 편리하다).

첫째, 입력 중 하나를 제외한 모든 값을 역전시켜 역 DFT를 계산할 수 있다(Duhamel et al., 1988):

$1}{displaystyle {\mathcal{{}}}}}}}}}{\displaystystyle {\mathcal}F}^{-1}(\{x_{n}\}\}\}}={\frac {1}{{{{}}}}}}={\fracN}{{\mathcal {F}(\{x_{N-n}\}})$

(평소처럼 첨자는 모듈로 ${\displaystyle \mathrm{N}}$으로 해석되므로, $n{\displaystyle }$= 0 ${\displaystyle n=0$의 경우 ${\displaystyle x_{}}$ N${\displaystyle {}_{}}$- ${\displaystyle 0_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$

둘째, 입력과 출력을 조합할 수도 있다.

${x}{1){\displaystyle {\mathbf {x}^{-1}={frac{1}{1}{1}N}{{\mathbcal {F}\mathbf {x}^{*}\mathbf {x}^}\mathb오$

셋째, 데이터 값의 수정이 필요 없기 때문에 선호되는 이 결합 트릭의 변형은 실제와 가상의 부분(포인터만 수정하면 컴퓨터로 할 수 있다)을 교환하는 것을 포함한다. Define ${\textstyle \operatorname {swap} (x_{n})}$ as ${\displaystyle x_{n}}$ with its real and imaginary parts swapped—that is, if ${\displaystyle x_{n}=a+bi}$ then ${\textstyle \operatorname {swap} (x_{n})}$ is ${\displaystyle b+ai}$. 동등하게$\mathrm{swap}{}_{}{xn}_{}$) {\$textstyle \operatorname {swap}(x_{$n})은 i x${\displaystyle {}_{}^{}}$n$display$ {\$displaystyle ix_{$n$\}^\{*\}\}\}$과(와$$) 같음. 그런 다음

$}}{\displaystyle {\mathbf {x}^{-1}(\mathbf {x} )={\frac {1}{{N}\operatorname {swap}(\mathbf {x}})({\mathbf {f}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

즉, 역변환이란 입력과 출력 모두를 위해 교환된 실제와 가상의 부품을 정합화(Duhamel et al., 1988)한 전방변환과 동일하다.

또한 이 결합 트릭은 DFT와 밀접하게 관련된 새로운 변환, 즉 그 자체의 역인 DFT를 정의하는데 사용될 수 있다. In particular, ${\displaystyle T(\mathbf {x} )={\mathcal {F}}\left(\mathbf {x} ^{*}\right)/{\sqrt {N}}}$ is clearly its own inverse: ${\displaystyle T(T(\mathbf {x} ))=\mathbf {x} }$. A closely related involutory transformation (by a factor of ${\t$$extstyle {\frac {1+i}{\sqrt {2}}}}$) is ${\displaystyle H(\mathbf {x} )={\mathcal {F}}\left((1+i)\mathbf {x} ^{*}\right)/{\sqrt {2N}}}$, since the ${\displaystyle (1+i)}$ factors in ${\displaystyle H(H(\mathbf {x} ))}$ cancel the 2. 실제 입력 $x{\displaystyle \mathbf{}}$ ${\${${\displaystyle x\mathbf{}}$$}}$의 $경우{\displaystyle }$$,$${\displaystyle }$H(${\displaystyle }$x )$${\$displaystyle$ H$(\mathbf {x}$ )의 실제 부분은 다름아닌 이산형 Hartley 변환이며, 이 역시 비자발적인 것이다.

and and and and and and.

DFT 매트릭스의 고유값은 단순하고 잘 알려져 있는 반면, 고유 벡터는 고유하지 않고 복잡하며 현재 진행 중인 연구의 대상이다.

N 길이의 DFT에 대해 위에 정의된$$ $U{\displaystyle \mathbf{}}$ ${\$을(를) 고려하십시오.

${\displaystyle \mathbf {U} _{m,n}={\frac {1}{\sqrt {N}}}\omega _{N}^{(m-1)(n-1)}={\frac {1}{\sqrt {N}}}e^{-{\frac {i2\pi }{N}}(m-1)(n-1)}.}$

이 행렬은 행렬 다항식 방정식을 만족한다.

$displaystyle \mathbf {U}^{4}=\mathbf {I}}}}$

$이$는 위의 역 속성에서 알 수 있다: U ${\$을$($를) 두 번 작동하면 원본 데이터가 역순으로 제공되므로 $U{\displaystyle \mathbf{}}${\$displaystyle \mathbf {U}$을(를) 네 번 작동하면 원본 데이터가 반환되므로 ID 매트릭스가 된다. 이는 고유값 $\lambda {\displaystyle }$ ${\displaystyle \lambda }$이(가) 다음 방정식을 충족함을$$ 의미한다.

$\displaystyle \lambda ^{4}=1.}$

따라서 $U{\displaystyle \mathbf{}}$ ${\$의 고유값은 통합의 네 번째 루트인 $\lambda$ ${\displaystyle \lambda }$은(는) +1, -1, +i 또는 -i이다.

이 $N{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle N}$ ${\displaystyle N\times$N} 행렬에$$ 대한 고유값은 4개뿐이므로 어느 정도 다중성이 있다. 다중성은 각 고유값에 해당하는 선형 독립 고유 벡터의 수를 제공한다. (N개의 독립 고유 벡터가 있으며, 단일 행렬은 절대 결함이 없다.)

나중에 가우스(Dickinson and Steiglitz, 1982년)가 해결한 문제와 맞먹는 것으로 나타났지만, 그들의 다중성 문제는 맥클렐런과 파크스(1972)에 의해 해결되었다. 다중성은 N modulo 4의 값에 따라 달라지며, 다음 표에 의해 제시된다.

변환 크기 N(정수 m)의 함수로서 유니터리 DFT 매트릭스 U의 고유값 λ의 곱.

N사이즈	λ = +1	λ = −1	λ = −i	λ = +i
4m	m + 1	m	m	m − 1
4m + 1	m + 1	m	m	m
4m + 2	m + 1	m + 1	m	m
4m + 3	m + 1	m + 1	m + 1	m

달리 명시되지 않은 $U{\displaystyle \mathbf{}}$ ${\$의 특성 다항식은 다음과$$ 같다.

${\displaystyle \det(\lambda I-\mathbf {U}=(\lambda -1)^{\lprogram\lfloor {\tfrac {N+4}{4}{4}}}{4}}}}}\\\rf\rfloor }(\\da +1)^{\\왼쪽\lfloor {\tfrac{N+2}{4}}}}}\오른쪽\\loor }(\lambda +i)^{\\좌측\lfloor{\tfrac{N+1}{4}}}}}}(\cHBDA -i)^{\\cHB\lfloor{4}\right\cHBLOOR }}}}}$

일반 고유 벡터에 대한 간단한 분석 공식은 알려져 있지 않다. 또한 동일한 고유값에 대한 고유 벡터의 선형 결합도 해당 고유값에 대한 고유 벡터이기 때문에 고유 벡터는 고유하지 않다. Various researchers have proposed different choices of eigenvectors, selected to satisfy useful properties like orthogonality and to have "simple" forms (e.g., McClellan and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Atakishiyev and Wolf, 1997; Candan et al., 2000; Hanna et al., 2004; Gurevich and Hadani, 2008).

간단한 접근법은 연속적인 푸리에 변환의 고유 기능을 탈피하는 것인데, 그 중 가장 유명한 것이 가우스 함수다. 함수의 주기적 합계는 주파수 스펙트럼의 분산을 의미하며, 디스코트(discretation)는 스펙트럼의 주기적 합산을 의미하므로, 디스코트되고 주기적으로 합산되는 가우스 함수는 이산형 변환의 고유 벡터를 산출한다.

• ${\displaystyle F(m)=\sum _{k\in \mathb{Z}}\exp \left(-{\frac {\pi \cdot(m+N\cdot k)^{2}}{N}\cdmpi쪽쪽)).}$

시리즈의 닫힌 형태 표현은 자코비 세타 함수에 의해 표현될 수 있다.

• ${\displaystyle F(m)={\frac {1}{\sqrt{N}\vartheta _{3}\pi m}{N},\exp \좌)).}$

특수 DFT 기간 N에 대한 다른 두 개의 단순한 폐쇄형 분석 고유 벡터가 발견되었다(Kong, 2008).

DFT 주기 N = 2L + 1 = 4K + 1의 경우, 여기서 K는 DFT의 고유 벡터는 다음과 같다.

• $displaystyle F(m)=\prod _{s=K+1}^{n1}L}\좌측[\cos \좌측({\frac {2\pi }{N}m\우측)-\cos \좌측({\frac {2\pi }{N}s\우측)\우측]}}$

DFT 주기 N = 2L = 4K의 경우, 여기서 K는 정수인 경우 DFT의 고유 벡터는 다음과 같다.

• ${\displaystyle F(m)=\sin \left({\frac {2\pi }{N}}m\right)\prod _{s=K+1}^{L-1}\left[\cos \left({\frac {2\pi }{N}}m\right)-\cos \left({\frac {2\pi }{N}}s\right)\right]}$

분수 푸리에 변환의 이산 아날로그를 정의하기 위해 DFT 매트릭스의 고유 벡터 선택은 최근 몇 년 동안 중요해졌다. 즉, DFT 매트릭스는 고유값을 지수화하여 부분 파워로 가져갈 수 있다(예: 루비오와 산타남, 2005). 연속적인 푸리에 변환의 경우, 자연직교 고유특성은 헤르미테 함수가므로, 이것들의 다양한 이산 유사점들이 Kravchuk 다항식(Atakishiyev and Wolf, 1997년)과 같은 DFT의 고유 벡터로 채용되었다. 그러나 부분 이산 푸리에 변환을 정의하기 위한 고유 벡터의 "최상의" 선택은 여전히 미해결 문제로 남아 있다.

불확실성 원리

확률적 불확실성 원리

변량 변수_k X가 다음에 의해 제약되는 경우

$displaystyle \sum \_{n=0}^{N-1}X_{n}^{n}^{n}=1,}}}$

그때

$displaystyle P_{n}=X_{n}^{2}}$

n의 이산 확률 질량 함수를 나타내는 것으로 간주할 수 있으며, 변환된 변수로부터 구성된 관련 확률 질량 함수를 사용할 수 있다.

${\displaystyle Q_{m}=N x_{m} ^{2}.}$

연속함수 $P{\displaystyle (}$ ${\displaystyle x}$) ${\displaystyle P(x)}$ 및$$ $Q{\displaystyle (k)}$ ${\displaystyle Q(k)}$의 경우$,$ 하이젠베르크 불확도 원리는 다음과 같이 명시한다.

${\displaystyle D_{0}(X){\{1}}D_{0}(x)\geq {1}{16\pi ^{2}}:$

여기서 $D{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$( ${\displaystyle X}$) ${\displaystyle D_{0}(X)}$과 D ${\displaystyle {0\mathrm{}}_{}x}$) ${\displaystyle D_{0}(x)$은 ${\displaystyle 각각}$$$ X ${\displaystyle {}^{\mathrm{}}}$ ${\$X$^{2$}}과$$ ${\displaystyle {}^{\mathrm{}}}$ 2 ${\$x$^{2$}}의 분산이며, 적절한$$ 정규화된 가우스 분포의 경우 달성된 동일하다. 분산이 DFT에 대해 유사하게 정의될 수 있지만, 불확실성은 변위 불변성이 아니기 때문에 유사한 불확실성 원리는 유용하지 않다. 그럼에도 불구하고 마사르와 스핀델에 의해 의미 있는 불확실성 원리가 도입되었다.^[8]

그러나, Hirschman 진입성 불확실성은 DFT의 경우에 유용한 유사성을 가질 것이다.^[9] Hirschman 불확실성 원리는 두 확률 함수의 Shannon 엔트로피 용어로 표현된다.

이산형 케이스에서 섀넌 엔트로피는 다음과 같이 정의된다.

$n}}{n=0}}}{n-1}^{n-1}}\ln P_{n}}}}}}}:{n}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}{n-{n-}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

그리고

$displaystyle H(x)=-\sum _{m=0}^{{N-1}Q_{m}\ln Q_{m}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}.$

그리고 등방성 불확실성 원칙은^[9]

$[\displaystyle H(X)+H(x)\geq \ln(N)]}}}}}}$

Pn ${\$ $P_$${n}$에 대해 동등성이 확보되었으며, $여기$서 $A{\displaystyle }$ ${\displaystyle A}$은(는) $N{\displaystyle }$ ${\displaystyle N}$의 정확한 정수 변위임$.$ 확률 질량 함수 ${\displaystyle Q_{}}$ ${\$이 된다$$. 적절하게 번역된 기간 $B{\displaystyle }$= ${\displaystyle N}$/ A$${\$displaystyle B=N/A}$에 비례한다$.$^[9]

결정론적 불확실성 원리

또한 신호 첨사성(또는 0이 아닌 계수의 수)을 사용하는 잘 알려진 결정론적 불확실성 원리가 있다.^[10] Let ${\displaystyle \left\ x\right\ _{0}}$ and ${\displaystyle \left\ X\right\ _{0}}$ be the number of non-zero elements of the time and frequency sequences ${\displaystyle x_{0},x_{1},\ldots ,x_{N-1}}$ and ${\displaystyle X_{$$각각$ 0$,X_{1},\ldots,X_{{N-1$ 그러면.

$\displaystyle N\leq \왼쪽\x\오른쪽\ _{0}\cdot \왼쪽\X\오른쪽\ _{0}.}$

As an immediate consequence of the inequality of arithmetic and geometric means, one also has ${\displaystyle 2{\sqrt {N}}\leq \left\ x\right\ _{0}+\left\ X\right\ _{0}}$. Both uncertainty principles were shown to be tight for specifically-chosen "picket-fence" sequences (discrete impulse trains), and f신호 복구 응용 프로그램을 위한 실용화.^[10]

실 수 있는 가수의 DFT .

• $x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$,${\displaystyle }$… , ${\displaystyle x_{}}$ ${\displaystyle {\mathrm{N}}_{}}$- 1 ${\$이 실제 숫자인 경우, $DFT{\displaystyle {}_{}}$ X${\displaystyle {}_{}{0\mathrm{}}_{}}$ , ${\displaystyle \dots ,}$ X ${\displaystyle N_{}}$- ${\displaystyle 1_{}}${\$displaystyle X_{0},\ldots ,X_{N-1}$은 짝수 대칭이다.

${\displaystyle x_{n}\in \mathbb {R} \quad \forall n\in \{0,\ldots ,N-1\}\implies X_{k}=X_{-k\mod N}^{*}\quad \forall k\in \{0,\ldots ,N-1\}}$, where ${\displaystyle X^{*}\,}$ denotes complex conjugation.

$따라서{\displaystyle }$ N$${\$displaystyle N}$ $X$${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}${\$displaystyle X_{0}$과($와$) ${\displaystyle {XN\mathrm{}}_{}}$/ 2 {\$displaystyle X_{N/2$}}조차도 실제 값을 가지며$$, 나머지 DFT는 $N{\displaystyle }$/${\displaystyle }$2 - ${\displaystyle 1}$ ${\displaystyle$ N$/2-1}$콤플렉스$$ 숫자로 완전히 지정된다.

• $x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle x_{}}$ ${\displaystyle {\mathrm{N}}_{}}$- 1 ${\$이 순전히 가상의 숫자라면$$, DFT $X{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$, ${\displaystyle \dots ,}$X ${\displaystyle {\mathrm{N}}_{}}$- 1 ${\$은 홀수 대칭이다.

${\displaystyle x_{n}\in i\mathbb {R} \quad \forall n\in \{0,\ldots ,N-1\}\implies X_{k}=-X_{-k\mod N}^{*}\quad \forall k\in \{0,\ldots ,N-1\}}$, where ${\displaystyle X^{*}\,}$ denotes complex conjugation.

일반화 DFT(변형 및 비선형 위상)

시간 및/또는 주파수 영역에서의 변환 샘플링을 각각 실제 교대조 a와 b로 이동할 수 있다. 이를 일반화된 DFT(또는 GDFT)라고도 하며, 시프트 DFT 또는 오프셋 DFT라고도 하며, 일반 DFT와 유사한 특성을 가지고 있다.

${\displaystyle X_{k}=\sum _{n-1}x_{n}e^{-{\frac {i2\pi }{{N}}(k+b)(n+a)}\quad \quad k=0,\dots,N-1.}$

$가장{\displaystyle \mathrm{}}$ 흔히 1/$[\디스플레이$ 스타일 1$/2]$의 교대조(표본의 절반)가 사용된다. While the ordinary DFT corresponds to a periodic signal in both time and frequency domains, ${\displaystyle a=1/2}$ produces a signal that is anti-periodic in frequency domain (${\displaystyle X_{k+N}=-X_{k}}$) and vice versa for ${\displaystyle b=1/2}$. Thus, the specific case of $$${\displaystyle a}$= ${\displaystyle b}$= ${\displaystyle 1}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle a=b=1/2$}은$($는) 홀수 시간 홀수 주파수 이산 푸리에 변환(또는² O DFT)으로 알려져 있다. 이러한 이동 변환은 대칭 데이터, 서로 다른 경계 대칭을 나타내기 위해 가장 자주 사용되며, 실제 대칭 데이터의 경우 이산 코사인 및 사인 변환의 다른 형태에 대응한다.

${\displaystyle 또}$ 다른 흥미로운 선택은 $a{\displaystyle }$= b${\displaystyle }$=${\displaystyle }$-${\displaystyle }$( ${\displaystyle \mathrm{N}}$- 1${\displaystyle }$)${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle a=b=-(N-1)/2}$인데$,$ 이를 중심 DFT(또는 CDFT)라고 한다. 중심 DFT는 N이 4의 배수일 때 4개의 고유값(위 참조) 모두 동일한 승수를 갖는 유용한 속성을 갖는다(Rubio 및 Santhaman, 2005).^[11]

GDFT라는 용어는 DFT의 비선형 위상 확장에도 사용된다. 따라서 GDFT 방법은 선형 및 비선형 위상 유형을 포함한 일정한 진폭 직교 블록 변환에 대한 일반화를 제공한다. GDFT는 원래 선형 위상 함수(Akansu 및 Agirman-Tosun, 2010)에 적절하게 설계된 위상 쉐이핑 함수(일반적으로 비선형)를 추가하여 기존 DFT(예: 자동/교차 상관)의 시간 및 주파수 영역 특성을 개선하기 위한 프레임워크다.^[12]

이산 푸리에 변환은 복잡한 평면의 단위 원 위에서 평가되는 z-변환기의 특별한 경우로 볼 수 있다. 보다 일반적인 z-변환기는 위의 복잡한 교대조 a와 b에 해당한다.

DFT

일반 DFT는 정확히 하나의 이산형 변수 n의 함수인$$ 1차원 시퀀스 또는 배열 ${\displaystyle x_{}}$ n ${\$를 변환한다. The multidimensional DFT of a multidimensional array ${\displaystyle x_{n_{1},n_{2},\dots ,n_{d}}}$ that is a function of d discrete variables ${\displaystyle n_{\ell }=0,1,\dots ,N_{\ell }-1}$ for ${\displaystyle \ell }$ in ${\displayst$$yle$1$,2,\reason ,d}$은(는) 다음에 의해 정의된다.

${\displaystyle X_{k_{1},k_{2},\dots ,k_{d}}=\sum _{n_{1}=0}^{N_{1}-1}\left(\omega _{N_{1}}^{~k_{1}n_{1}}\sum _{n_{2}=0}^{N_{2}-1}\left(\omega _{N_{2}}^{~k_{2}n_{2}}\cdots \sum _{n_{d}=0}^{N_{d}-1}\omega _{N_{d}}^{~k_{d}n_{d}}\cdot x_{n_{1},n_{2},\dots ,n_{d}}\right)\right),}$

where ${\displaystyle \omega _{N_{\ell }}=\exp(-i2\pi /N_{\ell })}$ as above and the d output indices run from ${\displaystyle k_{\ell }=0,1,\dots ,N_{\ell }-1}$. This is more compactly expressed in vector notation, where we define ${\displaystyle \mathbf{n}=(n_1,n_{}}$${\displaystyle \mathbf {n} =(n_{1},n_{2},\dots ,n_{d})}$ and ${\displaystyle \mathbf {k} =(k_{1},k_{2},\dots ,k_{d})}$ as d-dimensional vectors of indices from 0 to ${\displaystyle \mathbf {N} -1}$, which we define as ${\displaystyle \mathbf{N}-1=(N_1-1,N_2-1,\dots }$${\displaystyle ,}$ ${\displaystyle N_{}}$ ${\displaystyle \mathrm{d}{}_{}}$- 1${\displaystyle }$) ${\dplaystyle \mathbf {N} -1=(N_{1$}-$1,N_{2}-1,\dots,N_{d}-1$

${\displaystyle X_{\mathbf {k} }=\sum _{\mathbf {n} =\mathbf {0} }^{\mathbf {N} -1}e^{-i2\pi \mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }\,,}$

where the division ${\displaystyle \mathbf {n} /\mathbf {N} }$ is defined as ${\displaystyle \mathbf {n} /\mathbf {N} =(n_{1}/N_{1},\dots ,n_{d}/N_{d})}$ to be performed element-wise, and the sum denotes the set of nested summations above.

.

${\displaystyle x_{\mathbf {n} }={\frac {1}{\prod _{\ell =1}^{d}N_{\ell }}}\sum _{\mathbf {k} =\mathbf {0} }^{\mathbf {N} -1}e^{i2\pi \mathbf {n} \cdot (\mathbf {k} /\mathbf {N} )}X_{\mathbf {k} }\,.}$

1차원 DFT는 입력 $x{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$을 사인파의 중첩으로$$ 표현하므로 다차원 DFT는 입력을 평면파, 즉 다차원 사인파의 중첩으로 표현한다. 공간에서의 진동 $방향$은 k${\displaystyle }$/ ${\displaystyle N\mathbf{}}$ ${\$이며, 진폭은 $X{\displaystyle {}_{}}$ {\$displaystyle X_${\$mathbf${k$}}}}}}$이다$.$ 이 분해는 디지털 이미지 처리(2차원)부터 부분 미분 방정식 해결까지 모든 면에서 매우 중요하다. 용액은 평면 파동으로 분해된다.

다차원 DFT는 각 차원을 따라 1차원 DFT의 시퀀스를 구성하여 계산할 수 있다. In the two-dimensional case ${\displaystyle x_{n_{1},n_{2}}}$ the ${\displaystyle N_{1}}$ independent DFTs of the rows (i.e., along ${\displaystyle n_{2}}$) are computed first to form a new array ${\displaystyle y_{n_{1},k_{2}}}$. Then the ${\disp$${\displaystyle {열\mathrm{}}_{}}$(n 1$${\$displaystyle n_{$1$\})$을 따라 y의 독립형$$ DFT를 계산하여 최종 $결과{\displaystyle {}_{}}$ ${\displaystyle {X{}_{}}_{}}$ ${\displaystyle {{k\mathrm{}}_{}}_{}}$1, k ${\displaystyle {{2\mathrm{}}_{}}_{}}${\$displaystyle X_{k_${1$}, k_{$2$\}\}.$ 또는 열을 먼저 계산한 다음 행을 계산할 수 있다. 그 순서는 통근하는 위의 내포된 합계 때문에 중요하지 않다.

따라서 1차원 DFT를 계산하는 알고리즘은 다차원 DFT를 효율적으로 계산하기에 충분하다. 이 접근방식은 행-열 알고리즘으로 알려져 있다. 본질적으로 다차원 FFT 알고리즘도 있다.

입력 DFT 리얼입력

실제 $숫자$로 구성된$$ 입력 데이터 x n ${\displaystyle {{1\mathrm{}}_{}}_{}}$,${\displaystyle {{}_{}}_{}}$n ${\displaystyle {{2\mathrm{}}_{}}_{}}$,${\displaystyle {}_{}}$n ${\displaystyle {d_{}}_{}}$ ${\$n_{$1},n_{2},\dots$,n_${d}}$의 경우 DFT 출력은 위의 1차원 사례와 유사한 결합 대칭을 가진다.

${\displaystyle X_{k_{1},k_{2},\dots,k_{d}-k_{1}-k_{1},N_{2}-k_{2},\dots,{N_{d}-k_}-{d}}}^{*},},}$

$여기$서 별은 다시 복잡한 결합을 나타내며 $and{\displaystyle }$ ${\displaystyle \ell}$ -th$$ 첨자는 다시 $modulo{\displaystyle {}_{}}$ N ${\displaystyle {\ell }_{}}$ ${\$ interpreted${\displaystyle }$= ${\displaystyle 1}$, ${\displaystyle 2}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle d}$ ${\displaystyle \ell$= 1$,$ $2,\ldots ,d})$로 해석된다.$$

어플리케이션

DFT는 많은 분야에서 광범위하게 사용되어 왔다. 우리는 단지 아래의 몇 가지 예시만을 스케치한다(끝의 참고문헌 참조). DFT의 모든 애플리케이션은 이산 푸리에 변환과 그 변환의 invers, 즉 빠른 푸리에 변환을 계산하는 고속 푸리에 변환의 가용성에 결정적으로 의존한다.

스펙트럼 분석

신호 스펙트럼 분석에 DFT를 사용하는 경우$,{\displaystyle }$ 일반적으로$$ { ${\displaystyle x_{}}$ $}$ {\$displaystyle$\{$x_{n}\}\}$ 시퀀스는 일부 $신호{\displaystyle }$ ${\displaystyle x}$(${\displaystyle }$t )$${\$displaysty$ x$(t)\}$의 균일한 간격의 시간 샘플의 유한 집합을 나타내며$,$ $여기$서 t ${\displaystystyle t}$은 시간을 나타낸다$$. 연속 시간에서 샘플(discrete-time)로의 변환은 $x{\displaystyle }$( ${\displaystyle t}$) ${\displaystyle$ x$(t)}$의 기본 푸리에 변환을 이산 시간 푸리에 변환(DTFT)으로$$ 변경하며, 일반적으로 앨리어싱이라고 하는 왜곡 유형을 수반한다. 적절한 샘플링 속도 선택(Nyquist rate 참조)이 그러한 왜곡을 최소화하기 위한 핵심이다. 이와 유사하게, 매우 긴(또는 무한) 시퀀스에서 관리 가능한 크기로의 변환은 DTFT에서 상세(즉, 분해능)의 상실로 나타나는 누출이라고 하는 일종의 왜곡을 수반한다. 적절한 하위 시퀀스 길이의 선택은 그 효과를 최소화하기 위한 주요 열쇠다. 사용 가능한 데이터(및 처리 시간)가 원하는 주파수 분해능을 달성하는 데 필요한 양보다 많을 경우, 표준 기법은 예를 들어 분광그램을 만들기 위해 여러 DFT를 수행하는 것이다. 원하는 결과가 전력 스펙트럼이고 데이터에 소음 또는 무작위성이 있는 경우, 다중 DFT의 크기 성분의 평균은 스펙트럼의 분산을 감소시키는 유용한 절차(이 맥락에서 주기각이라고도 함)이다. 이러한 기법의 두 가지 예는 웰치 방법과 바틀렛 방법이다. 일반적인 하위제크법이다.잡음 신호의 동력 스펙트럼 추정을 스펙트럼 추정이라고 한다.

변형(혹은 착각)의 최종 원천은 DFT 그 자체인데, 이는 연속 주파수 영역의 함수인 DTFT의 이산 샘플링에 불과하기 때문이다. 그것은 DFT의 분해능을 높임으로써 완화될 수 있다. 이 절차는 § DTFT 샘플링에 설명되어 있다.

• 이 절차를 제로 패딩(zero-padding)이라고도 부르기도 하는데, 이는 고속 푸리에 변환(FFT) 알고리즘과 함께 사용되는 특정 구현이다. 제로 값 "샘플"로 곱과 추가를 수행하는 비효율성은 FFT의 고유 효율성으로 상쇄되는 것 이상이다.
• 이미 기술한 바와 같이 누설은 DTFT의 고유 분해능에 제한을 가하기 때문에 미세한 DFT로부터 얻을 수 있는 편익에는 실질적인 한계가 있다.

필터 뱅크

§ FFT 필터 뱅크 및 § DTFT 샘플링을 참조하십시오.

데이터 압축

디지털 신호 처리 분야는 주파수 영역(즉, 푸리에 변환)에서의 운용에 크게 의존한다. 예를 들어, 몇몇 손실 이미지 및 소리 압축 방법은 이산 푸리에 변환을 채택한다. 즉, 신호가 짧은 세그먼트로 절단되고 각각 변환되며, 그 다음, 감지할 수 없는 것으로 가정되는 고주파의 푸리에 계수는 폐기된다. 압축 해제기는 감소된 Fourier 계수에 기초하여 역변환을 계산한다. (압축 애플리케이션은 종종 DFT, 이산 코사인 변환 또는 때로는 수정된 이산 코사인 변환의 특수한 형태를 사용한다.) 그러나 비교적 최근의 일부 압축 알고리즘은 데이터를 세그먼트로 잘라내고 각 세그먼트를 변환하여 얻은 것보다 시간과 주파수 영역 간에 더 균일한 절충을 제공하는 파월렛 변환을 사용한다. JPEG2000의 경우 원본 JPEG로 영상을 고도로 압축할 때 나타나는 가상 이미지 기능을 피한다.

부분 미분 방정식

이산 푸리에 변환은 종종 부분 미분 방정식을 풀기 위해 사용되는데, 여기서 다시 DFT는 푸리에 시리즈에 대한 근사치(무한 N의 한계에서 복구됨)로 사용된다. 이 접근법의 장점은 분화의 고유 기능인 복잡한 ${\displaystyle {\mathrm{지수}}^{}}$ $e{\displaystyle {}^{}}$ i x ${\$에서 신호를 확장한다는 것이다${\displaystyle :}$ $d{\displaystyle (}$ e ${\displaystyle i{}^{}}$ ${\displaystyle x^{}}$)${\displaystyle }$/ ${\displaystyle d}$ x = ${\displaystyle i}$ ${\displaystyle n}$ e ${\displaystyle x^{}}$ ${\$}}{\$datastyle {{\d}{inx}}}{\big}/{dx=in$ 따라서 푸리에 표현에서 분화는 간단하다. 단지 i ${\displaystyle n}$ ${\displaystyle in$로 곱할 뿐이다. ($그러나{\displaystyle }$ n ${\displaystylen}$의 선택은 앨리어싱으로 인해 고유하지 않다$$. 수렴 방법을 위해서는 위의 삼각 보간 섹션의 그것과 유사한 선택이 사용되어야 한다.) 계수가 일정한 선형 미분 방정식은 쉽게 해결할 수 있는 대수 방정식으로 변형된다. 그런 다음 역 DFT를 사용하여 결과를 다시 일반적인 공간 표현으로 변환한다. 그러한 접근을 스펙트럼법이라고 한다.

Polynomial multiplication

Suppose we wish to compute the polynomial product c(x) = a(x) · b(x). The ordinary product expression for the coefficients of c involves a linear (acyclic) convolution, where indices do not "wrap around." This can be rewritten as a cyclic convolution by taking the coefficient vectors for a(x) and b(x) with constant term first, then appending zeros so that the resultant coefficient vectors a and b have dimension d > deg(a(x)) + deg(b(x)). Then,

${\displaystyle \mathbf {c} =\mathbf {a} *\mathbf {b} }$

Where c is the vector of coefficients for c(x), and the convolution operator ${\displaystyle *\,}$ is defined so

${\displaystyle c_{n}=\sum _{m=0}^{n}a_{m}b_{n-m\ \mathrm {mod} \ d}\qquad \qquad \qquad n=0,1\dots ,d-1}$

But convolution becomes multiplication under the DFT:

${\displaystyle {\mathcal {F}}(\mathbf {c} )={\mathcal {F}}(\mathbf {a} ){\mathcal {F}}(\mathbf {b} )}$

Here the vector product is taken elementwise. Thus the coefficients of the product polynomial c(x) are just the terms 0, ..., deg(a(x)) + deg(b(x)) of the coefficient vector

${\displaystyle \mathbf {c} ={\mathcal {F}}^{-1}({\mathcal {F}}(\mathbf {a} ){\mathcal {F}}(\mathbf {b} )).}$

With a fast Fourier transform, the resulting algorithm takes O(N log N) arithmetic operations. Due to its simplicity and speed, the Cooley–Tukey FFT algorithm, which is limited to composite sizes, is often chosen for the transform operation. In this case, d should be chosen as the smallest integer greater than the sum of the input polynomial degrees that is factorizable into small prime factors (e.g. 2, 3, and 5, depending upon the FFT implementation).

Multiplication of large integers

The fastest known algorithms for the multiplication of very large integers use the polynomial multiplication method outlined above. Integers can be treated as the value of a polynomial evaluated specifically at the number base, with the coefficients of the polynomial corresponding to the digits in that base (ex. ${\displaystyle 123=1\cdot 10^{2}+2\cdot 10^{1}+3\cdot 10^{0}}$). After polynomial multiplication, a relatively low-complexity carry-propagation step completes the multiplication.

Convolution

When data is convolved with a function with wide support, such as for downsampling by a large sampling ratio, because of the Convolution theorem and the FFT algorithm, it may be faster to transform it, multiply pointwise by the transform of the filter and then reverse transform it. Alternatively, a good filter is obtained by simply truncating the transformed data and re-transforming the shortened data set.

Some discrete Fourier transform pairs

Some DFT pairs

${\displaystyle x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}e^{i2\pi kn/N}}$	${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-i2\pi kn/N}}$	Note
${\displaystyle x_{n}e^{i2\pi n\ell /N}\,}$	${\displaystyle X_{k-\ell }\,}$	Frequency shift theorem
${\displaystyle x_{n-\ell }\,}$	${\displaystyle X_{k}e^{-i2\pi k\ell /N}\,}$	Time shift theorem
${\displaystyle x_{n}\in \mathbb {R} }$	${\displaystyle X_{k}=X_{N-k}^{*}\,}$	Real DFT
${\displaystyle a^{n}\,}$	${\displaystyle \left\{{\begin{matrix}N&{\mbox{if }}a=e^{i2\pi k/N}\\{\frac {1-a^{N}}{1-a\,e^{-i2\pi k/N}}}&{\mbox{otherwise}}\end{matrix}}\right.}$	from the geometric progression formula
${\displaystyle {N-1 \choose n}\,}$	${\displaystyle \left(1+e^{-i2\pi k/N}\right)^{N-1}\,}$	from the binomial theorem
${\displaystyle \left\{{\begin{matrix}{\frac {1}{W}}&{\mbox{if }}2n<W{\mbox{ or }}2(N-n)<W\\0&{\mbox{otherwise}}\end{matrix}}\right.}$	${\displaystyle \left\{{\begin{matrix}1&{\mbox{if }}k=0\\{\frac {\sin \left({\frac {\pi Wk}{N}}\right)}{W\sin \left({\frac {\pi k}{N}}\right)}}&{\mbox{otherwise}}\end{matrix}}\right.}$	${\displaystyle x_{n}}$ is a rectangular window function of W points centered on n=0, where W is an odd integer, and ${\displaystyle X_{k}}$ is a sinc-like function (specifically, ${\displaystyle X_{k}}$ is a Dirichlet kernel)
${\displaystyle \sum _{j\in \mathbb {Z} }\exp \left(-{\frac {\pi }{cN}}\cdot (n+N\cdot j)^{2}\right)}$	${\displaystyle {\sqrt {cN}}\cdot \sum _{j\in \mathbb {Z} }\exp \left(-{\frac {\pi c}{N}}\cdot (k+N\cdot j)^{2}\right)}$	Discretization and periodic summation of the scaled Gaussian functions for ${\displaystyle c>0}$. Since either ${\displaystyle c}$ or ${\displaystyle {\frac {1}{c}}}$ is larger than one and thus warrants fast convergence of one of the two series, for large ${\displaystyle c}$ you may choose to compute the frequency spectrum and convert to the time domain using the discrete Fourier transform.

Generalizations

Representation theory

The DFT can be interpreted as a complex-valued representation of the finite cyclic group. In other words, a sequence of ${\displaystyle n}$ complex numbers can be thought of as an element of ${\displaystyle n}$-dimensional complex space ${\displaystyle \mathbb {C} ^{n}}$ or equivalently a function ${\displaystyle f}$ from the finite cyclic group of order ${\displaystyle n}$ to the complex numbers, ${\displaystyle \mathbb {Z} _{n}\mapsto \mathbb {C} }$. So ${\displaystyle f}$ is a class function on the finite cyclic group, and thus can be expressed as a linear combination of the irreducible characters of this group, which are the roots of unity.

From this point of view, one may generalize the DFT to representation theory generally, or more narrowly to the representation theory of finite groups.

More narrowly still, one may generalize the DFT by either changing the target (taking values in a field other than the complex numbers), or the domain (a group other than a finite cyclic group), as detailed in the sequel.

Other fields

Many of the properties of the DFT only depend on the fact that ${\displaystyle e^{-{\frac {i2\pi }{N}}}}$ is a primitive root of unity, sometimes denoted ${\displaystyle \omega _{N}}$ or ${\displaystyle W_{N}}$ (so that ${\displaystyle \omega _{N}^{N}=1}$). Such properties include the completeness, orthogonality, Plancherel/Parseval, periodicity, shift, convolution, and unitarity properties above, as well as many FFT algorithms. For this reason, the discrete Fourier transform can be defined by using roots of unity in fields other than the complex numbers, and such generalizations are commonly called number-theoretic transforms (NTTs) in the case of finite fields. For more information, see number-theoretic transform and discrete Fourier transform (general).

Other finite groups

The standard DFT acts on a sequence x₀, x₁, ..., x_N−1 of complex numbers, which can be viewed as a function {0, 1, ..., N − 1} → C. The multidimensional DFT acts on multidimensional sequences, which can be viewed as functions

${\displaystyle \{0,1,\ldots ,N_{1}-1\}\times \cdots \times \{0,1,\ldots ,N_{d}-1\}\to \mathbb {C} .}$

This suggests the generalization to Fourier transforms on arbitrary finite groups, which act on functions G → C where G is a finite group. In this framework, the standard DFT is seen as the Fourier transform on a cyclic group, while the multidimensional DFT is a Fourier transform on a direct sum of cyclic groups.

Further, Fourier transform can be on cosets of a group.

Alternatives

There are various alternatives to the DFT for various applications, prominent among which are wavelets. The analog of the DFT is the discrete wavelet transform (DWT). From the point of view of time–frequency analysis, a key limitation of the Fourier transform is that it does not include location information, only frequency information, and thus has difficulty in representing transients. As wavelets have location as well as frequency, they are better able to represent location, at the expense of greater difficulty representing frequency. For details, see comparison of the discrete wavelet transform with the discrete Fourier transform.

See also

• Companion matrix
• DFT matrix
• Fast Fourier transform
• FFTPACK
• FFTW
• Generalizations of Pauli matrices
• Least-squares spectral analysis
• List of Fourier-related transforms
• Multidimensional transform
• Zak transform
• Quantum Fourier transform

Notes

References

Further reading

• Brigham, E. Oran (1988). The fast Fourier transform and its applications. Englewood Cliffs, N.J.: Prentice Hall. ISBN 978-0-13-307505-2.
• Smith, Steven W. (1999). "Chapter 8: The Discrete Fourier Transform". The Scientist and Engineer's Guide to Digital Signal Processing (Second ed.). San Diego, Calif.: California Technical Publishing. ISBN 978-0-9660176-3-2.
• Cormen, Thomas H.; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001). "Chapter 30: Polynomials and the FFT". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 822–848. ISBN 978-0-262-03293-3. esp. section 30.2: The DFT and FFT, pp. 830–838.
• P. Duhamel; B. Piron; J. M. Etcheto (1988). "On computing the inverse DFT". IEEE Transactions on Acoustics, Speech, and Signal Processing. 36 (2): 285–286. doi:10.1109/29.1519.
• J. H. McClellan; T. W. Parks (1972). "Eigenvalues and eigenvectors of the discrete Fourier transformation". IEEE Transactions on Audio and Electroacoustics. 20 (1): 66–74. doi:10.1109/TAU.1972.1162342.
• Bradley W. Dickinson; Kenneth Steiglitz (1982). "Eigenvectors and functions of the discrete Fourier transform" (PDF). IEEE Transactions on Acoustics, Speech, and Signal Processing. 30 (1): 25–31. CiteSeerX 10.1.1.434.5279. doi:10.1109/TASSP.1982.1163843. (Note that this paper has an apparent typo in its table of the eigenvalue multiplicities: the +i/−i columns are interchanged. The correct table can be found in McClellan and Parks, 1972, and is easily confirmed numerically.)
• F. A. Grünbaum (1982). "The eigenvectors of the discrete Fourier transform". Journal of Mathematical Analysis and Applications. 88 (2): 355–363. doi:10.1016/0022-247X(82)90199-8.
• Natig M. Atakishiyev; Kurt Bernardo Wolf (1997). "Fractional Fourier-Kravchuk transform". Journal of the Optical Society of America A. 14 (7): 1467–1477. Bibcode:1997JOSAA..14.1467A. doi:10.1364/JOSAA.14.001467.
• C. Candan; M. A. Kutay; H. M.Ozaktas (2000). "The discrete fractional Fourier transform" (PDF). IEEE Transactions on Signal Processing. 48 (5): 1329–1337. Bibcode:2000ITSP...48.1329C. doi:10.1109/78.839980. hdl:11693/11130.
• Magdy Tawfik Hanna, Nabila Philip Attalla Seif, and Waleed Abd El Maguid Ahmed (2004). "Hermite-Gaussian-like eigenvectors of the discrete Fourier transform matrix based on the singular-value decomposition of its orthogonal projection matrices". IEEE Transactions on Circuits and Systems I: Regular Papers. 51 (11): 2245–2254. doi:10.1109/TCSI.2004.836850. S2CID 14468134.CS1 maint: multiple names: authors list (link)
• Shamgar Gurevich; Ronny Hadani (2009). "On the diagonalization of the discrete Fourier transform". Applied and Computational Harmonic Analysis. 27 (1): 87–99. arXiv:0808.3281. doi:10.1016/j.acha.2008.11.003. S2CID 14833478. preprint at.
• Shamgar Gurevich; Ronny Hadani; Nir Sochen (2008). "The finite harmonic oscillator and its applications to sequences, communication and radar". IEEE Transactions on Information Theory. 54 (9): 4239–4253. arXiv:0808.1495. Bibcode:2008arXiv0808.1495G. doi:10.1109/TIT.2008.926440. S2CID 6037080. preprint at.
• Juan G. Vargas-Rubio; Balu Santhanam (2005). "On the multiangle centered discrete fractional Fourier transform". IEEE Signal Processing Letters. 12 (4): 273–276. Bibcode:2005ISPL...12..273V. doi:10.1109/LSP.2005.843762. S2CID 1499353.
• F.N. Kong (2008). "Analytic Expressions of Two Discrete Hermite-Gaussian Signals". IEEE Transactions on Circuits and Systems II: Express Briefs. 55 (1): 56–60. doi:10.1109/TCSII.2007.909865. S2CID 5154718.

External links

• Interactive explanation of the DFT
• Matlab tutorial on the Discrete Fourier Transformation Archived 2016-03-04 at the Wayback Machine
• Interactive flash tutorial on the DFT
• Mathematics of the Discrete Fourier Transform by Julius O. Smith III
• FFTW: Fast implementation of the DFT - coded in C and under General Public License (GPL)
• General Purpose FFT Package: Yet another fast DFT implementation in C & FORTRAN, permissive license
• Explained: The Discrete Fourier Transform
• Discrete Fourier Transform
• Indexing and shifting of Discrete Fourier Transform
• Discrete Fourier Transform Properties
• Generalized Discrete Fourier Transform (GDFT) with Nonlinear Phase