Nella teoria dell'informazione, il primo teorema di Shannon (o teorema della codifica di sorgente), stabilisce dei limiti alla massima compressione possibile di un insieme di dati e definisce il significato operativo dell'entropia.
Il teorema stabilisce che, per una serie di variabili aleatorie indipendenti ed identicamente distribuite (i.i.d.) di lunghezza che tende ad infinito, non è possibile comprimere i dati in un messaggio più corto dell'entropia totale senza perdita di informazione. Al contrario, compressioni arbitrariamente vicine al valore di entropia sono possibili, con probabilità di perdita di informazione piccola a piacere.
Il teorema della codifica di sorgente per simboli di codice, stabilisce un limite inferiore e superiore alla minima lunghezza attesa di una serie di parole di codice, in funzione dell'entropia della parola in ingresso (vista come una variabile aleatoria) e della dimensione dell'alfabeto in esame.
La codifica di sorgente è un mappaggio da una sequenza di simboli generati da una sorgente ad una sequenza di simboli di un alfabeto (solitamente binario), tale che i simboli sorgenti possano essere esattamente recuperati dai bit (codifica senza perdite) o recuperati con qualche distorsione (codifica con perdite). Questo è il concetto che sta alla base della compressione dei dati.
In altre parole si può dire che è la modalità con la quale ciascun evento associato ad una sorgente discreta viene codificato mediante una sequenza di simboli.
La codifica di sorgente introduce i concetti alla base della "qualità dell'informazione":
- la quantità di informazione
è data da
, dove
è la probabilità dell'informazione. Si può quindi dire che tra l'informazione stessa e la sua probabilità vi è una relazione inversamente proporzionale (un'alta probabilità porta ad una bassa quantità di informazione e viceversa).
Volendo, ora, stabilire un'unità di misura è opportuno far riferimento al caso in cui si ha bisogno dell'informazione minima per prendere una decisione.
Trascurando il caso limite (quando l'evento è certo) nel quale esiste un solo risultato, il caso con il minimo bisogno di informazione è quello in cui esistono due possibili risultati equiprobabili (es.: il lancio di una moneta).
Si definisce con bit la quantità di informazione necessaria, e sufficiente, per discriminare e decidere tra due soli eventi equiprobabili:
, dove
è l'indice di proporzionalità.
- L'informazione mediata, o entropia,
è pesata dai contributi dell'informazione per la sua probabilità:
[bit/simbolo].
- La velocità di modulazione, o baudrate è la velocità di emissione dei simboli da parte della sorgente:
, dove
è la durata del simbolo.
- La velocità di trasmissione media dell'informazione del sistema, o bitrate, si calcola con:
.
Altri parametri importanti si riassumono in:
- Lunghezza media del simbolo
(ni=lunghezza del codice)
- Rendimento del codice
(η assume valori da 0 a 1)
- Ridondanza
.
In teoria dell'informazione il teorema della codifica di sorgente (Claude Shannon, 1948) stabilisce che:
Sia
una variabile casuale a valori in un alfabeto finito
e sia
un codice decifrabile (ossia una funzione univoca) da
a
, dove
. Sia S la risultante lunghezza della parola di codice
.
Se
è ottima nel senso che ha la minima lunghezza attesa per la parola di codice
, allora
![{\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} \left\lbrace S\right\rbrace <{\frac {H(X)}{\log _{2}a}}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/107396c16b6de1964d1ce8087ef66cfcdfae5692)
(Shannon 1948)
Siano
una sorgente di variabili i.i.d. e
una serie di uscite con entropia
nel caso discreto ed uguale entropia differenziale nel caso continuo. Il teorema della codifica di sorgente stabilsce che per ogni
, esiste un
abbastanza grande ed un codificatore che prende
uscite i.i.d. della sorgente e le mappa su
bit, in modo che i simboli sorgente
siano recuperabili con probabilità di almeno
.
- Dimostrazione di raggiungibilità
Sia fissata una qualche
. L'insieme tipico,
, è definito come
La proprietà di equipartizione asintotica (AEP), mostra che per un
largo abbastanza, la probabilità che una sequenza generata dalla sorgente cada nell'insieme tipico,
, tende ad uno. In particolare per un
grande abbastanza,
.
La definizione di insieme tipico, implica che le sequenze che cadono nell'insieme tipico soddisfano la condizione
![{\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p(x_{1},x_{2},...,x_{n})\leq 2^{-n(H(X)-\varepsilon )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87a619756ca2e937c19058fc4d1150555bade9d9)
Si noti che:
- La probabilità che una sequenza di
cada in
è maggiore di ![{\displaystyle 1-\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/09646b74d0bca9befab4b7e9456a44a20d250ace)
, dato che la probabilità dell'insieme
è al massimo uno.
. Per la prova è sufficiente utilizzare il limite superiore della probabilità di ogni termine nell'insieme tipico ed il limite inferiore sulla probabilità dell'insieme set
.
Dato che
bit sono sufficienti per rappresentare ogni stringa nell'insieme.
L'algoritmo di codifica: il codificatore controlla che la sequenza di ingresso cada nell'insieme tipico; se sì produce in uscita l'indice della sequenza d'ingresso nell'insieme tipico; se no, il codificatore produce un arbitrario unumero binario
. Se la sequenza ricade nell'insieme tipico, il che avviene con probabilità di almeno
, il codificatore non commette errori. Quindi la probabilità di errore del codificatore è inferiore a
.
- Prova dell'inverso
L'inverso si dimostra mostrando che qualunque insieme di dimensione inferiore a
, avrebbe probabilità al limite sicuramente inferiore a 1 .
Sia
la lunghezza di ogni possibile parola di codice
(
). Definito
, dove
è tale che
.
Allora
![{\displaystyle {\begin{array}{rcl}H(X)&=&-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&&\\&\leq &-\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&&\\&=&-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}\log _{2}C\\&&\\&\leq &-\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&&\\&\leq &\mathbb {E} \left\lbrace S\right\rbrace \log _{2}a\\\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/651b7818307c09a44b978f806c8ac6bac2aad2f8)
dove la seconda linea deriva dalla disuguaglianza di Gibbs e la quarta dalla disuguaglianza di Kraft-McMillan:
e dunque
.
per la seconda disuguaglianza possiamo imporre
![{\displaystyle s_{i}=\lceil -\log _{a}p_{i}\rceil }](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d4ce1b2b20eab899e13952689f57ae0e7ec84ea)
in modo che
![{\displaystyle -\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3d69b1c1785dffb4b1df15103823e42e6daf02f)
e quindi
![{\displaystyle a^{-s_{i}}\leq p_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36657790767da95f5abe28686bc7a957c20d9f74)
e
![{\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6555a9325950933aaab932fb998351d6fe2497a)
e dalla disuguaglianza di Kraft, esiste una codice univoco con parole di codice aventi tale lunghezza. Quindi il minimo
soddisfa
![{\displaystyle {\begin{matrix}\mathbb {E} \left\lbrace S\right\rbrace &=&\sum p_{i}s_{i}\\&&\\&<&\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&&\\&=&\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&&\\&=&{\frac {H(X)}{\log _{2}a}}+1\\\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d12de09f048b018715dc0a5876a371fc8d18220)
Codifica di sorgente senza perdita a tasso fisso per sorgenti indipendenti discrete e non stazionarie
[modifica | modifica wikitesto]
Sia definito l'insieme tipico
come
![{\displaystyle A_{n}^{\varepsilon }=\;\{x_{1}^{n}:\left|-{\frac {1}{n}}\log p(X_{1},X_{2},...,X_{n})-{\bar {H_{n}}}(X)\right|<\varepsilon \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7e91b582f5f05c33d0780135633fabcd3cd67f3)
Allora per un dato
, per un
grande abbastanza,
.Ora ci limitiamo a codificare le sequenze nell'insieme tipico ed il solito metodo di codifica mostra che la cardinalità di questo insieme è inferiore a
. Quindi, in media,
bitn sono sufficienti per codificare la sequenza con probabilità di corretta decodifica superiore a
, dove
possono essere rese piccole a piacere aumentando
.