Quellcodierungssatz

Der von einer diskreten speicherlosen Quelle erzeugte Code muss effizient dargestellt werden, was ein wichtiges Problem bei der Kommunikation darstellt. Dazu gibt es Codewörter, die diese Quellcodes darstellen.

In der Telegraphie verwenden wir beispielsweise Morsecode, in dem die Alphabete mit gekennzeichnet sind Marks und Spaces. Wenn der BriefE wird berücksichtigt, was meistens verwendet wird, es wird mit bezeichnet “.” Während der Brief Q was selten verwendet wird, wird mit bezeichnet “--.-”

Schauen wir uns das Blockdiagramm an.

Wo Sk ist der Ausgang der diskreten speicherlosen Quelle und bk ist der Ausgang des Quellcodierers, der durch dargestellt wird 0s und 1s.

Die codierte Sequenz ist so, dass sie bequem am Empfänger decodiert wird.

Nehmen wir an, dass die Quelle ein Alphabet mit hat k verschiedene Symbole und dass die kth Symbol Sk tritt mit der Wahrscheinlichkeit auf Pk, wo k = 0, 1…k-1.

Lassen Sie das dem Symbol zugewiesene Binärcodewort Skdurch den Encoder mit Länge lk, gemessen in Bits.

Daher definieren wir die durchschnittliche Codewortlänge L des Quellcodierers als

$$ \ overline {L} = \ displaystyle \ sum \ limit_ {k = 0} ^ {k-1} p_kl_k $$

L repräsentiert die durchschnittliche Anzahl von Bits pro Quellensymbol

Wenn $ L_ {min} = \: Minimum \: möglich \: Wert \: von \: \ overline {L} $

Dann coding efficiency kann definiert werden als

$$ \ eta = \ frac {L {min}} {\ overline {L}} $$

Mit $ \ overline {L} \ geq L_ {min} $ haben wir $ \ eta \ leq 1 $

Der Quellcodierer wird jedoch als effizient angesehen, wenn $ \ eta = 1 $ ist

Dazu muss der Wert $ L_ {min} $ ermittelt werden.

Wir beziehen uns auf die Definition: „Bei einer diskreten speicherlosen Entropiequelle $ H (\ delta) $ ist die durchschnittliche CodewortlängeL für jede Quellcodierung ist $ \ overline {L} \ geq H (\ delta) $ begrenzt. "

In einfacheren Worten ist das Codewort (Beispiel: Morsecode für das Wort QUEUE ist -.- ..- .. ..) immer größer oder gleich dem Quellcode (QUEUE im Beispiel). Das heißt, die Symbole im Codewort sind größer oder gleich den Alphabeten im Quellcode.

Daher kann mit $ L_ {min} = H (\ delta) $ die Effizienz des Quellcodierers in Bezug auf die Entropie $ H (\ delta) $ wie folgt geschrieben werden

$$ \ eta = \ frac {H (\ delta)} {\ overline {L}} $$

Dieser Quellcodierungssatz wird als bezeichnet noiseless coding theoremwie es eine fehlerfreie Codierung herstellt. Es wird auch als bezeichnetShannon’s first theorem.