Truncated binary encoding

Afgekapt binaire codering is een entropy encoding die meestal gebruikt wordt voor uniforme kansverdelingen met een finiet alfabet. Het is geparametriseerd door een alfabet met een totale grootte van getal n. Het is een lichtjes algemenere vorm van binäre codering wanneer n geen macht van twee is.

Als n een macht van twee is, dan is de gecodeerde waarde voor 0 ≤ x < n de eenvoudige binäre code voor x van lengte log₂(n). Anders, laat k = vloer(log₂(n)), zodat 2^k < n < 2^k+1 en laat u = 2^k+1 − n.

Afgekapt binaire codering wijst de eerste u symbolen codewoorden van lengte k toe en wijst vervolgens de overgebleven n − u symbolen de laatste n − u codewoorden van lengte k + 1 toe. Omdat alle codewoorden van lengte k + 1 bestaan uit een niet-toegewezen codewoord van lengte k met een "0" of "1" toegevoegd, resulteert de code in een voorvoegcode.

Geschiedenis[bewerken]

Gebruikt sinds minstens 1984, inloopcodes, ook bekend als spaarcodes,^[1]^[2]^[3] worden ook afgekapt binaire codering genoemd.

Voorbeeld met n = 5[bewerken]

Bijvoorbeeld, voor het alfabet {0, 1, 2, 3, 4}, n = 5 en 2² ≤ n < 2³, dus k = 2 en u = 2³ − 5 = 3. Afgekapt binaire codering wijst de eerste u symbolen de codewoorden 00, 01, en 10, allemaal van lengte 2, toe, en wijst vervolgens de laatste n − u symbolen de codewoorden 110 en 111, de laatste twee codewoorden van lengte 3, toe.

Bijvoorbeeld, als n 5 is, wijst zowel gewone binaire codering als afgekapt binaire codering de volgende codewoorden toe. Cijfers getoond ~~doorgestreept~~ worden niet verstuurd in afgekapt binair.

Afgekapt binair	Codering			Standaard binair
0	0	0	0	0
1	0	0	1	1
2	0	1	0	2
NIET GEBRUIKT	0	1	1	3
NIET GEBRUIKT	1	0	0	4
NIET GEBRUIKT	1	0	1	5/NIET GEBRUIKT
3	1	1	0	6/NIET GEBRUIKT
4	1	1	1	7/NIET GEBRUIKT

Het kost 3 bits om n te coderen met rechtstreekse binaire codering, dus 2³ − n = 8 − 5 = 3 zijn niet gebruikt.

In numerieke termen, om een waarde x te versturen, waar 0 ≤ x < n, en waar er 2^k ≤ n < 2^k+1 symbolen zijn, zijn er u = 2^k+1 − n niet-gebruikte inzendingen wanneer de alfabetgrootte is afgerond naar de dichtstbijzijnde macht van twee. Het proces om het getal x in afgekapt binair te coderen is: als x kleiner is dan u, codeer het in k binäre bits; als x groter is dan of gelijk aan u, codeer de waarde x + u in k + 1 binäre bits.

Voorbeeld met n = 10[bewerken]

Een ander voorbeeld, het coderen van een alfabet van grootte 10 (tussen 0 en 9) vereist 4 bits, maar er zijn 2⁴ − 10 = 6 niet gebruikte codes, dus invoerwaarden kleiner dan 6 hebben het eerste bit verwijderd, terwijl invoerwaarden groter dan of gelijk aan 6 worden verplaatst door 6 naar het einde van de binaire ruimte. (Niet gebruikte patronen worden niet getoond in deze tabel.)

Invoer waarde	Verschuiving	Verschoven waarde	Standaard binair	Afgekapt binair
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

Om te decoderen, lees de eerste k bits. Als ze een waarde kleiner dan u coderen, is decodering compleet. Anders, lees een extra bit en trek u af van het resultaat.

Voorbeeld met n = 7[bewerken]

Hier is een extremer geval: met n = 7 is de volgende macht van 2 8, dus k = 2 en u = 2³ − 7 = 1:

Invoer waarde	Verschuiving	Verschoven waarde	Standaard binair	Afgekapt binair
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

Dit laatste voorbeeld toont dat een voorloopnulbit niet altijd een korte code aangeeft; als u < 2^k, beginnen sommige lange codes met een nulbit.

Eenvoudig algoritme[bewerken]

Genereer de afgekapt binaire codering voor een waarde x, 0 ≤ x < n, waar n > 0 de grootte van het alfabet is dat x bevat. n hoeft geen macht van twee te zijn.

string AfgekaptBinair (int x, int n)
{
	// Zet k = vloer(log2(n)), d.w.z. k zodat 2^k <= n < 2^(k+1).
	int k = 0, t = n;
	while (t > 1) { k++;  t >>= 1; }

	// Zet u op het aantal niet gebruikte codewoorden = 2^(k+1) - n.
	int u = (1 << k + 1) - n;

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

De routine Binair is illustratief; meestal zijn enkel de rechterste len bits van de variabele x gewenst. Hier geven we gewoon de binaire code voor x weer met behulp van len bits, vullen aan met hoge-orde 0's indien nodig.

string Binair (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;
}

Over efficiëntie[bewerken]

Als n geen macht van twee is, en k-bitsymbolen worden waargenomen met kans p, dan worden (k + 1)-bitsymbolen waargenomen met kans 1 − p. We kunnen het verwachte aantal bits per symbool $b_{e}$ berekenen als

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

Ruwe codering van het symbool heeft $b_{u}=k+1$ bits. Dan kan de relatieve ruimtebesparing s (zie Data compressieratio) van de codering gedefinieerd worden als

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

Wanneer vereenvoudigd, leidt deze expressie tot

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

Dit geeft aan dat de relatieve efficiëntie van afgekapt binaire codering toeneemt naarmate de kans p van k-bitsymbolen toeneemt, en de ruw-coderingssymboolbitlengte $b_{u}$ afneemt.