ソースコーディング定理
ディスクリートメモリレスソースによって生成されたコードは、効率的に表現する必要があります。これは、通信における重要な問題です。これを実現するために、これらのソースコードを表すコードワードがあります。
たとえば、電信では、アルファベットがで示されるモールス信号を使用します Marks そして Spaces。手紙の場合E 主に使用されると見なされ、それはによって示されます “.” 手紙が Q めったに使用されない、で示されます “--.-”
ブロック図を見てみましょう。
どこ Sk ディスクリートメモリレスソースの出力であり、 bk は、で表されるソースエンコーダの出力です。 0s そして 1s。
エンコードされたシーケンスは、受信機で便利にデコードされるようなものです。
ソースにアルファベットが含まれていると仮定しましょう k 異なるシンボルとその kth シンボル Sk 確率で発生します Pk、 どこ k = 0, 1…k-1。
バイナリコードワードをシンボルに割り当てましょう Sk、長さのあるエンコーダによる lk、ビット単位で測定。
したがって、ソースエンコーダの平均コードワード長Lを次のように定義します。
$$ \ overline {L} = \ displaystyle \ sum \ limits_ {k = 0} ^ {k-1} p_kl_k $$
L ソースシンボルあたりの平均ビット数を表します
$ L_ {min} = \：最小\：可能\：値\：の\：\ overline {L} $の場合
次に coding efficiency 次のように定義できます
$$ \ eta = \ frac {L {min}} {\ overline {L}} $$
$ \ overline {L} \ geq L_ {min} $を使用すると、$ \ eta \ leq 1 $になります。
ただし、$ \ eta = 1 $の場合、ソースエンコーダは効率的であると見なされます。
このためには、値$ L_ {min} $を決定する必要があります。
定義を参照してみましょう。「離散的なメモリレスのエントロピーソース$ H（\ delta）$が与えられた場合、平均コードワード長L すべてのソースエンコーディングは、$ \ overline {L} \ geq H（\ delta）$として制限されます。」
簡単に言うと、コードワード（例：QUEUEという単語のモールス信号は-.- ..- ..-。）は、常にソースコード（例ではQUEUE）以上です。つまり、コードワードの記号は、ソースコードのアルファベット以上です。
したがって、$ L_ {min} = H（\ delta）$の場合、エントロピー$ H（\ delta）$に関するソースエンコーダの効率は次のように記述できます。
$$ \ eta = \ frac {H（\ delta）} {\ overline {L}} $$
このソースコーディング定理は、 noiseless coding theoremエラーのないエンコーディングを確立するためです。とも呼ばれますShannon’s first theorem。