Rendimiento y redundancia de un código y Longitud media de un código y Códigos compactos

Que representa la longitud media de un código?

Longitud media de un código de la fuente S, L no puede ser inferior a H(S). Según esto, se define el rendimiento de un código. 

La longitud media de un código cómo se la alcanza?

La longitud media de un código se define como la sumatoria de los productos entre las probabilidades y longitudes de cada símbolo. 

L=∑iPili

Los códigos compactos son:

Inequívocamente descifrables y no tienen redundancia, pero, como se dijo en el apartado donde fueron tratados estos códigos, presentan el inconveniente de que la distribución de la fuente puede no ser conocida cuando se diseña el código.

La codificación de códigos compactos consiste en?

Detectar de errores, son capaces de detectar muchas combinaciones. Su implementación práctica es sencilla, son muy usados, pero también se deben agregar bits de redundancia aumentando el número de bits del mensaje que se desea transmitir.

Que inconveniente presentan estos códigos?

Los códigos de bloque suelen tener limitada capacidad de corrección de errores alrededor de 1 o 2 bits erróneos por palabra de código. Son códigos de bajo rendimiento debido a que tienen una gran redundancia (una palabra de código de Hamming tiene más bits de paridad que de información). Se podría pensar que si el número de bits de paridad es incrementado esto debería posibilitar la corrección de más y más errores. Sin embargo, agregando más y más bits de paridad, el ancho de banda aumenta igualmente

Dentro de lo codificación de códigos compactos cómo se define la tasa de información?

La tasa de informacion R se define como 

R=rH(s)$$R=rH(s)$$

, donde r son símbolos por segundo. Rse mide en bits (de informacion) por segundo.

El teorema de Shannon indica que para transmitir sin errores debe valer que la tasa de informacion sea menor o igual a la capacidad del enlace, o sea, 

R≤C$$R\le C$$

.

La Capacidad se define como?

La capacidad se define como 

C=IT=log(n)τ$$$$

, con una señal discreta de n niveles, 

Mediante un análisis corto rxplique Cómo funciona El código morse?

El código morse es difícil de aprender por lo que, para facilitar su aprendizaje, se suele utilizar una regla mnemotécnica que permite aprendérselo mediante un código consistente en asignar a cada letra una palabra clave determinada, que comienza con la letra que se quiere recordar. Luego, basta con sustituir cada vocal de la palabra clave por un punto o una raya según la siguiente regla:

• La inicial de la palabra clave es la letra correspondiente.
• El número de vocales que contiene la palabra clave indica la longitud de la codificación en morse de dicha letra.
• Si la vocal es una O se sustituye por una raya (-)
• Si se trata de cualquier otra vocal se sustituye por un punto (·)
• Al sustituir, solo se tendrá en cuenta los puntos y rayas obtenidos hasta la totalidad de la longitud en morse.

Utilizando recursos de la web, traduzca el siguiente texto a morse

"Código no Singular 

Se denomina código no singular a aquel código bloque en el cual a cada símbolo codificado le corresponde una única codificación. 

El código ASCII es un ejemplo de este tipo de código. "

-.-. -.. .. --. --- / -. --- / ... .. -. --. ..- .-.. .- .-. / ... . / -.. . -. --- -- .. -. .- / -.-. -.. .. --. --- / -. --- / ... .. -. --. ..- .-.. .- .-. / .- / .- --.- ..- . .-.. / -.-. -.. .. --. --- / -... .-.. --- --.- ..- . / . -. / . .-.. / -.-. ..- .- .-.. / .- / -.-. .- -.. .- / ... -- -... --- .-.. --- / -.-. --- -.. .. ..-. .. -.-. .- -.. --- / .-.. . / -.-. --- .-. .-. . ... .--. --- -. -.. . / ..- -. .- / -. .. -.-. .- / -.-. --- -.. .. ..-. .. -.-. .- -.-. .. -. .-.-.- / . .-.. / -.-. -.. .. --. --- / .- ... -.-. .. .. / . ... / ..- -. / . .--- . -- .--. .-.. --- / -.. . / . ... - . / - .. .--. --- / -.. . / -.-. -.. .. --. --- .-.-.- .-.-.

