Apunte de tipos de codigos (Teoría de las Comunicaciones)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Codigos de Bloque[editar]

Los codigos de bloque son aquellos tales que, si se tiene un alfabeto fuente S = {s1,...,sk} y un alfabeto codigo X = {x1,...,xn} (es decir, S se codifica con elementos de X) vale que cada simbolo de S se codifica con una secuencia de X.

Un ejemplo de codigo NO bloque seria aquel en que no haya codificacion para el s1 solo, sino que haya codificaciones distintas para s1s1, s1s2, s1s2s5, etc.

Longitud Fija vs Variable[editar]

Existen dos tipos de codigos, los de longitud fija y los de longitud variable. Al momento de comprimir, los primeros se comportan bien solo cuando todos los simbolos tienen la misma probabilidad (suponiendo ademas que se emplea una longitud minima). En cambio, los segundos pueden permitir asignar cadenas mas cortas a los simbolos mas probables y mas largas a los menos probables.

Al usar codigos de longitud variables surge el problema de la decodificación, que era trivial cuando los codigos eran de longitud fija (examinar una cantidad de bits equivalente a la longitud empleada y ver que simbolo representa).

Tipos de codigo[editar]

Singularidad[editar]

Definicion: Un codigo de longitud variable se dice no singular cuando todos los simbolos reciben una codificacion distinta. Mas formalmente: sea C un codigo que codifica a cada simbolo Si perteneciente a un alfabeto S con un Xi determinado. C es no singular si y solo si Xi es distinto de Xj para i distinto de j.

Ejemplo

C:

S1 ~> 0
S2 ~> 00
S3 ~> 11
S4 ~> 01

C':

S1 ~> 0
S2 ~> 0
S3 ~> 11
S4 ~> 01

Dada la definicion, C es no singular mientras que C' es singular.

Es de esperarse que si se comprime usando codigos singulares habra perdida de informacion pero en ciertos contextos como la compresion de archivos multimedia esto puede llegar a ser aceptable.

Decodificación unívoca[editar]

Definicion: Un codigo de longitud variable se dice unequivocamente decodificable si cada texto codificado con el mismo posee una unica interpretacion.

Ejemplo

C:

S1 ~> 0
S2 ~> 01
S3 ~> 11
S4 ~> 00

C':

S1 ~> 1
S2 ~> 01
S3 ~> 001
S4 ~> 0001

C":

S1 ~> 00
S2 ~> 01
S3 ~> 10
S4 ~> 11

C no es univocamente identificable ya que el texto 0011 puede ser interpretado como S4S3 o como S1S1S3. C' es univocamente decodificable ya que el uno es siempre usado como "separador". C" es univocamente decodificable por ser de longitud fija.

Extensiones enésimas[editar]

Definicion: Sea C una codificación de un alfabeto S, tal que para Si perteneciente a S se define un Xi. Se define Cn como la n-esima extension de ese codigo al conjunto {Xi1,Xi2,...,Xin}, donde cada Xij es la codificacion de un Sij en C.

Propiedad: Un codigo C es univocamente decodificable si y solo si Cn es no singular para todo n.

Ejemplo 3

C:

S1 ~> 0
S2 ~> 10
S3 ~> 101

C2 (2-esima extension de C):

S1S1 ~> 00
S1S2 ~> 010
S1S3 ~> 0101

S2S1 ~> 100
S2S2 ~> 1010
S2S3 ~> 10101

S3S1 ~> 1010
S3S2 ~> 10110
S3S3 ~> 101101

Como S2S2 y S3S1 reciben la misma codificacion, concluimos que C2 es singular. Luego C no es univocamente decodificable.

Código instantáneo[editar]

Definicion: Un codigo de longitud variable se dice instantaneo (o libre de contexto) si en cualquier texto codificado con el se puede decodificar cada uno de los simbolos solo a partir de los bits que lo codifican y no de los que lo preceden o suceden.

Propiedad: Sea C un codigo que codifica a cada simbolo Si perteneciente a un alfabeto S con un Xi determinado. C es un codigo instantaneo si y solo si Xi no es prefijo de Xj para i distinto de j.

Inecuación de Kraft: Da una condición necesaria y suficiente para la existencia de un código instantáneo con palabras de longitud l1,...,lk; con i los simbolos del alfabeto fuente y n la cantidad de simbolos del alfabeto codigo (2 para una fuente binaria).

Ejemplo

C:

S1 ~> 0
S2 ~> 01
S3 ~> 011
S4 ~> 111

C':

S1 ~> 0
S2 ~> 10
S3 ~> 110
S4 ~> 1110
S5 ~> 1111

C es univocamente identificable pero no es instantaneo (considerese el texto 0111111 correspondiente a S1S4S4) mientras que C' si lo es.

Cuando estamos emitiendo un texto codificado y el codigo es instantaneo, el receptor puede ir decodificandolo a medida que lo recibe. En caso contrario, cuando el codigo no es instantaneo, el receptor deberia esperar a recibirlo entero para recien poder empezar a decodificarlo. Ademas de esta demora en si, el receptor puede eventualmente quedarse sin espacio de almacenamiento (al momento de decodificar).

Por ultimo, observar que todos los codigos univocamente decodificables son no singulares y todos los codigos instantaneos son univocamente decodificables (y por ende tambien no singulares).

Codigos Compactos u Optimos[editar]

