Tornado-kode - Tornado code

I kodingsteorien er Tornado-koder en klasse slettingskoder som støtter feilretting . Tornado-koder krever konstant C mer overflødige blokker enn de mer dataeffektive slettekodene Reed – Solomon , men er mye raskere å generere og kan fikse slettinger raskere. Programvarebasert implementering av tornadokoder er omtrent 100 ganger raskere på små lengder og omtrent 10 000 ganger raskere på større lengder enn slettingskoder fra Reed – Solomon. Siden introduksjonen av Tornado-koder har det kommet mange andre lignende slettingskoder, spesielt Online-koder , LT-koder og Raptor-koder .

Tornado-koder bruker en lagvis tilnærming. Alle lag bortsett fra det siste bruker en LDPC feilkorrigeringskode, som er rask, men som har en sjanse for feil. Det endelige laget bruker en Reed – Solomon-korreksjonskode, som er tregere, men som er optimal når det gjelder gjenoppretting av feil. Tornado-koder dikterer hvor mange nivåer, hvor mange gjenopprettingsblokker i hvert nivå, og fordelingen som ble brukt til å generere blokker for de ikke-endelige lagene.

Oversikt

Inndataene er delt inn i blokker. Blokker er sekvenser av biter som alle har samme størrelse. Gjenopprettingsdata bruker samme blokkstørrelse som inndataene. Sletting av en blokk (inngang eller gjenoppretting) oppdages på noen annen måte. (For eksempel passerer en blokk fra disk ikke en CRC-sjekk eller en nettverkspakke med et gitt sekvensnummer kom aldri.)

Antall gjenopprettingsblokker er gitt av brukeren. Deretter bestemmes antall nivåer sammen med antall blokker i hvert nivå. Antallet i hvert nivå bestemmes av en faktor B som er mindre enn en. Hvis det er N-inngangsblokker, har det første gjenopprettingsnivået B * N-blokker, det andre har B * B * N, det tredje har B * B * B * N, og så videre.

Alle nivåer av utvinning unntatt den siste bruker en LDPC, som fungerer av xor (eksklusiv-eller). Xor opererer på binære verdier, 1s og 0s. A xor B er 1 hvis A og B har forskjellige verdier og 0 hvis A og B har samme verdier. Hvis du får resultat av (A xor B) og A, kan du bestemme verdien for B. (A xor B xor A = B) Tilsvarende, hvis du får resultat av (A x eller B), kan du bestemme verdien for A. Dette strekker seg til flere verdier, så gitt resultat av (A x eller B x eller C x eller D) og 3 av verdiene, kan den manglende verdien gjenopprettes.

Så gjenopprettingsblokkene i nivå 1 er bare xor til et sett med inngangsblokker. Tilsvarende er gjenopprettingsblokkene i nivå to hver xor for noen sett med blokker i nivå ett. Blokkene som brukes i xor velges tilfeldig, uten repetisjon. Imidlertid er antall blokker xor'ed for å lage en gjenopprettingsblokk valgt fra en veldig spesifikk fordeling for hvert nivå.

Siden xor er en rask operasjon og gjenopprettingsblokkene er en xor av bare en delmengde av blokkene i inngangen (eller på et lavere gjenopprettingsnivå), kan gjenopprettingsblokkene genereres raskt.

Det endelige nivået er en Reed – Solomon-kode. Reed-Solomon-koder er optimale når det gjelder å komme seg fra feil, men sakte å generere og gjenopprette. Siden hvert nivå har færre blokker enn det før, har Reed – Solomon-koden et lite antall gjenopprettingsblokker å generere og å bruke i gjenoppretting. Så selv om Reed – Solomon er treg, har den bare en liten mengde data å håndtere.

Under gjenoppretting gjenopprettes Reed – Solomon-koden først. Dette fungerer garantert hvis antall manglende blokker i neste til siste nivå er mindre enn de nåværende blokkene i siste nivå.

Når du går lavere, kan LDPC (xor) gjenopprettingsnivå brukes til å gjenopprette nivået under det med stor sannsynlighet hvis alle gjenopprettingsblokkene er tilstede og nivået under mangler høyst C 'færre blokker enn gjenopprettingsnivået. Algoritmen for gjenoppretting er å finne noen gjenopprettingsblokker som bare har ett av generatorsettet som mangler fra det lavere nivået. Da er xor til gjenopprettingsblokken med alle blokkene som er tilstede lik den manglende blokken.

Patentproblemer

Tornado-koder ble tidligere patentert i USA. Patent US6163870 A (arkivert 6. november 1997) og US 6081909 A (arkivert 6. november 1997) beskriver Tornado-koder, og har utløpt 6. november 2017. Patent US6307487 B1 (arkivert 5. februar 1999) og US6320520 B1 (arkivert 17. september 1999) nevner også Tornado-koder, og har utløpt henholdsvis 5. februar 2019 og 17. september 2019.

Sitater

Michael Luby opprettet Tornado-kodene.

Eksterne linker

En lesbar beskrivelse fra CMU (PostScript) [1] og en annen fra Luby ved International Computer Science Institute (PostScript) [2] .

Se også

Merknader

Referanser

  • M. Mitzenmacher (2004). "Digital Fountains: A Survey and Look Forward". Proc. 2004 IEEE Information Theory Workshop (ITW) .
  • M. Luby , M. Mitzenmacher , A. Shokrollahi , D. Spielman , V. Stemann (1997). "Praktiske tapsbestandige koder". Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing : 150–159. CS1 maint: flere navn: forfatterliste ( lenke )
  • M. Luby , M. Mitzenmacher , A. Shokrollahi (1998). "Analyse av tilfeldige prosesser via And-or Tree Evaluation". Proceedings of the 9.th ACM-SIAM Symposium on Discrete Algorithms : 364–373. CS1 maint: flere navn: forfatterliste ( lenke )