Codici random: differenze tra le versioni

Versione delle 20:23, 26 apr 2007

Versione attuale delle 19:52, 25 lug 2018

(9 versioni intermedie di 7 utenti non mostrate)

Riga 1:

{{F|matematica|febbraio 2013}}

I '''codici random''' sono stati definiti da [[Claude Shannon]] e sono attualmente di grande interesse nel campo della [[teoria dell'informazione]] grazie alle loro proprietà.

== Random EnsambleEnsemble ==

Esistono due differenti ensambleensemble di codici random: il ''random code ensambleensemble'' (RCE) ed il ''linear code ensambleensemble'' (LCE).

== RCE ==

Consideriamo una classe di codici di [[lunghezza]] n e [[rate]] r. Ogni possibile codice con queste caratteristiche avrà [[dimensione]] rn e [[cardinalità]] <math>m=2^{rn}</math>. Il random code ensambleensemble è costituito da tutti i codici aventi queste caratteristiche e tali per cui ognuno di essi abbia la medesima probabilità di realizzarsi. Ciò vuol dire che ognuno dei codici di questo insieme è costituito sezionando in blocchi di n bit una parola di nm bit che possono valere 0 o 1 con la stessa probabilità.

== LCE ==

Consideriamo una classe di [[codici lineari]] di [[lunghezza]] n e [[dimensione]] k. Ogni possibile codice con queste caratteristiche avrà [[rate]] r=k/n e [[cardinalità]] <math>m=2^{k}</math>. Ognuno di questi codici è generato da una differente [[matrice generatrice]] del [[codice (teoria dell'informazione)|codice]]. Il ''linear code ensambleensemble'' è costituito da tutte le [[matrici generatrici]] di tipo kxnk×n i cui elementi valgono 0 o 1 in modo equiprobabile. Ciò vuol dire che ognuno dei codici di questo insieme è costituito sezionando in blocchi di n bit una parola di <math>n*2\cdot2^k</math> bit che possono valere 0 o 1 con la stessa probabilità e disponendo tali parole sulle righe della matricmatrice generatrice. Data la casualità delle parole è evidente che alcune delle matrici del codice saranno singolari e non avranno dunque [[rango (algebra lineare)|rango]] massimo.

== TRC e TLC ==

Per codice tipico intendiamo una realizzazione non singolare del codice e tale per cui la probabilità dell'insieme dei codici caratterizzati dallo [[spettro delle lunghezze]] è maggiore della probabilità degli altri possibili insiemi costruiti con lo stesso criterio. Un typical random code è una realizzazione tipica del RCE e per bassi rate presenta un [[esponente di errore]] migliore dell'ensemble di cui fa parte e che si mantiene tra l'[[expurgated error exponent]] e gli esponenti di errore del RCE e del LCE, ma che converge dopo con l'esponente di errore del RCE e del LCE.

Un typical random code è una realizzazione tipica del RCE e per bassi rate presenta un [[esponente di errore]] migliore dell'ensamble di cui fa parte e che si mantiene tra l'[[expurgated error exponent]] e gli esponenti di errore del RCE e del LCE, ma che converge dopo con l'esponente di errore del RCE e del LCE.

Un tipycal linear code è una realizzazione tipica del LCE e consegue l'[[expurgated error exponent]] (esponente di errore epurato) che è considerato il migliore esponente di errore conseguibile, per poi ricongiungersi con il LCE e successivamente con lo [[sphere packing exponent]]. In termini di [[distanza minima]] si può dimostrare che i TLC conseguono risultati migliori dei TRC, poiché per un rate R i primi conseguono la [[distanza di Gilbert-Varshamov]] per il rate R mentre i secondi conseguono la [[distanza di Gilbert-Varshamov]] per il rate 2R.

In termini di [[distanza minima]] si può dimostrare che i TLC conseguono risultati migliori dei TRC, poiché per un rate R i primi conseguono la [[distanza di Gilbert-Varshamov]] per il rate R mentre i secondi conseguono la [[distanza di Gilbert-Varshamov]] per il rate 2R.

[[Categoria:Matematica dell'informazione e della comunicazione]]