prefixkódot

A prefixkód olyan kódkészlet, amelyben semelyik kódszó nem lehet egy másik kódszó kezdete. Más szóval, a kódjelek úgy vannak megválasztva, hogy a rövidebb kódokat nem lehet azonosítani úgy, hogy egy hosszabb kód előtagjaként lépnek be. Ennek eredménye az azonnali, vissza nem vezető dekódolás: a bejövő bitfolyam első olyan részéhez érve egyetlen érvényes kódjel azonosítható.

A prefixkódok jelentős része egy m apostrofúfa, ahol minden kódszó egy levél útvonalát írja le a teljes m-áras fa egy részén. A dekódolás úgy történik, hogy a bitfolyamot olvassuk, és amikor egy levélhez érkezünk, kiolvassuk a hozzárendelt szimbólumot, majd a folyamatot folytatjuk a fa gyökerétől. Ennek köszönhetően a dekódolás egyaránt hatékony és visszafelé legalábbis nem igényel visszakeresést.

Kraft-egyenlőtlenség: Ha a kódszavak hossza l_i egy D-áris ábécére vonatkozik, akkor sum D^{-l_i} ≤ 1 szükséges feltétel. Teljes kód esetén ez az összeg egyenlő lehet 1-gyel. Binary esetben ez a kifejezés sum 2^{-l_i} ≤ 1 formában írható fel.

Példák: a {0, 10, 110, 111} kódprefixkódnak tekinthető, mert egyik kódszó sem kezdete a másiknak. Jellemző használati területek közé tartozik a variábilis hosszúságú tömörítés, például Huffman-kódolásban, ahol a gyakrabban előforduló szimbólumokat rövidebb kódszavakkal kódolják.

Előnyök és korlátok: a prefixkódok gyors és egyszerű dekódolást biztosítanak, de hatékonyságuk a szimbólumok előfordulási valószínűségétől függ. Gyakran alkalmazzák adatátvitelben és tömörítő rendszerekben, ahol a kódkészletet a forrás statisztikája alapján tervezik.