Codificação binária truncada - Truncated binary encoding

A codificação binária truncada é uma codificação de entropia normalmente usada para distribuições uniformes de probabilidade com um alfabeto finito. É parametrizado por um alfabeto com tamanho total de número n . É uma forma um pouco mais geral de codificação binária quando n não é uma potência de dois .

Se n for uma potência de dois, então o valor codificado para 0 ≤ x < n é o código binário simples para x de comprimento log ₂ ( n ). Caso contrário, seja k = floor (log ₂ ( n )) tal que 2 ^k < n <2 ^{k +1} e seja u = 2 ^{k +1} - n .

A codificação binária truncada atribui as primeiras palavras-código dos símbolos u de comprimento k e, em seguida, atribui aos símbolos n - u restantes as últimas n - u palavras-código de comprimento k + 1. Porque todas as palavras-código de comprimento k + 1 consistem em uma palavra-código não atribuída de comprimento k com um "0" ou "1" anexado, o código resultante é um código de prefixo .

Exemplo com n = 5

Por exemplo, para o alfabeto {0, 1, 2, 3, 4}, n = 5 e 2 ² ≤ n <2 ³ , portanto, k = 2 e u = 2 ³ - 5 = 3. A codificação binária truncada atribui o primeiro u simboliza as palavras-código 00, 01 e 10, todas de comprimento 2, então atribui aos últimos n - u símbolos as palavras-código 110 e 111, as duas últimas palavras-código de comprimento 3.

Por exemplo, se n for 5, a codificação binária simples e a codificação binária truncada alocam as seguintes palavras-código . Dígitos mostrados~~chocado~~ não são transmitidos em binário truncado.

Binário truncado	Codificação			Binário padrão
0	0	0	0	0
1	0	0	1	1
2	0	1	0	2
NÃO UTILIZADO	0	1	1	3
NÃO UTILIZADO	1	0	0	4
NÃO UTILIZADO	1	0	1	5 / NÃO UTILIZADO
3	1	1	0	6 / NÃO UTILIZADO
4	1	1	1	7 / NÃO UTILIZADO

São necessários 3 bits para codificar n usando a codificação binária direta, portanto, 2 ³ - n = 8 - 5 = 3 não são usados.

Em termos numéricos, para enviar um valor x onde 0 ≤ x < n , e onde há 2 ^k ≤ n <2 ^{k +1} símbolos, há u = 2 ^{k + 1} - n entradas não utilizadas quando o tamanho do alfabeto é arredondado para cima com a potência de dois mais próxima. O processo para codificar o número x em binário truncado é: Se x for menor que u , codifique-o em k bits binários. Se x for maior ou igual a u , codifique o valor x + u em k + 1 bits binários.

Exemplo com n = 10

Outro exemplo, a codificação de um alfabeto de tamanho 10 (entre 0 e 9) requer 4 bits, mas há 2 ⁴ - 10 = 6 códigos não utilizados, então valores de entrada menores que 6 têm o primeiro bit descartado, enquanto valores de entrada maiores ou iguais a 6 são compensados por 6 no final do espaço binário. (Os padrões não utilizados não são mostrados nesta tabela.)

Valor de entrada	Desvio	Valor de compensação	Binário Padrão	Binário truncado
0	0	0	0000	000
1	0	1	0001	001
2	0	2	0010	010
3	0	3	0011	011
4	0	4	0100	100
5	0	5	0101	101

6	6	12	0110	1100
7	6	13	0111	1101
8	6	14	1000	1110
9	6	15	1001	1111

Para decodificar, leia os primeiros k bits. Se eles codificarem um valor menor que u , a decodificação estará completa. Caso contrário, leia um bit adicional e subtraia u do resultado.

Exemplo com n = 7

Aqui está um caso mais extremo: com n = 7, a próxima potência de 2 é 8, então k = 2 e u = 2 ³ - 7 = 1:

Valor de entrada	Desvio	Valor de compensação	Binário Padrão	Binário truncado
0	0	0	000	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 exemplo demonstra que um bit zero à esquerda nem sempre indica um código de acesso; se u <2 ^k , alguns códigos longos começarão com um bit zero.

Algoritmo simples

Gere a codificação binária truncada para um valor x , 0 <= x < n , onde n > 0 é o tamanho do alfabeto contendo x . n não precisa ser uma potência de dois.

string TruncatedBinary (int x, int n)
{
	// Set k = floor(log2(n)), i.e., k such that 2^k <= n < 2^(k+1).
	int k = 0, t = n;
	while (t > 1) { k++;  t >>= 1; }

	// Set u to the number of unused codewords = 2^(k+1) - n.
	int u = (1 << k+1) - n;

	if (x < u)  return Binary(x, k); 
        else  return Binary(x+u, k+1));
}

A rotina binária é expositiva; normalmente, apenas os bits de len mais à direita da variável x são desejados. Aqui, simplesmente emitimos o código binário para x usando bits len , preenchendo com 0s de alta ordem, se necessário.

string Binary (int x, int len)
{
	string 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;
}

Na eficiência

Se n não for uma potência de dois e k símbolos de bit são observados com probabilidade p , k + 1 símbolos de bit são observados com probabilidade 1 - p . Podemos calcular o número esperado de bits por símbolo como: ${\ displaystyle b_ {e}}$

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

A codificação bruta do símbolo é em bits. Em seguida, os s de economia de espaço relativo (ver Data_compression_ratio ) da codificação podem ser definidos como ${\ displaystyle b_ {u} = k + 1}$

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

Quando simplificada, esta expressão leva a:

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

Isso indica que a eficiência relativa da codificação binária truncada aumenta à medida que a probabilidade p de k símbolos de bits aumenta e os bits de codificação bruta por símbolo diminuem. ${\ displaystyle b_ {u}}$

Languages

In other projects