{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbsphinx": "hidden"
   },
   "source": [
    "# The Discrete 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": [
    "## Summary of Properties, Theorems and Transforms\n",
    "\n",
    "The [properties](properties.ipynb), [theorems](theorems.ipynb) and transforms of the discrete Fourier transform (DFT) as derived in the previous sections are compiled in the following. The corresponding tables serve as a reference for the application of the DFT in the theory of signals and systems. Please refer to the respective sections for details."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Definition\n",
    "\n",
    "The DFT of length $N$ and its inverse are defined as\n",
    "\n",
    "\\begin{align}\n",
    "X[\\mu] &= \\sum_{k = 0}^{N-1} x[k] \\, e^{- j \\mu \\frac{2 \\pi}{N} k} \\\\\n",
    "x[k] &= \\sum_{k = 0}^{N-1} X[\\mu] \\, e^{j \\mu \\frac{2 \\pi}{N} k}\n",
    "\\end{align}\n",
    "\n",
    "for $k, \\mu \\in \\mathbb{Z}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Properties and Theorems\n",
    "\n",
    "Under the assumption of causal signals of finite length $N$ or peridic signals of period $N$, the properties and theorems of the DTFT are given as\n",
    "\n",
    "|  | $x[k]$ | $X[\\mu] = \\text{DFT}_N \\{ x[k] \\}$ |\n",
    "|:---|:---:|:---:|\n",
    "| [Linearity](properties.ipynb#Linearity) | $A \\, x_1[k] + B \\, x_2[k]$ | $A \\, X_1[\\mu] + B \\, X_2[\\mu]$ |\n",
    "| [Real-valued signal](properties.ipynb#Real-valued-signals) | $x^*[k]$ | $X^*[N-\\mu]$ |\n",
    "| [Convolution](theorems.ipynb#Convolution-Theorem) | $x[k] \\circledast_N h[k]$ | $X[\\mu] \\cdot H[\\mu]$ |\n",
    "| [Periodic shift](theorems.ipynb#Shift-Theorem) | $x[k - \\kappa]$ | $e^{-j \\mu \\frac{2 \\pi}{N} \\kappa} \\cdot X[\\mu]$ |\n",
    "| [Multiplication](theorems.ipynb#Multiplication-Theorem) | $x[k] \\cdot h[k]$ | $\\frac{1}{N} X[\\mu] \\circledast_{N} H[\\mu]$ |\n",
    "| [Modulation](theorems.ipynb#Modulation-Theorem) | $e^{j M \\frac{2 \\pi}{N} k} \\cdot x[k]$ | $X[\\mu - M]$ |\n",
    "| [Parseval's Theorem](theorems.ipynb#Parseval's-Theorem) | $\\sum_{k = 0}^{N-1} \\lvert x[k] \\rvert^2$ | $\\frac{1}{N} \\sum_{\\mu = 0}^{N-1} \\lvert X[\\mu] \\rvert^2$ |\n",
    "\n",
    "\n",
    "where $A, B \\in \\mathbb{C}$ and $\\kappa, M \\in \\mathbb{Z}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Selected Transforms\n",
    "\n",
    "DFTs which are frequently used are given as\n",
    "\n",
    "| $x[k]$ | $X[\\mu] = \\text{DFT}_N \\{ x[k] \\}$ |\n",
    "|:---:|:---:|\n",
    "| $\\delta[k]$ | $1$ |\n",
    "| $1$ | $N \\cdot \\delta[\\mu]$ |\n",
    "| $e^{j \\Omega_0 k}$ | $e^{j (\\Omega_0 - \\mu \\frac{2 \\pi}{N} ) \\frac{N-1}{2} } \\cdot \\frac{\\sin \\left( \\frac{N (\\Omega_0 - \\mu \\frac{2\\pi}{N})}{2} \\right)}{\\sin \\left( \\frac{ \\Omega_0 - \\mu \\frac{2\\pi}{N}}{2} \\right)}$ |\n",
    "| $\\text{rect}_M[k]$ | $e^{-j \\pi \\mu \\frac{M-1}{N} } \\cdot \\frac{\\sin \\left( \\frac{M \\pi \\mu}{N} \\right)}{\\sin \\left( \\frac{ \\pi \\mu}{N} \\right)}$ |\n",
    "\n",
    "\n",
    "\n",
    "where $0 \\leq \\Omega_0 < 2 \\pi$ and $0 < M \\leq N$. Additional transforms may be found in the literature or [online](https://en.wikipedia.org/wiki/Discrete_Fourier_transform#Some_discrete_Fourier_transform_pairs)."
   ]
  },
  {
   "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 (ipykernel)",
   "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}