21-09-21 L04.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04 - Inversion of z-transform and the z-space\n",
    "Lecture 04 - 21 September 2021\n",
    "\n",
    "As a starting point, this lecture will provide some examples regarding the inversion of the z-transform:\n",
    "\n",
    "## Examples of z-transform inversion\n",
    "\n",
    "### The delta\n",
    "Let's take $x(z)=1$; $ROC=\\mathcal{C}$:\n",
    "\\begin{align*}\n",
    "    x[n]=\\frac{1}{2\\pi i} \\oint_{\\Gamma um 0}z^{n-1}dz = \\delta_{n-1, -1} = \\delta_{n,0} = \\delta[n]\n",
    "\\end{align*}\n",
    "\n",
    "### A Rational function\n",
    "$X(z)=\\frac{z}{z-a}$, $ROC:\\{z: |z|<a\\}$\n",
    "\\begin{align*}\n",
    "    x[n]=\\frac{1}{2\\pi i} \\oint_{\\Gamma um 0} \\frac{z}{z-a} z^{n-1}dz = \\frac{1}{2\\pi i} \\oint_{\\Gamma um 0} \\frac{z^n}{z-a}dz\n",
    "\\end{align*}  \n",
    "As stated by the ROC, $\\Gamma$ must be chosen so that it DOES not enclose $a$.\n",
    "![Gamma must be chosen so that it does not enclose a. There are two cases.](images/21-09-21_gamma_example1.jpg)\n",
    "\n",
    "At this point there are two subcases to handle depending on the value of n:  \n",
    "1. If $n\\geq 0$: there a NO OTHER POLES and the integral is 0\n",
    "2. If $n<0$: there is a pole of order $|n|$ in the origin. By using the lemma proved in the previous lecture and choosing $m=-n$ we have:  \n",
    "\\begin{align*}\n",
    "        x[n]&=\\frac{1}{(m-1)!}\\left[ \\frac{d^{m-1}}{dz^{m-1}} \\frac{z^{-m}}{z-a}z^{m} \\right]_{z=0} = \\frac{1}{(m-1)!}\\left[ \\frac{d^{m-1}}{dz^{m-1}} \\frac{1}{z-a} \\right]_{z=0} \\\\\n",
    "        &= \\frac{1}{(m-1)!}\\left[ (m-1)! (-1)^{m-1} (z-a)^{-m} \\right]_{z=0} = (-1)^{m-1} (-a)^{-m} = - a^{-m} = -a^{n} \\text{ with } n<0\n",
    "\\end{align*}\n",
    "\n",
    "So that the final result is, by combining the two cases, $x[n]=-U[-n-1]a^n$.\n",
    "\n",
    "### Same rational function, different ROC\n",
    "Let's consider again the same rational function but with a different ROC: $X(z)=\\frac{z}{z-a}$, $ROC:\\{z: |z|>a\\}$. This time there is NO WAY to avoid the pole in $a$. Thanks to the [residue theorem](https://en.wikipedia.org/wiki/Residue_theorem) the contributions from the poles can be separated:\n",
    "\\begin{align*}\n",
    "    x[n] = \\frac{1}{2\\pi i} \\oint_{\\Gamma um 0} \\frac{z^n}{z-a}dz = -a^n U[-n-1] + \\text{ pole in a }\n",
    "\\end{align*}\n",
    "\n",
    "**pole in a** (the order is $m=1$):\n",
    "\n",
    "\\begin{align*}\n",
    "    \\frac{1}{(m-1)!}\\left[ \\frac{d^{m-1}}{dz^{m-1}} \\frac{z^{n}}{z-a}(z-a)^{m} \\right]_{z=a} = \\frac{1}{0!}\\left[ \\frac{d^{0}}{dz^{0}} \\frac{z^{n}}{z-a}(z-a)^{1} \\right]_{z=a} = a^n\n",
    "\\end{align*}\n",
    "\n",
    "Summing up: $x[n]=a^{n}(1-U[-n-1]) = U[n]a^n$.\n",
    "\n",
    "\n",
    "### Poisson process\n",
    "A [poisson process](https://en.wikipedia.org/wiki/Poisson_point_process) is a process where the probability of an event in an interval $dt$ is given by $dP=\\Gamma dt$ and no more than one event can happen in the same time interval. Let's now define $P(n, t)$ as the probability of having $n$ events in an interval $[0, t]$. At time $t=0$ no events can occur and $P(n, t=0)=\\delta_{n,0}$.\n",
    "\n",
    "![Poisson process on an interval](images/21-09-21_poisson_process.jpg)\n",
    "\n",
    "If one considers a slightly bigger interval $[0, t+dt]$, still with $n$ occurrence, the two probabilities are linked via\n",
    "\n",
    "\\begin{align*}\n",
    "    P(n, t+dt) = P(n,t)(1-\\Gamma dt) + P(n-1, t) \\Gamma dt\n",
    "\\end{align*}\n",
    "\n",
    "That is, the probability that in $[0, t]$ happend $n-1$ events and the $n-th$ event happend in the interval $[t, t+dt]$ plus the probability that $n$ events already happened in $[0, t]$ and no new event happend in $[t, t+dt]$.  \n",
    "Let's write the probability as a difference equation and consider the limit $dt\\rightarrow0$:\n",
    "\n",
    "\\begin{align*}\n",
    "    \\frac{P(n, t+dt) - P(n, t)}{dt} = \\Gamma \\left[ P(n-1, t) - p(n, t) \\right] \\implies \\frac{dP(n, t)}{dt} = \\Gamma \\left[ P(n-1, t) - P(n, t) \\right]\n",
    "\\end{align*}\n",
    "\n",
    "By applying the z-transform $\\left( \\Pi(z,t)=Z\\left\\{ P(n, t) \\right\\} \\right)$ and solving the differential equation in the $z-space$:\n",
    "\n",
    "\\begin{align*}\n",
    "    \\Pi(z,t) &= \\sum_{n} z^{-n} P(n,t) \\implies \\frac{d\\Pi(z,t)}{dt} = \\Gamma \\left[ \\frac{\\Pi(z,t)}{z}-\\Pi(z,t) \\right] = \\Gamma\\Pi(z,t) \\left( \\frac{1}{z}-1\\right)\\\\\n",
    "    &\\implies \\Pi(z,t) = \\Pi(z,0)e^{\\Gamma(\\frac{1}{z}-1)t}\n",
    "\\end{align*}\n",
    "\n",
    "where $\\Pi(z,0)$ is given by the condition that no event occurs in the point $t=0$: $\\Pi(z,0)=Z(\\delta[n])=1$ (initial condition in space).\n",
    "\n",
    "It is now necessary to go back to the $n-space$ from the $z-space$. This can be done by Taylor-expanding the exponential depending on $z$:\n",
    "\n",
    "\\begin{align*}\n",
    "    \\Pi(z,t) &= e^{\\Gamma(\\frac{1}{z}-1)t} = e^{-\\Gamma t}e^{\\frac{\\Gamma t}{z}} = e^{-\\Gamma t} \\sum_{k=0}^{+\\infty} \\frac{1}{k!} \\left(\\frac{\\Gamma t}{z}\\right)^k \\\\\n",
    "\\end{align*}\n",
    "\n",
    "and compute the inverse z-transform:\n",
    "\n",
    "\\begin{align*}\n",
    "    P(n,t) &= \\frac{e^{-\\Gamma t}}{2\\pi i} \\oint_{\\Gamma um 0\\\\ \\Gamma\\in ROC} \\sum_{k=0}^{+\\infty} \\frac{1}{k!} \\left(\\frac{\\Gamma t}{z}\\right)^k z^{n-1} dz \\\\\n",
    "    &= \\frac{e^{-\\Gamma t}}{2\\pi i} \\sum_{k=0}^{+\\infty} \\frac{1}{k!} \\oint_{\\Gamma um 0\\\\ \\Gamma\\in ROC} \\left(\\frac{\\Gamma t}{z}\\right)^k z^{n-1} dz \\\\\n",
    "    &= \\frac{e^{-\\Gamma t}}{2\\pi i} \\sum_{k=0}^{+\\infty} \\frac{1}{k!} \\oint_{\\Gamma um 0\\\\ \\Gamma\\in ROC} \\left(\\Gamma t\\right)^k z^{n-1-k} dz \\\\\n",
    "    &= e^{-\\Gamma t} \\sum_{k=0}^{+\\infty} \\frac{\\left(\\Gamma t\\right)^k}{k!} \\frac{1}{2\\pi i} \\oint_{\\Gamma um 0\\\\ \\Gamma\\in ROC}  z^{n-1-k} dz \\\\\n",
    "    &= e^{-\\Gamma t} \\sum_{k=0}^{+\\infty} \\frac{1}{k!} \\left(\\Gamma t\\right)^k \\delta_{n-1-k, -1} = \\frac{\\left(\\Gamma t\\right)^n}{n!} e^{-\\Gamma t} \\\\\n",
    "\\end{align*}\n",
    "Which is the probability mass function of the [Poisson distribution](https://en.wikipedia.org/wiki/Poisson_distribution). The $ROC$ was used when we swapped the integral and the summation.\n",
    "\n",
    "### Fibonacci sequence\n",
    "The Fibonacci frequence is obtained via the following procedure:\n",
    "\\begin{align*}\n",
    "    y[n] &= y[n-1] + y[n-2] + x[n] \\\\\n",
    "    x[n] &= \\delta[n]\n",
    "\\end{align*}\n",
    "\n",
    "An analytical form can be obtained via the z-transform:\n",
    "\\begin{align*}\n",
    "    h[n] &= h[n-1] + h[n-2] + \\delta[n] \\\\\n",
    "    \\implies h(z) &= h(z)\\left( \\frac{1}{z} + \\frac{1}{z^2} +1 \\right) \\\\\n",
    "        &= \\frac{z^2}{z^2-z-1} \\\\\n",
    "        &= \\frac{1}{\\sqrt{5}} \\left[ \\beta \\frac{z}{z-\\beta} - \\alpha \\frac{z}{z-\\alpha}\\right] \\\\\n",
    "        &\\text{ with } \\alpha =\\frac{1+\\sqrt{5}}{2} \\text{ and } \\beta=\\frac{1-\\sqrt{5}}{2} \\quad \\text{ROC:} |z|>\\beta \n",
    "\\end{align*}\n",
    "\n",
    "By inverting the z-transform:\n",
    "\\begin{align*}\n",
    "    h(n) = \\frac{1}{\\sqrt{5}} \\left[ \\beta^{n+1} - \\alpha^{n+1} \\right] U[n]\n",
    "\\end{align*}\n",
    "\n",
    "Let's now make a small detour and check whether the formula found is correct:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Values obtained with the relation:\n",
      " [ 0  1  1  2  3  5  8 13 21 34]\n",
      "\n",
      "Values obtained from scratch with the iterative procedure:\n",
      " [ 0.  1.  1.  2.  3.  5.  8. 13. 21. 34.]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA2cAAAEvCAYAAADB37lNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAlYUlEQVR4nO3df3DV9Z3v8debJCSBpEJBUg1quOikuoBEUpfKWkPdkrilik47S69rB2Ycuruty+5t8ULHuXan1gXZ2nvb7Q+ZYvDuYtMtBXpRV1wHg7AttGCsYBErXaQcRUAamrAhkPC+f+QQCCSQ5HyS8zmH52Mmk5xzvt/zfec1R+HF93s+x9xdAAAAAID0GpLuAQAAAAAAlDMAAAAAiALlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIhA7mAebPTo0V5WVjaYhwzi2LFjGj58eLrHyApkGQ5ZhkGO4ZBlOGQZDlmGQY7hkGU4mZrl9u3bD7v75d09NqjlrKysTNu2bRvMQwZRX1+vqqqqdI+RFcgyHLIMgxzDIctwyDIcsgyDHMMhy3AyNUsze7unx7isEQAAAAAiQDkDAAAAgAhQzgAAAAAgAoP6nrPunDx5Uvv379fx48fTPUqPLrvsMu3atSvdY3QqKCjQ2LFjlZeXl+5RAAAAAASS9nK2f/9+FRcXq6ysTGaW7nG61dTUpOLi4nSPIUlyd73//vvav3+/xo0bl+5xAAAAAASS9ssajx8/rlGjRkVbzGJjZho1alTUZxoBAAAA9F3ay5kkilkfkRcAAACQfS5azsyswMx+YWa/MrPXzezvz3n8W2bWPHAjDrxbbrlFkrR37149/fTTQZ/70Ucf7fZYAAAAALrRdECqvUNqeq9fu69tSGja4g0at/BZTVu8QWsbEoEHHDi9OXPWKunj7n6jpMmSasxsqiSZWaWkkQM33uD42c9+Jql/5aytre2Cj59bzk4fCwAAAEA3Nj4m7dsibVzS513XNiS0aPUOJRpb5JISjS1atHpHxhS0i5Yz73D6zFhe8svNLEfSUkkPDuB85xmIJlxUVCRJWrhwoTZt2qTJkyfrm9/8ptrb27VgwQLddtttmjRpkp544glJHZ9Gfuutt+rOO+/UDTfcIEmaNWuWpkyZoj/6oz/SsmXLOp+vpaVFkydP1r333tvlWLNnz9azzz7bOcOcOXO0atWqzmN+5CMf6XJMAAAAIKs9Mkb66mXStuWSn+r4/tXLOu7vpaXrd6vlZHuX+1pOtmvp+t2hpx0Q5u4X36ijiG2XdK2k77j7/zSz+ZKGuPs3zazZ3Yt62HeepHmSVFJSMqWurq7L45dddpmuvfbaXg377M739NVnf6Pjbac67yvIHaKvfvI6fXJCSa+eoztXXHGF3n33XW3atEnf+ta39OMf/1iSVFtbq0OHDulLX/qS2traNGPGDD311FP63e9+p8985jPasmWLysrKJElHjhzRBz/4QbW0tKiqqkrPPfecRo0a1fnc5x5r3bp1euaZZ/TEE0/oxIkTuvHGG/XKK6+orq5Ohw4d0oMPPqjW1tbOY54+zmlvvfWWjh492u/fOV2am5s7CypSQ5ZhkGM4ZBkOWYZDlmGQYzhk2bOhrUc0fk+tRh/eqpxTrWofkq/Do6dqz/i5OpF//sV63WU55/ljPT7/iprhwWfuj+nTp29398ruHuvVUvru3i5pspmNkLTGzD4m6TOSqnqx7zJJyySpsrLSq6q67rJr165eL1P/7Y2/7FLMJOl42yl9e+M+zf5o7wpeT4qLizVs2DDl5uZ2zvPyyy/rtdde009/+lMNGTJER48e1bvvvqthw4bp5ptv1sSJEzv3/8Y3vqE1a9ZIkhKJhA4cONBZqM79/YqLi3XPPfdo4cKFGjp0qDZs2KDbbrtNY8aM6TzmunXrJKnzmGcfS+r4rLOKioqUfud0qK+v17mvAfQPWYZBjuGQZThkGQ5ZhkGO4ZDlRazbJB3aLOUWKKf9hEquvlYl1Xd3u2l3WZZu2aBEY8t525aOKMyI3Pv0OWfu3mhmL0maro6zaG8lVw4cZmZvuXtqDeki3ukm6Avdnyp317e//W3dcsstXQpWfX29hg8f3uX2iy++qJ///OcaNmyYqqqqLrrUfUFBgaqqqrR+/Xr96Ec/0uzZs7scs7q6ekB+JwAAACBaxw5KU+ZKlXOlbbVSc98WBVlQXa5Fq3d0ubSxMC9HC6rLQ086IHqzWuPlyTNmMrNCSZ+QtN3dP+TuZe5eJum/BrqYSdKVIwr7dH9fFRcXq6mpqfN2dXW1vve97+nkyZOSpDfffFPHjp1/qvTo0aMaOXKkhg0bpjfeeENbtmzpfCwvL69z/3P9+Z//uWpra7Vp0ybV1NT06ZgAAABA1pm9Upr5uPShiR3fZ6/s0+6zKkr1D/dMVOmIQpk6zpj9wz0TNauidGDmDaw3Z86ukPRU8n1nQyT9q7s/M7BjdW+gm/CkSZOUk5OjG2+8UXPmzNH8+fO1d+9e3XrrrTIzXX755Vq7du15+9XU1Oj73/++rr/+epWXl2vq1Kmdj82bN0+TJk3STTfdpJUru764ZsyYofvuu0933XWXhg4dKkm6//77tXfvXt10001y9x6PCQAAAOB8sypKM6aMneui5czdX5N0wTc39bQYSGinQ166frfeaWzRlSMKtaC6POXwm5s7FqPMy8vThg0bujz26KOPatGiRV0ua6yqqupyzWp+fr7+7d/+rdvnXrJkiZYsObMM6OljnT7ekSNHumw/ZMgQPfroo+ctwQ8AAAAgu/XpPWcxyOQmDAAAAAA96c2HUAMAAAAABhjlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIgA5awPioou/IkBjY2N+u53v9t5+5133tGnP/3pgR4LAAAAQBagnJ3D3XXq1Kl+7XtuObvyyiu1atWqUKMBAAAAyGKZWc6aDki1d0hN7wV5ur1796q8vFyf+9znNGHCBH3ta1/TRz7yEU2aNEkPP/zweds3Nzfr9ttv10033aSJEyfqpz/9qSRp4cKF2rNnjyZPnqwFCxZo7969mjBhgiTp+PHjmjt3riZOnKiKigq99NJLkqQVK1bonnvuUU1Nja677jo9+OCDQX4nAAAAAJkl4z6EWpK08TFp3xZp4xJp5uNBnvI3v/mNnnrqKf3hD3/QqlWr9Itf/ELurjvvvFP/8R//oZqams5tCwoKtGbNGn3gAx/Q4cOHNXXqVN15551avHixdu7cqVdffVVSR+k77Tvf+Y7MTDt27NAbb7yhGTNm6M0335Qkvfrqq2poaFB+fr7Ky8v1wAMP6KqrrgryewEAAADIDJlVzh4ZI7W1nrm9bXnHV26+9NDBlJ76mmuu0dSpU/XlL39ZL7zwgioqKiR1nCXbs2dPl23dXV/5ylf08ssva8iQIUokEnrvvQufxdu8ebMeeOABSdKHP/xhXXPNNZ3l7Pbbb9dll10mSbrhhhv09ttvU84AAACAS0xmlbP5r0nrH5LeeEZqa5FyC6XrZ0ozvp7yUw8fPlxSR/FatGiRPv/5z3c+1tTU1GXblStX6tChQ9q+fbvy8vJUVlam48eP9/vY+fn5nT/n5OSora2t388FAAAAIDNl1nvOij8k5RdL7a1SbkHH9/wPSMUlwQ5RXV2tJ598Us3NzZKkRCKhQ4cOddnm6NGjGjNmjPLy8vTSSy/p7bff7hivuPi8InfarbfeqpUrV0qS3nzzTe3bt0/l5eXB5gYAAACQ2TLrzJkkHTsoTZkrVc6VttVKzWEWBTltxowZ2rVrlz760Y9K6lg+//vf/36Xbe6991596lOf0sSJE1VZWakPf/jDkqRRo0Zp2rRpmjBhgu644w594Qtf6Nznr//6r/VXf/VXmjhxonJzc7VixYouZ8wAAAAAXNoyr5zNXnnm50CLgZSVlWnnzp2dt+fPn6/58+d33j59Nuz02bTRo0fr5z//ebfP9fTTT3e5ffp5CwoKVFtbe972c+bM0Zw5czpvP/PMM/37JQAAAABktMy6rBEAAAAAshTlDAAAAAAiQDkDAAAAgAhEUc7cPd0jZBTyAgAAALJP2stZQUGB3n//fQpHL7m73n//fRUUFKR7FAAAAAABpX21xrFjx2r//v3nfZZYTI4fPx5VGSooKNDYsWPTPQYAAACAgNJezvLy8jRu3Lh0j3FB9fX1qqioSPcYAAAAALJY2i9rBAAAAABQzgAAAAAgCpQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIjARcuZmV1lZi+Z2a/N7HUzm5+8/zPJ26fMrHLgRwUAAACA7NWbM2dtkr7k7jdImirpC2Z2g6Sdku6R9PIAzgcAAABkhqYDUu0dUtN7fd51bUNC0xZv0LiFz2ra4g1a25AYgAERu4uWM3d/191fSf7cJGmXpFJ33+Xuuwd6QAAAACAjbHxM2rdF2rikT7utbUho0eodSjS2yCUlGlu0aPUOCtolKLcvG5tZmaQKSVsHZBoAAAAg0zwyRmprPXN72/KOr9x86aGDF9196frdajnZ3uW+lpPtWrp+t2ZVlIaeFhEzd+/dhmZFkjZK+rq7rz7r/npJX3b3bT3sN0/SPEkqKSmZUldXl+rMg665uVlFRUXpHiMrkGU4ZBkGOYZDluGQZThkGQY5XtjQ1iMav6dWow9vVc6pVrUPydfh0VO1Z/xcncgf2WXb7rKc8/yxHp97Rc3wAZk5G2Tq63L69Onb3b3bNTt6debMzPIk/UTSyrOLWW+4+zJJyySpsrLSq6qq+rJ7FOrr65WJc8eILMMhyzDIMRyyDIcswyHLMMixF9Ztkg5tlnILlNN+QiVXX6uS6rvP26y7LEu3bFCiseW8bUtHFJL7BWTj67I3qzWapOWSdrn74wM/EgAAAJBhjh2UpsyV7n+x43tz7xcFWVBdrsK8nC73FeblaEF1eegpEbnenDmbJuk+STvM7NXkfV+RlC/p25Iul/Ssmb3q7tUDMiUAAAAQs9krz/w8s2/nM06/r2zp+t16p7FFV44o1ILqct5vdgm6aDlz982SrIeH14QdBwAAALj0zKoopYyhV59zBgAAAAAYYJQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgAhctZ2b2pJkdNLOdZ933NTN7zcxeNbMXzOzKgR0TAAAAALJbb86crZBUc859S919krtPlvSMpP8VeC4AAAAMhqYDUu0dUtN7fd51bUNC0xZv0LiFz2ra4g1a25AYgAGBS8dFy5m7vyzpyDn3/eGsm8MleeC5AAAAMBg2Pibt2yJtXNKn3dY2JLRo9Q4lGlvkkhKNLVq0egcFDUhBbn93NLOvS/qcpKOSpgebCAAAAAPvkTFSW+uZ29uWd3zl5ksPHbzo7kvX71bLyfYu97WcbNfS9bs1q6I09LTAJcHcL37Sy8zKJD3j7hO6eWyRpAJ3f7iHfedJmidJJSUlU+rq6lIaOB2am5tVVFSU7jGyAlmGQ5ZhkGM4ZBkOWYZDlj0b2npE4/fUavThrco51ar2Ifk6PHqq9oyfqxP5I7ts212Oc54/1uNzr6gZPiAzZwNek+FkapbTp0/f7u6V3T3W7zNnZ1kp6TlJ3ZYzd18maZkkVVZWelVVVYBDDq76+npl4twxIstwyDIMcgyHLMMhy3DI8iLWbZIObZZyC5TTfkIlV1+rkuq7z9usuxxLt2xQorHlvG1LRxSS+QXwmgwnG7Ps11L6ZnbdWTfvkvRGmHEAAAAwaI4dlKbMle5/seN7c+8XBVlQXa7CvJwu9xXm5WhBdXnoKYFLxkXPnJnZDyVVSRptZvvVcYbsz8ysXNIpSW9L+suBHBIAAAADYPbKMz/PfLxPu55+X9nS9bv1TmOLrhxRqAXV5bzfDEjBRcuZu3+2m7uXD8AsAAAAyCCzKkopY0BA/bqsEQAAAAAQFuUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAiQDkDAAAAgAhQzgAAAAAgApQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACACKZUzM/s7M3vdzHaa2Q/NrCDUYAAAAD1qOiDV3iE1vdev3dc2JDRt8QaNW/ispi3eoLUNicADAkDf9bucmVmppL+RVOnuEyTlSJodajAAAIAebXxM2rdF2rikz7uubUho0eodSjS2yCUlGlu0aPUOChqAtMsNsH+hmZ2UNEzSO6mPBAAA0INHxkhtrWdub1ve8ZWbLz10sFdPsXT9brWcbO9yX8vJdi1dv1uzKkpDTgsAfWLu3v+dzeZL+rqkFkkvuPu93WwzT9I8SSopKZlSV1fX7+OlS3Nzs4qKitI9RlYgy3DIMgxyDIcswyHLng1tPaLxe2o1+vBW5ZxqVfuQfB0ePVV7xs/VifyR523fXZZznj/W4/OvqBkefOZswGsyHLIMJ1OznD59+nZ3r+zusX6fOTOzkZLukjROUqOkH5vZX7j7v5y9nbsvk7RMkiorK72qqqq/h0yb+vp6ZeLcMSLLcMgyDHIMhyzDIcuLWLdJOrRZyi1QTvsJlVx9rUqq7+520+6yLN2yQYnGlvO2LR1RSO494DUZDlmGk41ZprIgyJ9K+k93P+TuJyWtlnRLmLEAAAB6cOygNGWudP+LHd+b+7YoyILqchXm5XS5rzAvRwuqy0NOCQB9lsp7zvZJmmpmw9RxWePtkrYFmQoAAKAns1ee+Xnm433e/fT7ypau3613Glt05YhCLagu5/1mANKu3+XM3bea2SpJr0hqk9Sg5OWLAAAAMZtVUUoZAxCdlFZrdPeHJT0caBYAAAAAuGSl9CHUAAAAAIAwKGcAAAAAEAHKGQAAAABEgHIGAAAAABGgnAEAAABABChnAAAAABAByhkAAAAARIByBgAAAAARoJwBAAAAQAQoZwAAAAAQAcoZAAAAAESAcgYAAAAAEchNZWcz2yupSVK7pDZ3rwwxFAAAAABcalIqZ0nT3f1wgOcBACD7NR2QVs2VPr1CKi7p065rGxJaun633mls0ZUjCrWgulyzKkoHZk4AwKDjskYAAAbTxsekfVukjUv6tNvahoQWrd6hRGOLXFKisUWLVu/Q2obEwMwJABh0qZ45c0kvmJlLesLdlwWYCQCA7PPIGKmt9cztbcs7vnLzpYcOXnT3pet3q+Vke5f7Wk62a+n63Zw9A4AsYe7e/53NSt09YWZjJP27pAfc/eVztpknaZ4klZSUTKmrq0tl3rRobm5WUVFRusfICmQZDlmGQY7hkOWFDW09ovF7ajX68FblnGpV+5B8HR49VXvGz9WJ/JFdtu0uyznPH+vxuVfUDB+QmbMBr8swyDEcsgwnU7OcPn369p7W6kjpzJm7J5LfD5rZGkk3S3r5nG2WSVomSZWVlV5VVZXKIdOivr5emTh3jMgyHLIMgxzDIcteWLdJOrRZyi1QTvsJlVx9rUqq7z5vs+6yLN2yQYnGlvO2LR1RSO4XwOsyDHIMhyzDycYs+/2eMzMbbmbFp3+WNEPSzlCDAQCQdY4dlKbMle5/seN783u93nVBdbkK83K63FeYl6MF1eWhpwQApEkqZ85KJK0xs9PP87S7Px9kKgAAstHslWd+nvl4n3Y9/b4yVmsEgOzV73Lm7r+VdGPAWQAAwAXMqiiljAFAFmMpfQAAAACIAOUMAAAAACJAOQMAAACACFDOAAAAACAClDMAAAAAiADlDAAAAAAikMqHUBeY2S/M7Fdm9rqZ/X3IwQAAAADgUpLKmbNWSR939xslTZZUY2ZTg0wFAIhL0wGp9g6p6b0+77q2IaFpizdo3MJnNW3xBq1tSAzAgAAAZL5+lzPv0Jy8mZf88iBTAQDisvExad8WaeOSPu22tiGhRat3KNHYIpeUaGzRotU7KGgAAHQjN5WdzSxH0nZJ10r6jrtvDTIVACAOj4yR2lrP3N62vOMrN1966OBFd1+6frdaTrZ3ua/lZLuWrt+tWRWloacFACCjmXvqJ7vMbISkNZIecPed5zw2T9I8SSopKZlSV1eX8vEGW3Nzs4qKitI9RlYgy3DIMgxyvLChrUc0fk+tRh/eqpxTrWofkq/Do6dqz/i5OpE/ssu23WU55/ljPT73iprhAzJzNuB1GQ5ZhkGO4ZBlOJma5fTp07e7e2V3j6V05uw0d280s5ck1Ujaec5jyyQtk6TKykqvqqoKcchBVV9fr0ycO0ZkGQ5ZhkGOvbBuk3Ros5RboJz2Eyq5+lqVVN993mbdZVm6ZYMSjS3nbVs6opDcL4DXZThkGQY5hkOW4WRjlqms1nh58oyZzKxQ0ickvRFoLgBALI4dlKbMle5/seN7c+8XBVlQXa7CvJwu9xXm5WhBdXnoKQEAyHipnDmbLGm1meUlb29w92dSHwkAEJXZK8/8PPPxPu16+n1lS9fv1juNLbpyRKEWVJfzfjMAALqRSjnbKek2d3/FzIolbTezG9z914FmA4DUNB2QVs2VPr1CKi7p8+5rGxKUigBmVZSSGwAAvZDKUvrvuvsryZ+bJO2SxJ++AOLRz+XfJZaABwAAgy/IgiBmViapQhJL6QNIvxSXf5dYAh4AAAy+lJfSN7MiSRslfd3dV3fzOEvpoxNZhkOWPUt1+XeJJeD7g9dkOGQZDlmGQY7hkGU4mZrlgC2ln1wM5CeSVnZXzCSW0kdXZBkOWV5ECsu/SywB3x+8JsMhy3DIMgxyDIcsw8nGLFNZSt8kLZe0y937tnwXAAy0FJZ/l1gCHgAADL5UzpxNk3SfJJnZ30h6TdJX3P25EIMBQEpSWP5dYgl4AAAw+Ppdztx9s5k9IOmIpCfdfXKwqZCZUli2nCXLz8Ly79FgCXgAADCY+n1ZoyS5+z9J2hdoFmS6fi5bzpLl52D5dwAAgEtSkKX0cYlLcdlylixPYvl3AACAS1qIpfT/RNKL7l7Qw+P/LOkeSRo1atSwFStWpHS8dGhvb1dOTs7FN7xE5Z/4va7f/7Q+9PttyvUTarOhOjCyUruuuleteSO6bNtdll/cLEnWzTO7/ulPBmrq+PQlR4ksQ+G/73DIMhyyDIcswyDHcMgynEzN8lOf+tTALKXfG+5+n5ILh1RWVvrMmTMH+pDBZeMyncGte0X6/RYpt0C57Sc09r9dr7Ez/+K8zbrL8h929rRk+TDNnPnxgZo4Tr3MUSLLUPjvOxyyDIcswyHLMMgxHLIMJxuzTOk9Z0CnFJYtZ8nys7D8OwAAwCUr1Q+hflvSWElDzKxN0j+7+9wgkyGzpLBsOUuWn4Xl3wEAAC5ZqV7W+HlJ/0dSjqQfuPvi1EcaZCxbHgWWLA+HLAEAADJTvy9rNLMcSd+RdIekGyR91sxuCDXYoGHZcgAAAAARSOXM2c2S3nL330qSmdVJukvSr0MMNuBYthwAAABARPq9lL6ZfVpSjbvfn7x9n6Q/dvcvnrPdPEnzJKmkpGRKXV1dahMHMrT1iMbvqdXow1uVc6pV7UPydXj0VO0ZP1cn8kd22ba5uVlFRUXnPcec54/1+PwraoYHnzkb9JQl+o4swyDHcMgyHLIMhyzDIMdwyDKcTM1y+vTpaV1Kf5mkZVLHUvpRLXe5bpN0aLOUW6Cc9hMqufpalVTffd5mPS3TWbqlp2XLC7NuWc9QsnHJ03QhyzDIMRyyDIcswyHLMMgxHLIMJxuzTGUp/YSkq866PTZ5X+Zg2XIAAAAAkUjlzNkvJV1nZuPUUcpmS/rvQaYaLCxbDgAAACAS/S5n7t5mZl+UtF4dS+k/6e6vB5ssQ7BsOQAAAIAQUnrPmbs/J+m5QLMAAAAAwCUrlfecAQAAAAACoZwBAAAAQAQoZwAAAAAQAcoZAAAAAESAcgYAAAAAEaCcAQAAAEAEKGcAAAAAEAFz98E7mNkhSW8P2gHDGS3pcLqHyBJkGQ5ZhkGO4ZBlOGQZDlmGQY7hkGU4mZrlNe5+eXcPDGo5y1Rmts3dK9M9RzYgy3DIMgxyDIcswyHLcMgyDHIMhyzDycYsuawRAAAAACJAOQMAAACACFDOemdZugfIImQZDlmGQY7hkGU4ZBkOWYZBjuGQZThZlyXvOQMAAACACHDmDAAAAAAiQDm7CDOrMbPdZvaWmS1M9zyZysyeNLODZrYz3bNkMjO7ysxeMrNfm9nrZjY/3TNlKjMrMLNfmNmvkln+fbpnymRmlmNmDWb2TLpnyWRmttfMdpjZq2a2Ld3zZDIzG2Fmq8zsDTPbZWYfTfdMmcjMypOvx9NffzCzv033XJnIzP4u+efNTjP7oZkVpHumTGVm85M5vp5tr0cua7wAM8uR9KakT0jaL+mXkj7r7r9O62AZyMw+JqlZ0v919wnpnidTmdkVkq5w91fMrFjSdkmzeE32nZmZpOHu3mxmeZI2S5rv7lvSPFpGMrP/IalS0gfcfWa658lUZrZXUqW7Z+Ln9kTFzJ6StMndf2BmQyUNc/fGNI+V0ZJ/L0pI+mN3z8TPrU0bMytVx58zN7h7i5n9q6Tn3H1FeifLPGY2QVKdpJslnZD0vKS/dPe30jpYIJw5u7CbJb3l7r919xPqeCHcleaZMpK7vyzpSLrnyHTu/q67v5L8uUnSLkml6Z0qM3mH5uTNvOQX/1rVD2Y2VtInJf0g3bMAkmRml0n6mKTlkuTuJyhmQdwuaQ/FrN9yJRWaWa6kYZLeSfM8mep6SVvd/b/cvU3SRkn3pHmmYChnF1Yq6Xdn3d4v/iKMSJhZmaQKSVvTPErGSl6K96qkg5L+3d3Jsn/+t6QHJZ1K8xzZwCW9YGbbzWxeuofJYOMkHZJUm7zc9gdmNjzdQ2WB2ZJ+mO4hMpG7JyT9o6R9kt6VdNTdX0jvVBlrp6RbzWyUmQ2T9GeSrkrzTMFQzoAMZGZFkn4i6W/d/Q/pnidTuXu7u0+WNFbSzclLJdAHZjZT0kF3357uWbLEn7j7TZLukPSF5CXh6LtcSTdJ+p67V0g6Jon3jacgeWnonZJ+nO5ZMpGZjVTH1VfjJF0pabiZ/UV6p8pM7r5L0hJJL6jjksZXJbWnc6aQKGcXllDXJj42eR+QNsn3R/1E0kp3X53uebJB8nKnlyTVpHmUTDRN0p3J90rVSfq4mf1LekfKXMl/XZe7H5S0Rh2X16Pv9kvaf9bZ8FXqKGvovzskveLu76V7kAz1p5L+090PuftJSasl3ZLmmTKWuy939ynu/jFJv1fHGhFZgXJ2Yb+UdJ2ZjUv+i9FsSf8vzTPhEpZcxGK5pF3u/ni658lkZna5mY1I/lyojoV/3kjrUBnI3Re5+1h3L1PH/yM3uDv/GtwPZjY8udCPkpfgzVDH5TvoI3c/IOl3ZlaevOt2SSyclJrPiksaU7FP0lQzG5b8s/x2dbxvHP1gZmOS369Wx/vNnk7vROHkpnuAmLl7m5l9UdJ6STmSnnT319M8VkYysx9KqpI02sz2S3rY3Zend6qMNE3SfZJ2JN8rJUlfcffn0jdSxrpC0lPJ1ceGSPpXd2cZeKRTiaQ1HX9vU66kp939+fSOlNEekLQy+Y+rv5U0N83zZKzkPxZ8QtLn0z1LpnL3rWa2StIrktokNUhalt6pMtpPzGyUpJOSvpBNC/6wlD4AAAAARIDLGgEAAAAgApQzAAAAAIgA5QwAAAAAIkA5AwAAAIAIUM4AAAAAIAKUMwAAAACIAOUMAAAAACJAOQMAAACACPx/DdjgkO93lbEAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 1080x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "def fibonacci_iterative(n:int)->set:\n",
    "    fibs = np.empty(n);    \n",
    "    fibs[0] = 0;\n",
    "    fibs[1] = 1;\n",
    "\n",
    "    for i in range(2, n):\n",
    "        fibs[i] = fibs[i-1] + fibs[i-2];\n",
    "    \n",
    "    return fibs;\n",
    "\n",
    "\n",
    "def fibonacci_relation(n:int)->set:\n",
    "    fibs = np.arange(0, n, 1)    \n",
    "    alpha = (1-np.sqrt(5))/2\n",
    "    beta  = (1+np.sqrt(5))/2\n",
    "    # I should vectorize this...\n",
    "    for i in range(n):\n",
    "        fibs[i] = ( beta**(i) - alpha**(i) )/np.sqrt(5)\n",
    "    \n",
    "    return fibs\n",
    "\n",
    "n = 10 # <-- CHANGE THIS, number of points\n",
    "\n",
    "x = np.arange(0, n, 1)\n",
    "yi = fibonacci_iterative(n)\n",
    "yr = fibonacci_relation(n)\n",
    "\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(15, 5))\n",
    "plt.plot(x+0.1, yi, lw=0, marker='o', label=\"iterative\")\n",
    "ax.plot(x-0.1, yr, lw=0, marker='*', label=\"relation\")\n",
    "ax.set_xticks(x)\n",
    "ax.set_yticks(yr)\n",
    "ax.grid()\n",
    "ax.legend()\n",
    "#ax.semilogy() # <-- UNCOMMENT THIS, Log scale on y \n",
    "\n",
    "print(\"Values obtained with the relation:\\n\", yr)\n",
    "print(\"\\nValues obtained from scratch with the iterative procedure:\\n\", yi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "it is possible to notice how the formula correctly reproduces the expected values and, if one sets a semilog scale on y, that it shows the reason for the exponential behaviour at high values of n. For high values of $n$ the formula tends to be of the form\n",
    "\\begin{align*}\n",
    "    \\lim_{n\\rightarrow \\infty} \\frac{1}{\\sqrt{5}} \\left[ \\beta^{n+1} - \\alpha^{n+1} \\right] U[n] \\simeq \\frac{\\beta^{n+1}}{\\sqrt{5}}\n",
    "\\end{align*}\n",
    "\n",
    "## Basic properties of LTI systems in the z-space (domain)\n",
    "\n",
    "### a) Reality\n",
    "\\begin{align*}\n",
    "    \\left. \\begin{array}{cr}\n",
    "        x(z) =\\sum_{n} x[n]z^{-n} \\\\\n",
    "        x^*(z) =\\sum_{n} x^*[n](z^*)^{-n} \\\\\n",
    "        x^*(z^*) =\\sum_{n} x^*[n]z^{-n}\n",
    "    \\end{array}\\right\\} \\text{ if } x[n]\\in \\mathcal{R} \\implies x^{*}(z^{*})=x(z)\n",
    "\\end{align*}\n",
    "\n",
    "That is, the transfer function of a real system must have an even number of poles symmetric with respect to the real axis.  \n",
    "Is the inverse true?\n",
    "\\begin{align*}\n",
    "    \\sum_{n} (x^*[n]-x[n])z^{-n}=0 \\implies x^*(z^*)-x(z)=0 \\iff x^*[n]=x[n]\n",
    "\\end{align*}\n",
    "\n",
    "### b) BIBO stability\n",
    "Assume a BIBO stable sequence (that is $\\sum_{n} \\left| x[n]\\right| < \\infty$). In general it is possible to write\n",
    "\n",
    "\\begin{align*}\n",
    "    x(z) = \\sum_{n} x[n]z^{-n} \\text{ with } z\\in \\text{ROC}.\n",
    "\\end{align*}\n",
    "\n",
    "If one chooses $\\left| z \\right| = 1$ then $x(z) = \\sum_{n} x[n] < \\infty$, therefore, if a system is BIBO stable then the unitary circonference belongs to the ROC ($\\Gamma_1 \\in \\text{ROC}$).\n",
    "On the other hand, if the z transform exits it is possible to freely insert $\\left|z\\right|=1$ (that is $z\\in\\Gamma_1$) and then the system is BIBO stable, at least on $\\Gamma_1$.\n",
    "\n",
    "```{admonition} Theorem\n",
    "A system is BIBO stable $\\iff \\Gamma_1 \\in$ ROC.\n",
    "```\n",
    "\n",
    "### c) Causality (with $x[n]\\neq \\alpha \\delta[n]$)\n",
    "A system is _CAUSAL_ if and only if $0 \\not \\in $ ROC while $\\infty \\subset $ ROC.  \n",
    "**proof**  \n",
    "- $\\implies$ as $x(z)=\\sum_{n=0}^{\\infty} x[n]z^{-n}$ the condition $0\\not \\in \\text{ROC}$ is necessary to avoid the pole $\\left. z^{-n}\\right|_{z=0}$. $\\infty$ can be seen to be in the ROC by taking the limit.  \n",
    "- $\\impliedby$ it is possible to Laurent expand the transform\n",
    "\\begin{align*}\n",
    "    x(z)=\\sum_{k=-\\infty}^{0}\\frac{a_k}{k!}z^k = \\sum_{n=\\infty}^{0}\\frac{a_{-n}}{(-n)!}z^{-n}=\\sum_{n=0}^{\\infty}\\frac{a_{-n}}{(-n)!}z^{-n}\n",
    "\\end{align*}\n",
    "and obtain the z-transform with $0\\not \\in$ ROC. Notice how in the last step the commutative property of the sum was exploited.\n",
    "\n",
    "\n",
    "### d) Non Causality (with $x[n]\\neq \\alpha \\delta[n]$)\n",
    "A system is _NON CAUSAL_ if and only iff $0\\in $ ROC while $\\infty \\not \\subset $ ROC.  \n",
    "**proof**  \n",
    "$\\implies x(z)=\\sum_{n=-\\infty}^{0} x[n]z^{-n} \\implies 0\\in \\text{ROC;} \\quad \\infty \\not \\in \\text{ROC}$.  \n",
    "$\\impliedby$ Taylor expand the z-transform ($x(z)=\\sum_{k=0}^{\\infty} a_k z^{k}=\\sum_{n=-\\infty}^{0} x_{-n}z^{-n}$) and evaluate ROC.\n",
    "\n",
    "### e) Both causality and non causality (with $x[n]=\\alpha \\delta[n]$)\n",
    "A system is _both_ causal and not causal if and only if $0\\in$ROC and $\\infty\\subset$ROC."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In chronological order, the next lectures are Laboratory Classes 1-3, namely:\n",
    "- Introduction to Verilog programming on an FPGA device. Counters and frequency dividers.\n",
    "- Multiplexers and demultiplexers\n",
    "- Synchronous counters. Toggle flip-flops. Monostable multivibrators."
   ]
  }
 ],
 "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
}