Golomb koder
Golomb- koder er en familie af entropikoder . Golomb-koden kan også betyde en af repræsentanterne for denne familie.
Overvej en kilde, der uafhængigt genererer ikke-negative heltal med sandsynligheder , hvor er et vilkårligt positivt tal, der ikke overstiger 1, det vil sige en kilde beskrevet af en geometrisk fordeling . Hvis et positivt heltal er sådan, at
,
så vil den optimale tegn-for-tegn-kode (det vil sige den kode, der forbinder hvert kodet tegn med et bestemt kodeord) for en sådan kilde være en kode konstrueret i overensstemmelse med proceduren foreslået af Solomon Golomb , ifølge hvilken ethvert kodet tal , med et kendt kodeord, en unær notation af et tal og et kodet i overensstemmelse med proceduren beskrevet nedenfor, resten af divisionen :
![{\displaystyle q=\left[{\frac {n}{m}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5289efd5d43ca2d4a4617e0d1fdc902350bc068)
- Hvis er en potens af 2, så er den resterende kode en binær repræsentation af tallet , placeret i bit.
- Hvis ikke en potens af 2, beregnes tallet . Yderligere:
Senere viste R. Gallagher og D. Van Voorhees, at koden foreslået af Golomb er optimal ikke kun for et diskret sæt værdier, der opfylder ovenstående kriterium, men også for enhver , for hvilken den dobbelte ulighed er sand.
,
hvor er et positivt heltal. Da der for enhver altid højst er én værdi , der opfylder ovenstående ulighed, viser proceduren for kodning af en geometrisk kilde foreslået af S. Golomb sig at være optimal for enhver værdi af .
En ekstremt nem at implementere, men ikke altid optimal, version af Golomb-koden i tilfældet, hvor er en potens af 2, kaldes Rice-koden.
Eksempel
Lad , det er påkrævet at kode nummeret .
Værdien, der opfylder den dobbelte Gallagher-Van Voorhees ulighed .
I overensstemmelse med kodningsproceduren beskrevet ovenfor er kodeordet svarende til det kodede tal 13 konstrueret som en unær repræsentation af kvotienten n/m:
,![{\displaystyle q=\left[{\frac {n}{m}}\right]=\left[{\frac {13}{4}}\right]=3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bda6c0fc99dd767697d009baca714c1dd2a1b11c)
(unær kode , dvs. q nuller efterfulgt af et),
og kodet resten
,
(kode , det vil sige selve resten, skrevet i bits).
Resulterende kodeord
Se også
Links
- SW Golomb. Run-længde-kodninger // IEEE Trans. inf. Theor. - 1966. - nr. 3, IT-12 . - s. 399-401.
- R. G. Gallager, D. C. Van Voorhis. Optimale kildekoder til geometrisk fordelte heltalsalfabeter // IEEE Trans. inf. Theor. - 1975. - nr. 2, IT-21 . - S. 228-230.
- R. R. Rice, J. R. Plaunt. Adaptiv kodning med variabel længde til effektiv komprimering af tv-data fra rumfartøjer // IEEE Trans. på Fællesskabet. - 1971. - Bd. 16(9). - s. 889-897.
- 2.3 Golomb-koder / Amir Said, om bestemmelse af optimale parametriserede præfikskoder til adaptiv entropikodning. HPL-2006-74
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Tabsfri |
| ||||||
| Lyd |
| ||||||
| Billeder |
| ||||||
| Video |
| ||||||