数え上げ符号

数え上げ符号（かぞえあげふごう）は、符号化方式の1つ。次の手順で符号化を行う。

• 符号化の対象（情報系列）の1情報ブロック中にある "1" の個数（ハミング重み）を数える。
• "1" の個数と情報ブロックの長さを定めると 0と 1 の組み合わせも限られるので、0 と 1 の組み合わせを列挙し、情報ブロックが何番目の組み合わせと一致するかを数える。
• "1" の個数を2進数表現したものと、何番目のバイナリ系列と一致したかを数え、2進数表現したものを組み合わせて符号語とする。

下記の例のように符号化後の方がより多くのビットを使用する場合もある。この例では圧縮としての符号化を目的としたものではない。この符号化方式をナップサック暗号に組み合せると、よく知られた攻撃法を回避できるという提案もある。

例

符号化対象を 0101100︵7ビット︶とする。符号化対象に "1" は最大7個ある可能性があるため、符号化後の長さを一定にするためには$7<2^{3}=8$ となり3ビット必要。35通りを2進数で表現するには$35<2^{6}=64$ となり、6ビット必要となる。符号化後の長さを一定にするためには、このように 3+6=9 ビット必要となる︵圧縮を目的とするなら、最小表現方式を使用するのも良い︶。

STEP1‥符号化対象のバイナリ系列 "0101100" の中の "1" の個数を数える。

"1" の個数‥3

STEP2‥"1" が3つある長さ7の符号の全ての組み合わせは、7C3 = 35 通りある。

"0000111","0001110","0011100","0111000","1110000",

"0001011","0010110","0101100","1011000","0001101",

"0011010","0110100","1101000","0010011","0100110",

"1001100","0010101","0101010","1010100","0011001",

"0110010","1100100","0100011","1000110","0100101",

"1001010","0101001","1010010","0110001","1100010",

"1000011","1000101","1001001","1010001","1100001"

符号化対象の "0101100" は35通りの中の8番目にあたる。

STEP3‥上で得た情報をバイナリ表現をして連結する。

3を2進数表現したもの "011"

8番目の符号である事を示す 8 を2進数表現したもの "001000"

上の二つを連結した "011001000" を数え上げ符号とする。

関連項目

• 符号化方式
• データ圧縮