Kļūdu kontrole

Kļūdu kontrole (angļu: Error detection and correction jeb EDAC) ir datu kļūdu atklāšanas un labošanas process ierakstīšanas un atskaņošanas vai pārraides laikā pa sakaru līnijām.

Datu integritātes kontrole un kļūdu labošana ir svarīgi uzdevumi daudzos informācijas apstrādes līmeņos (jo īpaši OSI tīkla modeļa fiziskajā, kanāla un transporta līmeņos), jo datu glabāšanas un informācijas pārsūtīšanas procesā neizbēgami rodas kļūdas. Dažādas kļūdu kontroles piemērošanas jomas nosaka atšķirīgas prasības izmantotajām stratēģijām un kodiem.

Komunikācijas sistēmās ir iespējamas vairākas kļūdu novēršanas stratēģijas:

kļūdu noteikšana datu blokos un automātisks atkārtotas nosūtīšanas pieprasījums bojātiem blokiem — šo pieeju galvenokārt izmanto kanāla un transporta līmeņos;
kļūdu noteikšana datu blokos un bojāto bloku atmešana — šo pieeju dažreiz izmanto straumēšanas multivides sistēmās, kur pārraides kavēšanās ir svarīga un nav laika atkārtotai pārraidei;
preventīvā pārsūtīšanas kļūdu labošana pārsūtītajai informācijai pievieno tādus papildu datus, kas ļauj kļūdas labot bez papildu pieprasījuma.

Kļūdu kontrolē parasti tiek izmantota trokšņa korekcijas jeb prettraucēšanas kodēšana — datu kodēšana, rakstot vai pārsūtot, un dekodēšana, lasot vai saņemot, izmantojot korekcijas kodus, kas ļauj atklāt un, iespējams, izlabot datu kļūdas. Trokšņa korekcijas kodēšanas algoritmus dažādās lietojumprogrammās var ieviest gan programmatūrā, gan aparatūrā.

Vēsture

Lielu ieguldījumu mūsdienu labojošo kodu attīstībā kopš 1947. gada ir veicis Ričards Hemmings.^[1] Hemminga koda apraksts parādījās Kloda Šenona rakstā "Matemātiskās komunikācijas teorija",^[2] un to vispārināja Marsels Golajs.^[3]

Kļūdu labošanas stratēģijas

Preventīva kļūdu labošana

Preventīva kļūdu labošana (arī tiešā kļūdu labošana angl. Forward Error Correction, FEC) ir troksni koriģējoša kodēšanas un dekodēšanas tehnika, kas ļauj labot kļūdas, izmantojot paredzēšanas metodi. To izmanto, lai novērstu datu pārraides kļūmes un kļūdas, pārsūtot lieku pakalpojumu informāciju, uz kuras pamata var atjaunot sākotnējo saturu. Praksē to plaši izmanto datu pārraides tīklos, telekomunikāciju tehnoloģijās. Pārsūtīšanas kļūdu labošanas kodiem pārsūtītajos datos nepieciešama lielāka dublēšanās nekā kodiem, kas tikai atklāj kļūdas.

Piemēram, satelīta televīzijā, pārraidot ciparu signālu no FEC 7/8, tiek pārraidīti astoņi informācijas biti: 7 biti noderīgas informācijas un 1 vadības bits^[4]; DVB-S tiek izmantoti tikai 5 veidi: 1/2, 2/3, 3/4 (populārākie), 5/6 un 7/8. Ja visas pārējās lietas ir vienādas, var apgalvot, ka jo zemāka FEC vērtība, jo mazāk paketes ir atļauts pazaudēt, un tāpēc augstāka ir vajadzīgā signāla kvalitāte.

Tiešās kļūdu labošanas tehnika tiek plaši izmantota dažādās datu glabāšanas ierīcēs — cietajos diskos, zibatmiņā, brīvpiekļuves atmiņā. Jo īpaši servera lietojumprogrammas izmanto ECC atmiņu — brīvpiekļuves atmiņu, kas spēj atpazīt un labot spontāni radušās kļūdas.

Automātiskas retranslācijas pieprasījums

Automātiskās atkārtojuma pieprasīšanas (Automatic Repeat Request, ARQ) sistēmas ir balstītas uz kļūdu noteikšanas tehnoloģiju. Ir izplatītas šādas automātiskās pieprasīšanas metodes:

