21-09-14 L02.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 02 - Stability of Systems and Difference Equations\n",
    "Lecture 02 - 14 September 2021\n",
    "\n",
    "In the previous lecture, we gave some basic definitions and showed that an LTI system is fully characterized by its **impulse response**.\n",
    "\n",
    "An interesting property of LTI systems is that it is possible to imagine the impulse response and the input sequence as the two inputs of a convolution. This means that it is possible to freely swap the input sequence and the impulse response.\n",
    "\n",
    "\n",
    "\\begin{align*}\n",
    "    x[n] \\rightarrow [SYSTEM] \\rightarrow y[n] &\\implies (x[n], h[n]) \\rightarrow [CONVOLUTION] \\rightarrow y[n] \\\\\n",
    "    &\\implies (h[n], x[n]) \\rightarrow [CONVOLUTION] \\rightarrow y[n]\n",
    "\\end{align*}\n",
    "\n",
    "![](images/21-09-14_symmetry_convolution.jpeg)\n",
    "\n",
    "\n",
    "Matematically:\n",
    "\\begin{align*}\n",
    "    y[n] = \\sum_{k=-\\infty}^{\\infty} x[n] h[n-k]\\quad \\xrightarrow[k'=n-k]{k=k'-n} \\quad \\sum_{k'=-\\infty}^{\\infty} x[n-k'] h[k']\n",
    "\\end{align*}\n",
    "\n",
    "\n",
    "We will now discuss three important features that a system can have, namely **reality**, **causality / non-causality**, and **marginal stability / Bibo stability**.\n",
    "\n",
    "## Key properties of a system\n",
    "\n",
    "### Reality\n",
    "A system is said to be real iff $h[n]\\in \\mathcal{R}$.\n",
    "\n",
    "### (Non) Causality\n",
    "A system is said to be causal (or nonanticipative) iff $h[n] = 0 \\textit{ if } n<0$. An equivalent definition is: the output $y[n_{0}]$ depends on only the input $x[n]$ for values of $n < n_{0}$. The idea behind this property is that the output depends only on past inputs and not on future inputs.\n",
    " \n",
    "\n",
    "A non-causal system is defined **by substituting the \"less than\" with a \"greater than\"**: <br/>\n",
    "A system is said to be causal (or nonanticipative) iff $h[n] = 0 \\textit{ if } n>0$. An equivalent definition is: the output $y[t_{0}]$ depends on only the input $x[n]$ for values of $n>n_{0}$.\n",
    "\n",
    "\n",
    "```{note}\n",
    "A system can be BOTH causal and NON CAUSAL. A class of systems that satisfy this properties are amplifiers $h[n]= \\alpha\\ \\delta[n]$. These kind of systems respect both conditions as they have $h[n]=0$ for both $t<0$ and $t>0$.\n",
    "```\n",
    "\n",
    "An intuitive way to remember causality is the following: consider a causal linear system defined as:\n",
    "\\begin{equation*}\n",
    "    y[n] = \\sum_{k=-\\infty}^{+\\infty} x[k] h[n-k]\n",
    "\\end{equation*}\n",
    "\n",
    "and label the current time step as zero $n=0$:\n",
    "\\begin{equation*}\n",
    "    y[0] = \\sum_{k=-\\infty}^{+\\infty} x[k] h[-k]\n",
    "\\end{equation*}\n",
    "\n",
    "The usual definition of cauality implies that the system can not depend on future inputs because we don't know those inputs yet. Future inputs are labelled with positive indices, e.g. $x[1], x[2], etc$. For those values of $k$ we have $h[-1], h[-2], etc$. So, the only way for the system to remove the dependence on future inputs is to have $h[l] = 0 \\iff l<0$.\n",
    "\n",
    "\n",
    "### Marginal Stability\n",
    "A system is marginal stable iff $\\exists L<+\\infty\\ :\\ |h[n]| \\leq L\\ \\forall n$.\n",
    "\n",
    "An example of marginal stable system is one with $h[n]=U[n]= 1$ (*the integrator*):\n",
    "\\begin{equation*}\n",
    "    y[n] = \\sum_{k=-\\infty}^{+\\infty} x[k]\\ U[n-k] = \\sum_{k=-\\infty}^{n} x[k]\n",
    "\\end{equation*}\n",
    "\n",
    "### BIBO Stability\n",
    "A system is BIBO Stable (Bounded Input - Bounded Output) if to each and every bounded input $x[n]$ it corresponds a bounded output.\n",
    "\\begin{equation*}\n",
    "    \\forall\\ x[n]\\ :\\ |x[n]|<+\\infty \\implies \\exists L<\\infty\\ :\\ |y[n]|<L\\quad \\forall n\n",
    "\\end{equation*}\n",
    "\n",
    "An amplifiers is a BIBO stable system (trivial if we take $L=\\max_{n}\\{x[n]\\}\\times\\alpha$) but an integrator is not. If we choose $x[n]=U[n]$ we have:\n",
    "\\begin{equation*}\n",
    "    y[n] = \\sum_{k=-\\infty}^{n} U[k] = \\sum_{k=0}^{n} 1 = n+1\n",
    "\\end{equation*}\n",
    "so I can just choose $n=L$ to \"surpass\" every $L$ I've chosen.\n",
    "\n",
    "### Th: BIBO Stability\n",
    "```{admonition} Theorem\n",
    "Condition sufficient and necessary for a system to be BIBO Stable is that $h[n]$ is **absolutely convergent**, that is $\\exists L <\\infty\\ :\\ \\sum_{n}|h[n]| \\le L$.\n",
    "```\n",
    "\n",
    "#### Proof of sufficiency ($\\impliedby$)\n",
    "Assume the input sequence to be bounded $|x[n]| \\leq L\\in\\mathcal{R}^{+}\\ \\forall n$ and apply the Cauchy–Schwarz inequality:\n",
    "\n",
    "\\begin{align*}\n",
    "    |y[n]| &= |\\sum_{k} h[k] x[n-k]| \\leq \\sum_{k} |h[k]|\\ |x[n-k]| \\\\\n",
    "            &\\leq \\max_{k}\\{h[k]\\} \\sum_{k} |h[n-k]| \\leq \\max_{k}\\{h[k]\\}\\ L < +\\infty\n",
    "\\end{align*}\n",
    "\n",
    "\n",
    "#### Proof of necessity ($\\implies$)\n",
    "The proof of necessity is a bit trickier. Instead of the direct way, we will work \"ad absurdum\" by proving that if the system is *NOT BIBO stable* then $h[k]$ is *NOT absolutely convergent*. In other words, if to some limited output it correspond an unbounded output, then the impulse response can not be absolutely convergent.\n",
    "\n",
    " <!-- This proof works because the other cases were already taken care of [^cases].\n",
    "\n",
    "[^cases]: Let's list the cases for clarity's sake:\n",
    "    - $h[k]$ is NOT absolutely convergent $\\implies$ S is NOT BIBO stable: it's the proof\n",
    "    - $h[k]$ is absolutely convergent $\\implies$ S is NOT BIBO stable: impossible for the \"Proof of sufficiency\"\n",
    "    - $h[k]$ is NOT absolutely convergent $\\implies$ S is BIBO stable: it's in the proof\n",
    "    - $h[k]$ is absolutely convergent $\\implies$ S is BIBO stable: that's what we are aiming for -->\n",
    "    \n",
    "Let's consider a sequence defined as:\n",
    "\\begin{align*}\n",
    "    x[n] = \\left\\{\\begin{array}{lr}\n",
    "        \\frac{h^*[-n]}{|h[-n]|} \\quad \\textit{if} \\quad |h[-n]|\\neq 0\\\\\n",
    "        0  \\quad \\textit{if} \\quad |h[-n]| = 0\\\n",
    "        \\end{array}\\right.\n",
    "\\end{align*}\n",
    "\n",
    "Now we evaluate the output of said system in n=0 and use the fact that we want the system **NOT** BIBO stable:\n",
    "\n",
    "\\begin{align*}\n",
    "    y[n] = \\sum_{k} h[k] \\frac{h^*[k-n]}{|h[k-n]|} \\rightarrow y[0] = \\sum_{k} h[k] \\frac{h^*[k]}{|h[k]|} = \\sum_k |h[k]| = +\\infty\n",
    "\\end{align*}\n",
    "\n",
    "With this, we proved that if the system if not BIBO stable then $h[k]$ is not absolutely convergent.\n",
    "\n",
    "\n",
    "### Stability of a sequence\n",
    "\n",
    "Sometime we will talk about BIBO stability of a sequence. In this context it means $\\sum_n |x[n]| < +\\infty$.\n",
    "\n",
    "\n",
    "## Difference equations\n",
    "\n",
    "A discrete way to characterize LTI systems other than differential equation and their solution are difference equations. The most generic form of a second order difference equation is\n",
    "\\begin{equation*}\n",
    "    y[n] = y[n-1] + y[n-2] + x[n]\n",
    "\\end{equation*}\n",
    "where $x[n]$ is called \"initial conditions\".\n",
    "\n",
    "### e.g. Fibonacci sequence\n",
    "\\begin{equation*}\n",
    "f[n] = \\left\\{\\begin{array}{lr}\n",
    "        0  \\quad \\textit{if} \\quad n\\leq 0\\\\\n",
    "        1  \\quad \\textit{if} \\quad n = 0\\\\\n",
    "        f[n] = f[n-1] + f[n-2]\n",
    "        \\end{array}\\right.\n",
    "\\end{equation*}\n",
    "Where the first two conditions are the input / initial conditions.\n",
    "\n",
    "### Exercise\n",
    "\n",
    "Let's consider $y[n]=ay[n-1] + x[0]\\delta[n]$. How can we find $h[n]$?\n",
    "\n",
    "To do that, let's divide both sides by the input $x[n]$ so that we obtain the $h[n]=a h[n-1]+\\delta[n]$ and distinguish the two cases where $h[n]$ is causal or non causal:\n",
    "\n",
    "#### Case 1: $h[n]$ is Causal\n",
    "\n",
    "If $h[n]$ is causal it has to satisfy the condition $h[n]=0$ if $n<0$. It is then possible to write:\n",
    "- $h[0] = a h[0-1] + \\delta[0] = a\\cdot0 + 1=1$\n",
    "- $h[1] = a h[1-1] + \\delta[1] = a\\cdot 1 + 0=a$\n",
    "- $h[0] = a h[2-1] + \\delta[2] = a\\cdot a + 0=a^2$\n",
    "- ...\n",
    "\n",
    "$\\implies h[n]=a^n U[n]$.\n",
    "\n",
    "#### Case 2: $h[n]$ is Non Causal\n",
    "\n",
    "If $h[n]$ is non causal it has to satisfy the condition $h[n]=0$ if $n>0$. By inverting the difference equation it is possible to write: $h[n-1] = (h[n]-\\delta[n])/a$. Now we work step by step like in the previous case:\n",
    "\n",
    "- $h[0] = (h[1]-\\delta[1])/a = (0-0)/a = 0$\n",
    "- $h[-1] = (h[0]-\\delta[0])/a = (0-1)/a = -1/a$\n",
    "- $h[-2] = (h[-1]-\\delta[-1])/a = (-1/a-0)/a = -1/a^2$\n",
    "- $h[-3] = (h[-2]-\\delta[-2])/a = (-1/a^2-0)/a = -1/a^3$\n",
    "- ...\n",
    "\n",
    "$\\implies h[n]=-1 \\cdot U[n] \\cdot a^{n}$\n",
    "\n",
    "It is possible to rewrite this expression so that we consider only positive n: $h[n]=-1 \\cdot U[-(n+1)] \\cdot a^{-n}$\n",
    "\n",
    "\n",
    "#### Summing up\n",
    "By considering both cases one at a time, it is possible to find the value of $h[n]$:\n",
    "\n",
    "\\begin{equation*}\n",
    "h[n] = \\left\\{\\begin{array}{lr}\n",
    "        h[n]=a^n  \\quad \\textit{if CAUSAL}\\\\\n",
    "        h[n]=-U[-n-1] a^{-n}  \\quad \\textit{if NON CAUSAL}\n",
    "        \\end{array}\\right.\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}