Golomb codes（ゴロム符号）

理屈

小さい整数ほど頻繁に現れるときの簡略符号化。 予測誤差の符号化に便利。

• S. W. Golomb, Run-length encodings, IEEE Transactions on Information Theory IT-12(3), 399--401.
• Robert F. Rice, Some Practical Universal Noiseless Coding Techniques, JPL Publication 79-22, 1979.

実装の例

LOCO-I/JPEG-LS 風

    int n = 1; // 個数のカウンタ
    int a = 0; // 予測誤差の絶対値の和

    while (予測誤差 e を読む) {
        for (k = 0; (n << k) < a; k++);
        m = (e >= 0) ? 2*e : -2*e-1;
        (m >> k) ビットの 0 を出力;
        1 ビットの 1 を出力;
        m の最後の k ビットを出力;
        a += abs(e);
        if (++n >= 64) {
            a /= 2;  n /= 2;
        }
    }

例（k=0）

例（k=1）

余談

Solomon W. Golomb はペントミノの考案者でもある。

Optimal Golomb Rulers（最適ゴロム定規／最短ゴロム定規）

• Table of known optimal Golomb rulers

奥村晴彦

Last modified: 2004-12-17 22:58:21