{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": false, "deletable": true, "editable": true }, "source": [ "Entropic Coding and Compression\n", "===============================\n", "\n", "*Important:* Please read the [installation page](http://gpeyre.github.io/numerical-tours/installation_python/) for details about how to install the toolboxes.\n", "$\\newcommand{\\dotp}[2]{\\langle #1, #2 \\rangle}$\n", "$\\newcommand{\\enscond}[2]{\\lbrace #1, #2 \\rbrace}$\n", "$\\newcommand{\\pd}[2]{ \\frac{ \\partial #1}{\\partial #2} }$\n", "$\\newcommand{\\umin}[1]{\\underset{#1}{\\min}\\;}$\n", "$\\newcommand{\\umax}[1]{\\underset{#1}{\\max}\\;}$\n", "$\\newcommand{\\umin}[1]{\\underset{#1}{\\min}\\;}$\n", "$\\newcommand{\\uargmin}[1]{\\underset{#1}{argmin}\\;}$\n", "$\\newcommand{\\norm}[1]{\\|#1\\|}$\n", "$\\newcommand{\\abs}[1]{\\left|#1\\right|}$\n", "$\\newcommand{\\choice}[1]{ \\left\\{ \\begin{array}{l} #1 \\end{array} \\right. }$\n", "$\\newcommand{\\pa}[1]{\\left(#1\\right)}$\n", "$\\newcommand{\\diag}[1]{{diag}\\left( #1 \\right)}$\n", "$\\newcommand{\\qandq}{\\quad\\text{and}\\quad}$\n", "$\\newcommand{\\qwhereq}{\\quad\\text{where}\\quad}$\n", "$\\newcommand{\\qifq}{ \\quad \\text{if} \\quad }$\n", "$\\newcommand{\\qarrq}{ \\quad \\Longrightarrow \\quad }$\n", "$\\newcommand{\\ZZ}{\\mathbb{Z}}$\n", "$\\newcommand{\\CC}{\\mathbb{C}}$\n", "$\\newcommand{\\RR}{\\mathbb{R}}$\n", "$\\newcommand{\\EE}{\\mathbb{E}}$\n", "$\\newcommand{\\Zz}{\\mathcal{Z}}$\n", "$\\newcommand{\\Ww}{\\mathcal{W}}$\n", "$\\newcommand{\\Vv}{\\mathcal{V}}$\n", "$\\newcommand{\\Nn}{\\mathcal{N}}$\n", "$\\newcommand{\\NN}{\\mathcal{N}}$\n", "$\\newcommand{\\Hh}{\\mathcal{H}}$\n", "$\\newcommand{\\Bb}{\\mathcal{B}}$\n", "$\\newcommand{\\Ee}{\\mathcal{E}}$\n", "$\\newcommand{\\Cc}{\\mathcal{C}}$\n", "$\\newcommand{\\Gg}{\\mathcal{G}}$\n", "$\\newcommand{\\Ss}{\\mathcal{S}}$\n", "$\\newcommand{\\Pp}{\\mathcal{P}}$\n", "$\\newcommand{\\Ff}{\\mathcal{F}}$\n", "$\\newcommand{\\Xx}{\\mathcal{X}}$\n", "$\\newcommand{\\Mm}{\\mathcal{M}}$\n", "$\\newcommand{\\Ii}{\\mathcal{I}}$\n", "$\\newcommand{\\Dd}{\\mathcal{D}}$\n", "$\\newcommand{\\Ll}{\\mathcal{L}}$\n", "$\\newcommand{\\Tt}{\\mathcal{T}}$\n", "$\\newcommand{\\si}{\\sigma}$\n", "$\\newcommand{\\al}{\\alpha}$\n", "$\\newcommand{\\la}{\\lambda}$\n", "$\\newcommand{\\ga}{\\gamma}$\n", "$\\newcommand{\\Ga}{\\Gamma}$\n", "$\\newcommand{\\La}{\\Lambda}$\n", "$\\newcommand{\\si}{\\sigma}$\n", "$\\newcommand{\\Si}{\\Sigma}$\n", "$\\newcommand{\\be}{\\beta}$\n", "$\\newcommand{\\de}{\\delta}$\n", "$\\newcommand{\\De}{\\Delta}$\n", "$\\newcommand{\\phi}{\\varphi}$\n", "$\\newcommand{\\th}{\\theta}$\n", "$\\newcommand{\\om}{\\omega}$\n", "$\\newcommand{\\Om}{\\Omega}$" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "This numerical tour studies source coding using entropic coders (Huffman and arithmetic).\n", "\n", "You need to install the package _ape_" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "options(repr.plot.width=3.5, repr.plot.height=3.5)\n", "options(warn=-1) # turns off warnings, to turn on: \"options(warn=0)\"\n", "\n", "library(Matrix)\n", "library(stringr)\n", "library(ape)\n", "\n", "# Importing the libraries\n", "for (f in list.files(path=\"nt_toolbox/toolbox_general/\", pattern=\"*.R\")) {\n", " source(paste(\"nt_toolbox/toolbox_general/\", f, sep=\"\"))\n", "}\n", "for (f in list.files(path=\"nt_toolbox/toolbox_signal/\", pattern=\"*.R\")) {\n", " source(paste(\"nt_toolbox/toolbox_signal/\", f, sep=\"\"))\n", "}" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Source Coding and Entropy\n", "-------------------------\n", "Entropic coding converts a vector $x$ of integers into a binary stream\n", "$y$. Entropic coding exploits the\n", "redundancies in the statistical distribution of the entries of $x$ to\n", "reduce as much as possible the size of $y$. The lower bound for the\n", "number of bits $p$ of $y$ is the Shannon bound :\n", "\n", "$$p=-\\sum_ih(i)\\log_2(h(i))$$\n", "\n", "where $h(i)$ is the probability of apparition of symbol $i$ in $x$.\n", "\n", "Fist we generate a simple binary signal $x$ so that $0$ has a probability $p$\n", "to appear in $x$.\n", "\n", "Probability of 0." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "p = 0.1" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Size.\n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "n = 512" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Signal, should be with token 1,2." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "x = ceiling(runif(n, 0, 1) > p ) +1" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "One can check the probabilities by computing the empirical histogram." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1] \"Empirical p = 0.083984375\"\n" ] } ], "source": [ "h = c(sum(x==1), sum(x==2))\n", "h = h/sum(h)\n", "\n", "print(paste(\"Empirical p =\" , h[1]))" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "We can compute the entropy of the distribution represented as a vector $h$ of proability that should sum to 1.\n", "We take a max to avoid problems with null probabilties." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1] \"Entropy = 0.416065091363473\"\n" ] } ], "source": [ "e = - sum(h*log2(c(max(h[1],1e-20), max(h[2],1e-20))))\n", "print(paste(\"Entropy = \", e))" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Huffman Coding\n", "--------------\n", "A Hufman code $C$ associates to each symbol $i$ in $\\{1,...,m\\}$ a binary code $C_i$\n", "whose length is as close as possible to the optimal bound\n", "$-\\log_2\\left(h(i)\\right)$, where $h(i)$ is the probability of apparition of the\n", "symbol $i$.\n", "\n", "We select a set of proabilities." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "h = c(.1, .15, .4, .15, .2)" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "The tree $T$ contains the codes and is generated by an iterative algorithm.\n", "The initial \"tree\" is a collection of empty trees, pointing to the symbols numbers." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "m = length(h)\n", "T = list(list())" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "We build iteratively the Huffman tree\n", "by grouping together the two erees that have the smallest probabilities.\n", "The merged tree has a probability which is the sum of the two selected\n", "probabilities.\n", "\n", "Initial probability." ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "#we use the symbols i = 1,2,3,4,5 (as strings) with the associated probabilities h(i)\n", "\n", "for (i in (1:m))\n", "{\n", " T[[i]] = list(toString(i), h[i])\n", " \n", " }\n" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Iterative merging of the leading probabilities." ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "while (length(T)>=2)\n", "{\n", " T = T[order(sapply(T,'[[',2))]\n", " q = as.numeric(T[[1]][2])+as.numeric(T[[2]][2])\n", " t = T[1:2]\n", " T = T[-(1:2)]\n", " T[[length(T)+1]] = list(t,q)\n", "}" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "We trim the computed tree by removing the probabilities." ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "trim = function(T)\n", "{\n", " T0 = T[[1]][1]\n", " if (typeof(T0[[1]][1]) == 'character')\n", " {\n", " return (T0)\n", " }\n", " else\n", " {\n", " return (list(trim(T0[[1]][1]),trim(T0[[1]][2])))\n", " }\n", "}\n", "\n", "K = list()\n", "K[[1]] = list(trim(T)[[1]][[1]][1],trim(T)[[2]])\n", "T = K " ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "We display T " ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAA8AAAAEsCAIAAACDrU0cAAAABmJLR0QA/wD/AP+gvaeTAAAN\nVklEQVR4nO3dX2jV9R/H8c8xWxuUf6j1B/QmkSkLvJCyFWGF/cFFd2oWQWB2YUZIODCyhZmJ\nWAc0YuEQlAz8A5UYDoLQCg6IECwWmg2hKMi/DcvUTme/iwMi5XTvH9HnnM7jcSH63c0LQ3vu\nw9fzKQwPDycAAGB0xuQeAAAA9URAAwBAgIAGAIAAAQ0AAAECGgAAAgQ0AAAECGgAAAgQ0AAA\nECCgAQAgQEADAECAgAYAgAABDQAAAQIaAAACBDQAAAQIaAAACBDQAAAQIKABACBAQAMAQICA\nBgCAAAENAAABAhoAAAIENAAABAhoAAAIENAAABAgoAEAIEBAAwBAgIAGAIAAAQ0AAAECGgAA\nAgQ0AAAECGgAAAgQ0AAAECCgAQAgQEADAECAgAYAgAABDQAAAQIaAAACBDQAAAQIaAAACBDQ\nAAAQIKABACBAQAMAQICABgCAAAENAAABAhoAAAIENAAABAhoAAAIENAAABAgoAEAIEBAAwBA\ngIAGAIAAAQ0AAAECGgAAAgQ0AAAECGgAAAgQ0AAAECCgAQAgQEADAECAgAYAgAABDQAAAQIa\nAAACBDQAAAQIaAAACBDQAAAQIKABACBAQAMAQICABgCAAAENAAABAhoAAAIENAAABAhoAAAI\nENAAABAgoAEAIEBAAwBAgIAGAIAAAQ0AAAECGgAAAgQ0AAAECGgAAAgQ0AAAECCgAQAgQEAD\nAECAgAYAgAABDQAAAQIaAAACBDQAAAQIaAAACBDQAAAQIKABACBAQAMAQICABgCAAAENAAAB\nAhoAAAIENAAABAhoAAAIENAAABAgoAEAIEBAAwAwol27dhUKhc7OztxDaoiABgBgRN9++21K\n6bbbbluyZMmtt97a3Nx8xx13rF+/vlwu556WTWF4eDj3BgDg33PhwoW1a9e2tbWNGeMcjSsp\nl8t9fX2VSuX9998vFP4ajQ8//PCePXuuvfbaXPMyEtAA0FhWr169cuXK3CuoG7fccsvPP/88\nc+bM9evXz5o1a2hoaOfOnStWrPjtt9/eeOONl19+OffADAQ0ADSW7du3P/HEE8uWLevo6Mi9\nhZpWPYHu6elpaWn5y5d6e3sXL17c1tZ26NChLNvyEtAA0Fh27tw5f/78HTt2zJs3L/cW6tWJ\nEydaW1ubmprOnz+fe0sGXn4CACDmjz/+SCndcMMNuYfkIaABABhRa2troVD4y6sa27ZtSynd\nfffdmUZlJqABABjRo48+mlJasGDB/v37z50799NPP23YsKH671BfeOGF3OvyGJt7AAAAtWvN\nmjX79u3r7++///77L32+dOnSRx55JNOozJxAAwAwosmTJ/f3969cubK9vb2lpWX8+PH33Xff\n1q1bN27cmHtaNk6goQ649QD4B5VKpZRSpVLJPYS6MXHixFWrVq1atSr3kFohoKEOrFu3rru7\nO/cK4D9lYGAg9wSoVwIa6sDUqVNTSm49AP4RpVKpWCy2t7fnHgL1SkBDHai+udHR0eHWA+Af\nUSwWvRLG/+eHH36YMWPG6dOnG/kyPn94AAAYlUql8vTTT58+fTr3kMwENAAAo/Lmm2/u378/\n94r8BDQAAFd34MCB1157bcKECbmH5CegAQC4il9//fXJJ58sl8s9PT25t+QnoAEAuIrnn39+\ncHDwmWeeWbBgQe4t+fkUDgBoLNUrVKrXqcAVlMvlvr6+np6e3bt3b926dcqUKY18++ClBDQA\nNJYjR46klIrFYrFYzL2FOnDhwoW9e/eOHTv2gw8+uP7663PPqQkCGgAaS1dXV6VSaWtr81HQ\nXFn1BPq7774bGhpavXr1XXfdlXtRrSg08odgQ73YuXPn/Pnzd+zY4SIVAP5lhULhCl9tzJL0\nrScAAAR4hQMAgBH9/Yy5eibdmGfPVU6gAQAgQEADAECAgAYAgADvQOd04cKFtWvX+iAhrqp6\n30H17gMAyKuR336uEtA5rVu3rru7O/cK6sbAwEDuCQCAgM5q6tSpKaVly5Z1dHTk3kJNK5VK\nxWKxvb099xAAQEBnVX1zo6Ojw+0YXFWxWPSqDwDUAv8/BgDgSn7//ffVq1fPmDFj3LhxLS0t\n06ZNW758+enTp3PvysYJNAAAIzp79uzs2bMPHjx48cnhw4cPHz68Z8+eUqk0YcKEjNtycQIN\nAMCINm7cePDgwdbW1u3bt//yyy9DQ0Mff/zxpEmTDh061LCfhSCgAQAY0fbt21NK77777vz5\n88ePHz9u3LjHH398y5YtKaVdu3blXpeHgAYAYESDg4MppTlz5lz68M4770wpnTx5Ms+m3LwD\nDQDAiIaGhv7+8LPPPkspTZs27V+fUxMENAA0FvfgMkrlcrmvr6+np6elpeXS5/v27Vu0aFFK\nafny5ZmmZSagAaCxuAeXkKampk2bNlV/fvLkyRUrVvT29qaUuru7n3rqqazTshHQANBY3IPL\nKFVPoDds2JBSqlQq77333iuvvHLq1KmpU6f29PQ8+OCDuQdmI6ABoLG4B5fRW7hwYUrp2LFj\n8+bN+/zzzydOnPjWW28tXbq0qakp97ScBDQAACM6d+7cQw891N/f39nZuXnz5ptvvjn3ovwE\nNAAAI9q8eXN/f//s2bM/+uijsWOlY0o+BxoAgCvYs2dPSuntt99Wzxf5jQAAYERff/11Smnm\nzJmX/erw8PC/O6cmOIEGAGBEDXvd4BU4gYY6UKlUUkqlUin3EOC/oPqXSfUvFriqs2fP5p5Q\ncwQ01IEjR46klIrFYrFYzL0F+I8YGBjIPQHqlYCGOtDV1VWpVNy7C/wjSqVSsVhsb2/PPQTq\nlYCGOtDU1PTqq6/mXgH8dxSLRd+Q839YvHhxb29vY/7DwUv5w5NTuVy++CMAQC07e/bs7t27\nc6+oCQI6p08++eTijwAAtenUqVN79+597LHHjh07lntLTfAKR06dnZ3btm3r7OzMPQQAYEQ3\n3nhj7gm1RUDnVL3Rx70+AEAtu/jSc6FQyLukRniFAwAAApx9AkBjcTcTo1Qul/v6+np6elpa\nWnJvqS0CGgAai7uZCGlqatq0aVPuFbVFQANAY3E3E6NUPYHesGFD7iE1R0ADQGNxNxOjt3Dh\nwtwTapFvPQEAIEBAAwBAgIAGAIAAAQ0AAAECGgAAAnwKBwAAo3LxTu8G5wQaAAACBDQAAAQI\naAAARnT8+PHnnntu0qRJzc3Nt99++7x587766qvcozLzDjQAAJd35syZjo6OwcHB6i+PHj16\n9OjRDz/8cPfu3XPnzs27LSMn0AAAXF6xWBwcHJwyZcqXX3557ty5b775Zs6cOX/++WeD3wYv\noAEAuLxdu3allN5555177733uuuumz59+pYtW1JKAwMDuaflJKABALi8o0ePppTuueeei0/K\n5XJK6aabbsq2qQZ4BxoAgMs7c+bMpb/88ccfX3zxxZTSokWLMi2qCQI6p0qlklIqlUq5hwAA\nXEZzc/PcuXOvueaalFKhUKg+XLJkSYO/A52Gyef111/P/d8fAOBKPv3002q3XHwyZsyYZ599\n9vz583k7KiMn0Dl1dXVVKpW2trYxY7yMDgDUnObm5gceeKD680qlcvLkyVKp9NJLL/X29ra2\ntq5ZsybvvFwKw+40BwBg1A4cODBr1qzJkyd///33ubfk4eATAIDLa2lpKRQKJ06cuPTh9OnT\nU0rHjx/PNCo/AQ0AwOW1tbWllPbt23fpwy+++CKlNGXKlCyTaoFXOAAAIMAJNAAABAhoAAAI\nENAAABAgoAEAIEBAAwBAgIAGAIAAAQ0AAAECGgAAAgQ0AAAECGgAAAgQ0AAAECCgAQAgQEAD\nAECAgAYAgAABDQAAAQIaAAACBDQAAAQIaAAACBDQAAAQIKABACBAQAMAQICABgCAAAENAAAB\nAhoAAAIENAAABAhoAAAIENAAABAgoAEAIEBAAwBAgIAGAIAAAQ0AAAECGgAAAgQ0AAAECGgA\nAAgQ0AAAECCgAQAgQEADAECAgAYAgAABDQAAAQIaAAACBDQAAAQIaAAACBDQAAAQIKABACBA\nQAMAQICABgCAAAENAAABAhoAAAIENAAABAhoAAAIENAAABAgoAEAIEBAAwBAgIAGAIAAAQ0A\nAAECGgAAAgQ0AAAECGgAAAgQ0AAAECCgAQAgQEADAECAgAYAgAABDQAAAQIaAAACBDQAAAQI\naAAACBDQAAAQIKABACBAQAMAQICABgCAAAENAAABAhoAAAIENAAABAhoAAAIENAAABAgoAEA\nIEBAAwBAgIAGAIAAAQ0AAAECGgAAAgQ0AAAECGgAAAgQ0AAAECCgAQAgQEADAECAgAYAgAAB\nDQAAAQIaAAACBDQAAAQIaAAACBDQAAAQIKABACBAQAMAQICABgCAAAENAAABAhoAAAIENAAA\nBAhoAAAIENAAABAgoAEAIEBAAwBAgIAGAIAAAQ0AAAECGgAAAgQ0AAAECGgAAAgQ0AAAECCg\nAQAgQEADAECAgAYAgAABDQAAAQIaAAACBDQAAAQIaAAACBDQAAAQIKABACBAQAMAQICABgCA\nAAENAAABAhoAAAL+B4jjNYKvuKoiAAAAAElFTkSuQmCC", "text/plain": [ "plot without title" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# flatten list\n", "x2 = paste0(lapply(T, function(y) paste0(\"(\", paste0(y, collapse = \",\"), \")\")), collapse = \",\")\n", "\n", "# remove unwanted characters\n", "x2 = gsub('\\\"|c|list| ', \"\", x2)\n", "x2 = paste0(\"(\", x2, \");\")\n", "\n", "# remove brackets from single term list object\n", "x3 = str_replace_all(x2, \"\\\\([a-z]*\\\\)\", function(x) gsub(\"^\\\\(|\\\\)$\", \"\", x))\n", "\n", "# plot\n", "plot(read.tree(text = x3), color=\"blue\")" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Once the tree $T$ is computed, one can compute the code $C_{i}$\n", "associated to each symbol $i$. This requires to perform a deep first\n", "search in the tree and stop at each node." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "codes = list()\n", "c = compute_huffcode(h)\n", "for (i in (1:length(h)))\n", "{\n", " codes[[toString(i)]] = c[i]\n", "}" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Display the code." ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1] \"Code of token 1 = 100\"\n", "[1] \"Code of token 2 = 110\"\n", "[1] \"Code of token 3 = 0\"\n", "[1] \"Code of token 4 = 101\"\n", "[1] \"Code of token 5 = 111\"\n" ] } ], "source": [ "for (e in (1:length(codes)))\n", "{\n", " print(paste(\"Code of token\", e, \"=\", codes[[toString(e)]]))\n", "}" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "We draw a vector $x$ according to the distribution $h$.\n", "\n", "Size of the signal." ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "n = 1024" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Randomization." ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "rand_discr = function (p, m)\n", "{\n", " # rand_discr - discrete random generator \n", " \n", " # y = rand_discr(p, n);\n", " \n", " # y is a random vector of length n drawn from \n", " # a variable X such that\n", " # p(i) = Prob( X=i )\n", " p = p/sum(p)\n", " n = length(p)\n", " coin = runif(m, 0, 1)\n", " cumprob = c(0,cumsum(p))\n", " sample = matrix(0, nrow=1, ncol=m)\n", "\n", " for (j in (1:n))\n", " {\n", " ind = c((coin > cumprob[j]) & (coin <= cumprob[j+1]))\n", " sample[ind] = j\n", " }\n", " return (sample)\n", "}\n", "\n", "x = rand_discr(h, n)" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "__Exercise 1__\n", "\n", "Implement the coding of the vector $x$ to obtain a binary vector $y$, which corresponds to replacing each sybmol $x(i)$ by the code $C_{x(i)}$." ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "source(\"nt_solutions/coding_2_entropic/exo1.R\")" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "## Insert your code here." ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Compare the length of the code with the entropy bound." ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1] \"Entropy bound = 2197.95388894312\"\n", "[1] \"Huffman code = 2256\"\n" ] } ], "source": [ "e = - sum(h*log2(c(max(h[1],1e-20),max(h[2],1e-20),max(h[3],1e-20),max(h[4],1e-20),max(h[5],1e-20))))\n", "print(paste(\"Entropy bound = \", n*e))\n", "print(paste(\"Huffman code = \", nchar(y)))" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Decoding is more complicated, since it requires to iteratively parse the tree $T$." ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Initial empty decoded stream." ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "x1 = c()" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Perform decoding." ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "T0 = K\n", "for (e in strsplit(y,split=''))\n", "{\n", " if (e == '0')\n", " {\n", " T0 = T0[[1]]\n", " } \n", " else\n", " {\n", " T0 = T0[[1]][[2]]\n", " }\n", " if (typeof(T0) == 'character')\n", " {\n", " i = i+1\n", " x1 = c(x1,T0)\n", " T0 = T\n", " }\n", "}" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "We test if the decoding is correct." ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1] \"Error (should be zero) : 0\"\n" ] } ], "source": [ "err = norm(x - as.double(x1))\n", "print(paste(\"Error (should be zero) : \", err))" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Huffman Block Coding\n", "--------------------\n", "A Huffman coder is inefficient because it can distribute only an integer\n", "number of bit per symbol. In particular, distribution where one of the\n", "symbol has a large probability are not well coded using a Huffman code.\n", "This can be aleviated by replacing the set of $m$ symbols by $m^q$\n", "symbols obtained by packing the symbols by blocks of $q$ (here we use $m=2$ for a binary alphabet). This breaks\n", "symbols with large probability into many symbols with smaller proablity,\n", "thus approaching the Shannon entropy bound.\n", "\n", "\n", "Generate a binary vector with a high probability of having 1, so that the\n", "Huffman code is not very efficient (far from Shanon bound).\n", "\n", "Proability of having 0." ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "t = .12" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Probability distriution." ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "h = c(t, 1-t)" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Generate signal." ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "n = 4096 * 2\n", "x = (runif(n, 0, 1) >t) +1" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "For block of length $q=3$, create a new vector by coding each block\n", "with an integer in $\\{1,...,m^q=2^3\\}$. The new length of the vector is\n", "$n_1/q$ where $n_1=\\lceil n/q\\rceil q$.\n", "\n", "Block size." ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "q = 3" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Maximum token value." ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "m = 2" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "New size." ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "n1 = (floor(n/q)+1)*q" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "New vector." ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "x1 = matrix(0, nrow=1, ncol=n1)\n", "x1[1:length(x)] = x\n", "x1[length(x):length(x1)] = 1\n", "x1 = x1 - 1\n", "x2 = c()\n", "\n", "for (i in seq(1,n1,by=q))\n", "{\n", " mult = m**c(1:q-1)\n", " x2 = c(x2, sum(x1[i:(i+q)]*mult))\n", "}" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "We generate the probability table $H$ of $x_1$ that represents the probability\n", "of each new block symbols in $\\{1,...,m^q\\}$." ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "H = h\n", "for (i in (1:(q-1)))\n", "{\n", " Hold = H\n", " H = c()\n", " for (j in (1:length(h)))\n", " {\n", " H = c(H, h[j]*Hold)\n", " }\n", "}\n" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "A simpler way to compute this block-histogram is to use the Kronecker product." ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [ { "data": { "text/html": [ "
    \n", "\t
  1. 0.001728
    2. \n", "\t
  2. 0.012672
    3. \n", "\t
  3. 0.012672
    4. \n", "\t
  4. 0.092928
    5. \n", "\t
  5. 0.012672
    6. \n", "\t
  6. 0.092928
    7. \n", "\t
  7. 0.092928
    8. \n", "\t
  8. 0.681472
    9. \n", "
\n" ], "text/latex": [ "\\begin{enumerate*}\n", "\\item 0.001728\n", "\\item 0.012672\n", "\\item 0.012672\n", "\\item 0.092928\n", "\\item 0.012672\n", "\\item 0.092928\n", "\\item 0.092928\n", "\\item 0.681472\n", "\\end{enumerate*}\n" ], "text/markdown": [ "1. 0.001728\n", "2. 0.012672\n", "3. 0.012672\n", "4. 0.092928\n", "5. 0.012672\n", "6. 0.092928\n", "7. 0.092928\n", "8. 0.681472\n", "\n", "\n" ], "text/plain": [ "[1] 0.001728 0.012672 0.012672 0.092928 0.012672 0.092928 0.092928 0.681472" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "H = h\n", "for (i in (1:(q-1)))\n", "{\n", " H = kronecker(H,h)\n", "}\n", "H" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "__Exercise 2__\n", "\n", "For various values of block size $k$, Perform the Huffman coding and compute the length of the code.\n", "Compare with the entropy lower bound." ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1] \"Entropy Bound = 0.529360865287364\"\n", "[1] \"---\"\n", "[1] \"Huffman(block size = 2 = 0.1458740234375\"\n", "[1] \"Huffman(block size = 3 = 0.0238037109375\"\n", "[1] \"Huffman(block size = 4 = 0.005615234375\"\n", "[1] \"Huffman(block size = 5 = 0\"\n", "[1] \"Huffman(block size = 6 = 0\"\n", "[1] \"Huffman(block size = 7 = 0\"\n", "[1] \"Huffman(block size = 8 = 0\"\n", "[1] \"Huffman(block size = 9 = 0\"\n", "[1] \"Huffman(block size = 10 = 0\"\n", "[1] \"Huffman(block size = 11 = 0\"\n" ] }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeAAAAHgCAIAAADytinCAAAABmJLR0QA/wD/AP+gvaeTAAAg\nAElEQVR4nO3daVwT1/4G8F8IAgk7gkoVV1A0uFSttRUrKFCtS0H/Itpbcem1XpdrtVTbWq9L\nta1Sl2pVXFqxLlRQES16K4u4a61V3AFxRVxQkCWEPf8X0+amSQgTSDIT8nxf+IHDyeTJkPw4\nzpw5I5DL5QQAAPxjwXUAAADQDAUaAICnUKABAHgKBRoAgKdQoAEAeAoFGgCAp1CgAQB4CgUa\nAICnUKABAHgKBRoAgKdQoAEAeAoFGgCAp1CgAQB4CgUaAICnUKABAHgKBRoAgKdQoAEAeAoF\nGgCAp1CgAQB4CgUaAICnUKABAHgKBRoAgKdQoAEAeAoFGgCAp1CgAQB4CgUaAICnUKABAHgK\nBRoAgKdQoAEAeAoFGgCAp1CgAQB4CgUaAICnUKABAHgKBRoAgKdQoAEAeAoFGgCAp1CgAQB4\nCgUaAICnUKABAHjKXAq0QCAQCAQN76PRhQsX3nrrLTs7O+WHa2zkP5Y7od77Sr8xuKISj+dp\nG8hE38mNg0Aul3OdwRiY95b2F8umj0Zdu3a9du0a87Xi4Rob+Y/lTqj3vtJvDK6oxON52gYy\n0Xdy42AuI2iDunnzJhGdO3eupqZGeyM0SnK5vBFXLryTOYQRtG59tDywurrawsJCeyP/YQTN\nBs/j6ZeJvpMbB+zxWtV2YFG5XflroVDIfK2xUbn91KlTQ4cOdXV1dXJy8vX1TUxMJKKKiorl\ny5f7+PiIRCJXV9cRI0ZcvnxZ/dlzcnI+//zzbt26OTo6Ojs7d+/efd68eTk5ORoTHjt2LDAw\n0NHR0dHRceDAgadPn2b/8nfs2NG7d2+xWOzm5jZy5Mg//vijzodUVlZ+9913r7/+uqOjo62t\nbffu3ZcuXVpcXKzSrays7JtvvunWrZtYLLa3t+/bt29UVFR1dbX2jVdVVQ0dOlQgEAQGBpaX\nl2vpyXL7LNPev38/PDzc3d1dJBJJJJLvvvtOvS7Xdki6zv3/+PHjyZMnN2/e3M7Ork+fPrt3\n71bfmkaKPsnJyf7+/sybITg4OD09Xb2zXC7/6aef/Pz8XFxcbG1te/To8fXXX5eUlNS2zejo\naG9vb+atq/GdrNMOVN8s8fKzwPJtw3Jn6o3cPLB5sSp9anuIcrvG/VnbTma+3rp1q8pIRCAQ\n7Nq1y9fXV+VRYrH45s2byk998eJFBwcH9e3b2dmdOXNGJeGWLVtUPlFWVlZXrlxhsxNmzJih\n8hRNmjTZv3+/lp3z4sWL1157TT1bhw4dMjIyFN2ePXvWvXt39W7Dhw+vrq6ubfs1NTXjxo0j\nojfffLOkpERLfpbbZ5n2+vXrzs7OKn2mTZumEk/jt3Xu/1u3bjVv3lxl45999pn6vq3t17R+\n/XqVp7C2tj58+LByz9LS0iFDhqi/0rZt2167dk19m4sXL1bvrKDrDtS4WTn/Pgss3zbsd6a+\noEDX2qe2h6i3a+xZWzcLC4u33377woULMpnsypUrffv2Vfya//GPf6Snp0ul0suXL/fr14+I\nwsPDlbcQFBRERK+99trJkycLCwuLi4svXLjwzjvvEFHfvn1VnkgoFAYHB9+4caOiouLy5cud\nOnVS32Btr46IfH19z507V1ZWlpWVNXr0aCKyt7fPycmp7dUNHjyYiLy9vRMTE4uKioqLi9PS\n0vr3709EXl5eUqlULpfX1NQEBAQQUe/evU+cOCGVSu/du7ds2TJLS0si2rFjR217j/mD0aNH\nj4KCAi3h2W+fTdrq6upu3boxu+LChQtlZWU3btxg9rb2twqb/V9ZWcls/J133klPT5fJZNeu\nXVP+8LP5NQmFwiFDhqSnp5eWll69evXdd98lImdn5ydPnih6/uMf/yCizp07Hzx4sLi4uKio\nSPFK27Rpw7xS5W1aWFjMmjXrwYMHNTU1tf2uWe5ALZvl1WeB/duG/c7UF/Mq0GyoPKS2TWlv\n0dJt0KBByn+TFf93+/DDD5U737hxg/mtKzfa29sTUWZmpnLjs2fPiMja2lrliYKCgpSf6Jdf\nfiGi9u3ba95Bf39sz549y8vLFY2KarJgwQKNr+7XX38lIhcXF+XSIJfLy8vLX331VSJau3at\nXC7/73//S0QtW7YsLCxU7vbJJ58Q0dtvv60Sg/l64cKFRNSpU6enT59qD89y+yzTxsfHMzWo\ntLRUeVf06dNH+1uFzf6PiYkhou7du1dUVChvXDEs1f5KmT4+Pj7KD6+qqmIevnjxYqblzJkz\nzK57+fKlyivt1asXEX3//fcq2xw1apTG51JuYbkDtWyWV58Flm8bnXamvqBAq1J5SG2b0t6i\npduRI0eUG6VSKdN+9epV5faqqioisrGxqfOlZWRkaEx+4sQJ5W75+flEZGdnp31rzGPj4uJU\n2rdu3UpEb7zxhsZX9/777xPR3Llz1Te4Y8cO5qOo6Pb111+r9MnKyiIiV1dXlRhyuXzt2rXM\nh/Phw4fak7PfPsu0Y8eOJaIff/xRpU9sbKz2twqb/T9q1CiNG9+zZ09tbzxlTJ/NmzertDNH\nsd98803m20mTJhHRvn371LcQFxdHRO+8847KNs+dO6fxuZRbWO5ALZvl1WeB5dtGp52pL+ZV\noHXqY6ACnZeXp7FnWVkZy8wPHjzYs2fP119//c9//jMgIMDW1lZjcpW/84o5UuobVH/S3Nxc\nlXbmrd+0aVON2by8vIjot99+05iWiJo1ayaXyzt27EhEly5d0p5Bsf2dO3cyhw7ZPIT99lmm\n7dChAxHduXNHpY/iNJRKWpVvte//du3akdoAUC6XP3z4kP2vSeWwrCK/i4sL8y2zQ1SSMJ48\neUJErVq1Utmm+iF+9Twsd6CWzfLqs8DybaPTztQXFOha+9T2EPV2jT1r61ZVVcUym3r76dOn\ne/bsSX9X2/+4lf9Pp/2J1PtUVlaqtDOjG0tLS42bYj4Y6p83uVxeVlZGRE2aNJHL5XZ2dkT0\n4sUL7RkU27e0tGROIs2bN6/Oh7DfPsu0IpFIY7GoqKjQ/lZhs//FYjERFRUVqfRRTFDR/hKY\nPir/JVfkV/yaFAWrNsrDUvbvQ5Y7UMtmefVZ0Oltw3Jn6oul9qcEFeqziHTFTDOqh+Tk5MGD\nB1dXV9vZ2Q0aNKhXr16dO3fu1atXu3btNM7Kasis1fLycuYMiQLzwbOxsdHYn6lZTEVTUVhY\nqHggs5E63+gK1tbWiYmJkydPXr169QcffODp6am9P8vts0zL/M+6oqLC2tpauQ/TXift+5/J\nwJRpZdpnEKpQfzgzNlTsgcrKSu1b0OnpFFjuwDrx5LPA8m1joJ1ZB72XfH5i82JV+mh8yO3b\nt9XbNfZk2Y19+5tvvklEYWFhKsOuOgd0dbar98nOzlZpv3r1KhF17NhR46aY6WLXr19X3+C5\nc+eIqHPnznK53M3NTePGa4uRnJwsl8v37t1LRMOGDavzUSy3zzIt0+3GjRsqfdTfA/XY/8zs\nvefPn6v0Ub6oWgumj8o5Ovlfh007dOjAfOvu7k5EdZ5cZR+bwXIHatksrz4LLN82Ou1MfcGF\nKrVq0qQJ/fXXVUGnaz30i7lU5Pvvv2fOXysoPtJ6dPLkSZWWpKQkItI49ZWImDkeTB8V+/fv\nJ6LXX3+diJippur78OrVqwKBoGXLlirtgwYNIqJRo0b179//l19+OXLkiPbYLLevU9qUlBSV\nPsePH9cegw3mAPfvv/+u0s7MKGDp/PnzKi1MNmZSgeILNhcZ6YTlDjQc/X4WWL5tDLQz62DM\nvwYcYvNiVfq88sorRHTy5ElFS1VVVe/evdU3pXHjLLuxb2fei1lZWcp9KioqmAmhpNcRdM+e\nPZUPQ1dUVHh7exPRgQMHNG4qKiqKiFq3bl1cXKy8tfz8fGa0lZSUJJfLN27cyGxc5eAjcxHK\nuHHjaot64cIFgUDQsWNH5Vll6lhun2XaDRs2EFHnzp2Vn7SsrKxLly7adzib/R8REUFq/y0o\nLCxUlAMtL1OxqYEDBypmK8vl8tLSUmaGb3R0NNOyc+dOIurXr59yNwYzPcbT01On2AyWO1DL\nZnn1WWD5ttFpZ+oLCnStfUJDQ4moe/fu6enpZWVl165dCw4OtrW1VazDoH3j6o0NfFMylyH0\n7t37/PnzMpksJycnOjpaIpEIhUIrKysievToUf2eSL2PQCAYNmwY88IzMjKCg4OJ6NVXX1Wc\nbFHZVGlpKXOAuE+fPqmpqSUlJcXFxampqcygw9/fX9GNGTmOHDny+vXrZWVlmZmZH374IfOM\n6heAKQd77733iGjFihVawrPcPsu0Uqm0bdu2RDR06NArV66Ul5ffuHEjKCiIOaekpQqw2f9Z\nWVnMoe2pU6fm5ORIpdK0tLSePXsqDsuy+TURUVhY2M2bN8vKyi5duvTWW28RUbt27RR/URSz\ntkeOHHnx4sWysrK8vLxjx44NHTqUefgPP/ygU2yddqCWzfLqs8DybaPTztQXFOha+/zxxx/M\nUQ5lu3bt4qpA37x508nJSSWPra3t7t27mUutFJ11fSL1PosWLVJ5oqZNmypfwqu+qStXrqhf\nuExE3t7ejx8/VnS7fPmyi4uLerdly5Zpj/rgwQORSGRvb6+8NXUst88y7W+//abyn2gLCwtm\nrjE1rEDL5fLt27ernyVjrsoRCoVaXqNiU4qLzhUcHR3T09OVe+bm5mq8iFkgEMyZM0dLPO3t\nLHdgbQ/X6bnU2/X+WWD5tmG/M/UFBVpbnzNnzgQEBDg6OtrY2PTt2/fgwYMau7F8CzbwTSmX\nyzMzM0ePHu3i4mJjY+Pl5TV79ux79+7J5fJff/3V1dW1RYsW9XsijX22bt3atWtXGxsbd3f3\niRMnqlwnonFTz549mzNnjqenp7W1taOjY+/evb/++mvly/AYOTk5U6ZMadWqVZMmTVxdXYcP\nH56SksIm6vz584lo/Pjx2l8Cm+2zT5uZmTlq1ChHR0d7e3s/Pz/mP+8q8bR/q6X93LlzQ4cO\ndXR0FIlE3bp127x5c0FBARE5OTlpf43MpmpqatatW9elSxcbG5tmzZqFh4erz9qWy+Uymezb\nb7999dVXxWKxnZ2dp6fnhAkTlP+/omtsBssdyPLToWu73j8LLN82LHemvpjLcqMAJuHChQt9\n+vTp2bPnxYsXtXQzq/VOzRlmcQBwwM3NTSAQXLlyRaX9hx9+ICI/Pz8OMgH/oEADcIBZd23s\n2LH//e9/8/PzmbPQ06dP37Rpk1gsnj59OtcBgRdwiAOAA7m5ub6+vnfv3lVpt7a2jo6ODgsL\n0/5wHOIwEyjQANwoLi7esmXLzz//fOfOndLSUnd394EDB/773//u2rVrnY9FgTYTKNAAADyF\nY9AAADyFAg0AwFMo0AAAPIUCDQDAUyjQAAA8hQINAMBTKNAAADyFAg0AwFMo0AAAPIUCDQDA\nUyjQAAA8hQINAMBTKNAAADxlqeVnzJKGLGFVPAAA/cIIGgCAp7QVaOWbyxYWFo4aNap58+bb\ntm17+PBhWVnZvXv31q1b17x583nz5lVXVxstMQCAmdB2iEPZtGnT9u3bd/To0cDAQKalTZs2\nM2bM6NChwzvvvGNhYfHVV18ZLCQAgDlie0cVR0fHoqKioqIie3t75fbCwkInJ6dmzZo9ffrU\nMAkBAMwU22PQTZo0IaLU1FSV9lOnThFRWVmZfmMBAADbAj1q1CgimjRp0saNGx8+fFheXp6T\nk7Np06b333+fiEJCQgyYEQDALLE9xFFYWDh8+PCTJ0+q/6hnz55JSUkuLi76zgYAYNZ0uKt3\nTU3Nzz//vHPnzt9//z0/P9/W1lYikYwZM+Zf//qXlZWVQVMCAJghHQo0AAAYEy5UAQDgKbYF\nWi6Xr1y5smvXrnZ2dgJNDJoSAMAMsb1QJTIyct68eQaNAgAAytiOoKOioohoxIgRd+7cqa6u\nlqsxZEgAAHPE9iShtbV1RUXFw4cPW7VqZehMAABA7EfQ7du3JyJMdgYAMBq2BfqTTz4hon37\n9hkyDAAA/A/bk4STJk16/PjxjBkzampq3n33XUdHR8zcAAAwKLbHoOssxzhPCACgX7hQBQCA\np3Cpd90KCwu3b98uk8m4DgIABiESicLDwx0dHbkOoortMWhztmvXrlmzZnGdAgAMyNLSctq0\naVynUMW2QJvzMejKykoi+uGHH7p37851FgDQs/T09MmTJzMfc75p6AhaIBAIhUJzuGlsp06d\nevXqxXUKANAzPt8QSofFkpTJZLLMzMzly5c7ODgsXLjQHAo0AICR1XMEbWNj4+XlNXfu3BYt\nWoSHh4vF4jlz5ug3GQCAmWvoNDvmboTr1q3TRxgAAPifhhbogoICIsrNzdVHGAAA+J8GFegn\nT54wRzY8PDz0lAcAAP6kn2l2U6dO1UcYAAD4nwaNoK2trbt167Zt27aIiAh9BTJRxcUUEEAp\nKVznAIBGhO0IuhFfh6IXpaWUkkKenjRoENdRAKCxwGJJ+tG8Obm60vXrXOcAgEZEhwJdU1Oz\nadOmfv36OTo6WllZeXh4hIaGpqWlGSybiZFIUKABQJ90uJIwNDR06tSpZ86cKSoqqqyszMnJ\niYuL8/f3x0JCDImECgoIEw4BQF/YFujNmzfv27fPxcUlOjr62bNnMpnsxo0bCxcuFIlEa9eu\n3bFjh0FTKnvw4MGSJUv8/f1btmwpEoksLS0dHBy8vb1DQ0O3bdsmlUqNlkSFREJEdO0aV88P\nAI2OnB1mnaC4uDiV9p07dxKRr68vy+000IYNG6ytrbW8nJYtWx4+fFi/T7pmzRoiOnXqlPZu\nx4/LieSrVun3yQHAsE6dOkVEa9as4TqIBmxH0NevXyeiwYMHq7SPGDGCiK5evarzXwbdJSYm\nTps2rbKyMiwsbNeuXVlZWQUFBVVVVVKpNDs7Oz4+PiQk5NGjR8HBwWfPnjVCHhU+PkSEw9AA\noDdsC7RQKCSikpISlXbmPiPGWa8vMjKSiFavXh0TEzNu3DhPT08nJyehUCgWi9u3bx8cHLx/\n//65c+dWVFQsWbLECHlUuLhQixY4xAEAesO2QDNr1cfHx6u0JyQkEJGXl5d+Y2l06dIlIpow\nYYKWPswlM7/99psR8qhjJnJgyjgA6AXbAj1z5kwimjNnztKlS2/fvl1WVvbw4cOVK1d+9NFH\nRBQeHm7AjH+xsLAgooqKCi19mJE+VzdH8PGhkhJ68ICTJweAxoZtgQ4LC/v444/LysoWLFjg\n5eUlEolat24dERFRWlo6bNgwpkwbWs+ePYloxYoVWvqsWrVK0dP4mIkcOAwNAHqhw4Uq3377\nbVJSUkhIiLu7OzO5zdfXd8uWLQkJCZaWxrj57IIFC4RCYWRkZGBg4O7duzMzM6VSaU1NTXFx\n8d27d2NjY0eMGLFs2TKBQPD5558bIY86zLQDAD3SrbAGBAQEBAQYKEqd/Pz89u7dO2XKlOTk\n5OTkZI197OzsoqKigoKCjJyN4eNDAgFG0ACgH8YY+epRcHBwUFBQTExMSkrKxYsXnz9/XlhY\naGVl5ebm1qVLl8DAwPDw8KZNm3IVz8GBWrZEgQYA/TCxAk1EYrF48uTJkydP5jqIZj4+dPw4\nVVeTUMh1FAAwcTocgy4oKJg/f36PHj3s7e2trKzc3d2HDh36888/yzGtTIlEQjIZ3b3LdQ4A\nMH1sR9APHz709fV9oDSD7MmTJ4cPHz58+PDmzZsTEhLs7e0Nk5AV5oYvfPhToZjI4enJdRQA\nMHFsR9AREREPHjxo3rz5jz/+mJubW1ZWdu/evfXr17u4uBw7duyzzz4zaEoTggu+AUBf2Bbo\nX3/9lYh+/vnniRMnuru7W1tbt2nTZtq0aTExMUQUFxdnwIx/EdROvYMR8mjUpQtZWKBAA4Ae\n6HZHFWZNO2X9+vUjovLycr0lqp2zs7MRnqWBbG2pTRtMhQYAPWBboMeNG0dEKWp3Rf3999+J\naPTo0fqNpVF6evqAAQOIyMnJac+ePcqL8jEd1Fs4IZFQRgZVVXEYAQAaA7YFetWqVf/3f/83\nZcqU2NhYZpHPp0+f7ty5c9y4cRMnTly7dq1BUzI8PDxSU1OXLl1aUlIyZsyYiRMnqq+uxwc+\nPlReTrdvc50DAEyctlkcGo/kjhkzRqVl27Zt27ZtM86g1cLCYv78+YGBgePGjYuOjj558uTu\n3bv79OljhKdmT3HBt7c311EAwJSZ5F29+/Tpc+nSpfHjx2dnZ/fr1++rr77iOtHfYMkkANAL\nbQVap1uzGC0xw97efvv27TExMba2tvPnzzfys2vXuTMJhSjQANBQJjmCVggLC0tPT/f19eU6\nyN/Y2FCHDijQANBQprcWh4o2bdqcPHmy3g+vrq4+fPiw9lt2MXdy0ekmABIJHTpE5eWk9Q63\nAADamHyBbqBjx44x972t0+7du/38/Fhu1seH4uMpM5O6dq1/NgAwc+ZeoP39/Q8ePKh9BL1h\nw4a0tLRWrVqx36ziPCEKNADUWyMs0DotnCQUCocPH669z+HDh+mvOyKyhIkcANBwpn2SkLc6\ndSIrK1zwDQAN0ghH0HxYdLRJE/L0xAgaABqE7Qh6x44dhYWFBo3SyPj40J07JJNxnQMATBbb\nAj1+/PhmzZq98847P/zww/Pnzw2aqXGQSKi6mm7d4joHAJgstgV6+PDhAoHgyJEjH3zwQYsW\nLfz9/detW5eTk2PQcBo9ePBgyZIl/v7+LVu2FIlElpaWDg4O3t7eoaGh27Ztk0qlxo+kkWJF\nDgCA+mFboA8ePJiXl7d79+6RI0daW1unpaX9+9//bt26db9+/b7//vvS0lKDplTYuHFjx44d\nFy5cmJaWxtzYpbq6uri4OCMjIy4ubtKkSZ06dTpy5IhxwmiHW6sAQAPpMIvD3t5+7Nix+/bt\ny8vLi4uLGzNmjK2t7ZkzZ2bOnNm+ffvVq1cbetn+xMTEadOmVVZWhoWF7dq1Kysri1n4VCqV\nZmdnx8fHh4SEPHr0KDg4+OzZswZNwkaHDmRtjQINAA2g04pIKgoKCiZOnKjYVNu2bQ8ePNiQ\nDWrHrNb/3Xffaekzd+5cIho8eLAen3fChAlE9OWXX+r6wO7d5W3b6jEIAOjfqVOniGjNmjVc\nB9GgPvOgi4uLf/7559DQUA8Pj23btjGNr776an5+/ogRI6Kiohr8V0MzZk0MplzWJiIigoh+\n++03A2XQiURC9+9TcTHXOQDANOlQoF+8eLFt27bhw4e7ubmNHTs2Li6utLS0X79+K1euvHfv\n3h9//MEU65UrVxoqq4UFEVVUVGjpIxQKSceFjQxHIiG5nG7e5DoHAJgmtheqDBo06MSJE1VV\nVUTUpEmTwMDAkSNHhoSENG/eXNGHWXXo/v37hghKRD179kxNTV2xYsWKFStq67Nq1Sqmp4Ey\n6ERxnpBnt3wBANPAtkCnpqaKRKKhQ4eOHDlyxIgRTk5O6n3y8/OJyMHBQZ8BlSxYsOD48eOR\nkZGXLl2aOHFi7969mZl2Uqn0+fPnFy5c2Llz56FDhwQCweeff26gDDrBihwA0BBsC/TevXsH\nDx5sa2urpU+zZs3khrzM2s/Pb+/evVOmTElOTk5OTtbYx87OLioqKigoyHAx2GvXjmxtMRUa\nAOqJbYEeNWqUQXOwFBwcHBQUFBMTk5KScvHixefPnxcWFlpZWbm5uXXp0iUwMDA8PLxp06Zc\nx/yThQV5e2MEDQD1ZHqLJYnF4smTJ0+ePJnrIKz4+NDFi/TyJWk6JgQAoI0OszgKCwv/85//\n9OjRw87OzsrKqkWLFkFBQZs2bdI+rcLM4TA0ANQb2xH0o0eP+vfvf/fuXUXL06dPk5KSkpKS\nfvzxx6NHjzo6OhomYd10WqHfyBQFul8/rqMAgKlhO4L++OOP796927Jly127dj179qysrOzu\n3burV692dHT87bffFi5caNCUpgsrcgBAvbEt0Mxtn/bs2TNu3Dg3Nzdra+u2bdt+9NFH0dHR\nRLR//37DRTRpHh7k6IgCDQD1wbZAi8ViIurVq5dKe2BgIBEVFRXpN1ajIRBQ586YaQcA9cG2\nQDOzJtTXuLh69SoRvfvuu/qN1ZhIJPT0KeXlcZ0DAEwN2wK9ePHi6dOnh4WF/fjjjzk5OZWV\nlS9fvjxw4MDYsWNHjhz5/fffGzSldsyyTxwG0I45T3jjBtc5AMDUsJ3F0aRJE+YL9QnI9+7d\nUzkGzedyaXzMecJr12jAAK6jAIBJqc9yo6ATTIUGgPphO4LGoLjeXnmFXFxQoAFAZxhBG4NE\ngokcAKAzHQp0TU3Npk2b+vXr5+joaGVl5eHhERoampaWZrBsjYdEQvn59OQJ1zkAwKSwLdBy\nuTw0NHTq1KlnzpwpKiqqrKzMycmJi4vz9/efNWuWQSM2AsxhaAyiAUAnbAv05s2b9+3b5+Li\nEh0d/ezZM5lMduPGjYULF4pEorVr1+7YscOgKU0dLvgGgHpgW6C3bNlCRJs2bQoPD3dzc7Ox\nsencufOiRYuY9s2bNxswo+lDgQaAemBboK9fv05EgwcPVmln7kPIXE8ItXF1pWbNcIgDAHTD\ntkAzd8suKSlRaZfJZERUVlam31iNj0RC168TJisCAHtsC3T37t2JKD4+XqU9ISGBiLy8vPQb\nq/Hx8aGiIsrJ4ToHAJgOtgV65syZRDRnzpylS5fevn27rKzs4cOHK1eu/Oijj4goPDzcgBkb\nBVxPCAC6Ylugw8LCPv7447KysgULFnh5eYlEotatW0dERJSWlg4bNowp06AFZtoBgK50uFDl\n22+/TUpKCgkJcXd3t7S0dHBw8PX13bJlS0JCgqWl6d181sgwkQMAdKVbYQ0ICAgICDBQlMbN\nyYleeQUFGgB0wHYEbWNjIxAIKisrDZqmcfPxoevXqaaG6xwAYCLYFujg4GAiOnPmjCHDNHIS\nCZWW0r17XOcAABPBtkBv3br1/fffHz9+fEJCQnFxsUEzNVaYyAEAOmF7DC34+p0AACAASURB\nVNre3p75ghlKq8OC0XVSnCccPpzrKABgCrAetPFIJCQQYAQNAGzhjirGY2dHrVtjKjQAsIUR\ntFFJJHTrFlVXc50DAEwB2wItEAgEAoGuPwIVPj5UVkbZ2VznAABT0NAR9K1bt+ivte6gTrjg\nGwDYq7tAKw+QBWo6d+5MRG3btjVoykYDM+0AgD09HINu3br16tWrG74dc9ClCwmFKNAAwErd\nsziY+RvMIBpzORpIJKJ27VCgAYAVHe7qjeqsFxIJZWRQRQXXOQCA93Qo0CtXruzataudnZ36\nkWjM4mDPx4cqKykri+scAMB7bC9UiYyMnDdvnkGjmAnFeULmCwCA2rAdQUdFRRHRiBEj7ty5\nU11dLVdjyJCNCiZyAABLbEfQjx49IqL169e3atXKkHkav06dyNISU6EBoG5sR9Dt27cnIhcX\nF0OGMQvW1uTpiRE0ANSNbYH+5JNPiGjfvn2GDGMufHzo9m2SybjOAQD8xrZAT5o0aenSpTNm\nzNi+ffvLly95ctC5oqJi2bJl3t7e1tbWrq6uw4YN+/XXX7kOVTeJhKqrKTOT6xwAwG9sj0Er\nJtJNmDBBYwcjlGyVi2UqKyuHDBmSmprKfPvixYvExMTExMQZM2asW7fO0GEaQrEiR/fuXEcB\nAB4z4eVGV69enZqaamtru2XLlry8vNzc3MjISBsbm++//37nzp1cp9NGcWsVAAAtdLuSUAuD\nptQoOjqaiL755psPPvjA1dXV3d09IiJi+fLlRLR161bj52HPy4usrVGgAaAOJjyCzs7OJqLR\no0crN44aNYqI0tPTucnEjqUldeyImXYAUAdtBZrlNdxcXert5ORERA4ODsqNTZs2JaLy8nLj\n59GJREL37pFUynUOAOAx3UbQfFh2o7KykvmCGSz/9ttvyj89d+4cEXXo0MH4wXQikVBNDd28\nyXUOAOAx0zvEIRaLvby8hg4dWl5eLhAIIiIiFD+6devWrFmziGjkyJHcBWQF5wkBoE5sp9nx\nQUBAQEZGRk5Ozu3bt2/fvs00/v7774oOzO1dPDw8Zs+ezU1E1rAiBwDUyZQKdFJSEhHJZLKs\nrKxMJYoOrq6ugwcP/uqrr5jD03zWoQOJRDhPCADamFKBZohEom7dunXr1k39R3l5ecbPUz8W\nFuTtjRE0AGhjesegGw0fH3r4kAoLuc4BAHzVSAo0H6aX6EoiIbmcbtzgOgcA8FUjKdCmCOcJ\nAUC7uo9Bq49MuRqr1vm8yh14st6eFphpBwDamdII2tnZmesI+tSmDdnbo0ADQK20Feg6F0gy\n8mJJ6enpAwYMICInJ6c9e/aoP7tp3SNRIKDOnTHTDgBqZUojaA8Pj9TU1KVLl5aUlIwZM2bi\nxIklJSVch2oQiYQeP6YXL7jOAQC8ZEoFmogsLCzmz59/+vTpDh06REdH9+jRQ2UtDtPCnCfE\nRA4A0MjECjSjT58+ly5dGj9+fHZ2dr9+/b766iuuE9UTc54QRzkAQCOTLNBEZG9vv3379piY\nGFtb2/nz53Mdp54w0w4AtDDVAs0ICwtLT0/39fXlOkg9tWpFzs4o0ACgmemtxaGiTZs2J0+e\nrPfDq6urDx8+XFZWpqXPvXv3iKimpqbez6JFly44xAEAmpl8gW6gY8eOjRgxgk3Pu3fvGiKA\nREKnT9OzZ9SsmSE2DwAmrI4C/fTp03nz5h06dOjFX3PBpFLpvHnzYmNji4uL27ZtGxoa+umn\nn4pEIsNHNQh/f/+DBw9qH0Fv2LAhLS2tXbt2hgjAHIa+do0GDjTE5gHAhGkr0FKp1M/P79at\nW8qN77//fnx8PPP1rVu3lixZkpKSkpqaamVlZcCYumAu+GZ5rYpQKBw+fLj2PocPHyYiCwuD\nHK9XXPCNAg0AKrQVnfXr19+6datdu3ZXrlxhWv7444/4+HgHB4ejR4/KZLK0tLSWLVuePn16\n165dRknbCGEiBwDURluB3r9/PxGtWrWqa9euTMuOHTuI6NNPPw0MDLSxsRkwYMB3331HRD//\n/LPho7JlKpd6M5o3Jzc3nCcEAA20FegbN24QUb9+/RQthw4dIqLRo0crWgICAojo8uXLhgpo\nBjCRAwA0qvUYtGLpzmZq0wu8vLxUWp49e6bTkV9Q5uNDx4/To0fUsiXXUQCAT2odQcvlchsb\nGyLKz89nDhrk5OQQkbu7u/KicczsDhcXF6MdWHjw4MGSJUv8/f1btmwpEoksLS0dHBy8vb1D\nQ0O3bdsmlUqNkEG/cBgaADTSdojD09OTiC5cuMB8++uvv9Lfj3gQUWJiIhH5MHMRDG/jxo0d\nO3ZcuHBhWlpabm5uWVlZdXV1cXFxRkZGXFzcpEmTOnXqdOTIEeOE0RfFTDsAAGXaCvTIkSOJ\naM6cORkZGRkZGV9++SURjRkzhvnpixcv9uzZM3v2bOVGg0pMTJw2bVplZWVYWNiuXbuysrIK\nCgqqqqqkUml2dnZ8fHxISMijR4+Cg4PPnj1rhDz6wpyCxQgaAFRpWYO/qKioc+fOyp379OlT\nVVWlcjTjjTfeqKys1Gl1//phVuv/7rvvtPSZO3cuEQ0ePFiPzzthwgQi+vLLL/W4TRUtWshf\nf91wmweAWp06dYqI1qxZw3UQDbSNoO3t7U+cOBEeHu7g4GBvbx8WFvbLL78IhULmp7a2tl26\ndFm4cGFKSoqlpTEuGb906RIRMeWyNhEREURkcotE+/jQ9euEM6wAoKyOwurq6hodHR0dHa3+\nI+PfzYS5lq+iokJLH+bvR2VlpZEy6YlEQsnJ9OABtWnDdRQA4A1TWm60Z8+eRLRixQotfVat\nWqXoaUJwnhAA1NWnQAsEAsUsaWNasGCBUCiMjIwMDAzcvXt3ZmamVCqtqakpLi6+e/dubGzs\niBEjli1bJhAIPv/8c+PHawjFihwAAAqmtNyon5/f3r17p0yZkpycnJycrLGPnZ1dVFRUUFCQ\nkbM1kERCAgEKNAD8jSkVaCIKDg4OCgqKiYlJSUm5ePHi8+fPCwsLrays3NzcunTpEhgYGB4e\n3rRpU65j6szBgVq1wiEOAPgbEyvQRCQWiydPnjx58mSug+iZRELHj1N1Nf01TQYAzJ0pnSRs\n3Hx8SCYjw9y2BQBMUn0KNDODWu9R6o2rk5b6hYkcAKCijgL99OnTCRMmKB/VlUqlM2bMaNas\nmUgk6ty588KFC2UymYFDmgUsmQQAKhrhLa9MlERCFhYo0ADwP7jlFV+IxdS2LQo0APxPI7zl\nlemSSOjWLaqq4joHAPBDY7jlFd9OWtabREIVFZSVxXUOAOAH3PKKRxTnCf++yCsAmCnTu+VV\nI8asyIGZdgDAMLFbXjVu3t4kFOI8IQD8yZRuedXo2dhQhw4o0ADwJ23zoCMiIuLi4q5fv+7t\n7c209OnTJyQkhPna1dWV+eKNN96YMmWKQVOaDx8fOniQysvJ2prrKADANVO65ZU5kEioqooy\nM7nOAQA8YEq3vDIHihU5/pp6DgDmC6vZ8QturQIACijQ/NKxI1lZoUADABEKNN80aUJeXpgK\nDQBEKNA8JJHQnTtUWsp1DgDgGgo070gkVFNDf1/kFQDMEQo07+A8IQAw2BZoGxsbgUBQWVlp\n0DRAuLUKAPyFbYEODg4mojNnzhgyDBAReXqSSITzhADAukBv3br1/fffHz9+fEJCQnFxsUEz\nmTmhkDp2xAgaAOq6klDB3t6e+YIZSqvDWqN65ONDu3dTcTH9tdcBwBzhJCEfSSQkl9PNm1zn\nAABOsS3Q8roYNKW5UazIAQDmDCNoPsJMOwAgnQp0TU3Npk2b+vXr5+joaGVl5eHhERoampaW\nZrBs5qttW7K1RYEGMHc6HOIIDQ2dOnXqmTNnioqKKisrc3Jy4uLi/P39Z82aZdCIZsjCgjp3\nxiEOAHPHtkBv3rx53759Li4u0dHRz549k8lkN27cWLhwoUgkWrt27Y4dOwya0gxJJPToEeXn\nc50DALjDtkBv2bKFiDZt2hQeHu7m5mZjY9O5c+dFixYx7Zs3bzZgRrPEnCfERA4Ac8a2QF+/\nfp2IBg8erNI+YsQIIrp69ap+YwFznhBHOQDMGdsCzdyKUP02VzKZjIjKysr0GwuwIgcAsC3Q\n3bt3J6L4+HiV9oSEBCLy8vLSbyzw8CBHRxRoALPGtkDPnDmTiObMmbN06dLbt2+XlZU9fPhw\n5cqVH330ERGFh4cbMKNZEgioSxcUaACzxrZAh4WFffzxx2VlZQsWLPDy8hKJRK1bt46IiCgt\nLR02bBhTpkG/JBJ6+pTy8rjOAQAc0eFClW+//TYpKSkkJMTd3d3S0tLBwcHX13fLli0JCQmW\nlmwXXQL2cBgawMzpVlgDAgICAgIMFAVUKAq0nx/HSQCAE7ijCn9hRQ4AM4c7qvCXuzs1bYqp\n0ADmC3dU4bUuXVCgAcyX6d1R5cGDB9HR0ceOHcvMzMzPz6+srBSLxa+88kq3bt2GDBkSGhpq\na2trnCRG4ONDJ0/S48fk7s51FAAwOhObfbFx48bZs2eXl5crNxYXF2dkZGRkZMTFxS1YsGDL\nli1DhgzhKqF+Kc4TokADmCFTuqNKYmLitGnTKisrw8LCdu3alZWVVVBQUFVVJZVKs7Oz4+Pj\nQ0JCHj16FBwcfPbsWSPkMQLcWgXAnJnSLI7IyEgiWr16dUxMzLhx4zw9PZ2cnIRCoVgsbt++\nfXBw8P79++fOnVtRUbFkyRIOc+oRJnIAmDNTmsVx6dIlIpowYYKWPhEREUT022+/GSeSobm6\nUrNmKNAAZsqUZnFYWFgQUUVFhZY+zKp7jWm+to8PXb9OuCsvgBliW6Dt7e137Njx4MGD4OBg\nBwcHgRqDpmT07NmTiFasWKGlz6pVqxQ9GweJhIqKKCeH6xwAYHSmdFfvBQsWCIXCyMjIwMDA\n3bt3Z2ZmSqXSmpqa4uLiu3fvxsbGjhgxYtmyZQKB4PPPP+c6rN7gPCGA2WI7zc5o05y18PPz\n27t375QpU5KTk5OTkzX2sbOzi4qKCgoKMnI2w1GcJ2wsUwcBgC0TmwcdHBwcFBQUExOTkpJy\n8eLF58+fFxYWWllZubm5denSJTAwMDw8vGnTplzH1CcfHxIIcJ4QwBzpUKALCgrWrVsXHR39\n+PHjioqK6upqLy+vuXPnfvDBB8Y5Bs0Qi8WTJ0+ePHmy0Z6RW46O9MorOMQBYI7YFmiZTObn\n53flyhXlxtu3b0+ZMuXYsWO7du0yZo02NxIJnTpFNTVkYUqnDACgodh+4tetW3flyhUfH5+b\nN28qGk+cONG+ffuYmJgtW7YYJl4dKioqli1b5u3tbW1t7erqOmzYsF9//ZWTJAbl40OlpXTv\nHtc5AMC42Bbo3bt3E9Hq1au9vb0Vjf3791+zZg0R/fjjj4YIp0JlPl9lZeWQIUO++OKLjIyM\nioqKFy9eJCYmDh48mLl9YmOCW6sAmCe2BTojI4OIevXqpdLu6+tLRLdu3dJvLDZWr16dmppq\na2u7ZcuWvLy83NzcyMhIGxub77//fufOncbPYziYaQdgntgWaCsrK/rrWj5lzMJyVVVV+o3F\nRnR0NBF98803H3zwgaurq7u7e0RExPLly4lo69atxs9jOBIJJnIAmCO2BbpHjx5EdOrUKZX2\nxMREIurWrZt+Y7GRnZ1NRKNHj1ZuHDVqFBGlp6cbP4/h2NlRmzYo0ABmh22BnjFjBhHNnj37\n+l914unTp5s3b54zZw4RcXLY18nJiYgcHByUG5lJ0CoLRjcCEgndvElc/EcFADjDtkCPHj16\n7ty5WVlZPsyVbUQtWrT48MMPi4qK/vWvf40dO9ZgCVUpFkJiBssqC9edO3eOiDp06GC0PMYh\nkVB5OWVnc50DAIxIh4m1y5cvT05ODgkJad68uaWlpbOz86BBg2JjYzds2GC4fOrEYrGXl9fQ\noUPLy8sFAgGzvijj1q1bs2bNIqKRI0caM5IRYCIHgBnS7VLvQYMGDRo0yEBR6hQQEJCRkZGT\nk3P79u3bt28zjb///ruiQ+fOnYnIw8Nj9uzZ3EQ0GOb/LdeuUaP70wMAtTKltTiSkpKISCaT\nZWVlZSpRdHB1dR08ePBXX33FHJ5uTDp3JqEQI2gA82JKBZohEom6deumcd5IXl6erlurrq4+\nfPhwWVmZlj737t0jopqaGl03rkciEbVrhwINYF5Mr0Dr17Fjx0aMGMGmZw7Xa+b7+FBiIlVU\nkJUVt0EAwEjMvUD7+/sfPHhQ+wg6MTFx+/bt48aNM1oqjSQSOnCAsrL+PGEIAI1eIyzQzHod\nLO8wIBQKhw8frr1Pbm7u9u3bmzRpoodwDaC44BsFGsBMYP1Kk4GZdgDmphGOoPlwdy5D8PYm\nS0sUaAAzwnYELZfLV65c2bVrVzs7O/VbemO1fiOwsiIvL6xpB2BG2I6gIyMj582bZ9AoUCeJ\nhOLjSSYjkYjrKABgeGxH0FFRUUQ0YsSIO3fuVFdXy9UYMuTfPHjwYMmSJf7+/i1bthSJRJaW\nlg4ODt7e3qGhodu2bZNKpUZLYnwSCVVXU0YG1zkAwCjYFuhHjx4R0fr169u1a6e+KrTRbNy4\nsWPHjgsXLkxLS8vNzS0rK6uuri4uLs7IyIiLi5s0aVKnTp2OHDnCVTxDYy74xmFoADPBttS2\nb9+eiFxcXAwZpg6JiYnTpk2rrKwMCwvbtWtXVlZWQUFBVVWVVCrNzs6Oj48PCQl59OhRcHDw\n2bNnOcxpOEyB3rsX644CmAW2BfqTTz4hon379hkyTB0iIyOJaPXq1TExMePGjfP09HRychIK\nhWKxuH379sHBwfv37587d25FRcWSJUs4zGk4HTvS0KF04ACNGEElJVynAQADY1ugJ02atHTp\n0hkzZmzfvv3ly5ecTGW7dOkSEU2YMEFLH2b1UZVFohsNCwtKSKCpU+nIEerXj7i++BwADIvt\nLA7FRLra6qMRSjZz7LuiokJLH6FQSEqL+jc+QiFt3Eje3jR7NvXtS4cPExe3GwMAYzClKwl7\n9uxJRCtWrNDSZ9WqVYqejdisWRQdTXl55OdHx49znQYADEOHC1W0M2hKxoIFC4RCYWRkZGBg\n4O7duzMzM6VSaU1NTXFx8d27d2NjY0eMGLFs2TKBQPD5558bIQ+3xo+nI0eopoaCgmj3bq7T\nAIABmNKl3n5+fnv37p0yZUpycnJycrLGPnZ2dlFRUUFBQUbOxomBA+nUKRo6lP7xD8rMpEWL\nuA4EAHplSgWaiIKDg4OCgmJiYlJSUi5evPj8+fPCwkIrKys3N7cuXboEBgaGh4czN/Y2Ez4+\ndPYsDRtGixfTo0e0cSNZmtivFABq1dBPc0FBgYuLS8uWLY22nr1YLJ48efLkyZON83T898or\ndOIEhYbS1q2Ul0e7d5NYzHUmANAHHU4Sbtu2rU2bNiprJDGXrpSXlxssIdTNzo4OHqR//pMS\nEsjPj5494zoQAOgD2wKdkpIyadKkBw8eqD7ewuL111+Pjo7Wcy5dYDk9IrK0pE2baOFCunCB\n+vbFeh0AjQHbAr1s2TIi+uyzz0pKSjZv3uzs7HzixIn09PQ2bdr4+fkNHTrUkCGBFYGAFi2i\nbdsoJ4fefJNOnuQ6EAA0DNsCfeXKFSKaO3eura3tG2+8UVBQEBER0a1bt6+//nr58uWxsbGG\nDAk6mDCBEhOpqooCA2nPHq7TAEADsC3QNTU19NdVfO7u7kR048YNuVweGBhIRN9++63BEoLO\nAgPp5Elyc6OxY0nrZT0AwGtsCzRzbV5ERMSTJ0+aNm0qEolKSkru3r0rEomI6DpWwOSZbt3o\n3Dnq2pXmzaNZs6imhutAAKA7tgX6s88+EwgEO3bsYIbPvXr1IqLY2Nj4+HgiatasmeEi1snI\ndwwwFS1bUloaDRhAa9fS//0fyWRcBwIAHbEt0IMGDdq7d2/fvn1tbW2J6J///CcRffbZZ++9\n9x4RjR8/3nARod6cnenoURo3juLjaeBAysvjOhAA6EKHC1VGjhw5cuRI5uv333///v37mzZt\nqqioeO+99+bPn2+YeNBQVla0cyd5edHixfTGG3TkCHl5cZ0JANip52p2AoFgwYIFOTk5z549\nW716tZWVlX5jgR4x0++2bKH79+mNN+jMGa4DAQA7bAt0eXn5F1984eXlZWNjI9DEoCmh4T74\ngPbuJZmMgoLo0CGu0wAAC2wL9Ny5c5ctW3b79m1c1W263n2X0tLI1pZCQmj9eq7TAEBd2Bbo\nmJgYIlqyZElJSQlX60FDw732Gp07R56eNGMGpt8B8B3bAl1aWkpEc+bMYWZxgOlq147OnKH+\n/WntWhozhsrKuA4EALVgW6AHDBhARDdu3DBkGDASFxdKSqIxY2jvXho0iF684DoQAGjCtkCv\nX7++TZs248ePT0lJKSwsNGgmMAJra4qJoblz6cwZeustun+f60AAoIZtgW7duvW//vWvW7du\nBQQEODk5YRZHIyAQ0PLltGYN3bpFb7xBf/zBdSAA+Du2BfqLL7749NNPDRoFODFrFu3dSy9f\n0oABlJjIdRoAUMK2QP/www9EtHjx4oKCAsziaGRCQig1lUQievdd2rSJ6zQA8BfdriScPXu2\nk5OTgaIAh/r2pbNnqX17mjqVPv2U8AcXgA/YFugpU6YQ0YULFwwZBrjUoQOdPEmvvUbLl9Ok\nSVRZyXUgALPHtkAvWrRo1qxZEydOTEhIYI5yGDQWcKJ5czp2jIYNo+hoatWK3nuPoqMpN5fr\nWADmiu1qdpaWf/YMDg7W2AElu3GwtaUDB+ibb2jvXoqJod27iYgkEgoMpMBAGjCAcKESgNHU\nczU7aMSEQpo/ny5doqdPKTaWpkyh4mJas4aGDiUnJ+rdmz79lJKTqaqK66AAjR3bETQGyGbI\nzY1Gj6bRo4mI7tyh5GRKTqajR+niRVq+nJo2pYEDKSCAgoKobVuOowI0Sjos2A/mrH17mjKF\npkyhqipKT/+zWMfHU1zcnz8NCKCAAAoMJEzzAdAXbQWauT6QGTsrfw3mzNKSevWiXr1o3jx6\n8YJSU/8cVm/eTJs3k1BIPXr8WawHDKAmTbiOC2DKtB2DFovFRHT+/PkarEoJmjRtSqNH06ZN\ndPcuZWfTpk00ciRlZ9Py5RQYSC4uFBhIy5fTxYtcBwUwTdpG0D179jx16lTfvn0VLVrW3MDg\n2swpjoFUV9Ply38eAzlxgpKT//wpM6weNIhcXLjOCmAitI2gV61a5ePjIxQKjZYGGgGh8M8D\nIElJlJ9PSUk0bx45O9PmzRQaSs2a/W8eCG7OA6CdthH0a6+9dvXqVeZrHIOGerC1/XPgTER3\n7lBSEiUlUWoqLV9Oy5eTnR116sR1RGjsHB3pwAGyt+c6R71gmh0YSfv29OGH9OGHVF1Nv/9O\nSUl07BhhaXEALTCLA4xNKKTXX6fXX6cvvuA6CgC/YRYHAABPaSvQPXv2JKK+ffsqzhOq30gF\nd1QBADAQzOIAAOApzOIAAOApzOIAAOAptgW6zqPMqOAAAPrV0NXsBAKBUCisrq7WSxo+y8jI\nsLGx4TZDZWVldHR0mzZtLCxMfiHvmpqa27dve3p6NoLXQo3r5TSy13L//v0JEyY0qX3hroyM\nDGNG0o3GW3TXSSaTZWZmLl++3NHR8csvv6ypqanfdkzC+vXruf4tAYBhrV+/nutKo0E9R9A2\nNjZeXl5z585t0aJFeHi4WCyeM2eOfvcXf7z33ntVVVUymYzrIHTlypXdu3f7+vq2adOG6ywN\ndf/+/VOnTjWO10KN6+U0vtcybty4bt26aekmEonee+89o6XSQQMLfFFRERG1bdtWL38uQLvY\n2Fgiio2N5TqIHjSm1yJvXC8Hr4U/GnqMqaCggIhycednAAB9a1CBfvLkCXNkw8PDQ095AADg\nT/qZZjd16lR9hAEAgP9p0DQ7a2vrTp06zZ49e8KECXrKAwAAf8KVhAAAPGXyE9EBABorFGgA\nAJ6q+44qLOEYCACAfmEEDQDAU9pG0OqDYqwKzS2RSKT419Q1ptdCjevl4LXwh0CnaosCza3q\n6uqUlJRBgwY1gtvcNKbXQo3r5eC18AcKNAAAT+EYNAAAT6FAAwDwFAo0AABPoUADAPAUCjQA\nAE9pm8WBKwkBADiEETQAAE/pNg8aAACMBiNoAACeQoEGAOApFGgAAJ5CgQYA4CkUaAAAnkKB\nBgDgKRRoAACeQoEGAOApFGjTIJPJli5d2r17dwcHB5FI5O3t/cknnxQUFHCdq6EePnzo4uKi\n06ICfPP48eOZM2d6enpaW1s3a9YsJCQkPT2d61D1dPr06YEDB9rZ2dna2r711ltpaWlcJ9LN\nP//5Ty3vpbS0tICAABcXF2dnZ39//8TERGNmqyc58J5UKu3du7f6787b27ugoIDrdPVXXV09\nYMAAk34f3r17t1WrViq/F3t7++zsbK6j6ez8+fNWVlbKL8TS0vLYsWNc52JLKpU2a9astvfS\ngQMH1O96tWHDBiOH1JWpfjDMyjfffENEbm5ue/bsefnyZWFhYUJCAlMX/v3vf3Odrv6WLl1q\n6gMF5g+Mr6/v5cuXS0tLz58/3717dyIaN24c19F0FhgYSETvv/9+Xl5ebm5uSEgIEfXt25fr\nXHV78eLF4cOH/f39a3svKWr3J5988uzZs8LCwjVr1lhYWFhbW9+/f9/4gdkz1Q+GWXn11VeJ\nKC4uTrkxJSWFiF555RWuUjXQ+fPnLS0tnZycTLdAnzp1iog8PDyKiooUjdevXyei5s2bcxis\nfsRiMRE9efKE+fbx48dEZG1tzW0qNuo8KrB161YiCggIUG4MCwsjosWLFxsrZn3gGLQJyM7O\nJqKAgADlxtdee42IXrx4wU2mhikpKRk3blxVVVVUVBTXWervl19+IaKZM2fa29srGrt06SKX\ny588ecJdrnqys7MjpUWGq6qqiMjNzY3LTOwoylltHZjRzMSJE5UbuslP3AAAC8lJREFUhw8f\nTkTHjh0zdLyGQIE2AYWFhXK5XDHYZKSmphKRt7c3R6EaZPr06dnZ2RMmTBgzZgzXWerv5MmT\nRDRo0KB169Z16tTJ2tq6Xbt2c+fOLS4u5jpafTAjyunTpz958uTx48fTp08novfee4/rXHpw\n8eJFIlI5kdOnTx8iyszM5CYTS5yN3aEBjh071rRpUyLauXMn11l09vPPPxNRhw4diouL5X+N\nergOVR8eHh5E9OGHH6p8prp06ZKfn891Op3JZLJp06Ypv5Dx48eXl5dznUsHtb2XXFxciKik\npES5kZkEZWNjY6x09WGSHwxz9vz5c2YukUAgWLhwIddxdHbv3j1HR0dLS8vz588zLaZboJlj\nAo6Ojps3b87LyyspKUlISHB1dSWijz/+mOt0Ojtw4ICnp6dygW7atOnGjRu5zqWD2t5LzPyN\n6upq5UbmGI5QKDRWuvowyQ+Geaqurt6wYQMzFvDy8kpJSeE6UX34+voS0dKlSxUtplugLS0t\nieinn35Sbty2bRsReXp6cpWqfvbv3y8QCFq1arV///6CgoK8vLw9e/a4u7sTUVRUFNfp2Krt\nvSQSiYhI+VyuXC6XSqVEZG9vb6x09WGSHwwz9PTp07feeouInJ2dV65caVr/8VTWmA64OTs7\nE9Hz58+VG5nTtlZWVlylqh9mdmBqaqpyY1JSEnMwiqtUuqrtXdS6dWsiunPnjnIjc+69U6dO\nxkpXHzhJaALKysoCAwNPnDgxdOjQW7duzZkzR+WCAuBEu3btiKiyslK5kfmWmbJmQm7dukV/\nTQ1S6Nu3LxE9fPiQm0z606VLFyK6cOGCcuOVK1eIqFu3btxkYgcF2gT8+OOPV65cGTBgwIED\nB5j59qZLfYyg3M5tNl3179+fiGJjY5Ub4+Pj6a8ZAiaEOXR+7tw55carV68SEXMu1KQx1+Ds\n2rVLufGnn34iosGDB3OTiSXjDtihPoYMGUJEFy9e5DqIQZju+/DatWuWlpZisXjdunW5ubkv\nXrz46aefmDnRhw4d4jqdbmbOnElELVu23Ldv3/PnzwsLCxMTE9u3b09EX3zxBdfp2KrtvfT8\n+XPmjO4XX3yRn5+fl5c3b9485vWqTO3gG5P8YJgb9dUeGtOfWJN+FevWrVNfnWfq1Klc59JZ\nfn5+jx491N9dr7/+emlpKdfp2NLyXtqxY4fKb8rKyurw4cNGTqgrU/1gmBXmHDQKND8lJycP\nGjTIzs5OLBb37t17y5YtNTU1XIeqD5lMtmLFildffVUkEllbW0skksWLF5tQdZbX9V769ddf\n33rrLXt7e2dn57fffvv06dPGzFY/ArmpHfgDADATOEkIAMBTKNAAADyFAg0AwFMo0AAAPIUC\nDQDAUyjQAAA8hQINAMBTKNAAADyFAg0AwFMo0AAAPIUCDQDAUyjQAAA8hQINAMBTKNAAADyF\nAg0AwFMo0AAAPIUCDQDAUyjQAAA8hQINAMBTKNAAADyFAg0AwFMo0AAAPIUCDQDAUyjQAAA8\nhQINAMBTKNAAADyFAg0AwFMo0AAAPIUCDQDAUyjQAAA8hQINAMBTKNAAADyFAg0cEKixt7fv\n169ffHy8xp76fV59bc0QGwRQJpDL5VxnALOjpajt3bt31KhRKj319S7V79YMsUEAZRhBA2fk\nf6moqLh9+/aYMWOIaOnSpVzn0gGTn+sU0GhhBA0c0DjwzM/Pb9q0qUgkKi0t1d5Tv88LwFsY\nQQNfFBYWEpGHh4f2brGxsf3793dwcBCLxa+99trmzZtVCq5cLt+0aVOPHj1EIlGrVq1Gjx59\n48YNjZtau3atQCDo06dPSUlJbU93+vTp4ODgNm3aWFtbu7m5BQUFJSQkKH6qcgxa/di6+kHq\nvXv3+vn5OTo6isXiHj16REZGymQy7S+5pKRkxowZbm5urq6u06dPl8lkOPZtLuQARqfy3quo\nqLh582ZAQAARbdy4UUvPefPmqb+HR40aVV1dregzZcoUlQ62trbXrl1T2doPP/wgEAg6deqU\nl5dXW87t27drrINr167VGE/jR0woFCo6zJ07V71D9+7d8/Pza8tQU1MzaNAg5f7h4eH48JoJ\n/I6BAxoLGRHNnz9fY0/m65SUFCKysbHZsGFDbm5ucXFxbGysi4sLEUVFRTF9EhMTicjBweHA\ngQOlpaUZGRn9+vUjonHjxilvLSYmxsLColWrVvfv39eSs02bNkT03Xff5efnl5eX5+TkrFix\ngoiaN2+uHk/FvXv33N3dlbMx+b28vA4dOvTy5cv8/PykpCQfHx8iWrx4cW0ZYmJiiMjFxeXQ\noUNSqfT48eMtW7ZEgTYT+B0DB2or0JaWlrNnz66qqlLpyXw9cuRIIlq6dKnypqKjo4nozTff\nZL599913iWjlypWKDszxDaakMltLSEiwtLR0cXG5fv269pwikYiITp48qf2FqLfn5+d37tyZ\niL744gtFY0hICBExY3mFmzdvElG7du1qe4ohQ4YQ0fr16xUtu3btQoE2E/gdAwfU60thYeF/\n//tfb29vIlqyZInGnsyANCsrS/mBz549Y4bMyn2ys7O1PK+1tTUzkq2oqNCec8aMGURkYWHR\nv3//BQsWHD16VCqVan8hcrlcJpP5+voS0YQJE5TbmzdvXttfJhsbm9oyNGvWjIiUR/rMS0aB\nNgf4HQMHaqsvly9fJqK2bdtq7GlpaUlEMplM+SHMGbYmTZow3zZp0oSIysvLtTxvkyZNmAKq\nPNDWqKamZseOHf7+/lZWVsxjRSJReHj48+fPa3sh1dXVzEh/8ODBlZWVyj9i8mskEAhqy8A8\nSvkVVVRUoECbCfyOgQO11Rem2lpbW2vs6eDgQEQPHjxQfghzBKNVq1bMt3Z2dkT05MkTLc+7\ne/fu3NxcsVjs5OSkKLXalZaWpqWlLVq0yMvLi4iCgoJqeyEzZ84kol69ehUXF6tsxNnZWUu2\n2tja2hKR8pnM3NxcFGgzgWl2wCPnz58norZt22r8abdu3YgoLi5OuXHPnj1E9MYbbyj3OXr0\nqKLDxYsXBQIBc7qPMXbsWHd39zlz5rx8+fI///mPljzu7u4CgeDhw4cikWjAgAELFy48deoU\nER0/flxj/xUrVqxbt65du3aJiYnMnwplr776KhEdPHhQufHkyZMCgYCp+xp5enoSUWpqqqJF\n+dVBI8f1XwgwR+rvvdLS0qNHj7Zr147+PqVBueeWLVuIyNbWduvWrU+fPi0uLt65c6dYLCai\nlJQUpk9UVBQRNW/e/OjRoyUlJX/88QczTeKjjz5S2VpRUVGzZs2EQqHKWTtlo0ePJqKBAwde\nvnxZJpM9fPjwo48+IqJOnTqpx9u1a5dAIHB1dc3IyNC4NeZviaOj47Zt2548eVJQUHDw4MH2\n7dsTETObW6OFCxcSUevWrc+dO1dWVpaWltaiRQt8eM0EfsfAAS0jhp49eyofHFCuRNXV1cOG\nDVN/yPTp0xX9q6qqBg4cqNLBw8Pj2bNncrU/DN9//z0Rvf3227XlvHnzJnNGUZlAINi3b596\nPMVxanWKDarP0SaisWPH1tTU1JahsLCwU6dOyv2Dg4NVNguNFX7HwAH1IiUSiSQSyaJFi0pK\nStR7Kr6tqKiIjIyUSCTW1tb29vZvvvnmtm3bVKqbVCr97LPPWrdubW1t7enpOXPmzKdPn2rc\nWmVlZceOHYnol19+qS3q2bNnhw4d2rRpU6FQ6OzsHBgYmJSUpDFebdVZpZLu2LGjb9++YrHY\nwcGhT58+mzZt0lKdGc+ePZs4caKTk5Ojo2N4eHhxcTEKtJnAWhwApgeLipgJnCQEAOApFGgA\nAJ5CgQYA4CkcgwYA4CmMoAEAeAoFGgCAp1CgAQB4CgUaAICnUKABAHgKBRoAgKdQoAEAeAoF\nGgCAp1CgAQB4CgUaAICnUKABAHgKBRoAgKdQoAEAeAoFGgCAp1CgAQB4CgUaAICnUKABAHgK\nBRoAgKdQoAEAeAoFGgCAp1CgAQB4CgUaAICnUKABAHgKBRoAgKf+H5PHuku2EBtQAAAAAElF\nTkSuQmCC", "text/plain": [ "Plot with title \"Huffman block coding performance\"" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "source(\"nt_solutions/coding_2_entropic/exo2.R\")" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "## Insert your code here." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "" ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "R", "language": "R", "name": "ir" }, "language_info": { "codemirror_mode": "r", "file_extension": ".r", "mimetype": "text/x-r-source", "name": "R", "pygments_lexer": "r", "version": "3.4.2" } }, "nbformat": 4, "nbformat_minor": 0 }