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 уреди

U klasičnoj antici, prepisivači hebrejske Biblije su bili plaćeni za svoj rad prema broju stihova (redova stiha). Kako su prozne knjige Biblije retko kada su bile pisane štihovima, prepisivači su, da bi procenili obim posla, morali da prebroje slova.[2] Ovo je takođe pomoglo da se obezbedi tačnost u prenosu teksta uz izradu narednih kopija.[3][4] Između 7. i 10. veka nove ere, grupa jevrejskih pisara je formalizovala i proširila ovo da bi stvorila numeričku masoru kako bi se obezbedila tačna reprodukcija svetog teksta. To je uključivalo prebrojavanje broja reči u redu, odeljku, knjizi i grupama knjiga, beležeći središnji šav knjige, statistiku upotrebe reči i komentare.[2] Standardi su postali takvi da se odstupanje čak i u jednom slovu u svitku Tore smatralo neprihvatljivim.[5] Efikasnost njihovog metoda ispravljanja grešaka je potvrđena preciznošću kopiranja kroz vekove, što je pokazano otkrićem svitaka sa Mrtvog mora 1947–1956, koji datiraju iz oko 150. pre nove ere - 75. godine.[6]

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

Principi уреди

Sve šeme otkrivanja i ispravljanja grešaka dodaju redandantnost[10] (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.[11][12][13][14][15][16] 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.[17] 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.[18]

Reference уреди

  1. ^ Irvine, James; Harle, David (2002). Data Communications and Networks. ISBN 9780471808725. 
  2. ^ а б „Masorah”. Jewish Encyclopedia. 
  3. ^ Pratico, Gary D.; Pelt, Miles V. Van (2009). Basics of Biblical Hebrew Grammar: Second Edition. Zondervan. ISBN 978-0-310-55882-8. 
  4. ^ Mounce, William D. (2007). Greek for the Rest of Us: Using Greek Tools Without Mastering Biblical Languages. Zondervan. стр. 289. ISBN 978-0-310-28289-1. 
  5. ^ Mishneh Torah, Tefillin, Mezuzah, and Sefer Torah, 1:2. Example English translation: Touger, Eliyahu. The Rambam's Mishneh Torah. Moznaim Publishing Corporation. 
  6. ^ Brian M. Fagan (5. 12. 1996). „Dead Sea Scrolls”. The Oxford Companion to Archaeology. Oxford University Press. ISBN 0195076184. 
  7. ^ 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 
  8. ^ Shannon, C.E. (1948), „A Mathematical Theory of Communication”, Bell System Technical Journal, p. 418, 27 
  9. ^ Golay, Marcel J. E. (1949), „Notes on Digital Coding”, Proc.I.R.E. (I.E.E.E.), p. 657, 37 
  10. ^ MacKay, David J.C. (2003). „2.4 Definition of entropy and related functions”. Information Theory, Inference, and Learning Algorithms. Cambridge University Press. стр. 33. ISBN 0-521-64298-1. „The redundancy measures the fractional difference between H(X) and its maximum possible value,   
  11. ^ Edward A. Lee. „The Problem with Threads” (PDF). Приступљено 2009-05-29. 
  12. ^ Bocchino Jr., Robert L.; Adve, Vikram S.; Adve, Sarita V.; Snir, Marc (2009). Parallel Programming Must Be Deterministic by Default. USENIX Workshop on Hot Topics in Parallelism. 
  13. ^ „Intel Parallel Inspector Thread Checker”. Приступљено 2009-05-29. 
  14. ^ Lin, Yuan. „Data Race and Deadlock Detection with Sun Studio Thread Analyzer” (PDF). Приступљено 2009-05-29. 
  15. ^ Intel. „Intel Parallel Inspector”. Приступљено 2009-05-29. 
  16. ^ Worthington, David. „Intel addresses development life cycle with Parallel Studio”. Архивирано из оригинала 2009-05-28. г. Приступљено 2009-05-26. 
  17. ^ 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. 
  18. ^ 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 уреди