Golomb coding

Golomb kodlama örneği için bir kaynak x, 0.2'lik bir geometrik dağılım parametresiyle, M = 3'lük Golomb koduyla, 00 iki bit kodu %20'de kullanılır; 010, 011 ve 100 üç bit kodları %38'den fazla kullanılır; %4'ten az durumda 4 bit veya daha fazla gereklidir. Bu kaynak için entropi = 3.610 bit; bu kodla bu kaynak için hız = 3.639 bit; bu nedenle artımlılık = 0.030 bit, yani verim = 0.992 bit/bit.

Golomb kodlama verimsiz veri sıkıştırma yöntemidir ve 1960'larda Solomon W. Golomb tarafından icat edilen bir veri sıkıştırma kodları ailesini kullanır. Geometrik bir dağılım izleyen alfabetler için Golomb kodu, optimum bir önek kodudur, bu da girdi akışındaki küçük değerlerin önemli ölçüde daha sık göründüğü durumlarda Golomb kodlama için oldukça uygundur.

Rice kodlama

Rice kodlama (Robert F. Rice tarafından icat edilmiştir) Golomb kodlarının bir alt kümesini kullanarak daha basit (ama muhtemelen alt optimum) bir önek kodu üretmeyi ifade eder. Rice bu kod setini uyarlanabilir bir kodlama şemasında kullandı; "Rice kodlama" bu uyarlanabilir şema veya bu Golomb kodları alt kümesini kullanma anlamına gelebilir. Golomb kodunda ayarlanabilir bir parametre herhangi bir pozitif tam sayı değeri olabilirken, Rice kodları, ayarlanabilir parametrenin ikinin bir kuvveti olduğu kodlardır. Bu, Rice kodlarının bilgisayarda kullanımını kolaylaştırır, çünkü ikili aritmetikte 2 ile çarpma ve bölme daha verimli bir şekilde uygulanabilir.

Rice, geometrik dağılımların zamanla değiştiğini, tam olarak bilinmediğini veya her ikisinin de olduğunu göz önünde bulundurarak bu daha basit alt kümeyi önerdi, bu nedenle görünüşte optimum kodu seçmek oldukça avantajlı olmayabilir.

Rice kodlama, birkaç verimsiz resim sıkıştırma ve ses veri sıkıştırma yönteminde entropi kodlama aşaması olarak kullanılır.

Genel bakış

Bu görüntü, M parametresi en iyi şekilde seçildiğinde Golomb kodunun artımlılığını, p(0) >= 0.45 için bit cinsinden gösterir.

Kodların oluşturulması

Golomb kodlama, bir girdi değeri x'i, M ile bir bölme işlemi sonucunda elde edilen iki parçaya ayırır: q, bölüm sonucu ve r, kalan. Söz konusu parçalar sırasıyla tekli kodlama ile gönderilir, ardından kesilmiş ikili kodlama ile gönderilir. M = 1 olduğunda, Golomb kodlama tekli kodlamaya eşittir.

Golomb-Rice kodları, bir sayıyı belirli bir "kova" (q) konumu ve "kova" içindeki "ofset" (r) ile gösteren kodlar olarak düşünülebilir. Örnek görüntü, M = 3'lük Golomb-Rice parametresi kullanılarak tamsayı x'in kodlanması için q ve r değerlerini gösterir, kaynak olasılıkları 0.2'lik bir geometrik dağılım izler.

Formüller olarak, iki parça aşağıdaki ifade ile verilir, burada x kodlanan olumsuz tam sayıdır:

$q=\left\lfloor {\frac {x}{M}}\right\rfloor$

ve

$r=x-qM$.

q ve r, değişken sayıda bitlerle kodlanır: q tekli kodla, r ise Rice kodu için b bit, veya Golomb kodu için b veya math|b+1 bitlerle kodlanır (yani, M ikinin bir kuvveti değildir), burada $b=\lfloor \log _{2}(M)\rfloor$. Eğer $r<2^{b+1}-M$ ise, r'yi b bit kullanarak ikili temsiliyle kodlayın; aksi takdirde, b + 1 bit kullanarak r + 2^{b+1} - M sayısını ikili temsil ile kodlayın. Açıkça, $b=\log _{2}(M)$ eğer M bir ikinin kuvveti ise ve biz tüm r değerlerini b bitlerle kodlayabiliriz.

