Kod za ispravljanje grešaka

U računarstvu, telekomunikacijama, teoriji informacija i teoriji kodiranja, kod za ispravljanje grešaka, ili kod korigovanja grešaka (engl. error correcting code - ECC) koristi se za kontrolu grešaka u podacima preko nepouzdanih ili bučnih komunikacionih kanala.[1][2] Centralna ideja je da pošiljalac kodira poruku izlišnim informacijama u obliku ECC-a. Prekomernost omogućava primaocu da otkrije ograničeni broj grešaka koje se mogu pojaviti bilo gde u poruci i često da ih ispravi bez ponovnog prenosa. Američki matematičar Ričard Haming je bio pionir ovog polja tokom 1940-ih i izumeo je prvi kod za ispravljanje grešaka 1950: Hemingov (7,4) kod.[2]

ECC se razlikuje od otkrivanja grešaka jer se greške koje se nađu mogu ispraviti, a ne jednostavno otkriti. Prednost je u tome što sistem koji koristi ECC ne zahteva reverzni kanal da zahteva ponovni prenos podataka kada dođe do greške. Loša strana je što se fiksni trasnmisioni troškovi dodaju u poruku, što zahteva veću propusnu širinu kanala unapred. ECC se stoga primenjuje u situacijama kada su ponovni prenosi skupi ili nemogući, kao što su jednosmerne komunikacione veze i prilikom prenosa na više prijemnika u multikastu. Od ovakvog pristupa takođe imaju koristi i veze sa dugim kašnjenjem; u slučaju da satelit kruži oko Urana, ponovni prenos zbog grešaka može stvoriti kašnjenje od pet sati.

Korekcija grešaka unapred

U telekomunikacijama, teoriji informacija i teoriji kodiranja, ispravljanje grešaka unapred (engl. forward error correction - FEC) ili kodiranje kanala[3][4] je tehnika koja se koristi za kontrolu grešaka u prenosu podataka preko nepouzdanih ili bučnih komunikacionih kanala. Centralna ideja je da pošiljalac kodira poruku na redundantan način, najčešće koristeći ECC.

Izlišnost omogućava primaocu da otkrije ograničeni broj grešaka koje se mogu pojaviti bilo gde u poruci i često da ih ispravi bez ponovnog prenosa. FEC daje primaocu mogućnost ispravljanja grešaka bez potrebe za reverznim kanalom da bi se zahtevao ponovni prenos podataka, ali po ceni fiksnog, većeg propusnog opsega unapred. FEC se stoga primenjuje u situacijama kada su ponovni prenosi skupi ili nemogući, kao što su jednosmerne komunikacione veze i prilikom prenosa na više prijemnika u multikastu. FEC informacije se obično dodaju u uređaje za masovno skladištenje (magnetni, optički i SSD/fleš) kako bi se omogućio oporavak oštećenih podataka, široko se koristi u modemima, koristi se u sistemima u kojima je primarna memorija ECC memorija i u situacijama emitovanja gde prijemnik nema mogućnost da zahteva ponovni prenos ili gde bi to izazvalo značajno kašnjenje. Na primer, u slučaju da satelit kruži oko Urana, ponovni prenos zbog grešaka u dekodiranju može stvoriti kašnjenje od najmanje 5 sati.

FEC obrada u prijemniku može se primeniti na digitalni tok bita ili u demodulaciji digitalno modulisanog nosača. Za ovo drugo, FEC je sastavni deo početne analogno-digitalne konverzije u prijemniku. Viterbi dekoder primenjuje algoritam meke odluke za demodulaciju digitalnih podataka iz analognog signala oštećenog bukom. Mnogi FEC koderi takođe mogu da generišu signal stope greške u bitovima (engl. bit-error rate - BER) koji se može koristiti kao povratna informacija za fino podešavanje analogne prijemne elektronike.

Maksimalni udeo grešaka ili nedostajućih bitova koji se mogu ispraviti određen je dizajnom ECC-a, tako da su različiti kodovi za ispravljanje grešaka unapred pogodni za različite uslove. Generalno, jači kod indukuje veću suvišnost koju treba preneti koristeći raspoloživu propusnu širinu, što smanjuje efektivnu brzinu protoka, istovremeno poboljšavajući primljeni efektivni odnos signala i šuma. Teorema kodiranja bučnog kanala Kloda Šenona odgovara na pitanje koliko je propusnog opsega preostalo za komunikaciju podataka, pri čemu se koristi najefikasniji kod koji verovatnoću greške u dekodiranju svodi na nulu. Ovo uspostavlja granice teoretske maksimalne brzine prenosa informacija kanala sa određenim osnovnim nivoom šuma. Njegov dokaz nije konstruktivan, i stoga ne daje uvid u to kako da se izgradi kod za postizanje kapaciteta. Međutim, nakon više godina istraživanja, neki napredni FEC sistemi poput polarnog koda[4] postižu kapacitet Šenonovog kanala pod hipotezom o beskonačnoj dužini okvira.

