CODIFICACION DE LA FUENTE

Para que se realiza la codificación de la fuente?

Diseñar un sistema de comunicación para transmitir fiablemente (o con la mínima distorsión) un proceso aleatorio (la información).


Cómo se hace esta conversión de la fuente de información.

Aplicando el concepto al cifrado, decimos que un cifrado es 'con umbral' si para descifrar un mensaje se requiere que cooperen un número de entidades superior al umbral requerido. Este tipo de sistemas sólo es posible con clave pública. En estos sistemas el mensaje se cifra usando una clave pública y la clave privada es compartida de tal forma que permite la funcionalidad descrita. La existencia de un volumen oculto puede ser comprometida por implementaciones con elementos criptográficos predecibles o por algunas herramientas forenses que pueden revelar la presencia de datos cifrados no aleatorios. También se sugirió una vulnerabilidad de los volúmenes cifrados por trámite de la prueba de aleatoriedad chi-cuadrado, por la que sería necesaria, después de cada modificación de los datos cifrados, la inclusión de elementos correctivos para llevar el volumen a una condición de aleatoriedad verosímil

Cómo es el esquema de compresión.
En los últimos años se ha dado un aumento tanto de la capacidad de almacenamiento de datos como en la velocidad de procesamiento en las computadoras. Junto con esto, la tendencia es la disminución de costos en memoria principal y secundaria así como también un aumento de velocidad de estos dispositivos de almacenamiento. Estos acontecimientos ponen en cuestionamiento la necesidad de compresión de datos. Sin embargo, el auge que últimamente han tenido las redes de computadoras, demanda más prestaciones que están por encima de las posibilidades reales. El principal problema al que se enfrentan las redes de comunicación es la velocidad de transferencia de datos. El cambio a mayores velocidades no es tarea fácil, básicamente por razones como la no factibilidad de realizar cambios de infraestructura en las grandes Métodos de Compresión Métodos de Compresión: Diciembre de 2003 compañías de redes WAN (cableado, tecnologías, etc.) así como la falta de tecnología que acepte unas velocidades muy elevadas de transmisión.

Codificación de Huffman

La codificación de Huffman [H52] es un método propuesto en 1952 por David Huffman. La idea detrás de la codificación de Huffman es asignar códigos binarios lo más cortos posibles a aquellos símbolos que ocurren con mayor frecuencia en los datos. Los símbolos con poca frecuencia tendrán asignado códigos binarios de longitud más grande. El óptimo desempeño del algoritmo se consigue cuando el número de bits asignado a cada carácter es proporcional al logaritmo de la probabilidad de mismo.  

1) Si la lista contiene un solo nodo, terminar 

2) Los dos nodos (L y R) de la lista con las probabilidades más pequeñas se seleccionan. 

3) Se crea un nodo intermedio (F) y se construye un subárbol siendo F el padre, L y R los hijos izquierdo y derecho respectivamente. El arco entre los nodos F y L se etiquetan como 0 y el arco entre los nodos F y R se etiqueta como 1. 

4) F es agregado a la lista ordenada con valor de probabilidad igual a la suma de las probabilidades de L y R.

Codificación Aritmética 

Codificación aritmética [WNC87] es una técnica que obtiene excelente razón de compresión, aunque es un método lentota que requiere por lo menos de una multiplicación por cada símbolo de entrada. En teoría, la codificación aritmética asigna un único codeword a cada posible conjunto de datos. La compresión aritmética se basan también en las probabilidades de ocurrencia de los mensajes emitidos por la fuente de información. Se basa en la representación de un valor del intervalo [0,1] con más decimales (más precisión) cuanto más información contengan los datos a comprimir. La codificación aritmética se realiza siguiendo los pasos siguientes: 

1. Inicialmente, el intervalo actual es [L, H) = [0, 1) 

2. Para cada símbolo s en la entrada se realizan dos acciones: a. El intervalo actual se subdivide en subintervalos. El tamaño del subintervalo es proporcional a la probabilidad estimada de los símbolos. b. Se selecciona el subintervalo que corresponde a s, este intervalo es ahora el intervalo actual. 

3. Cuando el archivo se ha procesado, la salida final como resultado de la compresión es un número dentro del intervalo actual, generalmente, aquel que ocupe menos bits

Métodos substitucionales o basados en diccionario.  

Los métodos basados en diccionario usan el principio de remplazar cadenas de datos con codewords que identifican a esa cadena dentro de un diccionario [WMB99].    El diccionario contiene una lista de subcadenas y codewords asociados a cada una de ellas. El diccionario que contiene las cadenas de símbolos puede ser estático o adaptable (dinámico). Los métodos basados en diccionario, a diferencia de los métodos estadísticos, usan codewords de longitud fija y no requieren de las estadísticas de los símbolos para realizar la compresión.  Prácticamente, todos los métodos de compresión sustitucionales están basados en los métodos de compresión desarrollado por Jacob Ziv y Abraham Lempel en los 70s, los métodos LZ77 y LZ78. En ambos métodos una subcadena es remplazada por un apuntador a donde dicha cadena haya ocurrido previamente en el diccionario, el cual, se crea dinámicamente. Las principales diferencias entre los métodos sustitucionales son en como los apuntadores son representados y en las limitaciones que imponen sobre lo que los apuntadores pueden representar.

1. El codificador busca la subcadena más grande en el buffer de búsqueda (de derecha a izquierda) que sea el prefijo del buffer hacia el frente. a. Si tal subcadena existe,  la codificación consiste de una tripleta T = (O, L, C), donde O es la distancia en símbolos desde inicio de la subcadena encontrada hasta el final del buffer de búsqueda, L es la longitud de la subcadena encontrada y C es el símbolo siguiente a la subcadena encontrada en el buffer hacia el frente. b. Si la cadena no existe, O y L son puestos a cero y C es el primer símbolo del buffer hacia el frente (en la figura 2. 4, el símbolo ak+n+1). 

2. Ambos buffers se recorren hacia la izquierda L + 1 posiciones