オメガ符号

オメガ符号（Elias omega coding）は、マサチューセッツ工科大学のピーター・イライアスによって考案された、整数値を効率的に符号化するための可変長符号の一つです。この符号は、特に小さい整数を短い符号で表現できるという特徴を持ち、データ圧縮の分野で重要な役割を果たします。オメガ符号は、その符号化プロセスが再帰的であることから、「再帰的イライアス符号」とも呼ばれます。

符号化の手順

オメガ符号による符号化は、以下の手順で行われます。

1. 末尾に '0' を付加: まず、符号化したい整数のバイナリ表現の末尾に '0' を追加します。
2. 数値が1の場合の終了: もし、符号化対象の整数値が1であれば、ここで符号化は終了します。それ以外の場合は、次のステップに進みます。
3. バイナリ表現の追加: 符号化対象の数値のバイナリ表現を、先ほど付加した '0' の前に加えます。
4. 再帰的処理: 先の手順で追加したバイナリ表現の桁数から1を引いた値を、新たな符号化対象の数値として、ステップ2からの処理を繰り返します。

例：数値18の符号化

数値18をオメガ符号で符号化する具体的な例を見てみましょう。

1. まず、末尾に '0' が付加されます。結果は「`0`」となります。
2. 18のバイナリ表現 `10010` が、`0` の前に追加されます。結果は「`10010 0`」となります。
3. `10010` は5桁なので、5-1=4 を符号化対象として再帰処理を行います。4のバイナリ表現`100` を追加します。結果は「`100 10010 0`」となります。
4. `100` は3桁なので、3-1=2 を符号化対象として再帰処理を行います。2のバイナリ表現 `10` を追加します。結果は「`10 100 10010 0`」となります。
5. `10`は2桁なので、2-1=1を符号化対象として再帰処理を行います。1の場合は終了なので、最終的な符号語は「`10 100 10010 0`」となります。


1から17までの符号語

以下に、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. 符号語の読み込み: 符号語の先頭からビットを読み込みます。
3. 終了判定: 読み込んだビットが「0」の場合、復号された整数値はNであり、復号を終了します。
4. Nの更新: 読み込んだビットが「1」の場合、続くNビットをバイナリ表現とみなし、その値を新たなNの値とします。ステップ2に戻り、符号語の残りを読み込みます。

例：符号語 `101100` の復号

符号語 `101100` を復号する例を見てみましょう。

1. 初期値N=1とします。
2. 符号語の先頭「1」を読みます。続くN=1桁を読み取り、`10` をバイナリ表現とみなし、10進数の2を新たなNとします。符号語の残りは `1100`となります。
3. 符号語の先頭「1」を読みます。続くN=2桁を読み取り、`110` をバイナリ表現とみなし、10進数の6を新たなNとします。符号語の残りは `0`となります。
4. 符号語の先頭「0」を読みます。N=6であるため、復号結果は6となります。


オメガ符号は、そのシンプルさと効率性から、データ圧縮アルゴリズムや情報理論において重要な役割を果たしています。

関連項目

データ圧縮
* イライアス符号

もう一度検索