可変長エンコーディング

コードは、各ソースシンボルが異なる空でないビット列にマッピングされる場合、つまりソースシンボルからビット列へのマッピングが単射である場合に非特異である。

例えば、マッピング${\displaystyle M_{1}=\{\,{\texttt {a}}\mapsto {\texttt {0}},{\texttt {b}}\mapsto {\texttt {0}},{\texttt {c}}\mapsto {\texttt {1}}\,\}}$aとbはどちらも同じビット列0にマッピングされるため、非特異ではありません。このマッピングを拡張すると、損失のある（非可逆）符号化が生成されます。このような特異な符号化は、ある程度の情報損失が許容される場合（例えば、このようなコードが音声やビデオの圧縮で使用される場合、損失のある符号化はソース量子化と同等になります）には依然として有用です。

しかし、マッピング${\displaystyle M_{2}=\{\,{\texttt {a}}\mapsto {\texttt {1}},{\texttt {b}}\mapsto {\texttt {011}},{\texttt {c}}\mapsto {\texttt {01110}},{\texttt {d}}\mapsto {\texttt {1110}},{\texttt {e}}\mapsto {\texttt {10011}},{\texttt {f}}\mapsto {\texttt {0}}\}}$非特異符号は、その拡張によって可逆符号化を生成するため、一般的なデータ伝送に役立ちます（ただし、この機能は必ずしも必要ではありません）。非特異符号は、元の符号よりもコンパクトである必要はありません（多くのアプリケーションでは、より大きな符号が役立ちます。たとえば、符号化エラーや伝送エラーを検出または回復する方法として、あるいはセキュリティアプリケーションで、検出不可能な改ざんからソースを保護する方法としてなど）。

コードの拡張が非特異である場合、そのコードは一意に復号可能である。与えられたコードが一意に復号可能かどうかは、サルディナス・パターソンアルゴリズムで判定できる。

マッピング${\displaystyle M_{3}=\{\,{\texttt {a}}\mapsto {\texttt {0}},{\texttt {b}}\mapsto {\texttt {01}},{\texttt {c}}\mapsto {\texttt {011}}\,\}}$は一意に復号可能です（これは、マップ内の各ターゲットビット列の後のフォローセットを調べることで実証できます。各ビット列は、 が見つかるとすぐに終了するためです）。${\displaystyle {\texttt {0}}}$既存のコードに続いてマップ内でより長い有効なコードを作成することはできないが、明確に新しいコードを開始するビット）。

コードをもう一度検討してください ${\displaystyle M_{2}}$前のセクションから。^{[ 2 ]}このコードは一意に復号可能ではありません。文字列011101110011は、符号語のシーケンス01110 – 1110 – 011として解釈できるだけでなく、符号語のシーケンス011 – 1 – 011 – 10011としても解釈できるからです。したがって、このエンコードされた文字列の可能な復号はcdbとbabeの 2 つです。ただし、このようなコードは、すべての可能なソース シンボルのセットが完全に既知で有限である場合、またはこの拡張のソース要素が許容されるかどうかを決定する制約 (形式構文など) がある場合に役立ちます。このような制約により、同じシンボルにマッピングされた可能なソース シンボルのうちどれがこれらの制約の下で有効かをチェックすることで、元のメッセージを復号できます。

符号がプレフィックス符号であるのは、マッピング内のどのターゲットビット列も、同じマッピング内の別のソースシンボルのターゲットビット列のプレフィックスになっていない場合である。これは、シンボルの符号語全体を受信した後、シンボルを瞬時に復号できることを意味する。この概念を表す他の一般的な名称としては、プレフィックスフリー符号、瞬時符号、またはコンテキストフリー符号などがある。プレフィックス符号の特殊なケースとして、ブロック符号、LEB128、および可変長数量（VLQ）符号がある。

例えば、マッピング${\displaystyle M_{3}}$上記はプレフィックスコードではありません。なぜなら、ビット列0を読み取った後では、それがソースシンボルaをエンコードしているのか、それともbまたはcシンボルのエンコードのプレフィックスなのかが分からないからです。プレフィックスコードの例を以下に示します。

エンコードとデコードの例：

aabacdab → 00100110111010 → | 0 | 0 | 10 | 0 | 110 | 111 | 0 | 10 | →アーバクダブ

この例では、確率が${\displaystyle ({\texttt {a}},{\texttt {b}},{\texttt {c}},{\texttt {d}})}$だった${\displaystyle \textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)}$上記のコードを使用してソースシンボルを表すために使用されるビット数は、次のようになります。

$1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}}$。

この情報源のエントロピーはシンボルあたり1.75ビットであるため、このコードは情報源を可能な限り圧縮し、エラーゼロで復元できるようにします。