格倫布編碼

格倫布編碼（）是一種無失真資料壓縮方法，由數學家所羅門·格倫布在1960年代提出。其優點為易於編碼與解碼，另外對於擁有機率分布為幾何分佈G(p),p=0.5,的資料，格倫布編碼是最佳的前綴碼，且能無限逼近該資料的熵，目前廣泛用於無損影像壓縮。

編碼的建立
令輸入值為正整數n，參數值為正整數 M，輸出值格倫布碼為 c，其中 c 由兩種編碼組合而成，

c=(u,b)，u：一进制編碼，b：截斷二進制編碼。

計算 u 與 b。

q= \left\lfloor \frac nm \right\rfloor , r=n-q。

將 q 做一进制編碼，r 做截斷二進制編碼即可得到(u,b)。

格倫布-萊斯編碼中的商數q指示了所在區塊，而 r指示所在區塊內部的位置。如上圖，對整數 N 做格倫布-萊斯編碼，q 代表區塊、 r 表示區塊內部位置、M 為參數，每個區塊的大小皆相等且長度為 M，特別注意當編碼方式為格倫布-萊斯編碼時，即 M 為 2 的整數次方，所有 r的編碼長度相等。

參數 M 是伯努利過程的函數，其中伯努利過程的參數 p 定義為 p=P(X=0)，則 M 的所在區間為此伯努利過程的中位數-1到中位數+1之間。如下式：

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

當 M 足夠大時，我們可以將其表示成，M = \left\lfloor \frac{-1}{\log_2(1-p)}\right\rfloor。

使用符號整數
格倫布編碼主要是針對非負整數進行編碼，但也可以使用重疊(Overlap)與交錯(Interleave)擴展至對所有整數進行編碼。令一串用於編號的數列，(0,1,2,...)，給予非負整數偶數編號，給予負整數奇數編號，使得排列方式如下，(0,-1,1,-2,2,...)，即非負整數 x 映射至 \{x^\prime|x^\prime=2|x|, x\ge0\}，負整數 y 映射至 \{y^\prime |y^\prime=2|y|-1, y。

萊斯編碼
萊斯編碼（Rice coding，由Robert F. Rice所提出），為一種前綴碼，歸屬於格倫布編碼的子集合，參數 M 為 2 的整數次方，即 M=2^R,R\in N。此種特例未必是所有格倫布編碼中的最佳編碼方式，但由於目前電腦為二進位運算，萊斯編碼能快速且有效地以二進位運算實現。

性質
范氏霍夫曼編碼
格倫布編碼為一種范氏霍夫曼編碼。

演算法
#選擇參數 M
#待編碼數值為 n，計算：
##商數： q=\left\lfloor \frac nm \right\rfloor ,
##餘數： r=n-q。
#編碼
##商數編碼，對 q 進行一进制編碼，得到 u。
##餘數編碼，對 r 進行截斷二進制編碼，得到 b。
##合併，c=(u,b)。
#輸出 c=(u,b)

範例
設 M = 10。則 b = \lceil\log_2(10)\rceil = 4. 2^b-M = 16-10 = 6

|

|}

選擇42作為編碼時，42會被拆成 q=4 及 r=2，編碼為11110010，而商數編碼尾數必為0，能標示商數編碼位元的結束。

參考來源

• Golomb, S.W. (1966). [http://urchin.earth.li/~twic/Golombs_Original_Paper/ , Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401 ]
• R. F. Rice (1971) and R. Plaunt, [http://dx.doi.org/10.1109/TCOM.1971.1090789 , "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data, " IEEE Transactions on Communications, vol. 16(9), pp. 889–897, Dec. 1971.]
• R. F. Rice (1979), "Some Practical Universal Noiseless Coding Techniques, " Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79—22, Mar. 1979.
• Witten, Ian Moffat, Alistair Bell, Timothy. "Managing Gigabytes: Compressing and Indexing Documents and Images." Second Edition. Morgan Kaufmann Publishers, San Francisco CA. 1999 ISBN 1-55860-570-3
• David Salomon. "Data Compression",ISBN 0-387-95045-1.
• S. Büttcher, C. L. A. Clarke, and G. V. Cormack. [http://www.ir.uwaterloo.ca/book/ Information Retrieval: Implementing and Evaluating Search Engines] . MIT Press, Cambridge MA, 2010.