RICE.ipynb

Kernel: Python 2 (SageMath)

Exercici AvCont-5: Codificació Rice

%matplotlib inline
import numpy as np
from matplotlib import pyplot as plt
import pandas as pd

a) ¿Cuántos bits son necesarios para codificar todos los enteros entre -1023 y +1023 (en codificación binaria natural con bit de signo)?

print "Es necesiten", np.ceil(np.log2(len(xrange(-1023, 1023)))), "bits"

Es necesiten 11.0 bits

b) Calculad el código Rice de todos los enteros N entre -1023 y +1023 con M = 32.

def bitsNeeded(num):
    return int(np.ceil(np.log2(num)))
def rice(N,M):
    quocient = int(np.floor(abs(N)/float(M)))
    rest = abs(N) % M
    result = "{0}{1}{2:0={3}b}".format(int(N>=0), "1" * quocient + "0", rest, bitsNeeded(M))
    return result
nums = np.arange(-1023,1023 + 1)
riceCodes = np.vectorize(rice)(nums, 32)
df = pd.DataFrame({"Valor de N": nums, "Código RICE": riceCodes})
df.to_csv("riceCodeFrom-1023to1023.csv")
df

	Código RICE	Valor de N
0	01111111111111111111111111111111011111	-1023
1	01111111111111111111111111111111011110	-1022
2	01111111111111111111111111111111011101	-1021
3	01111111111111111111111111111111011100	-1020
4	01111111111111111111111111111111011011	-1019
5	01111111111111111111111111111111011010	-1018
6	01111111111111111111111111111111011001	-1017
7	01111111111111111111111111111111011000	-1016
8	01111111111111111111111111111111010111	-1015
9	01111111111111111111111111111111010110	-1014
10	01111111111111111111111111111111010101	-1013
11	01111111111111111111111111111111010100	-1012
12	01111111111111111111111111111111010011	-1011
13	01111111111111111111111111111111010010	-1010
14	01111111111111111111111111111111010001	-1009
15	01111111111111111111111111111111010000	-1008
16	01111111111111111111111111111111001111	-1007
17	01111111111111111111111111111111001110	-1006
18	01111111111111111111111111111111001101	-1005
19	01111111111111111111111111111111001100	-1004
20	01111111111111111111111111111111001011	-1003
21	01111111111111111111111111111111001010	-1002
22	01111111111111111111111111111111001001	-1001
23	01111111111111111111111111111111001000	-1000
24	01111111111111111111111111111111000111	-999
25	01111111111111111111111111111111000110	-998
26	01111111111111111111111111111111000101	-997
27	01111111111111111111111111111111000100	-996
28	01111111111111111111111111111111000011	-995
29	01111111111111111111111111111111000010	-994
...	...	...
2017	11111111111111111111111111111111000010	994
2018	11111111111111111111111111111111000011	995
2019	11111111111111111111111111111111000100	996
2020	11111111111111111111111111111111000101	997
2021	11111111111111111111111111111111000110	998
2022	11111111111111111111111111111111000111	999
2023	11111111111111111111111111111111001000	1000
2024	11111111111111111111111111111111001001	1001
2025	11111111111111111111111111111111001010	1002
2026	11111111111111111111111111111111001011	1003
2027	11111111111111111111111111111111001100	1004
2028	11111111111111111111111111111111001101	1005
2029	11111111111111111111111111111111001110	1006
2030	11111111111111111111111111111111001111	1007
2031	11111111111111111111111111111111010000	1008
2032	11111111111111111111111111111111010001	1009
2033	11111111111111111111111111111111010010	1010
2034	11111111111111111111111111111111010011	1011
2035	11111111111111111111111111111111010100	1012
2036	11111111111111111111111111111111010101	1013
2037	11111111111111111111111111111111010110	1014
2038	11111111111111111111111111111111010111	1015
2039	11111111111111111111111111111111011000	1016
2040	11111111111111111111111111111111011001	1017
2041	11111111111111111111111111111111011010	1018
2042	11111111111111111111111111111111011011	1019
2043	11111111111111111111111111111111011100	1020
2044	11111111111111111111111111111111011101	1021
2045	11111111111111111111111111111111011110	1022
2046	11111111111111111111111111111111011111	1023

2047 rows × 2 columns

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?

df["Bits para RICE"] = np.vectorize(len)(df["Código RICE"])
df["Comprime?"] = df["Bits para RICE"] < bitsNeeded(len(df)/2) + 1
print bitsNeeded(len(df))
nGood = df[df["Comprime?"]]["Valor de N"]
print "RICE comprime de {0} a {1}".format(np.min(nGood), np.max(nGood))

11
RICE comprime de -127 a 127

print len(df)

2047

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?

df["Bits ahorrados"] = bitsNeeded(len(df)) - df["Bits para RICE"]
print "El ahorro máximo es de {0} bits".format(np.max(df["Bits ahorrados"]))

El ahorro máximo es de 4 bits

d.1) ¿Para qué valor de M el rango de entrada óptima se extiende entre -255 y +255?

import itertools
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)))]
df = pd.DataFrame(data)
df["Código RICE"] = np.vectorize(rice)(df["Valor de N"], df["Valor de M"])
df["Bits para RICE"] = np.vectorize(len)(df["Código RICE"])
df["Comprime?"] = df["Bits para RICE"] < bitsNeeded(df["Valor de N"].nunique())
compressTable = df[df["Comprime?"]].pivot_table(values="Valor de N", index="Valor de M", aggfunc=[np.max,np.min])
targetM = compressTable[(compressTable["amax"]==255) & (compressTable["amin"]==-255)]
print "El valor de M que su entrada óptima se extiende desde -255 hasta 255 es {0}".format(targetM.index[0])

El valor de M que su entrada óptima se extiende desde -255 hasta 255 es 128

d.2) ¿Cuál es el máximo ahorro de bits ahora?

df["Bits ahorrados"] = bitsNeeded(df["Valor de N"].nunique()) + 1 - df["Bits para RICE"]
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"]))

Cuando M es 128 el máximo ahorro es 3

e.1) ¿Cuál es el mayor valor de M que permite lograr un máximo ahorro de hasta 6 bits?

maxMFor6 = df[df["Bits ahorrados"]>=6]["Valor de M"].max()
print "El valor de M más grande que permite ahorrar hasta 6 bits es {}".format(maxMFor6)

El valor de M más grande que permite ahorrar hasta 6 bits es 16

e.2) ¿Cuál es el rango de entrada óptima ahora?

print "El rango de entrada óptimo cuando M={0} es desde {1[amax]} hasta {1[amin]}".format(maxMFor6,compressTable.ix[maxMFor6])

El rango de entrada óptimo cuando M=16 es desde 79 hasta -79