<jupyter_start><jupyter_text>The Discrete-Time Fourier Transform*This Jupyter notebook is part of a [collection of notebooks](../index.ipynb) in the bachelors module Signals and Systems, Comunications Engineering, Universität Rostock. Please direct questions and suggestions to [<EMAIL>](mailto:<EMAIL>).*  DefinitionThe [discrete-time Fourier transform](https://en.wikipedia.org/wiki/Discrete-time_Fourier_transform) (DTFT) of a discrete signal $x[k]$ is defined as\begin{equation}X(e^{j \Omega}) = \sum_{k = -\infty}^{\infty} x[k] \, e^{-j \Omega k}\end{equation}where $\Omega \in \mathbb{R}$ denotes the normalized angular frequency. The DTFT maps a discrete signal $x[k]$ with $k \in \mathbb{Z}$ onto its continuous transform $X(e^{j \Omega}) = \mathcal{F}_* \{ x[k] \}$ with $\Omega \in \mathbb{R}$. It is frequently termed as *spectrum* of the discrete signal $x[k]$. The argument $e^{j \Omega}$ copes for the fact that the kernel $e^{-j \Omega k}$ of the DTFT is a [complex exponential signal](../discrete_signals/standard_signals.ipynbComplex-Exponential-Signal) $z^{-k}$ with $z = e^{j \Omega}$. Other common definitions of the DTFT may be found in the literature. They differ with respect to the sign of the exponential function and normalization factors. The properties, theorems and transforms may differ from the ones given here, as a consequence.A sufficient but not necessary condition for the existence of the DTFT is\begin{equation}\left|X(e^{j \Omega})\right| = \left| \sum_{k = -\infty}^{\infty} x[k] \, e^{-j \Omega k} \right| \leq \sum_{k = -\infty}^{\infty} \left| x[k] \right| < \infty\end{equation}where the upper bound results from the [triangle inequality](https://en.wikipedia.org/wiki/Triangle_inequality). As sufficient condition for the existence of the DTFT, it follows that a signal $x[k]$ needs to be absolutely summable.The DTFT is periodic with a period of $T_\text{p} = 2 \pi$,\begin{equation}X(e^{j \Omega}) = X(e^{j (\Omega + n \cdot 2 \pi)})\end{equation}for $n \in \mathbb{Z}$. This follows from the periodicity of its exponential kernel $e^{j \Omega k} = e^{j (\Omega + 2 \pi) k}$ for discrete $k \in \mathbb{Z}$. It is therefore sufficient to regard the DTFT in one period only. Typically the period $-\pi < \Omega < \pi$ is chosen. The information on the discrete signal $x[k]$ is contained in one period. As a consequence, the inverse discrete-time Fourier transform $x[k] = \mathcal{F}_*^{-1} \{ X(e^{j \Omega}) \}$ is defined as\begin{equation}x[k] = \frac{1}{2 \pi} \int_{-\pi}^{\pi} X(e^{j \Omega}) \, e^{j \Omega k} \; d \Omega\end{equation}  Transformation of the Dirac ImpulseThe transform $\mathcal{F}_* \{ \delta[k] \}$ of the [Dirac impulse](../discrete_signals/standard_signals.ipynbDirac-Impulse) is derived by introducing $\delta[k]$ into the definition of the DTFT and exploiting the sifting property of the Dirac impulse\begin{equation}\mathcal{F}_* \{ \delta[k] \} = \sum_{k = -\infty}^{\infty} \delta[k] \, e^{-j \Omega k} = 1\end{equation}The transform of the Dirac impulse is equal to one. Hence, all normalized frequencies $\Omega$ are present with equal weight. This is an important property in the theory of discrete signals and systems, since the Dirac impulse is used to characterize linear time-invariant (LTI) systems by their [impulse response](../discrete_systems/impulse_response.ipynb) $h[k] = \mathcal{H} \{ \delta[k] \}$. **Exercise*** Derive the DTFT of a shifted Dirac impulse $\delta[k - \kappa]$.  Transformation of the Rectangular SignalThe DTFT $X(e^{j \Omega}) = \mathcal{F}_* \{ \text{rect}_N[k] \}$ of the [rectangular signal](../discrete_signals/standard_signals.ipynbRectangular-Signal) is derived by introducing its definition into the definition of the DTFT. This results in\begin{equation}\mathcal{F}_* \{ \text{rect}[k] \} = \sum_{k = -\infty}^{\infty} \text{rect}[k] \, e^{-j \Omega k} =\sum_{k = 0}^{N-1} e^{-j \Omega k} = e^{-j \Omega \frac{N-1}{2}} \cdot \frac{\sin \left(\frac{N \Omega}{2} \right)}{\sin \left( \frac{\Omega}{2} \right)}\end{equation}The latter equality has been derived by noting that the sum constitutes a [finite geometrical series](https://en.wikipedia.org/wiki/Geometric_series) with the common ratio $e^{-j \Omega}$. Note, that\begin{equation}\frac{\sin \left(\frac{N \Omega}{2} \right)}{\sin \left( \frac{\Omega}{2} \right)} \bigg\rvert_{\Omega = n \cdot 2 \pi} = N \end{equation}for $n \in \mathbb{Z}$ due to [L'Hôpital's rule](https://en.wikipedia.org/wiki/L'H%C3%B4pital's_rule). **Example**The DTFT $X(e^{j \Omega}) = \mathcal{F}_* \{ \text{rect}_N[k] \}$ of the rectangular signal is computed for a specific length $N$ by evaluating the finite series above using `SymPy`.<jupyter_code>%matplotlib inline
import sympy as sym
sym.init_printing()

W = sym.symbols('Omega', real=True)
k = sym.symbols('k', integer=True)

N = 5
X = sym.summation(sym.exp(-sym.I*W*k), (k, 0, N-1))
X<jupyter_output><empty_output><jupyter_text>The magnitude $|X(e^{j \Omega})|$ and phase $\varphi(e^{j \Omega}) = \arg \{ X(e^{j \Omega}) \}$ of the spectrum is plotted for illustration<jupyter_code>sym.plot(sym.Abs(X), (W, -3*sym.pi, 3*sym.pi), xlabel=r'$\Omega$', ylabel=r'$| X(e^{j \Omega}) |$')
sym.plot(sym.arg(X), (W, -3*sym.pi, 3*sym.pi), xlabel=r'$\Omega$', ylabel=r'$\varphi(e^{j \Omega})$');<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.17054409005628518, 'fraction_numerical': 0.004690431519699813, 'mean_word_length': 4.647245762711864, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 11, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '297777', 'license': 'MIT', 'n_tokens_mistral': 1767, 'n_tokens_neox': 1701, 'n_words': 589, 'path': 'discrete_time_fourier_transform/definition.ipynb', 'repo_name': 'swchao/signalsAndSystemsLecture', 'size': '5370'}