Detekcija i korekcija grešaka

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. CS1 одржавање: Формат датума (веза)
  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, | log ⁡ ( | A X | ) {\displaystyle |\log(|{\mathcal {A}}_{X}|)} ” 
  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

  • Lin, Shu; Daniel J. Costello, Jr. (1983). Error Control Coding: Fundamentals and Applications. Prentice Hall. ISBN 0-13-283796-X. 
  • Soljanin, Emina; Liu, Ruoheng; Spasojevic, Predrag (2004). „Hybrid ARQ with Random Transmission Assignments”. Advances in network information theory. Providence, Rhode Island: American Mathematical Society. стр. 321—334. ISBN 0-8218-3467-3. Приступљено 18. 3. 2009.  also available as preprint.
  • Comroe, R.; D. Costello (jul 1984). „ARQ schemes for data transmission in mobile radio systems”. IEEE Journal on Selected Areas in Communications. 2 (4): 472—481. doi:10.1109/JSAC.1984.1146084. 
  • Davida, George I.; Sudhakar M. Reddy (septembar 1972). „Forward Error Correction with Decision Feedback”. Information and Control. 21 (2): 117—133. doi:10.1016/S0019-9958(72)90057-5. 
  • „Rate Matching & HARQ (WCDMA/HSDPA)”. Rate Matching & HARQ (WCDMA/HSDPA). [мртва веза]
  • Dahlman, Erik; Parkvall, Stefan; Sköld, Johan; Beming, Per (2008). 3G Evolution - HSPA and LTE for Mobile Broadband (2 изд.). Academic Press. стр. 119—123. ISBN 978-0-12-374538-5. 
  • Elwyn R. Berlekamp (2014), Algebraic Coding Theory, World Scientific Publishing (revised edition), ISBN 978-9-81463-589-9.
  • MacKay, David J. C.. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, . ISBN 0-521-64298-1.  Текст „year” игнорисан (помоћ); Текст „pages” игнорисан (помоћ); Недостаје или је празан параметар |title= (помоћ)
  • Vera Pless (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., ISBN 0-471-08684-3.
  • Randy Yates, A Coding Theory Tutorial.
  • Thorpe, S.J. (1990). Eckmiller, R.; Hartmann, G.; Hauske, G., ур. Parallel processing in neural systems and computers. North-Holland. ISBN 978-0-444-88390-2. Приступљено 30. 6. 2013. 
  • McGraw, Gary; Viega, John. „Make your software behave: Playing the numbers: How to cheat in online gambling.”. Архивирано из оригинала 2008-03-13. г. Приступљено 2007-07-02. 
  • „Determinism categories in the Mercury programming language”. Архивирано из оригинала 2012-07-03. г. Приступљено 2013-02-23. 
  • „Mercury predicate modes”. Архивирано из оригинала 2012-07-03. г. Приступљено 2013-02-25. 
  • Williams, Paul L.; Beer, Randall D. (2010). „Nonnegative Decomposition of Multivariate Information”. arXiv:1004.2515 Слободан приступ [cs.IT]. 
  • Gutknecht, A. J.; Wibral, M.; Makkeh, A. (2021). „Bits and pieces: Understanding information decomposition from part-whole relationships and formal logic”. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 477 (2251). Bibcode:2021RSPSA.47710110G. S2CID 221246282. arXiv:2008.09535 Слободан приступ. doi:10.1098/rspa.2021.0110. 
  • Reza, Fazlollah M. (1994) [1961]. An Introduction to Information Theory. New York: Dover [McGraw-Hill]. ISBN 0-486-68210-2. 
  • Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, Inc. ISBN 0-471-12845-7. 
  • Auffarth, B; Lopez-Sanchez, M.; Cerquides, J. (2010). „Comparison of Redundancy and Relevance Measures for Feature Selection in Tissue Classification of CT images”. Advances in Data Mining. Applications and Theoretical Aspects. Springer. стр. 248—262. CiteSeerX 10.1.1.170.1528 Слободан приступ. 

Spoljašnje veze

Detekcija i korekcija grešaka na Vikimedijinoj ostavi.
  • The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay
  • Compute parameters of linear codes Архивирано на сајту Wayback Machine (11. фебруар 2015)
  • ECC Page
  • SoftECC: A System for Software Memory Integrity Checking
  • A Tunable, Software-based DRAM Error Detection and Correction Library for HPC
  • Detection and Correction of Silent Data Corruption for Large-Scale High-Performance Computing
Normativna kontrola: Državne Уреди на Википодацима
  • Izrael
  • Sjedinjene Države