2. Códigos sin ruido

Abril 29, 2012

Índice

Conjuntos libres de prefijo

Códigos Instantáneos


 

Conjuntos libres de prefijo

Definición: $\text{bin}:\mathbb N_+\to \{0,1\}^*$ es la función que asigna a cada $n$ la representación binaria del número $n+1$ sin el 1 lider.

Nota: $\text{bin}$ es una enumeración de $ \{0,1\}^*$, donde $0\to\lambda, 1\to 0, 2\to 1, 3\to 00, 4\to 01, 5\to 10, 6\to 11,\dots$.

Definición: $\log n=|\text{bin}(n)|.$

Definición: $x\in A^*$ es prefijo de $y\in A^*$ si existe $z\in A^*$ tal que $y=xz$. Escribimos $x<_p y$. $S\subset A^*$ es libre de prefijo si para todo $x,y\in S$, $x<_py$ implica que $x=y$.

Ejemplo: El conjunto $S=\{ a_1^ia_2a_3^i: i\geq 1\}$ es libre de prefijo sobre el alfabeto $\{a_1,a_2,a_3\}$.

El conjunto $S=\{1^i0: i\geq 1\}$ es una representación de $\mathbb N$ mediante un conjunto libre de prefijo: $n\to 1^n0$ es la identificación entre ellos.

Podemos encontrar representaciones mejores:

Teorema: La aplicación $n\in \mathbb N_+\to 1^{\log n} 0 \text{bin}(n)$ representa $\mathbb N$ mediante un conjunto libre de prefijo $S$, donde cada natural es representado por una cadena de $2\log n+1$ bits.

Definición: Para cada $x\in\{0,1\}^*$, $\overline x$ es la cadena obtenida a partir de $x$ insertando un 0 enfrente de cada bit de $x$, y finalmente añadiendo un 1; $\overline \lambda =1.$

Ejemplo: $\overline{10}=01001, \overline{11}=01011.$

Nota: Es claro que $|\overline x |=2 \, |x|+1$.

Definición: $d(x)=\overline{\text{bin}(|x|)}x$, para todo $x\in A*$.

Ejemplo: $d(0101)=\overline{\text{bin}(4)}0101=\overline{01}0101=000110101.$

Teorema: El conjunto $S=\{d(x): x\in \{0,1\}^*\}$ es libre de prefijo

Nota: La aplicación $x\to d(x)$ representa $A^*$ mediante un conjunto libre de prefijo $S\subset A^*$, de modo que $|d(x)|=|x|+2|\log x|+1$. Consecuentemente, cada número natural $n>0$ tiene una representación en $S$ con $\log n +2\log\log n +1 $ bits.

Códigos instantáneos

Sean $Y=\{y_1,\dots,y_N\}$, $A=\{a_1,\dots,a_Q\}$ dos alfabetos tal que $2\leq Q<N$.

Definición: Un código es una aplicación inyectiva $\varphi: Y\to A^*$. Los elementos de $\varphi(Y)$ son las cadenas-código o palabras-código. Un código instantáneo o libre de prefijo es un código $\varphi$ tal que $\varphi(Y)$ es libre de prefijo.

Ejemplo: Sea $Y=\{y_1,y_2,y_3,y_4\}$ y $A=\{0,1\}$. La aplicación $\varphi_1$:
$$\varphi_1(y_1)=00,\varphi_1(y_2)=01,\varphi_1(y_3)=10,\varphi_1(y_4)=11,$$
es un código libre de prefijo.

Ejemploa: Sea $Y=\{y_1,y_2,y_3,y_4\}$ y $A=\{0,1\}$. La aplicación $\varphi_2$:
$$\varphi_2(y_1)=10,\varphi_2(y_2)=110,\varphi_2(y_3)=1110,\varphi_2(y_4)=11110,$$
es un código libre de prefijo.

Ejemplo: Sea $Y=\{y_1,y_2,y_3,y_4\}$ y $A=\{0,1\}$. La aplicación $\varphi_3$:
$$\varphi_3(y_1)=10,\varphi_3(y_2)=10,\varphi_3(y_3)=110,\varphi_3(y_4)=1110,$$
no es un código.

Ejemplo: Sea $Y=\{y_1,y_2,y_3,y_4\}$ y $A=\{0,1\}$. La aplicación $\varphi_4$:
$$\varphi_4(y_1)=01,\varphi_4(y_2)=011,\varphi_4(y_3)=0111,\varphi_4(y_4)=01111,$$
no es un código libre de prefijo, pero sí es un código.

Definición: Un código es unívocamente decodificable si la extensión de $\varphi$ a $Y^*$ es inyectiva.

Ejemplo: La secuencia $0010001101$ en el código $\varphi_1$ se descompone en las palabras $00,10,00,11,01$ y se decodifica en la palabra $y_1y_3y_1y_4y_2$.

