オメガ符号 (Elias omega coding) は、マサチューセッツ工科大学のによって開発された、整数の符号化を行うための符号である。 語頭を再帰的に符号化するため、再帰的イライアス符号とも呼ばれている。
符号化の手順
1以上の整数値に対して 末尾に '0' を付記する もし符号化しようとする数値が 1 であるならば、終了する。そうでなければ、数値のバイナリ表現を手前につける。 今出力した数値の桁数マイナス 1 を、新しく符号化すべき数値として、2. の処理を繰り返す。
数値が 18 のときの例を示す。 まず末尾に 0 が書かれる。 0 続いて、18 をバイナリ表現した 10010 をその前に書き加える（空白は便宜上のもの。以下同様）。 10010 0 この 10010 の桁数が 5 桁なので、5-1=4 として、再帰処理する。4 のバイナリ表現 100 を前に書き加える。 100 10010 0 この 100 の桁数が 3 桁なので、 3-1=2 として、再帰処理する。2 のバイナリ表現 10 を前に書き加える。 10 100 10010 0 この 10 の桁数が 2 桁なので、 2-1=1 として、再帰処理する。そして、1 の場合は終了なので、結果として、 10 100 10010 0 が 18 をオメガ符号で符号化したときの符号語となる。
1 から 17 までの符号語を示す。 1 0 2 10 0 3 11 0 4 10 100 0 5 10 101 0 6 10 110 0 7 10 111 0 8 11 1000 0 9 11 1001 0 10 11 1010 0 11 11 1011 0 12 11 1100 0 13 11 1101 0 14 11 1110 0 15 11 1111 0 16 10 100 10000 0 17 10 100 10001 0
復号の手順
変数 N を 1 にセットする。 符号語の最初を読み込む。 0 ならば、整数の 1 を表している。 1 ならば、それに続く N 桁と合わせてバイナリ符号となっているため、N をその値にセットする。 以降はこのステップを繰り返す。符号語の残りの先頭を読み込む。0 ならば、符号化された数値が N となることを表している。1 ならば、続く N 桁と合わせてバイナリ符号となっているため、 N をその値にセットする。
符号語 101100 を復号する例を示す。 まず N=1 として、先頭 1 記号を読み込む。値が 1 なので、続く N=1 記号を読み込んだ 10 をバイナリ符号とみなした 2 を、新たな N の値とする。すると、符号語の残りは、 1100 となる。先頭 1 記号を読み込む。値が 1 なので、続く N=2 記号を読み込んだ 110 をバイナリ符号とみなした 6 を、新たな N の値とする。すると、符号語の残りは、 0 となる。先頭 1 記号を読み込む。値が 0 なので、N=6 が求める整数値である。
符号長
オメガ符号の長さを小さい自然数から順に列記すると以下の通りになる。
1, 3, 3, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, … （）
関連項目
データ圧縮 イライアス符号