Truncated binary encoding

Tiedosto:Truncated binary encoding.png

Truncated binary encoding example

Truncated binary encoding on entropy encoding käytetään yleensä tasaisesti todennäköisyyksillä jakautuville äärellisille aakkosille. Se parametrisoidaan kokonaiskokoisella aakkostolla luvulla n. Se on hieman yleisempi muoto binääristä koodausta, kun n ei ole power of two.

Jos n on potenssi kahdella, niin koodattu arvo 0 ≤ x < n on yksinkertainen binäärikoodi x pituudelta log₂(n). Muussa tapauksessa, asetetaan k = floor(log₂(n)) niin, että 2^k < n < 2^k+1 ja u = 2^k+1 − n.

Trunkoitu binäärikoodaus määrittää ensimmäisille u symboleille koodisanoja pituudelta k ja sitten määrittää loput n − u symboleista viimeiset n − u koodisanat pituudelta k + 1. Koska kaikki koodisanat pituudelta k + 1 koostuvat käyttämättömästä koodisanasta pituudelta k "0" tai "1" lisättyinä, syntyvä koodi on prefix code.

Historia

Käytetty ainakin vuodesta 1984, vaiheittaiset koodit, tunnettu myös nimellä taloudelliset koodit, tunnettiin myös truncated binary encodingina.

Esimerkki n = 5

Esimerkiksi, aakkoselle {0, 1, 2, 3, 4}, n = 5 ja 2² ≤ n < 2³, niin k = 2 ja u = 2³ − 5 = 3. Trunkoitu binäärikoodaus määrittää ensimmäisille u symboleille koodisanat 00, 01 ja 10, kaikki pituudelta 2, ja sitten määrittää viimeisille n − u symboleille koodisanat 110 ja 111, viimeiset kaksi koodisanaa pituudelta 3.

Esimerkiksi, jos n on 5, yksinkertainen binäärikoodaus ja trunkoitu binäärikoodaus jakaa seuraavat koodisanat. Numerot, jotka ovat yli viivattuja, eivät välitetä trunkoidussa binäärikoodauksessa.

Trunkoitu binääri	Koodaus			Standard binääri
0	0	0	0	0
1	0	0	1	1
2	0	1	0	2
KÄYTÖSSÄ EI	0	1	1	3
KÄYTÖSSÄ EI	1	0	0	4
KÄYTÖSSÄ EI	1	0	1	5/KÄYTÖSSÄ EI
3	1	1	0	6/KÄYTÖSSÄ EI
4	1	1	1	7/KÄYTÖSSÄ EI

Suoraviivaisen binäärikoodauksen avulla kestää 3 bittiä koodata n, niin 2³ − n = 8 − 5 = 3 on käyttämätön.

Numeroina, lähettääksesi arvon x, jossa 0 ≤ x < n ja jossa on 2^k ≤ n < 2^k+1 symbolia, on u = 2^k+1 − n käyttämättä olevia merkintöjä, kun aakkoskoko pyöristetään lähimpään kahden potenssiin. Prosessi koodata luku x trunkoidussa binäärikoodauksessa on: jos x on pienempi kuin u, koodaa se k binäärisellä bitillä; jos x on suurempi tai yhtä suuri kuin u, koodaa arvo x + u k + 1 binäärisellä bitillä.

Esimerkki n = 10

Toinen esimerkki, koodataksesi aakkostoa kokoa 10 (väliltä 0–9) vaaditaan 4 bitsiä, mutta on 2⁴ − 10 = 6 käyttämätöntä koodia, joten syötearvot, jotka ovat pienempiä kuin 6, hylätään ensimmäinen bitti, kun taas syötearvot, jotka ovat suurempia tai yhtä suuria kuin 6, siirretään 6:lla binääristä tilasta loppuun. (Käyttämättömiä kuvioita ei näytetä tässä taulukossa.)

Syöte arvo	Siirto	Siirretty arvo	Standard binääri	Trunkoitu binääri
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

Dekoodataksesi, lue ensimmäiset k bitit. Jos ne koodaavat arvoa, joka on pienempi kuin u, dekoodaus on valmis. Muussa tapauksessa lue lisäbitti ja vähennä u tuloksesta.

Esimerkki n = 7

Tässä on äärimmäinen tapaus: kun n = 7, seuraava kahden potenssi on 8, joten k = 2 ja u = 2³ − 7 = 1:

Syöte arvo	Siirto	Siirretty arvo	Standard binääri	Trunkoitu binääri
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

Tämä viimeinen esimerkki näyttää, ettei johtava nollabitti aina merkitse lyhyttä koodia; jos u < 2^k, joistakin pitkistä koodeista alkaa nollabitti.

Yksinkertainen algoritmi

Luo trunkoitu binäärikoodaus arvolle x, 0 ≤ x < n, jossa n > 0 on aakkoston koko, joka sisältää x. n ei tarvitse olla kahden potenssi.

string TruncatedBinary (int x, int n)
{
	// Aseta k = floor(log2(n)), eli k niin, että 2^k <= n < 2^(k+1).
	int k = 0, t = n;
	while (t > 1) { k++;  t >>= 1; }

	// Aseta u käyttämättömien koodisanien määräksi = 2^(k+1) - n.
	int u = (1 << k + 1) - n;

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

Rutiini Binary on esimerkki; yleensä vain oikeanpuoleiset len bitit muuttujasta x halutaan. Tässä me vain tuotamme binäärisen koodin x:lle käyttäen len bittejä, täytetään korkean järjestyksen 0:lla tarvittaessa.

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;
}

Tehokkuudesta

Jos n ei ole kahden potenssi ja k-bittiset symbolit tapahtuvat todennäköisyydellä p, niin (k + 1)-bittiset symbolit tapahtuvat todennäköisyydellä 1 − p. Voimme laskea odotetun bittien määrän symbolia kohti $b_{e}$ seuraavasti:

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

Raakakoodaus symbolille on $b_{u}=k+1$ bittiä. Tällöin suhteellinen tilan säästö s (katso Data compression ratio) koodaukselle voidaan määritellä seuraavasti:

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

Yksinkertaistettuna tämä ilmaus johtaa seuraavaan:

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

Tämä osoittaa, että trunkoidun binäärikoodauksen suhteellinen tehokkuus kasvaa, kun k-bittisten symbolien todennäköisyys p kasvaa ja raakakoodauksen symbolin bittipituus $b_{u}$ pienenee.

Katso myös

• Benford's law
• Golomb coding

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

Read or create/edit this page in another language

• Truncated binary encoding in English