導入
エントロピー符号化(または可変長統計符号化) は、可逆ソース符号化方式であり、その目的は、圧縮および/または通信チャネルでの送信のためにデータ ソースの表現を変換することです。エントロピー符号化の主な種類は、ハフマン符号化と算術符号化です。
エントロピーコーディングはソース統計を使用してコードを構築します。つまり、ソースの一部をコードワードに関連付けるアプリケーションです。コードワードの長さはソースの統計的特性によって異なります。したがって、一般的には、最も頻繁に使用されるソース シンボルに最も短いコード ワードを割り当てる可変長コードを使用します。エントロピー コーディングは情報理論に由来し、これらのコードとその特性を扱います。エンコードされる情報は、有限サイズのアルファベットの値を持つ確率変数によって表されます。重要な結果は、圧縮の可能性に対する限界を確立し、この限界をエントロピーとして確立するソースコーディング定理です。
歴史的に 1940 年代から 1950 年代に情報理論とともに開発されたエントロピー コーディングは、データ圧縮の基本的な技術となっており、多くの圧縮プログラム、画像圧縮、およびビデオ圧縮標準に組み込まれています。
定義
離散ソース、つまり有限離散セットからシンボルのシーケンスをランダムに提供するデバイスを考えます。ソースには、テキスト、画像、またはより一般的には任意のデジタル信号を使用できます。ソースは、有限サイズのアルファベットの値を持つ一連の確率変数によってモデル化されます。
定義—ソースによって生成されたシンボルのシーケンスが一連の独立した同一分布変数である場合、ソースはメモリレスであると言われます。
定義—確率変数のソースコードC
D 進アルファベットAの記号列のセットはA + と表されます。一般に、このアルファベットは 2 進数であり、 D = 2 、 A = {0,1}となります。 +は0 と 1 で構成される有限サイズの文字列のセットになります。
コードCの予想される長さ (または X の確率法則に従った平均長) は、次の式で与えられます。
- $$ {L(C)=\sum_{x \in \Omega}p(x) \cdot l(x)} $$。
L ( C ) は、符号化率、つまりソース シンボルごとに符号化される平均ビット数とみなすこともできます。
定義— CコードのC +拡張は、 A +のΩ +を適用したもので、ソース シンボルのシーケンスをそのコードワードの連結に関連付けます。
- $$ {C^+(x_0 x_1 \ldots x_N)=C(x_0)C(x_1) \ldots C(x_N)} $$。
この定義は、非効率となる分離シンボルで区切られた孤立したシンボルではなく、シンボルのシーケンスを送信するという事実によって動機づけられています。
クラフト不等式
クラフトの不等式は、コードにプレフィックスを付けるコードワードの長さに関する必要十分条件を与えます。サイズDのアルファベットで定義されたコード、およびサイズ|のソース アルファベットΩの場合Ω |の場合、次の場合にのみ接頭辞が付けられます。