La longitud media de un codigo se define como la sumatoria de los productos entre las probabilidades y longitudes de cada simbolo.

Un código se dice compacto u óptimo si es unívocamente decodificable y es de longitud media mínima (respecto a todos los demás códigos univocos sobre los mismos alfabetos fuente y codigo).

Además, vale la siguiente desigualdad para que cualquier codigo sea univocamente decodificable.

Esto explica por que se desea reducir la entropia (la cual es relativa segun como se analice el texto) para lograr una codificacion de menor longitud.

Tasa de informacion[editar]

La tasa de informacion R se define como , donde r son símbolos por segundo. R se 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, .

La capacidad se define como , con una señal discreta de n niveles, periodo T y cada simbolo con duracion tau. Por lo tanto, hay estados posibles, donde la probabilidad de cada uno es la inversa de dicha cantidad.

Haciendo operatoria, y suponiendo simbolos equiprobables,


donde C es la cantidad de informacion en el periodo T.

De alli es posible deducir el teorema de Shannon en su forma conocida, sabiendo que en una fuente analogica vale y que , y que la capacidad de un canal es el doble del ancho de banda por Nyquist.

Ejercicios de parcial relacionados[editar]

1) Indicar si la siguiente afirmación es verdadera o falsa: "Dado un conjunto con X elementos, se pueden armar infinitos códigos unívocamente codificables" (Ejercicio correspondiente al 1er parcial del 2do cuatrimestre del 2004).

Verdadero: Puedo codificar trivialmente con X elementos de longitud fija max{X}. Después si hago las extensiones enésimas tengo infinitos códigos unívocamente decodificables (desperdician muchos pero todos tienen longitud múltiplo del original).

2) Un código unívocamente decodificable que no es instantáneo, ¿trae problemas de interpretación de la representación de los símbolos? (Ejercicio correspondiente al 1er parcial del 1er cuatrimestre del 2004)

Esto esta respondido mas arriba en el párrafo donde se explican las desventajas de no tener un código instantáneo.

3) Indicar si la siguiente afirmación es verdadera o falsa: "Dado un código óptimo para un conjunto de símbolos, se pueden armar 10 códigos mas y que sean diferentes" (Ejercicio correspondiente al recuperatorio del 1er parcial del 2do cuatrimestre del 2004)

Es cierto, partimos de que el código es óptimo, es decir, es unívocamente decodificable y L (long media del codigo) es mínimo, usamos la parte de que es unívocamente decodificable, es decir su extensión de orden n es no singular, es decir, todas las palabras diferentes. Se puede usar una extension de orden 3 , esto me genera 9 codigos mas, como son todos diferentes (porque la extension es no singular) listo.

4) Indicar si la siguiente afirmacion es verdadera o falsa: "Dado un codigo univocamente codificable, se pueden obtener infinitos codigos univocamente decodificables a partir de el." (Ejercicio correspondiente al 1er parcial del 2do cuatrimestre del 2005).

Verdadero: Puedo hacer la extensión enésima del código y será univocamente decodificable.

5) Indicar si la siguiente afirmación es verdadera o falsa:

a) La entropía de un alfabeto de símbolos es la cota máxima para la longitud promedio de cualquier codificación del mismo. b) Siempre existe un código instantáneo que no sea optimo. a: Falso. Es la cota mínima para que un codigo sea decodificable. b: Óptimo, también conocido como compacto,

Unívocamente decodificable y de longitud media mínima. la pregunta es rara, si existe uno siempre existirá... eje: tiene long media mínima pero no es decodificable.

No unívocamente decodificable y de longitud media mínima.'

C:

S1 ~> 0
S2 ~> 0


(Ejercicio correspondiente al recuperatorio del 1er parcial del 1er cuatrimestre del 2005)

6) Un compresor es un programa que toma una entrada (que podemos suponer formada por el alfabeto ASCII de 256 simbolos) y la codifica con el objetivo de lograr una salida de longitud promedio menor a 8 binits/simbolo. Buscando un algoritmo de compresion sin perdida, un proveedor ofrece un algoritmo capaz de reducir en 20% el tamaño de cualquier archivo de entrada. ¿Es esto posible? Justifique relacionando su respuesta con teoria de la informacion (Ejercicio correspondiente al 1er parcial del 1er cuatrimestre del 2006).

7) ¿Que define la entropia cuando es maxima? De un ejemplo de una fuente de H maxima = 1 bits/simbolo (Ejercicio correspondiente al 1er parcial del recuperatorio del 1er cuatrimestre del 2006).

La entropia H(S) de una fuente S es maxima si y solo si los simbolos Si que provee la fuente son equiprobables. Esto ocurrira cuando P(Si) = 1/q siendo q la cantidad de simbolos de S. El ejemplo pedido: sea la fuente S = {0,1} tal que P(0) = P(1) = 1/2. Entonces H(S) = - 1/2 * log(1/2) - 1/2 * log(1/2) = 1.

8) Se tiene una fuente de memoria nula con las siguientes probabilidades:

  • P(S1) = 0,6
  • P(S2) = 0,1
  • P(S3) = 0,1
  • P(S4) = 0,1
  • P(S5) = 0,05
  • P(S6) = 0,05

Codifique la salida de la fuente usando menos de 1,8 binits/simbolo.

(Ejercicio correspondiente al 1er parcial del 2do cuatrimestre del 2006)

Bibliografia y further-reading[editar]