Codificación de Fuente: Huffman y Rice

Algoritmo de Huffman

El Código de Huffman se basa en la construcción de un árbol binario, uniendo los símbolos de menor a mayor probabilidad. Esto genera una tabla de códigos $C(x)$ y sus longitudes $l(x)$.

Cálculo de Longitudes y Eficiencia

• Longitud Media (L) (bits generados por símbolo): $$L = \sum p(x) \cdot l(x)$$ Donde $p(x)$ es la probabilidad del símbolo y $l(x)$ es el número de bits de su código.
• Longitud Fija ($L_{fija}$) (para $N$ símbolos):
  1. Calcular la longitud mínima necesaria: $l_{min} = \log_2(N)$, donde $N$ es el número de símbolos distintos.
  2. La longitud fija es el entero superior más cercano que sea potencia de 2 (o el techo de $l_{min}$): $L_{fija} = \lceil \log_2(N) \rceil$. Ejemplo: Si $N=5$, $\log_2(5) \approx 2.32$. $L_{fija} = 3$ bits ($2^3=8 \ge 5$).
  3. Ahorro de bits respecto a Huffman: Calcular $L_{fija} – L_{media-huffman}$ (resultado en bits/símbolo).
  4. Para $10^8$ símbolos, el ahorro total es: $(L_{fija} – L_{media-huffman}) \cdot 10^8$ bits.

Codificación Rice

La codificación Rice (o Golomb-Rice) divide el símbolo $x$ en un cociente $X_c$ y un resto $X_r$, utilizando un parámetro $m$ tal que $2^m$ es el divisor.

Tabla de Codificación Rice

La tabla de codificación incluye:

• Cálculo de $X_c$ y $X_r$: $X_c = \lfloor x / 2^m \rfloor$ y $X_r = x \pmod{2^m}$.
• Código Unario: $X_c=0 \rightarrow 1$; $X_c=1 \rightarrow 01$; $X_c=2 \rightarrow 001$; etc. (Se añade un cero por cada incremento de $X_c$).
• Longitud Media con Rice: Se calcula de manera similar a Huffman, utilizando la longitud $l(x)$ obtenida en la tabla.

Propiedades del Código

• Instantáneo (Prefijo Libre): Un código es instantáneo si ninguna palabra de código es prefijo de otra palabra de código.
• Óptimo: Un código es óptimo si su longitud media $L$ es igual a la Entropía $H(X)$ (o si $L_{prob} = L_{huffman}$).
  • Entropía $H(X)$: $H(X) = -\sum p(x_i) \cdot \log_2(p(x_i))$.
  • Caso 1 (Comparación con Huffman): Si $L_{prob} = L_{huffman}$, el código es óptimo.
  • Caso 2 (Comparación con Entropía): Si $L_{unario} \ge H(X)$, el código no es óptimo.
• Efectividad (η): Se calcula cuando el código no es óptimo. $$\eta = \left( \frac{H(X)}{L_{código}} \right) \cdot 100$$

Modulación por Codificación de Pulsos (PCM)

Cuantificación Uniforme

• Número de Niveles (M): $M = 2^N$, donde $N$ es el número de bits por muestra.
• Rango Dinámico (R): $R = X_{max} – X_{min}$ (Valor máximo del intervalo menos valor mínimo).
• Paso de Cuantificación (Δ): $$\Delta = \frac{R}{M} = \frac{X_{max} – X_{min}}{2^N}$$
• Distorsión (D) (Error cuadrático medio de cuantificación): $$D = \frac{\Delta^2}{12}$$

Relación Entrada-Salida y Palabras Binarias

• Cuantizador: $K = \text{rint}(x / \Delta)$ (donde rint es la función de redondeo al entero más cercano).
• Decuantizador: $y = K \cdot \Delta$.
• Cálculo de la Palabra Binaria:
  1. Calcular el índice de cuantificación $K(0) = \text{rint}(x(0) / \Delta)$.
  2. Utilizar $K(0)$ para obtener la muestra decuantificada $y(0) = K(0) \cdot \Delta$.
• Función $C(x)$: El índice $k$ es la función de cuantificación: $k = C(x) = \text{rint}(x / \Delta)$.

Conjunto de Índices y Probabilidad

El Conjunto de Índices es el rango de valores enteros $k$ que se obtienen al cuantificar todos los valores de $x$ dentro del intervalo dado.

Para determinar el conjunto de índices, se sustituyen los valores de $x$ dentro del intervalo en la función $k = \text{rint}(x / \Delta)$.

Probabilidad de cada Índice $P(k)$ (Solo para el conjunto de índices):

La probabilidad de un índice $k$ se calcula integrando la función de densidad de probabilidad $p(x)$ sobre el intervalo de cuantificación asociado a $k$.

