{
"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 (or circular/cyclic) convolution](https://en.wikipedia.org/wiki/Circular_convolution) of 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}^{P-1} \\tilde{x}_P[k - \\kappa] \\; \\tilde{h}_P[\\kappa]\n",
"\\end{equation}\n",
"\n",
"where $\\circledast_P$ denotes the periodic convolution with period $P$. The periodic summations $\\tilde{x}_P[k]$ of $x[k]$ and $\\tilde{h}_P[k]$ of $h[k]$ with period $P$ are defined as\n",
"\n",
"\\begin{align}\n",
"\\tilde{x}_P[k] &= \\sum_{\\nu = -\\infty}^{\\infty} x_L[\\nu \\cdot P + k] \\\\\n",
"\\tilde{h}_P[k] &= \\sum_{\\nu = -\\infty}^{\\infty} h_N[\\nu \\cdot P + k]\n",
"\\end{align}\n",
"\n",
"The result of the circular convolution has a period of $P$.\n",
"\n",
"\n",
"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": {
"application/pdf": "JVBERi0xLjQKJazcIKu6CjEgMCBvYmoKPDwgL1BhZ2VzIDIgMCBSIC9UeXBlIC9DYXRhbG9nID4+CmVuZG9iago4IDAgb2JqCjw8IC9FeHRHU3RhdGUgNCAwIFIgL0ZvbnQgMyAwIFIgL1BhdHRlcm4gNSAwIFIKL1Byb2NTZXQgWyAvUERGIC9UZXh0IC9JbWFnZUIgL0ltYWdlQyAvSW1hZ2VJIF0gL1NoYWRpbmcgNiAwIFIKL1hPYmplY3QgNyAwIFIgPj4KZW5kb2JqCjEwIDAgb2JqCjw8IC9Bbm5vdHMgWyBdIC9Db250ZW50cyA5IDAgUgovR3JvdXAgPDwgL0NTIC9EZXZpY2VSR0IgL1MgL1RyYW5zcGFyZW5jeSAvVHlwZSAvR3JvdXAgPj4KL01lZGlhQm94IFsgMCAwIDcxMC4zMTU2MjUgNTY2LjUxODc1IF0gL1BhcmVudCAyIDAgUiAvUmVzb3VyY2VzIDggMCBSCi9UeXBlIC9QYWdlID4+CmVuZG9iago5IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMTEgMCBSID4+CnN0cmVhbQp4nO1byW4cNxS891f0UTmY4s7mIYcYjgUECRAlAnIwfDBkWZZjS7a8IX+f18s0i5wme7REHCMWIFuqeWLVsMlHst5QtG8a0Z63vH1D31/bZ+1z+v9lK9oj+j5vOP32rnGCMyWMlYZ+fYu/GmuZEZ0zBPPot9dN86o5/Ika+Uh/dNQ0yjBjvKIXtTBM6f6nd431lrmhqYC+BdRozYQf0dACohORHInOSTa9FdbBmyH6/pWMAkQF6yYFzWPql6/N45P28KloBW9PXjVKMuW87d+f5pwEticvmwP+Q3vypv35pBlIG8E949JYryOWCC7TCG7odcs5BWuNVDKh6iTTXnKRUCG8QuU8PUmppFVd55FKx1TSGOZNp5SKqCK4TCWNZM51Vk/hgcrGVEp6pqW2JqaK4LXnZJnU2lsjiRGpuphKc8k6z72TEVUEr1DRQDU0FyiWvpBKJONCO8uUcdInXAiXubT1zHvnhaUvF3ElA8NozzqprBARVwSXuYxWTFs9BPfhwJWMDCsVk533KuaK4DKXFZZ5xc3wZSOuZGgsJYs4hawweUpcWxNYzKPiA/0Jbx9xyiHKKiaM6wQ1qzrH+Pjj6Ttqsc+KTPOekf7+8Kmcmj/4u2+ooYaON2M55BYak3xooh/KjKdoZtJIRuOi/3d8Wwv5BihohvmUYMJKzdOoEHIQsZBjoHnKFW7ou4hgRksUjtKEGxaGhdwCaZ1bZtM+msECgeln7LgiLWWUQKBoWA9hEcOMligo/9gxPsokH5p+uDzqBw6NSXqvdtMh5bHyzzBWqF/EtKTwMWBDevBsCFDMc6Hs2Hl8cbwZRjmBb5bnuJHnYUR+aJfWP2sFraSDABoErDPt9Vn7V3tJqoWkNjsre2JKBtOXo0513HSUSKhL2uvzfGQbRf5xFEU2+cjr82kmDhMxiFaeGa7Gadge/sbbJ1chjHKA2iTiVtADlWJ8CN8jc5H8HiIe7U73fwo9bo7bG0442f7SCmZo37rjNKEJdfjk7MvF6dkfR4/b04+51WZpAlGi+7OGREeplNYjFUsENKxXVfThNh0EIkxnHKU3K14dkZpSPr1sEpEA46pcRyMcQlAjwJ52WJ7bik9bCs+kNMLFIgHGzUcdiXDCQokBNpIzvjk4VxLpJbNe0BONRQY42mJV0Yjnx2gvPsN7oJFyy3joiDUGuL5GPByDRoD3YED2K52VWqhEZICrT2w8+KNEgOsnSEN7G+65NiISiXD1lQZdDdQIcP0l23SW+KxziUiAK+980LABhQjf5/axU36UqUikIEVaCGf78+Mkvh9cO+5wF6XPEntWvuUJZ9tddIbRb6Zm13yoJPwmzncUHtoptM6H9zf63iJyvc9nG0MOXqXgzI48xvCpid7L+PXi8uzFdXt6dfnl6u3nTxdXlxtzY/LvlyoEfKoQgFxJna+33l1A0ddXtIGRW74+orfx9VEBojS1dvP1Ze8grvn6yBLBZZrE1weqvK8fUSG8QhX7+kCV9/WRKoLLVImvD1R5Xz96TAivPafI1weqvK+PVBG8QhX7+kBV8PUjLoTLXImvj1x5Xx+5IrjMlfj6yJX39aN5jXCZK/H1kSvr6+dSyApT8PWRZc3XF75j4o6+vlSOiS1fP6AFR1nSXl7t4OtLq/sUExNMWKl5y+kUu+7rS+q8bsvXD2iJYiiMrPv6Sjjm0j6awQKBoo2m38HXV7Qkmi1fP6AlCt0XgtZ9fdltOmTPfP14GxYm0Dfk7IfBNjioYtWQ/o8jEkd3byPv472m9vV+hN5iWN+nfx5l9YVhunD+eRCFwShHhYBWV4j7YZCIcH2NwSiPNAJcXyNs9lFjgBXX9Nhz9tCDiASjHEUCjIt8HYlwkkGJAaZMxETWrnwYkcEoj0QGONrKVNGI57RozzvDe6AxGOWRxgDX14iHUNAI8B4MSDDKI5EBrj6x8YCNEgO8BwkSjHIUifA9rjR39VRzEvEwextPddmVQ68v8lSXPYAk/CauYxQe2im0XvJUwUyQ/UfnNh8SpCc0thDOh9PBOFiwB78P5zbHpLJqPJsPJ7uDswlXHaLXA6qZV2oUP8IX0wmSVi8/+gcjfrVpREdnz4OXE24FHDezrZwOuGW0Pbfh7HnQTuGd0NqooDETntNyudHCjQb4ywRH591sI28z0j8vN/5p6kaaqdPHOG/XjxntuZ75OuB+C8/R5mS+vhnt+8WnXWGAZQQOPgfOBs+Mmw6AweYYA34cAoRklNkM9onYMCodDTsdfJGb1S4ox5ntnLMBsXIh+mriVuUC0dtULoAfbS3Gd6xbSNrOrpQtgALRMkdatJh58jUL5AF0hSepWMw8+YIF8CBa5knLFTNPvlqBjwZ3uyvPJq5VzDz5UgXwILrCkxQqZp5CnQKJAC0TpVWKQJQvUgARomWitEQRiPIVCpy9gJaJ0vpEIMqWJ5azxAoNFCcCxVptgk7Qd71x0DG5feFgAxYvBDC9Q1nCGZa2PkGFtp1gaoeaBG0DmN+qSQS0wDDUdNZLEsMuOtU/g4X26WXGdyhJCEpJdqskEdAShelrWOslCb/pjr2uSMxz5hsqSJBSBzcN5M5m/ffIUhniThFpneB7qFyqlKxPt3u9aACLzMLsWfA0HkIf3CcI+gIYlqka4vAuQVAHaNcxk/204oMohIsEoDCg0UJcRSFcIwCFARX9R+qy3t9DSMS7BUEioLjZqCIQbhaAwIAKTTMm60M/iES4VwASAxptp2ooxFsFuN+e0foK4U4BKAxodYV4oyAoBLT+QMT7BCAxoLUnM14bAIEBrZ8Q8dJAkAho9VUFrwyAwoBWX5nxvgAoDGjdrQ1+ED/IA/Qed4Z3vkCwKBD9kduUuhZtXPSGo0rXop2URO9uUUfBoZVC2ztfHZCU6bgdzQXh5NTG8t2B9sXH9v3Z9cXVy4vTpTsFx82//wT8LAplbmRzdHJlYW0KZW5kb2JqCjExIDAgb2JqCjIyMDQKZW5kb2JqCjE5IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMTc0ID4+CnN0cmVhbQp4nD2PS3IEMQhD9z4FRzAgPj5Pp7Ly3H87QCq9sVTCRs++lTZJ1OGbKeTQDy/2M/az9MS4u+A6zhgUrGQ45Cn0LEslN54Fvn3UEDVpBw+yMMIGmYDUd00QQsqdVvtR0h2jz+La1u4uFi+su4buvlAVmJAjC4/PIQ1UpqL/Lv4ySFVkEuo2uHFQuECV1qeQPmoYnHb9Jht/F3Qpn56gnOZs6E5NHn1eirt+vzKEPcIKZW5kc3RyZWFtCmVuZG9iagoyMCAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDg3ID4+CnN0cmVhbQp4nDWNwQ3AMAgD/5nCI8QQINmn6qvd/1tI1I99soyxWOhQS3EKwjsuNk7d+DaJQ09mAWUkjWWwUVQnh8QnZFqSsRazxb6dERCvDsV2osf+J0+7P7hOGcQKZW5kc3RyZWFtCmVuZG9iagoyMSAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDEzOSA+PgpzdHJlYW0KeJw9j7ENxTAIRHumuAWQABsbz5PoV/77t8FxkgLxdKA78GEQsNUs6WhS4LXjVLIaYBf8yaSB1QTaLaEVaF1KKA5aOusIRNsW9ekHfa6TeORSsaRqL7W+KWK5O/SO0W1awKNnTvau0Obgck9GQSZOylPWoZM0fTaZB9QiyWU82vvQ/P6Z9LsAu7wt2wplbmRzdHJlYW0KZW5kb2JqCjE3IDAgb2JqCjw8IC9CYXNlRm9udCAvRGVqYVZ1U2Fucy1PYmxpcXVlIC9DaGFyUHJvY3MgMTggMCBSCi9FbmNvZGluZyA8PCAvRGlmZmVyZW5jZXMgWyA4MCAvUCAxMDcgL2sgMTIxIC95IF0gL1R5cGUgL0VuY29kaW5nID4+Ci9GaXJzdENoYXIgMCAvRm9udEJCb3ggWyAtMTAxNiAtMzUxIDE2NjAgMTA2OCBdIC9Gb250RGVzY3JpcHRvciAxNiAwIFIKL0ZvbnRNYXRyaXggWyAwLjAwMSAwIDAgMC4wMDEgMCAwIF0gL0xhc3RDaGFyIDI1NSAvTmFtZSAvRGVqYVZ1U2Fucy1PYmxpcXVlCi9TdWJ0eXBlIC9UeXBlMyAvVHlwZSAvRm9udCAvV2lkdGhzIDE1IDAgUiA+PgplbmRvYmoKMTYgMCBvYmoKPDwgL0FzY2VudCA5MjkgL0NhcEhlaWdodCAwIC9EZXNjZW50IC0yMzYgL0ZsYWdzIDk2Ci9Gb250QkJveCBbIC0xMDE2IC0zNTEgMTY2MCAxMDY4IF0gL0ZvbnROYW1lIC9EZWphVnVTYW5zLU9ibGlxdWUKL0l0YWxpY0FuZ2xlIDAgL01heFdpZHRoIDEzNTAgL1N0ZW1WIDAgL1R5cGUgL0ZvbnREZXNjcmlwdG9yIC9YSGVpZ2h0IDAgPj4KZW5kb2JqCjE1IDAgb2JqClsgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAKNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCAzMTggNDAxIDQ2MCA4MzggNjM2Cjk1MCA3ODAgMjc1IDM5MCAzOTAgNTAwIDgzOCAzMTggMzYxIDMxOCAzMzcgNjM2IDYzNiA2MzYgNjM2IDYzNiA2MzYgNjM2IDYzNgo2MzYgNjM2IDMzNyAzMzcgODM4IDgzOCA4MzggNTMxIDEwMDAgNjg0IDY4NiA2OTggNzcwIDYzMiA1NzUgNzc1IDc1MiAyOTUKMjk1IDY1NiA1NTcgODYzIDc0OCA3ODcgNjAzIDc4NyA2OTUgNjM1IDYxMSA3MzIgNjg0IDk4OSA2ODUgNjExIDY4NSAzOTAgMzM3CjM5MCA4MzggNTAwIDUwMCA2MTMgNjM1IDU1MCA2MzUgNjE1IDM1MiA2MzUgNjM0IDI3OCAyNzggNTc5IDI3OCA5NzQgNjM0IDYxMgo2MzUgNjM1IDQxMSA1MjEgMzkyIDYzNCA1OTIgODE4IDU5MiA1OTIgNTI1IDYzNiAzMzcgNjM2IDgzOCA2MDAgNjM2IDYwMCAzMTgKMzUyIDUxOCAxMDAwIDUwMCA1MDAgNTAwIDEzNTAgNjM1IDQwMCAxMDcwIDYwMCA2ODUgNjAwIDYwMCAzMTggMzE4IDUxOCA1MTgKNTkwIDUwMCAxMDAwIDUwMCAxMDAwIDUyMSA0MDAgMTAyOCA2MDAgNTI1IDYxMSAzMTggNDAxIDYzNiA2MzYgNjM2IDYzNiAzMzcKNTAwIDUwMCAxMDAwIDQ3MSA2MTcgODM4IDM2MSAxMDAwIDUwMCA1MDAgODM4IDQwMSA0MDEgNTAwIDYzNiA2MzYgMzE4IDUwMAo0MDEgNDcxIDYxNyA5NjkgOTY5IDk2OSA1MzEgNjg0IDY4NCA2ODQgNjg0IDY4NCA2ODQgOTc0IDY5OCA2MzIgNjMyIDYzMiA2MzIKMjk1IDI5NSAyOTUgMjk1IDc3NSA3NDggNzg3IDc4NyA3ODcgNzg3IDc4NyA4MzggNzg3IDczMiA3MzIgNzMyIDczMiA2MTEgNjA4CjYzMCA2MTMgNjEzIDYxMyA2MTMgNjEzIDYxMyA5OTUgNTUwIDYxNSA2MTUgNjE1IDYxNSAyNzggMjc4IDI3OCAyNzggNjEyIDYzNAo2MTIgNjEyIDYxMiA2MTIgNjEyIDgzOCA2MTIgNjM0IDYzNCA2MzQgNjM0IDU5MiA2MzUgNTkyIF0KZW5kb2JqCjE4IDAgb2JqCjw8IC9QIDE5IDAgUiAvayAyMCAwIFIgL3kgMjEgMCBSID4+CmVuZG9iagoyNiAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDU5ID4+CnN0cmVhbQp4nDM1NVcwULC0ABKmpkYK5kaWCimGXEA+iJXLZWhpDmblgFkWxkAGSBmcYQCkwZpzYHpyuNIAqeEQWgplbmRzdHJlYW0KZW5kb2JqCjI3IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMTY1ID4+CnN0cmVhbQp4nEWPOxIDIQxDe06hI4B/wHk2k4q9fxvLO0kaLIwlP6IrOvbKw2NjysZrtLEnwhbuUjoNp6mMr4qnZ12gy2EyU29czVxgqrDIbk6x+hh8ofLs5oSvVZ4YwpdMCQ0wlTu5h/X6UZyWfCS7C4LqlI3KwjBH0vdATE2bp4WB/I8veWpBUJnmjWuWlUdrFVM0Z5gqWwuC9YGgOqX6A9P/TKe9P9z0PYAKZW5kc3RyZWFtCmVuZG9iagoyOCAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDMwNCA+PgpzdHJlYW0KeJw9kjuSwzAMQ3udghfIjPiT5PNkJ5X3/u0+MslWgEmJACgvdZmypjwgaSYJ/9Hh4WI75XfYns3MwLVELxPLKc+hK8TcRfmymY26sjrFqsMwnVv0qJyLhk2TmucqSxm3C57DtYnnln3EDzc0qAd1jUvCDd3VaFkKzXB1/zu9R9l3NTwXm1Tq1BePF1EV5vkhT6KH6UrifDwoIVx7MEYWEuRT0UCOs1yt8l5C9g63GrLCQWpJ57MnPNh1ek8ubhfNEA9kuVT4TlHs7dAzvuxKCT0StuFY7n07mrHpGps47H7vRtbKjK5oIX7IVyfrJWDcUyZFEmROtlhui9We7qEopnOGcxkg6tmKhlLmYlerfww7bywv2SzIlMwLMkanTZ44eMh+jZr0eZXneP0BbPNzOwplbmRzdHJlYW0KZW5kb2JqCjI5IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggNzEgPj4Kc3RyZWFtCnicM7Y0UDBQsDBT0DU0NlQwsjRWMDczUEgx5AIKgVi5XDCxHDDLzBLEMjQ3Q2LpmhlCZZFYIONyuGAG58DMy+FKAwDxtBYjCmVuZHN0cmVhbQplbmRvYmoKMzAgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCA2NyA+PgpzdHJlYW0KeJwztjRQMFCwNFfQNTQ2VDA2MFEwNzNQSDHkgjFzwSywbA4XTB2EZQZiGBmaILHMgMaBJeEMkBk5cNNyuNIAzoMV0wplbmRzdHJlYW0KZW5kb2JqCjMxIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMjMwID4+CnN0cmVhbQp4nDVRSW7DMAy86xXzgQDiLr/HQU/t/68d0glgYGhLnM0RGxsReInBz0HkxlvWjJr4m8ld8bs8FR4Jt4InUQRehnvZCS5vGJf9OMx88F5aOZMaTzIgF9n08ETIYJdA6MDsGtRhm2kn+oaEz45INRtZTl9L0EurEChP2X6nC0q0rerP7bMutO1rTzjZ7aknlU8gnluyApeNV0wWYxn0ROUuxfRBqrOFnoTyonwOsvmoIRJdopyBJwYHo0A7sOe2n4lXhaB1dZ+2jaEaKR1P/zY0NUki5BMlnNnSuFv4/p57/fwDplRTnwplbmRzdHJlYW0KZW5kb2JqCjMyIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMjI3ID4+CnN0cmVhbQp4nDVPO7IDIQzrOYUukBmMbWDPs5lUL/dvn2SyDRL+SPL0REcmXubICKzZ8bYWGYgZ+BZT8a897cOE6j24hwjl4kKYYSScNeu4m6fjxb9d5TPWwbsNvmKWFwS2MJP1lcWZy3bBWBoncU6yG2PXRGxjXevpFNYRTCgDIZ3tMCXIHBUpfbKjjDk6TuSJ52KqxS6/72F9waYxosIcVwVP0GRQlj3vJqAdF/Tf1Y3fSTSLXgIykWBhnSTmzllO+NVrR8dRiyIxJ6QZ5DIR0pyuYgqhCcU6OwoqFQWX6nPK3T7/aF1bTQplbmRzdHJlYW0KZW5kb2JqCjMzIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMjQ1ID4+CnN0cmVhbQp4nEVQu41DMQzrPQUXCGD9LHued0iV2789SkZwhSFaP5JaEpiIwEsMsZRv4kdGQT0LvxeF4jPEzxeFQc6EpECc9RkQmXiG2kZu6HZwzrzDM4w5AhfFWnCm05n2XNjknAcnEM5tlPGMQrpJVBVxVJ9xTPGqss+N14GltWyz05HsIY2ES0klJpd+Uyr/tClbKujaRROwSOSBk0004Sw/Q5JizKCUUfcwtY70cbKRR3XQydmcOS2Z2e6n7Ux8D1gmmVHlKZ3nMj4nqfNcTn3usx3R5KKlVfuc/d6RlvIitduh1elXJVGZjdWnkLg8/4yf8f4DjqBZPgplbmRzdHJlYW0KZW5kb2JqCjM0IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMzkyID4+CnN0cmVhbQp4nD1SS24FMQjbzym4QKXwTXKeqd7u3X9bm8xUqgovA7YxlJcMqSU/6pKIM0x+9XJd4lHyvWxqZ+Yh7i42pvhYcl+6hthy0ZpisU8cyS/ItFRYoVbdo0PxhSgTDwAt4IEF4b4c//EXqMHXsIVyw3tkAmBK1G5AxkPRGUhZQRFh+5EV6KRQr2zh7yggV9SshaF0YogNlgApvqsNiZio2aCHhJWSqh3S8Yyk8FvBXYlhUFtb2wR4ZtAQ2d6RjREz7dEZcVkRaz896aNRMrVRGQ9NZ3zx3TJS89EV6KTSyN3KQ2fPQidgJOZJmOdwI+Ge20ELMfRxr5ZPbPeYKVaR8AU7ygEDvf3eko3Pe+AsjFzb7Ewn8NFppxwTrb4eYv2DP2xLm1zHK4dFFKi8KAh+10ETcXxYxfdko0R3tAHWIxPVaCUQDBLCzu0w8njGedneFbTm9ERoo0Qe1I4RPSiyxeWcFbCn/KzNsRyeDyZ7b7SPlMzMqIQV1HZ6qLbPYx3Ud577+vwBLgChGQplbmRzdHJlYW0KZW5kb2JqCjM1IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggNzEgPj4Kc3RyZWFtCnicszC2UDBQMDQwUzA0N1IwNzZSMDE1UUgx5AIJgZi5XDDBHDDLGKgsByyLYEFkQSwjU1OoDhALosMQrg7BgsimAQDr5xgyCmVuZHN0cmVhbQplbmRvYmoKMzYgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCA5MCA+PgpzdHJlYW0KeJxNjUESwCAIA++8Ik9QRND/dHrS/1+r1A69wE4CiRZFgvQ1aksw7rgyFWtQKZiUl8BVMFwL2u6iyv4ySUydhtN7twODsvFxg9JJ+/ZxegCr/XoG3Q/SHCJYCmVuZHN0cmVhbQplbmRvYmoKMzcgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAxNjMgPj4Kc3RyZWFtCnicRZC5dQQxDENzVYESeIA66hk/R7P9pwtpvN5A+niEeIg9CcNyXcWF0Q0/3rbMNLyOMtyN9WXG+KixQE7QBxgiE1ejSfXtijNU6eHVYq6jolwvOiISzJLjq0AjfDqyx0Nb25l+Oq9/7CHvE/8qKuduYQEuqu5A+VIf8dSP2VHqmqGPKitrHmravwi7IpS2fVxOZZy6ewe0wmcrV/t9A6jnOoAKZW5kc3RyZWFtCmVuZG9iagozOCAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDY4ID4+CnN0cmVhbQp4nDMyt1AwULA0ARKGFiYK5mYGCimGXEC+qYm5Qi4XSAzEygGzDIC0JZyCiFtCNEGUglgQpWYmZhBJOAMilwYAybQV5QplbmRzdHJlYW0KZW5kb2JqCjM5IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggNDUgPj4Kc3RyZWFtCnicMzK3UDBQsDQBEoYWJgrmZgYKKYZclhBWLhdMLAfMAtGWcAoingYAn30MtQplbmRzdHJlYW0KZW5kb2JqCjQwIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMTYxID4+CnN0cmVhbQp4nEWQSxLDIAxD95xCR/BHBnyedLpK77+tIU2zgKexQAZ3JwSptQUT0QUvbUu6Cz5bCc7GeOg2bjUS5AR1gFak42iUUn25xWmVdPFoNnMrC60THWYOepSjGaAQOhXe7aLkcqbuzvlHcPVf9Uex7pzNxMBk5Q6EZvUp7nybHVFd3WR/0mNu1mt/FfaqsLSspeWE285dM6AE7qkc7f0FqXM6hAplbmRzdHJlYW0KZW5kb2JqCjQxIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMjE0ID4+CnN0cmVhbQp4nD1QuxFDMQjrPQUL5M587TfPy6XL/m0knKRCNkISlJpMyZSHOsqSrClPHT5LYoe8h+VuZDYlKkUvk7Al99AK8X2J5hT33dWWs0M0l2g5fgszKqobHdNLNppwKhO6oNzDM/oNbXQDVocesVsg0KRg17YgcscPGAzBmROLIgxKTQb/rXL3UtzvPRxvooiUdPCu+eX0y88tvE49jkS6vfmKa3GmOgpEcEZq8op0YcWyyEOk1QQ1PQNrtQCu3nr5N2hHdBmA7BOJ4zSlHEP/1rjH6wOHilL0CmVuZHN0cmVhbQplbmRvYmoKNDIgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCA4MCA+PgpzdHJlYW0KeJxFjLsNwDAIRHumYAR+JmafKJWzfxsgStxwT7p7uDoSMlPeYYaHBJ4MLIZT8QaZo2A1uEZSjZ3so7BuX3WB5npTq/X3BypPdnZxPc3LGfQKZW5kc3RyZWFtCmVuZG9iago0MyAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDIzNiA+PgpzdHJlYW0KeJxNUEtuRCEM23OKXOBJJCEBzkPVVef+27HDVO0qhhh/SA/pslUe61NidYns8qVNl8oyeRWo5U/b/1EMAm7/0MhBtLeMnWLmEtbFwiQ85TQjGyfXLB+PO08bZoXGxI3jnS4ZYJ8WATVblc2BOW06N0C6kBq3qrPeZFAMIupCzQeTLpyn0ZeIOZ6oYEp3JrWQG1w+1aEDcVq9Crlji5NvxBxZocBh0Exx1l8B1qjJslnIIEmGIc59o3uUCo2oynkrFcIPk6ER9YbVoAaVuYWiqeWS/B3aAjAFtox16QxKgaoAwd8qp32/ASSNXVMKZW5kc3RyZWFtCmVuZG9iago0NCAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDE1NyA+PgpzdHJlYW0KeJxFkLkRQzEIRHNVQQkSsAjqscfRd/+pF/lKtG8ALYevJVOqHyciptzXaPQweQ6fTSVWLNgmtpMachsWQUoxmHhOMaujt6GZh9TruKiquHVmldNpy8rFf/NoVzOTPcI16ifwTej4nzy0qehboK8LlH1AtTidSVAxfa9igaOcdn8inBjgPhlHmSkjcWJuCuz3GQBmvle4xuMF3QE3eQplbmRzdHJlYW0KZW5kb2JqCjQ1IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMzMyID4+CnN0cmVhbQp4nC1SOY4kMQzL/Qp+YADr8vGeHkzU+/90SVUFBapsyzzkcsNEJX4skNtRa+LXRmagwvCvq8yF70jbyDqIa8hFXMmWwmdELOQxxDzEgu/b+Bke+azMybMHxi/Z9xlW7KkJy0LGizO0wyqOwyrIsWDrIqp7eFOkw6kk2OOL/z7FcxeCFr4jaMAv+eerI3i+pEXaPWbbtFsPlmlHlRSWg+1pzsvkS+ssV8fj+SDZ3hU7QmpXgKIwd8Z5Lo4ybWVEa2Fng6TGxfbm2I+lBF3oxmWkOAL5mSrCA0qazGyiIP7I6SGnMhCmrulKJ7dRFXfqyVyzubydSTJb90WKzRTO68KZ9XeYMqvNO3mWE6VORfgZe7YEDZ3j6tlrmYVGtznBKyV8NnZ6cvK9mlkPyalISBXTugpOo8gUS9iW+JqKmtLUy/Dfl/cZf/8BM+J8AQplbmRzdHJlYW0KZW5kb2JqCjQ2IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMzE3ID4+CnN0cmVhbQp4nDVSS3JDMQjbv1Nwgc6Yv32edLJq7r+thCcrsC1AQi4vWdJLftQl26XD5Fcf9yWxQj6P7ZrMUsX3FrMUzy2vR88Rty0KBFETPfgyJxUi1M/U6Dp4YZc+A68QTikWeAeTAAav4V94lE6DwDsbMt4Rk5EaECTBmkuLTUiUPUn8K+X1pJU0dH4mK3P5e3KpFGqjyQgVIFi52AekKykeJBM9iUiycr03VojekFeSx2clJhkQ3SaxTbTA49yVtISZmEIF5liA1XSzuvocTFjjsITxKmEW1YNNnjWphGa0jmNkw3j3wkyJhYbDElCbfZUJqpeP09wJI6ZHTXbtwrJbNu8hRKP5MyyUwccoJAGHTmMkCtKwgBGBOb2wir3mCzkWwIhlnZosDG1oJbt6joXA0JyzpWHG157X8/4HRVt7owplbmRzdHJlYW0KZW5kb2JqCjQ3IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMTcgPj4Kc3RyZWFtCnicMza0UDCAwxRDLgAalALsCmVuZHN0cmVhbQplbmRvYmoKNDggMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAxMzEgPj4Kc3RyZWFtCnicRY/LDQQhDEPvVOES8hk+qYfVntj+r+swmkFC+EEiO/EwCKzz8jbQxfDRosM3/jbVq2OVLB+6elJWD+mQh7zyFVBpMFHEhVlMHUNhzpjKyJYytxvhtk2DrGyVVK2DdjwGD7anZasIfqltYeos8QzCVV64xw0/kEutd71Vvn9CUzCXCmVuZHN0cmVhbQplbmRvYmoKNDkgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAyNDggPj4Kc3RyZWFtCnicLVE5kgNBCMvnFXpCc9PvscuR9//pCsoBg4ZDIDotcVDGTxCWK97yyFW04e+ZGMF3waHfynUbFjkQFUjSGFRNqF28Hr0HdhxmAvOkNSyDGesDP2MKN3pxeEzG2e11GTUEe9drT2ZQMisXccnEBVN12MiZw0+mjAvtXM8NyLkR1mUYpJuVxoyEI00hUkih6iapM0GQBKOrUaONHMV+6csjnWFVI2oM+1xL29dzE84aNDsWqzw5pUdXnMvJxQsrB/28zcBFVBqrPBAScL/bQ/2c7OQ33tK5s8X0+F5zsrwwFVjx5rUbkE21+Dcv4vg94+v5/AOopVsWCmVuZHN0cmVhbQplbmRvYmoKNTAgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAxNzEgPj4Kc3RyZWFtCnicTZBNDkIhEIP3nKIXMKHzA4/zaFzp/bd28PnigvRLIUOnwwMdR+JGR4bO6HiwyTEOvAsyJl6N85+M6ySOCeoVbcG6tDvuzSwxJywTI2BrlNybRxT44ZgLQYLs8sMXGESka5hvNZ91k35+u9Nd1KV199MjCpzIjlAMG3AF2NM9DtwSzu+aJr9UKRmbOJQPVBeRstkJhailYpdTVWiM4lY974te7fkBwfY7+wplbmRzdHJlYW0KZW5kb2JqCjUxIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggNzIgPj4Kc3RyZWFtCnicNYyxEcAwCAN7ptAINlhg75NLRfZvQ3xOAy8dD5eiwVoNuoIjcHWp/NEjXbkpRZdjzoLhcapfSDFGPagj497HT7lfcBYSfQplbmRzdHJlYW0KZW5kb2JqCjUyIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggODggPj4Kc3RyZWFtCnicNYy7EcAwCEN7T8EIBouP98mlSvZvg+3QgKR394KDOkHyuBspnC5u2Vd6G4+TniYAsfRMQ+3fYEXVi1oULV9uY9BiKr4/+iQglnXyXjj0kBLeH8UXHXsKZW5kc3RyZWFtCmVuZG9iago1MyAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDIxMCA+PgpzdHJlYW0KeJw1UMsNQzEIu2cKFqgUAoFknla9df9rbdA7YRH/QljIlAh5qcnOKelLPjpMD7Yuv7EiC611JezKmiCeK++hmbKx0djiYHAaJl6AFjdg6GmNGjV04YKmLpVCgcUl8Jl8dXvovk8ZeGoZcnYEEUPJYAlquhZNWLQ8n5BOAeL/fsPuLeShkvPKnhv5G5zt8DuzbuEnanYi0XIVMtSzNMcYCBNFHjx5RaZw4rPWd9U0EtRmC06WAa5OP4wOAGAiXlmA7K5EOUvSjqWfb7zH9w9AAFO0CmVuZHN0cmVhbQplbmRvYmoKMjQgMCBvYmoKPDwgL0Jhc2VGb250IC9EZWphVnVTYW5zIC9DaGFyUHJvY3MgMjUgMCBSCi9FbmNvZGluZyA8PAovRGlmZmVyZW5jZXMgWyAzMiAvc3BhY2UgNDggL3plcm8gL29uZSAvdHdvIDUyIC9mb3VyIDU0IC9zaXggNTYgL2VpZ2h0IDYxIC9lcXVhbCA3NiAvTAo4MCAvUCA5MSAvYnJhY2tldGxlZnQgOTMgL2JyYWNrZXRyaWdodCA5NyAvYSA5OSAvYyAvZCAvZSAxMDQgL2ggL2kgMTA4IC9sCjExMCAvbiAvbyAvcCAxMTQgL3IgL3MgL3QgL3UgL3YgL3cgXQovVHlwZSAvRW5jb2RpbmcgPj4KL0ZpcnN0Q2hhciAwIC9Gb250QkJveCBbIC0xMDIxIC00NjMgMTc5NCAxMjMzIF0gL0ZvbnREZXNjcmlwdG9yIDIzIDAgUgovRm9udE1hdHJpeCBbIDAuMDAxIDAgMCAwLjAwMSAwIDAgXSAvTGFzdENoYXIgMjU1IC9OYW1lIC9EZWphVnVTYW5zCi9TdWJ0eXBlIC9UeXBlMyAvVHlwZSAvRm9udCAvV2lkdGhzIDIyIDAgUiA+PgplbmRvYmoKMjMgMCBvYmoKPDwgL0FzY2VudCA5MjkgL0NhcEhlaWdodCAwIC9EZXNjZW50IC0yMzYgL0ZsYWdzIDMyCi9Gb250QkJveCBbIC0xMDIxIC00NjMgMTc5NCAxMjMzIF0gL0ZvbnROYW1lIC9EZWphVnVTYW5zIC9JdGFsaWNBbmdsZSAwCi9NYXhXaWR0aCAxMzQyIC9TdGVtViAwIC9UeXBlIC9Gb250RGVzY3JpcHRvciAvWEhlaWdodCAwID4+CmVuZG9iagoyMiAwIG9iagpbIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwCjYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgMzE4IDQwMSA0NjAgODM4IDYzNgo5NTAgNzgwIDI3NSAzOTAgMzkwIDUwMCA4MzggMzE4IDM2MSAzMTggMzM3IDYzNiA2MzYgNjM2IDYzNiA2MzYgNjM2IDYzNiA2MzYKNjM2IDYzNiAzMzcgMzM3IDgzOCA4MzggODM4IDUzMSAxMDAwIDY4NCA2ODYgNjk4IDc3MCA2MzIgNTc1IDc3NSA3NTIgMjk1CjI5NSA2NTYgNTU3IDg2MyA3NDggNzg3IDYwMyA3ODcgNjk1IDYzNSA2MTEgNzMyIDY4NCA5ODkgNjg1IDYxMSA2ODUgMzkwIDMzNwozOTAgODM4IDUwMCA1MDAgNjEzIDYzNSA1NTAgNjM1IDYxNSAzNTIgNjM1IDYzNCAyNzggMjc4IDU3OSAyNzggOTc0IDYzNCA2MTIKNjM1IDYzNSA0MTEgNTIxIDM5MiA2MzQgNTkyIDgxOCA1OTIgNTkyIDUyNSA2MzYgMzM3IDYzNiA4MzggNjAwIDYzNiA2MDAgMzE4CjM1MiA1MTggMTAwMCA1MDAgNTAwIDUwMCAxMzQyIDYzNSA0MDAgMTA3MCA2MDAgNjg1IDYwMCA2MDAgMzE4IDMxOCA1MTggNTE4CjU5MCA1MDAgMTAwMCA1MDAgMTAwMCA1MjEgNDAwIDEwMjMgNjAwIDUyNSA2MTEgMzE4IDQwMSA2MzYgNjM2IDYzNiA2MzYgMzM3CjUwMCA1MDAgMTAwMCA0NzEgNjEyIDgzOCAzNjEgMTAwMCA1MDAgNTAwIDgzOCA0MDEgNDAxIDUwMCA2MzYgNjM2IDMxOCA1MDAKNDAxIDQ3MSA2MTIgOTY5IDk2OSA5NjkgNTMxIDY4NCA2ODQgNjg0IDY4NCA2ODQgNjg0IDk3NCA2OTggNjMyIDYzMiA2MzIgNjMyCjI5NSAyOTUgMjk1IDI5NSA3NzUgNzQ4IDc4NyA3ODcgNzg3IDc4NyA3ODcgODM4IDc4NyA3MzIgNzMyIDczMiA3MzIgNjExIDYwNQo2MzAgNjEzIDYxMyA2MTMgNjEzIDYxMyA2MTMgOTgyIDU1MCA2MTUgNjE1IDYxNSA2MTUgMjc4IDI3OCAyNzggMjc4IDYxMiA2MzQKNjEyIDYxMiA2MTIgNjEyIDYxMiA4MzggNjEyIDYzNCA2MzQgNjM0IDYzNCA1OTIgNjM1IDU5MiBdCmVuZG9iagoyNSAwIG9iago8PCAvTCAyNiAwIFIgL1AgMjcgMCBSIC9hIDI4IDAgUiAvYnJhY2tldGxlZnQgMjkgMCBSIC9icmFja2V0cmlnaHQgMzAgMCBSCi9jIDMxIDAgUiAvZCAzMiAwIFIgL2UgMzMgMCBSIC9laWdodCAzNCAwIFIgL2VxdWFsIDM1IDAgUiAvZm91ciAzNiAwIFIKL2ggMzcgMCBSIC9pIDM4IDAgUiAvbCAzOSAwIFIgL24gNDAgMCBSIC9vIDQxIDAgUiAvb25lIDQyIDAgUiAvcCA0MyAwIFIKL3IgNDQgMCBSIC9zIDQ1IDAgUiAvc2l4IDQ2IDAgUiAvc3BhY2UgNDcgMCBSIC90IDQ4IDAgUiAvdHdvIDQ5IDAgUgovdSA1MCAwIFIgL3YgNTEgMCBSIC93IDUyIDAgUiAvemVybyA1MyAwIFIgPj4KZW5kb2JqCjMgMCBvYmoKPDwgL0YxIDI0IDAgUiAvRjIgMTcgMCBSID4+CmVuZG9iago0IDAgb2JqCjw8IC9BMSA8PCAvQ0EgMCAvVHlwZSAvRXh0R1N0YXRlIC9jYSAxID4+Ci9BMiA8PCAvQ0EgMSAvVHlwZSAvRXh0R1N0YXRlIC9jYSAxID4+ID4+CmVuZG9iago1IDAgb2JqCjw8ID4+CmVuZG9iago2IDAgb2JqCjw8ID4+CmVuZG9iago3IDAgb2JqCjw8IC9NMCAxMiAwIFIgL00xIDEzIDAgUiAvTTIgMTQgMCBSID4+CmVuZG9iagoxMiAwIG9iago8PCAvQkJveCBbIC0zLjUgLTMuNSAzLjUgMy41IF0gL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAxMzEKL1N1YnR5cGUgL0Zvcm0gL1R5cGUgL1hPYmplY3QgPj4Kc3RyZWFtCnicbZBBDoQgDEX3PUUv8ElLRWXr0mu4mUzi/bcDcUBM3TTQvjx+Uf6S8E6lwPgkCUtOs+R605DSukyMGObVsijHoFEt1s51OKjP0HBjdIuxFKbU1uh4o5vpNt6TP/qwWSFGPxwOr4R7FkMmXCkxBoffCy/bw/8Rnl7UwB+ijX5jWkP9CmVuZHN0cmVhbQplbmRvYmoKMTMgMCBvYmoKPDwgL0JCb3ggWyAtMy41IC0zLjUgMy41IDMuNSBdIC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMTMxCi9TdWJ0eXBlIC9Gb3JtIC9UeXBlIC9YT2JqZWN0ID4+CnN0cmVhbQp4nG2QQQ6EIAxF9z1FL/BJS0Vl69JruJlM4v23A3FATN000L48flH+kvBOpcD4JAlLTrPketOQ0rpMjBjm1bIox6BRLdbOdTioz9BwY3SLsRSm1NboeKOb6Tbekz/6sFkhRj8cDq+EexZDJlwpMQaH3wsv28P/EZ5e1MAfoo1+Y1pD/QplbmRzdHJlYW0KZW5kb2JqCjE0IDAgb2JqCjw8IC9CQm94IFsgLTMuNSAtMy41IDMuNSAzLjUgXSAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDEzMQovU3VidHlwZSAvRm9ybSAvVHlwZSAvWE9iamVjdCA+PgpzdHJlYW0KeJxtkEEOhCAMRfc9RS/wSUtFZevSa7iZTOL9twNxQEzdNNC+PH5R/pLwTqXA+CQJS06z5HrTkNK6TIwY5tWyKMegUS3WznU4qM/QcGN0i7EUptTW6Hijm+k23pM/+rBZIUY/HA6vhHsWQyZcKTEGh98LL9vD/xGeXtTAH6KNfmNaQ/0KZW5kc3RyZWFtCmVuZG9iagoyIDAgb2JqCjw8IC9Db3VudCAxIC9LaWRzIFsgMTAgMCBSIF0gL1R5cGUgL1BhZ2VzID4+CmVuZG9iago1NCAwIG9iago8PCAvQ3JlYXRpb25EYXRlIChEOjIwMTkwNjI3MTUyODA2KzAyJzAwJykKL0NyZWF0b3IgKG1hdHBsb3RsaWIgMy4wLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZykKL1Byb2R1Y2VyIChtYXRwbG90bGliIHBkZiBiYWNrZW5kIDMuMC4zKSA+PgplbmRvYmoKeHJlZgowIDU1CjAwMDAwMDAwMDAgNjU1MzUgZiAKMDAwMDAwMDAxNiAwMDAwMCBuIAowMDAwMDE0NzIwIDAwMDAwIG4gCjAwMDAwMTM2OTYgMDAwMDAgbiAKMDAwMDAxMzczOSAwMDAwMCBuIAowMDAwMDEzODM4IDAwMDAwIG4gCjAwMDAwMTM4NTkgMDAwMDAgbiAKMDAwMDAxMzg4MCAwMDAwMCBuIAowMDAwMDAwMDY1IDAwMDAwIG4gCjAwMDAwMDAzOTggMDAwMDAgbiAKMDAwMDAwMDIwOCAwMDAwMCBuIAowMDAwMDAyNjc3IDAwMDAwIG4gCjAwMDAwMTM5MzQgMDAwMDAgbiAKMDAwMDAxNDE5NiAwMDAwMCBuIAowMDAwMDE0NDU4IDAwMDAwIG4gCjAwMDAwMDM4NTMgMDAwMDAgbiAKMDAwMDAwMzY0NSAwMDAwMCBuIAowMDAwMDAzMzE2IDAwMDAwIG4gCjAwMDAwMDQ5MDYgMDAwMDAgbiAKMDAwMDAwMjY5OCAwMDAwMCBuIAowMDAwMDAyOTQ1IDAwMDAwIG4gCjAwMDAwMDMxMDQgMDAwMDAgbiAKMDAwMDAxMjI5NiAwMDAwMCBuIAowMDAwMDEyMDk2IDAwMDAwIG4gCjAwMDAwMTE2MjIgMDAwMDAgbiAKMDAwMDAxMzM0OSAwMDAwMCBuIAowMDAwMDA0OTU4IDAwMDAwIG4gCjAwMDAwMDUwODkgMDAwMDAgbiAKMDAwMDAwNTMyNyAwMDAwMCBuIAowMDAwMDA1NzA0IDAwMDAwIG4gCjAwMDAwMDU4NDcgMDAwMDAgbiAKMDAwMDAwNTk4NiAwMDAwMCBuIAowMDAwMDA2Mjg5IDAwMDAwIG4gCjAwMDAwMDY1ODkgMDAwMDAgbiAKMDAwMDAwNjkwNyAwMDAwMCBuIAowMDAwMDA3MzcyIDAwMDAwIG4gCjAwMDAwMDc1MTUgMDAwMDAgbiAKMDAwMDAwNzY3NyAwMDAwMCBuIAowMDAwMDA3OTEzIDAwMDAwIG4gCjAwMDAwMDgwNTMgMDAwMDAgbiAKMDAwMDAwODE3MCAwMDAwMCBuIAowMDAwMDA4NDA0IDAwMDAwIG4gCjAwMDAwMDg2OTEgMDAwMDAgbiAKMDAwMDAwODg0MyAwMDAwMCBuIAowMDAwMDA5MTUyIDAwMDAwIG4gCjAwMDAwMDkzODIgMDAwMDAgbiAKMDAwMDAwOTc4NyAwMDAwMCBuIAowMDAwMDEwMTc3IDAwMDAwIG4gCjAwMDAwMTAyNjYgMDAwMDAgbiAKMDAwMDAxMDQ3MCAwMDAwMCBuIAowMDAwMDEwNzkxIDAwMDAwIG4gCjAwMDAwMTEwMzUgMDAwMDAgbiAKMDAwMDAxMTE3OSAwMDAwMCBuIAowMDAwMDExMzM5IDAwMDAwIG4gCjAwMDAwMTQ3ODAgMDAwMDAgbiAKdHJhaWxlcgo8PCAvSW5mbyA1NCAwIFIgL1Jvb3QgMSAwIFIgL1NpemUgNTUgPj4Kc3RhcnR4cmVmCjE0OTM0CiUlRU9GCg==\n",
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"from tools import cconv\n",
"%matplotlib inline\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, int(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": {
"text/plain": [
"Text(0, 0.5, 'y[k]')"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"application/pdf": "JVBERi0xLjQKJazcIKu6CjEgMCBvYmoKPDwgL1BhZ2VzIDIgMCBSIC9UeXBlIC9DYXRhbG9nID4+CmVuZG9iago4IDAgb2JqCjw8IC9FeHRHU3RhdGUgNCAwIFIgL0ZvbnQgMyAwIFIgL1BhdHRlcm4gNSAwIFIKL1Byb2NTZXQgWyAvUERGIC9UZXh0IC9JbWFnZUIgL0ltYWdlQyAvSW1hZ2VJIF0gL1NoYWRpbmcgNiAwIFIKL1hPYmplY3QgNyAwIFIgPj4KZW5kb2JqCjEwIDAgb2JqCjw8IC9Bbm5vdHMgWyBdIC9Db250ZW50cyA5IDAgUgovR3JvdXAgPDwgL0NTIC9EZXZpY2VSR0IgL1MgL1RyYW5zcGFyZW5jeSAvVHlwZSAvR3JvdXAgPj4KL01lZGlhQm94IFsgMCAwIDYwMi45MzEyNSAyMTQuNTYzNzUgXSAvUGFyZW50IDIgMCBSIC9SZXNvdXJjZXMgOCAwIFIKL1R5cGUgL1BhZ2UgPj4KZW5kb2JqCjkgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAxMSAwIFIgPj4Kc3RyZWFtCnicxVhNTxxHEL3Pr+hjcqCpr/46BjlBipQDDlIOlk8Yk2CTyFiKlX+f17BM1ywLs1KkiS0E+7am3uua+prhcDtxuAkUbvHzLbwL7/H7Q+Bwjp+bifDpbsoksSlLwqfP7pOwxZS1JKC0+PT7NH2cTn+Ai6+45nya1KI8XKMlJutGd1Nqsg9+dqCQxrrzN1/uwR2JPJLcQDAOEas7Bqj7N3AaU7Na85J+Bi3Sjn46Qzy+TWeX4fQnDkzh8uOUcjRO3GCqOQhOn8Llh+k7+j5c3oYfL6cH0omlPD+jA18nYcH3iVPuh5wpZI+iGU5fMtuCw6ErJI1jrqVJZs3meGzJI1liIm2leB6Pvs4jiK2KSYWtFMeTlzyqFNlIjT2PR1/nUcmxZcpJjRo7nrrH00osJRda3BuPrvAgbsZFpSVL/v7wXg5YTjBUytUTefR1IkPgKGlGfVWunmgvE5IqHDVTWaS0Q1dyGpHLjShl8IgnmlNhGQGmqCq1Z3KLUh7+6Paf9iL9VKiWItMuzhTLEnsha+CicMX3xrFHqxyss5miUrRcqzXPMcA1koIIFG4FaUD5ULXNRMwpVlU0C8/k0DUqZok4OBVpyINDFTe4EkdujawsuAa6ymUlGgnjaMztYNXNXDWjYxtbXnANdJWrSkQBSaFaJS8rb3EJoTmfMHoxZkRp+hASwhR5TKO7hznTr/7n3af3Tw6+hOdDI6UaOGc0l3B/HX4Lf6Lhs6Br1iz4ut/73b+Cw6KyoUuTtHB/87JlWFi+PV9YTi9b3t9MX6Z+qH66eZpoHxJZY7NcEhtzuLoLp79QePPXbIwyrbz7L4FbhEfG+SouXbNG9KWYWsEclmN8o0lSTejFuu6bI3ERYpHW1n3XKAhKa43RPFZ9o8VUVItVlXVrZEfOyaqwynoETygSkVgWNLR1a8Sktmx92h5hLRpRv62Y8RHCT3pU0CiLiJod4b2HPHOqycp6yE/6/UwVIT8mVU6QK1wyslWPSMNujbRH49UiPlcupotwXDFK+DlwTNjAjiwhFNvpm+u//7i6fnt+Fq6+uqXMDZABznXVW9OvG+pq+jTBna4BVkUfxILYttY19kuna4BMfQ0w0bK5sMxPq4hXNlBGXWEkKprY1tLGvuylDZTN0CFKQhVsLE2kYkFPpS3up0MZOzj6ov4P0sb276UNlGuKWbEH1M2lte4Pl7aFtIFy//Np89xSmXuU8QvxQHfKEtnm0novxdhBJnlpA+17YGOtafOm5h7MvLSBMlRWwtK5edRM+cCAcigDhl+sUJtLG0+ZXtpA+yuGlFCmm/cOa+35lBogE9AmWIG2FuYemP2+MVD0NKxnmTfvaVhNDwwph2aMK2L9L3mGdfxRm0IZp/5winWxPxztFGNFPnZFOyB31tU56dnLub2aP/CC8OBbP/g88OLw7oUXh7A++tWjtx0+XvF8Mf0Lc9lf0QplbmRzdHJlYW0KZW5kb2JqCjExIDAgb2JqCjEwOTIKZW5kb2JqCjE3IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggNzEgPj4Kc3RyZWFtCnicM7Y0UDBQsDBT0DU0NlQwsjRWMDczUEgx5AIKgVi5XDCxHDDLzBLEMjQ3Q2LpmhlCZZFYIONyuGAG58DMy+FKAwDxtBYjCmVuZHN0cmVhbQplbmRvYmoKMTggMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCA2NyA+PgpzdHJlYW0KeJwztjRQMFCwNFfQNTQ2VDA2MFEwNzNQSDHkgjFzwSywbA4XTB2EZQZiGBmaILHMgMaBJeEMkBk5cNNyuNIAzoMV0wplbmRzdHJlYW0KZW5kb2JqCjE5IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMzkyID4+CnN0cmVhbQp4nD1SS24FMQjbzym4QKXwTXKeqd7u3X9bm8xUqgovA7YxlJcMqSU/6pKIM0x+9XJd4lHyvWxqZ+Yh7i42pvhYcl+6hthy0ZpisU8cyS/ItFRYoVbdo0PxhSgTDwAt4IEF4b4c//EXqMHXsIVyw3tkAmBK1G5AxkPRGUhZQRFh+5EV6KRQr2zh7yggV9SshaF0YogNlgApvqsNiZio2aCHhJWSqh3S8Yyk8FvBXYlhUFtb2wR4ZtAQ2d6RjREz7dEZcVkRaz896aNRMrVRGQ9NZ3zx3TJS89EV6KTSyN3KQ2fPQidgJOZJmOdwI+Ge20ELMfRxr5ZPbPeYKVaR8AU7ygEDvf3eko3Pe+AsjFzb7Ewn8NFppxwTrb4eYv2DP2xLm1zHK4dFFKi8KAh+10ETcXxYxfdko0R3tAHWIxPVaCUQDBLCzu0w8njGedneFbTm9ERoo0Qe1I4RPSiyxeWcFbCn/KzNsRyeDyZ7b7SPlMzMqIQV1HZ6qLbPYx3Ud577+vwBLgChGQplbmRzdHJlYW0KZW5kb2JqCjIwIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggOTAgPj4Kc3RyZWFtCnicTY1BEsAgCAPvvCJPUETQ/3R60v9fq9QOvcBOAokWRYL0NWpLMO64MhVrUCmYlJfAVTBcC9ruosr+MklMnYbTe7cDg7LxcYPSSfv2cXoAq/16Bt0P0hwiWAplbmRzdHJlYW0KZW5kb2JqCjIxIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggODEgPj4Kc3RyZWFtCnicPcy7FYAwCAXQPlO8EUJ8gOzjsdL9W8FEG7h81QMdIRnUDW4dh7SsS3eTfep6tYmkyIDSU2pcGk6MqGl9qX1q4Lsb5kvViT/Nz+cDh8cZawplbmRzdHJlYW0KZW5kb2JqCjIyIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggODAgPj4Kc3RyZWFtCnicRYy7DcAwCER7pmAEfiZmnyiVs38bIErccE+6e7g6EjJT3mGGhwSeDCyGU/EGmaNgNbhGUo2d7KOwbl91geZ6U6v19wcqT3Z2cT3Nyxn0CmVuZHN0cmVhbQplbmRvYmoKMjMgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAzMTcgPj4Kc3RyZWFtCnicNVJLckMxCNu/U3CBzpi/fZ50smruv62EJyuwLUBCLi9Z0kt+1CXbpcPkVx/3JbFCPo/tmsxSxfcWsxTPLa9HzxG3LQoEURM9+DInFSLUz9ToOnhhlz4DrxBOKRZ4B5MABq/hX3iUToPAOxsy3hGTkRoQJMGaS4tNSJQ9Sfwr5fWklTR0fiYrc/l7cqkUaqPJCBUgWLnYB6QrKR4kEz2JSLJyvTdWiN6QV5LHZyUmGRDdJrFNtMDj3JW0hJmYQgXmWIDVdLO6+hxMWOOwhPEqYRbVg02eNamEZrSOY2TDePfCTImFhsMSUJt9lQmql4/T3AkjpkdNdu3Csls27yFEo/kzLJTBxygkAYdOYyQK0rCAEYE5vbCKveYLORbAiGWdmiwMbWglu3qOhcDQnLOlYcbXntfz/gdFW3ujCmVuZHN0cmVhbQplbmRvYmoKMjQgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAyNDggPj4Kc3RyZWFtCnicLVE5kgNBCMvnFXpCc9PvscuR9//pCsoBg4ZDIDotcVDGTxCWK97yyFW04e+ZGMF3waHfynUbFjkQFUjSGFRNqF28Hr0HdhxmAvOkNSyDGesDP2MKN3pxeEzG2e11GTUEe9drT2ZQMisXccnEBVN12MiZw0+mjAvtXM8NyLkR1mUYpJuVxoyEI00hUkih6iapM0GQBKOrUaONHMV+6csjnWFVI2oM+1xL29dzE84aNDsWqzw5pUdXnMvJxQsrB/28zcBFVBqrPBAScL/bQ/2c7OQ33tK5s8X0+F5zsrwwFVjx5rUbkE21+Dcv4vg94+v5/AOopVsWCmVuZHN0cmVhbQplbmRvYmoKMjUgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAxMzggPj4Kc3RyZWFtCnicPY9BDgMxCAPveYU/ECl2Qljes1VP2/9fS5rdXtAIjDEWQkNvqGoOm4INx4ulS6jW8CmKiUoOyJlgDqWk0h1nkXpiOBjcHrQbzuKx6foRu5JWfdDmRrolaIJH7FNp3JZxE8QDNQXqKepco7wQuZ+pV9g0kt20spJrOKbfveep6//TVd5fX98ujAplbmRzdHJlYW0KZW5kb2JqCjI2IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMjEwID4+CnN0cmVhbQp4nDVQyw1DMQi7ZwoWqBQCgWSeVr11/2tt0DthEf9CWMiUCHmpyc4p6Us+OkwPti6/sSILrXUl7MqaIJ4r76GZsrHR2OJgcBomXoAWN2DoaY0aNXThgqYulUKBxSXwmXx1e+i+Txl4ahlydgQRQ8lgCWq6Fk1YtDyfkE4B4v9+w+4t5KGS88qeG/kbnO3wO7Nu4SdqdiLRchUy1LM0xxgIE0UePHlFpnDis9Z31TQS1GYLTpYBrk4/jA4AYCJeWYDsrkQ5S9KOpZ9vvMf3D0AAU7QKZW5kc3RyZWFtCmVuZG9iagoxNSAwIG9iago8PCAvQmFzZUZvbnQgL0RlamFWdVNhbnMgL0NoYXJQcm9jcyAxNiAwIFIKL0VuY29kaW5nIDw8Ci9EaWZmZXJlbmNlcyBbIDQ4IC96ZXJvIC9vbmUgL3R3byA1MiAvZm91ciA1NCAvc2l4IDU2IC9laWdodCA5MSAvYnJhY2tldGxlZnQgOTMKL2JyYWNrZXRyaWdodCAxMDcgL2sgMTIxIC95IF0KL1R5cGUgL0VuY29kaW5nID4+Ci9GaXJzdENoYXIgMCAvRm9udEJCb3ggWyAtMTAyMSAtNDYzIDE3OTQgMTIzMyBdIC9Gb250RGVzY3JpcHRvciAxNCAwIFIKL0ZvbnRNYXRyaXggWyAwLjAwMSAwIDAgMC4wMDEgMCAwIF0gL0xhc3RDaGFyIDI1NSAvTmFtZSAvRGVqYVZ1U2FucwovU3VidHlwZSAvVHlwZTMgL1R5cGUgL0ZvbnQgL1dpZHRocyAxMyAwIFIgPj4KZW5kb2JqCjE0IDAgb2JqCjw8IC9Bc2NlbnQgOTI5IC9DYXBIZWlnaHQgMCAvRGVzY2VudCAtMjM2IC9GbGFncyAzMgovRm9udEJCb3ggWyAtMTAyMSAtNDYzIDE3OTQgMTIzMyBdIC9Gb250TmFtZSAvRGVqYVZ1U2FucyAvSXRhbGljQW5nbGUgMAovTWF4V2lkdGggMTM0MiAvU3RlbVYgMCAvVHlwZSAvRm9udERlc2NyaXB0b3IgL1hIZWlnaHQgMCA+PgplbmRvYmoKMTMgMCBvYmoKWyA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMAo2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDMxOCA0MDEgNDYwIDgzOCA2MzYKOTUwIDc4MCAyNzUgMzkwIDM5MCA1MDAgODM4IDMxOCAzNjEgMzE4IDMzNyA2MzYgNjM2IDYzNiA2MzYgNjM2IDYzNiA2MzYgNjM2CjYzNiA2MzYgMzM3IDMzNyA4MzggODM4IDgzOCA1MzEgMTAwMCA2ODQgNjg2IDY5OCA3NzAgNjMyIDU3NSA3NzUgNzUyIDI5NQoyOTUgNjU2IDU1NyA4NjMgNzQ4IDc4NyA2MDMgNzg3IDY5NSA2MzUgNjExIDczMiA2ODQgOTg5IDY4NSA2MTEgNjg1IDM5MCAzMzcKMzkwIDgzOCA1MDAgNTAwIDYxMyA2MzUgNTUwIDYzNSA2MTUgMzUyIDYzNSA2MzQgMjc4IDI3OCA1NzkgMjc4IDk3NCA2MzQgNjEyCjYzNSA2MzUgNDExIDUyMSAzOTIgNjM0IDU5MiA4MTggNTkyIDU5MiA1MjUgNjM2IDMzNyA2MzYgODM4IDYwMCA2MzYgNjAwIDMxOAozNTIgNTE4IDEwMDAgNTAwIDUwMCA1MDAgMTM0MiA2MzUgNDAwIDEwNzAgNjAwIDY4NSA2MDAgNjAwIDMxOCAzMTggNTE4IDUxOAo1OTAgNTAwIDEwMDAgNTAwIDEwMDAgNTIxIDQwMCAxMDIzIDYwMCA1MjUgNjExIDMxOCA0MDEgNjM2IDYzNiA2MzYgNjM2IDMzNwo1MDAgNTAwIDEwMDAgNDcxIDYxMiA4MzggMzYxIDEwMDAgNTAwIDUwMCA4MzggNDAxIDQwMSA1MDAgNjM2IDYzNiAzMTggNTAwCjQwMSA0NzEgNjEyIDk2OSA5NjkgOTY5IDUzMSA2ODQgNjg0IDY4NCA2ODQgNjg0IDY4NCA5NzQgNjk4IDYzMiA2MzIgNjMyIDYzMgoyOTUgMjk1IDI5NSAyOTUgNzc1IDc0OCA3ODcgNzg3IDc4NyA3ODcgNzg3IDgzOCA3ODcgNzMyIDczMiA3MzIgNzMyIDYxMSA2MDUKNjMwIDYxMyA2MTMgNjEzIDYxMyA2MTMgNjEzIDk4MiA1NTAgNjE1IDYxNSA2MTUgNjE1IDI3OCAyNzggMjc4IDI3OCA2MTIgNjM0CjYxMiA2MTIgNjEyIDYxMiA2MTIgODM4IDYxMiA2MzQgNjM0IDYzNCA2MzQgNTkyIDYzNSA1OTIgXQplbmRvYmoKMTYgMCBvYmoKPDwgL2JyYWNrZXRsZWZ0IDE3IDAgUiAvYnJhY2tldHJpZ2h0IDE4IDAgUiAvZWlnaHQgMTkgMCBSIC9mb3VyIDIwIDAgUgovayAyMSAwIFIgL29uZSAyMiAwIFIgL3NpeCAyMyAwIFIgL3R3byAyNCAwIFIgL3kgMjUgMCBSIC96ZXJvIDI2IDAgUiA+PgplbmRvYmoKMyAwIG9iago8PCAvRjEgMTUgMCBSID4+CmVuZG9iago0IDAgb2JqCjw8IC9BMSA8PCAvQ0EgMCAvVHlwZSAvRXh0R1N0YXRlIC9jYSAxID4+Ci9BMiA8PCAvQ0EgMSAvVHlwZSAvRXh0R1N0YXRlIC9jYSAxID4+ID4+CmVuZG9iago1IDAgb2JqCjw8ID4+CmVuZG9iago2IDAgb2JqCjw8ID4+CmVuZG9iago3IDAgb2JqCjw8IC9NMCAxMiAwIFIgPj4KZW5kb2JqCjEyIDAgb2JqCjw8IC9CQm94IFsgLTMuNSAtMy41IDMuNSAzLjUgXSAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDEzMQovU3VidHlwZSAvRm9ybSAvVHlwZSAvWE9iamVjdCA+PgpzdHJlYW0KeJxtkEEOhCAMRfc9RS/wSUtFZevSa7iZTOL9twNxQEzdNNC+PH5R/pLwTqXA+CQJS06z5HrTkNK6TIwY5tWyKMegUS3WznU4qM/QcGN0i7EUptTW6Hijm+k23pM/+rBZIUY/HA6vhHsWQyZcKTEGh98LL9vD/xGeXtTAH6KNfmNaQ/0KZW5kc3RyZWFtCmVuZG9iagoyIDAgb2JqCjw8IC9Db3VudCAxIC9LaWRzIFsgMTAgMCBSIF0gL1R5cGUgL1BhZ2VzID4+CmVuZG9iagoyNyAwIG9iago8PCAvQ3JlYXRpb25EYXRlIChEOjIwMTkwNjI3MTUyODA2KzAyJzAwJykKL0NyZWF0b3IgKG1hdHBsb3RsaWIgMy4wLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZykKL1Byb2R1Y2VyIChtYXRwbG90bGliIHBkZiBiYWNrZW5kIDMuMC4zKSA+PgplbmRvYmoKeHJlZgowIDI4CjAwMDAwMDAwMDAgNjU1MzUgZiAKMDAwMDAwMDAxNiAwMDAwMCBuIAowMDAwMDA2MjY5IDAwMDAwIG4gCjAwMDAwMDU4MDIgMDAwMDAgbiAKMDAwMDAwNTgzNCAwMDAwMCBuIAowMDAwMDA1OTMzIDAwMDAwIG4gCjAwMDAwMDU5NTQgMDAwMDAgbiAKMDAwMDAwNTk3NSAwMDAwMCBuIAowMDAwMDAwMDY1IDAwMDAwIG4gCjAwMDAwMDAzOTcgMDAwMDAgbiAKMDAwMDAwMDIwOCAwMDAwMCBuIAowMDAwMDAxNTY0IDAwMDAwIG4gCjAwMDAwMDYwMDcgMDAwMDAgbiAKMDAwMDAwNDU5MCAwMDAwMCBuIAowMDAwMDA0MzkwIDAwMDAwIG4gCjAwMDAwMDQwMDQgMDAwMDAgbiAKMDAwMDAwNTY0MyAwMDAwMCBuIAowMDAwMDAxNTg1IDAwMDAwIG4gCjAwMDAwMDE3MjggMDAwMDAgbiAKMDAwMDAwMTg2NyAwMDAwMCBuIAowMDAwMDAyMzMyIDAwMDAwIG4gCjAwMDAwMDI0OTQgMDAwMDAgbiAKMDAwMDAwMjY0NyAwMDAwMCBuIAowMDAwMDAyNzk5IDAwMDAwIG4gCjAwMDAwMDMxODkgMDAwMDAgbiAKMDAwMDAwMzUxMCAwMDAwMCBuIAowMDAwMDAzNzIxIDAwMDAwIG4gCjAwMDAwMDYzMjkgMDAwMDAgbiAKdHJhaWxlcgo8PCAvSW5mbyAyNyAwIFIgL1Jvb3QgMSAwIFIgL1NpemUgMjggPj4Kc3RhcnR4cmVmCjY0ODMKJSVFT0YK\n",
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"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 cell may take some time."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"application/pdf": "JVBERi0xLjQKJazcIKu6CjEgMCBvYmoKPDwgL1BhZ2VzIDIgMCBSIC9UeXBlIC9DYXRhbG9nID4+CmVuZG9iago4IDAgb2JqCjw8IC9FeHRHU3RhdGUgNCAwIFIgL0ZvbnQgMyAwIFIgL1BhdHRlcm4gNSAwIFIKL1Byb2NTZXQgWyAvUERGIC9UZXh0IC9JbWFnZUIgL0ltYWdlQyAvSW1hZ2VJIF0gL1NoYWRpbmcgNiAwIFIKL1hPYmplY3QgNyAwIFIgPj4KZW5kb2JqCjEwIDAgb2JqCjw8IC9Bbm5vdHMgWyBdIC9Db250ZW50cyA5IDAgUgovR3JvdXAgPDwgL0NTIC9EZXZpY2VSR0IgL1MgL1RyYW5zcGFyZW5jeSAvVHlwZSAvR3JvdXAgPj4KL01lZGlhQm94IFsgMCAwIDQ0OS4zODE4NzUgMzI3LjMwODg3NSBdIC9QYXJlbnQgMiAwIFIgL1Jlc291cmNlcyA4IDAgUgovVHlwZSAvUGFnZSA+PgplbmRvYmoKOSAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDExIDAgUiA+PgpzdHJlYW0KeJzNWk1v3DYQvetX8JgewpDD72PTDwNFL20N9FD04Dob14Fst7Hb9Of3UbtaznDlRSK02Q3g2PvIedI8kk9Daq16N1h1o4x6h58P6hf1K36/UVZd4OdmMPh0N3hftMs2p4CPI//oKGlncv1zRGfx8fdheDu8+hI0jwi7GIZQdIxTVNY5TfHgtlGnLNGRo8brkt0WbgwcnS70p1qgdyFpS4pi1Ba/32/Uz+peGWA2xBypJqR93P1Lg9HJhJzJBSrq/c3zPVXXcxheFm9t1tH64GO9F+N2GVobcHUfc2DwyOFYkOwuGcnDW6Y0f1DnlWgi7eehzEH74HC7DB0Zmp0mWkyTt5xlmkii2F2aJWiKNjqOjgwtEfe9mCZvOcs0CxZ2mKetsTqYRMEzeOSwtbiQWcxUNJ1lqriaTmWXa8JAGutT4vDIYXI6+OVUedN5pkpR096NHEKtjcZzfBS4i81cOyredJ7JOtzM7EiWSIcUyBSOjwIPYF92JdF0nskGhyvOyQarTSEv8VHg0em87E2i6TyTxRXD3p1S0iF7UzzHR4GnWowsJ8ubzjPZVHSZ7YmM04YoJeL4KPACwmcMijedZ7LFaT8bFMGIMmEqFo6PHCdUf3bZoETTWSZLJrbql7BQS0ZRQBwfBW6TjssGJZrOM1ky2s0GRQnPG1BYz/FR4A5etWxQouk8k3VOp9mgHD4Apeg4Pgrce5RSy8nypvNM1uPCs0G5Ol2jwy1xfBQ4brQsG5RoOs9ko9FxNijsZTCcwSUOjxxOVrtn7Ik3nWeqyWuz35wbg0drNOQ4Pgo8e9jycrK86dOTffUl1aMDUt8pW48ndG4HFMg3ojQv0aTs1YV69fXm79vrzY8Xr9X144CSXQdKxlpx1MBhfn4w/DTd2O56Rt0cXq8eYNSWj6EO2s06Da8Hqz4Mf+J/o14a8FpEbTsaX6cK6RLU9d3w+rKeteiSYogU1OWb4dW36G3U5dvhhf1CXb4bonYwe+Pj9hwGXV6YXYMP2UAJi0hXH5K2UaSJYdvxm8vhh881BuQtNlIOlagQisNrx+AjqI+OATnadsT6NQEf5RiY6M3/MQb2s4+Bw27NhEIohrlQHF47Bh9BfXQM6knhtqMNyX+2dUBtDKAcbilbOHjKJoo0GMqKMmRRMnbMiXwR3Rkqu9djkHqA4Em6BYP7gKKx7TRiWtwJuAvAHh52a3MXwOAuAJO/ELg6A2NwH5C1Kzam3AU0uAvwTpPFGJXOIhvcBUznLK74JAMY3AUUqtURLi8DGCwD6q6Assm5cwwGdwEWVZqNZOW84HAXgII2Z4NpLQMY3AdMdRJU6QIa3AVghGJIWU4lhvbdk/appGS7/g3uAhJqhmRMlsPG4S4gR51iCa67IwZ3AVgnwSdDcq5yWAY4g/1NrVTk1ONwF1DP1H30UebA4S6ALEwjoVKRAQzuAyLWiSvRdgEN7gKwbUk+FEudUTa4C4gem144nOzf0K47vMq4EFOXAYO7AKySbB1WrgxgsAzwxqI87wymgX3nghVCnTwM7bpjZBI5bIe6l0IN7pY+PPv1pWoPBZswe7DCqtUXTWn2/BcXV7f36uGtenv1+KSuH+7/fhj/erp9uK9PAFWfAJ/nGby/RB1A9EjypVdDP+35u0gbcM/xgHVBNI9nqCmu9sTNo2itgtlTKZOSzv5AmYauVIbT7pURrEeVqfudsFWGTqVMsXg+HSjT0JXKcNq9MoL1qDIZj5CyVcafShlsn+AQB9IweKU2gngvjuQ9qo7F3hibi0mefDJ5sAuvtVkvT4PXysOJmzyCd0EeV2p9j7Km7gm2bhNPpg0evfHQiRm8VhtO3LQRvM9rg8Iv75zYncxwrA/aHHoxg9dqw4mbNoL3eW2ws6edF8fTWU7I2h+6MYPXasOJmzaCd0kbp0OZTips8Mhgt67odKaTUBMueHKD1wrEiZtAgve4QBH+tPNkCqdznhy0W3DlBq8ViBM3gQTvcYGwXQg7Zw72dPaDrWBesOYGrxWIEzeBBO+CQPBkmnYWtsCo5jrZ0Mk8iCxpOvRnBq8USBDvBZK8xwQiA7eay2XjT+ZBREHHQ5Nm8FqBOHETSPAeFYisznPVbMrJPIjwSLWHJs3gtQJx4iaQ4D0qUD0wnutmW07mQRRIh0OTZvBagThxE0jwLglk5pTJZ5325bPLp3MhMJpDm2bwWok4cZNI8B6XKMKw9lV0iqfzoVS0XzDqBq+ViBM3iQTvcYkSLGsupkNweycS/es7mpf1bQ22bGm7r6UyHQRPr2Xupm+GV4rvN/c3T7/Xg7bH25v7q/Hxv1AcxQhTvN6GUT8eecsbsOWeVxaDqZ5pLrt+vdJWafP8IPIjyeWvnoN06Qvsd899gR39P+Fb8KJ3oznGbmpeu5lkxTy62Q8wTbWf15gJdTCdNTNFHdCvHu7+uHp/+/gwnZ5u/tlcT8em6un2bvOofts8fdhs7tWb2/eb6yd1df/m+QPW4V8Q8QeUCmVuZHN0cmVhbQplbmRvYmoKMTEgMCBvYmoKMTg3MgplbmRvYmoKMTYgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAyMzIgPj4Kc3RyZWFtCnicNVE7cgUxCOt9Cl0gM+Zvn2czr0ru30awk2ZhAQkJ5z3YiMSXGNId5YpvWZ1mGX4ni7z4WSmcvBdRgVRFWCHt4FnOaobBcyNT4HImPsvMJ9NixwKqiTjOjpxmMAgxjetoOR1mmgc9IdcHI27sNMtVDGm9W6rX91r+U0X5yLqb5dYpm1qpW/SMPYnLzuupLe0Lo47ipiDS4WOH9yBfxJzFRSfSzX4z5bCSNASnBfAjMZTq2eE1wsTPjARP2dPpfZSG1z5our53L+jIzYRM5RbKSMWTlcaYMVS/Ec0k9f0/0LM+f5owVEcKZW5kc3RyZWFtCmVuZG9iagoxNyAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDI0NCA+PgpzdHJlYW0KeJxNUUluxDAMu/sV/MAAlqzFeU+Kntr/X0s6GEwPhhhZ4hJ3Jyay8LKFuhY6HF828krYDPwetObEz4gV/9E2Iq18UG2BTMREkdBF3WjcI93wKkT7kQpeqd5jzUfcrTRv6djF/t4H05pHqqwK8ZBjc2QjaV0TRcf30HrPDdEpgwT63IQcEKU5ehWS/toP17XR7NbazJ6oDh6ZEsonzWpoTqeYIbOhHrepWMko3KgyKu5TGWk9yNs4ywBOjhPKaD3ZsZqI8lOfXEJeTMQJu+zsWIhNLGwc0n5U+sTy860342+mtZZCxgWJ0BSX3s94j+8/3VhbtAplbmRzdHJlYW0KZW5kb2JqCjE4IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggNTkgPj4Kc3RyZWFtCnicMzU1VzBQsLQAEqamRgrmRpYKKYZcQD6IlctlaGkOZuWAWRbGQAZIGZxhAKTBmnNgenK40gCp4RBaCmVuZHN0cmVhbQplbmRvYmoKMTkgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAzMDQgPj4Kc3RyZWFtCnicPZI7ksMwDEN7nYIXyIz4k+TzZCeV9/7tPjLJVoBJiQAoL3WZsqY8IGkmCf/R4eFiO+V32J7NzMC1RC8TyynPoSvE3EX5spmNurI6xarDMJ1b9Kici4ZNk5rnKksZtwuew7WJ55Z9xA83NKgHdY1Lwg3d1WhZCs1wdf87vUfZdzU8F5tU6tQXjxdRFeb5IU+ih+lK4nw8KCFcezBGFhLkU9FAjrNcrfJeQvYOtxqywkFqSeezJzzYdXpPLm4XzRAPZLlU+E5R7O3QM77sSgk9ErbhWO59O5qx6RqbOOx+70bWyoyuaCF+yFcn6yVg3FMmRRJkTrZYbovVnu6hKKZzhnMZIOrZioZS5mJXq38MO28sL9ksyJTMCzJGp02eOHjIfo2a9HmV53j9AWzzczsKZW5kc3RyZWFtCmVuZG9iagoyMCAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDIzNyA+PgpzdHJlYW0KeJxFUUlyBCEMu/cr9IGpwivwnk7NqfP/aywzSU4WYGsxaYGBLXiJIdbAzIEvuXxN6DR8NzLb8DrZHnBPuC7cl8uCZ8KWwFdUl3e9L13ZSH13h6p+ZmR7s0jNkJWVOvVCNCbYIRE9IzLJVixzg6QprVLlvihbgC7qlbZOO42SoCMU4W+UI+HpFUp2TWwaq9Q6oKEIy7YuiDqZJKJ2YXFq8ZYhIp91YzXH+ItOInbH4/6sMOtRJJLSZwfdcSajTZZdAzm5eaqwVio5iD5e0caE6nSqgWO817b0E2ngufZf4Qc+ff+PGPq53j/G7lwiCmVuZHN0cmVhbQplbmRvYmoKMjEgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAyMzAgPj4Kc3RyZWFtCnicNVFJbsMwDLzrFfOBAOIuv8dBT+3/rx3SCWBgaEuczREbGxF4icHPQeTGW9aMmvibyV3xuzwVHgm3gidRBF6Ge9kJLm8Yl/04zHzwXlo5kxpPMiAX2fTwRMhgl0DowOwa1GGbaSf6hoTPjkg1G1lOX0vQS6sQKE/ZfqcLSrSt6s/tsy607WtPONntqSeVTyCeW7ICl41XTBZjGfRE5S7F9EGqs4WehPKifA6y+aghEl2inIEnBgejQDuw57afiVeFoHV1n7aNoRopHU//NjQ1SSLkEyWc2dK4W/j+nnv9/AOmVFOfCmVuZHN0cmVhbQplbmRvYmoKMjIgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAyMjcgPj4Kc3RyZWFtCnicNU87sgMhDOs5hS6QGYxtYM+zmVQv92+fZLINEv5I8vRERyZe5sgIrNnxthYZiBn4FlPxrz3tw4TqPbiHCOXiQphhJJw167ibp+PFv13lM9bBuw2+YpYXBLYwk/WVxZnLdsFYGidxTrIbY9dEbGNd6+kU1hFMKAMhne0wJcgcFSl9sqOMOTpO5InnYqrFLr/vYX3BpjGiwhxXBU/QZFCWPe8moB0X9N/Vjd9JNIteAjKRYGGdJObOWU741WtHx1GLIjEnpBnkMhHSnK5iCqEJxTo7CioVBZfqc8rdPv9oXVtNCmVuZHN0cmVhbQplbmRvYmoKMjMgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAyNDUgPj4Kc3RyZWFtCnicRVC7jUMxDOs9BRcIYP0se553SJXbvz1KRnCFIVo/kloSmIjASwyxlG/iR0ZBPQu/F4XiM8TPF4VBzoSkQJz1GRCZeIbaRm7odnDOvMMzjDkCF8VacKbTmfZc2OScBycQzm2U8YxCuklUFXFUn3FM8aqyz43XgaW1bLPTkewhjYRLSSUml35TKv+0KVsq6NpFE7BI5IGTTTThLD9DkmLMoJRR9zC1jvRxspFHddDJ2Zw5LZnZ7qftTHwPWCaZUeUpnecyPiep81xOfe6zHdHkoqVV+5z93pGW8iK126HV6VclUZmN1aeQuDz/jJ/x/gOOoFk+CmVuZHN0cmVhbQplbmRvYmoKMjQgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAzOTIgPj4Kc3RyZWFtCnicPVJLbgUxCNvPKbhApfBNcp6p3u7df1ubzFSqCi8DtjGUlwypJT/qkogzTH71cl3iUfK9bGpn5iHuLjam+FhyX7qG2HLRmmKxTxzJL8i0VFihVt2jQ/GFKBMPAC3ggQXhvhz/8ReowdewhXLDe2QCYErUbkDGQ9EZSFlBEWH7kRXopFCvbOHvKCBX1KyFoXRiiA2WACm+qw2JmKjZoIeElZKqHdLxjKTwW8FdiWFQW1vbBHhm0BDZ3pGNETPt0RlxWRFrPz3po1EytVEZD01nfPHdMlLz0RXopNLI3cpDZ89CJ2Ak5kmY53Aj4Z7bQQsx9HGvlk9s95gpVpHwBTvKAQO9/d6Sjc974CyMXNvsTCfw0WmnHBOtvh5i/YM/bEubXMcrh0UUqLwoCH7XQRNxfFjF92SjRHe0AdYjE9VoJRAMEsLO7TDyeMZ52d4VtOb0RGijRB7UjhE9KLLF5ZwVsKf8rM2xHJ4PJntvtI+UzMyohBXUdnqots9jHdR3nvv6/AEuAKEZCmVuZHN0cmVhbQplbmRvYmoKMjUgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAxMzMgPj4Kc3RyZWFtCnicTY9BEsMwCAPvfoWegLEB8550ekr+fy2QNu4F7YyAkYYwCDxiDOswJbx6++FVpEtwNo75JRlFPAhqC9wXVAVHY4qd+Njdoeyl4ukUTYvrEXPTtKR0N1Eqbb2dyPjAfZ/eH1W2JJ2CHlvqhC7RJPJFAnPYVDDP6sZLS4+n7dneH2Y+M9cKZW5kc3RyZWFtCmVuZG9iagoyNiAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDI0NyA+PgpzdHJlYW0KeJxNUbttRDEM698UXOAA62t5ngtSXfZvQ8kIkMIgoS8ppyUW9sZLDOEHWw++5JFVQ38ePzHsMyw9yeTUP+a5yVQUvhWqm5hQF2Lh/WgEvBZ0LyIrygffj2UMc8734KMQl2AmNGCsb0kmF9W8M2TCiaGOw0GbVBh3TRQsrhXNM8jtVjeyOrMgbHglE+LGAEQE2ReQzWCjjLGVkMVyHqgKkgVaYNfpG1GLgiuU1gl0otbEuszgq+f2djdDL/LgqLp4fQzrS7DC6KV7LHyuQh/M9Ew7d0kjvfCmExFmDwVSmZ2RlTo9Yn23QP+fZSv4+8nP8/0LFShcKgplbmRzdHJlYW0KZW5kb2JqCjI3IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggOTAgPj4Kc3RyZWFtCnicTY1BEsAgCAPvvCJPUETQ/3R60v9fq9QOvcBOAokWRYL0NWpLMO64MhVrUCmYlJfAVTBcC9ruosr+MklMnYbTe7cDg7LxcYPSSfv2cXoAq/16Bt0P0hwiWAplbmRzdHJlYW0KZW5kb2JqCjI4IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMzM4ID4+CnN0cmVhbQp4nEVSS3LFMAjb5xRcIDPmZ+PzvE5X6f23lXA63Tz0DAgJMj1lSKbcNpZkhOQc8qVXZIjVkJ9GjkTEEN8pocCu8rm8lsRcyG6JSvGhHT+XpTcyza7QqrdHpzaLRjUrI+cgQ4R6VujM7lHbZMPrdiHpOlMWh3As/0MFspR1yimUBG1B39gj6G8WPBHcBrPmcrO5TG71v+5bC57XOluxbQdACZZz3mAGAMTDCdoAxNza3hYpKB9VuopJwq3yXCc7ULbQqnS8N4AZBxg5YMOSrQ7XaG8Awz4P9KJGxfYVoKgsIP7O2WbB3jHJSLAn5gZOPXE6xZFwSTjGAkCKreIUuvEd2OIvF66ImvAJdTplTbzCntrix0KTCO9ScQLwIhtuXR1FtWxP5wm0PyqSM2KkHsTRCZHUks4RFJcG9dAa+7iJGa+NxOaevt0/wjmf6/sXFriD4AplbmRzdHJlYW0KZW5kb2JqCjI5IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMTYzID4+CnN0cmVhbQp4nEWQuXUEMQxDc1WBEniAOuoZP0ez/acLabzeQPp4hHiIPQnDcl3FhdENP962zDS8jjLcjfVlxviosUBO0AcYIhNXo0n17YozVOnh1WKuo6JcLzoiEsyS46tAI3w6ssdDW9uZfjqvf+wh7xP/KirnbmEBLqruQPlSH/HUj9lR6pqhjyorax5q2r8IuyKUtn1cTmWcunsHtMJnK1f7fQOo5zqACmVuZHN0cmVhbQplbmRvYmoKMzAgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCA2OCA+PgpzdHJlYW0KeJwzMrdQMFCwNAEShhYmCuZmBgophlxAvqmJuUIuF0gMxMoBswyAtCWcgohbQjRBlIJYEKVmJmYQSTgDIpcGAMm0FeUKZW5kc3RyZWFtCmVuZG9iagozMSAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDQ1ID4+CnN0cmVhbQp4nDMyt1AwULA0ARKGFiYK5mYGCimGXJYQVi4XTCwHzALRlnAKIp4GAJ99DLUKZW5kc3RyZWFtCmVuZG9iagozMiAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDI1NSA+PgpzdHJlYW0KeJxFkUuSAyAIRPeegiOA/OQ8mZpVcv/tNJhMNnaXqP2ESiOmEiznFHkw/cjyzWS26bUcq52NAooiFMzkKvRYgdWdKeLMtUS19bEyctzpHYPiDeeunFSyuFHGOqo6FTim58r6qu78uCzKviOHMgVs1jkONnDltmGME6PNVneH+0SQp5Opo+J2kGz4g5PGvsrVFbhONvvqJRgHgn6hCUzyTaB1hkDj5il6cgn28XG780Cwt7wJpGwI5MgQjA5Bu06uf3Hr/N7/OsOd59oMV4538TtMa7vjLzHJirmARe4U1PM9F63rDB3vyZljctN9Q+dcsMvdQabP/B/r9w9QimaICmVuZHN0cmVhbQplbmRvYmoKMzMgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAxNjEgPj4Kc3RyZWFtCnicRZBLEsMgDEP3nEJH8EcGfJ50ukrvv60hTbOAp7FABncnBKm1BRPRBS9tS7oLPlsJzsZ46DZuNRLkBHWAVqTjaJRSfbnFaZV08Wg2cysLrRMdZg56lKMZoBA6Fd7touRypu7O+Udw9V/1R7HunM3EwGTlDoRm9SnufJsdUV3dZH/SY27Wa38V9qqwtKyl5YTbzl0zoATuqRzt/QWpczqECmVuZHN0cmVhbQplbmRvYmoKMzQgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAzMjAgPj4Kc3RyZWFtCnicNVG7ccUwDOs1BRfwnfiVNI9zr8rbvw1AOxVhGgRAqrxkSrlc6pJVssLkR4fqFE35PmCm/A71kOPoHtkhulPWlnsYCMvEPKWOWE2We7gFgS8MTYm5hfP3COgrBqMwE4G6xd8/QLMkMGlw8FOQa61aYokOPCwWWLMrzK0aKVTIVXw7NrkHBXJxs9CnHJoUt9yC8GWIZEdqsa/LZSnyu/UJGIQV5ohPFImF54EOZiLxJwNie/bZYldXL6oRGdZJhwdSBNJsbhIwNEWy6oMb2FfHNT9PR9nByUG/isH4NjiZL0l5XwWhEI8X/g7P2cixkkMkFPJ9tcCII2yAEaFP7SMQZSA0RffumVI+JlWK7wBGIRx9qlcyvBeR2WqGzf8ZXdkqCgZVWR+fRnAmg0k482SjCtNStdO/+9zj8wdjY3qACmVuZHN0cmVhbQplbmRvYmoKMzUgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAyMTQgPj4Kc3RyZWFtCnicPVC7EUMxCOs9BQvkznztN8/Lpcv+bSScpEI2QhKUmkzJlIc6ypKsKU8dPktih7yH5W5kNiUqRS+TsCX30ArxfYnmFPfd1ZazQzSXaDl+CzMqqhsd00s2mnAqE7qg3MMz+g1tdANWhx6xWyDQpGDXtiByxw8YDMGZE4siDEpNBv+tcvdS3O89HG+iiJR08K755fTLzy28Tj2ORLq9+YprcaY6CkRwRmryinRhxbLIQ6TVBDU9A2u1AK7eevk3aEd0GYDsE4njNKUcQ//WuMfrA4eKUvQKZW5kc3RyZWFtCmVuZG9iagozNiAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDgwID4+CnN0cmVhbQp4nEWMuw3AMAhEe6ZgBH4mZp8olbN/GyBK3HBPunu4OhIyU95hhocEngwshlPxBpmjYDW4RlKNneyjsG5fdYHmelOr9fcHKk92dnE9zcsZ9AplbmRzdHJlYW0KZW5kb2JqCjM3IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMjM2ID4+CnN0cmVhbQp4nE1QS25EIQzbc4pc4EkkIQHOQ9VV5/7bscNU7SqGGH9ID+myVR7rU2J1iezypU2XyjJ5FajlT9v/UQwCbv/QyEG0t4ydYuYS1sXCJDzlNCMbJ9csH487TxtmhcbEjeOdLhlgnxYBNVuVzYE5bTo3QLqQGreqs95kUAwi6kLNB5MunKfRl4g5nqhgSncmtZAbXD7VoQNxWr0KuWOLk2/EHFmhwGHQTHHWXwHWqMmyWcggSYYhzn2je5QKjajKeSsVwg+ToRH1htWgBpW5haKp5ZL8HdoCMAW2jHXpDEqBqgDB3yqnfb8BJI1dUwplbmRzdHJlYW0KZW5kb2JqCjM4IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMTU3ID4+CnN0cmVhbQp4nEWQuRFDMQhEc1VBCRKwCOqxx9F3/6kX+Uq0bwAth68lU6ofJyKm3Ndo9DB5Dp9NJVYs2Ca2kxpyGxZBSjGYeE4xq6O3oZmH1Ou4qKq4dWaV02nLysV/82hXM5M9wjXqJ/BN6PifPLSp6FugrwuUfUC1OJ1JUDF9r2KBo5x2fyKcGOA+GUeZKSNxYm4K7PcZAGa+V7jG4wXdATd5CmVuZHN0cmVhbQplbmRvYmoKMzkgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAzMzIgPj4Kc3RyZWFtCnicLVI5jiQxDMv9Cn5gAOvy8Z4eTNT7/3RJVQUFqmzLPORyw0QlfiyQ21Fr4tdGZqDC8K+rzIXvSNvIOohryEVcyZbCZ0Qs5DHEPMSC79v4GR75rMzJswfGL9n3GVbsqQnLQsaLM7TDKo7DKsixYOsiqnt4U6TDqSTY44v/PsVzF4IWviNowC/556sjeL6kRdo9Ztu0Ww+WaUeVFJaD7WnOy+RL6yxXx+P5INneFTtCaleAojB3xnkujjJtZURrYWeDpMbF9ubYj6UEXejGZaQ4AvmZKsIDSprMbKIg/sjpIacyEKau6Uont1EVd+rJXLO5vJ1JMlv3RYrNFM7rwpn1d5gyq807eZYTpU5F+Bl7tgQNnePq2WuZhUa3OcErJXw2dnpy8r2aWQ/JqUhIFdO6Ck6jyBRL2Jb4moqa0tTL8N+X9xl//wEz4nwBCmVuZHN0cmVhbQplbmRvYmoKNDAgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCA2OCA+PgpzdHJlYW0KeJwzMzZTMFCwMAISpqaGCuZGlgophlxAPoiVywUTywGzzCzMgSwjC5CWHC5DC2MwbWJspGBmYgZkWSAxILrSAHL4EpEKZW5kc3RyZWFtCmVuZG9iago0MSAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDMxNyA+PgpzdHJlYW0KeJw1UktyQzEI279TcIHOmL99nnSyau6/rYQnK7AtQEIuL1nSS37UJdulw+RXH/clsUI+j+2azFLF9xazFM8tr0fPEbctCgRREz34MicVItTP1Og6eGGXPgOvEE4pFngHkwAGr+FfeJROg8A7GzLeEZORGhAkwZpLi01IlD1J/Cvl9aSVNHR+Jitz+XtyqRRqo8kIFSBYudgHpCspHiQTPYlIsnK9N1aI3pBXksdnJSYZEN0msU20wOPclbSEmZhCBeZYgNV0s7r6HExY47CE8SphFtWDTZ41qYRmtI5jZMN498JMiYWGwxJQm32VCaqXj9PcCSOmR0127cKyWzbvIUSj+TMslMHHKCQBh05jJArSsIARgTm9sIq95gs5FsCIZZ2aLAxtaCW7eo6FwNCcs6Vhxtee1/P+B0Vbe6MKZW5kc3RyZWFtCmVuZG9iago0MiAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDE3ID4+CnN0cmVhbQp4nDM2tFAwgMMUQy4AGpQC7AplbmRzdHJlYW0KZW5kb2JqCjQzIDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMTMxID4+CnN0cmVhbQp4nEWPyw0EIQxD71ThEvIZPqmH1Z7Y/q/rMJpBQvhBIjvxMAis8/I20MXw0aLDN/421atjlSwfunpSVg/pkIe88hVQaTBRxIVZTB1DYc6YysiWMrcb4bZNg6xslVStg3Y8Bg+2p2WrCH6pbWHqLPEMwlVeuMcNP5BLrXe9Vb5/QlMwlwplbmRzdHJlYW0KZW5kb2JqCjQ0IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMzM4ID4+CnN0cmVhbQp4nDVSOa7dQAzrfQpdIIB2zZznBal+7t+GlF8KQ7RWipqOFpVp+WUhVS2TLr/tSW2JG/L3yQqJE5JXJdqlDJFQ+TyFVL9ny7y+1pwRIEuVCpOTksclC/4Ml94uHOdjaz+PI3c9emBVjIQSAcsUE6NrWTq7w5qN/DymAT/iEXKuWLccYxVIDbpx2hXvQ/N5yBogZpiWigpdVokWfkHxoEetffdYVFgg0e0cSXCMjVCRgHaB2kgMObMWu6gv+lmUmAl07Ysi7qLAEknMnGJdOvoPPnQsqL8248uvjkr6SCtrTNp3o0lpzCKTrpdFbzdvfT24QPMuyn9ezSBBU9YoaXzQqp1jKJoZZYV3HJoMNMcch8wTPIczEpT0fSh+X0smuiiRPw4NoX9fHqOMnAZvAXPRn7aKAxfx2WGvHGCF0sWa5H1AKhN6YPr/1/h5/vwDHLaAVAplbmRzdHJlYW0KZW5kb2JqCjQ1IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMjQ4ID4+CnN0cmVhbQp4nC1ROZIDQQjL5xV6QnPT77HLkff/6QrKAYOGQyA6LXFQxk8Qlive8shVtOHvmRjBd8Gh38p1GxY5EBVI0hhUTahdvB69B3YcZgLzpDUsgxnrAz9jCjd6cXhMxtntdRk1BHvXa09mUDIrF3HJxAVTddjImcNPpowL7VzPDci5EdZlGKSblcaMhCNNIVJIoeomqTNBkASjq1GjjRzFfunLI51hVSNqDPtcS9vXcxPOGjQ7Fqs8OaVHV5zLycULKwf9vM3ARVQaqzwQEnC/20P9nOzkN97SubPF9Phec7K8MBVY8ea1G5BNtfg3L+L4PePr+fwDqKVbFgplbmRzdHJlYW0KZW5kb2JqCjQ2IDAgb2JqCjw8IC9GaWx0ZXIgL0ZsYXRlRGVjb2RlIC9MZW5ndGggMTcxID4+CnN0cmVhbQp4nE2QTQ5CIRCD95yiFzCh8wOP82hc6f23dvD54oL0SyFDp8MDHUfiRkeGzuh4sMkxDrwLMiZejfOfjOskjgnqFW3BurQ77s0sMScsEyNga5Tcm0cU+OGYC0GC7PLDFxhEpGuYbzWfdZN+frvTXdSldffTIwqcyI5QDBtwBdjTPQ7cEs7vmia/VCkZmziUD1QXkbLZCYWopWKXU1VojOJWPe+LXu35AcH2O/sKZW5kc3RyZWFtCmVuZG9iago0NyAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDcyID4+CnN0cmVhbQp4nDWMsRHAMAgDe6bQCDZYYO+TS0X2b0N8TgMvHQ+XosFaDbqCI3B1qfzRI125KUWXY86C4XGqX0gxRj2oI+Pex0+5X3AWEn0KZW5kc3RyZWFtCmVuZG9iago0OCAwIG9iago8PCAvRmlsdGVyIC9GbGF0ZURlY29kZSAvTGVuZ3RoIDg4ID4+CnN0cmVhbQp4nDWMuxHAMAhDe0/BCAaLj/fJpUr2b4Pt0ICkd/eCgzpB8rgbKZwubtlXehuPk54mALH0TEPt32BF1YtaFC1fbmPQYiq+P/okIJZ18l449JAS3h/FFx17CmVuZHN0cmVhbQplbmRvYmoKNDkgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCA4NyA+PgpzdHJlYW0KeJw1TbkRwDAI65mCEcyj2OyTS+Xs3wbsuEE6fSCUG2vkAYLhnW8h+KYvGYR1CE8quyU6bKGGswqSieFXNnhVror2tZKJ7GymMdigZfrRzrdJzwel3huYCmVuZHN0cmVhbQplbmRvYmoKNTAgMCBvYmoKPDwgL0ZpbHRlciAvRmxhdGVEZWNvZGUgL0xlbmd0aCAyMTAgPj4Kc3RyZWFtCnicNVDLDUMxCLtnChaoFAKBZJ5WvXX/a23QO2ER/0JYyJQIeanJzinpSz46TA+2Lr+xIgutdSXsypognivvoZmysdHY4mBwGiZegBY3YOhpjRo1dOGCpi6VQoHFJfCZfHV76L5PGXhqGXJ2BBFDyWAJaroWTVi0PJ+QTgHi/37D7i3koZLzyp4b+Ruc7fA7s27hJ2p2ItFyFTLUszTHGAgTRR48eUWmcOKz1nfVNBLUZgtOlgGuTj+MDgBgIl5ZgOyuRDlL0o6ln2+8x/cPQABTtAplbmRzdHJlYW0KZW5kb2JqCjE0IDAgb2JqCjw8IC9CYXNlRm9udCAvRGVqYVZ1U2FucyAvQ2hhclByb2NzIDE1IDAgUgovRW5jb2RpbmcgPDwKL0RpZmZlcmVuY2VzIFsgMzIgL3NwYWNlIDQ4IC96ZXJvIC9vbmUgL3R3byAvdGhyZWUgL2ZvdXIgL2ZpdmUgL3NpeCAvc2V2ZW4gL2VpZ2h0IC9uaW5lCjY3IC9DIDcxIC9HIDc2IC9MIDk3IC9hIC9iIC9jIC9kIC9lIC9mIC9nIC9oIC9pIDEwOCAvbCAvbSAvbiAvbyAvcCAxMTQgL3IKL3MgL3QgL3UgL3YgL3cgL3ggXQovVHlwZSAvRW5jb2RpbmcgPj4KL0ZpcnN0Q2hhciAwIC9Gb250QkJveCBbIC0xMDIxIC00NjMgMTc5NCAxMjMzIF0gL0ZvbnREZXNjcmlwdG9yIDEzIDAgUgovRm9udE1hdHJpeCBbIDAuMDAxIDAgMCAwLjAwMSAwIDAgXSAvTGFzdENoYXIgMjU1IC9OYW1lIC9EZWphVnVTYW5zCi9TdWJ0eXBlIC9UeXBlMyAvVHlwZSAvRm9udCAvV2lkdGhzIDEyIDAgUiA+PgplbmRvYmoKMTMgMCBvYmoKPDwgL0FzY2VudCA5MjkgL0NhcEhlaWdodCAwIC9EZXNjZW50IC0yMzYgL0ZsYWdzIDMyCi9Gb250QkJveCBbIC0xMDIxIC00NjMgMTc5NCAxMjMzIF0gL0ZvbnROYW1lIC9EZWphVnVTYW5zIC9JdGFsaWNBbmdsZSAwCi9NYXhXaWR0aCAxMzQyIC9TdGVtViAwIC9UeXBlIC9Gb250RGVzY3JpcHRvciAvWEhlaWdodCAwID4+CmVuZG9iagoxMiAwIG9iagpbIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwCjYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgNjAwIDYwMCA2MDAgMzE4IDQwMSA0NjAgODM4IDYzNgo5NTAgNzgwIDI3NSAzOTAgMzkwIDUwMCA4MzggMzE4IDM2MSAzMTggMzM3IDYzNiA2MzYgNjM2IDYzNiA2MzYgNjM2IDYzNiA2MzYKNjM2IDYzNiAzMzcgMzM3IDgzOCA4MzggODM4IDUzMSAxMDAwIDY4NCA2ODYgNjk4IDc3MCA2MzIgNTc1IDc3NSA3NTIgMjk1CjI5NSA2NTYgNTU3IDg2MyA3NDggNzg3IDYwMyA3ODcgNjk1IDYzNSA2MTEgNzMyIDY4NCA5ODkgNjg1IDYxMSA2ODUgMzkwIDMzNwozOTAgODM4IDUwMCA1MDAgNjEzIDYzNSA1NTAgNjM1IDYxNSAzNTIgNjM1IDYzNCAyNzggMjc4IDU3OSAyNzggOTc0IDYzNCA2MTIKNjM1IDYzNSA0MTEgNTIxIDM5MiA2MzQgNTkyIDgxOCA1OTIgNTkyIDUyNSA2MzYgMzM3IDYzNiA4MzggNjAwIDYzNiA2MDAgMzE4CjM1MiA1MTggMTAwMCA1MDAgNTAwIDUwMCAxMzQyIDYzNSA0MDAgMTA3MCA2MDAgNjg1IDYwMCA2MDAgMzE4IDMxOCA1MTggNTE4CjU5MCA1MDAgMTAwMCA1MDAgMTAwMCA1MjEgNDAwIDEwMjMgNjAwIDUyNSA2MTEgMzE4IDQwMSA2MzYgNjM2IDYzNiA2MzYgMzM3CjUwMCA1MDAgMTAwMCA0NzEgNjEyIDgzOCAzNjEgMTAwMCA1MDAgNTAwIDgzOCA0MDEgNDAxIDUwMCA2MzYgNjM2IDMxOCA1MDAKNDAxIDQ3MSA2MTIgOTY5IDk2OSA5NjkgNTMxIDY4NCA2ODQgNjg0IDY4NCA2ODQgNjg0IDk3NCA2OTggNjMyIDYzMiA2MzIgNjMyCjI5NSAyOTUgMjk1IDI5NSA3NzUgNzQ4IDc4NyA3ODcgNzg3IDc4NyA3ODcgODM4IDc4NyA3MzIgNzMyIDczMiA3MzIgNjExIDYwNQo2MzAgNjEzIDYxMyA2MTMgNjEzIDYxMyA2MTMgOTgyIDU1MCA2MTUgNjE1IDYxNSA2MTUgMjc4IDI3OCAyNzggMjc4IDYxMiA2MzQKNjEyIDYxMiA2MTIgNjEyIDYxMiA4MzggNjEyIDYzNCA2MzQgNjM0IDYzNCA1OTIgNjM1IDU5MiBdCmVuZG9iagoxNSAwIG9iago8PCAvQyAxNiAwIFIgL0cgMTcgMCBSIC9MIDE4IDAgUiAvYSAxOSAwIFIgL2IgMjAgMCBSIC9jIDIxIDAgUiAvZCAyMiAwIFIKL2UgMjMgMCBSIC9laWdodCAyNCAwIFIgL2YgMjUgMCBSIC9maXZlIDI2IDAgUiAvZm91ciAyNyAwIFIgL2cgMjggMCBSCi9oIDI5IDAgUiAvaSAzMCAwIFIgL2wgMzEgMCBSIC9tIDMyIDAgUiAvbiAzMyAwIFIgL25pbmUgMzQgMCBSIC9vIDM1IDAgUgovb25lIDM2IDAgUiAvcCAzNyAwIFIgL3IgMzggMCBSIC9zIDM5IDAgUiAvc2V2ZW4gNDAgMCBSIC9zaXggNDEgMCBSCi9zcGFjZSA0MiAwIFIgL3QgNDMgMCBSIC90aHJlZSA0NCAwIFIgL3R3byA0NSAwIFIgL3UgNDYgMCBSIC92IDQ3IDAgUgovdyA0OCAwIFIgL3ggNDkgMCBSIC96ZXJvIDUwIDAgUiA+PgplbmRvYmoKMyAwIG9iago8PCAvRjEgMTQgMCBSID4+CmVuZG9iago0IDAgb2JqCjw8IC9BMSA8PCAvQ0EgMCAvVHlwZSAvRXh0R1N0YXRlIC9jYSAxID4+Ci9BMiA8PCAvQ0EgMSAvVHlwZSAvRXh0R1N0YXRlIC9jYSAxID4+ID4+CmVuZG9iago1IDAgb2JqCjw8ID4+CmVuZG9iago2IDAgb2JqCjw8ID4+CmVuZG9iago3IDAgb2JqCjw8ID4+CmVuZG9iagoyIDAgb2JqCjw8IC9Db3VudCAxIC9LaWRzIFsgMTAgMCBSIF0gL1R5cGUgL1BhZ2VzID4+CmVuZG9iago1MSAwIG9iago8PCAvQ3JlYXRpb25EYXRlIChEOjIwMTkwNjI3MTUyODU4KzAyJzAwJykKL0NyZWF0b3IgKG1hdHBsb3RsaWIgMy4wLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZykKL1Byb2R1Y2VyIChtYXRwbG90bGliIHBkZiBiYWNrZW5kIDMuMC4zKSA+PgplbmRvYmoKeHJlZgowIDUyCjAwMDAwMDAwMDAgNjU1MzUgZiAKMDAwMDAwMDAxNiAwMDAwMCBuIAowMDAwMDEzOTc5IDAwMDAwIG4gCjAwMDAwMTM3ODUgMDAwMDAgbiAKMDAwMDAxMzgxNyAwMDAwMCBuIAowMDAwMDEzOTE2IDAwMDAwIG4gCjAwMDAwMTM5MzcgMDAwMDAgbiAKMDAwMDAxMzk1OCAwMDAwMCBuIAowMDAwMDAwMDY1IDAwMDAwIG4gCjAwMDAwMDAzOTkgMDAwMDAgbiAKMDAwMDAwMDIwOCAwMDAwMCBuIAowMDAwMDAyMzQ2IDAwMDAwIG4gCjAwMDAwMTIzMjYgMDAwMDAgbiAKMDAwMDAxMjEyNiAwMDAwMCBuIAowMDAwMDExNjY4IDAwMDAwIG4gCjAwMDAwMTMzNzkgMDAwMDAgbiAKMDAwMDAwMjM2NyAwMDAwMCBuIAowMDAwMDAyNjcyIDAwMDAwIG4gCjAwMDAwMDI5ODkgMDAwMDAgbiAKMDAwMDAwMzEyMCAwMDAwMCBuIAowMDAwMDAzNDk3IDAwMDAwIG4gCjAwMDAwMDM4MDcgMDAwMDAgbiAKMDAwMDAwNDExMCAwMDAwMCBuIAowMDAwMDA0NDEwIDAwMDAwIG4gCjAwMDAwMDQ3MjggMDAwMDAgbiAKMDAwMDAwNTE5MyAwMDAwMCBuIAowMDAwMDA1Mzk5IDAwMDAwIG4gCjAwMDAwMDU3MTkgMDAwMDAgbiAKMDAwMDAwNTg4MSAwMDAwMCBuIAowMDAwMDA2MjkyIDAwMDAwIG4gCjAwMDAwMDY1MjggMDAwMDAgbiAKMDAwMDAwNjY2OCAwMDAwMCBuIAowMDAwMDA2Nzg1IDAwMDAwIG4gCjAwMDAwMDcxMTMgMDAwMDAgbiAKMDAwMDAwNzM0NyAwMDAwMCBuIAowMDAwMDA3NzQwIDAwMDAwIG4gCjAwMDAwMDgwMjcgMDAwMDAgbiAKMDAwMDAwODE3OSAwMDAwMCBuIAowMDAwMDA4NDg4IDAwMDAwIG4gCjAwMDAwMDg3MTggMDAwMDAgbiAKMDAwMDAwOTEyMyAwMDAwMCBuIAowMDAwMDA5MjYzIDAwMDAwIG4gCjAwMDAwMDk2NTMgMDAwMDAgbiAKMDAwMDAwOTc0MiAwMDAwMCBuIAowMDAwMDA5OTQ2IDAwMDAwIG4gCjAwMDAwMTAzNTcgMDAwMDAgbiAKMDAwMDAxMDY3OCAwMDAwMCBuIAowMDAwMDEwOTIyIDAwMDAwIG4gCjAwMDAwMTEwNjYgMDAwMDAgbiAKMDAwMDAxMTIyNiAwMDAwMCBuIAowMDAwMDExMzg1IDAwMDAwIG4gCjAwMDAwMTQwMzkgMDAwMDAgbiAKdHJhaWxlcgo8PCAvSW5mbyA1MSAwIFIgL1Jvb3QgMSAwIFIgL1NpemUgNTIgPj4Kc3RhcnR4cmVmCjE0MTkzCiUlRU9GCg==\n",
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import timeit\n",
"\n",
"n = np.arange(17) # lengths = 2**n to evaluate\n",
"reps = 100 # 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.barh(n, 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.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 1
}