Contele de Tanner

Graficul Tanner este un grafic bipartit utilizat pentru a constrânge stările sau egalitățile care definesc codurile de corectare a erorilor . În teoria codificării, graficele Tanner au fost folosite pentru a construi coduri mai lungi din altele mai mici. Atât codificatoarele, cât și decodificatoarele folosesc intens aceste grafice.

Numit după Michael Tanner.

Origini

Graficele Tanner au fost propuse de Michael Tanner [1] pentru a genera coduri mai lungi de corectare a erorilor din coduri mai mici folosind tehnici recursive. El a rezumat tehnicile lui Peter Elias pentru derivarea codurilor.

Tanner a discutat limitele inferioare ale codurilor derivate din aceste grafice, indiferent de caracteristicile specifice ale codurilor care au fost folosite pentru a construi coduri mai mari.

Grafice Tanner pentru coduri de bloc de linii

Graficele Tanner sunt împărțite în noduri de subcod și noduri de semn. Pentru codurile de bloc liniare, nodurile de subcod definesc rândurile matricei de verificare a parității H. Nodurile de semn reprezintă coloanele matricei H. O muchie conectează nodul de subcod cu nodul de semn dacă există un element diferit de zero în matrice la intersecția rândului și coloanei.

Limite dovedite de Tanner

Tanner a demonstrat următoarele limite.

Fie viteza codului liniar rezultat, fie gradul nodurilor semn , iar gradul nodurilor subcodului fie . Dacă fiecare nod de subcod este asociat cu un cod de linie (n,k) cu rata r = k/n, atunci rata de cod este delimitată de

Complexitatea computațională a metodelor bazate pe graficul Tanner

Avantajul acestor tehnici recursive este că sunt prietenoase din punct de vedere computațional. Algoritmul de codare pentru graficele Tanner este extrem de eficient în practică, deși nu garantează convergența, cu excepția graficelor fără ciclu, despre care se știe că nu dau coduri asimptotic bune [2] .

Aplicații ale contelui Tanner

Algoritmul de decodare al lui Zemor , care este o abordare recursivă de complexitate redusă pentru construirea codurilor, se bazează pe graficele Tanner.

O matrice rară pentru cod cu o densitate scăzută a verificărilor de paritate poate fi reprezentată ca un grafic Tanner, care permite ca astfel de grafice să fie utilizate ca o structură de date suport în algoritmul matricei de verificare a parității cunoscut sub numele de Progressive Edge Growth [3] .

Note

  1. ↑ R. Michael Tanner Profesor de informatică, Școala de Inginerie Universitatea din California, Santa Cruz Mărturie în fața reprezentanților Biroului pentru Drepturi de Autor din Statele Unite, 10 februarie 1999 . Preluat la 8 martie 2019. Arhivat din original la 8 mai 2017.
  2. ↑ Etzion, Trachtenberg, Vardy, 1998 .
  3. ↑ Xiao-Yu Hu, E. Eleftheriou, DM Arnold. Grafice de bronzare regulate și neregulate cu creștere progresivă a marginilor  // IEEE Transactions on Information Theory. — 2005-1. - T. 51 , nr. 1 . — S. 386–398 . — ISSN 0018-9448 . - doi : 10.1109/TIT.2004.839541 . Arhivat din original pe 27 februarie 2021.

Literatură