Univerzális kód

Az egész számok univerzális kódja az adattömörítésben  egy olyan előtagkód, amely a pozitív egész számokat bináris szavakká alakítja, azzal a kiegészítő tulajdonsággal, hogy az egész számok valós valószínűségi eloszlása ​​esetén, amíg az eloszlás monoton (vagyis bármely ) esetén A bináris szavak hossza a várható hosszúság állandó tényezőjén belül van, amelyet az optimális kód az adott valószínűségi eloszláshoz rendelne.

Egy univerzális kód akkor aszimptotikusan optimális, ha a tényleges és az optimális várható hosszúság közötti együtthatót a kód információs entrópiafüggvénye hozza összefüggésbe, amely 1-hez közelít, ahogy az entrópia a végtelenhez közelít.

A legtöbb egész szám előtagkód hosszabb kulcsszavakat rendel a nagyobb egész számokhoz. Egy ilyen kód felhasználható a lehetséges üzenetek halmazából származó üzenet hatékony kódolására úgy, hogy az üzenetek halmazát egyszerűen a valószínűség szerint csökkenő sorrendbe rendezzük, majd továbbítjuk a kívánt üzenet indexét. Az univerzális kódokat általában nem használják jól ismert valószínűségi eloszlások esetén.

Az univerzális kódok a következők:

• Unáris kódolás
• Elias gamma kód
• Elias delta kód
• Elias Omega kód
• delta kód
• Fibonacci kódolás
• Exponenciális Golomb kód

Néhány nem univerzális kód:

• egyetlen kódolás , az Elias kódokban használatos
• Rice kódolás
• Golomb kódolás

Nem univerzalitásuk abban nyilvánul meg, hogy ha bármelyiket használjuk a Gauss-Kuzmin eloszlás vagy a zéta eloszlás kódolására s=2 paraméterrel, akkor a kulcsszó várható hossza végtelen. Például, ha zéta-eloszlásonként egyhelyi kódolást használunk, a következő várt hosszt kapjuk:

Gyakorlati felhasználás adattömörítésben

A Huffman-kód és az aritmetikai kódolás (ha együtt használhatók) jobb eredményeket ad, mint bármely más univerzális kód.

Az univerzális kódok azonban hasznosak, ha a Huffman-kód nem használható – például amikor nem lehet meghatározni az egyes üzenetek pontos valószínűségét, de a valószínűségek rangsorolása ismert.

Az általános kódok akkor is hasznosak, ha a Huffman-kód nem működik megfelelően. Például, ha a feladó ismeri az üzenet valószínűségét, de a címzett nem, a Huffman-kód megköveteli, hogy a valószínűségeket átadják a címzettnek. Az általános kód használata kiküszöböli ezeket a kellemetlenségeket.

Minden univerzális kód megadja a valószínűségek saját "implikált eloszlását" , ahol  az i-edik kulcsszó hossza és  az átviteli szimbólum valószínűsége. Ha a tényleges üzenetvalószínűség – és a Kullback-Leibler távolság minimalizál egy kódot -val , akkor az optimális Huffman-kód ehhez az üzenetkészlethez egyenértékű lesz ezzel a kóddal. Mivel az univerzális kódok gyorsabbak, mint a Huffman-kód, az univerzális kódot részesítjük előnyben olyan esetekben, amikor elég kicsi.

Bármilyen geometriai eloszlás esetén a Golomb kódolás az optimális. Az univerzális kódok esetében az implikált eloszlás megközelítőleg engedelmeskedik egy hatványtörvénynek , például pontosabban a Zipf-törvénynek . A Fibonacci-kód esetében az implikált eloszlás megközelítőleg engedelmeskedik a törvénynek , ahol az aranymetszés aránya .

Linkek

• Egész szám kódolás