x, Golomb tarafından işlenen bir Bernoulli sürecinin uzunluğudur ve geometrik bir dağılımda başlar. M parametresinin en iyi seçimi, ilgili Bernoulli sürecinden bir fonksiyondur, bu süreç p = P(x=0) başarı olasılığı ile parametrelenmiştir. M, dağılımın medyanı veya medyan ±1'dir. Aşağıdaki eşitsizliklerle belirlenebilir:

$(1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M},$

bu da şu şekilde çözülebilir:

$M=\left\lceil -{\frac {\log(2-p)}{\log(1-p)}}\right\rceil$.

Örneğin, p(0) = 0.2 için:

$M=\left\lceil -{\frac {\log(1.8)}{\log(0.8)}}\right\rceil =\left\lceil 2.634\right\rceil =3$.

Bu dağılım için Golomb kodu, aynı olasılıklar için Huffman koduna eşdeğerdir, eğer sonsuz bir kaynak değeri kümesi için Huffman kodu hesaplanabilirse.

İşaretli tamsayılar ile kullanım

Golomb'un şeması, olumsuz sayılar içeren dizileri kabul etmek için genişletilebilir, "çakışma ve geçiş" bir şeması kullanarak, bütün değerler olumsuz bir sayıdan benzersiz ve tersine çevrilebilir bir şekilde yeniden atanır. Dizi 0, -1, 1, -2, 2, -3, 3, -4, 4, ... şeklinde başlar. n-inci olumsuz değer (yani, tmath|-n) tek bir sayıya (tmath|2n-1) eşleştirilir ve m-inci olumsuz değer çift sayıya (tmath|2m) eşleştirilir. Bu, x olumlu bir değer ise ($x'=2|x|=2x,\ x\geq 0$), y olumsuz bir değer ise ($y'=2|y|-1=-2y-1,\ y<0$) ifade edilebilir. Bu kod basitliği açısından kullanılabilir, ancak alt optimum olabilir. İki tarafa yönelik geometrik dağılımlar için gerçekten optimum kodlar, dağılım parametrelerine bağlı olarak Golomb kodunun çeşitli varyantlarını içerir, buradaki gibi.

Basit algoritma

Aşağıda, kalan kod için basit kesilmiş ikili kodlama kullanan Rice-Golomb kodlama verilmiştir (kalan kodların istatistik dağılımı düz değilse ve özellikle tüm mümkün kalanların kullanılmadığı durumlarda, aritmetik veya Huffman kodlamaları gibi farklı uzunlukta ikili kodlamalar mümkündür). Bu algoritma, M parametresi bir ikinin kuvveti ise, daha basit Rice kodlamasına eşdeğer olacaktır:

1. M parametresini bir tam sayı değerine sabitleyin.
2. N, kodlanacak sayı için,

kalan = r = N mod M

1. Kod sözcüğü oluşturun

Kalan kodu (kesilmiş ikili kodlama ile)

b = \lfloor\log_2(M)\rfloor olsun

Eğer r \ge 2^{b+1}-M ise, r+2^{b+1}-M sayısını b + 1 bit kullanarak ikili temsiliyle kodlayın.

Kod çözme:

1. q'nin tekli temsilini çözün (kodun başındaki 1'lerin sayısını sayın)
2. 0 ayrımcısını atlayın
3. b = \lfloor\log_2(M)\rfloor olsun

Aksi takdirde, b + 1 biti r olarak bir ikili sayı olarak yorumlayın, kalan r = r' - 2^{b+1} + M olacaktır

1. N = q * M + r hesaplayın

Örnek

M = 10 olsun. Böylece b = \lfloor\log_2(10)\rfloor = 3. Kesinti noktası 2^{b+1} - M = 16 - 10 = 6.

Bölüm kısmının kodlanması Şablon:Mvar çıktı bitleri 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 $\vdots$ $\vdots$ N $\underbrace {111\cdots 111} _{N}0$

Kalan kısmının kodlanması Şablon:Mvar ofset ikili çıktı bitleri 0 0 0000 000 1 1 0001 001 2 2 0010 010 3 3 0011 011 4 4 0100 100 5 5 0101 101 6 12 1100 1100 7 13 1101 1101 8 14 1110 1110 9 15 1111 1111

