Teorema del codice sorgente

Il codice prodotto da una sorgente senza memoria discreta deve essere rappresentato in modo efficiente, il che è un problema importante nelle comunicazioni. Perché ciò avvenga, ci sono parole in codice, che rappresentano questi codici sorgente.

Ad esempio, in telegrafia, usiamo il codice Morse, in cui gli alfabeti sono indicati con Marks e Spaces. Se la letteraE è considerato, che viene utilizzato principalmente, è indicato da “.” Mentre la lettera Q che è usato raramente, è indicato da “--.-”

Diamo uno sguardo al diagramma a blocchi.

Dove S_k è l'output della sorgente senza memoria discreta e b_k è l'uscita del codificatore sorgente che è rappresentato da 0s e 1s.

La sequenza codificata è tale da essere opportunamente decodificata sul ricevitore.

Supponiamo che la fonte abbia un alfabeto con k simboli diversi e che il file k^th simbolo S_k si verifica con la probabilità P_k, dove k = 0, 1…k-1.

Lascia che la parola in codice binario sia assegnata al simbolo S_k, dal codificatore avente lunghezza l_k, misurato in bit.

Quindi, definiamo la lunghezza media della parola in codice L del codificatore sorgente come

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

L rappresenta il numero medio di bit per simbolo sorgente

Se $ L_ {min} = \: minimo \: possibile \: valore \: di \: \ overline {L} $

Poi coding efficiency può essere definito come

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

Con $ \ overline {L} \ geq L_ {min} $ avremo $ \ eta \ leq 1 $

Tuttavia, il codificatore di origine è considerato efficiente quando $ \ eta = 1 $

A tal fine, è necessario determinare il valore $ L_ {min} $.

Facciamo riferimento alla definizione: "Data una sorgente di entropia discreta priva di memoria $ H (\ delta) $, la lunghezza media della parola in codiceL per qualsiasi codifica sorgente è limitato come $ \ overline {L} \ geq H (\ delta) $. "

In parole più semplici, la parola in codice (esempio: il codice Morse per la parola QUEUE è -.- ..-. ..-.) È sempre maggiore o uguale al codice sorgente (QUEUE nell'esempio). Ciò significa che i simboli nella parola in codice sono maggiori o uguali agli alfabeti nel codice sorgente.

Quindi con $ L_ {min} = H (\ delta) $, l'efficienza del codificatore sorgente in termini di Entropia $ H (\ delta) $ può essere scritta come

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

Questo teorema del codice sorgente è chiamato come noiseless coding theorempoiché stabilisce una codifica priva di errori. È anche chiamato comeShannon’s first theorem.