Unary coding

Tiedosto:Unary coding example.png

Esimerkki yksikkökoodista

Yksikkökoodaus eli thermometrikoodaus on entropiakoodaus, joka esittää luonnollista lukua, n, koodilla, joka on pituudeltaan n + 1 (tai n), yleensä n ykköstä seuraava nolla (jos luonnollinen luku tulkitaan epänegatiiviseksi kokonaisluvuksi) tai n − 1 ykköstä seuraava nolla (jos luonnollinen luku tulkitaan ainoastaan positiiviseksi kokonaisluvuksi). Esimerkiksi luku 5 esitetään muodossa 111110 tai 11110. Joissakin esityksissä käytetään n tai n − 1 nollaa seuraavaa ykköstä. Ykösset ja nollat ovat vaihdettavissa ilman yleistä menetystä. Yksikkökoodaus on sekä etuliitekoodi että itsesynkronoivakoodi.

Yksikkökoodaus on optimaalisti tehokas koodaus seuraavalle diskreetille todennäköisyysjakaumalle:

$\operatorname {P} (n)=2^{-n}\,$

missä $n=1,2,3,...$.

Symboli kerrallaan koodatessa se on optimaalinen minkä tahansa geometrinen jakauma:

$\operatorname {P} (n)=(k-1)k^{-n}\,$

missä k ≥ φ = 1.61803398879..., kultainen leikkaus, tai yleisemmin mikä tahansa diskreetti jakauma, jossa

$\operatorname {P} (n)\geq \operatorname {P} (n+1)+\operatorname {P} (n+2)\,$

missä $n=1,2,3,...$. Vaikka se on optimaalinen symboli kerrallaan koodaus tällaisille todennäköisyysjakaumille, Golomb-koodaus saavuttaa paremman pakkaustilavuuden geometriselle jakaumalle, koska se ei käsittele syötemerkkejä itsenäisesti, vaan ryhmittelee syötteet implisiittisesti. Samasta syystä aritmeettinen koodaus toimii paremmin yleisille todennäköisyysjakaumille, kuten viimeksi mainitussa tapauksessa.

Yksikkökoodi käytössä tänään

Yksikkökoodin käyttöesimerkkejä ovat:

• Golomb Rice -koodissa yksikkökoodaus käytetään koodata osamääräosuus Golomb-koodisanasta.
• UTF-8-merkistössä yksikkökoodaus käytetään monibyte-sarjan johtavassa tavussa ilmaisemaan tavujen määrää sarjassa, jotta sarjan pituus voidaan määrittää ilman jatkotavujen tarkastelua.
• Pikaviestinneuraaliverkot käyttävät yksikkökoodausta tehokkaan datan esitystavan vuoksi.

Yksikkökoodaus lintujen laulussa

Yksikkökoodaus käytetään hermostoverkkoissa, jotka ovat vastuussa lintujen laulun tuotannosta. Linnun aivoissa sijaitseva ydin, joka osallistuu sekä lintujen laulun oppimiseen että tuottamiseen, on HVC (korkea äänikeskus). Erilaiset komennomerkit eri sävelille lintulaulussa lähtevät eri kohdista HVC:stä. Tämä koodaus toimii avaruuskoodauksena, joka on tehokas strategia biologisille verkoille sen perusteellisen yksinkertaisuuden ja kestävyyden vuoksi.

Standardijuoksunpituus yksikkökoodit

Kaikki binäärit tiedot määritellään kyvyllä esittää yksikkönumeroita vuorottelevissa juoksunpituuksissa ykösia ja nollia. Tämä noudattaa standardimääritelmää yksikkösta eli N samanlaisia numeroita 1 tai 0. Kaikki juoksunpituudet määritelmän mukaan sisältävät vähintään yhden numeron ja edustavat siten ainoastaan positiivisia kokonaislukuja.

n	RL code	Next code
1	1	0
2	11	00
3	111	000
4	1111	0000
5	11111	00000
6	111111	000000
7	1111111	0000000
8	11111111	00000000
9	111111111	000000000
10	1111111111	0000000000
...

Nämä koodit takaa, että ne päättyvät pätevästi mihin tahansa datan pituuteen (luettaessa satunnaista dataa) ja kirjoitusvaiheessa (erillisessä) mahdollistavat ylimääräisen bittien käytön ja siirron (se bitti, joka käytetään ensimmäiseen bittiin) säilyttäen kokonaisen ja kokonaislukujen yksikkökoodien pituudet tarkalleen N.

