21-11-08 L10.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 10 - FFT\n",
    "Lecture 10 - 08 November 2021\n",
    "\n",
    "## Brief Recap of last lecture\n",
    "```{admonition} Assumption\n",
    "Assume $f(t)$ periodic with period $NT,\\ N\\in\\mathcal{N}^{+}_{even \\neq 0}$ and $\\frac{\\pi}{T}$ band limited.\n",
    "```\n",
    "The following expressions hold:\n",
    "\n",
    "### Fourier Series\n",
    "\\begin{align*}\n",
    "    f(t)=\\sum_{k} a_k e^{-i\\omega_k t} \\qquad \\omega_k=\\frac{2\\pi}{T}k \\qquad \\text{Fourier Series}\\\\\n",
    "    a_k=\\frac{1}{TN}\\int_{-\\frac{NT}{2}}^{\\frac{NT}{2}} f(t) e^{i\\omega_k t}dt \\qquad \\qquad \\text{Fourier Coefficients}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "\n",
    "### Coefficients\n",
    "\\begin{align*}\n",
    "F_k = \\begin{cases}\n",
    "a_k N \\quad &\\text{if } 0\\leq k<\\frac{N}{2} \\\\\n",
    "a_{k-N}N \\quad &\\text{if } \\frac{N}{2}\\leq k<N \\\\\n",
    "\\end{cases} \\quad \\iff \\quad a_k = \\begin{cases}\n",
    "\\frac{F_k}{N} \\quad &\\text{if } 0\\leq k<\\frac{N}{2} \\\\\n",
    "\\frac{F_{k+N}}{N} \\quad &\\text{if } -\\frac{N}{2}\\leq k<0 \\\\\n",
    "\\end{cases}\n",
    "\\end{align*}\n",
    "\n",
    "\n",
    "### Discrete Fourier Transform\n",
    "\\begin{align*}\n",
    "F_k = \\sum_{n=0}^{N-1}f[n]e^{i \\frac{2\\pi}{N}nl}\n",
    "\\end{align*}\n",
    "\n",
    "### Inverse Discrete Fourier Transform\n",
    "\\begin{align*}\n",
    "f[n]=\\frac{1}{N}\\sum_{k=0}^{N-1} F_ke^{-i\\frac{2\\pi}{N}kn}\n",
    "\\end{align*}\n",
    "\n",
    "### Twiddle Factor\n",
    "\\begin{align*}\n",
    "W_N&=e^{i\\frac{2\\pi}{N}}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "_With these expressions in mind it is possible to start developing the \"Radix 2 decimation in time_ **Fast Fourier Transfrom** _(FFT)\"_.\n",
    "\n",
    "## Fast Fourier Transform\n",
    "\n",
    "### Moular property of the Twiddle Factor\n",
    "\\begin{align*}\n",
    "\\require{cancel}\n",
    "W_N^k &=e^{i\\frac{2\\pi}{N}} \\qquad \\text{write } k=k-k \\text{ mod }N + k \\text{ mod }N\\\\\n",
    "&= \\cancelto{1}{e^{i\\frac{2\\pi (k-k \\text{ mod }N) N}{N}}}  e^{2\\pi i \\frac{k \\text{ mod }N}{N}} = W^{k \\text{ mod }N}_N\n",
    "\\end{align*}\n",
    "\n",
    "where the fact that $k-k \\text{ mod }N$ is always an integer multiple of N (by definition) is used.\n",
    "\n",
    "```{admonition} Assumption\n",
    "Assume that $N$ is a power of two, that is $N=2^{\\mu}$; $\\mu = log_2(N)$\n",
    "```\n",
    "and separate the even and odd terms of the DFT:\n",
    "\n",
    "\\begin{align*}\n",
    "F_k = \\sum_{n=0}^{N-1}f_n W^{2nk}_N &= \\sum_{n=0}^{N/2-1}f_{2n}W^{2nk}_{N/2} + \\sum_{n=0}^{N/2-1}f_{2n+1}W_{N/2}^{(2n+1)k} \\\\\n",
    "&= \\sum_{n=0}^{N/2-1}f_{2n}W^{nk}_{N/2} + W^{k}_{N}\\sum_{n=0}^{N/2-1}f_{2n+1}W_{N/2}^{nk}\\\\\n",
    "&= \\sum_{n=0}^{N/2-1}f_{2n}W^{n(k \\text{ mod }\\frac{N}{2})}_{N/2} + W^k_N \\sum_{n=0}^{N/2-1}f_{2n+1}W_{N/2}^{n(k \\text{ mod }\\frac{N}{2})} \\\\\n",
    "&= F_{(k \\text{ mod }\\frac{N}{2})}^{EVEN} + W^{k}_{N}\\ F_{(k \\text{ mod }\\frac{N}{2})}^{ODD}\n",
    "\\end{align*}\n",
    "\n",
    "This relation is, indeed, a recurrence relation. Let's focus on it!\n",
    "\n",
    "\\begin{align*}\n",
    "W^{k}_{N} &= \\begin{cases}\n",
    "    W^{k\\text{ mod } N/2}_N = W^{k}_{N} &\\qquad \\text{if } 0\\leq k < \\frac{N}{2} \\\\\n",
    "    W^{k\\text{ mod } N/2+ N/2}_N   &\\qquad \\text{if } \\frac{N}{2}\\leq k < N \\\\\n",
    "\\end{cases} \\\\\n",
    "&= \\begin{cases}\n",
    "    W^{k\\text{ mod } N/2}_N &\\qquad \\text{if } 0\\leq k < \\frac{N}{2} \\\\\n",
    "    -W^{k\\text{ mod } N/2}_N   &\\qquad \\text{if } \\frac{N}{2}\\leq k < N \\\\\n",
    "\\end{cases}\\\\\n",
    "&= W_{N}^{k\\text{ mod } N/2}\\ \\begin{cases}\n",
    "    1 &\\qquad \\text{if } 0\\leq k < \\frac{N}{2} \\\\\n",
    "    -1   &\\qquad \\text{if } \\frac{N}{2}\\leq k < N \\\\\n",
    "\\end{cases}\n",
    "\\end{align*}\n",
    "where the fact that $W_{N}^{N/2}=e^{i \\frac{2\\pi}{N}\\frac{N}{2}}=e^{i\\pi}= -1$ was used. The final expression is:\n",
    "\\begin{align*}\n",
    "    F_k &= F_{k\\text{ mod }\\frac{N}{2}}^{EVEN} + m(k-\\frac{N}{2}) W^{k\\text{ mod }\\frac{N}{2}}_N F_{k\\text{ mod }\\frac{N}{2}}^{ODD} \\\\\n",
    "    \\text{with }\\quad m(l)&= \\begin{cases}\n",
    "        1 &\\text{ if } l<0 \\\\\n",
    "        -1 &\\text{ if } l\\geq0\n",
    "    \\end{cases}\n",
    "\\end{align*}\n",
    "\n",
    "### Example\n",
    "The formula can be easily recalled by using the \"butterfly diagram\" and assuming the $F$s to be vectors $F_k=\\sum_{n=0}^{N-1}f_n W^{nk}_N$:\n",
    "\n",
    "![Example: Fast Fourier Transform of a cosine](images/21-11-08_example_FFT.jpeg)\n",
    "\n",
    "As a final remark, if the number of point N is _not_ a power of two the simplest way to perform the FFT is to pad the sequence with zeros  or use [windowing](https://en.wikipedia.org/wiki/Window_function)."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Edit 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.8.10"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}