Teoria dell'informazione e codici

QwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqElementi diwertyuiopasdfghjklzxcvbnmqwertyuiTeoria dell’informazione eCodiciopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcGiancarlo Ippolitovbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmrtyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopas

Elementi di teoria dell’informazione e codici

Appunti presi a lezione del corso di Teoria dell’informazione e codici tenuto dal professor Alessandro Neri A.A. 2008/2009.

Giancarlo Ippolito

Prefazione

Questa premessa che scrivo serve al solo scopo di far capire ad un eventuale lettore di questi appunti un concetto fondamentale. Quando si studia una qualsiasi materia universitaria, in questo caso teoria dell’informazione e codici, non si può basare il proprio studio solo su degli appunti scritti, ma è assolutamente necessario avere sotto mano un libro di testo.

Perché? Beh, ci sono molti motivi:

• Un libro è sicuramente completo perché tratta più argomenti e non si limita solo a quelli che vengono spiegati a lezione dal professore.
• Un libro è scritto sicuramente in una lingua più fluida e dunque i concetti vengono spiegati nel modo più semplice e in un italiano corretto.
• Un libro è scritto da delle persone competenti che hanno molti anni di esperienza, viceversa gli appunti sono scritti da studenti come me. Nelle dispense può capitare che un concetto venga espresso non nel migliore dei modi o che addirittura (e spero non sia il mio caso) venga interpretato personalmente risultando alla fine scritto in modo impreciso se non del tutto errato.

Da queste quattro righe che ho scritto si capisce che usare un libro di testo per studiare è assolutamente d’obbligo, ma allora vi domanderete a cosa servono questi appunti? Questi appunti servono come integrazione al libro, come se fossero un quaderno personale sul quale si siano scritte le proprie note che vadano eventualmente corrette e/o integrate studiando dal libro e seguendo la lezione.

Le dispense sono dunque un valido aiuto per ripassare ma sta allo studente capire se in queste sono presenti errori e/o inesattezze che debbano essere corrette. Comunque, spero che queste dispense che ho scritto possano essere di aiuto agli studenti e che siano scritte senza troppi errori.

Giancarlo Ippolito

1

Indice degli argomenti

