Etuliitteen koodi - Prefix code

Etuliite koodi on eräänlainen koodin järjestelmä erottuu hallussa "etuliite omaisuus", joka vaatii, ettei kokonainen koodisana järjestelmässä, joka on etuliite (alkusegmentin) minkään muun koodisanan järjestelmässä. Se on triviaalisesti totta kiinteän pituisen koodin osalta, joten vain muuttuvan pituisen koodin näkökohta .

Esimerkiksi koodisanoilla {9, 55} olevalla koodilla on etuliiteominaisuus; koodi, joka koostuu {9, 5, 59, 55}, ei ole, koska "5" on etuliite "59" ja myös "55". Etuliitekoodi on ainutlaatuisesti dekoodattava koodi : täydellisen ja tarkan sekvenssin saamiseksi vastaanotin voi tunnistaa jokaisen sanan tarvitsematta erityistä merkintää sanojen väliin. On kuitenkin olemassa ainutlaatuisesti dekoodattavia koodeja, jotka eivät ole etuliitekoodeja; esimerkiksi etuliitekoodin kääntöpuoli on edelleen ainutlaatuisesti dekoodattava (se on loppuliitekoodi), mutta se ei välttämättä ole etuliitekoodi.

Etuliitekoodit tunnetaan myös nimellä etuliitteettömät koodit , etuliitteen ehtokoodit ja hetkelliset koodit . Vaikka Huffman-koodaus on vain yksi monista algoritmeista etuliitekoodien johtamiseksi, etuliitekoodeja kutsutaan myös laajalti "Huffman-koodeiksi", vaikka koodia ei olisi tuotettu Huffman-algoritmilla. Termiä pilkuttamaton koodi käytetään joskus myös synonyyminä etuliitteettömille koodeille, mutta useimmissa matemaattisissa kirjoissa ja artikkeleissa (esim. Pilkuttamatonta koodia) tarkoitetaan itsesynkronoituvaa koodia , etuliitekoodien alaluokkaa.

Etuliitekoodeja käyttämällä sanoma voidaan lähettää ketjutettujen koodisanojen sarjana ilman kaistan ulkopuolisia merkintöjä tai (vaihtoehtoisesti) sanojen välisiä erikoismerkkejä sanojen kehystämiseksi . Vastaanottaja voi purkaa viestin yksiselitteisesti etsimällä ja poistamalla toistuvasti sekvenssejä, jotka muodostavat kelvolliset koodisanat. Tämä ei ole yleensä mahdollista koodeilla, joista puuttuu etuliiteominaisuus, esimerkiksi {0, 1, 10, 11}: vastaanotin, joka lukee "1" koodisanan alussa, ei tiedä, oliko se täydellinen koodisana " 1 ", tai vain koodisanan" 10 "tai" 11 "etuliite; joten merkkijono "10" voidaan tulkita joko yhtenä koodisanana tai sanojen "1" ja sitten "0" ketjutuksena.

Eri pituiset Huffman-koodit , maan kutsukoodit , ISBN- maiden maa- ja julkaisijaosat , UMTS W-CDMA 3G -standardissa käytetyt toissijaiset synkronointikoodit ja useimpien tietokoneiden mikroarkkitehtuurien käskyjoukot (konekieli) ovat etuliitekoodeja.

Etuliitekoodit eivät ole virheenkorjauskoodeja . Käytännössä viesti voidaan ensin pakata etuliitekoodilla ja koodata sitten uudelleen kanavakoodauksella (virhekorjaus mukaan lukien) ennen lähetystä.

Kaikille ainutlaatuisesti dekoodattaville koodeille on etuliitekoodi, jolla on samat koodisanan pituudet. Kraftin eriarvoisuus luonnehtii koodisanan pituuksia, jotka ovat mahdollisia ainutlaatuisesti dekoodattavassa koodissa.

Tekniikat

Jos jokainen sana koodi on sama pituus, koodi kutsutaan kiinteä-koodin , tai lohko-koodi (vaikka termi lohko koodia käytetään myös kiinteän koon virheenkorjauskoodeja in kanavakoodaus ). Esimerkiksi ISO 8859-15 -kirjaimet ovat aina 8 bittiä pitkiä. UTF-32 / UCS-4- kirjainten pituus on aina 32 bittiä. ATM-solut ovat aina 424 bittiä (53 tavua) pitkiä. Kiinteän pituinen, kiinteän pituinen k- bittinen koodi voi koodata jopa lähdesymboleihin. ${\ displaystyle 2 ^ {k}}$

Kiinteän pituinen koodi on välttämättä etuliitekoodi. Mikä tahansa koodi on mahdollista muuttaa kiinteän pituiseksi koodiksi täyttämällä kiinteät symbolit lyhyempiin etuliitteisiin pisin etuliitteiden pituuden saavuttamiseksi. Vaihtoehtoisesti tällaisia ​​täytekoodeja voidaan käyttää redundanssin aikaansaamiseksi, joka sallii automaattisen korjauksen ja / tai synkronoinnin. Kiinteän pituiset koodaukset ovat kuitenkin tehottomia tilanteissa, joissa jotkut sanat lähetetään paljon todennäköisemmin kuin toiset.

Lyhennetty binäärikoodaus on suoraviivainen kiinteäpituisten koodien yleistäminen tapausten käsittelemiseksi, joissa symbolien lukumäärä n ei ole kahden voima. Lähdesymboleille on annettu koodisanat, joiden pituus on k ja k +1, missä k valitaan siten, että 2 ^k <n ≤ 2 ^{k + 1} .

