Teoria Dell'Informazione

  • Published on
    18-Jun-2015

  • View
    3.163

  • Download
    3

Embed Size (px)

Transcript

<p>TEORIADELLINFORMAZIONEECODICISandroBelliniPolitecnicodiMilanoPrefazioneQuestebrevi notesonostatescrittepergli studenti del corsodi TeoriadellinformazioneecodicidametenutopressolaFacolt`adiIngegneriadelPolitecnicodiMilano. Partedelmaterialequi presentatosi trovasutesti classici, manonmancanomodi di vederepi` umoderni reperibili solo in articoli recenti. Lo scopo principale `e di fornire una sintesi, senzachesidebbaestrarrelinformazionedapi` ufontie,inevitabilmente,connotazionidiverse.Il primo capitolo `e dedicato alla teoria dellinformazione, creata da Shannon e resa pubblicanel 1948. Sonoriassunti i pi` usemplici, maanchepi` uimportanti, risultati sullacodicadi sorgenteedi canale. Si pu`oaermarechesenzaquesti riferimenti leapplicazioni eglisviluppipraticineidecenniseguentienoadoggisarebberostatimoltopi` ulenti.Si assume che il lettore abbia gi`a una conoscenza adeguata della teoria delle probabilit`a, esiastatoalmenoparzialmenteespostoaiproblemidellatrasmissionenumerica.Il secondocapitolopresentaunaintroduzionemoltosempliceallacodicaablocco, i cuiprimi passi sono riferibili agli stessi anni in cui nacque la teoria dellinformazione. Si mostracomemolti dei codici di interessepraticosianosinteticamentedescritti daunpolinomiogeneratore,senzatuttaviaentrarenelprogettodelcodice(salvomostrare,comegi`aShan-non aveva aermato, che se non vi fossero problemi di complessit`a il caso sarebbe un buonalleatonellacostruzionedicodiciecienti).Icodici convoluzionali, chehannodominatolascenapermolti anni, sonopresentati nelterzo capitolo. Nonoccorrono particolari strumenti matematici per capire, o addirit-turaprogettare, codici convoluzionali. Il capitolo`equindi abbastanzaagevole, comeilprecedente.Nel quarto capitolo sono riferiti gli elementi fondamentali della teoria dei campi niti, cio`edellabasematematicadei codici abloccopi` unoti epi` ufrequentementeusati. Lastessamatematica `eindispensabilepercomprendereladecodicaalgebricaditalicodici.Ilcapitolosuccessivod`aglielementiperlacostruzionedeicodiciBCHeReed-Solomoneper la loro decodica. Oggi le occasioni in cui si scelgono tali codici non sono pi` u frequenticomeinpassato,benchesoprattuttoiReed-Solomonsidifendanoancorabene. Lascarsaadattabilit`a delle tecniche algebriche alla decodica softfa preferire altri codici quando taleinformazione `e disponibile alluscita del canale di trasmissione. Tuttavia la matematica deicampi niti `e talmente interessante e aascinante che vien voglia di augurare ancora lungavitaallesueapplicazioni(fracuioggioccorrecitarealcunetecnichedicrittograa).Ilsestocapitolo`ededicatoadapprofondimentisuicodiciablocco, einparticolareadueimportanti applicazioni della trasformata di Hadamard: le relazioni tra pesi di un codice edel suo duale, ed il calcolo delle probabilit`a a posteriori dei bit dinformazione basato sulleparoledelcodiceduale.Il capitolosuccessivointroducei turbocodici, chehannorivoluzionatolostatodellartedella codica negli ultimi anni (sempre che siano tollerabili i ritardi nella trasmissione pro-dotti dablocchidi grande dimensione). Comincianoadessere disponibilialcunistrumentiiiperlaprevisionedelleprestazionideiturbocodici,chevengonosinteticamentepresentati.Nellultimocapitolosiarontailproblemadeicodiciadattiallecostellazionimultilivello,esipresentailpuntodivistapi` umodernosullargomento. Simostracomeicodicibinari(e quindi in particolare i turbo codici) possano essere utilizzati anche con tali costellazioni.Tuttaviasi accennaancheallatecnicachehadominatotali applicazioni per ventanni,ancheseorasembrerebbedestinataadunrapidodeclinoperlomenonelleapplicazionichepossonosopportareiconsiderevoliritardideiturbocodici.Questotestonon`epensatoperunarapidaconsultazione, mapiuttostoperunapprendi-mento pi` u sistematicodei fondamenti dellateoriadellinformazione e dei codici,mettendoin evidenza come i maggiori progressi nelle tecniche di codica abbiano sempre avuto comeguidaeispirazionelateoriadellinformazione.E sempremoltodicileresistereallatentazionedi includerequael`adivagazioni eap-profondimenti, forsenonstrettamenteindispensabili machetuttaviapossonoincuriosirequalche lettore. In genere si cede alleleganza formale di un risultato, tendendo a trascurareil fattochenontutti gli utilizzatori netrarrannolostessopiacere. Durantelelezioni sitornarapidamenteallarealt`a.Allo stesso modo la tentazione in cui non deve cadere un docente `e tramandare tutto quantoha studiato, indipendentemente dalla reale utilit`a. Occorre mettere nella giusta prospettivail vasto materiale disponibile, e in denitiva cancellare ampie porzioni del passato per darespazioalnuovo.E bene avvertire il lettore che per semplicare la notazione sono frequentemente sottintesigli estremi di integrali esomme, qualorasianoinniti oppurechiaramentededucibili dalcontesto.Ringrazioling. MarcoFerrari, concui collaborodatemponelleattivit`aistituzionali diricercaedidattica,inparticolare(manonsolo)perleguredelcapitolosuiturbocodiciepericommentisututtoiltesto.Le imprecisioni e gli errori sono inevitabili, e sono responsabilit`a solo dellautore. Spero chenonsianotropponumerosiecherisultifacileintuirecosaavreivoluto,edovuto,scrivere.CometuttiimieilavoridedicoanchequestoaIlia,miamoglie.SandroBelliniIndice1 Teoriadellinformazione 11.1 Introduzioneallateoriadellinformazione . . . . . . . . . . . . . . . . . . . 11.2 Codicadisorgente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.1 Sorgenticontinueediscrete . . . . . . . . . . . . . . . . . . . . . . 21.2.2 Sorgentisenzamemoriaeconmemoria . . . . . . . . . . . . . . . . 21.2.3 Entropiadisorgentisenzamemoria . . . . . . . . . . . . . . . . . . 31.2.4 Codicadisorgentisenzamemoria . . . . . . . . . . . . . . . . . . 51.2.5 Entropiacondizionata . . . . . . . . . . . . . . . . . . . . . . . . . 81.2.6 Entropiadisorgenticonmemoria . . . . . . . . . . . . . . . . . . . 101.3 Modellidelcanaleditrasmissione . . . . . . . . . . . . . . . . . . . . . . . 111.4 Informazionemutua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.5 Capacit`adicanale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.5.1 Entropia,informazionemutuaecapacit`anelcasocontinuo . . . . . 161.6 Teoremadellacodicadicanale . . . . . . . . . . . . . . . . . . . . . . . . 201.6.1 Maggiorazionedellaprobabilit`adierrore . . . . . . . . . . . . . . . 201.6.2 Canalisenzamemoria . . . . . . . . . . . . . . . . . . . . . . . . . 221.6.3 Esponentederrore . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.6.4 Considerazioninalisullacodicadicanale . . . . . . . . . . . . . 262 Introduzioneallacodica: codiciablocco 272.1 Codicadicanale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.1.1 Codicilineari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.1.2 CodicidiHamming . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.1.3 Matricegeneratriceediparit`a. . . . . . . . . . . . . . . . . . . . . 302.1.4 Sindrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31iiiiv INDICE2.1.5 Rappresentazionepolinomiale . . . . . . . . . . . . . . . . . . . . . 322.1.6 Decodicahardesoft . . . . . . . . . . . . . . . . . . . . . . . . . 332.1.7 Decodicaamassimaverosimiglianzaebitperbit. . . . . . . . . . 342.1.8 Codicigeneratiinmodocasuale . . . . . . . . . . . . . . . . . . . . 352.2 Codiciciclici. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392.2.1 CodiciBCH. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402.2.2 CodiciReed-Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . 402.2.3 Codicipererroriconcentratiapacchetti . . . . . . . . . . . . . . . 412.2.4 Codiciconcatenati . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.2.5 Codiciprodotto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.3 Prestazionideicodiciablocco . . . . . . . . . . . . . . . . . . . . . . . . . 433 Introduzioneallacodica: codiciconvoluzionali 453.1 Codiciconvoluzionali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.2 Decodicaamassimaverosimiglianza . . . . . . . . . . . . . . . . . . . . . 473.3 Codiciconvoluzionalirecursivisistematici . . . . . . . . . . . . . . . . . . . 503.4 Decodicabitperbit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513.5 Codiciconvoluzionalitail biting . . . . . . . . . . . . . . . . . . . . . . . . 523.6 Prestazionideicodiciconvoluzionali . . . . . . . . . . . . . . . . . . . . . . 534 Algebradeicampiniti 574.1 Campiniti(odiGalois) . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.1.1 Campiniticonunnumeroprimodielementi . . . . . . . . . . . . 584.1.2 Campiniticonunnumerodielementinonprimo . . . . . . . . . . 594.1.3 Rappresentazionedeglielementideicampiniti . . . . . . . . . . . 604.1.4 Elementiprimitivierappresentazioneesponenziale . . . . . . . . . 624.1.5 Calcolodiespressionialgebriche . . . . . . . . . . . . . . . . . . . . 634.1.6 Polinomiprimitivigeneratoridelcampo . . . . . . . . . . . . . . . 644.1.7 Sequenzepseudocasuali . . . . . . . . . . . . . . . . . . . . . . . . . 664.2 Propriet`aspecichedellalgebradeicampiniti . . . . . . . . . . . . . . . 684.2.1 RappresentazioniisomorfediGF(qm) . . . . . . . . . . . . . . . . . 714.2.2 RappresentazionediGF(2m)conaltrebasi . . . . . . . . . . . . . . 725 Codiciabloccoedecodicaalgebrica 75INDICE v5.1 TrasformatadiscretadiFourierneicampiniti . . . . . . . . . . . . . . . . 755.1.1 Denizionedellatrasformatadiscreta . . . . . . . . . . . . . . . . . 755.1.2 Propriet`adellatrasformatadiscreta. . . . . . . . . . . . . . . . . . 775.2 Codiciciclici. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785.2.1 Polinomiogeneratore . . . . . . . . . . . . . . . . . . . . . . . . . . 785.2.2 Polinomiodiparit`a . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.2.3 Codiceduale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.2.4 Strutturadelcodicatore . . . . . . . . . . . . . . . . . . . . . . . . 805.2.5 Modicazionideicodici(binari) . . . . . . . . . . . . . . . . . . . . 815.2.6 Alcunepropriet`adeicodiciciclici . . . . . . . . . . . . . . . . . . . 825.3 CodiciBCH. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825.3.1 CodiciBCHbinari . . . . . . . . . . . . . . . . . . . . . . . . . . . 835.3.2 CodicidiHamming . . . . . . . . . . . . . . . . . . . . . . . . . . . 845.3.3 CodiciBCHnonprimitivi . . . . . . . . . . . . . . . . . . . . . . . 845.3.4 CodiciBCHnonbinari . . . . . . . . . . . . . . . . . . . . . . . . . 845.4 CodiciReed-Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855.5 Decodicaalgebrica(codiciBCHeRS) . . . . . . . . . . . . . . . . . . . 865.5.1 Polinomiolocatoredeglierrori . . . . . . . . . . . . . . . . . . . . . 865.5.2 UnadimostrazionealternativadelBCHbound . . . . . . . . . . . . 885.5.3 Valutazionedeivalorideglierrori . . . . . . . . . . . . . . . . . . . 885.5.4 Alcuneconsiderazionipratiche. . . . . . . . . . . . . . . . . . . . . 905.5.5 Unsempliceesempio . . . . . . . . . . . . . . . . . . . . . . . . . . 915.6 Soluzionedellakeyequation . . . . . . . . . . . . . . . . . . . . . . . . . . 925.6.1 AlgoritmodiEuclide . . . . . . . . . . . . . . . . . . . . . . . . . . 925.6.2 AlgoritmodiBerlekamp-Massey . . . . . . . . . . . . . . . . . . . . 955.6.3 Possibilicontrollinalisullasoluzione . . . . . . . . . . . . . . . . . 975.6.4 Correzionedierroriecancellazioni . . . . . . . . . . . . . . . . . . 976 Complementisuicodiciablocco 996.1 Decodicaamassimaverosimiglianzadeicodiciablocco . . . . . . . . . . 996.2 TrasformatadiHadamard . . . . . . . . . . . . . . . . . . . . . . . . . . . 1006.3 TeoremadiMacWilliams. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1016.3.1 Esempi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1036.3.2 Distribuzioneapprossimatadeipesi . . . . . . . . . . . . . . . . . . 103vi INDICE6.3.3 DistribuzionedeipesideicodiciReed-Solomon. . . . . . . . . . . . 1046.3.4 Codicibinariutilizzaticomerivelatori . . . . . . . . . . . . . . . . 1056.3.5 Codiciutilizzaticomerivelatoriecorrettori . . . . . . . . . . . . . 1066.3.6 Probabilit`aderrorealluscitadeldecodicatore . . . . . . . . . . . 1076.4 AlgoritmodiHartmanneRudolph . . . . . . . . . . . . . . . . . . . . . . 1087 Turbocodici 1137.1 Decodicaiterativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1147.1.1 Concatenazioneparallela . . . . . . . . . . . . . . . . . . . . . . . . 1147.1.2 Concatenazioneserie . . . . . . . . . . . . . . . . . . . . . . . . . . 1157.2 Codicicomponentiepermutazione . . . . . . . . . . . . . . . . . . . . . . 1167.2.1 Perforazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1187.2.2 Concatenazionedipi` ucodici . . . . . . . . . . . . . . . . . . . . . . 1197.3 Convergenzadelladecodicaiterativa . . . . . . . . . . . . . . . . . . . . 1227.4 Prestazioniasintotichedeiturbocodici . . . . . . . . . . . . . . . . . . . . 1287.5 Altreapplicazionidellaelaborazioneiterativa . . . . . . . . . . . . . . . . 1288 Codicipercostellazionimultilivello 1318.1 Capacit`adellecostellazionimultilivello . . . . . . . . . . . . . . . . . . . . 1328.1.1 Esempidicapacit`adicostellazionimultilivello . . . . . . . . . . . . 1348.1.2 Demodulazionebitperbit . . . . . . . . . . . . . . . . . . . . . . . 1368.1.3 Bitinterleavedcodedmodulation. . . . . . . . . . . . . . . . . . . . 1388.2 Trelliscodedmodulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138Capitolo1Teoriadellinformazione1.1 IntroduzioneallateoriadellinformazioneLeprincipalidomandeacuid`arispostalateoriadellinformazionesonoleseguenti:data una sorgente che emette messaggi da inviare ad un destinatario, quale sia il modopi` u economico per rappresentare, con qualit`a pressata, linformazione da trasmettereodamemorizzaresuunqualchesupportosicodatouncanalenonideale, lacui uscitasiaunareplicadistorta(rumorosa)dellin-gresso,comesipossatrasmettereomemorizzarelinformazioneinmodoadabilePer entrambi i tipi di questioni si hanno almeno due aspetti da considerare: uno relativo alletecniche utilizzabili in pratica per codicare una sorgente e per trasmettere linformazione;laltro, pi` u teorico, su quali siano le migliori prestazioni ottenibili con vincoli pressati sullacomplessit`adellelaborazione: ilcasopi` usemplice,epi` uspessoconsiderato,`eaddiritturasenzavincolidicomplessit`a.Lateoriadellinformazionesi concentrasui limiti teorici alleprestazioni dellacodicadisorgenteedellatrasmissioneinpresenzadidisturbi. Tuttavialeindicazionichelateoriafornisce nonsonosolouno stimoloa ricercare metodipratici che siavvicininoalle miglioriprestazioni possibili, ma spesso danno anche utili suggerimenti per orientarsi nella ricerca.Iproblemipi` usempliciarontatidallateoriadellinformazionerelativamenteallacodicadi sorgenteriguardanolacodicasenzaperditadi informazione, ovveroinvertibilesenzaalcunadegradazione. Quandoadesempiosi comprimeunle di calcolatoresi pretendedi riottenerlosenzaalcunbit sbagliato. Quando...</p>