Nota: No todo código unívocamente decodificable es instantáneo como es el caso del ejemplo $\varphi_4$.

Nota: La ventaja de los códigos libres de prefijo es que se pueden decodificar sobre la marcha, puesto que el final de una cadena-código se reconoce inmediatamente y las siguientes partes del mensaje no tienen que ser observados antes de que la codificación empiece.

Teorema: [Kraft] Sean $(n_i)_{i=1}^N$ enteros positivos. Estos números son las longitudes de las cadenas-código de un código instantáneo $\varphi: Y\to A^*$ si y solo si $\displaystyle \sum_{j=1}^N Q^{-n_j}\leq 1$.

Demostración: Sea $\varphi:Y\to A^*$ un código instantáneo tal que $|\varphi(y_i)|=n_i$, $1\leq i\leq N$. Sea $r_i$ el número de cadenas de longitud $i$. Claramente $r_j=0$ si $j>m=\max\{n_1,\dots,n_N\}.$ Como el código es instantáneo:
$$\begin{aligned}
r_1&\leq Q\\
r_2&\leq (Q-r_1)Q=Q^2-r_1Q\\
r_3&\leq ((Q-r_1)Q-r_2)Q=Q^3-r_1Q^2-r_2Q\\
& \,\,\, \vdots\\
r_m& \leq Q^m-r_1Q^{m-1}-r_2Q^{m-2}-\dots-r_{m-1}Q.
\end{aligned}
$$
Diviendo la última desigualdad por $Q^m$ tenemos
$$\sum_{i=1}^m r_i Q^{-i}\leq 1.$$
Ahora
$$\sum_{i=1}^m r_iQ^{-i}=\sum_{j=1}^N Q^{-n_j}\leq 1.$$
Para el rec?­proco, de la desigualdad anterior
$$
\begin{aligned}
r_1Q^{-1} &\leq \sum_{i=1}^m r_i Q^{-i}\leq 1,\\
r_1Q^{-1}+r_2Q^{-2} &\leq \sum_{i=1}^m r_iQ^{-i}\leq 1,\\
& \, \, \, \vdots \\
r_m &\leq Q^m -r_1Q^{m-1}-\dots-r_{m-1}Q,
\end{aligned}
$$
luego tenemos las desigualdades
$$
\begin{aligned}
r_1 &\leq Q\\
r_2 &\leq (Q-r_1)Q\\
r_3 &\leq Q^3 -r_1Q^2-r_2Q\\
&\, \, \, \vdots \\
r_m & \leq Q^m-r_1Q^{m-1}-\dots -r_{m-1}Q,
\end{aligned}
$$
mostrando que existen los elementos suficientes para construir un código instantáneo cuyas cadenas tengan longitudes $n_1,\dots,n_N$.

Definición: La desigualdad $\displaystyle \sum_{i=1}^N Q^{-n_i}\leq 1$ se llama desigualdad de Kraft.

Nota: El teorema no asegura que todo código que satisfaga la desigualdad sea un código libre de prefijo. Un contraejemplo es el código $\varphi_4$ definido sobre $Y=\{y_1,y_2,y_3,y_4\}$ con valores en $\{0,1\}^*$, cuya definición recordamos:

$$\varphi_4(y_1)=01, \varphi_4(y_2)=011, \varphi_4(y_3)=0111, \varphi_4(y_4)=01111.$$

Teorema: [McMillan] Si un código es unívocamente decodificable con cadenas-código de longitudes $n_1,n_2,\dots,n_N$, entonces la desigualdad de Kraft debe ser satisfecha.

Demostración: Sea $r\in\mathbb N$. Entonces: 

$$\left(\sum_{k=1}^N Q^{-n_k}\right)^r = \sum_{k_1=1}^N \sum_{k_2=1}^N \cdots \sum_{k_r=1}^N Q^{-(n_{k_1}+n_{k_2}+\dots+n_{k_r})}.$$

La suma $n_{k_1}+\dots+n_{k_r}$ es la longitud de una cadena formada por $r$ cadenas-código yuxtapuestas. Al variar los nómeros $k_1,\dots,k_r$ obtenemos todas las posibles longitudes de cadenas formadas por yuxtaposición de $r$ cadenas-códigos. Sea $r_i$ el nómero de secuencias de $r$ cadenas-código yuxtapuestas con un total de $i$ letras. Claramente $r_i=0$ si $i>rm$, donde $m=\{n_1,n_2,\dots,n_N\}$. Así
$$\left(\sum_{K=1}^N Q^{-n_k}\right)^r=\sum_{i=1}^{r m} r_iQ^{-i}$$
Dado que el código es unívocamente codificable toda las secuencias de $r$ cadenas-códigos yuxtapuestas con un total de $i$ letras tienen que ser distintas, esto es $r_i\leq Q^i$ y por lo tanto
$$\sum_{k=1}^N Q^{-n_k}\leq \left(\sum_{i=1}^{rm} 1\right)^{1/r}=(rm)^{1/r}.$$
Tomando límites cuando $r\to+\infty$, la parte de la derecha tiende a uno. Esto termina la prueba del teorema.