Huffman-koodaus on kehittyneempi tekniikka vaihtelevan pituisten etuliitekoodien rakentamiseksi. Huffman-koodausalgoritmi ottaa syötteenä taajuuksia, jotka koodisanoilla pitäisi olla, ja rakentaa etuliitteen koodin, joka minimoi koodisanan pituuksien painotetun keskiarvon. (Tämä liittyy läheisesti entropian minimointiin.) Tämä on muoto häviöttömästä datan pakkaamisesta, joka perustuu entropiakoodaukseen .

Jotkut koodit merkitsevät koodisanan lopun erityisellä "pilkku" -symbolilla, joka poikkeaa tavallisista tiedoista. Tämä on jonkin verran analogista lauseen sanojen välille; ne merkitsevät, missä yksi sana loppuu ja toinen alkaa. Jos jokainen koodisana päättyy pilkkuun eikä pilkku näy muualla koodisanassa, koodi on automaattisesti etuliiteeton. Nykyaikaiset viestintäjärjestelmät lähettävät kuitenkin kaiken sekvensseinä "1" ja "0" - kolmannen symbolin lisääminen olisi kallista, ja sen käyttö vain sanojen päissä olisi tehotonta. Morse-koodi on jokapäiväinen esimerkki vaihtelevan pituisesta koodista pilkulla. Pitkät tauot kirjainten välillä ja vieläkin pidemmät sanojen väliset tauot auttavat ihmisiä tunnistamaan, missä yksi kirjain (tai sana) päättyy ja seuraava alkaa. Vastaavasti Fibonacci-koodaus käyttää "11" -merkkiä jokaisen koodisanan loppuun.

Itsesynkronoivat koodit ovat etuliitekoodeja, jotka mahdollistavat kehysten synkronoinnin .

Liittyvät käsitteet

Pääte koodi on joukko sanoja yksikään joka on pääte muita; vastaavasti joukko sanoja, jotka ovat etuliitteen koodin käänteisiä. Kuten etuliitekoodin kohdalla, merkkijonon esitys tällaisten sanojen ketjutuksena on ainutlaatuinen. Bifix koodi on joukko sanoja, jotka on sekä etu- ja jälkiliitteen koodi. Optimaalinen etuliite koodi on etuliite koodi pienellä keskimääräinen pituus. Toisin sanoen, oletetaan aakkosto n symbolien todennäköisyydet ja etuliite koodin C . Jos C ' on toinen etuliitekoodi ja C: n koodisanojen pituudet , niin . ${\ displaystyle p (A_ {i})}$${\ displaystyle \ lambda '_ {i}}$${\ displaystyle \ sum _ {i = 1} ^ {n} {\ lambda _ {i} p (A_ {i})} \ leq \ sum _ {i = 1} ^ {n} {\ lambda '_ { i} p (A_ {i})} \!}$

Tänään käytössä olevat etuliitekoodit

Esimerkkejä etuliitekoodeista ovat:

• vaihtelevan pituiset Huffman-koodit
• maakoodit
• Chen – Ho-koodaus
• ISBN- maiden maa- ja julkaisijaosat
• toissijaiset synkronointikoodit, joita käytetään langattomassa UMTS W-CDMA 3G -standardissa
• VCR Plus + -koodit
• Unicode-muunnosmuoto , erityisesti UTF-8- järjestelmä Unicode- merkkien koodaamiseksi , joka on sekä etuliitteetön koodi että itsesynkronoituva koodi
• vaihtelevan pituinen määrä

Tekniikat

Yleisesti käytettyjä tekniikoita etuliitekoodien muodostamiseksi ovat Huffman-koodit ja aikaisemmat Shannon – Fano-koodit sekä yleiskoodit , kuten:

• Elias-delta-koodaus
• Elias-gammakoodaus
• Elias omega -koodaus
• Fibonacci-koodaus
• Levenshtein-koodaus
• Unary-koodaus
• Golomb-riisikoodi
• Hajallaan oleva ruutu (yksinkertainen salaustekniikka, joka tuottaa etuliitekoodeja)
• Vbinaarinen koodaus

Huomautuksia

Viitteet

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Koodit ja automaatit . Matematiikan tietosanakirja ja sen sovellukset. 129 . Cambridge: Cambridge University Press . ISBN   978-0-521-88831-8 . Zbl   1187.94001 .
• Elias, Peter (1975). "Universaalit koodisanajoukot ja kokonaislukujen esitykset". IEEE Trans. Inf. Teoria . 21 (2): 194–203. doi : 10.1109 / tissi 1975.1055349 . ISSN   0018-9448 . Zbl   0298.94011 .
• DA Huffman, "Menetelmä vähimmäisredundanssikoodien muodostamiseksi", Proceedings of the IRE, syyskuu 1952, s. 1098–1102 (Huffmanin alkuperäinen artikkeli)
• Profiili: David A. Huffman , Scientific American , syyskuu 1991, s. 54–58 (taustakertomus)
• Thomas H.Cormen , Charles E.Leiserson , Ronald L.Rivest ja Clifford Stein . Johdanto algoritmeihin , toinen painos. MIT Press ja McGraw-Hill, 2001. ISBN   0-262-03293-7 . Osa 16.3, s. 385–392.
•  Tämä artikkeli sisältää  julkista aineistoa päässä General Services Administration asiakirjan "Federal Standard 1037C" .

Ulkoiset linkit

• Koodit, puut ja Kona Macpheen etuliiteominaisuus