Előtag kód - Prefix code

Az előtag kód egy olyan kódrendszertípus, amely megkülönböztethető az "előtag tulajdonság" birtoklásával, amely megköveteli, hogy a rendszerben ne legyen olyan teljes kódszó, amely a rendszer bármely más kódszavának előtagja (kezdeti szegmense) legyen. Triviálisan igaz a rögzített hosszúságú kódokra, tehát csak egy szempont a változó hosszúságú kódban .

Például a (z) {9, 55} kódszavakkal ellátott kód az előtag tulajdonsággal rendelkezik; a {9, 5, 59, 55} kódból álló kód nem, mert az "5" az "59" és az "55" előtag. Az előtag kód egyedülállóan dekódolható kód : teljes és pontos sorrendet kapva a vevő minden szót azonosíthat anélkül, hogy a szavak között külön jelölőt igényelne. Vannak azonban egyedülállóan dekódolható kódok, amelyek nem előtag-kódok; például az előtag kód fordítottja továbbra is egyedileg dekódolható (ez utótag kód), de nem feltétlenül előtag kód.

Az előtag-kódok más néven előtag nélküli kódok , előtag-állapotkódok és pillanatnyi kódok . Bár a Huffman-kódolás csak egy a sok algoritmus közül az előtag-kódok levezetésére, az előtag-kódokat széles körben "Huffman-kódoknak" is nevezik, még akkor is, ha a kódot nem Huffman-algoritmus állította elő. A vessző nélküli kód kifejezést néha az előtag nélküli kódok szinonimájaként is alkalmazzák, de a legtöbb matematikai könyvben és cikkben (pl.) A vessző nélküli kódot önszinkronizáló kódra , az előtagkódok alosztályára használják.

Az előtagkódok használatával az üzenet összefűzött kódszavak sorozataként továbbítható, sávon kívüli jelölők vagy (alternatívaként) speciális jelölők nélkül a szavak között az üzenet szavainak keretezésére . A címzett egyértelműen dekódolhatja az üzenetet, ismételten megkeresve és eltávolítva az érvényes kódszavakat alkotó szekvenciákat. Ez általában nem lehetséges olyan kódokkal, amelyekből hiányzik az előtag tulajdonság, például {0, 1, 10, 11}: a vevő egy kódszó elején "1" -et olvasva nem tudná, hogy ez volt-e a teljes kódszó " 1 ", vagy pusztán a" 10 "vagy" 11 "kódszó előtagja; így a "10" karakterlánc akár egyetlen kódszóként, akár az "1", majd a "0" szavak összefűzéseként értelmezhető.

A változó hosszúságú Huffman-kódok , az országhívó kódok , az ISBN-ek országa és kiadói részei, az UMTS W-CDMA 3G vezeték nélküli szabványban használt másodlagos szinkronizációs kódok és a legtöbb számítógépes mikroarchitektúra utasításkészlete (gépi nyelve) előtag-kód.

Az előtag-kódok nem hibajavító kódok . A gyakorlatban egy üzenetet előbb tömöríthetünk egy előtag kóddal, majd az átvitel előtt ismét kódolhatjuk csatornakódolással (beleértve a hibajavítást is).

Bármely egyedülállóan dekódolható kódhoz tartozik egy előtag kód, amelynek azonos a kódszó hossza. Kraft egyenlőtlensége jellemzi azokat a kódszavas hosszúságokat, amelyek egy egyedülállóan dekódolható kódban lehetségesek.

Technikák

Ha minden szót a kód hossza azonos, a kód nevezzük fix hosszúságú kódot , vagy egy blokk-kód (bár a kifejezés blokk kód is használható fix méretű a hibajavító kódokat a csatorna kódolási ). Például az ISO 8859-15 betűk mindig 8 bit hosszúak. Az UTF-32 / UCS-4 betűk mindig 32 bit hosszúak. Az ATM-cellák mindig 424 bit (53 bájt) hosszúak. Egy rögzített hosszúságú, rögzített hosszúságú k bit kódolhat akár forrásszimbólumokat. ${\ displaystyle 2 ^ {k}}$

A rögzített hosszúságú kód szükségszerűen előtag-kód. Bármelyik kódot rögzített hosszúságú kódgá lehet alakítani úgy, hogy rögzített szimbólumokat tölt be a rövidebb előtagokra, hogy megfeleljen a leghosszabb előtagok hosszának. Alternatív módon ilyen kitöltőkódokat lehet alkalmazni redundancia bevezetésére, amely lehetővé teszi az autokorrekciót és / vagy a szinkronizálást. A rögzített hosszúságú kódolások azonban nem hatékonyak olyan helyzetekben, amikor egyes szavak sokkal nagyobb valószínűséggel kerülnek továbbításra, mint mások.

A csonkított bináris kódolás a rögzített hosszúságú kódok egyszerű általánosítása azoknak az eseteknek a kezelésére, amikor az n szimbólumok száma nem kettő hatványa. A forrásszimbólumokhoz k és k +1 hosszúságú kódszavakat rendelünk , ahol k úgy van megválasztva, hogy 2 ^k <n ≤ 2 ^{k + 1} .

