Codici random

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 Ensamble

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

RCE

Consideriamo una classe di codici di lunghezza n e rate r. Ogni possibile codice con queste caratteristiche avrà dimensione rn e cardinalità m = 2^rn. Il random code ensamble è 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à m = 2^k. Ognuno di questi codici è generato da una differente matrice generatrice del codice. Il linear code ensamble è costituito da tutte le matrici generatrici di tipo k×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 bit che possono valere 0 o 1 con la stessa probabilità e disponendo tali parole sulle righe della matrice generatrice. Data la casualità delle parole è evidente che alcune delle matrici del codice saranno singolari e non avranno dunque 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'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.