RENDIMIENTO Y REDUNDANCIA DE UN CÓDIGO Y LONGITUD MEDIA DE UN CÓDIGO

Cuál es el objetivo de la codificación?

La codificación es la operación que permite pasar del alfabeto fuente al alfabeto código. 

Los códigos que deben tener propiedades?

Esta definición es demasiado general para el estudio de la codificación, por lo tanto se tendrá en cuenta sólo aquellos códigos que posean ciertas propiedades suplementarias.

Qué constituye la primera propiedad de código?

La primera de estas propiedades es que el código constituya un bloque. Esto es un código que asigna cada uno de los símbolos del alfabeto fuente S a una secuencia fija del alfabeto código X. Esas secuencias fijas (secuencias de xj) reciben el nombre de palabras código. Se denominará Xi a la palabra de código que corresponde al símbolo si. Hay que notar que Xi constituye una secuencia de xj ‘s.1

La segunda propiedad a que se refiere exactamente, cuál es su tabla de descripción?

La segunda propiedad es que todas las palabras Xi sean distintas, lo que se denomina no singular. Se denomina código no singular aquel bloque de código en el cual a cada símbolo codificado le corresponde una única codificación.
Qué constituye la primera propiedad de código?

La tercera propiedad que objetivo debe cumplir, que tabla debe ordenarse para cumplir en esta tercera propiedad?

La tercera de las propiedades es que el código sea unívocamente decodificable. Para poder definir esta propiedad, se necesita conocer una nueva definición. La extensión de orden n de un bloque de código que hace corresponder los símbolos si con las palabras de código Xi , es el bloque de código que hace corresponder las secuencias de símbolos de la fuente (si1, si2,......., sin) con las secuencias de las palabras de código (Xi1, Xi2, ......, Xin).

A través de un ordenador gráfico, indique los distintas clases de códigos que se utilizan.Cuál es el propósito de la decodificación?

Cuál es el propósito de la decodificación?

Un canal de información viene determinado por un alfabeto de entrada A = {a1, a2, ......., ar}; un alfabeto de salida B = {b1,b2, ......., bs}; y un conjunto de probabilidades condicionales P(bj/ai). P(bj/ai) es la probabilidad de recibir a la salida el símbolo bj cuando se envía el símbolo de entrada ai.

Cuál es la probabilidad de error y sus reglas de dicisión?

Considerando un canal con un alfabeto de entrada A = {a1, a2, ...., ar} y un alfabeto de salida B = {b1, b2, ...., bs}, se denomina regla de decisión, d(bj) a la función que especifica el símbolo de entrada único que corresponde a cada símbolo de salida: d(bj) = ai . Un canal de r entradas y s salidas admite rs reglas de decisión diferentes. Se elegirá la regla de decisión que haga mínima la probabilidad de error. 

La posibilidad de error de un canal será mínima con la regla de decisión que asigna a cada símbolo de salida el símbolo de entrada de mayor probabilidad. 

Cuál es el primer teorema de Shannon?

El primer teorema de Shannon demuestra la existencia de una unidad común con la que puede medirse cualquier fuente de información. El valor de símbolo de una fuente S puede definirse en términos del número equivalente de dígitos binarios necesario para representarlo. El teorema establece que el valor medio de un símbolo S es H(S), llamado entropía de la fuente. 

Qué objetivo persigue el rendimiento y redundancia de un código?

La redundancia es la información superflua o innecesaria para interpretar el significado de los datos originales. La introducción de redundancia en la codificación tiene como finalidad mejorar la fiabilidad de la transmisión. 

R = 1−η

A que se refiere la longitud media de un código de la fuente?

Supongamos que L es la longitud media de un código de la fuente S, L no puede ser inferior a H(S). 

Con que formula se refiere el rendimiento de un código?

COMPRESION RLE

Cómo se realiza el proceso de compresión de imágenes RLE.

