Earl av Tanner

Tanner-grafen är en tvådelad graf som används för att begränsa tillstånd eller likheter som definierar felkorrigeringskoder . I kodningsteorin har Tanner-grafer använts för att konstruera längre koder från mindre. Både kodare och avkodare använder sig mycket av dessa grafer.

Uppkallad efter Michael Tanner.

Origins

Tanner-grafer föreslogs av Michael Tanner [1] för att generera längre felkorrigerande koder från mindre koder med hjälp av rekursiva tekniker. Han sammanfattade Peter Elias tekniker för att härleda koder.

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

Tanner-grafer för linjeblockkoder

Tanner-grafer är uppdelade i subkodnoder och teckennoder. För linjära blockkoder definierar subkodnoderna raderna i paritetskontrollmatrisen H. Teckennoderna representerar kolumnerna i matrisen H. En kant förbinder subkodnoden med teckennoden om det finns ett element som inte är noll i matris i skärningspunkten mellan raden och kolumnen.

Gränser bevisade av Tanner

Tanner bevisade följande gränser.

Låt vara hastigheten den resulterande linjära koden, låt graden av teckennoder vara , och låt graden av subkodnoder vara . Om varje underkodsnod är associerad med en linjekod (n,k) med hastighet r = k/n, så begränsas kodhastigheten av

Beräkningskomplexitet för metoder baserade på Tanner-grafen

Fördelen med dessa rekursiva tekniker är att de är beräkningsvänliga. Kodningsalgoritmen för Tanner-grafer är extremt effektiv i praktiken, även om den inte garanterar konvergens, förutom för cykellösa grafer, som är kända för att inte ge asymptotiskt bra koder [2] .

Tillämpningar av Count Tanner

Zemors avkodningsalgoritm , som är en rekursiv metod med låg komplexitet för att konstruera koder, är baserad på Tanner-grafer.

En gles matris för kod med en låg täthet av paritetskontroller kan representeras som en Tanner-graf, vilket gör att sådana grafer kan användas som en stöddatastruktur i paritetskontrollmatrisalgoritmen känd som Progressive Edge Growth [3] .

Anteckningar

  1. ↑ R. Michael Tanner Professor i datavetenskap, School of Engineering University of California, Santa Cruz . Hämtad 8 mars 2019. Arkiverad från originalet 8 maj 2017.
  2. ↑ Etzion, Trachtenberg, Vardy, 1998 .
  3. ↑ Xiao-Yu Hu, E. Eleftheriou, DM Arnold. Regelbundna och oregelbundna progressiva kant-tillväxt tanner grafer  // IEEE Transactions on Information Theory. — 2005-1. - T. 51 , nej. 1 . — S. 386–398 . — ISSN 0018-9448 . - doi : 10.1109/TIT.2004.839541 . Arkiverad från originalet den 27 februari 2021.

Litteratur