Teoria dell'Informazione: Sorgenti, Codici e Canali

Sorgenti

Sorgente senza memoria

Consideriamo una sorgente S che emette simboli da un alfabeto S = {s₁,...s_n} con probabilità P(s₁),...,P(s_n). La sorgente è senza memoria se i simboli emessi sono statisticamente indipendenti.

Entropia di sorgente senza memoria

Quantità media di informazione per simbolo emesso dalla sorgente. Può essere interpretata come l'incertezza media che un osservatore ha prima di vedere l'output della sorgente. (H(S) = ∑_i=1,q P(s_i) * log₂(1/P(s_i)).

• Entropia nulla: quando si sa già cosa verrà emesso dalla sorgente, quindi non c'è nulla di aleatorio.
• Entropia massima: la sorgente S fornisce il massimo dell'informazione quando tutti i simboli che emette hanno la stessa probabilità.

Distanza di Hamming

La distanza di Hamming tra due parole di codice è il numero di bit per cui le due parole differiscono. Posso sistemare le parole di codice ai vertici di un ipercubo di Hamming.

Definizione: La distanza di Hamming di un codice C è la distanza minima fra tutte le possibili coppie di parole di codice e si indica con d_H(C).

• Rilevazione di errore: se la distanza di Hamming di un codice è almeno pari a d + 1 (con d intero) allora è possibile rilevare errori fino a quelli di ordine d.
• Correzione di errore: se la distanza di Hamming di un codice è inferiore a 2t + 1 (con t intero) è possibile correggere errori fino a quello di ordine t applicando il criterio di massima verosimiglianza.
• Rilevazione e correzione: se la distanza di Hamming di un codice è non inferiore a d + t + 1, con d > t, allora è possibile correggere t errori e rilevare fino a d errori.

Incertezza evento

In un processo di comunicazione tra 2 agenti (sorgente e destinazione), c'è scambio di informazione quando si produce un effetto sul ricevente, rimuovendo incertezza legata al verificarsi di un esito incerto. I = 1/P(E). Sia E un evento che si verifica con probabilità P(E). Se ci viene comunicato che l'evento E si è verificato, allora riceviamo I(E) = log₂(1/P(E)) bit.

Canali

Fissato un sistema astratto di simboli tra sorgente e destinazione. Un canale è un mezzo fisico attraverso il quale si propagano opportune modificazioni dello stato del canale. Queste modificazioni codificano i simboli che S comunica a D. (Trasduzione: trasformazione del dominio del segnale)

Sorgenti binarie e codifica

Sorgente senza memoria binaria

Emette solo due simboli S = {s₁, s₂}.

Codice di sorgente

È un meccanismo attraverso il quale i simboli di sorgente vengono codificati al fine di essere comunicati alla destinazione. Data sorgente S = {s₁,...,s_n} e alfabeto di codifica X = {x₁,...,x_n} un codice C trasforma sequenze di simboli di S in sequenza di simboli di X, ovvero parole di codice.

• Codice a blocchi: è un codice che mappa ogni simbolo di una sorgente in una fissata sequenza di simboli dell’alfabeto X. (s_i -> x_i)
• Codice non regolare: quando a simboli di sorgente s_i diversi vengono associate parole di codice diverse.
• Estensione n-esima di codice a blocchi: che mappa i simboli s_i in parole di codice x_i è un codice a blocchi che mappa sequenze di simboli in sequenze di parole di codice (Cs_i -> x_i).
• Codice univocamente decodificabile: un codice C è univocamente decodificabile se e solo se la sua estensione n-esima C^h è non singolare per ogni h. A sequenze di simboli sorgente (s₁,...,s_n) della stessa lunghezza corrispondono parole di codice distinte. Un codice univocamente decodificabile è detto istantaneo se è possibile decodificare ogni parola di codice in una sequenza senza doversi riferire ai simboli successivi. Il codice C è istantaneo se non esiste parola di codice che sia prefissa di un'altra.

Lunghezza media di codice (McMillan)

Consideriamo un codice a blocchi che trasforma i simboli di sorgente s₁...s_q in parole di codice x₁...x_q. Siano P₁...P_q le probabilità dei simboli e siano L₁...L_q le lunghezze delle parole di codice. Allora la lunghezza media del codice è: L = ∑_i=1,q P_i * L_i.

Codifica compatta

Data una sorgente S e un alfabeto di codifica X a r simboli, il codice C è compatto se la sua lunghezza media L(S,C) è minore o uguale alla lunghezza media L(S,C') di qualsiasi altro codice C' sulla stessa sorgente e sullo stesso alfabeto di codifica.

Codifica di Huffman

È un modo per costruire i codici compatti su una data sorgente S senza dover ricorrere alla sua estensione n-esima.

• Il codice non è unico perché al passo s_i+1 <- s_i si possono scambiare 0 con 1.
• La scelta dei simboli con peso minore potrebbe non essere unica, ma la lunghezza media del codice non cambia.
• Il codice è compatto e istantaneo.
• Le parole di codice più corte sono assegnate ai simboli più probabili, mentre i due ultimi simboli q e q-1 hanno la stessa lunghezza.
• Se P_i = 2^-λi allora L_i = λ_i se λ_i è un intero.

Canali senza memoria

È descritto da un alfabeto di ingresso A = {a₁…a_r}, un alfabeto di uscita B = {b₁…b_s} e un insieme di probabilità condizionate P(b_j|a_i) per tutti gli i e j. P(b_j|a_i) è la probabilità che in output si riceva il simbolo b_j dato che in input è stato mandato a_i.

Canale binario simmetrico

È detto simmetrico perché la probabilità di avere in output 0 dato che in input c'era 1 è uguale alla probabilità di avere in output 1 dato che in input c'era 0.

Canale senza rumore

Un canale descritto dalla matrice di canale è senza rumore quando in ogni colonna è presente un solo elemento non nullo [Equivocazione H(A|B) = 0] perché conoscendo l’output so per certo qual è stato l’input. [Irrilevanza H(B|A) >= 0] perché H(B|A) = H(B|a₁) * P(a₁) + H(B|a₂) * P(a₂).... Quindi a destinazione arriva irrilevanza dovuta al canale. [I(A;B) = H(A) in un canale senza rumore: tutto ciò che parte arriva a destinazione.

Canale deterministico

Un canale descritto da una matrice di canale si dice deterministico quando in ogni riga è presente uno ed un solo elemento non nullo. [Irrilevanza H(B|A) = 0] perché conoscendo l’input so per certo quale sarà l’output. [Equivocazione H(A|B) >= 0] perché H(A|B) = H(A|b₁) * P(b₁) + H(A|b₂) * P(b₂).... [I(A;B) = H(B)] perché il canale perde informazione.

Canale deterministico e senza rumore

Un canale descritto da una matrice di canale si dice deterministico e senza rumore quando in ogni riga e in ogni colonna della matrice è presente un solo elemento non nullo [Equivocazione H(A|B) e irrilevanza H(B|A)] sono nulle perché conoscendo l’input so per certo l’output e viceversa. [I(A;B) = H(A) = H(B)].