Kod za ispravljanje grešaka

U računarstvu, telekomunikacijama, teoriji informacija i teoriji kodiranja, kod za ispravljanje grešaka, ili kod korigovanja grešaka (енгл. 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 (енгл. 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 (енгл. 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. 
  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« 
  4. ^ а б Maunder, Robert (2016). „Overview of Channel Coding”. 

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

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