跳至內容

指數哥倫布碼

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

指數哥倫布碼Exponential-Golomb coding)是一種無失真數據壓縮方法。

用來表示非負整數的k階指數哥倫布碼可用如下步驟生成:

  1. 將數字以二進制形式寫出(B),去掉最低的k個位元(D),之後加1 (A = B + 1)
  2. 計算A的位元個數(C),將此數減一,即是需要增加的前導零個數(Z = C -1)
  3. 將第一步中去掉的最低k個位元位補回位元串尾部 (ExpG = Z個0 + A + D)

0階指數哥倫布碼如下所示:

      Step 1                         Step 2           Step 3 
 0 => B = 0   ,D = None, A = 1    => C = 1 , Z = 0 => 1
 1 => B = 1   ,D = None, A = 10   => C = 2 , Z = 1 => 010
 2 => B = 10  ,D = None ,A = 11   => C = 2 , Z = 1 => 011
 3 => B = 11  ,D = None ,A = 100  => C = 3 , Z = 2 => 00100
 4 => B = 100 ,D = None ,A = 101  => C = 3 , Z = 2 => 00101
 5 => B = 101 ,D = None ,A = 110  => C = 3 , Z = 2 => 00110
 6 => B = 110 ,D = None ,A = 111  => C = 3 , Z = 2 => 00111
 7 => B = 111 ,D = None ,A = 1000 => C = 4 , Z = 3 => 0001000
 8 => B = 1000,D = None ,A = 1001 => C = 4 , Z = 3 => 0001001

以數字9為例, (1)2進制值B 為1001,因為K為0階,去除0個位元,故D值為空,把B值加1 得到 A,值為 1010, (2)計算A的位元個數,得到C值為4,故減1後得到前導零Z ,值為3 (3)最後組合 Z + A + D之後,得到 000+1010 + 空 ,故Exp-G值為 0001010


1階指數哥倫布碼如下所示:

      Step 1                      Step 2           Step 3
 0 => B = 0   ,D = 0 , A = 1   => C = 1 , Z = 0 => 10
 1 => B = 1   ,D = 1 , A = 1   => C = 1 , Z = 0 => 11
 2 => B = 10  ,D = 0 , A = 10  => C = 2 , Z = 1 => 0100
 3 => B = 11  ,D = 1 , A = 10  => C = 2 , Z = 1 => 0101
 4 => B = 100 ,D = 0 , A = 11  => C = 2 , Z = 1 => 0110
 5 => B = 101 ,D = 1 , A = 11  => C = 2 , Z = 1 => 0111
 6 => B = 110 ,D = 0 , A = 100 => C = 3 , Z = 2 => 001000
 7 => B = 111 ,D = 1 , A = 100 => C = 3 , Z = 2 => 001001
 8 => B = 1000,D = 0 , A = 101 => C = 3 , Z = 2 => 001010