A Huffman-kódolás egy kifinomultabb technika a változó hosszúságú előtag-kódok elkészítésére. A Huffman-kódolási algoritmus bemenetként veszi azokat a frekvenciákat, amelyeknek a kódszavaknak rendelkezniük kell, és egy olyan előtag-kódot készít, amely minimalizálja a kódszó hosszának súlyozott átlagát. (Ez szorosan összefügg az entrópia minimalizálásával.) Ez a veszteségmentes adattömörítés egyik formája, amely az entrópia kódolásán alapul .

Néhány kód a kódszó végét egy speciális "vessző" szimbólummal jelöli, amely eltér a normál adatoktól. Ez némileg analóg a szavak közötti szóközökkel egy mondatban; megjelölik, hol az egyik szó véget ér, hol a másik kezdődik. Ha minden kódszó vesszővel végződik, és a vessző nem jelenik meg máshol a kódszóban, akkor a kód automatikusan előtagmentes. A modern kommunikációs rendszerek azonban mindent az "1" és a "0" sorozataként küldenek - egy harmadik szimbólum hozzáadása drága lenne, és csak a szavak végén történő használata nem hatékony. A morze kód egy változó hosszúságú kód vesszővel ellátott példája. A betűk közötti hosszú szünetek és a szavak közötti még hosszabb szünetek segítenek az embereknek felismerni az egyik betű (vagy szó) végének és a következő kezdetét. Hasonlóképpen, a Fibonacci kódolás "11" -et használ minden kódszó végének jelölésére.

Az önszinkronizáló kódok olyan előtag-kódok, amelyek lehetővé teszik a keretszinkronizálást .

Kapcsolódó fogalmak

Az utótag kód olyan szavak összessége, amelyek egyikének sem képzője más; ekvivalensen olyan szavak halmaza, amelyek az előtag kód fordítottja. Csakúgy, mint egy előtag kódnál, a karakterlánc reprezentációja az ilyen szavak összefűzésének is egyedi. A bifix kód olyan szavak összessége, amelyek mind előtag, mind utótag kódok. Az optimális előtagkód egy minimális átlagos hosszúságú előtagkód. Vagyis tegyünk fel egy n szimbólumból álló ábécét valószínűséggel a C előtag kódhoz . Ha C ' egy másik előtag kód, és a C' kódszavainak hossza , akkor . ${\ 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})} \!}$

A ma használt előtag-kódok

Példák az előtag kódokra:

• változó hosszúságú Huffman-kódok
• országhívószámok
• Chen – Ho kódolás
• az ISBN-ek ország- és kiadói részei
• az UMTS W-CDMA 3G vezeték nélküli szabványban használt másodlagos szinkronizációs kódok
• VCR Plus + kódok
• Unicode transzformációs formátum , különös tekintettel az Unicode karakterek kódolására szolgáló UTF-8 rendszerre , amely mind előtag nélküli, mind önszinkronizáló kód
• változó hosszúságú mennyiség

Technikák

Az előtagkódok készítéséhez általánosan használt technikák közé tartoznak a Huffman-kódok és a korábbi Shannon – Fano-kódok , valamint az univerzális kódok, mint például:

• Elias delta kódolás
• Elias gamma kódolás
• Elias omega kódolás
• Fibonacci kódolás
• Levenshtein kódolás
• Unárikus kódolás
• Golomb Rice kód
• Kihúzódó ellenőrző tábla (egyszerű kódolási technika, amely előhívókódokat állít elő)
• Vbinary kódolás

Megjegyzések

Hivatkozások

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Kódok és automaták . Matematika enciklopédia és alkalmazásai. 129 . Cambridge: Cambridge University Press . ISBN   978-0-521-88831-8 . Zbl   1187.94001 .
• Elias, Peter (1975). Msgstr "Univerzális kódszókészletek és az egész számok ábrázolása". IEEE Trans. Inf. Elmélet . 21 (2): 194–203. doi : 10.1109 / tit.1975.1055349 . ISSN   0018-9448 . Zbl   0298.94011 .
• DA Huffman, "Módszer a minimális redundancia kódok felépítésére", Proceedings of the IRE, 1952. szeptember, 1098–1102. Oldal (Huffman eredeti cikke)
• Profil: David A. Huffman , Scientific American , 1991. szeptember, 54–58. Oldal (Háttértörténet)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest és Clifford Stein . Bevezetés az algoritmusokba , második kiadás. MIT Press és McGraw-Hill, 2001. ISBN   0-262-03293-7 . 16.3. Szakasz, 385–392.
•  Ez a cikk magában  köztulajdonban lévő anyagok a General Services Administration dokumentumot: „Federal Standard 1037C” .

Külső linkek

• Kódok, fák és a Kona Macphee előtag tulajdonság