{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbsphinx": "hidden"
   },
   "source": [
    "# The Discrete-Time Fourier Transform\n",
    "\n",
    "*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 [Sascha.Spors@uni-rostock.de](mailto:Sascha.Spors@uni-rostock.de).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Properties\n",
    "\n",
    "The discrete-time Fourier transform (DTFT) has a number of specific properties that are reviewed in the following."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Invertibility\n",
    "\n",
    "For many types of signals it is possible to recover the discrete signal $x[k]$ from its DTFT $X(e^{j \\Omega}) = \\mathcal{F}_* \\{ x[k] \\}$\n",
    "\n",
    "\\begin{equation}\n",
    "x[k] = \\mathcal{F}_*^{-1} \\left\\{ \\mathcal{F}_* \\{ x[k] \\} \\right\\}\n",
    "\\end{equation}\n",
    "\n",
    "A sufficient condition for the theorem to hold is that both the signal $x[k]$ and its DTFT are absolutely summable/integrable. For this type of signals, above relation can be proven by applying the definition of the DTFT and its inverse and rearranging terms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example**\n",
    "\n",
    "The invertibility of the DTFT is illustrated at the example of the [complex exponential signal](../discrete_signals/standard_signals.ipynb#Complex-Exponential-Signal) $x[k] = e^{j \\Omega_0 k}$ [whose DTFT is given as](definition.ipynb#Transformation-of-the-Exponential-Signal) $X(j \\omega) = {\\bot \\!\\! \\bot \\!\\! \\bot} ( \\frac{\\Omega - \\Omega_0}{2 \\pi} )$. Note that the signal nor its spectrum are absolutely integrable. However, the invertibility still holds as is shown by evaluating the [integral of the inverse DTFT](definition.ipynb#Definition). Since the integration is only performed in the range $\\Omega = -\\pi$ to $\\pi$, it is sufficient to consider a single Dirac impulse $2 \\pi \\cdot \\delta(\\Omega - \\Omega_0)$ instead of the Dirac comb for the computation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWwAAAAvCAYAAADHJPDPAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAMQElEQVR4Ae2djZHVNhDHcwwFENIBdHCBCgId5KOCJB2QoQKGdAAdMNAB6SCBDnKpIIEOLv+fkHSSnj+fZZ/83mrGZ2u1Wq3+Wq3lte754vr6+quW0sXFxT3pc196XbWkl+liCNRGwGy9NqKnL+9ug118Lp3+1fF7qpuM+5ny3+j429O/1fmDHPtrn598kqxfxPybjleqn7UzWYgxGgLLEVjV1s3Olw9QaxIuWlthlwD5Vcg/ov9WOmeVvRL9gehPy3pjedX9JJ4fVPePMV4rNwS2QGANWzc732LktmtjDw77veAgRMKK+iDJIInp4Mwnr5RV54Hq/K06FwcCVyDQnto66xCPYTBuWMKoqq2bnY9j3iLH0Fy504rCUvKJjmc63hY6PVL+r4KWZnGEc1fYT1THrawBx7fLar16QraEXlYXvD+BDuf9qV1fY9nEVrZudl5/+LaQ2DtXYgwbxyVNiOuScJL/6WDl+hHCBgmn+0LHS+lyT+1+9m3irNGtL1H2rq+wh05b732fcabEwf9R/mXfSlhlIYZOey+m4KI634v3G/FOXv2L/9aT1xuMwvsCdHqsg5j/USEk6knuJbJ1PXe8aL9akg7nYusnYedr2GM1Y1pB0OBcUSFNYsBvuQ6H8i91UPgk0NY6qw3aZ3cIDo5QRaoHNJFuaOFadJwtOhJycHW41oHu1OMcyxIe4teU/ZLQLsN1eRYfj6qOV2f0zHQs+cl7Pl6Kxr60fi2dwe6DDvrLTTPqTt6XUZ6VpXxj117G0fXH5I+Vq/2zsXX1ddd27sdqVXscs5fbLO+aK8HJEYY4mER+wD9tpbTaw1E8K9sTDf2icw3lohHGyPiVz5xkR54Ji0elLkevo6YdJRz7+9Cmp1EwVg/ZBzqnclq7lr6sqJnkB7bg+43Tpu8ZxnP6obrs0GGlHm8GW16r7bOwdfVz93auPqxuj1va3ty21P+DuRIcNpOUiZhNVOUxbugHq9S5jY/x07Zvi3N0hrTtyzKniTwlR9PZ8Xu+7AYjWuaAlAeEUI8Yn1st63zQR9HCCj57yhCdxnm073U6Ks/0GOJtoUz6EvKhX4POVOXBJo6+GUlGNiZb9t+3TT9P2tbVv13bufTfzB63tL+5bXl7jbZ6RwQScckrCfvscod/cKJrJ5znR6/DT0ljxNHR662PPboiH9cKMffAf1+FxN7TRB6nH5KL6/lMyvtrYEjOz3UNLjFuq3Zx4iTa6kzioS972xUCLiQeQYfSn74w8A/x9pWBzY99hSvTz8XW927nwb62sMeVTW6R+GyuOIcth8R+5IcdYp1zUll88ShnxE6OTzquBw7CAVkS7z0dvFCkPscrHemNwE0kylQxrf9INLfyEz11vFx/8GWhLRxw6UjJpzci6rmXXr5fHyWD1cgbHTGJhm7EwVNdKA86DDnkH8QXnTyV0iTZR2GYyljhusRtrIl07MZ4y3KwCROyLFs1f0a2fut2vnAgt7THhaoOV18437O5EneJlE2qkUvRGPSwiv1KNOK5JBwSE5adAzi6Rz7vnFTq4EWnHitOHB83Buf8vfznojn5ouNUkZsl0Tv3X4vOzots9wUyJLd0pKyQI62Up/xBm14BnDipdLz0mRRlfslmf8GjdPSO4VgMM+nrZOgnY951405bDOW8bzg2EZvEJppI3hZPytZv284rDOyW9lhB3W4RFeZ7Plc0sJ1xWDUPY4xn6prJHOO2umYl7OK+/jrGnVOZ8OhghZzFPH2dLDac1jv22rfHjaV3l8gU2aqPQ0JvYrbpAW0wPq1ysItYhfZEOwrDUH/Ns3QL4zT4QtH3DQxiXA29lMCcA7tge2SnXXlexmZ0p82QjJpl6KLjLG1d/a5u5zXGRnptZo819O2SoT4snu+Skc2VzkklJlaH0YB7lIkvAcWLQ8smcKgjejAIJrKbzDozsas769BmjbP048VY7CMylXiq4CLbmVK2p3LqjvZPPFG+rnsx7JCPHsT2cDRTj84baipbshiXA2cceFQWJlHWf18v0pRn9Rz7FuqHs8owZGX7nTplSqv0M21XbZy1rav/q9h5jbGTjE3sMdhDDZ2DrK6z5Mc5oetJ81182Vw5cNhiIBQw5qwREvdt67p3taQyZl7k7epIizSvd3RC6KgENr0OLfRDPKMOWzyTMQxytzhLL24A2dNQaFd0brgHK3DR6G92Q1AenA523iBLCYc++JQS2lzzLB3O3taFAQOymp0vHT/ptro9LtVxSn3146j5rnrZXLkjQkyKt7D8figF4o4J0fg3SVZWaaL8TUIoy5MidzkU7y15bz2v/rKyI8WXrV+yLt7+Wvh89vm+E/0NMvp45mLYJ6cKPekzMf04/oVwduO4mH+wCX+mryUm5DHSrgQ/L4hvLUnvs7f1ZMzXtPOjxjjRbQt7PErHmZWOne/ZXIkOWwAxuR7LGcWXjF4hDDtOLg8kK5PsZZzofS+Rep216iC7udTlkL2u96VsiU+X/uDVexM7AsOuNmrTeAHMExeT98rrGNtQnv78pfIwnsGpY1CkaCNfsi4PXl0JepDTVb4qTX0xWxfCa9v5wkHc0h4XqjpcfeF8z+bKXZryk5GYCr/3QEwvJJh51E13Y+Csw37pwMdqim1amRP3hcShwuR2JN8B6BytJrb+Oaeb6Ptdl5F3dACnF3aTdBS7R/E5GHbJqE3jSYqxxfHiTOk7/QiJPLtwuMliF8FRh/LyPMTDzp8lu0zKtibnpT/9MFu/QWxNO79pZf7VlvY4X7t5Neb6zFR6Nlecw1YpBowhI7hM6aSlDMf8omDqctSORQ7uNQ5PB87531BP9MyJB3pD55+li9s3rjNb2Z5K56mrQpxReuNTNkuzMMxqrpehb6nOfyqfjj32QQw7pPCkwc2ahIMO1+Rx6H148TR2Wzdrs3VG5yataec3rcy/2tIe52s3r8aS+Z7NleZ/D3seLu1w6wbFy5K477wdzepror7y0pGnj+jgReNlFu9DMqctOo6ft+VhP3d9hUziZgi0aOdz7HEzoI5oqGuu3DlCjlWZhgAryNafIqb1ZJyLn6dlJeCSDI1rQj6Zs/bFrMxva3XtVbBTRQRatPM59lgRiuqiDuaKrbCrY3wjUI6L0MivPY7rhvEErtTX4IQJe7F6Dr8BE3vnVwxsGeUR0dKJINCinU+xx5bh75sr5rBXHDWBThyXPejmoASEn9iEidJY94ojYKK3QMDsvD7KfXPFHHZ9rDOJAp6YLf/1OPvr7pmgnWeEAy+0/xAOXWGSnffO1Dc7r2cDQ3PFHHY9nE2SIWAIGAKrImAvHVeF14QbAoaAIVAPAXPY9bA0SYaAIWAIrIrAhaS7X+NZtRUTbggYAoaAIbAYAYthL4bQBBgChoAhsA0CFhLZBmdrxRAwBAyBxQiYw14MoQkwBAwBQ2AbBMxhb4OztWIIGAKGwGIEzGEvhtAEGAKGgCGwDQJ3t2nGWjEE6iHg/6su/LzrI0n+Twe/XRJ/LbBeaybJEGgHAXPY7YyFaTIBAe+s+Sq7+1QZVUTjh6c+6Mxvlvf+NvsE8cZiCDSNgG3ra3p4TLkSATllPkDwsxxz9gNSovOb3Hz26uuyjuUNgVNBwGLYpzKS59MPfmv7kxw0v4SYJlbWfNnoQUq0a0PglBAwh31Ko3kefcExX5Ur7KTrpSNPiuzSENg3Auaw9z1+Z6e9HDW/p931ebFLwFBZfPGo1fYzQiU6rgeO9DuWZ4endXhfCNhLx32Nl2nbgYCcMc6aUEjYORJeRMLNy0lW3XzF/o0OdpWQdy8nUwcvmiVDoGkE7KVj08Njyk1BQA6bDx7zcQT3Dc3gwJV/R33l+dr7O+Wv/DW8cSUOjyVDYA8ImMPewyiZjr0IyAG7kEZw1l2M4uEr7e4zbbru3GXSVc9ohkBrCFgMu7URMX0mIyDny2fHiFv3fp1ePIRLPidCL8Wf5pMiuzQE2kbAHHbb42Pa9SAgR/y9ih6mzlq0BxxFFZw5seuQyvJAt7Mh0DwC5rCbHyJTsETAr5ofy1nHl4yeByfOv6m7JD5eLrqP/3pSoLOX25IhsDsELIa9uyE7b4X9Cvq9UCj/Bf2+aIQ74pY/8fKy8SfRvg2oicZ/RL7ucPaBxc6GQLMI2La+ZofGFOtBgJeGhDVc/LrgKXd+8KLxRcFTOvqi2LKGQLsI/A/U+byDGD2AsgAAAABJRU5ErkJggg==\n",
      "text/latex": [
       "$\\displaystyle \\frac{2 \\pi e^{i \\Omega_{0} k} \\theta\\left(\\pi - \\Omega_{0}\\right) - 2 \\pi e^{i \\Omega_{0} k} \\theta\\left(- \\Omega_{0} - \\pi\\right)}{2 \\pi}$"
      ],
      "text/plain": [
       "     ⅈ⋅Ω₀⋅k                          ⅈ⋅Ω₀⋅k                   \n",
       "2⋅π⋅ℯ      ⋅Heaviside(π - Ω₀) - 2⋅π⋅ℯ      ⋅Heaviside(-Ω₀ - π)\n",
       "──────────────────────────────────────────────────────────────\n",
       "                             2⋅π                              "
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import sympy as sym\n",
    "%matplotlib inline\n",
    "sym.init_printing()\n",
    "\n",
    "k = sym.symbols('k', integer=True)\n",
    "W, W0 = sym.symbols('Omega Omega0', real=True)\n",
    "\n",
    "X = 2*sym.pi*sym.DiracDelta(W - W0)\n",
    "x = 1/(2*sym.pi) * sym.integrate(X * sym.exp(sym.I*W*k), (W, -sym.pi, sym.pi))\n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This result includes the restriction of the normalized angular frequency to $-\\pi < \\Omega_0 < \\pi$ due to the usage of a single Dirac impulse instead of the Dirac comb. The result is specialized to $\\Omega_0 = \\frac{1}{2}$ in order to show that above result indeed constitutes a complex exponential signal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAABoAAAAWCAYAAADeiIy1AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABt0lEQVRIDb2VgVHDMAxFCccA5digbNAyQtmAMgIjwDFC2aArUDYoI0A3KBtwsEH4L0g+JxFHnHLoTrFsSd+WIstVXddHf0lVVa2FdyHceY57nE9KZYG+Bj5brb101w/aqHtqA7/U2DtANSZ1iuRKYFOA5f/A6GRRLm2+0DjB5pCI3gRy7htk48xkxkcxETYn4lTFLFf+xSz3ZQ6keCMmkoSbhHzxNxkQ8R470cLtJd+KV2LSuhdjN0U/KnVy/BTATv8D4LzCSOVaetL6JL4WN6kcVQxyLqZRERXvIoeTUiela1Qr+bfUFUfUzUB2ec+ko9oohueeHaXnJCfK8V78bmtU0Z1VmS21B/l8SH/Kqvkzr9pWmrERLKJdUPvpEiKLV24TjdI398QwsGejhOuyb0LI7HbjCnPknqQLmesiWbZ0i9De/xFvCDRR+ICTb2grwF6+v1Xtr/zAIM27tsZmnEzEZxOdcsiafGk7TW9Djnw8dWwUGkRO+Zr8eHvwd256YG6D7J2B3hSSUsLb8yMJZC7mPjpHT0faiNCpukSUquU9znmyHCakziBQLwK/Q6S19XoOg4ytvgBvwdSYmEpeXAAAAABJRU5ErkJggg==\n",
      "text/latex": [
       "$\\displaystyle e^{\\frac{i k}{2}}$"
      ],
      "text/plain": [
       " ⅈ⋅k\n",
       " ───\n",
       "  2 \n",
       "ℯ   "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.subs(W0, sym.S.Half)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linearity\n",
    "\n",
    "The DTFT is a linear operation. For two signals $x_1[k]$ and $x_2[k]$ with transforms $X_1(e^{j \\Omega}) = \\mathcal{F}_* \\{ x_1[k] \\}$ and $X_2(e^{j \\Omega}) = \\mathcal{F}_* \\{ x_2[k] \\}$ the following holds\n",
    "\n",
    "\\begin{equation}\n",
    "\\mathcal{F}_* \\{ A \\cdot x_1[k] + B \\cdot x_2[k] \\} = A \\cdot X_1(e^{j \\Omega}) + B \\cdot X_2(e^{j \\Omega})\n",
    "\\end{equation}\n",
    "\n",
    "with $A, B \\in \\mathbb{C}$. The DTFT of a weighted superposition of discrete signals is equal to the weighted superposition of the individual DTFTs. This property is useful to derive the DTFT of signals that can be expressed as superposition of other signals for which the DTFT is known or can be calculated easier. Linearity holds also for the inverse DTFT."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Transformation of the cosine and sine signal\n",
    "\n",
    "The DTFT of $\\cos(\\Omega_0 k)$ and $\\sin(\\Omega_0 k)$ is derived by expressing both as harmonic exponential signals using [Euler's formula](https://en.wikipedia.org/wiki/Euler's_formula)\n",
    "\n",
    "\\begin{align}\n",
    "\\cos(\\Omega_0 k) &= \\frac{1}{2} \\left(  e^{-j \\Omega_0 k} + e^{j \\Omega_0 k} \\right) \\\\\n",
    "\\sin(\\Omega_0 k) &= \\frac{j}{2} \\left( e^{-j \\Omega_0 k} - e^{j \\Omega_0 k}  \\right)\n",
    "\\end{align}\n",
    "\n",
    "together with the DTFT $\\mathcal{F}_* \\{ e^{j \\Omega_0 k} \\} = {\\bot \\!\\! \\bot \\!\\! \\bot} ( \\frac{\\Omega - \\Omega_0}{2 \\pi} )$ of the complex exponential signal yields\n",
    "\n",
    "\\begin{align}\n",
    "\\mathcal{F} \\{ \\cos(\\Omega_0 k) \\} &= \\frac{1}{2} \\left[ {\\bot \\!\\! \\bot \\!\\! \\bot} \\left( \\frac{\\Omega + \\Omega_0}{2 \\pi} \\right) + {\\bot \\!\\! \\bot \\!\\! \\bot} \\left( \\frac{\\Omega - \\Omega_0}{2 \\pi} \\right)  \\right] \\\\\n",
    "\\mathcal{F} \\{ \\sin(\\Omega_0 k) \\} &= \\frac{j}{2} \\left[ {\\bot \\!\\! \\bot \\!\\! \\bot} \\left( \\frac{\\Omega + \\Omega_0}{2 \\pi} \\right) - {\\bot \\!\\! \\bot \\!\\! \\bot} \\left( \\frac{\\Omega - \\Omega_0}{2 \\pi} \\right)  \\right]\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Symmetries\n",
    "\n",
    "In order to investigate the symmetries of the DTFT $X(e^{j \\Omega}) = \\mathcal{F}_* \\{ x[k] \\}$ of a signal $x[k]$, first the case of a real valued signal $x[k] \\in \\mathbb{R}$ is considered. The results are then generalized to complex signals $x[k] \\in \\mathbb{C}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Real valued signals\n",
    "\n",
    "Decomposing a real valued signal $x[k] \\in \\mathbb{R}$ into its even and odd part $x[k] = x_\\text{e}[k] + x_\\text{o}[k]$ and introducing these into the definition of the DTFT yields\n",
    "\n",
    "\\begin{align}\n",
    "X(e^{j \\Omega}) &= \\sum_{k = -\\infty}^{\\infty} \\left( x_\\text{e}[k] + x_\\text{o}[k] \\right) e^{-j \\Omega k} \\\\\n",
    "&= \\sum_{k = -\\infty}^{\\infty} \\left( x_\\text{e}[k] + x_\\text{o}[k] \\right) \\cdot \\left( \\cos(\\Omega k) - j \\sin(\\Omega k) \\right) \\\\\n",
    "&= \\underbrace{\\sum_{k = -\\infty}^{\\infty} x_\\text{e}[k] \\cos(\\Omega k)}_{X_\\text{e}(e^{j \\Omega})} + \n",
    "j \\underbrace{\\sum_{k = -\\infty}^{\\infty} - x_\\text{o}[k] \\sin(\\Omega k)}_{X_\\text{o}(e^{j \\Omega})}\n",
    "\\end{align}\n",
    "\n",
    "For the last equality the fact was exploited that an infinite series with symmetric limits is zero for odd functions. In order to conclude on the symmetry of $X(e^{j \\Omega})$ its behavior for a reverse of the sign of $\\Omega$ has to be investigated. Due to the symmetry properties of $\\cos(\\Omega k)$ and $\\sin(\\Omega k)$, it follows that the DTFT of the\n",
    "\n",
    "* even part $x_\\text{e}[k]$ is real valued with even symmetry $X_\\text{e}(e^{j \\Omega}) = X_\\text{e}(e^{-j \\Omega})$\n",
    "* odd part $x_\\text{o}[k]$ is imaginary with odd symmetry $X_\\text{o}(e^{j \\Omega}) = - X_\\text{o}(e^{-j \\Omega})$\n",
    "\n",
    "Combining this, it can be concluded that the DTFT $X(e^{j \\Omega})$ of a real-valued signal $x[k] \\in \\mathbb{R}$ shows complex conjugate symmetry\n",
    "\n",
    "\\begin{equation}\n",
    "X(e^{j \\Omega}) = X^*(e^{- j \\Omega})\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Complex Signals\n",
    "\n",
    "By following the same procedure as above for an imaginary signal, the symmetries of the DTFT of the even and odd part of an imaginary signal can be derived. The results can be combined, by decomposing a complex signal $x[k] \\in \\mathbb{C}$ and its DTFT into its even and odd part for both the real and imaginary part. This results in the following symmetry relations\n",
    "\n",
    "![Symmetries of the Fourier transform](symmetries.png)\n",
    "\n",
    "The transformation symbols $\\circ \\!\\! - \\!\\! \\bullet$ illustrate which part of the signal $x[k]$ is related to which part of its spectrum $X(e^{j \\Omega})$. For instance, the odd part of the real part $\\Re \\{ x_\\text{o} [k] \\}$ results in an imaginary spectrum with odd symmetry $\\Im \\{ X_\\text{o} (e^{j \\Omega}) \\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbsphinx": "hidden"
   },
   "source": [
    "**Copyright**\n",
    "\n",
    "This notebook is provided as [Open Educational Resource](https://en.wikipedia.org/wiki/Open_educational_resources). Feel free to use the notebook for your own purposes. The text is licensed under [Creative Commons Attribution 4.0](https://creativecommons.org/licenses/by/4.0/), the code of the IPython examples under the [MIT license](https://opensource.org/licenses/MIT). Please attribute the work as follows: *Sascha Spors, Continuous- and Discrete-Time Signals and Systems - Theory and Computational Examples*."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}