Teoria Dell'Informazione e Codici

  • Published on
    13-Jul-2015

  • View
    124

  • Download
    0

Embed Size (px)

Transcript

<p>Teoria dellinformazione e codiciIng. Pazzo 20 settembre 2009</p> <p>2 Si consiglia di afancare il materiale presente in questo riassunto agli appunti presi a lezione. Questo perch (ovviamente!) non si vuole avere alcuna presunzione di esaustivit, n di assoluta correttezza: nonostante le revisioni nora effettuate, potrebbero infatti essere ancora presenti molti errori e imprecisioni.</p> <p>2</p> <p>Indice1 Introduzione alla Teoria dellInformazione 1.1 Schema del collegamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 La teoria dellinformazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Eventi, variabili aleatorie, bit dinformazione . . . . . . . . . . . . . . . . . . . . . 1.3.1 Informazione associata a due eventi indipendenti . . . . . . . . . . . . . . 1.3.2 Entropia di una variabile aleatoria . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Probabilit condizionata, probabilit marginale, distribuzione congiunta 1.3.4 Entropia congiunta, entropia condizionata . . . . . . . . . . . . . . . . . . 7 7 8 8 9 9 12 13 19 19 20 20 21 22 24 26 26 27 28 29 29 30 31 31 32 32 33 33 34 36 39 40 40 42 44 45 46 47 48 49</p> <p>. . . . . . .</p> <p>. . . . . . .</p> <p>. . . . . . .</p> <p>. . . . . . .</p> <p>. . . . . . .</p> <p>. . . . . . .</p> <p>. . . . . . .</p> <p>2</p> <p>Codica di sorgenti discrete 2.1 Osservazione simbolo per simbolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Osservazione per gruppi di simboli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Entropia di una sorgente stazionaria: due denizioni . . . . . . . . . . . . . . . . . . . . . . 2.4 Ridondanza e confronto fra sorgenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Tecniche di compressione dei dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Codici a presso e disuguaglianza di Kraft . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Unapplicazione della disuguaglianza di Kraft: i codici a presso di Shannon-Fano 2.6 Teorema della codica di sorgente (I teorema di Shannon) . . . . . . . . . . . . . . . . . . . 2.7 Codice di Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Codica a blocchi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Codica a corse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Codice di Lempel-Ziv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.11 Considerazioni nali: lossy o lossless? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . .</p> <p>3</p> <p>La codica di canale e la capacit 3.1 Canale discreto senza memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Capacit di canale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Canale deterministico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Canale binario simmetrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Canale binario a cancellazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4 Canale Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.5 Canale binario non simmetrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Capacit di canale con blocchi di simboli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Disuguaglianza del data processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Disuguaglianza di Fano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Codica di canale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Teorema della codica di canale (secondo teorema di Shannon) . . . . . . . . . . . . . . . . . 3.8 Variabili aleatorie continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Entropia differenziale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9.1 Teorema: la distribuzione uniforme ha entropia massima (caso intervallo limitato) . 3.9.2 Teorema: la distribuzione gaussiana ha entropia massima (caso intervallo illimitato) 3.9.3 Teorema: la distribuzione esponenziale negativa ha entropia massima (caso intervallo 0, ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3</p> <p>4 4 Il limite di Shannon 4.1 Capacit del canale additivo gaussiano bianco . . . . . . . . . . . . . . 4.2 Caso tempo-continuo a banda limitata (formula di Hartley-Shannon) . 4.2.1 Incorrelazione del rumore . . . . . . . . . . . . . . . . . . . . . . 4.3 Il limite di Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Antipodal Signalling AWGN . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Hard decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Unquantized output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Low SNR region . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 Trattamento dei segnali passa-banda e water-lling . . . . . . . . . . . . 4.8.1 Caso tempo-discreto . . . . . . . . . . . . . . . . . . . . . . . . . I codici di canale: codici a blocco 5.1 Codici a blocco . . . . . . . . . . . . . . . . . . . . . 5.1.1 Alcune denizioni e terminologia . . . . . . 5.2 Concetti elementari di algebra lineare . . . . . . . . 5.3 Codici a blocco lineari . . . . . . . . . . . . . . . . . 5.4 La matrice generatrice . . . . . . . . . . . . . . . . . 5.5 Codici sistematici . . . . . . . . . . . . . . . . . . . . 5.6 Matrice di controllo parit . . . . . . . . . . . . . . . 5.7 Codici estesi . . . . . . . . . . . . . . . . . . . . . . . 5.8 Codici purgati . . . . . . . . . . . . . . . . . . . . . . 5.9 Il Singleton Bound . . . . . . . . . . . . . . . . . . . . 5.10 Codici di Hamming . . . . . . . . . . . . . . . . . . . 5.11 La decodica e la Teoria della Decisione . . . . . . . 5.12 Decodica ottima per codici a blocco su canale BSC 5.13 Rilevazione degli errori e standard array . . . . . . . 5.14 Capacit di correzione di un codice (canale BSC) . . 5.15 Criterio ML per canali additivi gaussiani . . . . . . 5.16 Union Bound . . . . . . . . . . . . . . . . . . . . . . . 5.17 Codici accorciati (shortened codes) . . . . . . . . . . . 5.18 Codici a blocco lineari ciclici . . . . . . . . . . . . . 5.19 Codicatore per codici ciclici (sistematici e non) . . 5.20 Calcolo della sindrome . . . . . . . . . . . . . . . . . 5.21 Applicazioni notevoli dei codici ciclici . . . . . . . . 5.21.1 CRC: Cyclic Redundancy Check Codes . . . . . 5.21.2 Codici Hamming ciclici . . . . . . . . . . . . 5.21.3 Codice di Golay . . . . . . . . . . . . . . . . . 5.21.4 Codici BCH . . . . . . . . . . . . . . . . . . . 5.22 Codici di Reed-Solomon . . . . . . . . . . . . . . . . 5.23 Codici per la rilevazione di errori burst . . . . . . . 5.24 Codici MLSR (Maximum Length Shift-Register Codes)</p> <p>INDICE 51 51 53 55 56 57 60 61 62 63 65 69 69 70 71 71 73 74 74 76 77 77 78 78 79 80 82 84 85 88 89 92 92 94 94 95 95 95 95 96 96 99 99 100 101 102 102 103 103 103 103</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>. . . . . . . . . .</p> <p>5</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>. . . . . . . . . . . . . . . . . . . . . . . . . . . . .</p> <p>6</p> <p>Codici a traliccio 6.1 Codici convoluzionali . . . . . . . . . . . . . . . . . . . . . . . 6.2 Diagramma a traliccio . . . . . . . . . . . . . . . . . . . . . . . 6.3 Decodica dei codici convoluzionali con hard decisions su BSC 6.4 Algoritmo di Viterbi . . . . . . . . . . . . . . . . . . . . . . . . 6.4.1 Complessit . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.2 Altri aspetti implementativi . . . . . . . . . . . . . . . . 6.5 Codici convoluzionali punturati . . . . . . . . . . . . . . . . . 6.6 Codici convoluzionali sistematici . . . . . . . . . . . . . . . . . 6.7 Codici convoluzionali catastroci (paura eh!?) . . . . . . . . . 4</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>. . . . . . . . .</p> <p>INDICE 7 Altri aspetti riguardanti i codici di canale 7.1 Interleaving . . . . . . . . . . . . . . . . 7.1.1 Interleaving a blocco . . . . . . 7.2 Codici concatenati . . . . . . . . . . . 7.3 Turbo-codici . . . . . . . . . . . . . . . 7.4 LDPC: Low Density Parity Check . . . . 7.4.1 QC-LDPC . . . . . . . . . . . .</p> <p>5 105 105 105 106 106 108 108</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>. . . . . .</p> <p>5</p> <p>6</p> <p>INDICE</p> <p>6</p> <p>Capitolo 1</p> <p>Introduzione alla Teoria dellInformazione1.1 Schema del collegamento</p> <p>Figura 1.1:</p> <p>Lo schema del collegamento</p> <p>Nessun riassunto di Teoria dellInformazione deve iniziare senza aver prima visto lo schema del collegamento! Questo schemino essenziale mostra il percorso che linformazione compie, dalla sorgente allutilizzatore nale; gli step sono i seguenti: sorgente: trattasi della sorgente dellinformazione: pu essere unentit analogica1 (un suono), ma anche uninformazione in formato digitale come un documento, un brano audio, etc. . . codicatore di sorgente: ha il compito di rappresentare i dati in maniera pi sintetica, in modo che si possa spedire quanta pi informazione possibile nel minor tempo possibile. Possono essere di due tipi, in base a se viene persa informazione (esempio: codica JPEG) o meno (esempio: compressione ZIP); codicatore di canale: ha il compito di proteggere, con laggiunta di simboli di ridondanza, i dati dai disturbi che possono essere fonte di errori; canale: letere, un lo, oppure un supporto di memorizzazione di massa (hard-disk); decodicatore di canale: componente duale del codicatore di canale; decodicatore di sorgente: componente duale del codicatore di sorgente; lutilizzatore nale: colui che desidera fruire dellinformazione.1 In</p> <p>tal caso sar necessario un convertitore A/D.</p> <p>7</p> <p>8</p> <p>CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELLINFORMAZIONE</p> <p>1.2</p> <p>La teoria dellinformazioneThe information is the difference which makes a difference. Linformazione quella differenza che fa la differenza. Gregory Bateson</p> <p>Che cos linformazione? In una comunicazione, che avviene attraverso un dato alfabeto di simboli, linformazione viene associata a ciascun simbolo trasmesso e viene denita come la riduzione di incertezza che si poteva avere a priori sul simbolo trasmesso. Linformazione non semplicemente una variazione: una sequenza del tipo</p> <p>... 01010101010101010...varia continuamente, ma non porta informazione perch assolutamente prevedibile. In questo senso, linformazione legata alla non prevedibilit di un certo evento: ad esempio, se affermiamo che Oggi, in questo punto, non sono caduti degli aerei, non diamo una grande informazione perch si presuppone che questo accada per la stragrande maggioranza del tempo. Viceversa laffermazione Oggi, in questo punto, sono caduti degli aerei ha una componente informativa molto pi preziosa (anche se un po drammatica). La Teoria dellinformazione quel settore delle telecomunicazioni che si occupa di denire le basi teoriche su cui si fonda la scienza dellinformazione. La sua nascita relativamente recente: essa viene solitamente fatta risalire al 1948, anno in cui Claude Shannon pubblic sul Bell System Technical Journal Una teoria matematica della comunicazione in cui introduceva per la prima volta in modo sistematico lo studio dellinformazione e della comunicazione. Grazie alla sua affascinante teoria, Shannon riuscito a denire e specicare in maniera quantitativa i meccanismi di compressione, codica e trasmissione dei dati, mostrandocene i limiti ultimi.</p> <p>1.3</p> <p>Eventi, variabili aleatorie, bit dinformazione</p> <p>Linformazione fortemente legata al concetto di evento e il concetto di evento a quello di variabile aleatoria (v.a. o r.m.2 ). Indicheremo con X una generica variabile aleatoria e con linsieme di tutti gli L valori che essa pu assumere x1 , x2 , . . . , x L In questo contesto, L viene detta cardinalit di . A ciascun possibile risultato dellesperimento incarnato dalla variabile aleatoria viene associato un valore e una probabilit: p X p X p X x1 x2 ... xL p xL pL p x1 p x2 p1 p2</p> <p>Chiaramente, per le basilari propriet del calcolo aleatorio, si deve avere che</p> <p> pii</p> <p>1</p> <p>(1.1)</p> <p>Linformazione portata dallesperimento x pari a: I x log2 1 p x log2 p x (1.2)</p> <p>Gracando la curva otteniamo la gura 1.2. Lunit di misura per I il cosiddetto Shannon (Sh) detto anche bit di informazione.2 Random</p> <p>Variable.</p> <p>8</p> <p>CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELLINFORMAZI...</p>