RLE es un candidato natural para la compresión de datos gráficos. Una imagen digital, se compone de pequeños puntos llamados píxeles. Cada píxel puede ocupar, uno o varios bits; con un bit, sólo se pueden representar dos colores —normalmente blanco o negro—; con n bits por píxel, el número de tonalidades disponibles aumenta a 2n, colores o tonos de gris. Suponemos que los píxeles se almacenan en la memoria en una matriz llamada mapa de bits (bitmap); en la cual, por lo tanto, se tienen los datos de entrada de la imagen. Los píxeles se disponen normalmente en el mapa de bits en líneas de exploración (scan lines), de manera que el primer píxel del mapa de bits, es el punto situado en la esquina superior izquierda de la imagen, y el último, es el situado en la esquina inferior derecha.

La compresión de una imagen mediante RLE, se basa en la observación de que, al seleccionar un píxel de la imagen al azar, existe una probabilidad muy alta de encontrar otros adyacentes a él —sus vecinos— con el mismo color.

Ejercicio 1.3

¿Cuál sería el archivo comprimido para el siguiente bitmap de 6 × 8?

6, 8, 0, 1, 3, 1, 4, 1, 3, 1, 4, 1, 3, 1, 4, 1, 3, 1, 2, 2, 2, 2, 6, 1, 1. Los dos primeros, son la resolución del bitmap (6 × 8). El siguiente, indica que el primer píxel es negro. Si se almacenan usando un byte por número, el tamaño es de 25 bytes —en comparación con el del mapa de bits de tan sólo 6 × 8 bits = 6 bytes—. El método no funciona con imágenes pequeñas.

Cómo se ejemplifica el proceso para la compresión de imágenes en escala de gris

RLE también puede utilizarse para comprimir imágenes en escala de grises. Cada bloque (run) de píxeles con la misma intensidad (nivel de gris) se codifica como un par (run length, valor del píxel).

El run length, ocupa normalmente un byte, lo que permite secuencias de hasta 255 píxeles. El valor del píxel ocupa varios bits, dependiendo del número de niveles de gris (típicamente, entre 4 y 8 bits).

Cómo son las formas de muestreo en RLE.

Ejercicio 1.4  

 Hay otra razón obvia, por la que cada fila de un bitmap debería ser codificada individualmente. ¿Cuál es?

El método RLE para imágenes se basa en la idea de que los píxeles adyacentes tienden a ser idénticos. No es común que el último píxel de una fila sea idéntico al primer píxel de la fila siguiente.

Explique el algoritmo RLE como trabaja para su funcionamiento.

La desventaja del algoritmo RLE para imágenes consiste en que cuando se modifica la imagen, normalmente los run lengths tienen que ser reconstruidos por completo. La salida proporcionada por el método RLE en imágenes complejas, a veces puede ser más grande que el almacenamiento de la imagen sin comprimir (i.e., una imagen sin comprimir —un volcado píxel a píxel del bitmap original—).

Codificar el algoritmo de compresión RLE

Compilar el algoritmo de compresión RLE

VISUAL STUDIO

JAVA

TÉCNICAS DE CODIFICACIÓN DE LA FUENTE

CÓDIGO BRAILLE:

Este conocido código, que permite a los ciegos a leer, fue desarrollado por Louis Braille en 1820, y después de haber sido modificado varias veces, todavía se sigue utilizando hoy en día. Hay disponibles muchos libros en Braille en el National Braille Press. El código Braille se compone de grupos (o celdas) de 3 × 2 puntos cada una, con relieve en papel grueso. Cada uno de los 6 puntos de un grupo pueden ser planos o elevados, lo que implica que el contenido de la información de un grupo es equivalente a 6 bits, siendo posibles por ello un total de 2^6 = 64 grupos

resolver el ejercicio 1.1

Encuéntrense frases redundantes que formen parte de la vida cotidiana.

:(1) hacer una pregunta, (2) es absolutamente necesario, (3) con previo aviso, (4) punto de ebullición caliente, (5) subir, (6) un examen riguroso, (7) exactamente lo mismo, (8) obsequio, (9) calentador de agua, (10) mi opinión personal, (11) recién nacido, (12) aplazado hasta más tarde, (13) sorpresa inesperada, (14) misterios sin resolver

