Tanner graf - Tanner graph

I kodingsteori er en Tanner-graf , oppkalt etter Michael Tanner, en bipartitt-graf som brukes til å angi begrensninger eller ligninger som spesifiserer feilrettingskoder . I kodingsteori brukes garvergrafer for å konstruere lengre koder fra mindre. Både kodere og dekodere bruker disse grafene mye.

Origins

Tanner grafer ble foreslått av Michael Tanner som et middel til å lage større feilrettingskoder fra mindre ved å bruke rekursive teknikker. Han generaliserte teknikkene til Elias for produktkoder.

Tanner diskuterte lavere grenser for kodene oppnådd fra disse grafene uavhengig av de spesifikke egenskapene til kodene som ble brukt til å konstruere større koder.

Tanner grafer for lineære blokkkoder

Tanner grafer er delt inn i underkodeknuter og siffernoder. For lineære blokkkoder angir underkodeknuter radene for paritetskontrollmatrisen H. Siffernodene representerer kolonnene i matrisen H. En kant kobler en underkodeknode til en sifferknute hvis det eksisterer en ikke-null oppføring i skjæringspunktet til tilsvarende rad og kolonne.

Grenser bevist av Tanner

Tanner beviste følgende grenser

La være hastigheten på den resulterende lineære koden, la graden av sifferknutene være og graden av underkodeknuter . Hvis hver underkode-node er assosiert med en lineær kode (n, k) med frekvensen r = k / n, begrenses kodenes hastighet av ${\ displaystyle R}$${\ displaystyle m}$${\ displaystyle n}$

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

Beregningsmessig kompleksitet av Tanner-grafbaserte metoder

Fordelen med disse rekursive teknikkene er at de er beregningsdyktige. Kodingsalgoritmen for Tanner-grafer er ekstremt effektiv i praksis, selv om den ikke er garantert å konvergere med unntak av syklusfrie grafer, som er kjent for ikke å innrømme asymptotisk gode koder.

Bruksområder for Tanner-graf

Zemors avkodingsalgoritme , som er en rekursiv tilnærming med lav kompleksitet til kodekonstruksjon , er basert på Tanner-grafer.

Merknader

• Michael Tanners originale papir
• Michael Tanners side