ARQ pieprasījuma ar apstāšanos (stop-and-wait ARQ) ideja ir tāda, ka raidītājs gaida, kamēr uztvērējs apstiprina iepriekšējā datu bloka veiksmīgu saņemšanu, pirms sāk nākamā nosūtīšanu. Gadījumā, ja datu bloks tika saņemts kļūdaini, uztvērējs nosūta negatīvu apstiprinājumu (negative acknowledgement, NAK), un raidītājs atkārto bloka pārraidi. Šī metode ir piemērota pusdupleksam sakaru kanālam.

Nepārtrauktai ARQ ar atgriešanos (continuous ARQ with pullback) metodi nepieciešams pilns duplekss kanāls. Datu pārsūtīšana no raidītāja uz uztvērēju tiek veikta vienlaikus. Kļūdas gadījumā pārraide tiek atsākta no kļūdainā bloka (t.i., kļūdainais bloks un visi nākamie tiek pārsūtīti).

Nepārtrauktā ARQ ar selektīvu atkārtošanas metodi nosūta tikai kļūdaini saņemtus datu blokus.

Tīkla kodēšana

Par tīkla kodēšanu sauc Informācijas teorijas sadaļu, kurā tiek pētīts jautājums par datu pārraides optimizēšanu tīklā, izmantojot paņēmienus datu pakešu modificēšanai pagaidu mezglos. Lai izskaidrotu tīkla kodēšanas principus, tiek izmantots "tauriņu" tīkla piemērs, kas pirmo reizi tika apskatīts pirmajā tīkla kodēšanas darbā "Tīkla informācijas plūsma".^[5] Atšķirībā no statiskā tīkla kodēšanas, kur saņēmējs zina visas ar paketi veiktās manipulācijas, tajā tiek runāts arī par nejaušu tīkla kodēšanu, gadījumos, kad šī informācija nav zināma. Pirmie darbi par šo tēmu pieder Ketteram, Kšišangam un Silvam.^[6]^[7]^[8]^[9] Šo pieeju sauc arī par tīkla kodēšanu ar nejaušiem koeficientiem — kad koeficienti, zem kuriem, pārsūtītās sākotnējās paketes tiks iekļautas rezultāta paketēs, kuras saņēmējs ir saņēmis ar nezināmiem koeficientiem, kuri var būt atkarīgi no pašreizējās tīkla struktūras un pat no nejaušajiem lēmumiem, kas pieņemti starpposma mezglos.

Enerģijas pieaugums

Pārraidot informāciju pa sakaru kanālu, kļūdas varbūtība ir atkarīga no signāla un trokšņa attiecības demodulatora ieejā, tādējādi pastāvīgā trokšņa līmenī raidītāja jaudai ir izšķiroša nozīme. Satelītu un mobilajās sistēmās, kā arī citos sakaru veidos enerģijas taupīšanas jautājums ir aktuāls. Turklāt dažās sakaru sistēmās (piemēram, telefonā) tehniskie ierobežojumi nedod neierobežotu signāla stipruma pieaugumu.

Tā kā kļūdu labojošais kodējums ļauj labot kļūdas, to lietojot, raidītāja jaudu var samazināt, informācijas pārraides ātrumu atstājot nemainīgu. Enerģijas pieaugumu definē kā SNR starpību kodēšanas klātbūtnē un neesamībā.

Piezīmes

