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).
Usrednjavanje buke za redukciju grešaka
[уреди | уреди извор]Moglo bi se reći da ECC radi tako što „usrednjava šum“; pošto svaki bit podataka utiče na mnoge prenete simbole, oštećenje nekih simbola šumom obično omogućava da se originalni korisnički podaci ekstrahuju iz drugih, neoštećenih primljenih simbola koji takođe zavise od istih korisničkih podataka.
- Zbog ovog efekta „udruženja rizika“, digitalni komunikacioni sistemi koji koriste ECC imaju tendenciju da rade znatno iznad određenog minimalnog odnosa signal-šum, a ne ispod njega.
- Ova tendencija sve ili ništa – efekat litice – postaje sve izraženija kako se koriste jači kodovi koji se bliže približavaju teorijskoj Šenonovoj granici.
- Preplitanje ECC kodiranih podataka može redukovat svojstva „sve ili ništa” prenetih ECC kodova kada se greške kanala obično javljaju u rafalima. Međutim, ovaj metod ima ograničenja; najbolje se koristi na uskopojasnim podacima.
Većina telekomunikacionih sistema koristi fiksni kanalski kod dizajniran da toleriše očekivanu stopu bitne greške u najgorem slučaju, a zatim uopšte ne funkcionišu ako je stopa grešaka u bitovima još gora. Međutim, neki sistemi se prilagođavaju datim uslovima greške kanala: neki slučajevi hibridnog automatskog zahteva za ponavljanje koriste fiksni ECC metod sve dok ECC može da obradi stopu greške, a zatim se prebacuje na ARQ kada stopa greške postane previsoka; adaptivna modulacija i kodiranje koristi različite ECC brzine, dodajući više bitova za ispravljanje grešaka po paketu kada postoje veće stope grešaka u kanalu, ili ih uklanjaju kada nisu potrebne.
Tipovi
[уреди | уреди извор]
Dve glavne kategorije ECC kodova su blok kodovi i konvolucijski kodovi.
- Blok kodovi rade na blokovima (paketima) fiksne veličine bitova ili simbola unapred-određene veličine. Praktični blok kodovi se generalno mogu teško dekodirati u polinomskom vremenu do njihove dužine bloka.
- Konvolucijski kodovi rade na tokovima bitova ili simbola proizvoljne dužine. Oni se najčešće meko dekodiraju Viterbijevim algoritmom, mada se ponekad koriste i drugi algoritmi. Viterbijevo dekodiranje omogućava asimptotski optimalnu efikasnost dekodiranja sa povećanjem dužine ograničenja konvolucionog koda, ali na račun eksponencijalno rastuće složenosti. Konvolucijski kod koji je prekinut je takođe 'blok kod' po tome što kodira blok ulaznih podataka, ali je veličina bloka konvolucionog koda generalno proizvoljna, dok kodovi bloka imaju fiksnu veličinu koju diktiraju njihove algebarske karakteristike. Tipovi završetka za konvolucione kodove uključuju „odgrizanje repa” i „ispiranje bita”.
Postoji mnogo tipova blok kodova; Rid–Solomonovo kodiranje je vredno pažnje zbog svoje široke upotrebe na kompakt diskovima, DVD-ovima i hard diskovima. Drugi primeri klasičnih blok kodova uključuju Golay, BCH, višedimenzionalni paritet i Hamingove kodove.
Hamingov ECC se obično koristi za ispravljanje grešaka NAND fleš memorije.[5] Ovo obezbeđuje jednobitnu korekciju greške i detekciju 2-bitne greške. Hamingovi kodovi su pogodni samo za pouzdanije NAND ćelije sa jednim nivoom (SLC). NAND gušćih ćelija na više nivoa (MLC) može da koristi više-bitni ispravljajući ECC kao što je BCH ili Rid-Solomon.[6][7] NOR Flaš obično ne koristi nikakvu ispravku grešaka.[6]
Klasični blok kodovi se obično dekodiraju korišćenjem algoritama tvrdog odlučivanja,[8] što znači da se za svaki ulazni i izlazni signal donosi teška odluka da li odgovara jediničnom ili nultom bitu. Nasuprot tome, konvolucijski kodovi se obično dekodiraju korišćenjem algoritama meke odluke kao što su Viterbi, MAP ili BCJR algoritmi, koji obrađuju (diskretizovane) analogne signale i koji omogućavaju mnogo više performanse ispravljanja grešaka od dekodiranja sa tvrdom odlukom.
Skoro svi klasični blok kodovi primenjuju algebarska svojstva konačnih polja. Stoga se klasični blok kodovi često nazivaju algebarskim kodovima.
Za razliku od klasičnih blok kodova koji često specificiraju sposobnost otkrivanja ili ispravljanja grešaka, mnogim modernim blok kodovima kao što su LDPC kodovi nedostaju takve garancije. Umesto toga, savremeni kodovi se procenjuju u smislu njihove stope bitnih grešaka.
Većina kodova za ispravljanje grešaka unapred ispravlja samo preokret bitova, ali ne i umetanja ili brisanja bitova. U ovoj postavci, Hemingova udaljenost je odgovarajući način za merenje stope bitne greške. Nekoliko kodova za ispravljanje grešaka unapred je dizajnirano da ispravljaju umetanje i brisanje bitova, kao što su kodovi markera i kodovi vodenih žigova. Levenštajnova udaljenost je prikladniji način za merenje stope bitne greške kada se koriste takvi kodovi.[9]
Brzina koda i kompromis između pouzdanosti i brzine prenosa podataka
[уреди | уреди извор]Osnovni princip ECC-a je dodavanje redundantnih bitova kako bi se pomoglo dekoderu da sazna pravu poruku koju je kodirao predajnik. Brzina koda datog ECC sistema je definisana kao odnos između broja bitova informacija i ukupnog broja bitova (tj. informacija plus bitova redundancije) u datom komunikacionom paketu. Otuda je brzina koda realan broj. Niska brzina koda blizu nule implicira jak kod koji koristi mnogo redundantnih bitova za postizanje dobrih performansi, dok velika brzina koda blizu 1 implicira slab kod.
Redundantni bitovi koji štite informacije moraju se preneti koristeći iste komunikacione resurse koje pokušavaju da zaštite. Ovo uzrokuje fundamentalni kompromis između pouzdanosti i brzine prenosa podataka.[10] U jednom ekstremu, jak kod (sa niskom brzinom koda) može da izazove značajno povećanje SNR prijemnika (odnos signal-šum) smanjujući stopu greške u bitu, po cenu smanjenja efektivne brzine prenosa podataka. Sa druge strane, nekorišćenje bilo kakvog ECC-a (tj. brzina koda jednaka 1) koristi ceo kanal za potrebe prenosa informacija, po cenu ostavljanja bitova bez ikakve dodatne zaštite.
Jedno interesantno pitanje je: koliko efikasan u smislu prenosa informacija može biti ECC koji ima zanemarljivu stopu grešaka u dekodiranju? Na ovo pitanje je odgovorio Klod Šenon svojom drugom teoremom, koja kaže da je kapacitet kanala maksimalna brzina bitova koju može postići bilo koji ECC čija stopa grešaka teži nuli.[11] Njegov dokaz se oslanja na Gausovo nasumično kodiranje, koje nije pogodno za aplikacije u stvarnom svetu. Gornja granica koju je dao Šenonov rad inspirisala je dugo putovanje u dizajniranju ECC-a koji se mogu približiti krajnjoj granici performansi. Različiti kodovi danas mogu dostići skoro Šenonovu granicu. Međutim, ECC-i za postizanje kapaciteta su obično izuzetno složeni za implementaciju.
Najpopularniji ECC-ovi imaju kompromis između performansi i računarske složenosti. Obično njihovi parametri daju raspon mogućih brzina koda, koji se može optimizovati u zavisnosti od scenarija. Obično se ova optimizacija radi kako bi se postigla niska verovatnoća greške u dekodiranju uz minimiziranje uticaja na brzinu prenosa podataka. Drugi kriterijum za optimizaciju brzine koda je balansiranje niske stope greške i broja retransmisija kako bi se postigla energetska cena komunikacije.[12]
Reference
[уреди | уреди извор]- ^ 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.
- ^ а б 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.
- ^ 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”
- ^ а б Maunder, Robert (2016). „Overview of Channel Coding”.
- ^ "Hamming codes for NAND flash memory devices" Архивирано 21 август 2016 на сајту Wayback Machine. EE Times-Asia. Apparently based on "Micron Technical Note TN-29-08: Hamming Codes for NAND Flash Memory Devices" Архивирано 29 август 2017 на сајту Wayback Machine. 2005. Both say: "The Hamming algorithm is an industry-accepted method for error detection and correction in many SLC NAND flash-based applications."
- ^ а б „What Types of ECC Should Be Used on Flash Memory?” (Application note). Spansion. 2011. „Both Reed–Solomon algorithm and BCH algorithm are common ECC choices for MLC NAND flash. ... Hamming based block codes are the most commonly used ECC for SLC.... both Reed–Solomon and BCH are able to handle multiple errors and are widely used on MLC flash.”
- ^ Jim Cooke (август 2007). „The Inconvenient Truths of NAND Flash Memory” (PDF). стр. 28. „For SLC, a code with a correction threshold of 1 is sufficient. t=4 required ... for MLC.”
- ^ Baldi, M.; Chiaraluce, F. (2008). „A Simple Scheme for Belief Propagation Decoding of BCH and RS Codes in Multimedia Transmissions”. International Journal of Digital Multimedia Broadcasting. 2008: 1—12. doi:10.1155/2008/957846
.
- ^ Shah, Gaurav; Molina, Andres; Blaze, Matt (2006). „Keyboards and covert channels”. USENIX. Приступљено 20. 12. 2018.
- ^ Tse, David; Viswanath, Pramod (2005), Fundamentals of Wireless Communication, Cambridge University Press, UK
- ^ Shannon, C. E. (1948). „A mathematical theory of communication” (PDF). Bell System Technical Journal. 27 (3–4): 379—423 & 623—656. doi:10.1002/j.1538-7305.1948.tb01338.x. hdl:11858/00-001M-0000-002C-4314-2 .
- ^ Rosas, F.; Brante, G.; Souza, R. D.; Oberli, C. (2014). „Optimizing the code rate for achieving energy-efficient wireless communications”. Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC). стр. 775—780. ISBN 978-1-4799-3083-8. doi:10.1109/WCNC.2014.6952166.
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.
- 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.
- 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.
- 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.
- Robert G. Gallager (1963). Low Density Parity Check Codes (PDF). Monograph, M.I.T. Press. Приступљено 7. 8. 2013.
- 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
[уреди | уреди извор]
- 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= -