La codificación binaria truncada es una codificación de entropía que se utiliza normalmente para distribuciones de probabilidad uniformes con un alfabeto finito. Está parametrizado por un alfabeto con tamaño total de número n . Es una forma un poco más general de codificación binaria cuando n no es una potencia de dos .
Si n es una potencia de dos, entonces el valor codificado para 0 ≤ x < n es el código binario simple para x de longitud log 2 ( n ). De lo contrario, sea k = piso (log 2 ( n )) tal que 2 k < n <2 k +1 y sea u = 2 k +1 - n .
La codificación binaria truncada asigna los primeros símbolos u palabras de código de longitud k y luego asigna los n - u símbolos restantes las últimas n - u palabras de código de longitud k + 1. Porque todas las palabras de código de longitud k + 1 consisten en una palabra de código no asignada de longitud k con un "0" o "1" agregado, el código resultante es un código de prefijo .
Ejemplo con n = 5
Por ejemplo, para el alfabeto {0, 1, 2, 3, 4}, n = 5 y 2 2 ≤ n <2 3 , por lo tanto, k = 2 y u = 2 3 - 5 = 3. La codificación binaria truncada asigna el primer u simboliza las palabras de código 00, 01 y 10, todas de longitud 2, luego asigna los últimos n - u símbolos las palabras de código 110 y 111, las dos últimas palabras de código de longitud 3.
Por ejemplo, si n es 5, la codificación binaria simple y la codificación binaria truncada asignan las siguientes palabras de código . Dígitos mostradosgolpeado no se transmiten en binario truncado.
truncado binaria | Codificación | Binario estándar | ||
---|---|---|---|---|
0 | 0 | 0 | 0 | |
1 | 0 | 1 | 1 | |
2 | 1 | 0 | 2 | |
NO USADO | 3 | |||
NO USADO | 4 | |||
NO USADO | 5 / SIN UTILIZAR | |||
3 | 1 | 1 | 0 | 6 / SIN UTILIZAR |
4 | 1 | 1 | 1 | 7 / SIN UTILIZAR |
Se necesitan 3 bits para codificar n utilizando una codificación binaria sencilla, por lo tanto, 2 3 - n = 8 - 5 = 3 no se utilizan.
En términos numéricos, para enviar un valor x donde 0 ≤ x < n , y donde hay 2 k ≤ n <2 k +1 símbolos, hay u = 2 k + 1 - n entradas no utilizadas cuando el tamaño del alfabeto se redondea hacia arriba a la potencia de dos más cercana. El proceso para codificar el número x en binario truncado es: Si x es menor que u , codifíquelo en k bits binarios. Si x es mayor o igual que u , codifique el valor x + u en k + 1 bits binarios.
Ejemplo con n = 10
Otro ejemplo, codificar un alfabeto de tamaño 10 (entre 0 y 9) requiere 4 bits, pero hay 2 4 - 10 = 6 códigos sin usar, por lo que los valores de entrada menores que 6 tienen el primer bit descartado, mientras que los valores de entrada mayores o iguales a 6 están desplazados por 6 al final del espacio binario. (Los patrones no utilizados no se muestran en esta tabla).
Valor de entrada | Compensar | Valor de compensación | Binario estándar | Binario truncado |
---|---|---|---|---|
0 | 0 | 0 | 000 | |
1 | 0 | 1 | 001 | |
2 | 0 | 2 | 010 | |
3 | 0 | 3 | 011 | |
4 | 0 | 4 | 100 | |
5 | 0 | 5 | 101 | |
6 | 6 | 12 | 0110 | 1100 |
7 | 6 | 13 | 0111 | 1101 |
8 | 6 | 14 | 1000 | 1110 |
9 | 6 | 15 | 1001 | 1111 |
Para decodificar, lea los primeros k bits. Si codifican un valor menor que u , la decodificación está completa. De lo contrario, lea un bit adicional y reste u del resultado.
Ejemplo con n = 7
Aquí hay un caso más extremo: con n = 7, la siguiente potencia de 2 es 8, por lo que k = 2 y u = 2 3 - 7 = 1:
Valor de entrada | Compensar | Valor de compensación | Binario estándar | Binario truncado |
---|---|---|---|---|
0 | 0 | 0 | 00 | |
1 | 1 | 2 | 001 | 010 |
2 | 1 | 3 | 010 | 011 |
3 | 1 | 4 | 011 | 100 |
4 | 1 | 5 | 100 | 101 |
5 | 1 | 6 | 101 | 110 |
6 | 1 | 7 | 110 | 111 |
Este último ejemplo demuestra que un bit cero inicial no siempre indica un código corto; si u <2 k , algunos códigos largos comenzarán con un bit cero.
Algoritmo simple
Genere la codificación binaria truncada para un valor x , 0 <= x < n , donde n > 0 es el tamaño del alfabeto que contiene x . n no necesita ser una potencia de dos.
cadena TruncatedBinary (int x, int n){// Establecer k = piso (log2 (n)), es decir, k tal que 2 ^ k <= n <2 ^ (k + 1).int k = 0, t = n;mientras que (t> 1) {k ++; t >> = 1; }// Establezca u en el número de palabras de código no utilizadas = 2 ^ (k + 1) - n.int u = (1 << k + 1) - n;si (x )> de lo contrario, devuelve Binary (x + u, k + 1));}
La rutina Binary es expositiva; por lo general, solo se desean los bits len más a la derecha de la variable x . Aquí simplemente generamos el código binario para x usando len bits, rellenando con ceros de orden superior si es necesario.
cadena binaria (int x, int len){cadena s = "";while (x! = 0) {si (par (x)) s = '0' + s;si no s = '1' + s;x >> = 1;}while (s. longitud)>devoluciones;}
Sobre la eficiencia
Si n no es una potencia de dos, y se observan k símbolos de bits con probabilidad p , se observan k + 1 símbolos de bits con probabilidad 1 - p . Podemos calcular el número esperado de bits por símbolo. como:
.
La codificación sin formato del símbolo es bits. Entonces ahorro de espacio con relación s (ver Data_compression_ratio ) de la codificación se puede definir como
.
Cuando se simplifica, esta expresión conduce a:
.
Esto indica que la eficiencia relativa de la codificación binaria truncada aumenta a medida que aumenta la probabilidad p de k símbolos de bits y los bits de codificación sin procesar por símbolo disminuye.