数え上げ符号

数え上げ符号（かぞえあげふごう）は、符号化方式の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 ビット必要となる（圧縮を目的とするなら、最小表現方式を使用するのも良い）。