Codificación binaria truncada

La codificación binaria truncada es una codificación entrópica que se utiliza habitualmente para distribuciones de probabilidad uniformes con un alfabeto finito. Está parametrizada por un alfabeto de tamaño total n . Es una forma ligeramente 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 ₂ ( n ). De lo contrario, sea k = floor(log ₂ ( n )), de modo que 2 ^k < n < 2 ^{k +1} y sea u = 2 ^{k +1} − n .

La codificación binaria truncada asigna a los primeros u símbolos palabras clave de longitud k y luego asigna a los n − u símbolos restantes las últimas n − u palabras clave de longitud k + 1. Debido a que todas las palabras clave de longitud k + 1 consisten en una palabra clave no asignada de longitud k con un "0" o un "1" añadido, el código resultante es un código de prefijo .

Utilizados desde al menos 1984, los códigos de fase , también conocidos como códigos económicos , ^{[ 1 ] [ 2 ] [ 3 ]} también se conocen como codificación binaria truncada.

Por ejemplo, para el alfabeto {0, 1, 2, 3, 4}, n = 5 y 2 ² ≤ n < 2 ³ , por lo tanto k = 2 y u = 2 ³ − 5 = 3. La codificación binaria truncada asigna a los primeros u símbolos las palabras clave 00, 01 y 10, todas de longitud 2, y luego asigna a los últimos n − u símbolos las palabras clave 110 y 111, las dos últimas palabras clave de longitud 3.

Por ejemplo, si n es 5, la codificación binaria simple y la codificación binaria truncada asignan las siguientes palabras clave. Dígitos mostradosgolpeadono se transmiten en binario truncado.

Se necesitan 3 bits para codificar n usando una codificación binaria directa, por lo tanto, 2 ³ − n = 8 − 5 = 3 no se utilizan.

En términos numéricos, para enviar un valor x , donde 0 ≤ x < n , y donde hay 2k ^≤ n < 2k ^{+ 1} símbolos, hay u = ^{2k + 1} − n entradas no utilizadas cuando el tamaño del alfabeto se redondea 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 , se codifica en k bits binarios; si x es mayor o igual que u , se codifica el valor x + u en k + 1 bits binarios.

Otro ejemplo: codificar un alfabeto de tamaño 10 (entre 0 y 9) requiere 4  bits, pero hay 2⁴ ⁻ 10 = 6 códigos sin usar. Por lo tanto, a los valores de entrada menores que 6 se les descarta el primer bit, mientras que a los valores de entrada mayores o iguales a 6 se les desplaza 6 posiciones al final del espacio binario. (Los patrones sin usar no se muestran en esta tabla).

Para decodificar, lee los primeros k bits. Si codifican un valor menor que u , la decodificación ha finalizado. De lo contrario, lee un bit adicional y resta u al resultado.

Aquí tenemos un caso más extremo: con n = 7, la siguiente potencia de 2 es 8, por lo que k = 2 y u = 2³ ⁻ 7 = 1:

Este último ejemplo demuestra que un bit cero inicial no siempre indica un código corto; si u < 2k ^, algunos códigos largos comenzarán con un bit cero.

Genera 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 tiene por qué ser una potencia de dos.

string TruncatedBinary ( int x , int n ) { // Establecer k = floor(log2(n)), es decir, k tal que 2^k <= n < 2^(k+1). int k = 0 , t = n ; while ( t > 1 ) { k ++ ; t >>= 1 ; }// Establece u al número de palabras clave no utilizadas = 2^(k+1) - n. int u = ( 1 << k + 1 ) - n ;if ( x < u ) return Binary ( x , k ); else return Binary ( x + u , k + 1 )); }

La rutina Binaryes explicativa; normalmente solo se necesitan los lenbits más a la derecha de la variable x . Aquí, simplemente generamos el código binario de x usando lenbits, rellenando con ceros de orden superior si es necesario.

cadena Binaria ( int x , int len ​​) { cadena s = "" ; while ( x != 0 ) { if ( even ( x )) s = '0' + s ; else s = '1' + s ; x >>= 1 ; } while ( s . Length < len ) s = '0' + s ; return s ; }

Si n no es una potencia de dos, y los símbolos de k bits se observan con probabilidad p , entonces los símbolos de ( k + 1) bits se observan con probabilidad 1 − p . Podemos calcular el número esperado de bits por símbolo.${\displaystyle b_{e}}$como

${\displaystyle b_{e}=pk+(1-p)(k+1).}$

Codificación sin procesar del símbolo${\displaystyle b_{u}=k+1}$bits. Entonces, el ahorro de espacio relativo s (ver Relación de compresión de datos ) de la codificación se puede definir como

${\displaystyle s=1-{\frac {b_{e}}{b_{u}}}=1-{\frac {pk+(1-p)(k+1)}{k+1}}.}$

Cuando se simplifica, esta expresión conduce a

${\displaystyle s={\frac {p}{k+1}}={\frac {p}{b_{u}}}.}$

Esto indica que la eficiencia relativa de la codificación binaria truncada aumenta a medida que aumenta la probabilidad p de símbolos de k bits y la longitud de bits del símbolo de codificación sin procesar.${\displaystyle b_{u}}$disminuye.

• Ley de Benford
• Codificación en Golomb