Golomb kódok

A Golomb kódok entrópiakódok  családját alkotják . A Golomb kód e család egyik képviselőjét is jelentheti.

Tekintsünk egy forrást, amely függetlenül generál nemnegatív egész számokat valószínűségekkel , ahol  egy tetszőleges pozitív szám, amely nem haladja meg az 1-et, azaz egy geometriai eloszlással leírt forrás . Ha egy pozitív egész szám olyan, hogy

akkor egy ilyen forrás optimális karakterenkénti kódja (azaz az a kód, amely minden kódolt karaktert egy bizonyos kódszóhoz társít) egy olyan kód lesz, amelyet a Solomon Golomb által javasolt eljárásnak megfelelően állítottak össze, amely szerint bármely kódolt szám ismert kódszóval, egy szám egy unáris jelölésével és az alábbiakban leírt eljárásnak megfelelően kódolt számmal, az osztás többi része :

1. Ha 2 hatványa, akkor a maradék kód a szám bináris reprezentációja , bitekben elhelyezve .
2. Ha nem 2 hatványa, akkor a szám kiszámításra kerül . További:

Később R. Gallagher és D. Van Voorhees kimutatta, hogy a Golomb által javasolt kód nemcsak a fenti kritériumot kielégítő diszkrét értékkészlethez optimális , hanem minden olyan értékhez is, amelyre igaz a kettős egyenlőtlenség.

ahol  egy pozitív egész szám. Mivel minden esetben mindig legfeljebb egy érték van , amely kielégíti a fenti egyenlőtlenséget, a S. Golomb által javasolt geometriai forrás kódolási eljárása minden értékre optimálisnak bizonyul .

A Golomb kód rendkívül könnyen megvalósítható, de nem mindig optimális változatát abban az esetben, ha 2 hatványa van, Rice kódnak nevezzük.

Példa

Let , a szám kódolása kötelező .

Az az érték, amely kielégíti a kettős Gallagher-Van Voorhees egyenlőtlenséget .

A fent leírt kódolási eljárásnak megfelelően a 13 kódolt számnak megfelelő kódszót az n/m hányados unáris reprezentációjaként állítjuk elő:

(unáris kód , azaz q nulla, majd egy),

és kódolt maradék

(kód , vagyis maga a maradék, bitben írva).

Az eredményül kapott kódszó

Lásd még

• Exponenciális Golomb kód

Linkek

• SW Golomb. Run-length kódolások  // IEEE Trans. inf. Theor. - 1966. - 3. szám, IT-12 . - P. 399-401.
• R. G. Gallager, D. C. Van Voorhis. Optimális forráskódok geometriai eloszlású egész ábécékhez  // IEEE Trans. inf. Theor. - 1975. - 2. szám, IT-21 . - P. 228-230.
• R. R. Rice, J. R. Plaunt. Adaptív változó hosszúságú kódolás az űrhajó televíziós adatainak hatékony tömörítéséhez  // IEEE Trans. a közösségen. - 1971. - 1. évf. 16. (9) bekezdése alapján. - P. 889-897.
• 2.3 Golomb-kódok / Amir Said, Az optimális paraméterezett előtagkódok meghatározásáról az adaptív entrópiakódoláshoz. HPL-2006-74