Elias gamma coding

Elias γ kodlama veya Elias gamma kodlama, Peter Elias tarafından geliştirilen pozitif tam sayıları kodlamak için kullanılan bir evrensel koddur.^[1]^{:197, 199} Bu kodlama, önceden belirlenemeyen üst sınırları olan tam sayıların kodlanmasında en çok kullanılır.

Kodlama[değiştir]

Bir sayı x ≥ 1'i kodlamak için:

$N=\lfloor \log _{2}x\rfloor$ ile sayının en yüksek iki üssü alınır, bu da 2^N ≤ x < 2^N+1 olacak şekilde.
$N$ tane sıfır biti yazılır,
Sonra x sayısının binary şekli, $N+1$ bit uzunluğunda bir sayı olarak eklenir.

Aynı işlemi açıklamak için başka bir yol:

$N$ sayısını unary olarak kodlayın; yani, $N$ tane sıfırı birle sonlandırın.
Bu $N$ kodlamasına $x$ sayısının geri kalan $N$ binary rakamlarını ekleyin.

Bir sayı $x$ için Elias gamma (γ) $2\lfloor \log _{2}(x)\rfloor +1$ bit kullanır.^[1]^:199

Kodlama şu şekilde başlar (kod için implied probability dağılımı açıklık için eklenmiştir):

Sayı	Binary	γ kodlama	İmplied probability
1 = 2⁰ + 0	`1`	`1`	1/2

2 = 2¹ + 0	`1 0`	`0 1 0`	1/8
3 = 2¹ + 1	`1 1`	`0 1 1`	1/8

4 = 2² + 0	`1 00`	`00 1 00`	1/32
5 = 2² + 1	`1 01`	`00 1 01`	1/32
6 = 2² + 2	`1 10`	`00 1 10`	1/32
7 = 2² + 3	`1 11`	`00 1 11`	1/32

8 = 2³ + 0	`1 000`	`000 1 000`	1/128
9 = 2³ + 1	`1 001`	`000 1 001`	1/128
10 = 2³ + 2	`1 010`	`000 1 010`	1/128
11 = 2³ + 3	`1 011`	`000 1 011`	1/128
12 = 2³ + 4	`1 100`	`000 1 100`	1/128
13 = 2³ + 5	`1 101`	`000 1 101`	1/128
14 = 2³ + 6	`1 110`	`000 1 110`	1/128
15 = 2³ + 7	`1 111`	`000 1 111`	1/128

16 = 2⁴ + 0	`1 0000`	`0000 1 0000`	1/512
17 = 2⁴ + 1	`1 0001`	`0000 1 0001`	1/512

Kod Çözme[değiştir]

Elias gamma kodlaması ile kodlanmış bir tam sayıyı çözmek için:

Akıştan 0'ları okuyup sayın, ilk 1'e kadar. Bu 0 sayısını N olarak adlandırın.
Ulaşılan bir rakamın ilk rakamı olarak düşünün, 2^N değeriyle, tam sayının geri kalan N rakamlarını okuyun.

Kullanımlar[değiştir]

Gamma kodlama, en büyük kodlanmış değerin önceden bilinmediği uygulamalarda veya küçük değerlerin büyük değerlere göre çok daha sık kullanıldığı verileri sıkıştırmasında kullanılır.Şablon:Dubious Bu durumlarda gamma kodlama daha boyut verimli olabilir. Örneğin, yukarıdaki tabloda görülüyor ki, küçük bir sayıyı (örneğin 5) sabit 8-bit boyutunda saklamak 00000101 verirken, γ-kodlama değişken bit boyutunda 00 1 01 verir, 3 bit daha az olacaktır. Büyük sayılar ise (örneğin 254) sabit 8-bit boyutunda 11111110 verirken, γ-kodlama değişken bit boyutunda 0000000 1 1111110 verir, 7 bit fazla olacaktır.

Gamma kodlama, Elias delta codede bir temel taş olarak kullanılır.

Genelleştirmeler[değiştir]

Şablon:See also Gamma kodlama sıfır veya negatif tam sayıları kodlamaz. Sıfırı kodlamak için bir yol, kodlamadan önce 1 eklemek ve kodlamadan sonra 1 çıkarmaktır. Başka bir yol, her sıfır olmayan kodu bir 1 ile başlatmak ve sıfırı tek bir 0 olarak kodlamaktır.

Tüm tam sayıları kodlamak için bir bijection kurmak, sayıları (0, −1, 1, −2, 2, −3, 3, ...) (1, 2, 3, 4, 5, 6, 7, ...) şeklinde eşlemektir. Yazılımda bu en kolay yol, negatif girdileri çift çıktılara, pozitif girdileri ise tek çıktılara eşlemektir, bu da en az anlamlı bit sign bit olarak ters çevrilir:
${\begin{cases}x\mapsto 2x+1&\mathrm {when~} x\geq 0\\x\mapsto -2x&\mathrm {when~} x<0\\\end{cases}}$

Exponential-Golomb coding, gamma kodunu daha "düz" bir güç yasası dağılımına sahip tam sayılara genişletir, şekilde Golomb coding unary kodu genişletir. Bu, sayıyı pozitif bir bölenle bölmek, bölümün bir fazlasının gamma kodunu yazmak ve geri kalanı normal bir binary kodla yazmaktır.