Előtag kódja

Az előtag kód a kódoláselméletben  egy változó hosszúságú szóból álló kód, amely a következő tulajdonsággal rendelkezik (a Fano feltétel teljesülése ) : ha a kód tartalmazza az a szót , akkor bármely nem üres b karakterlánc esetén az ab szó nem létezik a kódban. Bár az előtag kódja különböző hosszúságú szavakból áll, ezek a szavak elválasztó karakter nélkül is írhatók.

Például a 0, 10 és 11 szavakból álló kód előtag, a 01001101110 üzenet pedig egyedi módon bontható szavakra:

0 10 0 11 0 11 10

A 0, 10, 11 és 100 szavakból álló kód nem előtag, ugyanaz az üzenet többféleképpen értelmezhető.

0 10 0 11 0 11 10 0 100 11 0 11 10

Definíció

Az úgynevezett "előtagok" a kódszó utolsó karakterének szekvenciális elvetésével szerezhetők meg. Például az 11101101 kódkombinációnál az előtagok 11101101, 1110110, 111011, 11101, 1110, 111, 11, 1.

Akár így:

Minden kódkombinációt írunk, kezdő nullák nélkül: 0 //előtag //egy //10 <- megjegyzés (kizárja) azokat, amelyek mások kezdete //tizenegy 100 //előtag 101 //kommentár nélküli kódok - az előtagkód előtagjai. 110 111 ... //legyen ez mind három bites kombináció.

Az eredményül kapott kódsorozat (0, 100, 101, 110, 111) megegyezik a Huffman kódsorozat előtagjával .

Ha a kódkombinációk között nincs szóköz vagy egyéb írásjel, akkor az 111011101 kombináció egyértelmű dekódolásához egyik kódkombináció sem reprezentálható a felsorolt ​​opciókkal (előtagokkal). Egy kódot előtagnak nevezünk, ha egyik kombinációja sem ugyanazon kód másik kombinációjának előtagja. A kódkombináció azon részét, amely a kombináció előtagját kiegészíti, utótagnak nevezzük. Az előtag kódok vizuálisan ábrázolhatók kódfák segítségével. Ha a kódfa egyik csomópontja sem az adott kód csomópontja, akkor az előtag tulajdonságaival rendelkezik. A másokhoz nem kapcsolódó facsomópontokat levélcsomópontoknak nevezzük. A hozzájuk tartozó kombinációk előtagkód-kombinációk.

Példák

Minden fix hosszúságú szókód nyilvánvalóan előtagkód. Nézzünk néhány nem triviális példát.

• Telefonszámok vezetékes hálózatokban.
• UTF-8 .
• Az adattömörítéshez használt Huffman kód .
• Pascal és más nyelvek szintaxisa LL(1) szintaxissal (feltételezve, hogy a lexéma szimbólum, az operátor pedig egy szó ). Ezért az operátor típusának meghatározásához a Pascal fordítónak nem kell visszaadnia az olvasott karaktereket a folyamba, vagy nem kell tárolnia a veremben .

A morze kód nem előtag. A ponton és a gondolatjelen kívül egy elválasztó karaktert is tartalmaz – egy kötőjel hosszúságú szünetet .

Lásd még

• Kraft-McMillan egyenlőtlenség