導入
デルタコーディングまたはエリアスデルタコーディングは、ピーター・エリアスによって発明され、主にデータ圧縮に使用されるエントロピーコーディングです。
製品デルタ コードはプレフィックスおよびユニバーサルコードです。
原理
ガンマコーディングと同様に、デルタコーディングでは、コーディングする値の間隔を最初に知る必要がなく、ゼロを除くすべての自然整数をコーディングすることができます（たとえば、固定サイズのバイナリコーディングとは異なります）。あらかじめ決められた上限値以下の数値も暗号化可能）。
これを行うには、デルタ コーディングを 2 つの手順で実行します。
- 整数を表すのに必要なビット数をガンマコーディングでエンコードする。
- これと同じ数の必要なビットをバイナリコーディングして整数を実際にコーディングします。
したがって、このアプローチはガンマ コーディングのアプローチと似ていますが、最初のステップの単項コーディングがガンマ コーディングに置き換えられる点が異なります。
実際には、整数の最上位ビットは暗黙的であるためエンコードされませんが、ガンマ コーディング中に行われるのとは異なり、最初のステップでそのビット数がエンコードされます (ガンマ値のため 1 を減算する必要はありません)。コーディングでは、厳密に正の自然整数のみをコーディングできます)。
数学的には、整数をエンコードするには
コード長
厳密に正の自然数Nに関連付けられたガンマ コードの長さL は、次のように表すことができます。
この長さは、 N を使用するとガンマ コーディング中ほど急速に増加しません。後者とは異なり、デルタコーディングでは、漸近的に最適な長さのコードを取得することができます。
相対整数のコーディング
ガンマ コーディングと同様に、全単射を使用してデルタ コーディングで相対整数をエンコードし、実際のコーディングの前に負またはゼロの数値を厳密に正の数値に変換することができます。デコード後、元の相対整数を見つけるために逆の演算を実行する必要があります。
例
| 10進数 N | バイナリ N | ビット数 $$ {G = \lceil \log_2 N \rceil} $$ | ビット数 (ガンマコーディングのG ) | 最上位ビットを除いたバイナリ B = N − 2 G | デルタコード ガンマのGに続いてB | 同等のガンマコード |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 | |
| 2 | 10 | 2 | 100 | 0 | 100 0 | 10 0 |
| 3 | 11 | 2 | 100 | 1 | 100 1 | 10 1 |
| 4 | 100 | 3 | 101 | 00 | 101 00 | 110 00 |
| 5 | 101 | 3 | 101 | 01 | 101 01 | 110 01 |
