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[уреди | уреди извор]

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 (енгл. automatic repeat request, ARQ) i često se koristi na Internetu. Alternativni pristup kontroli greške je hibridni automatski ponovljeni zahtev (енгл. hybrid automatic repeat request, HARQ), koji je kombinacija ARQ i kodiranja ispravke grešaka.^[6]

Reference[уреди | уреди извор]

^ James Irvine; David Harle (2002). Data Communications and Networks. ISBN 9780471808725.
^ 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
^ Shannon, C.E. (1948), „A Mathematical Theory of Communication”, Bell System Technical Journal, p. 418, 27
^ Golay, Marcel J. E. (1949), „Notes on Digital Coding”, Proc.I.R.E. (I.E.E.E.), p. 657, 37
^ 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.
^ 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[уреди | уреди извор]

Shu Lin; Daniel J. Costello, Jr. (1983). Error Control Coding: Fundamentals and Applications. Prentice Hall. ISBN 0-13-283796-X.
Soljanin, Emina; Ruoheng Liu; Predrag Spasojevic (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, 2003. ISBN 0-521-64298-1
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.

Spoljašnje veze[уреди | уреди извор]

[1] James Irvine; David Harle (2002). Data Communications and Networks. ISBN 9780471808725.

[Thompson-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.

[1]

[2]

[3]

[4]

[5]

[6]