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

Archivo:Back.png Volver a la página de la materia

Codigos de Bloque

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

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).

Este documento de codificación y compresión puede servir como complemento para el apunte.

Tipos de codigo

Singularidad

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

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 unequivocamente 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

Definicion: La n-esima extension de un codigo C que codifica cada simbolo Si perteneciente a un alfabeto S con un Xi determinado se denota Cn y corresponde a un codigo que a cada simbolo Oi = {Si1,Si2,...,Sin}, con Sij perteneciente a S, lo codifica con {Xi1,Xi2,...,xin} siendo Xij la codificacion de 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

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).
$\sum _{i}n^{-li}\leq 1$

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

La longitud media de un codigo se define como la sumatoria de los productos entre las probabilidades y longitudes de cada simbolo.
$L=\sum _{i}P_{i}l_{i}$

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.
$H(S)\leq L_{x}$

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

La tasa de informacion R se define como $R=rH(s)$, 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, $R\leq C$.

La capacidad se define como $C=\tau ^{-1}log(n)$, con una señal discreta de n niveles, periodo T y cada simbolo con duracion tau. Por lo tanto, hay $n^{T/\tau }$ estados posibles.

Haciendo operatoria, y suponiendo simbolos equiprobables,
$I_{i}=-log(P_{i})\wedge P_{i}={\frac {1}{n^{T/\tau }}}\longrightarrow I_{i}=T\ \tau *log(n)$
$C=I/T=log(n)/\tau$
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 $n=(1+S/N)^{1/2}$ y que $T/\tau =2bit$.

Ejercicios de parcial relacionados

1) Indicar si la siguiente afirmacion es verdadera o falsa: "Dado un conjunto con X elementos, se pueden armar infinitos codigos univocamente 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 univocamente decodificables (desperdician muchos pero todos tienen longitud múltiplo del original).

2) Un codigo univocamente decodificable que no es instantaneo, ¿trae problemas de interpretacion de la representacion de los simbolos? (Ejercicio correspondiente al 1er parcial del 1er cuatrimestre del 2004)

Esto esta respondido mas arriba en el parrafo donde se explican las desventajas de no tener un codigo instantaneo.

3) Indicar si la siguiente afirmacion es verdadera o falsa: "Dado un codigo optimo para un conjunto de simbolos, se pueden armar 10 codigos mas y que sean diferentes" (Ejercicio correspondiente al recuperatorio del 1er parcial del 2do cuatrimestre del 2004)

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 afirmacion es verdadera o falsa:

a) La entropia de un alfabeto de simbolos es la cota maxima para la longitud promedio de cualquier codificacion del mismo. b) Siempre existe un codigo instantaneo que no sea optimo.

a: Falso. Es la cota mínima para que un codigo sea decodificable. b: No se que es óptimo.

(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

• Coding and Information Theory (Richard W. Hamming)
• The Theory of Information and Coding (R. J. McEliece)