Način rada

ECC se ostvaruje dodavanjem izlišnosti u transmitovane informacije koristeći algoritam. Izlišni bit može biti složena funkcija mnogih originalnih informacionih bitova. Originalne informacije mogu se ili ne moraju pojaviti doslovno u kodiranom izlazu; kodovi koji uključuju nemodifikovani ulaz u izlaz su sistematski, dok su oni koji to nisu nesistematski.

Pojednostavljeni primer ECC-a je prenos svakog bita podataka 3 puta, što je poznato kao (3,1) kod ponavljanja. Kroz bučni kanal, prijemnik može videti 8 verzija izlaza, pogledajte donju tabelu.

Triplet primljen Protumačen kao
000 0 (bez greške)
001 0
010 0
100 0
111 1 (bez greške)
110 1
101 1
011 1

Ovo omogućava ispravljanje greške u bilo kom od tri uzorka „većinskim glasanjem” ili „demokratskim glasanjem”. Sposobnost ispravljanja ovog ECC je:

  • Do 1 bita tripleta pri greški, ili
  • Do 2 bita iz tripleta izostavljena (slučajevi nisu prikazani u tabeli).

Iako je jednostavan za primenu i široko se koristi, ova trostruka modularna izlišnost je relativno neefikasan ECC. Bolji ECC kodovi obično ispituju poslednjih nekoliko desetina ili čak poslednjih nekoliko stotina prethodno primljenih bitova kako bi se utvrdilo kako da se dekodira trenutni mali set bitova (obično u grupama od 2 do 8 bitova).

Reference

  1. ^ Glover, Neal; Dudley, Trent (1990). Practical Error Correction Design For Engineers (Revision 1.1, 2nd изд.). CO, USA: Cirrus Logic. ISBN 0-927239-00-0. ISBN 978-0-927239-00-4. 
  2. ^ а б Hamming, R. W. (април 1950). „Error Detecting and Error Correcting Codes”. Bell System Technical Journal. USA: AT&T. 29 (2): 147—160. doi:10.1002/j.1538-7305.1950.tb00463.x. CS1 одржавање: Формат датума (веза)
  3. ^ Charles Wang; Dean Sklar; Diana Johnson (2001). „Forward Error-Correction Coding”. Crosslink. The Aerospace Corporation. 3 (1). Архивирано из оригинала 25. 2. 2012. г. Приступљено 5. 3. 2006. „How Forward Error-Correcting Codes Work” CS1 одржавање: Формат датума (веза)
  4. ^ а б Maunder, Robert (2016). „Overview of Channel Coding”. 

