Earl of Tanner

Tanner-graafi on kaksiosainen graafi , jota käytetään rajoittamaan tiloja tai yhtäläisyyksiä, jotka määrittävät virheenkorjauskoodit . Koodausteoriassa Tanner - graafia on käytetty pidempien koodien rakentamiseen pienemmistä. Sekä enkooderit että dekooderit käyttävät paljon näitä kaavioita.

Nimetty Michael Tannerin mukaan.

Origins

Michael Tanner [1] ehdotti Tanner -kaavioita pidempien virheenkorjauskoodien luomiseksi pienemmistä koodeista rekursiivisia tekniikoita käyttäen. Hän tiivisti Peter Eliasin koodien johtamistekniikat.

Tanner käsitteli näistä kaavioista johdettujen koodien alarajoja riippumatta suurempien koodien rakentamiseen käytettyjen koodien erityisominaisuuksista.

Tanner-kaaviot rivilohkokoodeille

Tanner-kaaviot on jaettu alikoodisolmuihin ja merkkisolmuihin. Lineaarisille lohkokoodeille alikoodisolmut määrittelevät pariteettitarkistusmatriisin H rivit . Etumerkkisolmut edustavat matriisin H sarakkeita. Reuna yhdistää alikoodisolmun etumerkkisolmuun, jos siinä on nollasta poikkeava elementti. matriisi rivin ja sarakkeen leikkauskohdassa.

Tannerin todistamat rajat

Tanner osoitti seuraavat rajat.

Olkoon tuloksena olevan lineaarisen koodin nopeus [en], merkkisolmujen aste olkoon ja aste . Jos jokainen alikoodisolmu liittyy rivikoodiin (n,k), jonka nopeus on r = k/n, koodinopeus on rajoitettu

Tanner-graafiin perustuvien menetelmien laskennallinen monimutkaisuus

Näiden rekursiivisten tekniikoiden etuna on, että ne ovat laskentaystävällisiä. Tanner-graafien koodausalgoritmi on käytännössä äärimmäisen tehokas, vaikka se ei takaa konvergenssia, paitsi syklittömät graafit, jotka eivät tunnetusti anna asymptoottisesti hyviä koodeja [2] .

Count Tannerin sovellukset

Zemorin dekoodausalgoritmi , joka on vähän monimutkainen rekursiivinen lähestymistapa koodien rakentamiseen, perustuu Tanner-graafiin.

Harva matriisi koodille, jolla on alhainen pariteettitarkistustiheys, voidaan esittää Tanner-graafina, mikä mahdollistaa tällaisten graafien käytön tukitietorakenteena pariteettitarkistusmatriisialgoritmissa, joka tunnetaan nimellä Progressive Edge Growth [3] .

Muistiinpanot

  1. ↑ R. Michael Tanner Tietojenkäsittelytieteen professori, Kalifornian yliopiston tekniikan korkeakoulu, Santa Cruz Todistus Yhdysvaltain tekijänoikeusviraston edustajille 10. helmikuuta 1999 . Haettu 8. maaliskuuta 2019. Arkistoitu alkuperäisestä 8. toukokuuta 2017.
  2. ↑ Etzion, Trachtenberg, Vardy, 1998 .
  3. ↑ Xiao-Yu Hu, E. Eleftheriou, DM Arnold. Säännölliset ja epäsäännölliset progressiiviset reunankasvun tanner-kaaviot  // IEEE Transactions on Information Theory. - 2005-1. - T. 51 , no. 1 . — S. 386–398 . — ISSN 0018-9448 . - doi : 10.1109/TIT.2004.839541 . Arkistoitu alkuperäisestä 27. helmikuuta 2021.

Kirjallisuus