• Capitolo 1. Teoria dell’informazione……………………………………pag. 6
• 1.1 Introduzione alla teoria dell’informazione
• 1.2 Sorgente continua e discreta
• 1.3 Sorgente con o senza memoria
• 1.4 Codifica a blocchi
• 1.5 Entropia
• 1.5.1 Entropia di una sorgente ergodica senza memoria
• 1.5.2 Entropia per una sorgente binaria ergodica senza memoria
• 1.6 Entropia congiunta
• 1.7 Entropia condizionata
• 1.8 Disuguaglianza di Kraft
• 1.9 Ottimizzazione della lunghezza delle parole di codice
• 1.10 Il canale trasmissivo
• 1.11 Probabilità di transizione di un canale
• 1.12 Equivocazione di canale
• 1.13 Capacità di canale
• 1.14 Capacità di un canale binario
• 1.15 Secondo teorema di Shannon
• 1.16 Capacità di un canale Gaussiano limitato in banda
• 1.17 Diseguaglianza di Fano
• Capitolo 2. Teoria del tasso di distorsione……………………………pag. 43
• 2.1 La quantizzazione
• 2.2 Quantizzazione scalare
• 2.3 La quantizzazione scalare Max-Lloyd
• 2.4 Quantizzazione di una sorgente con distribuzione uniforme
• 22.5 Codifica PCM (ITU G.711)
• 2.6 Quantizzazione vettoriale
• 2.7 Algoritmo LBG Codifica di sorgente:
• Capitolo 3. Codificatori di sorgente…………………………………….pag. 60
• 3.1 Il codificatore Huffman
• 3.2 Codifica di Shannon-Fano-Elias
• 3.3 Codifica e decodifica aritmetica
• 3.4 Codifica universale: Algoritmo di Lempel-Ziv
• Capitolo 4. Codifica vocale………………………………………………pag. 73
• 4.1 Codifica temporale: DPCM-ADPCM
• 4.2 Codifica per modelli
• 4.3 Linear Predictive Coding LPC
• 4.4 Predittori a breve termine
• 4.5 Metodo dell’autocorrelazione
• 4.6 Calcolo della funzione di autocorrelazione
• 4.7 Predittori a lungo termine
• 4.8 Analisi LP: Schema a blocchi
• 4.9 Line Spectral Pair LSP
• 4.10 Quantizzazione dei coefficienti LSP
• 4.11 Predizione dei coefficienti LSP
• 4.12 Pesaggio percettivo
• 4.13 Schema complessivo codificatore decodificatore vocale
• 4.14 Codifica nel GSM
• Capitolo 5. Codifica audio MPEG……………………………………….pag. 95
• 35.1 Codifica in frequenza
• 5.2 MPEG-1
• 5.3 Analisi psicoacustica MPEG-1 layer 1
• 5.4 Blocco FFT e stima dello spettro
• 5.5 Identificazione dei mascheranti tonali e non
• 5.6 MPEG-1 Layer 3. L’mp3
• 5.7 Cenni sulla trasformata MDCT
• 5.8 Distorsione Pre-Echo
• 5.9 Bit reservoir Codifica di canale
• Capitolo 6. Codifica Hamming…………………………………………pag. 110
• 6.1 Codificatore lineare a blocchi
• 6.2 Codice a blocco di Hamming
• 6.3 Codici a blocco sistematici
• 6.4 Rivelazione d’errore per codici a blocco
• 6.5 Codice duale di un codice sistematico
• 6.6 Rivelazione e correzione errori in un canale binario simmetrico
• Capitolo 7. Codici convoluzionali……………………………………..pag. 128
• 7.1 Codici convoluzionali
• 7.2 Diagramma degli stati
• 7.3 Diagramma a traliccio (Trellis)
• 7.4 Decodifica a massima verosimiglianza
• 7.5 Caso del canale binario simmetrico
• 7.6 Caso canale gaussiano additivo
• 7.7 Algoritmo di Viterbi 4
• Capitolo 8. Turbo codici…………………………………………………pag. 147
• 8.1 Introduzione alla codifica turbo
• 8.2 Codificatori convoluzionali sistematici ricorsivi (RSC)
• 8.3 Interleaver
• 8.3.1 Block Interleaver
• 8.3.2 Random Interleaver
• 8.3.3 Interleaver
• 8.3.4 Semirandom Interleaver
• 8.4 Stato finale del codificatore
• 8.5 Decodificatore turbo
• 8.6 Algoritmi di decodifica
• 8.7 Teorema di Bahl
• 8.8 Algoritmo di Bahl
• 8.9 Codici punturati
• Appendice A. Cenni sull’algoritmo di Levinson-Durbin…………..pag. 183
• Appendice B. Teoria della stima e della decisione………………..pag. 191
• Appendice C. Serie di Markov………………………………………....pag. 205
• Appendice D. Sistema uditivo umano………………………………..pag. 213
• Appendice E. Cenni sul protocollo HDCL e ARQ…………………..pag. 223
• Bibliografia………………………………………………………………...pag. 235

5

Elementi di teoria dell’informazione e codici Capitolo 1

Teoria dell’informazione

1.1 Introduzione alla teoria dell’informazione

Cercando informazioni su internet come fanno un po’ tutti gli studenti quando si cimentano nel trovare informazioni su qualcosa, ci si imbatte in molte definizioni della frase teoria dell’informazione. La definizione forse più completa che definisce meglio la frase teoria dell’informazione e codici è quella riportata sul sito dell’enciclopedia Encarta che cita le seguenti parole (bib.vi):

“Teoria dell’informazione Teoria che ha per oggetto lo studio delle leggi matematiche che regolano l’elaborazione e la trasmissione dell’informazione. In particolare, si deve alla teoria dell’informazione la sistematizzazione dei metodi di misurazione e rappresentazione dell’informazione (codifica) e la formulazione di relazioni fra variabili matematiche per ottenere un utilizzo ottimale dei sistemi di comunicazione e telecomunicazione nella“. trasmissione dei messaggi.

