Teoria dell'informazione e codici

Qwertyuiopasdfghjklzxcvbnmqwerty

uiopasdfghjklzxcvbnmqwertyuiopasd

fghjklzxcvbnmqwertyuiopasdfghjklzx

cvbnmqwertyuiopasdfghjklzxcvbnmq

Elementi di

wertyuiopasdfghjklzxcvbnmqwertyui

Teoria dell’informazione e

Codici

opasdfghjklzxcvbnmqwertyuiopasdfg

hjklzxcvbnmqwertyuiopasdfghjklzxc

Giancarlo Ippolito

vbnmqwertyuiopasdfghjklzxcvbnmq

wertyuiopasdfghjklzxcvbnmqwertyui

opasdfghjklzxcvbnmqwertyuiopasdfg

hjklzxcvbnmqwertyuiopasdfghjklzxc

vbnmqwertyuiopasdfghjklzxcvbnmq

wertyuiopasdfghjklzxcvbnmqwertyui

opasdfghjklzxcvbnmqwertyuiopasdfg

hjklzxcvbnmrtyuiopasdfghjklzxcvbn

mqwertyuiopasdfghjklzxcvbnmqwert

yuiopasdfghjklzxcvbnmqwertyuiopas

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

2

2.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

3

5.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 Inerleaver

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’informazioni. 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 noon 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 k

1 L ( ) ( )

k =

estensione contenente tutte i possibili messaggi di ordine k sarà , i cui

,...,

A b b

1

L Lk

( )

k

elementi sono le L possibili sequenza di caratteri appartenenti ad A .

= ,...,

b a a

1

j 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 c

j 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 =1111

1 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 coma 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