↑ Thomas M. Thompson. From error-correcting codes through sphere packings to simple groups. [Washington] : Mathematical Association of America, 1983. ISBN 978-1-61444-021-5. OCLC 681278322.
↑ Shannon, C. E. (1948-07). "A Mathematical Theory of Communication". Bell System Technical Journal 27 (3): 379–423. doi:10.1002/j.1538-7305.1948.tb01338.x. ISSN 0005-8580.
↑ "Correspondence". Proceedings of the IRE 37 (6): 657–657. 1949-06. doi:10.1109/jrproc.1949.233620. ISSN 0096-8390.
↑ Lundstrom, Lars-Ingemar (2012-08-21). Understanding Digital Television. doi:10.4324/9780080492391.
↑ Ahlswede, R.; Ning Cai; Li, S.-Y.R.; Yeung, R.W. (2000-07). "Network information flow". IEEE Transactions on Information Theory 46 (4): 1204–1216. doi:10.1109/18.850663. ISSN 0018-9448.
↑ Koetter, Ralf; Kschischang, Frank R. (2007-06). "Coding for Errors and Erasures in Random Network Coding". 2007 IEEE International Symposium on Information Theory (IEEE). doi:10.1109/isit.2007.4557321. ISBN 978-1-4244-1397-3.
↑ Silva, Danilo; Kschischang, Frank R. (2007-06). "Using Rank-Metric Codes for Error Correction in Random Network Coding". 2007 IEEE International Symposium on Information Theory (IEEE). doi:10.1109/isit.2007.4557322. ISBN 978-1-4244-1397-3.
↑ Koetter, Ralf; Kschischang, Frank R. (2008-08). "Coding for Errors and Erasures in Random Network Coding". IEEE Transactions on Information Theory 54 (8): 3579–3591. doi:10.1109/tit.2008.926449. ISSN 0018-9448.
↑ Silva, Danilo; Kschischang, Frank R.; Koetter, Ralf (2008-09). "A Rank-Metric Approach to Error Control in Random Network Coding". IEEE Transactions on Information Theory 54 (9): 3951–3967. doi:10.1109/tit.2008.928291. ISSN 0018-9448.

Literatūra

Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.
Clark, George C., Jr., and J. Bibb Cain. Error-Correction Coding for Digital Communications. New York: Plenum Press, 1981. ISBN 0-306-40615-2.
Lin, Shu, and Daniel J. Costello, Jr. «Error Control Coding: Fundamentals and Applications». Englewood Cliffs, N.J.: Prentice-Hall, 1983. ISBN 0-13-283796-X.
Mackenzie, Dana. «Communication speed nears terminal velocity». New Scientist 187.2507 (9 июля 2005): 38-41. ISSN 0262-4079.
Wicker, Stephen B. Error Control Systems for Digital Communication and Storage. Englewood Cliffs, N.J.: Prentice-Hall, 1995. ISBN 0-13-200809-2.
Wilson, Stephen G. Digital Modulation and Coding, Englewood Cliffs, N.J.: Prentice-Hall, 1996. ISBN 0-13-210071-1.

[1] Thomas M. Thompson. From error-correcting codes through sphere packings to simple groups. [Washington] : Mathematical Association of America, 1983. ISBN 978-1-61444-021-5. OCLC 681278322.

[2] Shannon, C. E. (1948-07). "A Mathematical Theory of Communication". Bell System Technical Journal 27 (3): 379–423. doi:10.1002/j.1538-7305.1948.tb01338.x. ISSN 0005-8580.

[3] "Correspondence". Proceedings of the IRE 37 (6): 657–657. 1949-06. doi:10.1109/jrproc.1949.233620. ISSN 0096-8390.

[4] Lundstrom, Lars-Ingemar (2012-08-21). Understanding Digital Television. doi:10.4324/9780080492391.

[5] Ahlswede, R.; Ning Cai; Li, S.-Y.R.; Yeung, R.W. (2000-07). "Network information flow". IEEE Transactions on Information Theory 46 (4): 1204–1216. doi:10.1109/18.850663. ISSN 0018-9448.

[6] Koetter, Ralf; Kschischang, Frank R. (2007-06). "Coding for Errors and Erasures in Random Network Coding". 2007 IEEE International Symposium on Information Theory (IEEE). doi:10.1109/isit.2007.4557321. ISBN 978-1-4244-1397-3.

[7] Silva, Danilo; Kschischang, Frank R. (2007-06). "Using Rank-Metric Codes for Error Correction in Random Network Coding". 2007 IEEE International Symposium on Information Theory (IEEE). doi:10.1109/isit.2007.4557322. ISBN 978-1-4244-1397-3.

[8] Koetter, Ralf; Kschischang, Frank R. (2008-08). "Coding for Errors and Erasures in Random Network Coding". IEEE Transactions on Information Theory 54 (8): 3579–3591. doi:10.1109/tit.2008.926449. ISSN 0018-9448.

[9] Silva, Danilo; Kschischang, Frank R.; Koetter, Ralf (2008-09). "A Rank-Metric Approach to Error Control in Random Network Coding". IEEE Transactions on Information Theory 54 (9): 3951–3967. doi:10.1109/tit.2008.928291. ISSN 0018-9448.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]