SISTEMA DE COMPRESION T.G.V.

SISTEMA DE COMPRESION T.G.V.

Uso en Criptografia

1. Partiendo de un conjunto de n bytes(caracteres), se toman los cuatro primeros bytes.
2. Cada byte se descompone en dos nibbles (conjuntos de 4 bits), cada uno representa de 0 a 15 en decimal, se toma cada uno de los 8 nibbles y se comparan con la siguiente tabla:

0000	0001	0010	0011	0100	0101	0110	0111
1000	1001	1010	1011	1100	1101	1110	1111

3. Si queremos expresar 4 bits con solo 3 bits, es decir podemos referirnos a un elemento de la tabla superior o inferior con 3 bits y un bit o flag por cada nibble que indica 0 o 1.

4	2	1
x	x	x

Por tanto podemos escribir del 0 al 7, que indicara cual es el valor del mismo mas 1 bit que sera 1 o 0.

En este punto tenemos 8 grupos de 3 bits mas 1 byte (8 bits) ordenados de 0 a 7 referenciando el nibble de 0 a 7 que apuntan.

4. Si queremos representar 3 bits con solo 2 bits nos encontramos un problema similar al anterior.

2	1
x	x

Por tanto podemos escribir del 0 al 3, que indicara cual es el valor del mismo mas 1 bit que sera 1 o 0.

x000

x001

x010

x011

x100

x101

x110

x111

Entonces ahora mi bit de señal me indicara en que posición izquierda o derecha(lo mismo que antes pero en lugar de abajo o arriba, izquierda y derecha) estan los dos bits de cada nibble. Ahora tenemos 8 grupos de 2 bits y un byte (8 bits) “apuntador” (ya tenemos uno anterior y este total 2 bytes).

5. Si queremos representar 2 bits con solo 1bit nos encontramos un problema similar al anterior.

1

x

Por tanto podemos escribir del 0 al 3, que indicara cual es el valor del mismo mas 1 bit que sera 1 o 0.

xx00

xx01

xx10

xx11

Entonces ahora mi bit de señal me indicara en que posición izquierda o derecha, sera 0 o 1, y me quedo con los 8 bits de menor peso(1 byte) y un byte(8 bits) “apuntador”. Es decir no hemos reducido el numero de bytes o de nibbles. Solo hemos tornado filas por columnas.

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Sistemas de compresión.

Los sistemas existentes nos ofrecen para esquemas sin perdida varias opciones, pero el ejemplo de los basados en diccionario es interesante, partamos de lo anterior, y supongamos que lo que hacemos es definir la probabilidad de que después de un 0 venga otro 0 o un 1, es decir 6 bits que me indican y tomo 1 solo byte

00	10	11	01	00	10	11	01	00	10	11	01	00	10	11	01
x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x

Y que si un 0 es seguido de otro 0 en 2 bits seria 101xxx, si fuese un 0 seguido de 1 seria 110xxx y en el mejor de los casos el 111xxx indicaria un 0 seguido de un 1 y seguido de 0. Ahora vamos a comparar los distintos valores y a ver que obtenemos. Pero claro estamos generando 2 bytes(16 bits) para representar solo 1 byte (8 bits), pero hemos generado 14 ceros y 2 unos, es decir hemos reducido 8 bits a 2 bits mas su posición que son 4 bits, pero mas 1 bit que indica izquierda o derecha.

¿Pero y si el byte fueran dos nibbles iguales? Podriamos representarlo por 1 nibble con su posición desde este nibble es decir dos nibbles, seguidos del mismo valor indicarian 0001 como posición de desplazamiento, el 0000 es su posición inicial y los 4 de menor peso indicarian el nibble.

b	a	11	10	01	00
x	x	x	x	x	x

Entonces las tablas se simplifican:

				00					00
				01					01
				10					10
				11					11

00 01 10 11 00 01 10 11

Ya que son iguales, en ambos nibbles, pero y si en lugar de hacerlo en los dos lo hiciera con los 8 nibbles de 4 bytes y en vez de 2 bits pusiera 4, diciendo donde se repite de 0 a 15.

d	c	b	a	11	10	01	00
x	x	x	x	x	x	x	x

En el peor de los casos me encuentro con 16 bytes para representar 16 nibbles (8 bytes), con lo que estoy duplicando el tamaño, pero en el caso que los bits a, b, c y d fueran 0 (el peor de los casos), introduzco otros 8 bytes (16 nibbles) y al menos tengo 16 bytes para representar 16 bytes, es decir la razon 1:1 de compresión.

¿Pero y si usaramos un diccionario con los valores posibles de los nibbles?

00 00 01

00 00 10

00 00 11

00 01 00

00 01 01

00 01 10

00 01 11

00 10 00

00 10 01

00 10 10

00 10 11

00 11 00

01 00 00

01 00 01

01 00 10

01 00 11

01 01 00

01 01 01

01 01 10

01 01 11

01 10 00

01 10 01

01 10 10

01 10 11

01 11 00

01 11 01

01 1110

01 11 11

Ahora vamos a hacer un ‘diccionario’ con los posibles valores de un dato de 23 pares de nibbles(ATGC),el genoma humano,que es la información que enviaremos y corresponderá a una información más amplia de la tabla almacenada en el receptor/emisor.El compresor/decompresor TGV comprimirá y descomprimirá la información en ‘cadenas de ADN/DNA’.Este metodo NO TIENE PERDIDAS DE INFORMACIÓN COMO EL ANTERIOR.

La idea es que el emisor y el receptor del mensaje tengan una tabla con los 'valores de conversión'..snehtuaÆ