3. Determinación de Extremos de Integración: Para un índice $k$, los extremos del intervalo de cuantificación son $x_{i}$ y $x_{d}$ tales que $k = \text{rint}(x / \Delta)$ para $x \in [x_i, x_d)$.
4. Cálculo de la Integral: $$P(k) = \int_{x_i}^{x_d} p(x) dx$$ Ejemplo: Si $k=-1$ y $p(x)=1/5$ (constante), y los extremos son $[-2, -1]$, entonces $P(-1) = \int_{-2}^{-1} (1/5) dx = [x/5]_{-2}^{-1} = (-1/5) – (-2/5) = 1/5 = 0.2$.

Decodificación de Secuencias de Bits

Decodificación de una Secuencia Rice

1. Identificar la primera secuencia de bits (hasta el primer ‘1’).
2. Dividir la secuencia en: $C_c$ (código del cociente, hasta el primer ‘1’) y $C_r$ (código del resto, los $m$ bits siguientes, donde $2^m$ es el parámetro Rice).
3. Determinar $X_c$ (Cociente): Es el número de ceros antes del primer ‘1’ en $C_c$.
4. Determinar $X_r$ (Resto): Es el valor decimal de los $m$ bits de $C_r$.
5. Calcular el valor absoluto $X_{abs}$: $X_{abs} = 2^m \cdot X_c + X_r$.
6. Determinar el valor final $x$ (con signo):
   • Si $X_{abs}$ es par: $x = X_{abs} / 2$.
   • Si $X_{abs}$ es impar: $x = -(X_{abs} + 1) / 2$.
7. Repetir el proceso para la siguiente parte de la secuencia de bits para obtener $x_2$, etc.

Conversión Analógica a Digital (A/D)

Obtención de los Primeros Bits

1. Calcular el índice de codificación $k = \text{round}(x / \Delta)$ para las muestras $x_1, x_2, \dots$ dadas.
2. Determinar el Rango de Cuantificación para $N$ bits: $[ -2^{N-1}, 2^{N-1} – 1 ]$. Ejemplo: Para $N=10$ bits, el rango es $[-512, 511]$.
3. Saturación: Si un índice $k$ calculado está fuera del rango, se satura al valor extremo más cercano del rango (ej: si $k=632$, se usa $511$).
4. Convertir los índices saturados a binario de $N$ bits (utilizando complemento a dos si es necesario, o rellenando con ceros a la izquierda).
5. Concatenar las secuencias binarias de $k_1, k_2, \dots$ para obtener la secuencia total de bits.

Cálculo del Índice de Cuantificación ($k$) a partir de la Palabra Binaria

Para una palabra binaria de $N$ bits ($b_{N-1} b_{N-2} \dots b_0$), el índice $k$ se calcula utilizando la representación en complemento a dos:

La fórmula general es:

$$k = -b_{N-1} \cdot 2^{N-1} + b_{N-2} \cdot 2^{N-2} + \dots + b_0 \cdot 2^0$$

Donde $b_i$ es el valor del bit (0 o 1).

Caso 2: Sin Probabilidad de Saturación: El valor máximo de la señal $X_s$ se relaciona con el paso de cuantificación $\Delta$ y el número de niveles $M$ como: $X_s = \Delta M / 2$.

Métricas de Tasa y Ruido

Tasa Binaria (R)

Caso 1: Convertidor (Caso Normal)

$$R = f_s \cdot L$$

Donde $f_s$ es la frecuencia de muestreo y $L$ es la longitud del código (bits/muestra). Si $L$ no se conoce, se puede calcular como $L = \log_2(M)$.

Caso 2: Imagen o Audio Multicanal

$$R = \text{Resolución} \cdot \text{Tasa de Imagen} \cdot \text{Canales}$$

• Resolución: Columnas $\times$ Filas.
• Canales: RGB=3, Audio Estéreo=2, Audio Mono/Voz/Imagen Monocroma=1.

Caso 3: Conversión a Bits/Muestra

Para convertir una tasa binaria total (bits/segundo) a bits por muestra:

$$\frac{\text{Bits}}{\text{Muestra}} = \frac{\text{Tasa Binaria (bits/s)}}{\text{Frecuencia de Muestreo } f_s \text{ (muestras/s)}}$$

Longitud del Código de Longitud Fija (L)

Se puede obtener a partir de la tasa binaria y la frecuencia de muestreo:

$$L = \frac{R}{f_s} \quad (\text{en bits/muestra})$$

Paso de Cuantificación (Δ)

Si se conoce el rango simétrico $2X_s$ y el número de niveles $M=2^L$:

$$\Delta = \frac{2 \cdot X_s}{M}$$

Relación Señal a Ruido (SNR en dB)

La relación señal a ruido se calcula en decibelios:

$$\text{SNR (dB)} = 10 \cdot \log_{10} \left( \frac{P_x}{D} \right)$$

Donde $P_x$ es la potencia de la señal y $D$ es la distorsión de cuantificación ($D = \Delta^2/12$).