本條目存在以下問題 ，請協助
改善本條目 或在
討論頁 針對議題發表看法。
此條目
缺少有關 应用 的信息。
(2022年12月27日 ) 請擴充此條目 相關信息。討論頁 可能有詳細細節。
格倫布編碼 （英語：Golomb coding ）是一種無失真資料壓縮方法，由數學家所羅門·格倫布 在1960年代提出。其優點為易於編碼與解碼，另外對於擁有機率分布為幾何分佈
G
(
p
)
,
p
=
0.5
,
{\displaystyle G(p),p=0.5,}
前綴碼 ，且能無限逼近該資料的熵 ，目前廣泛用於無損影像壓縮 。
令輸入值為正整數
n
{\displaystyle n}
M
{\displaystyle M}
c
{\displaystyle c}
c
{\displaystyle c}
c
=
(
u
,
b
)
{\displaystyle c=(u,b)}
u
{\displaystyle u}
一进制 編碼，
b
{\displaystyle b}
截斷二進制編碼 。
計算
u
{\displaystyle u}
b
{\displaystyle b}
q
=
⌊
n
m
⌋
,
{\displaystyle q=\left\lfloor {\frac {n}{m}}\right\rfloor ,}
r
=
n
−
q
{\displaystyle r=n-q}
將
q
{\displaystyle q}
一进制 編碼，
r
{\displaystyle r}
截斷二進制編碼 即可得到
(
u
,
b
)
{\displaystyle (u,b)}
格倫布-萊斯編碼中的商數
q
{\displaystyle q}
r
{\displaystyle r}
N
{\displaystyle N}
q
{\displaystyle q}
r
{\displaystyle r}
M
{\displaystyle M}
M
{\displaystyle M}
M
{\displaystyle M}
2
{\displaystyle 2}
r
{\displaystyle r}
參數
M
{\displaystyle M}
伯努利過程 的函數，其中伯努利過程 的參數
p
{\displaystyle p}
p
=
P
(
X
=
0
)
{\displaystyle p=P(X=0)}
M
{\displaystyle M}
伯努利過程 的中位數 -1到中位數+1之間。如下式：
(
1
−
p
)
M
+
(
1
−
p
)
M
+
1
≤
1
<
(
1
−
p
)
M
−
1
+
(
1
−
p
)
M
.
{\displaystyle (1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M}.}
當
M
{\displaystyle M}
M
=
⌊
−
1
log
2
(
1
−
p
)
⌋
{\displaystyle M=\left\lfloor {\frac {-1}{\log _{2}(1-p)}}\right\rfloor }
格倫布編碼主要是針對非負整數進行編碼，但也可以使用重疊(Overlap)與交錯(Interleave)擴展至對所有整數進行編碼。令一串用於編號的數列，(0,1,2,...)，給予非負整數偶數編號，給予負整數奇數編號，使得排列方式如下，(0,-1,1,-2,2,...)，即非負整數
x
{\displaystyle x}
映射 至
{
x
′
|
x
′
=
2
|
x
|
,
x
≥
0
}
{\displaystyle \{x^{\prime }|x^{\prime }=2|x|,x\geq 0\}}
y
{\displaystyle y}
映射 至
{
y
′
|
y
′
=
2
|
y
|
−
1
,
y
<
0
}
{\displaystyle \{y^{\prime }|y^{\prime }=2|y|-1,y<0\}}
萊斯編碼（Rice coding，由Robert F. Rice所提出），為一種前綴碼 ，歸屬於格倫布編碼的子集合，參數
M
{\displaystyle M}
2
{\displaystyle 2}
M
=
2
R
,
R
∈
N
{\displaystyle M=2^{R},R\in N}
格倫布編碼為一種范氏霍夫曼編碼 。
選擇參數
M
{\displaystyle M}
待編碼數值為
n
{\displaystyle n}
商數：
q
=
⌊
n
m
⌋
,
{\displaystyle q=\left\lfloor {\frac {n}{m}}\right\rfloor ,}
餘數：
r
=
n
−
q
{\displaystyle r=n-q}
編碼
商數編碼，對
q
{\displaystyle q}
u
{\displaystyle u}
餘數編碼，對
r
{\displaystyle r}
截斷二進制編碼 ，得到
b
{\displaystyle b}
合併，
c
=
(
u
,
b
)
{\displaystyle c=(u,b)}
輸出
c
=
(
u
,
b
)
{\displaystyle c=(u,b)}
設 M = 10。則
b
=
⌈
log
2
(
10
)
⌉
=
4
{\displaystyle b=\lceil \log _{2}(10)\rceil =4}
2
b
−
M
=
16
−
10
=
6
{\displaystyle 2^{b}-M=16-10=6}
商數編碼
q 輸出位元
0
0
1
10
2
110
3
1110
4
11110
5
111110
6
1111110
⋮
{\displaystyle \vdots }
⋮
{\displaystyle \vdots }
N
111
⋯
111
⏟
N
0
{\displaystyle \underbrace {111\cdots 111} _{N}0}
餘數編碼
r 偏移
二進位
輸出位元
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
選擇42作為編碼時，42會被拆成
q
=
4
{\displaystyle q=4}
r
=
2
{\displaystyle r=2}
Golomb, S.W. (1966). , Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401 （页面存档备份 ，存于互联网档案馆 ）
R. F. Rice (1971) and R. Plaunt, , "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. Information Retrieval: Implementing and Evaluating Search Engines （页面存档备份 ，存于互联网档案馆 ）. MIT Press, Cambridge MA, 2010.
https://en.wikipedia.org/wiki/Golomb_coding （页面存档备份 ，存于互联网档案馆 ）