Teorema: Todo código unívocamente decodificable puede ser reemplazado por un código libre de prefijo sin cambiar las longitudes de las cadenas-código.

Demostración: Inmediata a partir de los dos teoremas anteriores.

Consideremos un modelo probabilístico para $Y$, esto es, una función $p:Y\to(0,1]$ tal que $$\sum_{i=1}^N p(y_i)=1.$$

Definición: La información contenida en $y_i$ se define $$I(y_i)=-\log_2p(y_i).$$

Definición: Sea $f$ una función real definida sobre $Y$. Se define la esperanza o promedio de $f$: $$\mathbb E(f)=\sum_{k=1}^N p(y_k)f(y_k).$$

Definición: La entropía es el promedio de la información $$\mathcal H=\mathcal H(Y)=-\sum_{k=1}^n p(y_k)\log_2(p(y_k)).$$

Utilizaremos la entropía para estudiar códigos.

Definición: Fijado un modelo probabilístico $p$ sobre $Y$ se define la longitud promedio del código instantáneo $\varphi$ como $$L_\varphi=\sum_{k=1}^N p(y_k) |\varphi(y_k)|.$$

Teorema: [Shannon] Sea $\varphi: Y\to A^*$ un código instantáneo y $p$ un modelo probabilístico sobre $Y$. Entonces: $$L_\varphi\geq \frac{\mathcal H(Y)}{\log_2 Q}$$

Demostración: Primero vamos a demostrar que dados $c_1,\dots, c_N, q_1,\dots , q_N$ números reales tal que $\displaystyle \sum_{i=1}^N q_i=1$ se tiene que
$$\sum_{i=1}^N q_ic_i \geq \prod_{k=1}^N c_i^{q_i}.$$
Dado que $\log_2(x)$ es cóncava
$$\log_2\left(\sum_{i=1}^N q_ic_i\right)\geq \sum_{i=1}^N q_i\log (c_i)=\log_2\left(\prod_{i=1}^N c_i^{q_i}\right)$$
y como $\log_2(x)$ es creciente, la desigualdad está demostrada.

Sean ahora $p_i,q_i$, $1\leq i\leq N$, todos ellos números positivos, tales que
$$\sum_{i=1}^N p_i=\sum_{i=1}^N q_i=1$$
Probemos que
$$-\sum_{i=1}^N q_i\log_2 p_i\geq -\sum_{i=1}^N q_i \log_2 q_i.$$
Pongamos $c_i=p_iq_i^{-1}$ y apliquemos la desigualdad probada anteriormente:
$$\sum_{i=1}^N q_i c_i \geq \prod_{i=1}^N c_i^{q_i}$$
luego
$$1=\sum_{i=1}^N p_i \geq \prod_{i=1}^N p_i^{q_i} q_i^{-q_i}$$
de donde deducimos que
$$\prod_{i=1}^N p_i^{q_i}\leq \prod_{i=1}^N q_i^{q_i}.$$
Ahora basta tomar logaritmos:
$$\sum_{i=1}^N q_i\log_2 p_i= \log\left(\prod_{i=1}^N p_i^{q_i}\right)\leq \log\left(\prod_{i=1}^N q_i^{q_i}\right)= \sum_{i=1}^N q_i\log_2 q_i,$$
y multiplicar la desigualdad por $-1$.

Concluyamos la demostración del teorema. Pongamos
$$
\begin{aligned}
n_i&=|\varphi(y_i)|\\
q_i&=p(y_i)\\
p_i&=Q^{-n_i}\left(\sum_{j=1}^N Q^{-n_j}\right)^{-1}.
\end{aligned}$$
Por la desigualdad de Kraft
$$\sum_{j=1}^N Q^{-n_j}\leq 1$$
y ahora
$$
\begin{aligned}
\mathcal H(Y)&=-\sum_{i=1}^N p(y_i) \log_2 (p(y_i))\\
&\leq -\sum_{i=1}^N p(y_i) \log_2 \frac{Q^{-n_i}}{\sum_{j=1}^N Q^{-n_j}}\\
&\leq -\sum_{i=1}^N p(y_i) \log_2 Q^{-n_i}\\
&\leq (\log_2 Q ) \sum_{i=1}^N p(y_i)|\varphi(y_i)|\\
&=L_\varphi \log_2 Q.
\end{aligned}
$$

Ejemplo: La cota inferior se alcanza para $N=8$, $Q=2$, $p(y_i)=1/8$, y un código uniforme de longitud 3, con lo que $\mathcal H (Y)=L_\varphi=3$.