Literatura

  • Clark, Jr., George C.; Cain, J. Bibb (1981). Error-Correction Coding for Digital Communications. New York, USA: Plenum Press. ISBN 0-306-40615-2. ISBN 978-0-306-40615-7. 
  • Wicker, Stephen B. (1995). Error Control Systems for Digital Communication and Storage. Englewood Cliffs, NJ, USA: Prentice-Hall. ISBN 0-13-200809-2. ISBN 978-0-13-200809-9. 
  • Wilson, Stephen G. (1996). Digital Modulation and Coding. Englewood Cliffs, NJ, USA: Prentice-Hall. ISBN 0-13-210071-1. ISBN 978-0-13-210071-7. 
  • "Error Correction Code in Single Level Cell NAND Flash memories" 16 February 2007
  • "Error Correction Code in NAND Flash memories" 29 November 2004
  • Observations on Errors, Corrections, & Trust of Dependent Systems, by James Hamilton, 26 February 2012
  • Sphere Packings, Lattices and Groups, By J. H. Conway, N. J. A. Sloane, Springer Science & Business Media, 9 March 2013 – Mathematics – 682 pages.
  • J.H. van Lint (1992). Introduction to Coding Theory. GTM. 86 (2nd изд.). Springer-Verlag. стр. 31. ISBN 3-540-54894-7. 
  • F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting CodesНеопходна слободна регистрација. North-Holland. стр. 35. ISBN 0-444-85193-3. 
  • W. Huffman; V.Pless (2003). Fundamentals of error-correcting codesНеопходна слободна регистрација. Cambridge University Press. ISBN 978-0-521-78280-7. 
  • Charan Langton (2001) Coding Concepts and Block Coding
  • Francis, Michael. "Viterbi Decoder Block Decoding-Trellis Termination and Tail Biting." Xilinx XAPP551 v2. 0, DD (2005): 1-21.
  • Chen, Qingchun, Wai Ho Mow, and Pingzhi Fan. "Some new results on recursive convolutional codes and their applications." Information Theory Workshop, 2006. ITW'06 Chengdu. IEEE. IEEE, 2006.
  • Fiebig, U-C., and Patrick Robertson. "Soft-decision and erasure decoding in fast frequency-hopping systems with convolutional, turbo, and Reed-Solomon codes." IEEE Transactions on Communications 47.11 (1999): 1646-1654.
  • Bhaskar, Vidhyacharan, and Laurie L. Joiner. "Performance of punctured convolutional codes in asynchronous CDMA communications under perfect phase-tracking conditions." Computers & Electrical Engineering 30.8 (2004): 573-592.
  • Modestino, J., and Shou Mui. "Convolutional code performance in the Rician fading channel." IEEE Transactions on Communications 24.6 (1976): 592-606.
  • Chen, Yuh-Long, and Che-Ho Wei. "Performance evaluation of convolutional codes with MPSK on Rician fading channels." IEE Proceedings F-Communications, Radar and Signal Processing. Vol. 134. No. 2. IET, 1987.
  • G. D. Forney (1967). „Concatenated codes”. Cambridge, Massachusetts: MIT Press. 
  • Shu Lin; Daniel J. Costello Jr. (1983). Error Control Coding: Fundamentals and ApplicationsСлободан приступ ограничен дужином пробне верзије, иначе неопходна претплата. Prentice Hall. стр. 278–280. ISBN 978-0-13-283796-5. 
  • Forney, G. David (април 1966). „Generalized Minimum Distance Decoding”. IEEE Transactions on Information Theory. 12 (2): 125—131. doi:10.1109/TIT.1966.1053873. CS1 одржавање: Формат датума (веза)
  • Yu, Christopher C.H.; Costello, Daniel J. (март 1980). „Generalized Minimum Distance Decoding for Qary Output Channels”. IEEE Transactions on Information Theory. 26 (2): 238—243. doi:10.1109/TIT.1980.1056148. CS1 одржавање: Формат датума (веза)
  • Wu, Yingquan; Hadjicostis, Christoforos (јануар 2007). „Soft-Decision Decoding of Linear Block Codes Using Preprocessing and Diversification”. IEEE Transactions on Information Theory. 53 (1): 387—393. doi:10.1109/tit.2006.887478. CS1 одржавање: Формат датума (веза)
  • J. P. Odenwalder (1970). „Optimal decoding of convolutional codes”. U.C.L.A., Systems Science Dept. (dissertation). 
  • Robert J. McEliece; Laif Swanson (20. 8. 1993). „Reed–Solomon Codes and the Exploration of the Solar System”. JPL. CS1 одржавање: Формат датума (веза)
  • Robert G. Gallager (1963). Low Density Parity Check Codes (PDF). Monograph, M.I.T. Press. Приступљено 7. 8. 2013. CS1 одржавање: Формат датума (веза)
  • Tahir, B., Schwarz, S., & Rupp, M. (2017, May). BER comparison between Convolutional, Turbo, LDPC, and Polar codes. In 2017 24th International Conference on Telecommunications (ICT) (pp. 1-7). IEEE.
  • Moon Todd, K. Error correction coding: mathematical methods and algorithms. 2005 by John Wiley & Sons. ISBN 0-471-64800-0.
  • Andrews, Kenneth S., et al. "The development of turbo and LDPC codes for deep-space applications." Proceedings of the IEEE 95.11 (2007): 2142-2156.
  • Hassan, A.E.S., Dessouky, M., Abou Elazm, A. and Shokair, M., 2012. Evaluation of complexity versus performance for turbo code and LDPC under different code rates. Proc. SPACOMM, pp.93-98.

Spoljašnje veze

Kod za ispravljanje grešaka на Викимедијиној остави.
  • Morelos-Zaragoza, Robert (2004). „The Correcting Codes (ECC) Page”. Приступљено 2006-03-05. 
  • lpdec: library for LP decoding and related things (Python)
  • Introducing Low-Density Parity-Check Codes (by Sarah J Johnson, 2010) Архивирано на сајту Wayback Machine (7. новембар 2019)
  • LDPC Codes – a brief Tutorial (by Bernhard Leiner, 2005)
  • LDPC Codes (TU Wien) Архивирано на сајту Wayback Machine (28. фебруар 2019)
  • The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, discusses LDPC codes in Chapter 47.
  • -author= -