{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "# Exercici AvCont-5: Codificació Rice" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": true }, "outputs": [], "source": [ "%matplotlib inline\n", "import numpy as np\n", "from matplotlib import pyplot as plt\n", "import pandas as pd" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### a) ¿Cuántos bits son necesarios para codificar todos los enteros entre -1023 y +1023 (en codificación binaria natural con bit de signo)?" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Es necesiten 11.0 bits\n" ] } ], "source": [ "print \"Es necesiten\", np.ceil(np.log2(len(xrange(-1023, 1023)))), \"bits\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### b) Calculad el código Rice de todos los enteros N entre -1023 y +1023 con M = 32. " ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Código RICEValor de N
001111111111111111111111111111111011111-1023
101111111111111111111111111111111011110-1022
201111111111111111111111111111111011101-1021
301111111111111111111111111111111011100-1020
401111111111111111111111111111111011011-1019
501111111111111111111111111111111011010-1018
601111111111111111111111111111111011001-1017
701111111111111111111111111111111011000-1016
801111111111111111111111111111111010111-1015
901111111111111111111111111111111010110-1014
1001111111111111111111111111111111010101-1013
1101111111111111111111111111111111010100-1012
1201111111111111111111111111111111010011-1011
1301111111111111111111111111111111010010-1010
1401111111111111111111111111111111010001-1009
1501111111111111111111111111111111010000-1008
1601111111111111111111111111111111001111-1007
1701111111111111111111111111111111001110-1006
1801111111111111111111111111111111001101-1005
1901111111111111111111111111111111001100-1004
2001111111111111111111111111111111001011-1003
2101111111111111111111111111111111001010-1002
2201111111111111111111111111111111001001-1001
2301111111111111111111111111111111001000-1000
2401111111111111111111111111111111000111-999
2501111111111111111111111111111111000110-998
2601111111111111111111111111111111000101-997
2701111111111111111111111111111111000100-996
2801111111111111111111111111111111000011-995
2901111111111111111111111111111111000010-994
.........
201711111111111111111111111111111111000010994
201811111111111111111111111111111111000011995
201911111111111111111111111111111111000100996
202011111111111111111111111111111111000101997
202111111111111111111111111111111111000110998
202211111111111111111111111111111111000111999
2023111111111111111111111111111111110010001000
2024111111111111111111111111111111110010011001
2025111111111111111111111111111111110010101002
2026111111111111111111111111111111110010111003
2027111111111111111111111111111111110011001004
2028111111111111111111111111111111110011011005
2029111111111111111111111111111111110011101006
2030111111111111111111111111111111110011111007
2031111111111111111111111111111111110100001008
2032111111111111111111111111111111110100011009
2033111111111111111111111111111111110100101010
2034111111111111111111111111111111110100111011
2035111111111111111111111111111111110101001012
2036111111111111111111111111111111110101011013
2037111111111111111111111111111111110101101014
2038111111111111111111111111111111110101111015
2039111111111111111111111111111111110110001016
2040111111111111111111111111111111110110011017
2041111111111111111111111111111111110110101018
2042111111111111111111111111111111110110111019
2043111111111111111111111111111111110111001020
2044111111111111111111111111111111110111011021
2045111111111111111111111111111111110111101022
2046111111111111111111111111111111110111111023
\n", "

2047 rows × 2 columns

\n", "
" ], "text/plain": [ " Código RICE Valor de N\n", "0 01111111111111111111111111111111011111 -1023\n", "1 01111111111111111111111111111111011110 -1022\n", "2 01111111111111111111111111111111011101 -1021\n", "3 01111111111111111111111111111111011100 -1020\n", "4 01111111111111111111111111111111011011 -1019\n", "5 01111111111111111111111111111111011010 -1018\n", "6 01111111111111111111111111111111011001 -1017\n", "7 01111111111111111111111111111111011000 -1016\n", "8 01111111111111111111111111111111010111 -1015\n", "9 01111111111111111111111111111111010110 -1014\n", "10 01111111111111111111111111111111010101 -1013\n", "11 01111111111111111111111111111111010100 -1012\n", "12 01111111111111111111111111111111010011 -1011\n", "13 01111111111111111111111111111111010010 -1010\n", "14 01111111111111111111111111111111010001 -1009\n", "15 01111111111111111111111111111111010000 -1008\n", "16 01111111111111111111111111111111001111 -1007\n", "17 01111111111111111111111111111111001110 -1006\n", "18 01111111111111111111111111111111001101 -1005\n", "19 01111111111111111111111111111111001100 -1004\n", "20 01111111111111111111111111111111001011 -1003\n", "21 01111111111111111111111111111111001010 -1002\n", "22 01111111111111111111111111111111001001 -1001\n", "23 01111111111111111111111111111111001000 -1000\n", "24 01111111111111111111111111111111000111 -999\n", "25 01111111111111111111111111111111000110 -998\n", "26 01111111111111111111111111111111000101 -997\n", "27 01111111111111111111111111111111000100 -996\n", "28 01111111111111111111111111111111000011 -995\n", "29 01111111111111111111111111111111000010 -994\n", "... ... ...\n", "2017 11111111111111111111111111111111000010 994\n", "2018 11111111111111111111111111111111000011 995\n", "2019 11111111111111111111111111111111000100 996\n", "2020 11111111111111111111111111111111000101 997\n", "2021 11111111111111111111111111111111000110 998\n", "2022 11111111111111111111111111111111000111 999\n", "2023 11111111111111111111111111111111001000 1000\n", "2024 11111111111111111111111111111111001001 1001\n", "2025 11111111111111111111111111111111001010 1002\n", "2026 11111111111111111111111111111111001011 1003\n", "2027 11111111111111111111111111111111001100 1004\n", "2028 11111111111111111111111111111111001101 1005\n", "2029 11111111111111111111111111111111001110 1006\n", "2030 11111111111111111111111111111111001111 1007\n", "2031 11111111111111111111111111111111010000 1008\n", "2032 11111111111111111111111111111111010001 1009\n", "2033 11111111111111111111111111111111010010 1010\n", "2034 11111111111111111111111111111111010011 1011\n", "2035 11111111111111111111111111111111010100 1012\n", "2036 11111111111111111111111111111111010101 1013\n", "2037 11111111111111111111111111111111010110 1014\n", "2038 11111111111111111111111111111111010111 1015\n", "2039 11111111111111111111111111111111011000 1016\n", "2040 11111111111111111111111111111111011001 1017\n", "2041 11111111111111111111111111111111011010 1018\n", "2042 11111111111111111111111111111111011011 1019\n", "2043 11111111111111111111111111111111011100 1020\n", "2044 11111111111111111111111111111111011101 1021\n", "2045 11111111111111111111111111111111011110 1022\n", "2046 11111111111111111111111111111111011111 1023\n", "\n", "[2047 rows x 2 columns]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def bitsNeeded(num):\n", " return int(np.ceil(np.log2(num)))\n", "def rice(N,M):\n", " quocient = int(np.floor(abs(N)/float(M)))\n", " rest = abs(N) % M\n", " result = \"{0}{1}{2:0={3}b}\".format(int(N>=0), \"1\" * quocient + \"0\", rest, bitsNeeded(M))\n", " return result\n", "nums = np.arange(-1023,1023 + 1)\n", "riceCodes = np.vectorize(rice)(nums, 32)\n", "df = pd.DataFrame({\"Valor de N\": nums, \"Código RICE\": riceCodes})\n", "df.to_csv(\"riceCodeFrom-1023to1023.csv\")\n", "df" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### c.1) ¿Para qué rango de valores de N, el código Rice requiere menos bits que la codificación binaria natural con bit de signo?" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "11\n", "RICE comprime de -127 a 127\n" ] } ], "source": [ "df[\"Bits para RICE\"] = np.vectorize(len)(df[\"Código RICE\"])\n", "df[\"Comprime?\"] = df[\"Bits para RICE\"] < bitsNeeded(len(df)/2) + 1\n", "print bitsNeeded(len(df))\n", "nGood = df[df[\"Comprime?\"]][\"Valor de N\"]\n", "print \"RICE comprime de {0} a {1}\".format(np.min(nGood), np.max(nGood))" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2047\n" ] } ], "source": [ "print len(df)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### c.2) Si la mayoría de datos a codificar pertenecen a este rango (rango de entrada óptima), el uso de código Rice será aconsejable (habrá ahorro de bits) ¿Cuál es el máximo ahorro de bits?\n" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "El ahorro máximo es de 4 bits\n" ] } ], "source": [ "df[\"Bits ahorrados\"] = bitsNeeded(len(df)) - df[\"Bits para RICE\"]\n", "print \"El ahorro máximo es de {0} bits\".format(np.max(df[\"Bits ahorrados\"]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### d.1) ¿Para qué valor de M el rango de entrada óptima se extiende entre -255 y +255?" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "El valor de M que su entrada óptima se extiende desde -255 hasta 255 es 128\n" ] } ], "source": [ "import itertools\n", "data = [{\"Valor de N\":pair[0], \"Valor de M\":pair[1]} for pair in itertools.product(np.arange(-1023,1023 + 1), np.power(2,np.arange(2,11)))]\n", "df = pd.DataFrame(data)\n", "df[\"Código RICE\"] = np.vectorize(rice)(df[\"Valor de N\"], df[\"Valor de M\"])\n", "df[\"Bits para RICE\"] = np.vectorize(len)(df[\"Código RICE\"])\n", "df[\"Comprime?\"] = df[\"Bits para RICE\"] < bitsNeeded(df[\"Valor de N\"].nunique())\n", "compressTable = df[df[\"Comprime?\"]].pivot_table(values=\"Valor de N\", index=\"Valor de M\", aggfunc=[np.max,np.min])\n", "targetM = compressTable[(compressTable[\"amax\"]==255) & (compressTable[\"amin\"]==-255)]\n", "print \"El valor de M que su entrada óptima se extiende desde -255 hasta 255 es {0}\".format(targetM.index[0])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### d.2) ¿Cuál es el máximo ahorro de bits ahora?" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cuando M es 128 el máximo ahorro es 3\n" ] } ], "source": [ "df[\"Bits ahorrados\"] = bitsNeeded(df[\"Valor de N\"].nunique()) + 1 - df[\"Bits para RICE\"]\n", "print \"Cuando M es {0} el máximo ahorro es {1}\".format(targetM.index[0], np.max(df[df[\"Valor de M\"]==targetM.index[0]][\"Bits ahorrados\"]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### e.1) ¿Cuál es el mayor valor de M que permite lograr un máximo ahorro de hasta 6 bits?" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "El valor de M más grande que permite ahorrar hasta 6 bits es 16\n" ] } ], "source": [ "maxMFor6 = df[df[\"Bits ahorrados\"]>=6][\"Valor de M\"].max()\n", "print \"El valor de M más grande que permite ahorrar hasta 6 bits es {}\".format(maxMFor6)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### e.2) ¿Cuál es el rango de entrada óptima ahora?" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "El rango de entrada óptimo cuando M=16 es desde 79 hasta -79\n" ] } ], "source": [ "print \"El rango de entrada óptimo cuando M={0} es desde {1[amax]} hasta {1[amin]}\".format(maxMFor6,compressTable.ix[maxMFor6])" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 2 (SageMath)", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.10" } }, "nbformat": 4, "nbformat_minor": 0 }