PROFILPELAJAR.COM

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

編碼的建立

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

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

計算 $u$ 與 $b$ 。

$q=\left\lfloor {\frac {n}{m}}\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<(1-p)^{M-1}+(1-p)^{M}.$

當 $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\geq 0\}$ ，負整數 $y$ 映射至 $\{y^{\prime }|y^{\prime }=2|y|-1,y<0\}$ 。

萊斯編碼

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

性質

范氏霍夫曼編碼

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

演算法

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