Kasutaja:Alpha5463/Veakorrektsioon
Veatõrje või veaavastus ja -parandus on vahendid, mis võimaldavad digitaalsete andmete usaldusväärset edastamist ebausaldusväärsete sidekanalite kaudu. Paljudes sidekanalites esineb kanali müra ning seega võivad andmeedastusel allikast vastuvõtjani tekkida vead. Veaavastus meetodid võimaldavad selliseid vigu tuvastada, samas kui veaparandusega saab tihti algsed andmed taastada.
Definitsioonid[muuda | muuda lähteteksti]
Veaavastus on mürast või muudest häiretest põhjustatud vigade tuvastamine saatjalt vastuvõtjani toimuva edastamise ajal.
Veatõrje on vigade tuvastamine ehk veaavastus ning algsete vigadeta andmete taastamine ehk veaparandus.
Ajalugu[muuda | muuda lähteteksti]
Veatõrjekoodide tänapäevane areng sai alguse 1947. aastal tänu Richard Hammingule.[2] Hammingi koodi kirjeldus ilmus Claude Shannoni teoses "A Mathematical Theory of Communication"[3] ning peagi üldistas selle Marcel J. E. Golay.[4]
Sissejuhatus[muuda | muuda lähteteksti]
Kõik veaavastus- ja parandusskeemid lisavad sõnumile teataval määral liiasust (st lisaandmeid), mida vastuvõtjad saavad kasutada edastatud sõnumi järjepidevuse kontrollimiseks ja vigaste andmete taastamiseks. Veaavastus- ja parandusskeemid võivad olla kas süstemaatilised või mittesüstemaatilised. Süstemaatilise skeemi puhul saadab saatja algandmed ja lisab kindla arvu kontrollbitte (või paarsusandmed), mis tuletatakse andmebittidest mingi deterministliku algoritmiga . Kui on vaja ainult veaavastust, võib vastuvõtja lihtsalt rakendada vastuvõetud andmebittidele sama algoritmi ja võrrelda oma väljundit vastuvõetud kontrollbittidega; kui väärtused ei ühti, on edastamise ajal ilmnenud viga. Süsteemis, mis kasutab mittesüstemaatilist koodi, teisendatakse algne sõnum kodeeritud sõnumiks, mis kannab sama teavet ja millel on vähemalt sama palju bitte kui algsel sõnumil.
Veakontroll on tõhus, kui skeem valitakse vastavalt sidekanali omadustele. Levinud kanalimudelid hõlmavad mäluta mudeleid, kus vead ilmnevad juhuslikult ja teatud tõenäosusega, ja dünaamilisi mudeleid, kus vead esinevad peamiselt pursetena. Järelikult saab veaavastus- ja paranduskoode üldiselt eristada juhuslike vigade avastuse/paranduse ja veapursete avastuse/paranduse vahel. Mõned koodid võivad sobida ka mõlema nii juhuslike vigade kui ka veapursete jaoks.
Kui kanali omadusi ei ole võimalik kindlaks määrata või need on väga muutlikud, võib veaavastusskeemi kombineerida vigaste andmete uuesti edastamise süsteemiga. Seda nimetatakse automaatseks korduvpäringuks ja seda kasutatakse kõige enam Internetis. Alternatiivne lähenemisviis on hübriidautomaatne korduspäring, mis on automaatse korduvpäringu ja veaparanduskodeerimise kombinatsioon.
Veaparandus[muuda | muuda lähteteksti]
On olemas kolm peamist veaparanduse tüüpi.[5]
Automaatne korduvpäring[muuda | muuda lähteteksti]
Automaatne korduvpäring (inglise keeles automatic repeat request ehk ARQ) on andmeedastuse veakontrolli meetod, mis kasutab usaldusväärsuse tagamiseks veatuvastuskoode, kviteerimis- ja/või negatiivseid kviteerimissignaale ning päringu aegumisi. Kviteerimissignaal ehk kinnitus (inglise keeles acknowledgement ehk ACK) on teade, mille vastuvõtja saadab näitamaks, et ta on andmekaadri õigesti vastu võtnud.
Tavaliselt, kui saatja ei saa kinnitust enne päringu aegumist (st mõistliku aja jooksul pärast andmekaadri saatmist), saadab ta kaadri uuesti, kuni see on kas õigesti vastu võetud või viga püsib kauem kui eelnevalt määratud arvu kordussaadetisi.
Automaatne korduvpäring on asjakohane, kui sidekanalil on muutuv või tundmatu läbilaskevõime, nagu näiteks Internetis. Automaatne korduvpäring eeldab aga tagakanali olemasolu, põhjustab latentsusaeg pikenemist kordusedastuste tõttu ning nõuab kordusedastuste jaoks puhvrite ja taimerite säilitamist, mis võrgu ülekoormuse korral koormata serverit ja võrgu üldist läbilaskevõimet.[6]
Kanali kodeerimine[muuda | muuda lähteteksti]
Kanali kodeerimine ehk edasine veaparandus (inglise keeles channel coding ehk forward error correction või FEC) on protsess, mille käigus lisatakse sõnumile üleliigsed andmed, näiteks veatõrjekood (inglise keeles error-correcting code ECC), nii et vastuvõtja saab selle taastada isegi siis, kui on tekkinud hulk vigu (kuni kasutatava koodi võimekuse piires), kas edastamisel või salvestamisel. Kuna vastuvõtja ei pea saatjalt küsima andmete uuesti edastamist, ei ole kanali kodeerimisel tagasikanalit vaja. Veatõrjekoode kasutatakse madalama kihi suhtluses, nagu mobiilsidevõrk, kiire fiiberoptiline side ja Wi-Fi,[7][8], samuti usaldusväärseks salvestuseks andmekandjates, nagu välkmälu, kõvaketas ja RAM.[9]
Veaparanduskoodidel eristatakse tavaliselt konvolutsioonikoode ja plokkkoode:
- Konvolutsioonikoode töödeldakse bittide kaupa. Need sobivad eriti hästi riistavaraliseks rakendamiseks ja Viterbi dekooder võimaldab optimaalset dekodeerimist .
- Plokk-koode töödeldakse plokkide kaupa. Plokk-koodide varasemad näited on korduskoodid, Hammingi koodid ja mitmemõõtmelised paarsuskontrollkoodid . Neile järgnesid mitmed tõhusad koodid, millest Reed-Solomoni koodid on nende praeguse laialdase kasutamise tõttu kõige märkimisväärsemad. Turbokoodid ja madala tihedusega paarsuskontrollkoodid (low-density parity-check codes või LDPC inglise keeles) on suhteliselt uued lahendused, mis suudavad pakkuda peaaegu optimaalset tõhusust.
Shannoni teoreem on oluline teoreem kanali kodeerimises ning kirjeldab maksimaalset infokiirust, mille puhul on võimalik usaldusväärne side teatava veatõenäosuse või signaali-müra suhtega (signal-to-noise ratio ehk SNR inglise keeles) kanalil. Seda ranget ülempiiri väljendatakse kanali läbilaskevõimena. Täpsemalt öeldes ütleb teoreem, et on olemas sellised koodid, mille kodeerimispikkuse suurenemisel saab diskreetse mäluta kanali veatõenäosuse muuta suvaliselt väikeseks, tingimusel, et koodikiirus on väiksem kui kanali läbilaskevõime. Koodikiirus on defineeritud murdosa k/n k lähtesümbolist ja n kodeeritud sümbolist.
Tegelik maksimaalne lubatud koodikiirus sõltub kasutatavast veatõrjekoodist ja võib olla väiksem. Selle põhjuseks on asjaolu, et Shannoni tõestus oli ainult olemuslik ega näidanud, kuidas luua koode, mis on ühtaegu optimaalsed ja millel on tõhusad kodeerimis- ja dekodeerimisalgoritmid.
Hübriidskeemid[muuda | muuda lähteteksti]
Hübriid automaatne korduvpäring on automaatse korduvpäringu ja kanali kodeerimise kooslus. On kaks peamist lähenemisviisi: [6]
- Sõnumid edastatakse alati koos kanalikodeeringu paarsusandmetega (ja veaavastus liiasusega). Vastuvõtja dekodeerib sõnumi paarsusandmete abil ja taotleb korduvpäringut ainult siis, kui paarsusandmetest ei olnud edukaks dekodeerimiseks piisavad (tuvastatud ebaõnnestunud terviklikkuse kontrolli kaudu).
- Sõnumid edastatakse ilma paarsusandmeteta (ainult koos veaavastus teabega). Kui vastuvõtja tuvastab vea, küsib ta saatjalt veaparandus teavet, kasutades korduvpäringut, ja kasutab seda algse sõnumi taastamiseks.
Veaavastus[muuda | muuda lähteteksti]
Kõige sagedamini kasutatakse vigade tuvastamiseks sobivat räsifunktsiooni (või täpsemalt kontrollsumma, tsüklilise liiasuse kontrolli või muud algoritmi). Räsifunktsioon lisab sõnumile fikseeritud pikkusega sildi, mis võimaldab vastuvõtjatel edastatud sõnumit kontrollida, arvutades sildi ümber ja võrreldes seda esitatud sildiga.
Korduskoodid[muuda | muuda lähteteksti]
Korduskood on kodeerimisskeem, mis saadab samu bitte mitu korda, et saavutada veavaba side. Edastatavad andmed jagatakse bitide plokkideks, mida saadetakse eelnevalt kindlaks määratud kordi. Näiteks bitimustri "1011" saatmiseks võib neljabitist plokki korrata kolm korda, saades seega signaali "1011 1011 1011". Kui see kaheteistkümnebitine muster on kätte saadud kui "1010 1011 1011" – kus esimene plokk erineb kahest teisest – on toimunud viga.
Korduskood on väga ebatõhus ja võib põhjustada probleeme, kui viga esineb iga grupi jaoks täpselt samas kohas (nt "1010 1010 1010" eelmises näites tunnistatakse õigeks). Korduskoodide eeliseks on see, et need on äärmiselt lihtsad ja neid kasutatakse tegelikult mõnes numbrijaama edastuses.[10][11]
Paarsuskontroll[muuda | muuda lähteteksti]
Paarsuskontrollis lisatakse lähtebittidele paarsusbitt, et tagada, et seatud bittide (st väärtusega 1 bittide) arv lõpptulemuses on paaris või paaritu. Paarsuskontroll on väga lihtne, kuid seda saab kasutada ainult üksikute või mõne muu paaritu arvu (st kolm, viis jne) vigade tuvastamiseks, sest paarisarv ümberpööratud bitte muudab paarsusbiti õigeks, isegi siis kui andmed on valed.
Kontrollsumma[muuda | muuda lähteteksti]
Sõnumi kontrollsumma on kindla sõnapikkusega sõnumi koodisõnade (nt baidiväärtuste) modulaararitmeetiline summa. Summa võib enne edastamist eitada pöördkoodiks, et tuvastada tahtmatud null-sõnumid.
Rakendused[muuda | muuda lähteteksti]
Rakendused, mis nõuavad madalat latentsust (nt telefonivestlused), ei saa kasutada automaatset korduvpäringut; nad peavad kasutama kanali kodeerimist. Selleks ajaks, kui korduvpäringuga viga avastatakse ja see uuesti edastatakse, saabuvad uued andmed liiga hilja, et neid saaks kasutada.
Rakendused, kus saatja unustab teabe kohe pärast selle saatmist (nt enamik telekaameraid), ei saa korduvpäringuid saata; nad peavad kanali kodeerima, sest kui tekib viga, ei ole algandmed enam kättesaadavad.
Korduvpäringuid saatvatel rakendustel peab olema tagakanal; rakendused, millel pole tagakanalit, ei saa seda kasutada.
Rakendused, mis nõuavad äärmiselt madalat veamäära (näiteks digitaalsed rahaülekanded), peavad kasutama automaatset korduvpäringut, kuna kanali kodeerimise puhul on võimalik, et vigu ei saa parandada.
Internet[muuda | muuda lähteteksti]
Tüüpilises TCP/IP-pinus kontrollitakse vead mitmel tasandil:
- Iga Etherneti kaader kasutab CRC-32 veatuvastust. Vastuvõtja riistvara loobub tuvastatud vigadega raamid.
- IPv4 päis sisaldab kontrollsummat, mis kaitseb päise sisu. Vale kontrollsummaga paketid loobutakse võrgus või vastuvõtja juures.
- Kontrollsumma jäeti IPv6 päisest välja, et vähendada töötlemiskulusid võrgu marsruutimises ja kuna eeldatakse, et praegune linkkihi tehnoloogia tagab piisava veatuvastuse (vt ka RFC 3819 ).
- UDP -l on valikuline kontrollsumma, mis katab kasuliku koormuse ja aadressiinformatsiooni UDP ja IP päises. Võrgupinu loobub vigase kontrollsummaga pakettidest. Kontrollsumma ei ole IPv4 puhul kohustuslik, aga IPv6 nõuab seda. Kui see on välja jäetud, eeldatakse, et andmelingi kiht tagab soovitud veakaitse taseme.
- TCP tagab TCP- ja IP-päistes sisalduva kasuliku koormuse ja adresseerimisteabe kaitsmiseks kontrollsummat. Võrgupinu loobub vale kontrollsummaga pakettidest ja lõpuks saadetakse need uuesti automaatse korduvpäringuga, kas otseselt (nt. kolmepoolse käepigistuse kaudu) või kaudselt päringu aegumise tõttu.
Vaata ka[muuda | muuda lähteteksti]
Viited[muuda | muuda lähteteksti]
- ↑ Xiaoli Sun, NASA Goddard. "NASA Beams Mona Lisa at the Moon" (inglise). Vaadatud 17.10.2022.
- ↑ Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), The Mathematical Association of America, lk vii, ISBN 0-88385-023-0
- ↑ Shannon, C.E. (1948), "A Mathematical Theory of Communication", Bell System Technical Journal, 27 (3): 379–423, DOI:10.1002/j.1538-7305.1948.tb01338.x, PMID 9230594
- ↑ Golay, Marcel J. E. (1949), "Notes on Digital Coding", Proc.I.R.E. (I.E.E.E.), 37: 657
- ↑ Gupta, Vikas; Verma, Chanderkant (november 2012). "Error Detection and Correction: An Introduction". International Journal of Advanced Research in Computer Science and Software Engineering. 2 (11).
- ↑ 6,0 6,1 A. J. McAuley, Reliable Broadband Communication Using a Burst Erasure Correcting Code, ACM SIGCOMM, 1990.
- ↑ Shah, Pradeep M.; Vyavahare, Prakash D.; Jain, Anjana (september 2015). "Modern error correcting codes for 4G and beyond: Turbo codes and LDPC codes". 2015 Radio and Antenna Days of the Indian Ocean (RADIO): 1–2. DOI:10.1109/RADIO.2015.7323369. ISBN 978-9-9903-7339-4. Vaadatud 22. mail 2022.
- ↑ "IEEE SA - IEEE 802.11ac-2013". IEEE Standards Association (inglise).
- ↑ "Transition to Advanced Format 4K Sector Hard Drives | Seagate US". Seagate.com (Ameerika inglise). Vaadatud 22. mail 2022.
- ↑ Frank van Gerwen. "Numbers (and other mysterious) stations". Vaadatud 12. märtsil 2012.
- ↑ Gary Cutlack (25. august 2010). "Mysterious Russian 'Numbers Station' Changes Broadcast After 20 Years". Gizmodo. Vaadatud 12. märtsil 2012.
Välislingid[muuda | muuda lähteteksti]
- ECC Page - populaarsete veaparanduskoodide kodeerimis- ja dekodeerimisprogrammid