Detekcija i korekcija grešaka

(преусмерено са Error detection and correction)

U teoriji informacija i kodiranja sa primenama u računarskoj nauci i telekomunikacijama, detekcija i korekcija grešaka ili kontrola grešaka su tehnike koje omogućavaju pouzdanu isporuku digitalnih podataka preko nepouzdanih komunikacionih kanala. Mnogi kanali komunikacije su podložni buci kanala i tako se mogu uvesti greške tokom prenosa sa izvora na prijemnik. Tehnike detekcije grešaka omogućavaju otkrivanje takvih grešaka, dok ispravljanje grešaka omogućava rekonstrukciju originalnih podataka u mnogim slučajevima.[1]

DefinicijeУреди

Detekcija greške je otkrivanje grešaka izazvanih bukom ili drugim pogoršanjima tokom prenosa sa predajnika na prijemnik. Korekcija grešaka je detekcija grešaka i rekonstrukcija originalnih podataka bez grešaka.

IstorijaУреди

Zasluge za savremeni razvoj kodova za ispravljanje grešaka se pridaju Ričardu Hemingu zbog njegovih doprinosa iz 1947. godine.[2] Opis Hemingovog koda objavljen je u „Matematičkoj teoriji komunikacije” Kloda Šenona[3] i ubrzo nakon toga ga je generalizovao Marsel Golaj.[4]

UvodУреди

Sve šeme otkrivanja i ispravljanja grešaka dodaju redandantnost (tj. neke dodatne podatke) u poruku, koje primaoci mogu koristiti da provere konzistentnost isporučene poruke i da povrate podatke za koje je utvrđeno da su oštećeni. Sheme otkrivanja i ispravljanja grešaka mogu biti sistematske ili nesistematične. U sistematskoj shemi, pošiljalac šalje originalne podatke i dodaje fiksni broj kontrolnih bitova (ili paritetnih podataka) koji su izvedeni iz bitova podataka nekim determiniranim algoritmom. Ako je potrebno samo otkrivanje grešaka, primalac može jednostavno da primeni isti algoritam na primljene bitove podataka i uporedi svoj izlaz sa primljenim kontrolnim bitovima; ako se vrednosti ne podudaraju, došlo je do greške u nekom trenutku tokom prenosa. U sistemu koji koristi nesistematični kod, originalna poruka se transformiše u šifriranu poruku koja sadrži iste informacije i koja ima najmanje onoliko bitova koliko i izvorna poruka.

Dobre performanse kontrole grešaka zahtevaju da se shema odabere na osnovu karakteristika kanala komunikacije. Uobičajeni modeli kanala uključuju modele bez pamćenja kod kojih se greške događaju nasumično i sa određenom verovatnoćom, i dinamičke modele gde se greške javljaju prvenstveno u naletima. Shodno tome, kodovi za otkrivanje i ispravljanje grešaka mogu se generalno razlikovati između otkrivanja/ispravljanja slučajnih grešaka i detekcije/ispravke naleta grešaka. Neki kodovi takođe mogu biti pogodni za mešavinu slučajnih grešaka i naleta grešaka.

Ako se karakteristike kanala ne mogu odrediti ili su veoma promenljive, shema otkrivanja grešaka može se kombinovati sa sistemom za ponovni prenos podataka koji nisu pravilno preneti.[5] Ovo je poznato kao automatsko ponavljanje zahteva (engl. automatic repeat request, ARQ) i često se koristi na Internetu. Alternativni pristup kontroli greške je hibridni automatski ponovljeni zahtev (engl. hybrid automatic repeat request, HARQ), koji je kombinacija ARQ i kodiranja ispravke grešaka.[6]

ReferenceУреди

  1. ^ James Irvine; David Harle (2002). Data Communications and Networks. ISBN 9780471808725. 
  2. ^ Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), The Mathematical Association of America, стр. vii, ISBN 0-88385-023-0 
  3. ^ Shannon, C.E. (1948), „A Mathematical Theory of Communication”, Bell System Technical Journal, p. 418, 27 
  4. ^ Golay, Marcel J. E. (1949), „Notes on Digital Coding”, Proc.I.R.E. (I.E.E.E.), p. 657, 37 
  5. ^ Gupta, Vikas; Verma, Chanderkant (novembar 2012). „Error Detection and Correction: An Introduction” (PDF). International Journal of Advanced Research in Computer Science and Software Engineering. 2 (11). Архивирано из оригинала (PDF) на датум 21. 08. 2019. Приступљено 21. 8. 2019. 
  6. ^ Frenger, P.; S. Parkvall; E. Dahlman (oktobar 2001). „Performance comparison of HARQ with Chase combining and incremental redundancy for HSDPA”. Vehicular Technology Conference, 2001. VTC 2001 Fall. IEEE VTS 54th. 3. Piscataway Township, New Jersey: IEEE Operations Center. стр. 1829—1833. ISBN 0-7803-7005-8. doi:10.1109/VTC.2001.956516. 

LiteraturaУреди

Spoljašnje vezeУреди