Yksiläisesti dekoodattavat ei-etuliite yksikkökoodit

Seuraava on esimerkki yksiläisesti dekoodattavista kodeista, joka ei ole etuliitekoodi eikä välittömästi dekoodattava (tarvitsee etukatselun dekoodatakseen).

n	Unary code	Alternative
1	1	0
2	10	01
3	100	011
4	1000	0111
5	10000	01111
6	100000	011111
7	1000000	0111111
8	10000000	01111111
9	100000000	011111111
10	1000000000	0111111111
...

Nämä koodit mahdollistavat myös (kirjoitettaessa merkittyjen kokonaislukujen) ylimääräisen bittien käytön ja siirron (se bitti, joka käytetään ensimmäiseen bittiin). Näin ne pystyvät siirtämään 'm' kokonaislukuja * N yksikköbittiä ja 1 lisäbitin informaatiota sisältävään m*N bittiin dataan.

Symmetriset yksikkökoodit

Seuraava joukko yksikkökoodauksia on symmetrisiä ja niitä voidaan lukea millä tahansa suunnassa. Ne ovat myös välittömästi dekoodattavia molemmissa suunnissa.

n (strictly positive)	Unary code	Alternative	n (non-negative)
1	1	0	0
2	00	11	1
3	010	101	2
4	0110	1001	3
5	01110	10001	4
6	011110	100001	5
7	0111110	1000001	6
8	01111110	10000001	7
9	011111110	100000001	8
10	0111111110	1000000001	9
...

Kanoniset yksikkökoodit

Kanonisissa yksikköarvoissa, kun maksimi on tiedossa, voidaan käyttää kanonisia yksikkökoodauksia, jotka ovat jonkin verran numeerista luonnetta ja eroavat merkkiperusteisista kodeista. Se käyttää alkuperäistä '0' tai '-1' ($\operatorname {2} ^{n}-1\,$) ja sitten maksimimäärä numeroita ja vähentää sitten numeroita yhdellä kerrallaan ja lisää tai vähentää tulosta numerolla '1'.

n	Unary code	Alternative
1	1	0
2	01	10
3	001	110
4	0001	1110
5	00001	11110
6	000001	111110
7	0000001	1111110
8	00000001	11111110
9	000000001	111111110
10	000000000	111111111

Kanoniset koodit voivat tarvita vähemmän prosessointiaikaa dekoodatessa, kun ne käsitellään numeroina eikä merkkijonona. Jos koodien määrä, jotka vaaditaan symbolin pituudelle, on eri kuin 1, eli on useampia ei-yksikkökoodauksia jostakin pituudesta, ne saavutetaan lisäämällä tai vähentämällä arvoja numeerisesti ilman pituuden vähentämistä tuossa tapauksessa.

Yleistetty yksikkökoodaus

Subhash Kak esitteli yleistetyn version yksikkökoodauksesta, jolla voidaan esittää lukuja paljon tehokkaammin kuin standardiyksikkökoodauksella. Tässä on esimerkki yleistetystä yksikkökoodauksesta kokonaisluvuille 0–15, joka vaatii vain 7 bittiä (missä kolme bittiä valitaan mielivaltaisesti kolmen yhden sijasta standardiyksikkössä näyttääkseen luvun). Huomaa, että esitys on syklinen, missä käytetään merkintöjä esittääkseen korkeammat kokonaisluvut korkeammissa sykleissä.

n	Unary code	Generalized unary
0	0	0000000
1	10	0000111
2	110	0001110
3	1110	0011100
4	11110	0111000
5	111110	1110000
6	1111110	0010111
7	11111110	0101110
8	111111110	1011100
9	1111111110	0111001
10	11111111110	1110010
11	111111111110	0100111
12	1111111111110	1001110
13	11111111111110	0011101
14	111111111111110	0111010
15	1111111111111110	1110100

Yleistetty yksikkökoodaus vaatii, että esitettävien lukujen alue määritellään etukäteen, koska tämä alue määrittää tarvittavien bittien määrän.

Katso myös

• Unary numeral system

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

Read or create/edit this page in another language

• Unary coding in English