Coduri aleatorii

Codurile aleatorii au fost definite de Claude Shannon și sunt în prezent de mare interes în domeniul teoriei informației datorită proprietăților lor.

Ansamblu aleatoriu

Există două ansambluri de coduri aleatorii diferite: ansamblul de cod aleator (RCE) și ansamblul de cod liniar (LCE).

RCE

Să luăm în considerare o clasă de coduri de lungime n și rata r. Orice cod posibil cu aceste caracteristici va avea dimensiunea și cardinalitatea rn $m=2^{rn}$ ${\ displaystyle m = 2 ^ {rn}}$ ${\ displaystyle m = 2 ^ {rn}}$ . Ansamblul de coduri aleatorii este alcătuit din toate codurile care au aceste caracteristici și astfel încât fiecare dintre ele are aceeași probabilitate de a fi realizat. Aceasta înseamnă că fiecare dintre codurile acestui set este constituit prin secționarea unui cuvânt de nm biți în blocuri de n biți care pot fi 0 sau 1 cu aceeași probabilitate.

LCE

Să luăm în considerare o clasă de coduri liniare de lungime n și dimensiune k. Orice cod posibil cu aceste caracteristici va avea rata r = k / n și cardinalitate $m=2^{k}$ ${\ displaystyle m = 2 ^ {k}}$ ${\ displaystyle m = 2 ^ {k}}$ . Fiecare dintre aceste coduri este generat de o matrice de generare de cod diferită. Ansamblul de cod liniar este alcătuit din toate matricile generatoare de tip k × ni ale căror elemente valorează 0 sau 1 într-un mod la fel de probabil. Aceasta înseamnă că fiecare cod al acestui set este constituit prin secționarea unui cuvânt din blocuri de n biți $n\cdot 2^{k}$ ${\ displaystyle n \ cdot 2 ^ {k}}$ ${\ displaystyle n \ cdot 2 ^ {k}}$ biți care pot fi 0 sau 1 cu aceeași probabilitate și aranjând aceste cuvinte pe rândurile matricei generatoare. Având în vedere caracterul aleatoriu al cuvintelor, este evident că unele dintre matricile codului vor fi singulare și, prin urmare, nu vor avea rang maxim.

TRC și TLC

Prin cod tipic înțelegem o realizare non-singulară a codului și astfel încât probabilitatea setului de coduri caracterizate de spectrul de lungime este mai mare decât probabilitatea celorlalte seturi posibile construite cu același criteriu. Un cod aleatoriu tipic este o implementare tipică a RCE și pentru rate mici are un exponent de eroare mai bun decât ansamblul căruia îi aparține și care este păstrat între exponentul de eroare expurgat și exponenții de eroare ai RCE și LCE, dar care converge apoi cu exponentul de eroare al RCE și LCE.

Un cod liniar tipic este o realizare tipică a LCE și urmează exponentul de eroare expurgat care este considerat cel mai bun exponent de eroare realizabil, și apoi se reunește cu LCE și ulterior cu exponentul de împachetare a sferei . În ceea ce privește distanța minimă, se poate demonstra că TLC-urile obțin rezultate mai bune decât TRC-urile, deoarece pentru o rată R primele ating distanța Gilbert-Varshamov pentru rata R, în timp ce acestea din urmă ating distanța Gilbert-Varshamov pentru rata 2R.