COMPRENSIÓN IRREVERSIBLE DE TEXTO

Algunas veces, es aceptable “comprimir” texto, simplemente desechando alguna información. Esto se conoce como compresión irreversible de texto o compactación. El texto es comprimido no es idéntico al original, por lo que estos métodos no son de propósito general; sólo pueden utilizarse en casos especiales.

En casos extremos, todos los caracteres, excepto letras y espacios, pueden ser despreciados, y se puede convertir todo el texto, a mayúsculas o minúsculas, reduciendo así el número de signos a codificar.

resolver el ejercicio 1.2

Un conjunto de caracteres que incluya las 26 letras en mayúsculas y el espacio, puede ser codificado con códigos de 5 bits, pero dejaría cinco códigos sin usar. Sugiérase una forma de utilizarlos.

Una forma razonable de utilizarlos es codificar las cinco cadenas más frecuentes en el texto.

Debido a que la compresión irreversible de texto es un método de propósito particular, el usuario puede saber qué cadenas son las más comunes en el flujo de datos a comprimir; tiene que proporcionárselas al codificador y además debe escribirlas al principio de la secuencia de salida (para el uso del decodificador)

Compresión del texto Ad hoc

A continuación, mostramos algunas sencillas e intuitivas ideas para aquellos casos en los que la compresión debe ser reversible (sin pérdidas):

Si el texto contiene muchos espacios, pero no están agrupados, se pueden eliminar; sus posiciones, se indican entonces mediante una cadena de bits, que contiene un 0 por cada carácter del texto que no es un espacio y un 1 por cada espacio. Por lo tanto, el texto

Utilice un organizador o tabla para conocer el código

CODIFICACIÓN RUN-LENGHT

La idea básica de este método es la siguiente: Si un dato d aparece n veces consecutivas en el flujo de entrada, se cambian las n ocurrencias con el par único nd. Las n apariciones consecutivas de un elemento de datos se llama run length9 de n, y este enfoque para la compresión de datos se llama codificación run-length o RLE. Aplicamos esta primera idea a la compresión de texto y luego a la compresión de imágenes.

 

COMPRESIÓN DE TEXTO RLE.

El reemplazo exacto de 2.⊔all⊔is⊔too⊔well con 2.⊔a2⊔is⊔t2⊔we2, es ambiguo y no funciona

. Claramente, el descompresor debería tener una manera de expresar que el primer 2 es parte del texto, mientras que los demás indican el número de repeticiones de las letras o y l. Incluso la cadena 2.⊔a2l⊔is⊔t2o⊔we2l, sigue sin resolver este problema (y además no proporciona compresión alguna). Un camino para resolver este problema es preceder cada repetición con un carácter especial de cambio de código (o código de escape). Si usamos @ como carácter de cambio de código, entonces la cadena 2.⊔a@2l⊔is⊔t@2o⊔we@2l, puede ser descomprimida sin ambigüedad. Sin embargo, esta cadena es más larga que la original, ya que sustituye dos letras consecutivas, con tres caracteres. Tenemos que adoptar la convención de que sólo se reemplacen por un factor de repetición, aquellos grupos compuestos por tres o más repeticiones de un mismo carácter. La Figura 1.6a es un diagrama de flujo, que explica el funcionamiento de un sencillo compresor de texto run-length.

 

CODIFICACIÓN RELATIVA

Esta es otra variante, a veces llamada diferenciación ([Gottlieb et al. 75]). Se utiliza cuando los datos a comprimir, están formados por una serie de números que no difieren en mucho entre sí (e.g., en la telemetría); o bien cuando se componen de cadenas similares. El último caso, se utiliza en la compresión de datos para envío por fax descrita en la Sección 2.13 y también en la compresión LZW

 En la telemetría, se utiliza un detector para recopilar datos a determinados intervalos y transmitirlos a una central para su posterior procesamiento. Un ejemplo, es el estudio de la temperatura de un lugar, en el que se realizan mediciones cada hora. Dos temperaturas sucesivas, no difieren mucho normalmente, por lo que el sensor necesita enviar sólo la primera de ellas, seguida por las diferencias.

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