格倫布編碼

维基百科,自由的百科全书
跳转至: 导航搜索

格倫布編碼是一種無失真資料壓縮方法,由數學家所羅門·格倫布在1960年代提出。

Rice編碼

Robert F. Rice提出Rice 編碼,是以哥倫布編碼為基礎做改良而更簡易的前置碼。Rice編碼可視為適應性編碼的一種或是哥倫布編碼的特例之一。哥倫布編碼有一個可調整參數,可以是任一正整數。而Rice編碼則是此調整參數為2的次方情況時。這讓Rice編碼在電腦運算上快速許多,因為電腦上是已二進位運算為主。 Rice編碼是一種熵編碼技術,可用在影像及圖像壓縮上。


編碼的建立[编辑]

哥倫布編碼使用可調整參數把輸入值分乘兩部分: , 除以的結果及餘數。 商數當做一元編碼而餘數放在後面做為可縮短的二進位編碼。當哥倫布編碼等同於一元編碼。

Golomb rice code.svg

哥倫布-Ric編碼可想成用bin(q) 指示位置而bin (r)代表偏移。上述圖片顯現使用哥倫布-Ric對整數 N編碼,另有位置q、偏移r、參數M。 而這兩部分如下式表達,是要被編碼的數字。


and 最後偏碼結果:

是變化的位元數,在Rice編碼則只有b位元數,而在哥倫布編碼, 會是b-1或b bits. 假設 . 如果 ,則用b-1 位元數編碼r. 相反的,如果 ,用b位元數編碼r'. 當M 是2的次方時,,則所有的r值都是b個位元.

參數M是伯努利試驗函數,其中. M則是中位數或中位數+/-1,如下式:

M愈大愈難抓取.

哥倫布編碼在分布上跟霍夫曼編碼有相同機率。


使用記號整數[编辑]

哥倫布原本是用來編碼非負整數,但也可改良用來編碼任意整數,利用重新排列數值使正整數排在特定的位置。例如一串數字0, -1, 1, -2, 2, -3, 3, -4, 4 ... ,-n排在nth奇數(2n-1),而mth正數排在mth偶數(2m)。 正數對應(),負數對應()。


演算法[编辑]

  1. 選擇整數作為M
  2. 要編碼數值N,找出下列式子
    1. 商數: q = int[N/M]
    2. 餘數: r = N除以M
  1. 產生整體編碼
    1. 編碼形式 : < 商數編碼 > < 餘數編碼 >
    2. 商數編碼
      1. q長度位元的1
      2. 在寫一個0位元
    3. 餘數編碼
      1. 如果M'是2的次方,編碼是二進位形式,需要。(Rice 編碼)
      1. 如果M'不是2的次方,令b = \lceil\log_2(M)\rceil</math>
        1. If 使用b-1 個位元編碼 r.
        2. If 使用b個位元 編碼

範例[编辑]

M = 10. 則 .

商數編碼
q 輸出位元
0 0
1 10
2 110
3 1110
4 11110
5 111110
6 1111110
N
餘數編碼
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及r=2,從上表中為q(4),r(2),編碼為11110,010,實際上不需要逗號去分隔兩部分,因為商數編碼最後的0能代表 餘數編碼的起始位置。

參考來源[编辑]