La nascita della teoria dell’informazione è abbastanza recente (1948) e il suo padre fondatore fu l’ingegnere Claude Shannon il quale, proprio in tale data presentò un suo elaborato dove si concentrava sul problema della ricostruzione, con un certo grado di certezza, di un messaggio inviato da un mittente. In anni successivi il lavoro di Shannon continuò pubblicando altri articoli di notevole importanza quali ad esempio, nel 1949, la teoria della comunicazione nei sistemi crittografici.

Sarebbe molto interessante continuare 6 Elementi di Teoria dell’Informazione e Codici a studiare le scoperte dell’ingegnere fondatore perché proprio da queste che tutta la teoria dell’informazione dipende ma questo non è possibile in queste dispense. Per i più interessati e curiosi raccomando la lettura dell’articolo riportato in bibliografia vii.

La teoria dell’informazione tenta di dare una risposta a due domande:

• 1. Data una sorgente che emette messaggi da inviare ad un destinatario, qual è il modo più economico e semplice per rappresentare, con una qualità prefissata, il messaggio da trasmettere?
• 2. Dato un canale affetto da rumore, come può essere trasmessa l’informazione in maniera sufficientemente affidabile?

Da queste due domande si evince dunque che la teoria dell’informazione si occupa di trovare il metodo più semplice ed economico di trasmettere informazione (codifica di sorgente), che vedremo essere di tipo con perdita di informazione (è tollerata una degradazione dell’informazione purché questa sia nota a priori) o senza perdita di informazione (codifica invertibile senza perdita di memoria, ad esempio un file zippato), e anche della trasmissione attraverso canali non ideali affetti da un certo rumore.

1.2 Sorgente continua e discreta

La sorgente è un processo aleatorio che emette delle realizzazioni in modo continuo o discreto. Di queste due specie di sorgenti si è interessati a studiare solo quelle discrete in quanto una sorgente continua può essere ricondotta a quella discreta tramite il teorema del campionamento di Shannon e il processo di quantizzazione.

L’operazione di quantizzazione, come vedremo anche più avanti, introduce un certo grado di errore che però risulta essere prevedibile e quindi conosciuto. La sorgente che si terrà in considerazione da ora in poi sarà dunque una sorgente discreta nel tempo e in ampiezza.

1.3 Sorgente con o senza memoria

Come detto nel paragrafo precedente una sorgente è un processo aleatorio e come tale gode delle sue proprietà statistiche, proprietà importanti al fine di codificare in modo economico un messaggio. D’altronde, obiettivo della teoria dell’informazione è proprio 7 Elementi di Teoria dell’Informazione e Codici quello di provare, per mezzo della teoria dei processi ergodici, teoremi fondamentali sulla codificazione dell'informazione trasmessa (in cui l'entropia gioca un ruolo essenziale).

Le sorgenti senza memoria sono sicuramente le più semplici da trattare e codificare in quanto, supposta stazionaria, per descriverla sono necessarie solo la conoscenza della probabilità dei messaggi emessi x , valori assunti dalla variabile aleatoria X, chiamata i alfabeto.

Le sorgenti con memoria, invece, hanno la caratteristica di avere i messaggi x dipendenti i l’uno dagli altri per cui si ha bisogno anche della conoscenza delle probabilità congiunte dei vari ordini, il che alle volte non è possibile. Può alle volte capitare che non siano conosciute anche le probabilità dei singoli messaggi ma, in questo caso, esistono opportune tecniche di codifica di sorgente attraverso le quali si hanno prestazioni vicine ai limiti teorici (codifica universale).

1.4 Codifica a blocchi

Sia S una sorgente discreta processo aleatorio che emette una realizzazione x[n]0 costituita da una successione di caratteri appartenenti all’alfabeto di sorgente A a L ( )= determinazioni e sia x la sequenza di k caratteri successivi, l’alfabeto,...,A a a k1 L ( ) ( )k = estensione contenente tutte i possibili messaggi di ordine k sarà , i cui,...,A b b1L Lk( )k elementi sono le L possibili sequenza di caratteri appartenenti ad A .= ,...,b a a1j j jk

Fig.1.1 Codifica a blocchi

