La codificació binària truncada és una codificació d'entropia que s'utilitza típicament per a distribucions de probabilitat uniformes amb un alfabet finit. Està parametritzada per un alfabet amb una mida total del nombre n . És una forma lleugerament més general de codificació binària quan n no és una potència de dos.

Si n és una potència de dos, aleshores el valor codificat per a 0 ≤ x < n és el codi binari simple per a x de longitud log² (n). Altrament, sigui k = floor(log² (n)), de manera que 2k < n < 2k +1 i sigui u = 2k +1 − n.

La codificació binària truncada assigna als primers u símbols paraules de codi de longitud k i després assigna als n − u símbols restants les últimes n − u paraules de codi de longitud k + 1. Com que totes les paraules de codi de longitud k + 1 consisteixen en una paraula de codi no assignada de longitud k amb un "0" o un "1" afegit, el codi resultant és un codi de prefix.

Història Utilitzats des d'almenys el 1984, els codis d'introducció gradual, també coneguts com a codis econòmics,Eastman, Willard L, et al. (Aug. 1984) Apparatus and Method for Compressing Data Signals and Restoring the Compressed Data Signals, US Patent 4,464,650.Acharya, Tinku et Já Já, Joseph F. (oct. 1996), An on-line variable-length binary encoding of text, Information Sciences, vol 94 no 1-4, p. 1-22.Job van der Zwan. "Phase-in Codes". també es coneixen com a codificació binària truncada.

Exemple amb n = 5 Per exemple, per a l'alfabet {0, 1, 2, 3, 4}, n = 5 i 22 ≤ n < 23, per tant k = 2 i u = 23 − 5 = 3. La codificació binària truncada assigna als primers símbols u les paraules de codi 00, 01 i 10, totes de longitud 2, i després assigna als últims símbols n − u les paraules de codi 110 i 111, les dues últimes paraules de codi de longitud 3.

Per exemple, si n és 5, la codificació binària simple i la codificació binària truncada assignen les paraules de codi següents. Dígits mostrats colpejat no es transmeten en binari truncat. Truncat binariCodificacióEstàndard binari0 00001 00112 0102NO UTILITZAT 0 1 13NO UTILITZAT 1 0 04NO UTILITZAT 1 0 15/NO UTILITZAT31106/NO UTILITZAT41117/NO UTILITZAT Es necessiten 3 bits per codificar n utilitzant una codificació binària directa, per tant, 23 − n = 8 − 5 = 3 no s'utilitzen.

En termes numèrics, per enviar un valor x, on 0 ≤ x < n, i on hi ha 2k ≤ n < 2k +1 símbols, hi ha u = 2k +1 − n entrades no utilitzades quan la mida de l'alfabet s'arrodoneix a la potència de dos més propera. El procés per codificar el nombre x en binari truncat és: si x és menor que u, codifiqueu-lo en k bits binaris; si x és major o igual que u, codifiqueu el valor x + u en k + 1 bits binaris.

Exemple amb n = 10 Un altre exemple, codificar un alfabet de mida 10 (entre 0 i 9) requereix 4 bits, però hi ha 24 − 10 = 6 codis no utilitzats, de manera que els valors d'entrada inferiors a 6 tenen el primer bit descartat, mentre que els valors d'entrada superiors o iguals a 6 es desplacen en 6 fins al final de l'espai binari. (Els patrons no utilitzats no es mostren en aquesta taula.) Entrada valorDesplaçamentDesplaçament valorEstàndard binariTruncat binari000 0 000000101 0 001001202 0 010010303 0 011011404 0 100100505 0 101101661201101100761301111101861410001110961510011111 Per descodificar, llegiu els primers k bits. Si codifiquen un valor inferior a u, la descodificació s'ha completat. En cas contrari, llegiu un bit addicional i resteu u del resultat.

Exemple amb n = 7 Aquí teniu un cas més extrem: amb n = 7 la següent potència de 2 és 8, de manera que k = 2 i u = 23 − 7 = 1: Entrada valorDesplaçamentDesplaçament valorEstàndard binariTruncat binari000 0 0000112001010213010011314011100415100101516101110617110111 Aquest darrer exemple demostra que un bit zero inicial no sempre indica un codi curt; si u < 2k, alguns codis llargs començaran amb un bit zero.

Algorisme simple Genera la codificació binària truncada per a un valor x, 0 ≤ x < n, on n > 0 és la mida de l'alfabet que conté x . No cal que n sigui una potència de dos.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)); }La rutina Binary és expositiva; normalment només es desitgen els bits len situats més a la dreta de la variable x. Aquí simplement generem el codi binari per a x utilitzant bits len, omplint amb 0 d'ordre superior si cal.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; }

Referències

Categoria:Codificació Categoria:Compressió de dades