Tanner graf

I kodningsteorin är en Tanner-graf , uppkallad efter Michael Tanner, en tvådelad graf som används för att ange begränsningar eller ekvationer som anger felkorrigeringskoder . I kodningsteori används Tanner-grafer för att konstruera längre koder från mindre. Både kodare och avkodare använder dessa grafer i stor utsträckning.

Ursprung

Tanner-grafer föreslogs av Michael Tanner som ett sätt att skapa större felkorrigeringskoder från mindre med hjälp av rekursiva tekniker. Han generaliserade Elias tekniker för produktkoder.

Tanner diskuterade nedre gränser för koderna som erhållits från dessa grafer, oavsett de specifika egenskaperna hos koderna som användes för att konstruera större koder.

Tanner-grafer för linjära blockkoder

Tanner-grafer är uppdelade i subkodnoder och siffernoder. För linjära blockkoder betecknar subkodnoderna rader i paritetskontrollmatrisen H. Siffernoderna representerar kolumnerna i matrisen H. En kant ansluter en subkodnod till en siffernod om en post som inte är noll finns i skärningspunkten för motsvarande rad och kolumn.

Gränser bevisade av Tanner

Tanner bevisade följande gränser

Låt $R$ vara hastigheten för den resulterande linjära koden, låt graden av siffernoderna vara $m$ och graden av subkodnoderna vara $n$ . Om varje subkodnod är associerad med en linjär kod (n,k) med hastighet r = k/n, så begränsas kodens hastighet av

$R\geq 1-(1-r)m\,$

Beräkningskomplexitet för Tanner-grafbaserade metoder

Fördelen med dessa rekursiva tekniker är att de är beräkningsmässigt lätthanterliga. Kodningsalgoritmen för Tanner-grafer är extremt effektiv i praktiken, även om den inte garanteras konvergera förutom för cykelfria grafer, som är kända för att inte medge asymptotiskt bra koder.

Tillämpningar av Tanner-graf

Zemors avkodningsalgoritm , som är en rekursiv lågkomplexitetsmetod för kodkonstruktion, är baserad på Tanner-grafer.

Anteckningar

• Michael Tanners originalpapper
• Michael Tanners sida