Alla realizzazione x[n] viene applicata una codifica a blocchi (k:M) a lunghezza di parola (k) dell’alfabeto A sia associata una non necessariamente costante tale che a carattere b j 8 Elementi di Teoria dell’Informazione e Codici ( )= parola di n caratteri del nuovo alfabeto a M simboli C . Di seguito è riportata,...,C c cj 1 M una tabella di esempio nella quale si hanno 4 caratteri emessi dalla sorgente, ognuna avente una sua probabilità di emissione, ai quali attraverso 3 codifiche a blocchi (codifica 1,2,3) differenti sono state associate ad ogni carattere una certa parola di codice.

Tabella 1.1

A questo punto ci si domanda quale di questi codici sia il migliore per poter rappresentare i caratteri della sorgente. Il codice che rappresenta i caratteri dell’alfabeto della sorgente deve soddisfare due proprietà:

• 1. Univocamente decodificabile: ogni parola di codice deve rappresentare un solo simbolo dell’alfabeto di ingresso perché poi sia possibile l’inversione della trasformazione (cioè deve essere possibile partire dalla parola del codice e ritornare al carattere della sorgente).

Figura 1.2 codice univocamente trasformabile

9 Elementi di Teoria dell’Informazione e Codici

• 2. Istantaneamente decodificabile: l’inversione deve poter avvenire istantaneamente senza dover aspettare gli altri caratteri. Affinché un codice sia istantaneamente è necessario che sia applicata la cosiddetta regola del prefisso, la quale dice che un codice è istantaneamente decodificabile se non esiste nessuna parola di codice che coincida interamente con un’altra parola di codice di lunghezza maggiore. Il codice riportato di seguito è un codice istantaneamente decodificabile.

a =0, a =10, a =110, a =1110, a =11111 2 3 4 5

Si può dimostrare che se un codice è istantaneamente decodificabile, allora esso è anche univocamente decodificabile.

1.5 Entropia

Nella teoria dell'informazione l'entropia è definita come la misura della quantità di incertezza o informazione presente in un certo segnale aleatorio. Da un altro punto di vista l'entropia è anche la minima complessità descrittiva di una variabile casuale.

Si deve a Claude Shannon lo studio dell'entropia in tale contesto. Nel primo teorema di Shannon, o teorema di Shannon sulla codifica di sorgente, egli dimostrò che una sorgente casuale d'informazione non può essere rappresentata con un numero di bit inferiore alla sua entropia, cioè alla sua autoinformazione media.

Per Claude Shannon la teoria dell’informazione è una caratteristica intrinseca dei sistemi usati per comunicare. L'informazione di un messaggio non può mai aumentare oltre il valore che aveva al momento della sua trasmissione, ma può invece diminuire per colpa di svariati processi che conducono ad una perdita parziale o ad un deterioramento del messaggio.

Fin qui la relazione fra le due grandezze può non essere evidente. Esse, anzi, (aumento per appaiono come due grandezze che presentano un comportamento opposto l'entropia, diminuzione per l'informazione). Ma l'analisi di queste due grandezze può essere più dettagliata.

Se guardiamo un sistema fisico dal punto di vista microscopico possiamo descriverlo con una distribuzione di probabilità, che fornisca, per ogni costituente microscopico, la probabilità di osservarlo con una certa velocità in una certa posizione. Boltzmann stabilì che c'era un collegamento matematico tra questa 10 Elementi di Teoria dell’Informazione e Codici distribuzione di probabilità e l'entropia, particolare che l'entropia di un sistema è proporzionale al valore medio assunto dal logaritmo di questa distribuzione di probabilità cambiato di segno.

Shannon introdusse una grandezza analoga per studiare l'informazione. Al livello più elementare ogni messaggio può essere espresso come sequenza di caratteri. A seconda del messaggio ogni carattere può essere previsto o meno, con diversi gradi di certezza a partire dai caratteri che precedono.

Quanto più un carattere è prevedibile, tanto meno aggiunge informazione al messaggio ridondante, globale, cioè è potrebbe essere omesso e il messaggio sarebbe compreso ugualmente. Se io trasmetto la sequenza "telefo" la persona che riceve saprà con certezza che la lettera che segue è "n", perché non ci sono parole in italiano che iniziano con "telefo" e continuano con altre lettere, per cui trasmettere questa "n" è ridondante, ma dopo la "n" avrà un certo grado di incertezza su cosa segue, potrebbe essere "o" e avere quindi