Editing Discrete-time Fourier transform (section)

== Periodic data ==
When the input data sequence <math>s[n]</math> is <math>N</math>-periodic, {{EquationNote|Eq.2}} can be computationally reduced to a discrete Fourier transform (DFT), because''':'''
* All the available information is contained within <math>N</math> samples.
* <math>S_{1/T}(f)</math> converges to zero everywhere except at integer multiples of <math>1/(NT),</math> known as [[harmonic]] frequencies.  At those frequencies, the DTFT diverges at different frequency-dependent rates.  And those rates are given by the DFT of one cycle of the <math>s[n]</math> sequence.
* The DTFT is periodic, so the maximum number of unique harmonic amplitudes is <math>(1/T)/(1/(NT)) = N.</math>

The DFT of one cycle of the <math>s[n]</math> sequence is''':'''

:<math>S[k] \triangleq \underbrace{\sum_{N} s[n]\cdot e^{-i 2 \pi \frac{k}{N}n}}_{\text{any n-sequence of length N}}, \quad k \in \mathbf{Z}.</math>

And <math>s[n]</math> can be expressed in terms of the inverse transform, which is sometimes referred to as a '''[[Discrete Fourier series]]''' (DFS)''':'''<ref name="Oppenheim" />{{rp|p 542}}

:<math>s[n] = \frac{1}{N}  \underbrace{\sum_{N} S[k]\cdot e^{i 2 \pi \frac{k}{N}n}}_{\text{any k-sequence of length N}}, \quad n \in \mathbf{Z}.</math>
With these definitions, we can demonstrate the relationship between the DTFT and the DFT''':'''

:<math>
\begin{align}
S_{1/T}(f) &\triangleq \sum_{n=-\infty}^{\infty} s[n]\cdot e^{-i 2\pi f nT}\\
&= \sum_{n=-\infty}^{\infty} \left[\frac{1}{N}  \sum_{k=0}^{N-1} S[k]\cdot e^{i 2 \pi \frac{k}{N}n}\right] \cdot e^{-i 2\pi f n T}\\
&= \frac{1}{N} \sum_{k=0}^{N-1} S[k] \underbrace{\left[\sum_{n=-\infty}^{\infty} e^{i 2 \pi \frac{k}{N}n} \cdot e^{-i 2\pi f n T}\right]}_{\operatorname{DTFT}\left(e^{i 2 \pi \frac{k}{N}n}\right)}\\
&= \frac{1}{N} \sum_{k=0}^{N-1} S[k] \cdot \frac{1}{T}\sum_{M=-\infty}^\infty \delta \left(f - \tfrac{k}{NT} - \tfrac{M}{T} \right)
\end{align}
</math>&nbsp; &nbsp; &nbsp; {{efn-la
|Oppenheim and Schafer,<ref name=Oppenheim/> p 551 (8.35), and Prandoni and Vetterli,<ref name=Prandoni/> p 82, (4.43).  With definitions''':''' &nbsp;<math>\tilde{X}(e^{i\omega}) \triangleq \tfrac{1}{T} S_{2\pi}(\omega),</math> &nbsp; <math>\omega \triangleq 2\pi f T,</math>&nbsp; <math>\tilde{X}[k] \triangleq S[k],</math>&nbsp; and &nbsp;<math>\delta\left(2\pi fT - \tfrac{2\pi k}{N}\right) \equiv \delta\left(f - \tfrac{k}{NT}\right)/(2\pi T),</math> this expression differs from the references by a factor of <math>2\pi</math> because they lost it in going from the 3rd step to the 4th.  Specifically, the DTFT of <math>e^{-ian}</math> at {{slink||Table of discrete-time Fourier transforms}} has a <math>2\pi</math> factor that the references omitted.
}}{{efn-ua
|From {{slink||Table of discrete-time Fourier transforms}} we have:
:<math>
\begin{align}
\operatorname{DTFT}\left( e^{i 2 \pi \frac{k}{N}n} \right) 
&= 2\pi \sum_{M=-\infty}^{\infty} \delta \left(\omega - 2 \pi \frac{k}{N} -2\pi M\right)\\
&= 2\pi \sum_{M=-\infty}^{\infty} \delta \left(2\pi f T -2 \pi \frac{k}{N} -2\pi M\right)\\
&=2\pi \sum_{M=-\infty}^{\infty} 
\tfrac{1}{2\pi T}\  \delta \left( \tfrac{1}{2\pi T} \left( 2\pi f T -2 \pi \frac{k}{N} -2\pi M \right) \right)\\
&=\frac{1}{T} \sum_{M=-\infty}^\infty \delta \left(f - \tfrac{k}{NT} - \tfrac{M}{T} \right)
\end{align}
</math>
}}

Due to the <math>N</math>-periodicity of both functions of <math>k,</math> this can be simplified to''':'''

:<math>S_{1/T}(f) = \frac{1}{NT} \sum_{k=-\infty}^{\infty} S[k] \cdot \delta\left(f-\frac{k}{NT}\right),</math>

which satisfies the inverse transform requirement''':'''

:<math>\begin{align}
s[n] &= T \int_{0}^{\frac{1}{T}} S_{1/T}(f)\cdot e^{i 2 \pi f nT} df\\
&=\frac{1}{N} \sum_{k=-\infty}^\infty S[k] \underbrace{\int_{0}^{\frac{1}{T}} \delta \left(f-\tfrac{k}{NT}\right) e^{i 2 \pi f nT} df}_{\text{zero for } k\ \notin\ [0,N-1]}\\
&=\frac{1}{N} \sum_{k=0}^{N-1} S[k] \int_{0}^{\frac{1}{T}} 
\delta \left(f-\tfrac{k}{NT}\right) e^{i 2 \pi f nT} df\\
&=\frac{1}{N} \sum_{k=0}^{N-1} S[k]\cdot e^{i 2 \pi \tfrac{k}{NT} nT}\\
&=\frac{1}{N} \sum_{k=0}^{N-1} S[k]\cdot e^{i 2 \pi \tfrac{k}{N} n}
\end{align}
</math>