Örneğin, M = 10'luk bir Rice-Golomb kodlama kullanarak, ondalık 42 sayısı ilk olarak q = 4 ve r = 2 olarak ayrılacak ve qcode(q),rcode(r) = qcode(4),rcode(2) = 11110,010 olarak kodlanacaktır (ayrılacak virgülü kodlamada göndermenize gerek yok, çünkü q kodunun sonundaki 0, q'nin nerede biteceğini ve r'nin nerede başlayacağını belirtir; her iki qcode ve rcode da kendi kendini sınırlandırır).

Uzunluk kodlaması için kullanım

P ve 1 – p bu bölümde önceki bölümlerde kullanıldığına göre tersidir.

P ve Q sembollerinden veya iki olaydan oluşan bir alfabet veya küme verildiğinde, sırasıyla p ve (1 – p) olasılıkları ile, burada p ≥ 1/2, Golomb kodlama bir veya daha fazla P'nin sıfır veya daha fazla uzunluklarını Q'lar tarafından ayrılmış şekilde kodlamak için kullanılabilir. Bu uygulamada, M parametresinin en iyi ayarlanması, yakın tam sayıya -1/log2p olarak bulunur. p = 1/2 olduğunda, M = 1 ve Golomb kodu tekli koda (n ≥ 0 P'lerden sonra bir Q, n ones izleyen bir zero) eşdeğerdir. Daha basit bir kod aranıyorsa, -log2(-log2 p) yakınındaki bir tam sayıya sahip Golomb-Rice parametresi mvar|b (yani, Golomb parametresi math|M=2^b) atanabilir; ancak her zaman en iyi parametre değilse de, genellikle en iyi Rice parametresidir ve sıkıştırma performansı optimum Golomb koduna oldukça yakındır. (Rice, veriler için farklı kodlar kullanarak en iyi olanını bulmak için çeşitli kodlar önerdi. Daha sonra bir JPL araştırmacısı, kod parametresini optimize etme veya tahmin etme yöntemlerini önerdi.)

Uzunlukları kodlayan bir Rice kodu kullanıldığında, b bitli ikili bölümü olan p olasılığına sahip bir X dizisini kodlamak için, eğer math|P[bit k-uzunluklu bir parçanın parçasıdır] k-uzunluklu bir parçanın olasılığıdır (k-1 P'ler ve bir Q) ve (k-uzunluklu bir parçanın sıkıştırma oranı) o parçanın sıkıştırma oranıdır, o zaman beklenen sıkıştırma oranı

${\begin{aligned}\mathbb {E} [{\text{sıkıştırma oranı}}]&=\sum _{k=1}^{\infty }({\text{k-uzunluklu bir parçanın sıkıştırma oranı}})\cdot \mathbb {P} [{\text{bit k-uzunluklu bir parçanın parçasıdır}}]\\&=\sum _{k=1}^{\infty }{\frac {b+1+\lfloor 2^{-b}(k-1)\rfloor }{k}}\cdot kp^{k-1}(1-p)^{2}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \sum _{i=j2^{b}+1}^{(j+1)2^{b}}p^{i-1}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \left(p^{2^{b}j}-p^{2^{b}(j+1)}\right)\\&=(1-p)\cdot \left(b+\sum _{m=0}^{\infty }p^{2^{b}m}\right)\\&=(1-p)\cdot \left(b+{\left(1-p^{2^{b}}\right)}^{-1}\right)\\\end{aligned}}$

Sıkıştırma genellikle 1-math|E[sıkıştırma oranı] ile ifade edilir, sıkıştırılan oran. p ≈ 1 için, uzunluk kodlama yaklaşımı sıkıştırma oranları entropiye yakındır. Örneğin, p=0.99 için Rice kodu b=6 kullanarak %91.89 sıkıştırma sağlar, entropi sınırı ise %91.92'dir.

Uyarlanabilir uzunluk Golomb-Rice kodlama

Bir tamsayı veri dağılımı bilinmiyorsa, Golomb-Rice kodlayıcısı için optimum parametre belirlenemez. Bu nedenle, birçok uygulamada iki geçişli bir yaklaşım kullanılır: önce, veri blokunun taraması yapılır ve veri için bir olasılık yoğunluk fonksiyonu (PDF) tahmin edilir. Bu tahmin edilmiş PDF'den Golomb-Rice parametresi belirlenir. Daha basit bir çeşidi, PDF'nin parametrelenmiş bir aileden geldiğini varsayarak, veriden PDF parametrelerini tahmin etmek ve ardından en iyi Golomb-Rice parametresini hesaplamaktır. Bu, aşağıda tartışılan uygulamalarda kullanılan yaklaşımdır.

Bilinmeyen veya değişen bir PDF'ye sahip tamsayı verileri verimli bir şekilde kodlamak için başka bir yaklaşım, geriye doğru uyarlanabilir bir kodlayıcı kullanmaktır. RLGR kodlayıcısı [1], son kodlanan sembolün M parametresini yukarı veya aşağı ayarlayarak oldukça basit bir algoritma kullanarak bu yapar. Bir kod çözücü aynı kuralı izleyerek kodlama parametrelerinin değişimini takip edebilir, bu nedenle yalnızca kodlanmış veri gönderilir, ek bilgi gerekmez. Genelleştirilmiş bir Gaus PDF'si varsayıldığında, bu PDF geniş bir veri istatistikleri kümesini kapsar, bu tür veri multimedya kodlardaki tahmin hatALARI veya dönüşüm katsayıları gibi, RLGR kodlama algoritması bu uygulamalarda oldukça iyi performans gösterir.

Uygulamalar

Golomb-Rice kodlu algoritma deneyi sıkıştırma oranları

Birçok sinyal kodeki, tahmin hatası için Rice kodunu kullanır. Tahminleme algoritmalarında, bu hatlar genellikle iki tarafa yönelik geometrik bir dağılıma uygundur, küçük hatlar daha sık göründüğünden, Rice kodu bu tür bir dağılım için Huffman kodunun yakın bir yaklaşımını sağlar, Huffman tablosunu göndermek gereğinden dolayı ek yük getirir. Bir sinyal sinüs dalgasıdır, çünkü diferansiyel hatlarının dalga biçimli bir sinyal oluşturduğu sinüs dalgası, geometrik bir dağılım oluşturmaz (en yüksek ve en düşük hat değerleri yüksek frekansla oluşur, ancak orta pozitif ve negatif hatlar daha az sıklıkla oluşur).

Birkaç verimsiz ses kodeki, tahmin hatası için Rice kodunu kullanır: Shorten, FLAC, Apple Lossless ve MPEG-4 ALS. Rice kodlama ayrıca FELICS verimsiz resim kodeklerinde kullanılır.

Golomb-Rice kodlayıcısı, tahmin hatlarını kodlamak için Rice algoritması tabanlı verimsiz resim kodeklerinde kullanılır. Bir deney, sıkıştırma oranları grafiğini verir.

JPEG-LS şeması, Rice-Golomb kodunu tahmin hatlarını kodlamak için kullanır.

Yukarıda bahsedilen uyarlanabilir Golomb-Rice kodlaması, RLGR kodlayıcısı [2], sanal makinelerde ekran içeriğini kodlamak için Microsoft Remote Desktop Protocol'ün RemoteFX bileşeninde kullanılır.

İlgili bağlantılar

• Elias delta kodlama
• Değişken uzunluklu kodlama

Daha fazla okuma

• Golomb, Solomon W. (1966). Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401
• Rice, Robert F.; Plaunt, R. (1971). "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data". IEEE Transactions on Communications. 16 (9): 889–897. doi:10.1109/TCOM.1971.1090789. 
• Robert F. Rice (1979), "Some Practical Universal Noiseless Coding Techniques", Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79–22, March 1979.
• Witten, Ian Moffat, Alistair Bell, Timothy. "Managing Gigabytes: Compressing and Indexing Documents and Images." Second Edition. Morgan Kaufmann Publishers, San Francisco CA. 1999 1-55860-570-3
• David Salomon. "Data Compression",0-387-95045-1.
• H. S. Malvar, Adaptive run-length/Golomb–Rice encoding of quantized generalized Gaussian sources with unknown statistics, Proc. Data Compression Conference, 2006.
• RLGR Entropy Encoding, Microsoft MS-RDPRFX Open Specification, RemoteFX codec for Remote Desktop Protocol.
• S. Büttcher, C. L. A. Clarke, and G. V. Cormack. Information Retrieval: Implementing and Evaluating Search Engines 2020-10-05 tarihinde Wayback Machine sitesinde arşivlendi.. MIT Press, Cambridge MA, 2010.

Şablon:Compression Methods

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

Read or create/edit this page in another language

• Golomb coding in English