オメガ符号

オメガ符号 (Elias omega coding) は、マサチューセッツ工科大学のピーター・イライアス（英語版）によって開発された、整数の符号化を行うための符号である。 語頭を再帰的に符号化するため、再帰的イライアス符号とも呼ばれている。

符号化の手順

[編集]

1以上の整数値に対して

  1. 末尾に '0' を付記する
  2. もし符号化しようとする数値が 1 であるならば、終了する。そうでなければ、数値のバイナリ表現を手前につける。
  3. 今出力した数値の桁数マイナス 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


復号の手順

[編集]
  1. 変数 N を 1 にセットする。
  2. 符号語の最初を読み込む。 0 ならば、整数の 1 を表している。 1 ならば、それに続く N 桁と合わせてバイナリ符号となっているため、N をその値にセットする。
  3. 以降はこのステップを繰り返す。符号語の残りの先頭を読み込む。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 が求める整数値である。


関連項目

[編集]