ソースコーディング定理

個別のメモリレスソースによって生成されたコードは、効率的に表現する必要があり、これは通信の重要な問題です。これを実現するために、これらのソースコードを表すコードワードがあります。

たとえば、電信では、モールス符号を使用します。この場合、アルファベットは Marks および Spaces で示されます。ほとんど使用される文字 E が考慮される場合、それは*“。” で示されますが、まれに使用される文字 *Q は*“ --.-” *で示されます。

ブロック図を見てみましょう。

ここで、* S〜k〜はディスクリートメモリレスソースの出力であり、 b〜k〜は *0s および 1s で表されるソースエンコーダーの出力です。

エンコードされたシーケンスは、受信側で便利にデコードされるようなものです。

ソースに k 個の異なるシンボルを持つアルファベットがあり、 k ^ th ^ シンボル* S〜k〜が P〜k〜の確率で発生すると仮定します。ここで、 *k = 0、1… k-1 。

ビットで測定された長さ* l〜k〜を持つエンコーダーによって、シンボル S〜k〜*に割り当てられたバイナリコードワードをみましょう。

したがって、ソースエンコーダーの平均コードワード長Lを次のように定義します。

\ overline \ {L} = \ displaystyle \ sum \ limits _ \ {k = 0} ^ \ {k-1} p_kl_k

*L* は、ソースシンボルごとの平均ビット数を表します

$ L _ \ {min} = \：最小\：可能\：値\：\：\ overline \ {L} $の場合

次に、*コーディング効率*は次のように定義できます。

\ 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}}

このソースコーディング定理は、エラーのないエンコーディングを確立するため、*ノイズレスコーディング定理*と呼ばれます。また、*シャノンの最初の定理*とも呼ばれます。

Digital-communication-source-coding-theorem