Tanner grafic - Tanner graph

În teoria codificării , un grafic Tanner , numit după Michael Tanner, este un grafic bipartit folosit pentru a stabili constrângerile sau ecuațiile care specifică codurile de corectare a erorilor . În teoria codificării , graficele Tanner sunt utilizate pentru a construi coduri mai lungi de la cele mai mici. Atât codificatorii cât și decodificatorii folosesc aceste grafice pe scară largă.

originile

Michael Tanner a propus graficele Tanner ca un mijloc de a crea coduri mai mari de corectare a erorilor de la cele mai mici, folosind tehnici recursive. El a generalizat tehnicile lui Elias pentru codurile de produse.

Tanner a discutat despre limitele inferioare ale codurilor obținute din aceste grafice indiferent de caracteristicile specifice ale codurilor care au fost utilizate pentru a construi coduri mai mari.

Grafice cu tancuri pentru coduri bloc liniare

Graficele Tanner sunt partiționate în noduri subcodice și noduri cifre. Pentru codurile de bloc liniare, nodurile subcodice indică rânduri ale matricei de verificare a parității H. Nodurile cifre reprezintă coloanele matricei H. O muchie conectează un nod subcod la un nod cifrat dacă există o intrare diferă în zero în intersecția corespunzătoare rând și coloană.

Obligatii dovedite de Tanner

Tanner a dovedit următoarele limite

Să fie rata codului liniar rezultat, să fie gradul de noduri cifre și gradul de noduri subcode . Dacă fiecare nod subcode este asociat cu un cod liniar (n, k) cu rata r = k / n, atunci rata codului este delimitată de ${\ displaystyle R}$${\ displaystyle m}$${\ displaystyle n}$

${\ displaystyle R \ geq 1- (1-r) m \,}$

Complexitatea computațională a metodelor bazate pe graficul Tanner

Avantajul acestor tehnici recursive este că acestea pot fi tratate prin calcul. Algoritmul de codare pentru graficele Tanner este extrem de eficient în practică, deși nu se garantează convergența cu excepția graficelor fără ciclu, despre care se știe că nu admite coduri bune asimptotic.

Aplicații ale graficului Tanner

Algoritmul de decodare al lui Zemor , care este o abordare recursivă de complexitate scăzută a construcției de coduri, se bazează pe graficele Tanner.

notițe

• Lucrarea originală a lui Michael Tanner
• Pagina lui Michael Tanner