{
 "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": [
    "## Fast Convolution\n",
    "\n",
    "The linear convolution of signals is a basic building block in many practical applications. The straightforward convolution of two finite-length signals $x[k]$ and $h[k]$ has considerable numerical complexity. This has led to the development of various algorithms that realize the convolution with lower complexity. The basic concept of the *fast convolution* is to exploit the [convolution theorem](theorems.ipynb#Convolution-Theorem) of the discrete Fourier transform (DFT). This theorem states that the periodic convolution of two signals is equal to a scalar multiplication of their spectra. The scalar multiplication has considerably less numerical operations that the convolution. The transformation of the signals can be performed efficiently by the [fast Fourier transform](fast_fourier_transform.ipynb) (FFT). \n",
    "\n",
    "Since the scalar multiplication of the spectra realizes a periodic convolution, special care has to be taken to realize a linear convolution in the spectral domain. The equivalence between linear and periodic convolution is discussed in the following."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Equivalence of Linear and Periodic Convolution\n",
    "\n",
    "The [linear convolution](../discrete_systems/linear_convolution.ipynb#Finite-Length-Signals) of a causal signal $x_L[k]$ of length $L$ with a causal signal $h_N[k]$ of length $N$ reads\n",
    "\n",
    "\\begin{equation}\n",
    "y[k] = x_L[k] * h_N[k] = \\sum_{\\kappa = 0}^{L-1} x_L[\\kappa] \\; h_N[k - \\kappa] = \\sum_{\\kappa = 0}^{N-1} h_N[\\kappa] \\; x_L[k - \\kappa]\n",
    "\\end{equation}\n",
    "\n",
    "The resulting signal $y[k]$ is of finite length $M = N+L-1$. Without loss of generality it is assumed in the following that $N \\leq L$. The computation of $y[k]$ for $k=0,1, \\dots, M-1$ requires $M \\cdot N$ multiplications and $M \\cdot (N-1)$ additions. The computational complexity of the convolution is consequently [on the order of](https://en.wikipedia.org/wiki/Big_O_notation) $\\mathcal{O}(M \\cdot N)$.\n",
    "\n",
    "The periodic convolution of the two signals $x_L[k]$ and $h_N[k]$ is defined as\n",
    "\n",
    "\\begin{equation}\n",
    "x_L[k] \\circledast_P h_N[k] = \\sum_{\\kappa = 0}^{N-1} h_N[\\kappa] \\cdot \\tilde{x}[k-\\kappa]\n",
    "\\end{equation}\n",
    "\n",
    "where $\\tilde{x}[k]$ denotes the periodic summation of $x_L[k]$ with period $P$\n",
    "\n",
    "\\begin{equation}\n",
    "\\tilde{x}[k] = \\sum_{\\nu = -\\infty}^{\\infty} x_L[k - \\nu P]\n",
    "\\end{equation}\n",
    "\n",
    "The result of the circular convolution is periodic with period $P$. To compute the linear convolution by a periodic convolution, one has to take care that the result of the linear convolution fits into one period of the periodic convolution. Hence, the periodicity has to be chosen as $P \\geq M$ where $M = N+L-1$. This can be achieved by zero-padding of $x_L[k]$ to the total length $M$ resulting in the signal $x_M[k]$ of length $M$ which is defined as\n",
    "\n",
    "\\begin{equation}\n",
    "x_M[k] = \\begin{cases} \n",
    "x_L[k] & \\text{for } 0 \\leq k < L \\\\\n",
    "0 & \\text{for } L \\leq k < M\n",
    "\\end{cases}\n",
    "\\end{equation}\n",
    "\n",
    "and similar for $h_N[k]$ resulting in the zero-padded signal $h_M[k]$ which is defined as\n",
    "\n",
    "\\begin{equation}\n",
    "h_M[k] = \\begin{cases} \n",
    "h_N[k] & \\text{for } 0 \\leq k < N \\\\\n",
    "0 & \\text{for } N \\leq k < M\n",
    "\\end{cases}\n",
    "\\end{equation}\n",
    "\n",
    "Using these signals, the linear and periodic convolution are equivalent for the first $M$ samples $k = 0,1,\\dots, M-1$\n",
    "\n",
    "\\begin{equation}\n",
    "x_L[k] * h_N[k] = x_M[k] \\circledast_M h_M[k]\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example\n",
    "\n",
    "The following example computes the linear, periodic and linear by periodic convolution of two signals $x[k] = \\text{rect}_L[k]$ and $h[k] = \\text{rect}_N[k]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAsoAAAI8CAYAAADoXY1EAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3XuYZGdd7v3vPRkQmHD2ANMhwzCIYJTE7M1ZoTFGzuDL\nKwoZTAYU91YJXIAKgv1Oht4o6qAG0K1sIMMpIISjisqwoZWDgQQIBBJOk3aS9EAwJIBMMCb07/2j\nVmcqndXd1XPotbrn+7muuqYOq5511zOrVv36qWetSlUhSZIk6ebWdR1AkiRJ6iMLZUmSJKmFhbIk\nSZLUwkJZkiRJamGhLEmSJLWwUJYkSZJaWChLOqol+ekkl3ado4+SfDjJMw/h+f+R5J6HL5EkrSwL\nZUlHhSTTSX52/v1V9dGqul8XmdaStqK6qm5fVf/WUSRJOmQWypLUgSTHdJ1BkrQ4C2VJR7Ukj0hy\nxdDt6SQvSPLZJNcmeWuSWw89/vgkn2ke+2iSnxx67IVJvprkO0k+n+QXhh47o1n+T5N8E9jekmVd\nkhc3bXw7yQVJxprHHprkk816P5HkIUPP+3CSlzbtfyfJPya5S/PYPyT5zXnruWgu22LtznvO9iRv\nGrq9Kclsk/l/AT8DvLpZ/yubZWaT3Ku5fockb0zyjaaPXzKvbz6S5E+SXJNkT5JHL/mfJ0lHmIWy\nJEHNu/0U4OeBzcCJwDaAJCcDrwOeBdwF+GvgfUlu1Tzvq8DDquoOwA7gzUl+ZKjdBzXL/BDwspYc\nLwB+GXh0Vd0ReCZwXZI7A38H/DlwV+DPgL9v7p/zNOCMpu0fAH67uf9c4LS5hZL8OHA88HcjtrtY\nPxVAVf0+8BHg2VV1h6p6TsvyrwZuD9wTGAdOT/KMoccfCFza5PgTBv0sSZ2yUJakWzq7qq6qqm8B\nfwuc1Nz/a8BfVdWFNfAm4HrgwQBV9c6quqq5/g7gKwwKwDkzVfWXVTVbVde3rPdXgZdU1VebNi6u\nqmuBxwFfrqpzm+e+Dfgi8ISh555TVXuadt8+lPndwIlJ7tHcPg14V1XdOGK7hyIwGCkHfgl4UVVd\nV1V7gVcAvzK07N6qen1VFfAG4G5Jfvgw5ZCkg2KhLEm3dNXQ9euAY5vrm4AXNNMDrklyLXAcsBEg\nyelD0zKuBU4AfnCorStY3D2Ay1ru3wjsnXffXmBs6PbX2zJX1XeB9wNPbR57KvDmZbR7OPwgcCvg\n8kXWc1P+qvoegyL7WCSpQxbKkjS6K4CXVdVdmsudq+rYqvqbJMcDrwF+s7n/zsAXaEZVG/OnLsx3\nObCl5f59DKYsDDsemBkx91uB05I8GLhNVU0dRLv7gdsN3b77vMcXe21XAzcw+ENjzqYF1iNJvWGh\nLOlocuskPzB0We6ZJ/4P8D+TPBAgyYYkj02yAdgAzAJXNwe4PQP4iWW2/zpgMsm9m/Z/spkv/H7g\nR5M8NckxSX4ZuB+DaSGjeD+DwvSlwN/Mu3/Udi8CHp7kHknuCLxo3uNXAfdqW3lVzTKYDvKyJMcm\n2QQ8D3hT2/KS1BcWypKOJn/PYFrC95p/b3HmCRYZGa2qTzE4kO/VSa4BvszgADqq6lIG827PZzCN\n4ATgo8vM96cMCsoPJPk28FrgtlV1DfB4BgfoXd38+7hm/vKimZts/wW8CziFwcF9c/eP3G5VfZBB\nkf054AJuWUyfDTwlyTeT/HlLrucw6PPLgH8B3lxV5ywWe7HXJEkrIYPjJiRJkiQNc0RZkiRJamGh\nLEmSJLWwUJYkSZJaWChLkiRJLdZ3HWAhSTzKUJIkSYdNVWXppQ7o9YhyVXlZ4rJ9+/bOM/T9Yh/Z\nT/aTfdTHi/1kH9lPK3s5GL0ulCVJkqSuWChLkiRJLSyUV7nx8fGuI/SefTQa+2k09tPS7KPR2E9L\ns49GYz8dOb39Zb4k1ddskiRJWl2SUKvhYL4kz0vy+SSfS/KWJLfuIockSZK0kBUvlJNsBM4ETq6q\n+zM4Rd1TVzqHJEmStJiuzqN8DLAhySxwO2BfRzkk9dD09F4mJnYxMzPL2Ng6Jie3sXnzJjP1OI8k\nrUWdzFFO8hzgZcB1wAeq6ldalnGOsnQUmp7ey6mnvoo9e3YAG4D9bNmynd27z+ysEOxbpr7lkaTV\nYFXMUU5yJ+BJwCZgI3BsktNWOoekfpqY2DVUAAJsYM+eHUxM7DJTT/NI0lrVxdSLnwMuq6prAJK8\nC3gocO78Bc8666ybro+Pj3v6E+koMDMzy4ECcM4G9u2b7SIO0L9MfcsjSX00NTXF1NTUIbXRRaF8\nOfDgJLcBrgdOAS5oW3C4UJZ0dBgbWwfs5+aF4H42buzutO99y9S3PJLUR/MHWXfs2LHsNlZ8r1pV\nnwTOAz4DfBYI8JqVziGpnyYnt7Fly3YGhSDMzb+dnNxmpp7mkaS1qpPhh6raUVX3q6r7V9UZVXVD\nFzkk9c/mzZvYvftMtm7dCcDWrTs7P0itb5n6lkeS1ip/mU9SbyXQt91A3zL1LY8k9dWqOOuFJEmS\ntBpYKEuSJEktLJQlSZKkFhbKkiRJUgsLZUmSJKmFhbIkSZLUootf5pPUI9PTe5mY2MXMzCxjY+uY\nnNzm+Xh1UNyWJK01nkdZOopNT+/l1FNfxZ49Oxj8HPLgF9768uMVfTxHcN8y9SVP37clSfI8ypKW\nZWJi11BhA7CBPXt2MDGxq8NUWo3cliStRRbK0lFsZmaWA4XNnA3s2zfbRRytYm5LktYiC2XpKDY2\ntg7YP+/e/Wzc6K5By+O2JGktcg8mHcUmJ7exZct2DhQ4g3mlk5PbOsuk1cltSdJaZKEsHcU2b97E\n7t1nsnXrTgC2bt3pwVc6KG5LktYiz3ohCejP2ROGmWlpfcsD/cwkSZ71QpIkSTpMLJQlSZKkFhbK\nkiRJUgsLZUmSJKlFJ4VykjsmeUeSS5N8IcmDusghSZIkLWR9R+s9G3h/VT0lyXrgdh3lkCRJklqt\n+OnhktweuKiqtiyxnKeH05ozPb2XiYldzMzMMja2jsnJbb05z2wfT+llpqX1LQ/0K1Of33OSVtbB\nnB6ui0L5ROA1wCXAicCFwHOr6nvzlrNQ1poyPb2XU099FXv27AA2MPfLZX35UYY+FTdzzLS0vuWB\n/mTq+3tO0spaLedRXg+cDPxFVZ0MXAe8qIMc0oqamNg19IENsIE9e3YwMbGrw1TS2uV7TtKh6mKO\n8pXAFVV1YXP7POCFbQueddZZN10fHx9nfHz8SGeTjpiZmVkOfGDP2cC+fbNdxJHWPN9z0tFtamqK\nqampQ2pjxQvlqroqyRVJ7lNVXwZOYTAN4xaGC2VptRsbWwfs5+Yf3PvZuNGzNEpHgu856eg2f5B1\nx44dy25jxecow03zlF8L3Aq4DHhGVX173jLOUdaa0vf5kn2ZVzrMTEvrWx7oT6a+v+ckrazVMkeZ\nqvpsVT2gqk6qqifPL5KltWjz5k3s3n0mW7fuBGDr1p1+YEtHkO85SYeqkxHlUTiirLWsLyNuw8w0\nmr5l6lseMJOkflo1I8qSJElS31koS5IkSS0slCVJkqQWFsqSJElSCwtlSZIkqYWFsiRJktSii5+w\nllbE9PReJiZ2MTMzy9jYOiYnt3n+VEmdc98krR6eR1lrUt9/kauP53Q102j6lqlvecBMi+n7vkla\nyzyPstSYmNg19EEEsIE9e3YwMbGrw1SSjnbum6TVxUJZa9LMzCwHPojmbGDfvtku4kgS4L5JWm0s\nlLUmjY2tA/bPu3c/Gze6yUvqjvsmaXXxnak1aXJyG1u2bOfAB9JgHuDk5LbOMkmS+yZpdbFQ1pq0\nefMmdu8+k61bdwKwdetOD5aR1Dn3TdLq4lkvtOb15Wj3YWYajZmW1rc8YKZR9TGTtJZ51gtJkiTp\nMLFQliRJklpYKEuSJEktlvwJ6yRnAMOzqDJ0e26eR81dr6o3HM6AkiRJUheWLJSBb1XVe+duJFlf\nVTe2LZjkSaOuOMk64ELgyqp64qjPkyRJklbCss96keRC4Geq6ntJHgN8r6qmlr3i5HnAfwPu0FYo\ne9aL1WV6ei8TE7uYmZllbGwdk5PbenO6oz4eWW6m0ZhpaX3LA2YaVZ8y9XkfLh0uB3PWi1FGlOf7\ng6ZIPh14AHA9MLWcBpIcBzwWeBnw/IPIoB6Znt7Lqae+ij17djD4adb9nH/+ds8NKkmrgPtwaWEj\nHcyX5IIkf9UUx5ckOQ24G/AK4P87iPX+GfA73Hzus1apiYldQztYgA3s2bODiYldHaaSJI3Cfbi0\nsFFHlH8fuAh4CPAM4CQGI8m3AT4CfHjUFSZ5HHBVVV2UZJwDBwTewllnnXXT9fHxccbHx0ddjVbQ\nzMwsB3awczawb99sF3EkScvgPlxr1dTUFFNTU4fUxkiFclX9U3P1Pc2FJMcAJwInLHOdDwOemOSx\nwG2B2yd5Y1WdPn/B4UJZ/TU2tg7Yz813tPvZuNGzD0pS37kP11o1f5B1x44dy25jyYP5kpxcVZ8e\nqbFlLNss/wjgBR7Mt7q1zW/bsqU/89v6dMDMHDONxkxL61seMNOo+pKp7/tw6XA5mIP5RimUfx+4\nnJufP/lmiwxdP66qXjbyyi2U14y5I6bf8pbtbN26o1dHTPflw2iYmUZjpqX1LQ+YaVR9ytTnfbh0\nuByRQrllJW8Dvgt8HPhYVX1pWQ2Mvh4L5VWoTzv+OWYajZlG07dMfcsDZhqVmaSVtSKFcrOiewMP\nZnBw3ynAe4GJqvqvZTe28DoslFehPu5kzTQaM42mb5n6lgfMNCozSStrpUaUH9Q87/zm9lOAzwKP\nr6o/XVZji6/HQnkV6uNO1kyjMdNo+papb3nATKMyk7SyVuoHR04Fbmh+WW8/g/nL/w585SDakiRJ\nknrpYArldwO3r6o/mrsjya8B04ctlSRJktSxg5qjvBKcerE69fFrOzONxkyj6VumvuUBM43KTNLK\nOpipF55NXJIkSWpxMFMv1ANz57ycmZllbGyd57yUJK0ZfsapL5x6sQr1+VeU+vi1nZlGY6bR9C1T\n3/KAmUZlpnZ9/ozT6ubUi6PExMSuoR0IwAb27NnBxMSuDlNJknTo/IxTn1gor0IzM7Mc2IHM2cC+\nfbNdxJEk6bDxM059YqG8Co2NrWNwCuth+9m40f9OSdLq5mec+sStbhWanNzGli3bObAjGczfmpzc\n1lkmSZIOBz/j1CcWyqvQ5s2b2L37TLZu3QnA1q07PchBkrQm+BmnPvGsF6tcH45QHta3PGCmUZlp\nNH3L1Lc8YKZRmWlpfcuj1c2zXkiSJEmHiYWyJEmS1MJCWZIkSWphoSxJkiS1WPFCOclxST6U5JIk\nFyd5zkpnkCRJkpayvoN13gg8v6ouSnIs8KkkH6iqL3aQRZIkSWq14oVyVX0d+Hpz/btJLgXGgN4W\nytPTe5mY2MXMzCxjY+uYnNzm+RwlSTqKWAscnboYUb5JknsCJwGf6DLHYqan93Lqqa9iz54dDH57\nfj/nn7/dk59LknSUsBY4enV2MF8z7eI84LlV9d2ucixlYmLX0BsDYAN79uxgYmJXh6kkSdJKsRY4\nenUyopxkPYMi+U1V9d6FljvrrLNuuj4+Ps74+PgRzzbfzMwsB94Yczawb9/simeRJEkrz1pgdZqa\nmmJqauqQ2uhq6sXrgUuq6uzFFhoulLsyNrYO2M/N3yD72bjRM+tJknQ0sBZYneYPsu7YsWPZbXRx\neriHAVuBn03ymSSfTvLolc4xqsnJbWzZsp3BGwRgP1u2bGdycltnmSRJ0sqxFjh6rXihXFUfq6pj\nquqkqvqpqjq5qv5xpXOMavPmTezefSZbt+4EYOvWnU7elyTpKGItcPRKVXWdoVWS6lu2BHoWqXeZ\n+pYHzDQqM42mb5n6lgfMNCozLa1veaCfmTSaJFRVlvMcJ9dIkiRJLSyUJUmSpBYWypIkSVILC2VJ\nkiSphYWyJEmS1MJCWZIkSWrR60L56U/fwfT03q5jSJIk9c709F6e/vQdPPKR262ZjpBen0cZvsuW\nLdt7c1LvPp47sW+Z+pYHzDQqM42mb5n6lgfMNCozLa1veaA/maan93Lqqa9iz54dDH5ae3+vaqY+\nWoPnUd7Anj07mJjY1XUQSZKk3piY2DVUJIM105HR80IZYAP79s12HUKSJKk3ZmZmOVAkz7FmOtxW\nQaG8n40bV0FMSZKkFTI2tg7YP+9ea6bDree9OZhvMzm5resgkiRJvTE5uY0tW7ZzoFi2ZjoSel0o\nb92600npkiRJ82zevIndu89k69adgDXTkdLrs170LVtfjnQd1rdMfcsDZhqVmUbTt0x9ywNmGpWZ\nlta3PGCm1WwNnvVCkiRJ6oaFsiRJktTCQlmSJElqYaEsSZIkteikUE7y6CRfTPLlJC/sIoMkSZK0\nmBUvlJOsA14NPAo4AXhakvuudA5JkiRpMV2MKD8Q+EpV7a2qG4C3AU/qIIckSZK0oC4K5THgiqHb\nVzb3SZIkSb3RRaHcdqJnT5MtSZKkXlnfwTqvBI4fun0csK9twbNyoKYeby5dKmgv8zvUt0x9ywNm\nGpWZRtO3TH3LA2YalZmW1rc80ONMjjnewtTUFFNTU4fUxor/hHWSY4AvAacAXwM+CTytqi6dt1zv\nfsJakiRJq9PB/IT1io8oV9X3kzwb+ACDqR+vm18kS5IkSV1b8RHlUTmiLEmSpMPlYEaU/WU+SZIk\nqYWFsiRJktTCQlmSJElqYaG8yh3qaU+OBvbRaOyn0dhPS7OPRmM/Lc0+Go39dORYKK9yvjmWZh+N\nxn4ajf20NPtoNPbT0uyj0dhPR46FsiRJktTCQlmSJElq0evzKHedQZIkSWvHcs+j3NtCWZIkSeqS\nUy8kSZKkFhbKkiRJUoteFspJHp3ki0m+nOSFXefpmyTHJflQkkuSXJzkOV1n6rMk65J8Osn7us7S\nR0numOQdSS5N8oUkD+o6Ux8leV6Szyf5XJK3JLl115n6IMnrklyV5HND9905yQeSfCnJPyW5Y5cZ\n+2CBfvrj5n13UZJ3JrlDlxm71tZHQ4/9dpLZJHfpIlufLNRPSc5saqeLk7y8q3x9scB77sQk/5rk\nM0k+meS/L9VO7wrlJOuAVwOPAk4Anpbkvt2m6p0bgedX1Y8DDwF+yz5a1HOBS7oO0WNnA++vqvsB\nJwKXdpynd5JsBM4ETq6q+wPrgad2m6o3zmGwvx72IuCDVfVjwIeA31vxVP3T1k8fAE6oqpOAr2A/\ntfURSY4Dfg7Yu+KJ+ukW/ZRkHHgC8BNV9ZPAzg5y9U3b9vTHwPaq+ilgO/AnSzXSu0IZeCDwlara\nW1U3AG8DntRxpl6pqq9X1UXN9e8yKGzGuk3VT80O9rHAa7vO0kdJbg/8TFWdA1BVN1bVdzqO1VfH\nABuSrAduB+zrOE8vVNVHgWvn3f0k4A3N9TcAv7CioXqorZ+q6oNVNdvcPB84bsWD9cgC2xLAnwG/\ns8JxemuBfvoN4OVVdWOzzNUrHqxnFuinWWDuG647ATNLtdPHQnkMuGLo9pVYBC4oyT2Bk4BPdJuk\nt+Z2sJ7epd29gKuTnNNMT3lNktt2Hapvqmof8ArgcgY71m9V1Qe7TdVrP1xVV8HgD3vghzrOsxo8\nE/iHrkP0TZInAFdU1cVdZ+m5+wAPT3J+kg+PMqXgKPU8YGeSyxmMLi/5LU4fC+W289tZ5LRIcixw\nHvDcZmRZQ5I8DriqGX0P7dvW0W49cDLwF1V1MnAdg6/NNSTJnRiMkm4CNgLHJjmt21RaK5K8BLih\nqs7tOkufNH+0v4TBV+Q33d1RnL5bD9ypqh4M/C7w9o7z9NVvMKiZjmdQNL9+qSf0sVC+Ejh+6PZx\n+BXnLTRf/54HvKmq3tt1np56GPDEJJcBbwUemeSNHWfqmysZjNZc2Nw+j0HhrJv7OeCyqrqmqr4P\nvAt4aMeZ+uyqJD8CkORuwDc6ztNbSc5gMD3MP7xuaQtwT+CzSaYZ1AOfSvLDnabqpysY7JeoqguA\n2SR37TZSL51RVe8BqKrzGEz3XVQfC+ULgHsn2dQcVf5UwLMV3NLrgUuq6uyug/RVVb24qo6vqnsx\n2I4+VFWnd52rT5qvx69Icp/mrlPwwMc2lwMPTnKbJGHQTx70eMD8b2zeB2xrrp8B+Mf8wM36Kcmj\nGYz+PbGqru8sVb/c1EdV9fmqultV3auqNjP4w/6nqso/vG75nnsPg/0Szf78VlX1zS6C9cz8fppJ\n8giAJKcAX16qgfVHKNhBq6rvJ3k2g6OB1wGvqyo/kIYkeRiwFbg4yWcYTE15cVX9Y7fJtEo9B3hL\nklsBlwHP6DhP71TVJ5OcB3wGuKH59zXdpuqHJOcC48Bdm3l/24GXA+9I8kwGf2Q8pbuE/bBAP70Y\nuDWwe/D3F+dX1W92FrJjbX00d6Bxo3DqxULb0uuBc5JcDFwPHPWDQgv007OAVyY5BvhP4NeXbMef\nsJYkSZJuqY9TLyRJkqTOWShLkiRJLSyUJUmSpBYWypIkSVILC2VJkiSphYWyJEmS1MJCWZIkSWph\noSxJkiS1sFCWJEmSWlgoS9IqleRRSS7oOockrVUWypK0el0EfKrrEJK0VlkoS9Lq9RDg412HkKS1\nykJZklavhwCfTPLkJBcmWd91IElaSyyUJWn1Ogk4uareBfxMVd3YdSBJWksslCVpFUpyDHA9cFyS\n06vqe11nkqS1xkJZklanE4ELgbcDD0jymI7zSNKaY6EsSavTCcBHgG8wGFl2RFmSDrNUVdcZJEmS\npN5xRFmSJElqYaEsSZIktbBQliRJklpYKEuSJEktLJQlSZKkFhbKkiRJUgsLZUmSJKmFhbIkSZLU\nwkJZkiRJamGhLEmSJLWwUJZ0WCT5fJKHH+Rzz0ny0kNtp0+STCf52UN4fqf9sNT6D/X1HYrDta1J\n0lIslKWjWJJ/S3Jdku8k+VqS1ye53cG0VVU/UVX/cqiZDlc7q0lb0dl1Pwyvv8uiuE3XfbNcSU5M\n8ooFHvupJC9a6UySRmOhLB3dCnhcVd0BOBl4APD7y2kgyTFHIpg030psa0n+e5K/T/LPSZ6Z5H8k\n+csk4wfZ3guA7cCdWx4LMAnc+pBCSzpiLJQlBaCqvgb8A/ATAEnunuS8JN9IsifJmTc9YTDC+LtJ\nPgt8N8kxw6OOSe6X5MNJrk1ycZIn3GyFg1G0TyX5dpK3AbeZ1/bPDt0+Lsk7mxz/nuSVrS9ikeWS\n3HehPM36XpDks83jb01y6+axFyZ5x7z1nJ3kz0d5nUPPmU1yr6Hbw1NN3ggcD/xtM7L/2/P7YbH1\nLJa/Jce2JO8buv3Vpv/nbl+e5P7D618oX+OnRlzvdJIXJflCkm8med3wsl1ta22q6kLge8Brq+r1\nVfXXwF8Af7PY8xZp7xXAexd4+P8FPnww7UpaGRbKkgBIcg/gscCnm5GuvwU+A9wdOAV4bpJTh57y\nVOAxwJ2q6vtD7awH3gf8I/BDwHOAtyT50ebxWwHvBt4A3AV4B4OCoS3TOuDvgGkGxdoY8LblLNfk\n+duF8jSeAvw8sBk4EdjW3P9W4DFJjh1az1Oa5y/6OuepttcHUFWnA5cDj6+qO1TVznmvbZT1LJR/\nvn8Gfrpp927AeuBhze17ARuq6nPLyDfqegFOA04FtgA/RvPNRV+2tXkeAXxs6Pa9gP9o2rxXkj9M\n8gfNv8PX/yDJE0donyR3BWaBq0dZXlI3LJQlvSfJNcC/MBjd+kMGUzB+sKpeVlXfr6p/A17LoGCZ\nc3ZV7auq6+e192AGBdcfVdWNVfVhBkXs04YeX19Vr2zafidwwQLZHsigePrdqvrPqvqvqvr4Mpdb\nKs/ca7mqqr7FoGg7CaCqLgc+DfxCs9wpwP6qugB4yAjtzskCr2+UZQ46/3xVNQ38R5KTGBSD/wTM\nJLkP8HDgI8vMN9J6G69qtpdvAS8byv9A+rGtDV7kYET9hqq6rLl9G+DXgd8CqKrLqur3qurFzb/D\n119cVe9bpPlhT66qd424rKSOrO86gKTOPakpMG6SZBMw1hTQMCiS1jEopudcuUB7G4Er5t23l8Eo\n79zjMy2Pt7kHsLeqZheOv+RyS+UBuGro+nUMiu45b2VQeL25+ffc5v67j9Du4XCo+ef7Z+CRwL2B\nKeBaYJxB4f/Py8y2nPUOby97GbwuaL4B6MG2NueRwOVJfonB3OFjgWdX1VLPG1mSBwKfOFztSTpy\nLJQltY0UXgFcVlU/tsjzFppOsI9B8TPseOBLzfWvccti8njgqwvkOD7JuiWK5cWW28egkF4oz1Le\nAexMMgb8PwxGKZfb7nXA8NlE7sbNC7wFp2awdH8u178ATwDuyWBk99vAVgav61ULPGexfKMa7qtN\nDF4X9Gdbm/NI4I1V9fa2B5spKs9qyZTmvvNHGFV+EHDbJI9hMPXlNkmeuIzRaEkrxKkXktp8EvhO\ncxDVbZoDqE5I8t9GeO4nGBx09btJ1mdwtoDHc2Bu8b8CNyY5s2n3yQy+fl8ox9eAlye5XZIfSPLQ\nZS73CWB/S563jvBaqKqrGYy0nsOgoJsrwpbT7kXAaUnWJXk0g2kPw77OYB5sm4X6c6T8LeZGlG9b\nVfsYTLd4NHBXBvOE21y1SL5R/VaSsSR3AX6PA9tDX7a1uTnoD2cw57nVvKkXw5elpl5kqI1XVdUf\nV9UfAZ8CPmqRLPWThbJ0dGsdqWtGZZ/AYM7pNPAN4P8Ad1zkedU89wbgiQwODLwaeDXwK1X15aHH\nnww8A7iGwQFh72zLNJTjRxkcUHYF8EuL5L3Fcovk+cpifTDPuQzmJ79laJ3Lafe5zbLXMpi+8e55\n7b8cmEhyTZLnDz//MOW/SfO8/6CZ2lBV/wHsYVCsDbc1fP0PF8q3DOcCH2AwmvtVBqPZXW9rN2nm\nJv8B8AMMpqIcFkmeDfwq8Igk25PcfuixpwBPAp6U5BcP1zolHT65+X5RkqTDK8k08KtV9aGus0jS\ncjiiLEmSJLWwUJYkHWl+dSlpVXLqhSRJktTCEWVJkiSpRW/Po5zEoW5JkiQdNlU1yi+l3qTXI8pV\n5WWJy/amcA/7AAAgAElEQVTt2zvP0PeLfWQ/2U/2UR8v9pN9ZD+t7OVg9LpQliRJkrpioSxJkiS1\nsFBe5cbHx7uO0Hv20Wjsp9HYT0uzj0ZjPy3NPhqN/XTk9Pb0cEmqr9kkSZK0uiShVsPBfEmel+Tz\nST6X5C1Jbt1FDkmSJGkhK14oJ9kInAmcXFX3Z3CKuqeudA5JkiRpMV2dR/kYYEOSWeB2wL6Ockjq\noenpvUxM7GJmZpaxsXVMTm5j8+ZNZupxHklaizqZo5zkOcDLgOuAD1TVr7Qs4xxl6Sg0Pb2XU099\nFXv27AA2APvZsmU7u3ef2Vkh2LdMfcsjSavBqpijnOROwJOATcBG4Ngkp610Dkn9NDGxa6gABNjA\nnj07mJjYZaae5pGktaqLqRc/B1xWVdcAJHkX8FDg3PkLnnXWWTddHx8f9/Qn0lFgZmaWAwXgnA3s\n2zfbRRygf5n6lkeS+mhqaoqpqalDaqOLQvly4MFJbgNcD5wCXNC24HChLOnoMDa2DtjPzQvB/Wzc\n2N1p3/uWqW95JKmP5g+y7tixY9ltrPhetao+CZwHfAb4LBDgNSudQ1I/TU5uY8uW7QwKQZibfzs5\nuc1MPc0jSWtVJ8MPVbWjqu5XVfevqjOq6oYuckjqn82bN7F795ls3boTgK1bd3Z+kFrfMvUtjySt\nVf4yn6TeSqBvu4G+ZepbHknqq1Vx1gtJkiRpNbBQliRJklpYKEuSJEktLJQlSZKkFhbKkiRJUgsL\nZUmSJKlFF7/MJ6lHpqf3MjGxi5mZWcbG1jE5uc3z8eqguC1JWms8j7J0FJue3supp76KPXt2MPg5\n5MEvvPXlxyv6eI7gvmXqS56+b0uS5HmUJS3LxMSuocIGYAN79uxgYmJXh6m0GrktSVqLLJSlo9jM\nzCwHCps5G9i3b7aLOFrF3JYkrUUWytJRbGxsHbB/3r372bjRXYOWx21J0lrkHkw6ik1ObmPLlu0c\nKHAG80onJ7d1lkmrk9uSpLXIQlk6im3evIndu89k69adAGzdutODr3RQ3JYkrUWe9UIS0J+zJwwz\n09L6lgf6mUmSPOuFJEmSdJhYKEuSJEktLJQlSZKkFhbKkiRJUotOCuUkd0zyjiSXJvlCkgd1kUOS\nJElayPqO1ns28P6qekqS9cDtOsohSZIktVrx08MluT1wUVVtWWI5Tw+nNWd6ei8TE7uYmZllbGwd\nk5PbenOe2T6e0stMS+tbHuhXpj6/5yStrIM5PVwXhfKJwGuAS4ATgQuB51bV9+YtZ6GsNWV6ei+n\nnvoq9uzZAWxg7pfL+vKjDH0qbuaYaWl9ywP9ydT395yklbVazqO8HjgZ+IuqOhm4DnhRBzmkFTUx\nsWvoAxtgA3v27GBiYleHqaS1y/ecpEPVxRzlK4ErqurC5vZ5wAvbFjzrrLNuuj4+Ps74+PiRziYd\nMTMzsxz4wJ6zgX37ZruII615vueko9vU1BRTU1OH1MaKF8pVdVWSK5Lcp6q+DJzCYBrGLQwXytJq\nNza2DtjPzT+497Nxo2dplI4E33PS0W3+IOuOHTuW3caKz1GGm+Ypvxa4FXAZ8Iyq+va8ZZyjrDWl\n7/Ml+zKvdJiZlta3PNCfTH1/z0laWatljjJV9dmqekBVnVRVT55fJEtr0ebNm9i9+0y2bt0JwNat\nO/3Alo4g33OSDlUnI8qjcERZa1lfRtyGmWk0fcvUtzxgJkn9tGpGlCVJkqS+s1CWJEmSWlgoS5Ik\nSS0slCVJkqQWFsqSJElSCwtlSZIkqUUXP2EtrYjp6b1MTOxiZmaWsbF1TE5u8/ypkjrnvklaPTyP\nstakvv8iVx/P6Wqm0fQtU9/ygJkW0/d9k7SWeR5lqTExsWvogwhgA3v27GBiYleHqSQd7dw3SauL\nhbLWpJmZWQ58EM3ZwL59s13EkSTAfZO02lgoa00aG1sH7J937342bnSTl9Qd903S6uI7U2vS5OQ2\ntmzZzoEPpME8wMnJbZ1lkiT3TdLqYqGsNWnz5k3s3n0mW7fuBGDr1p0eLCOpc+6bpNXFs15ozevL\n0e7DzDQaMy2tb3nATKPqYyZpLfOsF5IkSdJhYqEsSZIktbBQliRJklos+RPWSc4AhmdRZej23DyP\nmrteVW84nAElSZKkLixZKAPfqqr3zt1Isr6qbmxbMMmTRl1xknXAhcCVVfXEUZ8nSZIkrYQlp14M\nF8mN85PcFiDJY5KML7LsYp4LXLLYAk9/+g6mp/cuo8kjY3p6L09/+g4e+cjtZloleSRJo3MfLrVb\n9unhkjy5qt6V5HTgAcD1VfXby2zjOOAc4GXA89tGlJMUfJctW7Z3eo7J6em9nHrqq9izZweDnx3d\nb6ae55mvj6dgMtNozLS0vuUBM42qL5n6vg+XDpcjdnq4JBck+aumOL4kyWnA3YBXAP/f8qPyZ8Dv\ncPO5zy02sGfPDiYmdh3EKg6PiYldQzsPM62GPJKk0bkPlxY2yhxlgN8HLgIeAjwDOAm4HrgN8BHg\nw6OuMMnjgKuq6qJm2sYilf1ZAHzsYx9mauoRjI+Pj7qaw2ZmZpYDO485G9i3b3bFs8zpW6a+5ZEk\njc59uNaqqakppqamDqmNkQrlqvqn5up7mgtJjgFOBE5Y5jofBjwxyWOB2wK3T/LGqjr9loueBezn\nYQ9LJ0UywNjYOmA/N9+J7Gfjxu7OrNe3TH3LI0kanftwrVXj4+M3qx937Nix7DaWnKOc5OSq+vRI\njS1j2Wb5RwAvcI7y6s7Utzzz9WUe4DAzjcZMS+tbHjDTqPqSqe/7cOlwOVJzlB+b5PQkZzT/zr+c\nMXcBHnNw0dtt3bqz8zfq5s2b2L37TLZu3WmmVZJHkjQ69+HSwg7mrBdvA74LfBz4WFV96YgES2q5\n2Y60vvz1P6xvmfqWB8w0KjONpm+Z+pYHzDQqM0kr62BGlJddKDcrujfwYAYH950CvBeYqKr/WnZj\nC6/DQnkEfcvUtzxgplGZaTR9y9S3PGCmUZlJWlkrUigneVDzvPOb208BPgs8vqr+dFmNLb4eC+UR\n9C1T3/KAmUZlptH0LVPf8oCZRmUmaWUdTKE86unhhp0K3JDkeQwOk70c+HfgKwfRliRJktRLB1Mo\nvxu4fVX90dwdSX4NmD5sqSRJkqSOHdQc5ZXg1IvR9C1T3/KAmUZlptH0LVPf8oCZRmUmaWUdsZ+w\nliRJko42FsqSJElSCwtlSZIkqYWFsiRJktTCQlmSJElqYaEsSZIktbBQliRJklpYKEuSJEktLJQl\nSZKkFhbKkiRJUgsLZUmSJKmFhbIkSZLUwkJZkiRJarHihXKS45J8KMklSS5O8pyVziBJkiQtZX0H\n67wReH5VXZTkWOBTST5QVV/sIIskSZLUasVHlKvq61V1UXP9u8ClwNhK55AkSZIW0+kc5ST3BE4C\nPtFlDkmSJGm+zgrlZtrFecBzm5FlSZIkqTe6mKNMkvUMiuQ3VdV7F1rurLPOuun6+Pg44+PjRzyb\nJEmSVr+pqSmmpqYOqY1U1eFJs5yVJm8Erq6q5y+yTHWRbTEJ9CxS7zL1LQ+YaVRmGk3fMvUtD5hp\nVGaSVlYSqirLeU4Xp4d7GLAV+Nkkn0ny6SSPXukckiRJ0mJWfOpFVX0MOGal1ytJkiQth7/MJ0mS\nJLWwUJYkSZJaWChLkiRJLSyUJUmSpBYWypIkSVILC2VJkiSphYWyJEmS1MJCWZIkSWphoSxJkiS1\nsFCWJEmSWlgoS5IkSS0slCVJkqQWFsqSJElSCwtlSZIkqYWFsiRJktTCQlmSJElqYaEsSZIktbBQ\nliRJklpYKEuSJEktOimUkzw6yReTfDnJC7vIIEmSJC1mxQvlJOuAVwOPAk4AnpbkviudQ5IkSVpM\nFyPKDwS+UlV7q+oG4G3AkzrIIUmSJC2oi0J5DLhi6PaVzX2SJElSb3RRKKflvlrxFJIkSdIi1new\nziuB44duHwfsa1vwrByoqcebS5cK2sv8DvUtU9/ygJlGZabR9C1T3/KAmUbV20yOXWmNmJqaYmpq\n6pDaSNXKviGSHAN8CTgF+BrwSeBpVXXpvOVqpbNJkiRpbUpCVS3rz9MVH1Guqu8neTbwAQZTP143\nv0iWJEmSurbiI8qjckRZkiRJh8vBjCj7y3ySJElSCwtlSZIkqYWFsiRJktTCQnmVO9TTnhwN7KPR\n2E+jsZ+WZh+Nxn5amn00GvvpyLFQXuV8cyzNPhqN/TQa+2lp9tFo7Kel2UejsZ+OHAtlSZIkqYWF\nsiRJktSi1+dR7jqDJEmS1o7lnke5t4WyJEmS1CWnXkiSJEktLJQlSZKkFr0slJM8OskXk3w5yQu7\nztM3SY5L8qEklyS5OMlzus7UZ0nWJfl0kvd1naWPktwxyTuSXJrkC0ke1HWmPkryvCSfT/K5JG9J\ncuuuM/VBktcluSrJ54buu3OSDyT5UpJ/SnLHLjP2wQL99MfN++6iJO9McocuM3atrY+GHvvtJLNJ\n7tJFtj5ZqJ+SnNnUThcneXlX+fpigffciUn+NclnknwyyX9fqp3eFcpJ1gGvBh4FnAA8Lcl9u03V\nOzcCz6+qHwceAvyWfbSo5wKXdB2ix84G3l9V9wNOBC7tOE/vJNkInAmcXFX3B9YDT+02VW+cw2B/\nPexFwAer6seADwG/t+Kp+qetnz4AnFBVJwFfwX5q6yOSHAf8HLB3xRP10y36Kck48ATgJ6rqJ4Gd\nHeTqm7bt6Y+B7VX1U8B24E+WaqR3hTLwQOArVbW3qm4A3gY8qeNMvVJVX6+qi5rr32VQ2Ix1m6qf\nmh3sY4HXdp2lj5LcHviZqjoHoKpurKrvdByrr44BNiRZD9wO2Ndxnl6oqo8C1867+0nAG5rrbwB+\nYUVD9VBbP1XVB6tqtrl5PnDcigfrkQW2JYA/A35nheP01gL99BvAy6vqxmaZq1c8WM8s0E+zwNw3\nXHcCZpZqp4+F8hhwxdDtK7EIXFCSewInAZ/oNklvze1gPb1Lu3sBVyc5p5me8pokt+06VN9U1T7g\nFcDlDHas36qqD3abqtd+uKqugsEf9sAPdZxnNXgm8A9dh+ibJE8Arqiqi7vO0nP3AR6e5PwkHx5l\nSsFR6nnAziSXMxhdXvJbnD4Wym3nt7PIaZHkWOA84LnNyLKGJHkccFUz+h7at62j3XrgZOAvqupk\n4DoGX5trSJI7MRgl3QRsBI5Nclq3qbRWJHkJcENVndt1lj5p/mh/CYOvyG+6u6M4fbceuFNVPRj4\nXeDtHefpq99gUDMdz6Bofv1ST+hjoXwlcPzQ7ePwK85baL7+PQ94U1W9t+s8PfUw4IlJLgPeCjwy\nyRs7ztQ3VzIYrbmwuX0eg8JZN/dzwGVVdU1VfR94F/DQjjP12VVJfgQgyd2Ab3Scp7eSnMFgeph/\neN3SFuCewGeTTDOoBz6V5Ic7TdVPVzDYL1FVFwCzSe7abaReOqOq3gNQVecxmO67qD4WyhcA906y\nqTmq/KmAZyu4pdcDl1TV2V0H6auqenFVHV9V92KwHX2oqk7vOlefNF+PX5HkPs1dp+CBj20uBx6c\n5DZJwqCfPOjxgPnf2LwP2NZcPwPwj/mBm/VTkkczGP17YlVd31mqfrmpj6rq81V1t6q6V1VtZvCH\n/U9VlX943fI99x4G+yWa/fmtquqbXQTrmfn9NJPkEQBJTgG+vFQD649QsINWVd9P8mwGRwOvA15X\nVX4gDUnyMGArcHGSzzCYmvLiqvrHbpNplXoO8JYktwIuA57RcZ7eqapPJjkP+AxwQ/Pva7pN1Q9J\nzgXGgbs28/62Ay8H3pHkmQz+yHhKdwn7YYF+ejFwa2D34O8vzq+q3+wsZMfa+mjuQONG4dSLhbal\n1wPnJLkYuB446geFFuinZwGvTHIM8J/Ary/Zjj9hLUmSJN1SH6deSJIkSZ2zUJYkSZJaWChLkiRJ\nLSyUJUmSpBYWypIkSVILC2VJkiSphYWyJEmS1MJCWZIkSWphoSxJkiS1sFCWpFUqyaOSXNB1Dkla\nqyyUJWn1ugj4VNchJGmtslCWpNXrIcDHuw4hSWuVhbIkrV4PAT6Z5MlJLkyyvutAkrSWWChL0up1\nEnByVb0L+JmqurHrQJK0llgoS9IqlOQY4HrguCSnV9X3us4kSWuNhbIkrU4nAhcCbwcekOQxHeeR\npDXHQlmSVqcTgI8A32AwsuyIsiQdZqmqrjNIkiRJveOIsiRJktTCQlmSJElqYaEsSZIktbBQliRJ\nklpYKEuSJEktLJQlSZKkFhbKkiRJUgsLZUmSJKmFhbIkSZLUwkJZkiRJamGhLK1xSX46yaVd5+ij\nJB9O8sxDeP5/JLnn4UvUX0nukeQ7SXIQz31EkiuGbn8+ycMPb8KVleSMJB85hOf/7yQvOZyZJB1+\nFsrSGpFkOsnPzr+/qj5aVffrItNa0lZUV9Xtq+rfOoq0oqrqiqq6Q1XVwTYx1NZPVNW/HKZoXRqp\nL9qK6qr6jap62ZGJJelwsVCWdEQkOabrDDo8/L88ZGHEolpSv1goS2tcy9fe00lekOSzSa5N8tYk\ntx56/PFJPtM89tEkPzn02AuTfLX5Cv7zSX5h6LEzmuX/NMk3ge0tWdYleXHTxreTXJBkrHnsoUk+\n2az3E0keMvS8Dyd5adP+d5L8Y5K7NI/9Q5LfnLeei+ayLdbuvOdsT/Kmodubksw2mf8X8DPAq5v1\nv7JZZjbJvZrrd0jyxiTfaPr4JUNtnZHkI0n+JMk1SfYkefQi/2eL9fOWJFNJvtWs660LtDGX/1lJ\nZprL84ceT5IXNev59yRvS3Knec99ZpK9wP8d7o9mmbsneW+Sbyb5cpJfG2r7Nkl2Na/188AD5mW7\n6duPxbaJltf000k+1vxf7k1y+kH2/aOax345yQXz1vG8JO9Zqt0F+nrd0H0fbvrvvsD/Bh6SwVSd\na5rHz0ny0qHln5XkK0muTvKeJHcfemw2yf9o+vmbSV7dlkPS4WehLB0d5o9mPQX4eWAzcCKwDSDJ\nycDrgGcBdwH+Gnhfkls1z/sq8LCqugOwA3hzkh8ZavdBzTI/BLR9rfwC4JeBR1fVHYFnAtcluTPw\nd8CfA3cF/gz4++b+OU8Dzmja/gHgt5v7zwVOm1soyY8DxwN/N2K7i/VTAVTV7wMfAZ7dTD94Tsvy\nrwZuD9wTGAdOT/KMoccfCFza5PgTBv28kMX6eRL4p6q6E3Ac8KpF2qHJsgV4FPCiHJie81zgiQz+\nANgIXAv85bznPhy4b/Pc+a/3bcDlwN0YbE9/kOSRzWNnMdi2NjfPPWORfK3bxPyFktwDeD9wNvCD\nwEnARc3Dy+371zf3vw+4T5ItQ8s+DXjLiO0Oax0xrqovAv8T+Ndmqs5dWl7bzwJ/APwicHcG/fq2\neYs9Dvhvzev+pSQ/v0AOSYeRhbJ0dDq7qq6qqm8Bf8vgwxfg14C/qqoLa+BNwPXAgwGq6p1VdVVz\n/R3AVxgUIXNmquovq2q2qq5vWe+vAi+pqq82bVxcVdcyKAK+XFXnNs99G/BF4AlDzz2nqvY07b59\nKPO7gRObQgoGRfO7qurGEds9FIHBqCjwS8CLquq6qtoLvAL4laFl91bV65s5vm8A7pbkh9saXaKf\nbwA2JRmrqv+qqo8vkfGsqvrPqvo8cA6DQhDg1xn8X3ytqm4AXgr84tCoaAHbq+p78/8vm75+KPDC\nqrqhqj4LvHbo9T4F+F9V9e2qmgFeuUi+hbaJ+bYCu6vq7VX1/aq6tqo+d5B9f/ckP1xV32NQLD+t\neV0/CvwYgz8OR2n3cDkNeF1Vfbb5v/g9BiPQxw8t84dV9R9VdQXwYQ5s/5KOIAtl6eh01dD164Bj\nm+ubgBc0X1Ffk+RaBqOWGwGSnJ4D0zKuBU5gMLo35woWdw/gspb7NwJ75923Fxj+Cv7rbZmr6rsM\nRhqf2jz2VODNy2j3cPhB4FYMRgIXWs9N+ZsCLRzo95tZop9/h8G++5NJLl5khBMGxe6V8zJtbK5v\nAt49938NXMKgCB/+hmD4ucPuDlxTVcMjv8Ovd2PLehey0DbRttyelvsPpu/hQN+fy4E/Hk4D3tP8\nYTBKu4fLzbbTqtoPfHPeuhZ6z0o6giyUJQ27AnhZVd2ludy5qo6tqr9pRrdeA/xmc/+dgS/QjKo2\nljpg6XIG0wDm28fg6+1hxwMzI+Z+K3BakgcDt6mqqYNodz9wu6Hbd5/3+GKv7Wqakd6h+zYtsJ5F\nLdXPVfWNqvr1qhpj8JX+X6aZJ93WHIMCc87xDPoEBv8Xj5n3f72hqr42tPxCr3kfcJckG+a1Pfd6\nvzZvvcP9Mt8VtG8Tbcvdu+X+Q+37DwA/mOREBn9knXsQ7e5v/h3efu42dH2p98W+4fU0/XpXFv5D\nRdIKsVCW1pZbJ/mBoctyz1bwf4D/meSBMPjATvLY5oN7AzALXN0cgPUM4CeW2f7rgMkk927a/8lm\nvvD7gR9N8tQkxyT5ZeB+DKaFjOL9DAqNlwJ/M+/+Udu9CHh4BucLviPwonmPXwW0FqRVNctgOsjL\nkhybZBPwPOBNbcsvYdF+TvKLQwe7fatZ9vuLtDeR5LZJTgCewYG5r3/NYF7x8U27P5TkiUPPaztf\n8lyxfiXwceAPm+3s/gymUMyN5L8d+L0kd0pyHPDsRfK9lvZtYr63AKc0r/+YJHdJcuKh9n1VfR84\nj8Hc5TsDu5v7R263qq5mUEA/vfk/eyY3L/6vAo4bmus/37nAM5LcP8kPMJivfH4zzUJShyyUpbXl\n7xl8Lfu95t9bnHmCRUa3qupTDA7ke3XzdfyXaQ7EqqpLGczRPJ/BV9knAB9dZr4/ZVB8fCDJtxkU\nSbetqmuAxzM4QO/q5t/HDc1VXXRErqr+C3gXcAoHRgRZTrtV9UEGRfbngAu4ZTF9NvCU5qwDf96S\n6zkM+vwy4F+AN1fVOYvFXuC1LNXPDwA+keQ7wHuA5zTzZxfyzwwODtwN/HFV/d+h1/NeDvxffJyb\nzzdvyzd839MYHKy3D3gnMFFVH2oe28FgxHoa+EfgjYu007pN3GLFg6LxsQz+D68BPgPcv3n4UPv+\nrQy2nbc3BfKc5bT7LOB3GWxn9wM+NvTYhxh8K/D1JN9oeW0fAiYYbMMzDPr1qcOLLJFf0hGSOuhz\nx0uS+qoZAb0MuNW84k+SNCJHlCVp7Vr2z01Lkg6wUJaktcuvDCXpEDj1QpIkSWrhiLIkSZLUYn3X\nARaSxKFuSZIkHTZVtaxjN3o9olxVXpa4bN++vfMMfb/YR/aT/WQf9fFiP9lH9tPKXg5GrwtlSZIk\nqSsWypIkSVILC+VVbnx8vOsIvWcfjcZ+Go39tDT7aDT/f3v3HhvZWZ9x/PtzFgSYW4tKkWfFYowo\nNC0J23IXxTSsuBVSISEBpsSgthItC4KWQoHprjWionQpogGpQlwMKBRBSoE/KMQILFFoSAIJBBIu\nciwnsUsopbSKoWmCf/1jxtlZ7/H6eC9z3hl/P1KUGWd85tGbmTOPz7znPY7Tzhyjehync6fY5eEi\nIkvNJkmSpOESEeQwnMwXEa+NiG9HxLci4rKIuGcTOSRJkqTtDLwoR8QEcBg4mJmPobtE3YsGnUOS\nJEk6labWUT4PGI+IDeA+wFpDOSQVaHl5hXZ7ntXVDVqtMTqdWSYnD5ip4DySNIoamaMcEa8G3gr8\nDLgiM/+g4jHOUZb2oOXlFQ4dupSlpTlgHFhnauoICwuHGyuCpWUqLY8kDYOhmKMcEQ8ELgYOABPA\nfSPiJYPOIalM7fZ8XwEEGGdpaY52e95MheaRpFHVxNSLZwA3ZeZPACLik8CTgY9ufeDRo0fvvj09\nPe3yJ9IesLq6wfECuGmctbWNJuIA5WUqLY8klWhxcZHFxcUz2kYTRflm4IkRcS/gDuAi4OqqB/YX\nZUl7Q6s1BqxzYhFcZ2KiuWXfS8tUWh5JKtHWg6xzc3O73sbA96qZeRVwOXAt8E0ggPcOOoekMnU6\ns0xNHaFbBGFz/m2nM2umQvNI0qhq5PBDZs5l5qMz8zGZeUlm3tlEDknlmZw8wMLCYWZmjgEwM3Os\n8ZPUSstUWh5JGlVemU9SsSKgtN1AaZlKyyNJpRqKVS8kSZKkYWBRliRJkipYlCVJkqQKFmVJkiSp\ngkVZkiRJqmBRliRJkio0cWU+SQVZXl6h3Z5ndXWDVmuMTmfW9Xh1WnwtSRo1rqMs7WHLyyscOnQp\nS0tzdC+H3L3CWykXryhxjeDSMpWSp/TXkiS5jrKkXWm35/uKDcA4S0tztNvzDabSMPK1JGkUWZSl\nPWx1dYPjxWbTOGtrG03E0RDztSRpFFmUpT2s1RoD1rf8dJ2JCXcN2h1fS5JGkXswaQ/rdGaZmjrC\n8YLTnVfa6cw2lknDydeSpFFkUZb2sMnJAywsHGZm5hgAMzPHPPlKp8XXkqRR5KoXkoByVk/oZ6ad\nlZYHyswkSa56IUmSJJ0lFmVJkiSpgkVZkiRJqmBRliRJkio0UpQj4gER8YmIuDEivhMRT2gihyRJ\nkrSdfQ0977uAz2bmCyNiH3CfhnJIkiRJlQa+PFxE3A+4LjOndnicy8Np5Cwvr9Buz7O6ukGrNUan\nM1vMOrMlLullpp2VlgfKylTye07SYJ3O8nBNFOULgPcCNwAXANcAr8nMn295nEVZI2V5eYVDhy5l\naWkOGGfzymWlXJShpHKzyUw7Ky0PlJOp9PecpMEalnWU9wEHgfdk5kHgZ8AbG8ghDVS7Pd/3gQ0w\nztLSHO32fIOppNHle07SmWpijvKtwC2ZeU3v/uXAG6oeePTo0btvT09PMz09fa6zSefM6uoGxz+w\nN42ztrbRRBxp5Pmek/a2xcVFFhcXz2gbAy/KmXlbRNwSEY/MzO8DF9GdhnGS/qIsDbtWawxY58QP\n7nUmJlylUToXfM9Je9vWg6xzc3O73sbA5yjD3fOU3wfcA7gJeHlm/veWxzhHWSOl9PmSpcwr7Wem\nnTXdQxsAAA+/SURBVJWWB8rJVPp7TtJgDcscZTLzm5n5uMy8MDNfsLUkS6NocvIACwuHmZk5BsDM\nzDE/sKVzyPecpDPVyBHlOjyirFFWyhG3fmaqp7RMpeUBM0kq09AcUZYkSZJKZ1GWJEmSKliUJUmS\npAoWZUmSJKmCRVmSJEmqYFGWJEmSKjRxCWtpIJaXV2i351ld3aDVGqPTmXX9VEmNc98kDQ/XUdZI\nKv2KXCWu6WqmekrLVFoeMNOplL5vkkaZ6yhLPe32fN8HEcA4S0tztNvzDaaStNe5b5KGi0VZI2l1\ndYPjH0Sbxllb22gijiQB7pukYWNR1khqtcaA9S0/XWdiwpe8pOa4b5KGi+9MjaROZ5apqSMc/0Dq\nzgPsdGYbyyRJ7puk4WJR1kianDzAwsJhZmaOATAzc8yTZSQ1zn2TNFxc9UIjr5Sz3fuZqR4z7ay0\nPGCmukrMJI0yV72QJEmSzhKLsiRJklTBoixJkiRV2PES1hFxCdA/iyr67m/O88jN25n5obMZUJIk\nSWrCjkUZ+GlmfnrzTkTsy8y7qh4YERfXfeKIGAOuAW7NzOfX/T1JkiRpEHa96kVEXAM8NTN/HhHP\nBn6emYu7fuKI1wK/Bdy/qii76sVwWV5eod2eZ3V1g1ZrjE5ntpjljko8s9xM9ZhpZ6XlATPVVVKm\nkvfh0tlyOqte1DmivNVf90ryy4DHAXcAi7vZQETsB54DvBV43WlkUEGWl1c4dOhSlpbm6F6adZ0r\nrzzi2qCSNATch0vbq3UyX0RcHRH/0CvHN0TES4CHAO8A/uo0nvedwOs5ce6zhlS7Pd+3gwUYZ2lp\njnZ7vsFUkqQ63IdL26t7RPktwHXAk4CXAxfSPZJ8L+DLwJfqPmFEPBe4LTOvi4hpjp8QeJKjR4/e\nfXt6eprp6em6T6MBWl3d4PgOdtM4a2sbTcSRJO2C+3CNqsXFRRYXF89oG7WKcmZ+vnfzU71/iIjz\ngAuA83f5nE8Bnh8RzwHuDdwvIj6cmS/b+sD+oqxytVpjwDon7mjXmZhw9UFJKp37cI2qrQdZ5+bm\ndr2NHU/mi4iDmfmNWhvbxWN7j38a8GeezDfcqua3TU2VM7+tpBNmNpmpHjPtrLQ8YKa6SslU+j5c\nOltO52S+OkX5LcDNnLh+8gkP6bu9PzPfWvvJLcojY/OM6csuO8LMzFxRZ0yX8mHUz0z1mGlnpeUB\nM9VVUqaS9+HS2XJOinLFk3wMuB34KvCVzPzerjZQ/3ksykOopB3/JjPVY6Z6SstUWh4wU11mkgZr\nIEW590SPAJ5I9+S+i4BPA+3M/L9db2z757AoD6ESd7JmqsdM9ZSWqbQ8YKa6zCQN1qCOKD+h93tX\n9u6/EPgm8HuZ+Xe72tipn8eiPIRK3MmaqR4z1VNaptLygJnqMpM0WIO64Mgh4M7elfXW6c5f/g/g\nB6exLUmSJKlIp1OU/xm4X2b+zeYPIuIPgeWzlkqSJElq2GnNUR4Ep14MpxK/tjNTPWaqp7RMpeUB\nM9VlJmmwTmfqhauJS5IkSRVOZ+qFCrC55uXq6gat1phrXkqSRoafcSqFUy+GUMlXUSrxazsz1WOm\nekrLVFoeMFNdZqpW8mechptTL/aIdnu+bwcCMM7S0hzt9nyDqSRJOnN+xqkkFuUhtLq6wfEdyKZx\n1tY2mogjSdJZ42ecSmJRHkKt1hjdJaz7rTMx4f9OSdJw8zNOJfFVN4Q6nVmmpo5wfEfSnb/V6cw2\nlkmSpLPBzziVxKI8hCYnD7CwcJiZmWMAzMwc8yQHSdJI8DNOJXHViyFXwhnK/UrLA2aqy0z1lJap\ntDxgprrMtLPS8mi4ueqFJEmSdJZYlCVJkqQKFmVJkiSpgkVZkiRJqjDwohwR+yPiixFxQ0RcHxGv\nHnQGSZIkaSf7GnjOu4DXZeZ1EXFf4OsRcUVmfreBLJIkSVKlgRflzPwh8MPe7dsj4kagBRRblJeX\nV2i351ld3aDVGqPTmXU9R0mS9hC7wN7UxBHlu0XEw4ALga81meNUlpdXOHToUpaW5uhee36dK688\n4uLnkiTtEXaBvauxk/l60y4uB16Tmbc3lWMn7fZ83xsDYJylpTna7fkGU0mSpEGxC+xdjRxRjoh9\ndEvyRzLz09s97ujRo3ffnp6eZnp6+pxn22p1dYPjb4xN46ytbQw8iyRJGjy7wHBaXFxkcXHxjLbR\n1NSLDwA3ZOa7TvWg/qLclFZrDFjnxDfIOhMTrqwnSdJeYBcYTlsPss7Nze16G00sD/cUYAb43Yi4\nNiK+ERHPGnSOujqdWaamjtB9gwCsMzV1hE5ntrFMkiRpcOwCe9fAi3JmfiUzz8vMCzPzsZl5MDM/\nN+gcdU1OHmBh4TAzM8cAmJk55uR9SZL2ELvA3hWZ2XSGShGRpWWLgMIiFZeptDxgprrMVE9pmUrL\nA2aqy0w7Ky0PlJlJ9UQEmRm7+R0n10iSJEkVLMqSJElSBYuyJEmSVMGiLEmSJFWwKEuSJEkVLMqS\nJElShaKL8ktfOsfy8krTMSRJkoqzvLzCS186x9OffsTOdI4UvY4y3M7U1JFiFvUuce3E0jKVlgfM\nVJeZ6iktU2l5wEx1mWlnpeWBcjItL69w6NClLC3N0b209npRnalEI7iO8jhLS3O02/NNB5EkSSpG\nuz3fV5LBznRuFF6UAcZZW9toOoQkSVIxVlc3OF6SN9mZzrYhKMrrTEwMQUxJkqQBabXGgPUtP7Uz\nnW2Fj2Z3vk2nM9t0EEmSpGJ0OrNMTR3heFm2M50LRRflmZljTkqXJEnaYnLyAAsLh5mZOQbYmc6V\nole9KC1bKWe69istU2l5wEx1mame0jKVlgfMVJeZdlZaHjDTMBvBVS8kSZKkZliUJUmSpAoWZUmS\nJKmCRVmSJEmq0EhRjohnRcR3I+L7EfGGJjJIkiRJpzLwohwRY8C7gWcC5wMvjohHDTqHJEmSdCpN\nHFF+PPCDzFzJzDuBjwEXN5BDkiRJ2lYTRbkF3NJ3/9bezyRJkqRiNFGUqxZ6dplsSZIkFWVfA895\nK/DQvvv7gbWqBx6N4516uvdPkxKqa36DSstUWh4wU11mqqe0TKXlATPVZaadlZYHCs7kMceTLC4u\nsri4eEbbGPglrCPiPOB7wEXAvwNXAS/OzBu3PK64S1hLkiRpOJ3OJawHfkQ5M38REa8CrqA79eP9\nW0uyJEmS1LSBH1GuyyPKkiRJOltO54iyV+aTJEmSKliUJUmSpAoWZUmSJKmCRXnInemyJ3uBY1SP\n41SP47Qzx6gex2lnjlE9jtO5Y1Eecr45duYY1eM41eM47cwxqsdx2pljVI/jdO5YlCVJkqQKFmVJ\nkiSpQtHrKDedQZIkSaNjt+soF1uUJUmSpCY59UKSJEmqYFGWJEmSKhRZlCPiWRHx3Yj4fkS8oek8\npYmI/RHxxYi4ISKuj4hXN52pZBExFhHfiIjPNJ2lRBHxgIj4RETcGBHfiYgnNJ2pRBHx2oj4dkR8\nKyIui4h7Np2pBBHx/oi4LSK+1fezX4qIKyLiexHx+Yh4QJMZS7DNOL299767LiL+KSLu32TGplWN\nUd9/+/OI2IiIX24iW0m2G6eIONzrTtdHxNuayleKbd5zF0TEv0XEtRFxVUT89k7bKa4oR8QY8G7g\nmcD5wIsj4lHNpirOXcDrMvPXgScBf+oYndJrgBuaDlGwdwGfzcxHAxcANzacpzgRMQEcBg5m5mOA\nfcCLmk1VjA/S3V/3eyPwhcz8NeCLwF8OPFV5qsbpCuD8zLwQ+AGOU9UYERH7gWcAKwNPVKaTxiki\npoHnAb+Rmb8JHGsgV2mqXk9vB45k5mOBI8Df7rSR4ooy8HjgB5m5kpl3Ah8DLm44U1Ey84eZeV3v\n9u10i02r2VRl6u1gnwO8r+ksJYqI+wFPzcwPAmTmXZn5Pw3HKtV5wHhE7APuA6w1nKcImfmvwH9t\n+fHFwId6tz8E/P5AQxWoapwy8wuZudG7eyWwf+DBCrLNawngncDrBxynWNuM0yuBt2XmXb3H/Hjg\nwQqzzThtAJvfcD0QWN1pOyUW5RZwS9/9W7EEbisiHgZcCHyt2STF2tzBurxLtYcDP46ID/amp7w3\nIu7ddKjSZOYa8A7gZro71p9m5heaTVW0B2fmbdD9wx74lYbzDINXAP/SdIjSRMTzgFsy8/qmsxTu\nkcDvRMSVEfGlOlMK9qjXAsci4ma6R5d3/BanxKJctb6dJadCRNwXuBx4Te/IsvpExHOB23pH34Pq\n19Zetw84CLwnMw8CP6P7tbn6RMQD6R4lPQBMAPeNiJc0m0qjIiLeDNyZmR9tOktJen+0v5nuV+R3\n/7ihOKXbBzwwM58I/AXw8YbzlOqVdDvTQ+mW5g/s9AslFuVbgYf23d+PX3GepPf17+XARzLz003n\nKdRTgOdHxE3APwJPj4gPN5ypNLfSPVpzTe/+5XSLs070DOCmzPxJZv4C+CTw5IYzley2iPhVgIh4\nCPCjhvMUKyIuoTs9zD+8TjYFPAz4ZkQs0+0DX4+IBzeaqky30N0vkZlXAxsR8aBmIxXpksz8FEBm\nXk53uu8plViUrwYeEREHemeVvwhwtYKTfQC4ITPf1XSQUmXmmzLzoZn5cLqvoy9m5suazlWS3tfj\nt0TEI3s/ughPfKxyM/DEiLhXRATdcfKkx+O2fmPzGWC2d/sSwD/mu04Yp4h4Ft2jf8/PzDsaS1WW\nu8coM7+dmQ/JzIdn5iTdP+wfm5n+4XXye+5TdPdL9Pbn98jM/2wiWGG2jtNqRDwNICIuAr6/0wb2\nnaNgpy0zfxERr6J7NvAY8P7M9AOpT0Q8BZgBro+Ia+lOTXlTZn6u2WQaUq8GLouIewA3AS9vOE9x\nMvOqiLgcuBa4s/fv9zabqgwR8VFgGnhQb97fEeBtwCci4hV0/8h4YXMJy7DNOL0JuCew0P37iysz\n808aC9mwqjHaPNG4J3HqxXavpQ8AH4yI64E7gD1/UGibcfoj4O8j4jzgf4E/3nE7XsJakiRJOlmJ\nUy8kSZKkxlmUJUmSpAoWZUmSJKmCRVmSJEmqYFGWJEmSKliUJUmSpAoWZUmSJKmCRVmSJEmqYFGW\nJEmSKliUJWlIRcQzI+LqpnNI0qiyKEvS8LoO+HrTISRpVFmUJWl4PQn4atMhJGlUWZQlaXg9Cbgq\nIl4QEddExL6mA0nSKLEoS9LwuhA4mJmfBJ6amXc1HUiSRolFWZKGUEScB9wB7I+Il2Xmz5vOJEmj\nxqIsScPpAuAa4OPA4yLi2Q3nkaSRY1GWpOF0PvBl4Ed0jyx7RFmSzrLIzKYzSJIkScXxiLIkSZJU\nwaIsSZIkVbAoS5IkSRUsypIkSVIFi7IkSZJUwaIsSZIkVbAoS5IkSRUsypIkSVKF/weAyLiOPHpj\nbwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1085d9f98>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from tools import cconv\n",
    "\n",
    "L = 8  # length of signal x[k]\n",
    "N = 10  # length of signal h[k]\n",
    "P = 14 # periodicity of periodic convolution\n",
    "\n",
    "# generate signals\n",
    "x = np.ones(L)\n",
    "h = np.ones(N)\n",
    "\n",
    "# linear convolution\n",
    "y1 = np.convolve(x, h, 'full')\n",
    "# periodic convolution\n",
    "y2 = cconv(x, h, P)\n",
    "# linear convolution via periodic convolution\n",
    "xp = np.append(x, np.zeros(N-1))\n",
    "hp = np.append(h, np.zeros(L-1))\n",
    "y3 = cconv(xp, hp, L+N-1)\n",
    "\n",
    "# plot results\n",
    "def plot_signal(x):\n",
    "    plt.stem(x)\n",
    "    plt.xlabel('$k$')\n",
    "    plt.ylabel('$y[k]$')\n",
    "    plt.xlim([0, N+L])\n",
    "    plt.gca().margins(y=0.1)\n",
    "\n",
    "plt.figure(figsize = (10, 8))\n",
    "plt.subplot(3,1,1)\n",
    "plot_signal(y1)\n",
    "plt.title('Linear convolution')\n",
    "\n",
    "plt.subplot(3,1,2)\n",
    "plot_signal(y2)\n",
    "plt.title('Periodic convolution with period $P=%d$'%P)\n",
    "\n",
    "plt.subplot(3,1,3)\n",
    "plot_signal(y3)\n",
    "plt.title('Linear convolution as periodic convolution')\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**\n",
    "\n",
    "* Change the lengths `L`, `N` and `P` and check how the results for the different convolutions change."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Fast Convolution Algorithm\n",
    "\n",
    "Using the above derived equality of the linear and periodic convolution one can express the linear convolution $y[k] = x_L[k] * h_N[k]$ by the DFT as\n",
    "\n",
    "$$ y[k] = \\text{IDFT}_M \\{ \\; \\text{DFT}_M\\{ x_M[k] \\} \\cdot \\text{DFT}_M\\{ h_M[k] \\} \\; \\} $$\n",
    "\n",
    "The resulting algorithm is composed of the following steps\n",
    "\n",
    "1. Zero-padding of the two input signals $x_L[k]$ and $h_N[k]$ to at least a total length of $M \\geq N+L-1$\n",
    "\n",
    "2. Computation of the DFTs $X[\\mu]$ and $H[\\mu]$ using a FFT of length $M$\n",
    "\n",
    "3. Multiplication of the spectra $Y[\\mu] = X[\\mu] \\cdot H[\\mu]$\n",
    "\n",
    "4. Inverse DFT of $Y[\\mu]$ using an inverse FFT of length $M$\n",
    "\n",
    "The algorithm requires two DFTs of length $M$, $M$ complex multiplications and one IDFT of length $M$. On first sight this does not seem to be an improvement, since one DFT/IDFT requires $M^2$ complex multiplications and $M \\cdot (M-1)$ complex additions. The overall numerical complexity is hence in the order of $\\mathcal{O}(M^2)$. The DFT can be realized efficiently by the [fast Fourier transformation](fast_fourier_transform.ipynb) (FFT), which lowers the number of numerical operations for each DFT/IDFT significantly. The actual gain depends on the particular implementation of the FFT. Many FFTs are most efficient for lengths which are a power of two. It therefore can make sense, in terms of the number of numerical operations, to choose $M$ as a power of two instead of the shortest possible length $N+L-1$. In this case, the numerical complexity of the radix-2 algorithm is on the order of $\\mathcal{O}(M \\log_2 M)$.\n",
    "\n",
    "The introduced algorithm is known as *fast convolution* due to its computational efficiency when realized by the FFT. For real valued signals $x[k] \\in \\mathbb{R}$ and $h[k] \\in \\mathbb{R}$ the number of numerical operations can be reduced further by using a real valued FFT."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example\n",
    "\n",
    "The implementation of the fast convolution algorithm is straightforward. In the following example the fast convolution of two real-valued signals $x[k] = \\text{rect}_L[k]$ and $h[k] = \\text{rect}_N[k]$ is shown. The real valued FFT/IFFT is consequently used. Most implementations of the FFT include the zero-padding to a given length $M$, e.g as in `numpy` by `numpy.fft.rfft(x, M)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAlwAAADXCAYAAADP9I+CAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGKBJREFUeJzt3X1wZXd93/H3VyxpbJmnpEC6oqxlpW6BQh0nBAIpuQRv\nQkkM6bSd0lw1KH2aSdNdT6jz0NIbSb0Thna2SRkn+YOJsUhWhjYOJZAhxWLoTYakCwbbYGOTeoSy\n2NqxGxfiYtEhNvr2j3u1K8vn7mpXOvf8JL1fMzu+uvfo/j5zfO85X53fw4nMRJIkSfUZazqAJEnS\nfmfBJUmSVDMLLkmSpJpZcEmSJNXMgkuSJKlmFlySJEk1q73giogbIuKewb/jdbcnSZJUmloLroh4\nGfBPge8BrgGuj4ipOtuUJEkqTd1XuF4CnMrMb2TmN4E/AP5uzW1KkiQVpe6C617gdRHxvIi4HHgT\n8FdrblOSJKkoh+p888z8YkT8B+DjwNeAu4Ent24XEd5fSJIk7RmZGRezfe2D5jPzlsz87sxsAV8F\nHhiynf82/ZudnW08Q4n/3C/uF/eL+8T94n5p+t+lqPUKF0BEPD8z/ywiXkx//Nb31d2mJElSSWov\nuIDfiYhvA54A/mVmPjaCNiVJkopRe8GVma+ru439qNVqNR2hSO6Xau6Xau6Xp3OfVHO/VHO/7J64\n1L7IXQ0RkSXkkCRJupCIIC9y0PwouhQlHQArK6fpdBZYXV1nYmKMbneGyckjBz6LJIFXuCTtgpWV\n0xw9ehPLy/PAOLDG1NQsS0vHRl7olJRF0v50KVe4vHm1pB3rdBY2FTgA4ywvz9PpLBzoLJK0wYJL\n0o6trq5zrsDZMM6ZM+sHOoskbbDgkrRjExNjwNqWZ9c4fHj0h5iSskjSBo9Aknas251hamqWc4VO\nf9xUtztzoLNI0gYLLkk7Njl5hKWlY7TbJwBot080Nki9pCyStMFZipJ2VQSU8nUuKYuk/cNZipIk\nSQWqveCKiJ+JiHsj4vMRsRgR31J3m5IkSSWpteCKiMPAMeDazHwF/ZXt31pnm5JUipWV00xPz/P6\n188yPT3PysrppiNJasgobu3zDGA8ItaBy4EzI2hTOhC8hU25qla8P3XKFe+lg6r2QfMRcRz4JeDr\nwO2Z+Y8rtnHQvHSRSr2FTUkD1ZvMMj09z+LijTx1EdY12u0TnDw520woSbuiuJtXR8RzgbcAR4DH\ngNsi4scz89at287NzZ193Gq1aLVadUaT9rzht7DxhF4CV7yX9o9er0ev19vRe9TdpXgd8KXM/ApA\nRHwQeA1w3oJL0oV5Qi/buRXvn3qFyxXvpb1n64Wg+fn5i36Pur/5XwZeHRHfGhEBvAG4v+Y2pQPB\nW9iUzRXvJW1W65E5Mz8N3AbcBXwOCOA9dbYpHRSe0MvmiveSNnOleWkP25iluLg4S7s9X8QsRQfN\nl5tD0u64lEHzFlzSPlDSCd0s5eaQtDu8tY8kSVKBLLgkSZJqZsElSZJUMwsuSZKkmllwSZIk1cyC\nS5IkqWYWXJIkSTWz4JIkSapZrQVXRFwdEXdFxJ2D/z4WEcfrbFOSJKk0I1tpPiLGgIeAV2Xmg1te\nc6V5aQdKWsncLOXmkLQ7Sl9p/jpgeWuxJUmStN+NsuD6h8D7R9ieJElSEUbSpRgRzwTOAC/NzD+r\neN0uRWkHSuqyMku5OSTtjkvpUjxUV5gt/g7w2apia8Pc3NzZx61Wi1arVX8qSZKkC+j1evR6vR29\nx6iucL0f+O+Z+b4hr3uFS9qBkq6gmKXcHJJ2x6Vc4aq94IqIy4AvA1dl5teGbGPBJe1ASSd0s5SZ\nY2XlNJ3OAqur60xMjNHtzjA5eaTZUNIeVWTBta0QFlzaQ0o8cZVwQt9glvJyrKyc5ujRm1hengfG\ngTWmpmZZWjrW+GdX2ossuKSalXriavqEvplZyssxPT3P4uKN9D+zG9Zot09w8uRsU7GkPav0dbik\nPa/TWdhUbAGMs7w8T6ez0GAq6fxWV9d5arEFMM6ZM+tNxJEOJAsu6SJ44tJeNDExBqxteXaNw4c9\nBUij4rdNugieuLQXdbszTE3Ncu6z2+8K73ZnGsskHTSeJaSL4IlLe9Hk5BGWlo7Rbp8AoN0+0fi4\nQ+mgcdC8dJE2ZikuLs7Sbs87S3ELs5SbA8rKIu1VzlKURqikE5dZqpWSpZQcUFYWaa9ylqIkSVKB\nLLgkSZJqZsElSZJUs9oLroh4TkT8dkTcHxFfiIhX1d2mJElSSQ6NoI13Ax/NzH8QEYeAy0fQpiRJ\nUjFqnaUYEc8C7s7MqQts5yxF7TklzfYyS7VSspSSA8rKIu1VJc5SvAp4NCJuiYg7I+I9EXFZzW1K\nkiQVpe4uxUPAtcBPZ+ZnIuI/A78APO329HNzc2cft1otWq1WzdEkSZIurNfr0ev1dvQedXcpvhD4\nn5l51eDn7wd+PjOv37KdXYrac0rqmjFLtVKylJIDysoi7VXFdSlm5iPAgxFx9eCpNwD31dmmJElS\naUYxS/E4sBgRzwS+BPzkCNqUJBVq436kq6vrTEyMFXE/Uqlu3ktRe0KJB+iSumbMUq2ULKXkgOaz\nrKyc5ujRm1hengfGgTWmpmZZWjrW+Hda2i5vXq19qdQDdNMnrs3MUq2ULKXkgOazTE/Ps7h4I/3v\n8oY12u0TnDz5tPlUUpGKG8Ml7YZOZ2FTsQUwzvLyPJ3OQoOpJF2K1dV1nlpsAYxz5sx6E3GkkbHg\nUvE8QEv7x8TEGLC25dk1Dh/2dKT9zU+4iucBWto/ut0ZpqZmOfed7g8R6HZnGsskjYJnLBXPA7S0\nf0xOHmFp6Rjt9gkA2u0TjY/HlEbBQfPaEzZmKS4uztJuzztLcQuzVCslSyk5wCzSbnCWova9kg7Q\nZqlmlnJzgFmk3eAsRUmSpAJZcEmSJNXMgkuSJKlmtd9LMSL+FHgMWAeeyMzvrbtNSZKkkozi5tXr\nQCszvzqCtiRJkoozii7FGFE7kiRJRRpFIZTAxyLijoj45yNoT5IkqSij6FJ8TWY+HBHPB5Yi4v7M\n/OTWjebm5s4+brVatFqtEUSTJEk6v16vR6/X29F7jHTh04iYBb6Wmb+85XkXPtW2lLRQolmqmaXc\nHGAWaTcUt/BpRFweEVcMHo8DPwTcW2ebkiRJpRnapRgRH97G738lM2fO8/oLgf8WETloazEzb7+4\niJIkSXvb+cZwvQT4Z+d5PYBfO9+bZ+YKcM0l5JIkSdo3zldwvSMz/+B8vxwR87ucR5Ikad+54KD5\niLgyM/90y3OvzMw7di2Eg+a1TSUNsjVLNbOUmwPMstXKymk6nQVWV9eZmBij251hcvJIs6FUvEsZ\nNL+dgutO4PrMXB38/APAr2bmyy856dPbsOAqUIkHohIO0BvMUs0s5eYAs2y2snKao0dvYnl5HhgH\n1piammVp6VjjxzqVra6C65XArwPXA9cC76RfgD14qUEr2rDgKkypB6KmD9CbmaWaWcrNAWbZbHp6\nnsXFG+kf4zas0W6f4OTJ2aZiaQ+oZVmIQdfhceB2YA44upvFlsrU6SxsKrYAxllenqfTWWgwlSTt\nntXVdZ5abAGMc+bMehNxtM+db1mIj9C/Lc+Gy4HHgJsHld2b6w6n5nggkrTfTUyMAWtsvcJ1+LC3\n/9XuO98sxRMjS6HieCCStN91uzOcOjX7tKET3e6xhpNpPxrprX2GhnAMV3Ecw3VhZqlmlnJzgFm2\n2pgctLg4S7s9X8TkIJVvVwfNR8TvZeaPXqDBC26zrRAWXEUq8UBUwgF6g1mqmaXcHGCWYUrKovLt\ndsH158Afnu93gZdl5lXbCDYGfAZ4qGrslwVX2Uo6EJmlmlmqlZKllBxglmFKyqLyXUrBdb4xXG8Z\n/PcVwEPAVyq2+YtttnMDcB/w7O1HkyRJ2h+GFlwbt/WJiKP0C6Y7gfcCH7uYy1ER8SLgTcAvAW/f\nUVpJkqQ9aDvrcP074K8BNwMzwAMR8c6ImNpmG78C/CxPXWJCkiTpwDhfl+JZmZkR8TDwMPAk8Dzg\ntohYysyfG/Z7EfEjwCOZeXdEtOiP+6o0Nzd39nGr1aLVam0nmiRJUq16vR69Xm9H77GdW/scB94G\nPAr8BvChzHxiMBD+gcwceqUrIt4JTNMv0i4DngV8MDN/Yst2DpovWEmDSc1SzSzVSslSSg4wyzAl\nZVH56rqX4r8Hbs7M0xWvvSQz799muB8A/rWzFPeekg5EZqlmlmqlZCklB5hlmJKyqHy7PUsRgMz8\nxfO8tq1iS5Ik6SBzpXldUEl/+ZmlmlmqlZKllBxglmFKyqLyXcoVLm+MJ0mSVDMLLkmSpJpZcEmS\nJNXMgkuSJKlm21r4VJIk1Wtl5TSdzgKrq+tMTIzR7c4wOXmk6VjaJRZchfELJ0kHz8rKaY4evYnl\n5XlgHFjj1KlZlpaOeQ7YJ1wWoiBVX7ipqea/cCVNlzZLNbNUKyVLKTnALMM0nWV6ep7FxRvpH/s3\nrNFun+DkydmmYmkIl4XY4zqdhU3FFsA4y8vzdDoLDaaSJNVtdXWdpxZbAOOcObPeRBzVwIKrIH7h\nJOlgmpgYA9a2PLvG4cOepvcL/08WxC+cJB1M3e4MU1OznDsH9IeUdLszjWXS7qr1TB4RfykiPhUR\nd0XEPRFhR/R5+IWTpINpcvIIS0vHaLdPANBun2h8/K52V+2D5iPi8sz8ekQ8A/gj4HhmfnrLNg6a\nH9iYpbi4OEu7PV/ELMWmB5NuZpZqZqlWSpZScoBZhjGLLsalDJof2SzFiLgc+EPgpzLzji2vWXBt\nUdIXzizVzFLNLOXmALMMYxZdjCJnKUbEWETcBTwMLG0ttiRJkva72hc+zcx14Lsi4tnAhyLipZl5\n39bt5ubmzj5utVq0Wq26o0mSJF1Qr9ej1+vt6D1GuvBpRPwi8Hhm/vKW5+1S3KKkS8pmqWaWamYp\nNweYZRiz6GIU16UYEX85Ip4zeHwZcB3wxTrblCRJKk3dXYp/BXhfRIzRL+7+S2Z+tOY2JUmSiuK9\nFAtV0iVls1QzSzWzlJsDzDKMWXQxiutSlCRJkgWXJElS7Sy4JEmSambBJUmSVDMLLkmSpJpZcEmS\nJNWs9lv7SJKkvWVl5TSdzgKrq+tMTIzR7c4wOXmk6Vh7mgUXfrAkSdqwsnKao0dvYnl5HhgH1jh1\napalpWOeG3fgwC98WvXBmppq/oNV0sJ3ZqlmlmpmKTcHmGUYs5wzPT3P4uKN9M+JG9Zot09w8uRs\nU7GKUtzCpxHxooj4RETcFxH3RMTxOtu7FJ3OwqZiC2Cc5eV5Op2FBlNJktSM1dV1nlpsAYxz5sx6\nE3H2jbq7FJ8E3p6Zd0fEFcBnI+L2zCzmBtZ+sCRJOmdiYgxYY+sVrsOHnWe3E7Xuvcx8ODPvHjx+\nHLgfmKizzYt17oO1mR8sSdLB1O3OMDU1y7lzY3+oTbc701im/WBkVUVEXAlcA3xqVG1uhx8sSZLO\nmZw8wtLSMdrtEwC02ycaH9e8H4xk0PygO7EHdDPzdyteb2zQPJybpbi4OEu7PV/ELMWmB01uZpZq\nZqlmlnJzgFmGMUu1krKU5FIGzddecEXEIeD3gN/PzHcP2SZnZ8/NfGi1WrRarVpzVeco54Nllmpm\nqWaWaqVkKSUHmGUYs1QrKUuTer0evV7v7M/z8/NFFly/CTyamW8/zzaNXuE6l6OcD5ZZqpmlmlmq\nlZKllBxglmHMUq2kLCUpcVmI1wJt4Acj4q6IuDMi3lhnm5IkSaWpdVmIzPwj4Bl1tiFJklQ61z6Q\nJEmqmQWXJElSzSy4JEmSambBJUmSVDMLLkmSpJpZcEmSJNXMgkuSJKlmFlySJEk1s+CSJEmqWa0r\nzUuSJO3EysppOp0FVlfXmZgYo9udYXLySNOxLlrd91K8OSIeiYjPX2jb6el5VlZO1xlHkiTtISsr\npzl69CYWF2+k15tncfFGjh69aU/WC3V3Kd4C/PB2NtzLO1GSJO2+TmeB5eV5YHzwzDjLy/N0OgsN\npro0tRZcmflJ4Kvb23rv7kRJkrT7VlfXOVdsbRjnzJn1JuLsSGGD5vfmTpQkSbtvYmIMWNvy7BqH\nDxdWvmxDQYPm54C/4NFH/5her0er1Wo4jyRJalK3O8OpU7ObuhXXmJqapds9NtIcvV6PXq+3o/eI\nzNydNMMaiDgCfCQzX3GebRIeZ2pqlqWlY43NPoiAmnfHtpmlmlmqmaVaKVlKyQFmGcYs1UrIsjFL\ncXFxlnZ7vohZihFBZsZF/c4ICq4r6RdcLz/PNtluzzW+E0v4YG0wSzWzVDNLtVKylJIDzDKMWaqZ\npVpxBVdE3Aq0gG8HHgFmM/OWiu2y7sJvO8r6n2mWKmapZpZqpWQpJQeYZRizVDNLteIKrm2HsOB6\nGrNUM0s1s1QrJUspOcAsw5ilmlmqXUrBtfeG+UuSJO0xFlySJEk1s+CSJEmqmQWXJElSzSy4JEmS\nambBJUmSVDMLLkmSpJpZcEmSJNXMgkuSJKlmFlySJEk1q73giog3RsQXI+J/RcTP193e/tFrOkCh\nek0HKFSv6QCF6jUdoEC9pgMUqtd0gEL1mg6wb9RacEXEGPCrwA8DLwP+UUT8jTrb3D96TQcoVK/p\nAIXqNR2gUL2mAxSo13SAQvWaDlCoXtMB9o26r3B9L/BAZp7OzCeADwBvqblNSZKkotRdcE0AD276\n+aHBc5IkSQdGZGZ9bx7x94Efysx/Mfh5GnhlZt6wZbv6QkiSJO2yzIyL2f5QXUEGHgJevOnnFwFn\ntm50saElSZL2krq7FO8AvjMijkTEtwBvBT5cc5uSJElFqfUKV2Z+MyL+FXA7/eLu5sy8v842JUmS\nSlPrGC5JkiQ1vNK8i6I+XUS8KCI+ERH3RcQ9EXG86UyliIixiLgzIuyWHoiI50TEb0fE/RHxhYh4\nVdOZShARPxMR90bE5yNicTCk4cCJiJsj4pGI+Pym554XEbdHxJ9ExMci4jlNZmzCkP3yHwffo7sj\n4nci4tlNZmxC1X7Z9NqNEbEeEd/WRLamDNsnEXFsUL/cExHv2s57NVZwuSjqUE8Cb8/MlwLfB/y0\n++WsG4D7mg5RmHcDH83MlwB/CzjwXfYRcRg4Blybma+gP3Tirc2maswt9I+xm/0C8PHM/OvAJ4B/\nM/JUzavaL7cDL8vMa4AHcL+cFREvAq4DTo88UfOetk8iogVcD/zNzHw5cGI7b9TkFS4XRa2QmQ9n\n5t2Dx4/TP4Ee+LXLBl/4NwG/0XSWUkTEs4C/nZm3AGTmk5n5fxuOVYpnAOMRcQi4nIrZ0QdBZn4S\n+OqWp98CvG/w+H3Aj400VAGq9ktmfjwz1wc/nqI/q/5AGfJ5AfgV4GdHHKcIQ/bJTwHvyswnB9s8\nup33arLgclHUC4iIK4FrgE81m6QIG194Bx2ecxXwaETcMuhqfU9EXNZ0qKZl5hngPwFfBlaBP8/M\njzebqigvyMxHoP8HHvD8hvOU6J8Av990iBJExPXAg5l5T9NZCnI18LqIOBUR/yMivmc7v9RkwVW1\n9pYn04GIuAK4DbhhcKXrwIqIHwEeGVz5C6o/OwfRIeBa4Ncy81rg6/S7iw60iHgu/as4R4DDwBUR\n8ePNptJeERHvAJ7IzFubztK0wR9w7wBmNz/dUJySHAKem5mvBn4O+K/b+aUmC65tLYp6EA26QW4D\nfiszf7fpPAV4LfDmiPgS8H7g9RHxmw1nKsFD9P/y/Mzg59voF2AH3XXAlzLzK5n5TeCDwGsazlSS\nRyLihQAR8R3A/244TzEi4m30hy5YoPdNAVcCn4uIFfrn6c9GxAsaTdW8B+kfV8jMO4D1iPj2C/1S\nkwWXi6IO917gvsx8d9NBSpCZ/zYzX5yZV9H/nHwiM3+i6VxNG3QLPRgRVw+eegNOKoB+V+KrI+Jb\nIyLo75eDPJlg61XhDwMzg8dvAw7qH3VP2S8R8Ub6VyvenJnfaCxV887ul8y8NzO/IzOvysxJ+n/k\nfVdmHrQifet36EP0jysMjr/PzMz/c6E3aazgGvzlubEo6heAD7goKkTEa4E28IMRcddgbM4bm86l\nYh0HFiPibvqzFN/ZcJ7GZean6V/tuwv4HP0D5XsaDdWQiLgV+GPg6oj4ckT8JPAu4GhE/An9q4Hb\nmtK+nwzZLzcBVwBLg+PurzcasgFD9stmyQHrUhyyT94LXBUR9wC3Atu6AODCp5IkSTVrdOFTSZKk\ng8CCS5IkqWYWXJIkSTWz4JIkSaqZBZckSVLNLLgkSZJqZsElad8ZLKjsvd8kFcOCS9J+5SKDkoph\nwSVpX4uIqwYrh39301kkHVyHmg4gSXUZ3OfsA8DbMtMuRkmNseCStF+9gP5NZv+e92mV1DS7FCXt\nV48BDwLf33QQSfIKl6T96hvAjwG3R8Tjmfn+pgNJOrgsuCTtW5n5/yLiRzlXdH2k6UySDqbIdOa0\nJElSnRzDJUmSVDMLLkmSpJpZcEmSJNXMgkuSJKlmFlySJEk1s+CSJEmqmQWXJElSzf4/SYqvuolN\n1vAAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x108add5f8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "L = 8  # length of signal x[k]\n",
    "N = 10  # length of signal h[k]\n",
    "\n",
    "# generate signals\n",
    "x = np.ones(L)\n",
    "h = np.ones(N)\n",
    "\n",
    "# fast convolution\n",
    "M = N+L-1\n",
    "y = np.fft.irfft(np.fft.rfft(x, M)*np.fft.rfft(h, M))\n",
    "\n",
    "# show result\n",
    "plt.figure(figsize=(10, 3))\n",
    "plt.stem(y)\n",
    "plt.xlabel('k')\n",
    "plt.ylabel('y[k]');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Benchmark\n",
    "\n",
    "It was already argued that the numerical complexity of the fast convolution is considerably lower due to the usage of the FFT. As measure, the gain in terms of execution time with respect to the linear convolution is evaluated in the following. Both algorithms are executed for the convolution of two real-valued signals $x_L[k]$ and $h_N[k]$ of length $L=N=2^n$ for $n \\in \\mathbb{N}$. The length of the FFTs/IFFT was chosen as $M=2^{n+1}$. The results depend heavily on the implementation of the FFT and the hardware used. Note that the execution of the following script may take some time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA48AAAJsCAYAAABdzpaXAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3XmYbFV97//3B47MCiJ6UJFzgr+gMQSOOEaNNmqcEocY\n0QSj4DxFjfOQGNQbczVGxJvINU4ENDih0RgVjULJRYMK0gyCU7Rl8hxEPSDiwPD9/bF3Q9n0UKfr\nVO+uU+/X89TTtfb43VW1umv1Wt+1U1VIkiRJkrSY7boOQJIkSZK0+tl4lCRJkiQtycajJEmSJGlJ\nNh4lSZIkSUuy8ShJkiRJWpKNR0mSJEnSkmw8SppYSQ5LclLXccxKslOSTybZnORDXcezHEk+neRJ\nK3Su85LcfyXOtcD51yW5PsnE/C1tr3e/9vn/TfLXXcc0rCSHJ/l/i6z/kyQXJrkyyUErGVuXkhyb\n5PVD7N9p/ZQ0GhPzB0/S6LSNsK8l+VmSS5J8Ksl9u45rKVV1QlU9rOs4+jwOuDVwy6p6QtfBLCXJ\nkUmO719WVY+oqveN4Fw3+SJbVQdU1alb+1xbaFk3Sx7jhucN11tVz6mqN2ztEyzVmBuRxd7HNwPP\nrapbVNXZyz1Bf8N7W7OK66ekrWzc/mhJWmWSvBg4Cvg74DbAvsAxwKO6jGspSbbvOoZ5rAO+XVXL\napBorISmwZKuA9lCA8U7ZP2afW1Wi3XA+VvhOKvpmiRpWWw8Slq2JLcAXkfzX/lPVNUvquq6qvpU\nVb2i3WaHJEe3PZIXJ3lrkpu16x6Q5KIkL0uyqd3m0UkenuRbSS5P8qq+8x2Z5CNJPtgOITsjyYF9\n61+R5LvtuvOSPKZv3eFJTktyVJIfA0fO7eFoY9vUDhudTnKX2etMcnySy5J8v3+o3uwxkrw5yU+S\n/E+SBXszk9w5ySlJfprk3CSPbJe/Fvhb4M/a+J8yz75J8sr2Gn/Uvg57tOse3557t7b88CQ/THKr\nvvN+LsmPk1yQ5NC+4+6U5C1JZtq4Tk2y4+z7MyeG7yd5YJKHAq8GntD2OJ/Vrj8lyVP74v2b9rgb\nk/xr+5np73l7cpIftK/tqxd4zZ4BPBF4efvafKI/lr7PxoeTvK/d5uwkv92+Xpvaczy475i3SPLu\nJJe2n8H/lSTtujsm6bWfg8uSfGCh95OmofO09rN7SZp/piz5fgFfbH9ubuO9d/s63bXd9y/a1+fO\nbflpSf59gOPSHutL7Xt5VpIH9K07Jcnr09SFK5OclGTPBS+uqZuXpqm7T6GvAZS+3qbcWJdfnuSH\nwHvb5X/cxvDT9py/17f/Pkk+2r7GP0ryf9rr/b/A77efq58sENcRSc5vr+G7SZ7Zt242lhfnxt8r\nR/St3zPJfyS5IsnpwB0XOMcOSX5G813pnCTfaZcv9ntm3s9Oki/SfFbOafc7dIFzPqPvus5LsqFd\nPu/vjb734Z+T/Ge7338n+a123f9N8uY55/h4kr9qn//OQseds89NeoPbz+d+Gax+DvJ3YN73S9Iq\nU1U+fPjwsawH8FDg18B2i2zzeuDLwK3ax5eA17XrHgBcA/w1sD3wdOAy4P3ALsBdgF8A69vtjwR+\nBfxJu/1LgO8B27fr/xRY2z4/FLiqr3x4e67n0nwZ3LFddmq7/iHA14Cbt+U79e17PPDvbUzrgG8B\nT+k77q+Ap9J8OXw2cMkCr8Ua4DvAK9rnhwBXAr/dd33HL/Ja/lX7Wt4WuBnNl+wT+ta/j+ZL+57A\nJcDD2+W7ABcCT25j3AD8CPiddv3bgZOBvdv1926P/wDgwjkxfB944ELxAqcAT22fPxX4dvua7QJ8\ndHb7dtn1wL8AOwAHAr8E7rTAtR8LvH6JWK4GHty+v8e1n41XceNn63t9+36cpod8J2Av4HTgGe26\nE4BXtc93AO6zQEyz1/Bv7XEOoPn8PnCp96vd9zogfcf7V+BF7fN/aT8rz2rLxwEvHOC4twcuBx7a\nlh/Ulm/V9/58h6bBtGNb/vsFru9hwA+B3wF2bq/zOmC/ue8JN9blv29j2hE4GNgE3J3mc/Wk9j27\nWfseTQP/2L52N7zO9NXLRerCw7nx98IfAD8HNsyJ5cj2vX94u373dv0H28dOwO8CFy92vvY9/q2+\n8mK/Zxb87Mw9zjznORS4CDi4Le8H3IGlf28c277Hd2tf1/f3fR7+APhB3zn2oKknawc87uz7e5P3\nZKHPwgL1c5C/A/O+Xz58+Fhdj84D8OHDx/g+gMOAS5fY5ru0X2Tb8kNov8S3Xxp+TvsFGtit/YJ1\n977tzwAe1T4/Evhy37oAlwL3XeDcZwGPbJ8fDszMWd/feDwE+CZwL37zC/12zGnUAM8ETu47xrf7\n1u3cfqm6zTzx3G/u60XzZfNv+65vscbj+cAhfeXb0td4B3YHfgCcAxzTt93jgS/OOdY7gNe0r+HV\nwAHznG/YxuPngWf3rdt/Nl5ubDzdtm/9V4DHL3DtgzQeP9u37o9pvgj3f7auA25B88X5l8COfdv/\nGfCF9vlx7etz+yU+27ONx9/uW/Ym4F1LvV/A+jae7frWPxX4eN++T+XGRsAMcNAAx305cNycOE8C\nntT3/ry6b91zgE8vcH3voa9hCfw2izcefwncrG/7Y2gbCH3LvknToLk3TcPyJv94YoDG4zz7/Dvw\n/L5Yfj7ntd0E3LN9jX495z17w2Lna9/j/RZZ3/97ZsHPzgDHOWn2GuYsX+r3xrHAO/vWPRw4v688\nA9yvff504PPt8z8Y4LiLNR5vuB6Wrp+D/B24yfu1JZ8BHz58rMzDYauShvFjYK8sPunH7Wh6vWb9\noF12wzGqqtrnv2h/Xta3/hc0X/xn3TCMst3v4tnjpRkCOTtE7qc0vQp7zbfvXFV1CvDPNL1wG5O8\nI80Q0L1oekrmXsPt+8ob+47zC5oGWX/Ms243Twxzj7WYdcC/pxke+xOaRsQ1NI0hquoK4CM0133U\nnP3uPbtf+9oc1u63F00PzPcGjGFL3I7m+mb9gKaHY23fsk19z69m/tdtUP3H+gVw+ZzP1uz7si/N\ne/rDvtfjHTSTFQG8jKaR8dV2KN9NhhD3mf0Mzur/fC/2fhU39UXgD5Ksbc//IeB+SdYB/ZO1LHbc\ndcDj57zX96XpVZ61se/5Yq/53M/rD1g85/FHVXVNX3kd8JI5sezTHvcOND1i1y9yvAWlGZb932mG\nYf+UpsHUX9d/POfYs9d5a5rerbnv2Zace7HfM1vy2ZnrDsD/zLN8kN8bi72nHwL+vH1+GE0PMjT/\ndBjm99GWGOTvwHzvl6RVxsajpGH8N01vw2MW2eYSmi+Rs9bR9BYu1x1mnyQJzZfRS5PsC7yTJv/y\nllV1S+Ab/OaX3fm+sN+4suqfq+ruNF8G70TzRfBy4Np5ruGSZcR+aX/8rX234FgX0gxF3bN93LKq\ndq2qHwK0+VFPBT4A/FPffhcBvTn73aKq/pLm+n7B/HlfP6cZbkp7/O25sYEFS08Acik3fd2u4Tcb\neYNa6lxb4iKaz+2t+l6PParqQICquqyqnllVt6cZhnxMFp8ls/893ZcbP9+LvV83uZ6q+h+a9+IF\nNL08P6dpFDwTOK1v08WOexFNb3D/uptX1Zvnnm8AP5xzbevmi7v/EuaULwLeMCeW3arqQ+26fRf4\nx9Oi73WSHYATgX8Abt3W9c8w2GQ+P6LpPZ37ng1kqd8zy/js9LuI+evhsL83PgA8ro39XjTDx7f0\nuHN/F+w9Z/1yfhcM83dAUkdsPEpatqq6kma44NvTTHSzc5I1ba/AG9vNPgj8TZK9kuxFM1RymFs5\n3C3JY9qGzItoGgGnA7vSDKO6PMl27X/8Dxj0oEnunuSeSdbQfIH/JXBd+9/wDwNvSLJb2wv0omVe\nw1eAn6eZVGRNkima4ZWLTcjS71+Av2+/BJLk1kke1T7fqY3plTQNyNsleU67338C+6eZhGVNkpu1\n13untmfuWOCoJLdtX7t7t5NZfBvYqX0/1wB/Q5PHNWsTsL5txM/nA8CLkqxve3HfAHywr4dhS2Ya\n3USTAza0qtoIfA54a5Kbp7Ff2nvSJXlcktnel800n6vrFjhcgNe0n/3fBZ5C85mHRd4vmkbM9dy0\nsfBF4C+5cUKd3pzyUsd9P/DIJA9p38ud2glJ+nt5BvVh4Ig0k6rsQjOh05Z4F/DsJPds49w1ySOS\n7Ap8laZx+sYku6SZoOk+7X6bgH1mJ1SZxw7t4/Kquj7Jw2mGQS6p/ex9FHht+57dhWZI5qAW/T2z\nxGdnI4t/ht8NvDTJwe2x7pjkDgz5e6Oqpmn+SfRu4KT29zZbeNyzgd9NcmCSHWl+7/c3GJeqnx9g\n6/4dkNQRG4+ShlJVbwVeTNOwuIymV+S5NBOSQHMLjzNo8vDObp8vdm+4uf/Bnlv+BPAE4Kc0M/z9\nSTUzvF4AvIWmIbmRpvfwNAZ3C5ovuz+hydW5nGYyD4Dn0wyj+h5wKvD+qjp2C66hWdgM6XsU8Ij2\n+P9Mk4v2nQFjfBvN9X8uyRU0E1Dcs1339zT5ie+sql/TTE7yv5Lcsaquovly/Wc0/+2/FHgjzaQm\nAC8FzqWZMOjH7brt2i+Zz6XJfbsY+Bm/OdzvIzSNpx8nOWOea38vzRfEU2mG411N06vGPNvOV+73\nHpovrz9J8rEBtp9P//ZPpmmAnE/znn+EG4d23gP4SpIraT7HL6iqhYY2Fk3D7rvAfwH/UFVfaNct\n+H61w5vfAHypvabZ9/GLNMP1Tl2gvNRxLwYeTTMT7o9ohge+lBv/3g/8mlXVScDRNJMpfRv4wuJ7\n3GT/M4FnAP+cZnjtt2kbam0j7pE0eZQX0vS6Pb7d9WSa3ryNSS6b57hX0XyOPtIe989oXo9Fw+l7\n/nzg5jSN1/e2j4H2HeD3zGKfndcCx7fv9+Pmua4TaT4TJ7T7/zuw5wC/NwZ5Tz9AM3nS7JDVQX4f\n9V/3d2gmvfkCzfs49z6cS9XPYf8OSFolZicSkKRVL8mRwB2r6sldxyJJkjRp7HmUJEmSJC3JxqMk\nSZIkaUkOW5UkSZIkLWlN1wGslCS2kiVJkiRNtKraktnOf8NEDVutqol8HHnkkZ3H0FVMW/s8W+N4\nyz3Glu63JdsPsu3hhx++Yp+P1fawDq2u41mHxu9hHVpdxxzXOlRlPeo6hq5i8m/R1ttuWBPVeJxU\nU1NTXYdwEysV09Y+z9Y43nKPsaX7bcn2q/EzspqsxtfHOjT6/axDW89qfH3GtQ5tjWNah8bTanyN\nxrUebYt/i1bqvZiYnMckNSnXKo3Ca1/7Wl772td2HYY0tqxD0vCsR9JwklAOW5U0aqvxP57SOLEO\nScOzHkndsvEoSZIkSVqSjUdJkiRJ0pLMeZQkSZKkCWDOoyRJkiRp5Gw8ShpIr9frOgRprFmHpOFZ\nj6Ru2XiUJEmSJC3JnEdJkiRJmgDmPEqSJEmSRs7Go6SBmGciDcc6JA3PeiR1y8ajJEmSJGlJ5jxK\nkiRJ0gQw51GSJEmSNHI2HiUNxDwTaTjWIWl41iOpWzYeJUmSJElLMudRkiRJkiaAOY+SJEmSpJGz\n8ShpIOaZSMOxDknDsx5J3bLxKEmSJElakjmPkiRJkjQBzHmUJEmSJI2cjUdJAzHPRBqOdUganvVI\n6paNR0mSJEnSksx5lCRJkqQJYM6jJEmSJGnkbDxKGoh5JtJwrEPS8KxHUrdsPEqSJEmSlmTOoyRJ\nkiRNAHMeJUmSJEkjZ+NR0kDMM5GGYx2Shmc9krpl41GSJEmStCRzHiVJkiRpApjzKEmSJEkaORuP\nkgZinok0HOuQNDzrkdQtG4+SJEmSpCWZ8yhJkiRJE8CcR0mSJEnSyNl4lDQQ80yk4ViHpOFZj6Ru\n2XiUJEmSJC3JnEdJkiRJmgDmPEqSJEmSRs7Go6SBmGciDcc6JA3PeiR1y8ajJEmSJGlJ5jxKkiRJ\n0gQw51GSJEmSNHI2HiUNxDwTaTjWIWl41iOpWzYeJUmSJElLMudRkiRJkiaAOY+SJEmSpJGz8Shp\nIOaZSMOxDknDsx5J3bLxKEmSJElakjmPkiRJkjQBzHmUJEmSJI2cjUdJAzHPRBqOdUganvVI6paN\nR0mSJEnSksx5lCRJkqQJYM6jJEmSJGnkbDxKGoh5JtJwrEPS8KxHUrdsPEqSJEmSlmTOoyRJkiRN\nAHMeJUmSJEkjZ+NR0kDMM5GGYx2Shmc9krpl41GSJEmStCRzHiUNJgHrkCRJ0tgy51GSJEmSNHI2\nHiUNpNd1ANKYM1dLGp71SOqWjUdJkiRJ0pLMeZQ0GHMeJUmSxpo5j5IkSZKkkbPxKGkgva4DkMac\nuVrS8KxHUrdsPEqSJEmSlmTOo6TBmPMoSZI01sx5lCRJkiSNnI1HSQPpdR2ANObM1ZKGZz2SumXj\nUZIkSZK0JHMeJQ3GnEdJkqSxZs6jJEmSJGnkbDxKGkiv6wCkMWeuljQ865HULRuPkiRJkqQlrek6\ngJWULHt4rzTxCuuQJEmr0dq169i4cabrMDQBJmrCnObrr6TlKEKsQ5IkrUJhUr7TazirfsKcJLsn\n+UiSC5J8I8m9khyZ5OIkX28fD2u3XZfk6r7lx/Qd5zNJzkpybpJj0tcFkuT5Sb7ZrnvjqK9JmkS9\nrgOQxl6v6wCkbUCv6wCkibYSw1bfBny6qg5NsgbYFXgYcFRVHTXP9t+tqoPnWX5oVV0FkORE4FDg\nw0kOAR4JHFBV1ybZazSXIUmSJEmTa6SNxyQ3B/6gqo4AqKprgSvaTsOFukvnXd7XcLwZsAM3jkF9\nNvDG9thU1eVbK35JN5rqOgBp7E11HYC0DZjqOgBpoo162Op+wOVJjm2Hob4zyS7tuuclmU7y7iR7\n9O2zPsmZSU5Jcr/+gyU5CdgIXAmc2C7eH7h/ktPbfe4+4muSJEmSpIkz6sbjGuBg4O3tUNSrgVcC\nxwB3rKoNNI3Bt7Tb/xDYt6ruBrwEOCHJbrMHq6qHAbcFdgQe2HeOParq3sDLgQ+P+JqkidTrOgBp\n7PW6DkDaBvS6DkCaaKPOebwYuKiqzmjLJwKvqKof9W3zLuCTAFX1a+DX7fOvJ/kfmp7Fr89uXFW/\nTvJJ4NHAF9pzfKxd97Uk1ye5VVX9+KbhHAGsb5/vAWzgxuEPvfanZcuW5ytP06/7eCxbHr8yS6y3\nbNny0uXpJdZParkt9Zry1NSUZcv0ej2mp6fZvHkzADMzMwxr5LfqSPJF4BlV9e0kRwK7AG+tqo3t\n+hcB96iqw9rJbn5SVdcn2Q/4IvB7wDXAzatqYzvpzvuBU6vqmCTPAm5XVUcm2R/4r6paN08c3qpD\nGoK36pAkabXyVh0azLC36liJ2VZfAPxbO9HN94CnAP+UZANwPTADPKvd9v7A65NcA1wHPKuqNie5\nDfAfSXYAtgdOBt7R7vNe4L1JzgV+BTx5Ba5JkiRJkibKyHseVwt7HqXhnEI4xDokDaHHjUPNJC1P\nD+vRfOx51GCG7XncbmsGI0mSJEnaNtnzKGkg5jxKkrRa2fOowdjzKEmSJEkaORuPkgbS6zoAaez1\nug5A2gb0ug5Ammg2HiVJkiRJSzLnUdJAzHmUJGm1MudRgzHnUZIkSZI0cmu6DmBlLbuRLU28HmAd\nkiRp9Vm7dl3XIWhCTFTj0e58afl6cUiMNIxer8fU1FTXYUhjzXokdWuich4n5VqlkUjAOiRJkjS2\nzHmUJEmSJI3cRA1bTczXkpbrFOAQ65AkacKtXbuOjRtnug5D6sRENR69VYc0jGAdkobRA6Y6jkEa\ndz26rkebNvmPVE2uicp59IuvtHze51GSJPCeihpnqzrnMcmOSb6S5Kwk5yY5sl3+/iTfTHJOkncn\n2b5d/tJ226+321+bZI923e5JPpLkgiTfSHKvdvlBSf673e+rSe4+ymuSJEmSpEk08p7HJLtU1dVt\nA/FLwAuAPavqpHb9CcAXq+pf5uz3x8BfVdWD2/K/ttsdm2QNsEtVXZnks8BbqupzSR4OvLyqDpkn\nDnsepSGcQjjEOiQNoUfXw+2k8dej+3pkz6PG17A9jyPPeayqq9unO7bnq9mGY+urwD7z7PrnwAcA\nktwc+IOqOqI95rXAle121wO7t8/3AC7ZmvFLkiRJklam53E74EzgjsDbq+pVfevWAF8BXlBVX+pb\nvjNwMXDHqtqc5CDgncD5wEHAGcALq+oXSe4MfJZmNo8A96mqi+aJw55HaQjmPEqSBPY8apyNQ8/j\n9cBdk9wC+HiSu1TV+e3qY2iGon5pzm6PBE6rqs19cR4MPK+qzkhyNPBK4EjgOTQNyY8neRzwXuAP\n54/mCGB9+3wPYAM3Dn3otT8tW7Y8X3l2yWqJx7Jly5YtW+6u3JZ6TXlqasqy5VVZnp6eZvPmpkk1\nMzPDsFZ0ttUkfwtcVVVHtZPnHFRVj51nu48BH66qD7bltcB/V9V+bfl+wCuq6pFJNlfVHn37XlFV\nu89zTHsepSGY8ygNq8eNX0AlLU+P7uuRPY8aX6t9ttW9kuzePt8ZeDDwzSRPBx5Ck9c4d5/dgQcA\nn5hdVlWbgIuS7N8uehDNEFaAS5I8oN33QcC3R3Q5kiRJkjSxRtrzmOT3gONoGqnbAR+qqjckuQaY\nAa6i6Q78WFX9XbvP4cBDq+qwOcc6CHg3cDPge8BTquqKJPcF3gZsD/wSeG5VnTVPLPY8SkMw51GS\nJLDnUeNs2J7HFR222iUbj9JwbDxKkgQ2HjXOVvWwVUnbjl7XAUhjr9d1ANI2oNd1ANJEs/EoSZIk\nSVqSw1YlDcRhq5IkgcNWNc4ctipJkiRJGjkbj5IG0us6AGns9boOQNoG9LoOQJpoNh4lSZIkSUta\n03UAK2vZw3uliTcFWIckSZNu7dp1XYcgdWaiGo8mN0tDiBMESJIkTTKHrUoaSK/rAKQx1+v1ug5B\nGnvWI6lbNh4lSZIkSUuaqPs8Tsq1SiORgHVIkiRpbA17n8eJynlMnOxDWq7COiRJk2zt2nVs3DjT\ndRiSOjRRjcfm66+k5egRrEPSMHrMzlssjaNNm7r/B2Kv12NqaqrrMKSJNfKcxyTvSbIpyTlzlj8/\nyTeTnJvkje2yeyQ5q+/xmL7tX5TkvCTnJPm3JDvMOd4/JfnZqK9HkiRJkibRyHMek9wPuAo4vqoO\nbJdNAa8GHlFV1ybZq6ouT7IT8Ouquj7J3sDZwG2BvYHTgDtX1a+TfAj4VFUd3x7vbsALgcdU1S0W\niKPsNZGWrwixDknSBPOWTdK4GzbnceQ9j1V1GvDTOYufA7yxqq5tt7m8/fnLqrq+3WZn4Pq+fbYH\ndk2yBtgFuBQgyXbAm4GXjewiJEmSJGnCdXWrjv2B+yc5PckpSe4+uyLJPZOcR9Pr+Oyqur6qLgXe\nAlwIXAJsrqrPt7v8JfDxqtoEdD8YX9pG9boOQBp7va4DkMae93mUutXVhDlrgD2q6t5J7gF8GNgP\noKq+ChyQ5E7A8Uk+Q9PT+GhgHXAFcGKSw4BTgEOBBwx22iOA9e3zPYAN3Dh5Qa/9admy5fnK0/Tr\nPh7LlsevzBLrLVte/eXZxtvspDUrXZ6enu70/JYtj1t5enqazZs3AzAzM8OwVuQ+j0nWAZ/sy3n8\nNM2w1VPb8neBe1XVj+fsdzLwUpqG5UOr6hnt8icB9wI+Dbwb+CVNr+O+wP9U1f7zxGDOozQEcx4l\nadKZ8yiNu1Wf89gKvzmk9OPAgwCS7A/crKp+nGR9ku3b5etohrfO0AxXvXeSndLcaO5BwAVV9emq\nul1V7VdVvwVcPV/DUZIkSZI0nJE3HpOcAHwZ2D/JhUmeArwX2C/JucAJwJPbze8HnJ3k68BHgedU\n1U/aoawnAmfR5EIGeOc8p/PfYdKI9LoOQBp7va4DkMaeOY9St0ae81hVhy2w6knzbPt+4P0LHOd1\nwOuWONe8t+mQJEmSJA1nRXIeVwNzHqXhmPMoSZPOnEdp3I1LzqMkSZIkaYzZeJQ0kF7XAUhjr9d1\nANLYM+dR6paNR0mSJEnSksx5lDQQcx4ladKZ8yiNO3MeJUmSJEkjZ+NR0kB6XQcgjb1e1wFIY8+c\nR6lbI7/P4+qy7B5aSYB1SJIm19q167oOQVLHJirncVKuVRqJBKxDkiRJY8ucR0mSJEnSyNl4lDSQ\nXtcBSGPOXC1peNYjqVsTlfOYmK8lLdcpWIckTa61a9exceNM12FIUqcmKufR+zxKy+d9HiVNNu9x\nKGn8jW3OY5IXJTkvyTlJ/i3Jjkmel+Q7Sa5Lsmfftnsk+ViSs5OcnuQu7fJ9kpyc5Pwk5yZ5QVfX\nI0mSJEnbsk4aj0luBzwfOLiqDqQZPvsE4DTgQcAP5uzyauCsqjoIOBz4P+3ya4EXV9VdgN8Hnpfk\nzitwCdLE6XUdgDT2el0HII09cx6lbnU5Yc72wK5J1gC7AJdW1dlVdSE3vZncXYAvAFTVt4D1SW5d\nVRurarpdfhVwAXD7FbsCSZIkSZoQnTQeq+pS4C3AhcAlwOaq+vwiu5wNPBYgyT2BfYF9+jdIsh7Y\nAHxl60csaarrAKSxN9V1ANLYm5qa6joEaaJ1NWx1D+DRwDrgdsBuSQ5bZJc3Ansm+TrwPOAsmiGr\ns8fbDTgReGHbAylJkiRJ2oq6ulXHg4HvVdVPAJJ8DLgPcEK7/jemM6uqnwFPnS0n+T7w/fb5GpqG\n4/uq6hOLn/YIYH37fA+ajsqpttxrf1q2bHm+8tH06z4ey5bHrzy7bLXEY3nLym2p15Rne8Asr2z5\n6KOPZsOGDasmHsuWV3t5enqazZs3AzAzM8OwOrlVRzv09D3APYBfAccCX6uqt7frvw/cvap+3JZ3\nB66uqmuSPAO4b1Ud0a47Hri8ql68xDm9VYc0hFMIh1iHpCH0uLFBovHjrTpWg16vd8MXY0lbbthb\ndXR2n8ckRwJ/BlxDMwz16cCzgZcDa4HLgE9X1TOT3Bs4nmao6vnA06rqiiT3BU4FzqVpGRbw6qo6\naZ7z2XiUhuB9HiVNNhuPksbf2DYeV5qNR2k4Nh4lTTYbj5LG37CNx+22ZjCStl29rgOQxl6v6wCk\nsTeb0yWRK1JxAAAgAElEQVSpGzYeJUmSJElLctiqpIE4bFXSZHPYqqTx57BVSZIkSdLI2XiUNJBe\n1wFIY6/XdQDS2DPnUeqWjUdJkiRJ0pLMeZQ0EHMeJU02cx4ljb9hcx7XbM1gVr9lv06SAOuQpEm1\ndu26rkOQpM5NVOPR/xhKy9eL/3WXhtHr9Ziamuo6DGmsWY+kbpnzKEmSJEla0kTlPE7KtUojkYB1\nSJIkaWyZ87gFEvO1pOUqrEPSpFq7dh0bN850HYYkqWMT1Xh0tlVp+XoE65A0jB4w1XEMy7Npk/84\n0upgzqPULXMeJUmSJElL6jTnMcl2wBnAxVX1qCTrgQ8CtwS+Djypqq5Nsi/wXuDWwI+Bv6iqS9tj\n3AF4N3AH4HrgEVV14Tzn8j6P0hC8z6M0yZxtWZK2BcPmPHbd8/hC4Py+8puAt1TVnYDNwNPa5f8I\n/GtVHQS8Hnhj3z7HA2+qqrsA9wQuG3nUkiRJkjRhOms8JtkHeARNr+GsBwIfbZ8fBzymfX4X4GSA\nquoBj26P8TvA9lU1u+7qqvrlyIOXJlCv6wCksdfrOgBp7PV6va5DkCZalz2PbwVeRjuWNMmtgJ9W\n1fXt+ouB27fPp4E/bbd7LLBbklsC+wNXJPlokjOTvClOBylJkiRJW10ns60m+SNgU1VNJ5maXdw+\n+s0mWLwM+OckRwCnApcA19LEfz9gA3AR8GHgCODY+c98BLC+fb5Hu9vs6XvtT8uWLS9cZon1li1b\n3nbLbant+Zmd8dKy5ZUszy5bLfFYtrzay9PT02zevBmAmZkZhtXJhDlJ/h74C5oG4M7AzYGPAw8B\n9q6q65PcGziyqh4+Z99dgQuqat8k9wL+d1U9sF33F8C9qur585zTCXOkIThhjjTJnDBHkrYFYzlh\nTlW9uqr2rar9gD8DTq6qvwBOAQ5tNzsc+AQ0Q1r7hqO+imbmVYCvAbdsh7xCkzPZPwGPpK2k13UA\n0tjrdR2ANPZme1YkdaOTxuMiXgm8OMm3gT2B97TLp4BvJfkmcBvgDQBtfuRLgZOTnN1u+64VjViS\nJEmSJkCn93lcSQ5blYbjsFVpkjlsVZK2BWM5bFWSJEmSNF5sPEoaSK/rAKSx1+s6AGnsmfModcvG\noyRJkiRpSeY8ShqIOY/SJDPnUZK2BeY8SpIkSZJGzsajpIH0ug5AGnu9rgOQxp45j1K31nQdwMpa\ndg+tJMA6JE2mtWvXdR2CJGkVmKicx0m5VmkkErAOSZIkjS1zHiVJkiRJI2fjUdJAel0HII05c7Wk\n4VmPpG7ZeJQkSZIkLWmich67jkEaZ4XT5Wh51q5dx8aNM12HIUnSxBs253HCGo+Tca3SKBQh1iEt\nizeYlyRpNRjbCXOS7JPk5CTnJzk3yQva5bdM8rkk30ry2SS7z9nvHkmuTfLYvmVvSnJekm8kOXql\nr0WaBL2uA5DGnLla0vCsR1K3usx5vBZ4cVXdBfh94HlJ7gy8Evh8Vd0JOBl41ewOSbYD3gic1Lfs\n94H7VNUBwAHAPZPcf+UuQ5IkSZK2fZ01HqtqY1VNt8+vAi4A9gEeDRzXbnYc8Ji+3Z4PnAhc1n8o\nYKckOwE7A2uATaONXpo8U10HII25qamprkOQxp71SOrWqphtNcl6YANwOrC2qjZB08AEbt1uc3ua\nhuQ76Ju3o6pOpxlR90PgEuCzVfWtlYtekiRJkrZ9a7oOIMluNL2JL6yqqxaZFfWtwCuqqpJA24BM\nckfgzsDt2mWfT/LZqjrtpoc4AljfPt+Dpr061ZZ77U/Lli3PV/7NZOLu47E8TuUmT2m2x2A2Z2nS\nyrPLVks8li2PY/noo49mw4YNqyYey5ZXe3l6eprNmzcDMDMzw7A6nW01yRrgP4HPVNXb2mUXAFNV\ntSnJ3sApVfU7Sb43uxuwF/Bz4JnA/sCOVfWGdv/XAL+oqn+ccy5nW5WGcArhEOuQlsXZVuE3G9CS\nlsd6JA1nrG/VkeR44PKqenHfsjcBP6mqNyV5BXDLqnrlnP2OBT5ZVR9L8njg6cDDaYbhfgZ4a1V9\nas4+Nh6lIXirDi2fjUdJklaDYRuPnQ1bTXJf4InAuUnOomnZvRp4E/DhJE8FLgQOnWf3/m8hJwIP\nBM4FrqfpxfzUPPtIkiRJkpap057HlWTPozQch61q+ex5BIfbSVuD9UgazrA9j9ttzWAkSZIkSdsm\nex4lDcScRy2fPY+SJK0G9jxKkiRJkkbOxqOkgfS6DkAac7P335K0fNYjqVs2HiVJkiRJSzLnUdJA\nzHnU8pnzKEnSamDOoyRJkiRp5Cas8RgfPnws89GDzmPwMZ6PtWvXIXO1pK3BeiR1a03XAawkh01J\ny9eLQw8lSZIm2UTlPE7KtUojkYB1SJIkaWyZ8yhJkiRJGrmJGraaLLuRLU28U4BDxrQOrV27jo0b\nZ7oOQxOu1+sxNTXVdRjSWLMeSd2aqMajt+qQhhHGtQ5t2jSejV5JkqTVpLOcxyTvAf4Y2FRVB7bL\nbgl8CFgHzACPr6orkhwGvILmm+tVwHOq6ty+Y20HnAFcXFWPWuB83udRGsJ43+fRyX4kSZLGOefx\nWOChc5a9Evh8Vd0JOBl4Vbv8e8D9q2oD8HfAu+bs90Lg/BHGKkmSJEkTrbPGY1WdBvx0zuJHA8e1\nz48DHtNue3pVXdEuPx24/ewOSfYBHgG8e6QBSxOu13UA0pjz/nTS8KxHUrdW22yrt6mqTQBVtRG4\n9TzbPB34TF/5rcDLcEyqJEmSJI3Mams8LirJIcBTaPIfSfJHNDmT0zSzeTgrhjQiU10HII05Z4iU\nhmc9krq12mZb3ZRkbVVtSrI3cNnsiiQHAu8EHlZVs8Nd7ws8KskjgJ2Bmyc5vqqePP/hjwDWt8/3\nADZw41fiXvvTsmXL85Vnl6yWeLas/JvTu88Oe7Js2bJly5YtW96Wy9PT02zevBmAmZkZhtXZbKsA\nSdYDn6yq32vLbwJ+UlVvSvIK4JZV9cok+wJfAJ5UVacvcKwHAC9xtlVpNE4hHDK2dcjZVtW9Xq93\nwx90SctjPZKGM+xsq531PCY5AZgCbpXkQuBI4I3AR5I8FbgQOLTd/DXAnsAxSQJcU1X3XPmoJUmS\nJGkyddrzuJLseZSG430eJUmSxts43+dRkiRJkjQmbDxKGkiv6wCkMTc7kYGk5bMeSd2y8ShJkiRJ\nWpI5j5IGYs6jJEnSeDPnUZIkSZI0cjYeJQ2k13UA0pgzV0sanvVI6paNR0mSJEnSkiYs51HSchWw\n7AHyHVu7dh0bN850HYYkSVKnhs15XLM1g1ntJqWhLI1EnHRGkiRpkjlsVdJAel0HII05c7Wk4VmP\npG5tUeMxyXZJbjGqYCRJkiRJq9OSOY9JTgCeDVwHfA24BfC2qnrz6MPbesx5lG60rBzABBy2KkmS\nNLaGzXkcpPE4XVUbkjwROBh4JXBmVR243JN2oWk8+sVXaiwjf9HGoyRJ0lgbtvE4yLDVmyW5GfAY\n4D+q6hpshUkTp9d1ANKYM1dLGp71SOrWII3HfwFmgF2BU5OsA64cZVBJZpKcneSsJF9tlz0uyXlJ\nrktycN+2D05yRrv915IcMsrYJEmSJGkSLes+j0nWVNW1I4hn9vjfA+5WVT/tW3Yn4HqaxuxLq+rr\n7fKDgE1VtTHJ7wKfrap95jmmw1alGzhsVZIkadKM7D6PSV68xL5HLfekAwhzekWr6lsASTJn+dl9\nz7+RZMckN2uH10qSJEmStoLFhq3efInHKBXw2XYY6jMG3SnJ44CzbDhKW1+v6wCkMWeuljQ865HU\nrQV7HqvqdSsZyBz3aYeh3hr4ryQXVNVpi+3QDln938AfLrzVEcD69vkewAZgqi332p+WLU9CufkD\nPDU1dcNzYNHydP/RBtjesmXLv1metVrisWx5HMvT09OrKh7Llld7eXp6ms2bNwMwMzPDsAa5VcdO\nwNOA3wV2ml1eVU8d+uwDSHIk8LOqOqotnwK8ZDbnsV22D/AF4PCqOn2B45jzKN3AnEdJkqRJsxK3\n6ngfsDfwUOCLwD7Az5Z7wqUk2SXJbu3zXYGHAOfN3axv+92B/wReuVDDUZIkSZI0nEEaj/9fVb0G\n+HlVHQf8EXCvEca0FjgtyVnA6cAnq+pzSR6T5CLg3sB/JvlMu/1fAncEXtPe2uPrSfYaYXzSROp1\nHYA05maHE0laPuuR1K0Fcx77zE4+sznJAcBG4DajCqiqvk+TjDh3+ceBj8+z/A3AG0YVjyRJkiRp\nsJzHpwMfBQ4EjgV2A/62qt4x+vC2HnMepX7mPEqSJE2aYXMel2w8bitsPEr9bDxKkiRNmpFPmJNk\nxySHJXl1kr+dfSz3hJLGU6/rAKQxZ66WNDzrkdStQXIePwFcAZwJ/Gq04UiSJEmSVqNBch7Pq6oD\nViiekXHYqtTPYauSJEmTZiXu8/jlJL+33BNIkiRJksbfII3H+wFnJvlWknOSnJvknFEHNhrx4cMH\nYe3adWyp3hbvIamfuVrS8KxHUrcGyXl8+MijWCGTMrOsJEmSJG1tg+Q87jnP4p9V1TWjCWk0kpSN\nR2kI5jxKkiSNtZXIefw68CPg28B32uczSb6e5G7LPbEkSZIkaXwM0nj8L+ARVbVXVd2KZhjrfwLP\nBY4ZZXCSVo9e1wFIY85cLWl41iOpW4PkPN67qp4xW6iqzyX5x6p6VpIdRxjbVpcsu4dWY2zt2nVs\n3DjTdRiSJEnSWBsk5/FzwBeAD7aLngD8IfAw4GtVdfBII9xKvM/jJFvGPQ11U+Y8SpIkjbWVyHk8\nDNgH+DjwCWDfdtn2wOOXe+KFJNknyclJzm9vC/L8dvmRSS5ucy2/nuRhffscmOTLSc5LcnaSHbZ2\nXJIkSZI0yZbseVxpSfYG9q6q6SS7AWcCj6bp8fxZVR01Z/vtaSb1eWJVnZfklsDmuVOr2vM4yex5\n3Bp6CVO+jtKy9Xo9pqamug5DGmvWI2k4w/Y8LpjzmOToqvqrJJ9knlZXVT1quSddTFVtBDa2z69K\ncgFw+9mw5tnlIcDZVXVeu89PRxGXJEmSJE2yBXsek9ytqs5M8oD51lfVF0caWRPDeppJHg8AXgIc\nDlwJnAG8pKquSPJC4G7AbYC9gA9V1ZvnOZY9jxPLnsetwpxHSZKksTaynseqOrP9eUMjsR0Seoeq\nOme5JxxUO2T1ROCFbQ/kMcDrq6qS/B1wFPA0mmu4L3B34JfAF5KcUVWn3PSoRwDr2+d7ABuAqbbc\na39a3hbLs1N7zw51sbzMMqyueCxbtmzZsmXLli0vWJ6enmbz5s0AzMzMMKxBZlvtAY+iaaSdCVwG\nfKmqXjz02Rc+5xqae0l+pqreNs/6dcAnq+rAJE8AHlpVT23X/Q3wi6p6y5x97HmcWPY8bg3mPErD\n6fV6N/xBl7Q81iNpOCsx2+ruVXUl8Fjg+Kq6F/Dg5Z5wQO8Fzu9vOLYT6cx6LHBe+/yzwIFJdmob\nnQ8Azh9xfJIkSZI0UQbpeTyXZlKa44C/rqqvJTmnqg4cSUDJfYFTgXNpugoLeDXN7UE2ANcDM8Cz\nqmpTu89h7TbXA5+qqlfNc1x7HieWPY9bhTmPkiRJY23YnsdBGo+HAq8BTquq5ybZD3hzVf3pck/a\nBRuPk8zG41Zh41GSJGmsjXzYalV9pKoOrKrntuXvjVvDUdLwel0HII252YkMJC2f9Ujq1iA5j5Ik\nSZKkCbfksNVthcNWJ5nDVrcKh61KkiSNtZENW03ywvbnfZd7cEmSJEnStmGxYatPaX/+00oEIml1\n63UdgDTmzNWShmc9krq1ZpF1FyT5DnC7JOf0LQ9Qo7pVhyRJkiRp9Vk05zHJ3sBngUfNXVdVPxhh\nXFtdk/OoSbR27To2bpzpOozxZ86jJEnSWBv5fR7bk+wA7N8Wv1VV1yz3hF1JUk6aIg3BxqMkSdJY\nG/l9HpM8APgO8HbgGODbSe6/3BNKGk+9rgOQxpy5WtLwrEdStxbLeZx1FPCQqvoWQJL9gQ8Adxtl\nYJIkSZKk1WPJYatJzpk7Oc58y1Y7h61KQ3LYqiRJ0lgbdtjqID2PZyR5D/C+tvxE4MzlnrBLybJf\np22SE8lIkiRJGtSSOY/Ac4BvAC8AXgicDzx7lEGNTvnoe2zaNFYT5qpjva4DkMacuVrS8KxHUreW\n7Hmsql/R5D0eNfpwoO3l/GNg0+zQ2CT/ADwS+BXwP8BTqurKJGuAdwMHA9sD76uqN65EnJIkSZI0\nSQa6VcdKSnI/4Crg+L7G44OBk6vq+iRvBKqqXpXkz4FHVtVhSXam6RV9QFVdOM9xq+lx043Canv/\ntYqZ8yhJkjTWRn6rjpVWVacBP52z7PNVdX1bPB3YZ3YVsGuS7YFdaHomr1ypWCVJkiRpUqy6xuMA\nngp8pn1+InA18ENgBvjHqtrcUVzSNq3XdQDSmDNXSxqe9Ujq1pI5j+19HV8GrOvfvqoeOMK4Forl\nr4FrquqEdtE9gWuBvYFbAf8vyeeramalY5MkSZKkbdkgt+r4CPAO4F3AdaMNZ2FJDgceAfQ3Wg8D\nTmqHtP4oyZeAu9P0Qs7jCGB9+3wPYAMw1ZZ77c9JK7el9j95U1NTli0vWJ61WuKxbNmyZcuTVZ5d\ntlrisWx5tZenp6fZvLkZmDkzM8OwlpwwJ8mZVXW3oc+0BZKsBz5ZVb/Xlh8GvAW4f1X9uG+7lwN3\nqqqnJdkV+CrwhKo6b55jOmHOTThhjraAE+ZIkiSNtZFNmJNkzyR7Ap9M8twkt51d1i4fiSQnAF8G\n9k9yYZKnAP8E7Ab8V5KvJzmm3fztwM2TnAd8BXjPfA1HScPrdR2ANOZm/yMsafmsR1K3Fhu2eiZN\nV91sy/RlfesK2G8UAVXVYfMsPnaBbX8OPH4UcUiSJEmSbjTIsNWdquqXSy1b7Ry2Oh+HrWoLOGxV\nkiRprK3EfR6/POAySZIkSdI2arGcx72T3A3YOcldkxzcPqaAXVYsQkmrQq/rAKQxZ66WNDzrkdSt\nxXIeH0pzb4t9gKP6lv8MePUIY5IkSZIkrTKD5Dz+aVV9dIXiGRlzHudjzqO2gDmPkiRJY23YnMdB\nGo8vnmfxFcCZVTW93BOvNBuP87HxqC1g41GSJGmsrcSEOXcHng3cvn08C3gY8K4kL1/uiSWNl17X\nAUhjzlwtaXjWI6lbi+U8ztoHOLiqrgJIciTwKeD+NPeC/IfRhbe1LbuRvU1au3Zd1yFIkiRJGhOD\nDFv9JnBgVf26Le8InF1Vd05yVlXddQXiHFqScoimNASHrUqSJI21YYetDtLz+G/A6Uk+0ZYfCZyQ\nZFfg/OWeWJIkSZI0PpbMeayq/wU8E9hMM1HOs6vq9VX186p64qgDlLQ69LoOQBpz5mpJw7MeSd0a\npOcR4Czg0tntk+xbVReOLKoRSUaT87h27To2bpwZybElSZIkaTUYJOfx+cCRwCbgOppZZ6qqDhx9\neFvPaG/V4S0vNAHMeZQkSRprK3Gfx+8C96qqHy/3JKuBjUdpSDYeJUmSxtpK3OfxIppcx84l2T3J\nR5JckOQbSe7Vt+6lSa5PsmeXMUrbql7XAUhjzlwtaXjWI6lbg+Q8fg/oJfkU8KvZhVV11MiiWtjb\ngE9X1aFJ1gC7ACTZB3gw8IMOYpIkSZKkbd4gw1aPnG95Vb1uJBEtHMfNgemquuM86z4CvB74D+Bu\nVfWTebZx2Ko0DIetSpIkjbWR3+dxtpGYZNeq+vlyT7QV7AdcnuRY4CDgDOCvgAcBF1XVuaOaTVWS\nJEmSJt2Sjcckvw+8B9gN2DfJQcCzquq5ow5ujjXAwcDzquqMJG8FXgvcH/jD/pAXPsQRwPr2+R7A\nBmCqLffan8srz47Bn5qybHnbLE/T/LdmtcRj2fK4lWeXrZZ4LFsex/LRRx/Nhg0bVk08li2v9vL0\n9DSbN28GYGZmhmENMmz1K8DjgP+oqru2y86rqgOGPvsWSLIW+O+q2q8t34+m8XgAcDVNo3Ef4BLg\nnlV12Zz9HbYqDaGXMOXnXFq2Xq93wx90SctjPZKGsxKzrVJVF81ZdN1yT7hcVbUJuCjJ/u2iBwFn\nVtXeVbVfVf0WcDFw17kNR0nDm+o6AGnM+YVXGp71SOrWILOtXpTkPkAl2QF4AXDBaMNa0AuAf0ty\nM5pZYJ8yZ32x6LBVSZIkSdJyDNLz+GzgecDtaXr2NgArne8IQFWdXVX3qKoNVfXYqrpizvr95ptp\nVdLwel0HII252VwUSctnPZK6Nchsq5cDT+xfluSvgKNHFZQkSZIkaXVZcsKceXdKLqyqfUcQz8g4\nYY40JO/zKEmSNNZWZMKc+c673BNKkiRJksbPchuPdj9IE6bXdQDSmDNXSxqe9Ujq1oI5j0l+xvyN\nxAA7jywiSZIkSdKqs6ycx3FkzqM0JHMeJUmSxtqwOY+D3OdxGzKaVM21a9eN5LiSJEmStFosN+dx\nLFXVSB4bN850fWnSyPW6DkAac+ZqScOzHkndmqjGoyRJkiRpeSYq53FSrlUaCXMeJUmSxlpX93mU\nJEmSJE2QiWo8Jtlqj733Xt/15Ugrqtd1ANKYM1dLGp71SOrWhM22uvWG3G3aNJqZWyVJkiRpNRqb\nnMckOwKnAjvQNHpPrKrXJXk/cHfg18BXgWdV1XXz7L+V7/PovR01Ycx5lCRJGmvD5jyOTeMRIMku\nVXV1ku2BLwEvAPasqpPa9ScAX6yqf5lnXxuP0jBsPEqSJI21iZowp6qubp/uSNP7WLMNx9ZXgX1W\nPDBpAvS6DkAac+ZqScOzHkndGqvGY5LtkpwFbAT+q6q+1rduDfAk4KSF9pckSZIkLc9YTZhTVdcD\nd01yC+DjSe5SVee3q4+hGbL6pYWPcASwvn2+B7ABmGrLvfbnoOXmv19TU1M3PAcsW96my7NWSzyW\nLVu2bHmyyrPLVks8li2v9vL09DSbN28GYGZmhmGNVc5jvyR/C1xVVUclORI4qKoeu8j25jxKwzDn\nUZIkaaxNTM5jkr2S7N4+3xl4MPDNJE8HHgL8eZfxSdu6XtcBSGNu9j/CkpbPeiR1a5yGrd4WOC7J\ndjSN3g9V1aeTXAPMAKc3vYt8rKr+rsM4JUmSJGmbM7bDVreUw1alITlsVZIkaaxNzLBVSZIk/f/t\n3X+QrXddH/D3R2+B+vMqrRtLyr0gjQia3kFpsaCspB1oLaV2GERLYtJWCypQ6JT+nIEZR0vHaUUD\noi0YgUpiilRJBQsVThikOlRYE+VHK+0CVu+dac12au2kCXz7xz57s9ncu+fcffbsc57zvF4zOznf\n55zz7GdP8rmbz32+73MAhmN4BBYyG7oAGDlZLehPH8GwDI8AAADMJfN49DPKPDItMo8AAKMm8wgA\nAMDSGR6BhcyGLgBGTlYL+tNHMKwxfc7jMTjyFdqH2Ng4c2znAgAAWHWTyjxO5WeFpZB5BAAYNZlH\nAAAAls7wCCxkNnQBMHKyWtCfPoJhGR4BAACYa1KZx8vdt7FxJufPb59gNTBCMo8AAKPWN/M4seHx\ncj9rZSqvAxyZ4REAYNQm84Y5VfXGqrpQVXcdOP7iqvp4Vd1dVa8eqj5Yd7OhC4CRk9WC/vQRDGtM\nn/N4S5Kbk7x570BVbSZ5dpKvba3dX1V/bKDaAAAA1tqotq1W1Zkkd7TWru3WP5vkJ1tr713gubat\nQh+2rQIAjNpktq1exjVJvrmqfrWq3ldV3zB0QQAAAOto7MPjqSSnW2tPSfKKJLcPXA+srdnQBcDI\nyWpBf/oIhjWmzOOlfCbJ25OktfahqvpcVT2ytfY/L/3wG5Oc7W6fTnIuyWaSB/4w2ty0tra+1Hor\ne92yGvVYW49tvWdV6rG2HuN6a2trpeqxtl719dbWVnZ2dpIk29vb6Wtsmcez2c08fl23/p4kj2qt\nvbKqrknyntbamcs8V+YR+pB5BAAYtb6Zx9FceayqtybZTPLIqvp0klcm+akkt1TV3UnuTXLDcBUC\nAACsr1FdeezDlUfoZ1aVTX0CRzabzS5uJQKORh9BP1N/t1UAAABOgCuPu/e68gjzyDwCAIyaK48A\nAAAsneERWMhs6AJg5PbeQh04On0EwzI8AgAAMJfM4+69Mo8wj8wjAMCoyTwCAACwdBMbHuuSXxsb\nZwatCsZgNnQBMHKyWtCfPoJhnRq6gJNkayoAAMDRTCrzOJWfFZZC5hEAYNRkHgEAAFi6SQ2PVXXx\n66qrzg5dDozKbOgCYORktaA/fQTDmlTmcf9HdVy4cOSrtQAAAJMzqczjgz/n0Wc7whWReQQAGDWZ\nxyRV9bKq+s2ququqfqaqHjZ0TQAAAOtk9MNjVf2JJC9O8qTW2rXZ3Yr7/GGrgvUzG7oAGDlZLehP\nH8Gw1iXz+PlJvrCqPpfkC5L87sD1AAAArJW1yDxW1UuS/GCSP0zy7tba9Zd4jMwj9CHzCAAwan0z\nj6O/8lhVp5M8J8mZJP8ryduq6jtba2996KNvTHL24mo2m2Vzc/Pi7STW1taHrZPVqsfa2tra2tra\n2vqy662trezs7CRJtre309forzxW1XOTPLO19t3d+vokf7a19v0HHufKI/Qwq8qmnoEjm81mF3+h\nA0ejj6Af77aafDrJU6rqEVVVSa5L8rGBawIAAFgro7/ymCRV9crsvsPqfUk+kuRvtdbuO/AYVx6h\nD5lHAIBR63vlcS2Gx0UYHqEnwyMAwKjZtgqciNnQBcDI7b2RAXB0+giGZXgEAABgLttWgcXYtgoA\nMGq2rQIAALB0hkdgIbOhC4CRk9WC/vQRDMvwCAAAwFwTyzw+YGPjTM6f3x6oGhghmUcAgFHrm3k8\ndZzFrLqpDMoAAADHzbZVYCGzoQuAkZPVgv70EQzL8AgAAMBck8o8TuVnhaWQeQQAGDWf83gFqipX\nXXV26DIAAABGZ1LDY9Jy4cKnhi4CRmk2dAEwcrJa0J8+gmGtzfBYVZ9XVR+uqncMXQsAAMC6WZvM\nY7KiAboAABCkSURBVFW9LMnXJ/mS1tpfucT9LWlJykd2wFHIPAIAjJrMY5KqujrJX0ryhqFrAQAA\nWEdrMTwm+ZEkfy+7lxaBJZgNXQCMnKwW9KePYFinhi6gr6r61iQXWmtbVbWZ5JDLsDcmSV71qlfl\n9OnTOXfuXDY3N5M88IeRtbX1pddbSXZXq1GPtfXY1ntWpR5r6zGut7a2Vqoea+tVX29tbWVnZydJ\nsr29nb5Gn3msqh9K8oIk9yf5o0m+OMnbW2s3HHiczCP0IfMIADBqfTOPox8e96uqpyf5u94wB5bA\n8AgAMGreMAc4EbOhC4CR29tOBBydPoJhjT7zuF9r7c4kdw5dBwAAwLpZq22rh7FtFXqybRUAYNRs\nWwUAAGDpDI/AQmZDFwAjJ6sF/ekjGJbhEQAAgLlkHoHFyDwCAIyazCMAAABLN7HhsbKxcWboImCU\nZkMXACMnqwX96SMY1lp9zuM8tqsCAAAczaQyj1P5WWEpZB4BAEZN5hEAAIClMzwCC5kNXQCMnKwW\n9KePYFiTyjxWHfkK7UrY2DiT8+e3hy4DAACYoEllHnc/53HMfEYlA5J5BAAYtclnHqvq6qp6b1V9\ntKrurqqXDF0TAADAuhn98Jjk/iQvb609Ick3Jvm+qnr8wDXB2pkNXQCMnKwW9KePYFijHx5ba+db\na1vd7T9I8rEkjxq2KgAAgPWyVpnHqjqb3QskX9sNkvvvk3mEPmQeAQBGbfKZxz1V9UVJ3pbkpQcH\nRwAAAPpZi4/qqKpT2R0c39Ja+4XLP/LGJGe726eTnEuy2a1n3T9Xfd2tuj3/m5ub1tYnst5K8neS\nlanH2nps671jq1KPtfUY1695zWty7ty5lanH2nrV11tbW9nZ2UmSbG9vp6+12LZaVW9O8j9aay8/\n5DG2rUIPs6ps+u8Pjmw2m138hQ4cjT6CfvpuWx398FhVT03y/iR3Z3c6bEn+UWvtlw48zvAIfcg8\nAgCM2uSHx0UZHqEnwyMAwKh5wxzgRMyGLgBGbi+LAhydPoJhGR4BAACYy7bVUbFtlQHZtgoAMGq2\nrQIAALB0hkdgIbOhC4CRk9WC/vQRDMvwCAAAwFwyj6Mi88iAZB4BAEatb+bx1HEWs/qO/DqthI2N\nM0OXAAAATNSktq221kb9df789tAvIRM2G7oAGDlZLehPH8GwJjU8AgAAcDSTyjxO5WeFpZB5BAAY\nNZnHK1A17swjq2Nj44xtxAAATMrEtq02X76O5evChU9lamZDFwAjJ6sF/ekjGNbEhkcAAACOYi0y\nj1X1xiR/OcmF1tq1l3lM271qBMdhgp+5KfMIADBqfTOP63Ll8ZYkzxy6CAAAgHW1FsNja+0DSe4Z\nug5YZ7OhC4CRk9WC/vQRDGsthkcAAACWa1If1ZHcmORsd/t0knNJNrv1rPuntfUi692//dzc3Lx4\nO8nar/f/7KtQj7W1tbX1tNZ7x1alHmvrVV9vbW1lZ2cnSbK9vZ2+1uINc5Kkqs4kucMb5nAyvGEO\nAADj4g1zHlDdF7AEs6ELgJHb+xth4Oj0EQxrLYbHqnprkg8muaaqPl1VNw1dEwAAwDpZm22r89i2\nyvGybRUAgHGxbRUAAIClMzwCC5kNXQCMnKwW9KePYFiGRwAAAOaSeYQjkXkEAGBcZB4BAABYOsMj\nsJDZ0AXAyMlqQX/6CIZ1augCTtaRr9DCg2xsnBm6BAAAOFGTyjxO5WeFpZB5BAAYNZlHAAAAls7w\nCCxkNnQBMHKyWtCfPoJhGR4BAACYS+YRWIzMIwDAqMk8AgAAsHSGR2Ahs6ELgJGT1YL+9BEMy/AI\nAADAXDKPwGJkHgEARk3mEQAAgKUzPAILmQ1dAIycrBb0p49gWIZHYDHve9/QFQAAMCCZRwAAgAmQ\neQQAAGDpDI/AQuRMoB89BP3pIxiW4REAAIC5ZB4BAAAmQOYRAACApTM8AguRM4F+9BD0p49gWIZH\nAAAA5pJ5BAAAmACZRwAAAJbO8AgsRM4E+tFD0J8+gmEZHgEAAJhL5hEAAGACZB4BAABYOsMjsBA5\nE+hHD0F/+giGZXgEAABgLplHAACACZB5BAAAYOkMj8BC5EygHz0E/ekjGJbhEQAAgLlkHgEAACZA\n5hEAAIClMzwCC5EzgX70EPSnj2BYhkcAAADmknkEAACYAJlHAAAAls7wCCxEzgT60UPQnz6CYRke\nAQAAmEvmEQAAYAJkHgEAAFg6wyOwEDkT6EcPQX/6CIZleAQAAGAumUcAAIAJkHkEAABg6QyPwELk\nTKAfPQT96SMYluERAACAuWQeAQAAJkDmEQAAgKUzPAILkTOBfvQQ9KePYFiGRwAAAOaSeQQAAJgA\nmUcAAACWzvAILETOBPrRQ9CfPoJhGR4BAACYS+YRAABgAmQeAQAAWDrDI7AQORPoRw9Bf/oIhmV4\nBAAAYC6ZRwAAgAmQeQQAAGDpDI/AQuRMoB89BP3pIxiW4REAAIC5ZB4BAAAmQOYRAACApTM8AguR\nM4F+9BD0p49gWIZHAAAA5pJ5BAAAmACZRwAAAJbO8AgsRM4E+tFD0J8+gmEZHgEAAJhL5hEAAGAC\nZB4BAABYOsMjsBA5E+hHD0F/+giGZXgEAABgLplHAACACZB5BAAAYOkMj8BC5EygHz0E/ekjGJbh\nEQAAgLlkHgEAACZA5hEAAIClMzwCC5EzgX70EPSnj2BYhkcAAADmknkEAACYAJlHAAAAls7wCCxE\nzgT60UPQnz6CYRkeAQAAmEvmEQAAYAJkHgEAAFg6wyOwEDkT6EcPQX/6CIZleAQAAGAumUcAAIAJ\nkHkEAABg6QyPwELkTKAfPQT96SMYluERWMjW1tbQJcCo6SHoTx/BsAyPwEJ2dnaGLgFGTQ9Bf/oI\nhmV4nIBV3OJxUjUd9/c5jvMd9RxX+rwrefwq/jeySlbx9dFDy3+eHjo+q/j6jLWHjuOcemicVvE1\nGmsfrePvopP6d2F4nAB/2KzW+VbtD5tFH7u9vX1F33+d6KHVOp8eGh89tFrnHGsPJfpo1Yy1j9bx\nd9FJ/buY1Ed1DF0DAADAkPp8VMdkhkcAAACOzrZVAAAA5jI8AgAAMJfhEQAAgLkMjwAAAMxleAQA\nAGCuSQ+PVfWYqnpDVd0+dC0wRlX1BVX101X1k1X1nUPXA2Pj9xD0U1XPqap/WVW3VtVfGLoeGJuq\nenxVvb6qbq+qF859vI/qSKrq9tba84auA8amql6Q5J7W2i9W1W2ttecPXROMkd9D0E9VnU7yw621\n7x66Fhijqqokb2qt3XDY49biymNVvbGqLlTVXQeOP6uqPl5V/7mq/v5Q9cFYHKGXrk7yme72Z0+s\nUFhRfh9BPz166J8ked3JVAmr6yg9VFXPTvLvkrxz3vnXYnhMckuSZ+4/UFWfl+S13fEnJvmOqnp8\nd9/1VfUvquor9x5+ksXCCruiXsru4Hj13kNPqkhYYVfaQxcfdjLlwcq74h6qqlcneWdrbeskC4UV\ndcU91Fq7o7X2rUleMO/kazE8ttY+kOSeA4f/TJL/0lr7VGvtviS3JXlO9/i3tNZenuTeqnp9knP+\nJhiuvJeS/Nskz62q1yW54+QqhdV0pT1UVV/u9xA84Ag99OIk12X3d9H3nGixsIKO0ENPr6ofraqf\nSPKL885/6rgLXiGPygPb6ZLkd7L7wl3UWvv9JC86yaJghC7bS621P0zyN4YoCkbksB7yewjmO6yH\nbk5y8xBFwYgc1kN3Jrlz0ROtxZXHy7jUFiDvDgRXTi9BP3oI+tFD0M+x9dA6D4+/k+TR+9ZXJ/nd\ngWqBMdNL0I8egn70EPRzbD20TsNj5cFT9YeSPK6qzlTVw5I8P8k7BqkMxkUvQT96CPrRQ9DP0npo\nLYbHqnprkg8muaaqPl1VN7XWPpvkxUneneS3ktzWWvvYkHXCqtNL0I8egn70EPSz7B6q1mwZBwAA\n4HBrceURAACA5TI8AgAAMJfhEQAAgLkMjwAAAMxleAQAAGAuwyMAAABzGR4BAACYy/AIwKCq6iuq\n6meq6rer6kNV9StV9Zw5z/nKqrr9mL7/06rqN6vqw1X18AP3vaSqPlpVb7nCc35pVb3oOOo7LlX1\n9Kq6Y85jHlT3cb7OAIyf4RGAof18kllr7XGttScneX6Sqw97Qmvt91przzum7//Xk/xQa+1JrbV7\nD9z3oiR/vrV2/RWe88uSfO+xVHe82pz7H1T3Mb/OAIyc4RGAwVTVM5Lc21r7V3vHWmufaa29rrv/\nTFW9v6r+U/f1lH3H7+5uf1dV/VxVvauqPlFV/+wy3+u67urib1TVG6rqYVX1N5M8L8kPHLy6WFWv\nT/LYJO+qqpdW1ZO7q6K/XlUfqKo/1T3uCVX1a925t6rqq5L80ySP7Y49pJ6quqGr4yNV9abu2KOr\n6j9053hPVV3dHb+lqn60+96/XVV/rTt+W1U9a985b6mqb6uqh1fVT1XVXV2tm5f4/q+sqpfvW99d\nVY/u6v6qvboPvM6XPO+irz8A43dq6AIAmLQnJvnwIfdfyO6Vv/9XVY9LcmuSJ3f37b+K9qeTnEty\nX5JPVNWPtdb++96d3XbUW5J8S2vtk93A9sLW2o9V1dOS3NFae/v+b9xae1FVPTPJZmvtnqr6oiTf\n1Fr7XFVdl91B67lJXpjkNa21W6vqVJLPT/IPkjyxtfakgz9QVT0hyT9M8ue6857u7nptkp9urf3r\nqropyc1Jvq2776rW2lOr6muSvCPJ25Pclt2rtL9UVX8kyTO6Wr5vt/x2bVV9dZJ37w26h9h7LR9U\nd1Wd2XffYec99PUHYD248gjAyqiq13ZX3n6tO/SwJG+oqruS/JskX3OZp/5ya+0Pum2nH01y5sD9\nX53kv7bWPtmt35TkmxcpqftKktNJ3tZdifuRJE/ojv/HJP+4ql6R5Owltr4e9Iwkb2ut3ZMkrbWd\n7vg3Znc4TpK3JHnqvuf8fPfYjyX5iu7Yu5J8Szc4/sUk7+++99O656e19okk20muWeDnnOew8857\n/QFYA4ZHAIb0W0m+fm/RWvv+JNcl+ePdoZclOd9auzbJN2R3mLyU/QPbZ/PQnTX7h8Cj+oEk722t\nfV2SZyd5RFfzrd36/yZ556W2iV6ilktlDw8e27/e//NV933vTTJL8qwk357dK5EX7z/4+APuz4P/\nH+ARh1Y8/7zzXn8A1oDhEYDBtNbem+ThVfW39x3+wn23vzTJ73W3b8jultCj+HiSM1X12G59fZI7\nr/AcX5JkbyvmTXsHq+oxrbX/1lq7OckvJLk2yf9O8sWXOc8vJ3leVX159/wv645/MMl3dLdfkOQD\nl3n+/qHtZ7tanpbk33fH3p/dNwFKVV2T5E8m+cSBc2wn2dua+qQkj+mOH1b3IucFYI0ZHgEY2l9N\nsllVn6yqX81uNvEV3X0/nuTGqvpIdrdI/p8FzveQq3rdVbqbsrvt9Deye3XsJy73+Muc64eTvLqq\nfj0P/v357bX7UR8fyW6G882ttd9P8ivdm8s86A1kWmsfTfKDSe7snvPPu7temuSmqtrK7pD20svU\nt3/97iTflOQ9rbX7u2M/nuRUt9X31iTf1Vq778A5fi7JI7stuN+bbgg8rO4Fz3upegFYE9WaP+MB\nAAA4nCuPAAAAzGV4BAAAYC7DIwAAAHMZHgEAAJjL8AgAAMBchkcAAADmMjwCAAAw1/8HoZu+9rNZ\nl/oAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1087ba5c0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import timeit\n",
    "\n",
    "n = np.arange(17)  # lengths = 2**n to evaluate\n",
    "reps = 20  # number of repetitions for timeit\n",
    "\n",
    "gain = np.zeros(len(n))\n",
    "for N in n:\n",
    "    length = 2**N\n",
    "    # setup environment for timeit\n",
    "    tsetup = 'import numpy as np; from numpy.fft import rfft, irfft; \\\n",
    "            x=np.random.randn(%d); h=np.random.randn(%d)' % (length, length)\n",
    "    # direct convolution\n",
    "    tc = timeit.timeit('np.convolve(x, x, \"full\")', setup=tsetup, number=reps)\n",
    "    # fast convolution\n",
    "    tf = timeit.timeit('irfft(rfft(x, %d) * rfft(h, %d))' % (2*length, 2*length), setup=tsetup, number=reps)\n",
    "    # speedup by using the fast convolution\n",
    "    gain[N] = tc/tf\n",
    "\n",
    "# show the results\n",
    "plt.figure(figsize = (15, 10))\n",
    "plt.barh(n-.5, gain, log=True)\n",
    "plt.plot([1, 1], [-1, n[-1]+1], 'r-')\n",
    "plt.yticks(n, 2**n)\n",
    "plt.xlabel('Gain of fast convolution')\n",
    "plt.ylabel('Length of signals')\n",
    "plt.title('Comparison of execution times between direct and fast convolution')\n",
    "plt.grid()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**\n",
    "\n",
    "* For which lengths is the fast convolution faster than the linear convolution? \n",
    "* Why is it slower below a given signal length?\n",
    "* Is the trend of the gain as expected from above considerations?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbsphinx": "hidden"
   },
   "source": [
    "**Copyright**\n",
    "\n",
    "The notebooks are provided as [Open Educational Resource](https://de.wikipedia.org/wiki/Open_Educational_Resources). Feel free to use the notebooks for your own educational 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: *Lecture Notes on Signals and Systems* by Sascha Spors."
   ]
  }
 ],
 "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.6.4"
  },
  "nbsphinx": {
   "execute": "never"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}