Википедија

Детекција и корекција грешака

У теорији информација и кодирања са применама у рачунарској науци и телекомуникацијама, детекција и корекција грешака или контрола грешака су технике које омогућавају поуздану испоруку дигиталних података преко непоузданих комуникационих канала. Многи канали комуникације су подложни буци канала и тако се могу увести грешке током преноса са извора на пријемник. Технике детекције грешака омогућавају откривање таквих грешака, док исправљање грешака омогућава реконструкцију оригиналних података у многим случајевима.[1]

Дефиниције уреди

Детекција грешке је откривање грешака изазваних буком или другим погоршањима током преноса са предајника на пријемник. Корекција грешака је детекција грешака и реконструкција оригиналних података без грешака.

Историја уреди

У класичној антици, преписивачи хебрејске Библије су били плаћени за свој рад према броју стихова (редова стиха). Како су прозне књиге Библије ретко када су биле писане штиховима, преписивачи су, да би проценили обим посла, морали да преброје слова.[2] Ово је такође помогло да се обезбеди тачност у преносу текста уз израду наредних копија.[3][4] Између 7. и 10. века нове ере, група јеврејских писара је формализовала и проширила ово да би створила нумеричку масору како би се обезбедила тачна репродукција светог текста. То је укључивало пребројавање броја речи у реду, одељку, књизи и групама књига, бележећи средишњи шав књиге, статистику употребе речи и коментаре.[2] Стандарди су постали такви да се одступање чак и у једном слову у свитку Торе сматрало неприхватљивим.[5] Ефикасност њиховог метода исправљања грешака је потврђена прецизношћу копирања кроз векове, што је показано открићем свитака са Мртвог мора 1947–1956, који датирају из око 150. пре нове ере - 75. године.[6]

Заслуге за савремени развој кодова за исправљање грешака се придају Ричарду Хемингу због његових доприноса из 1947. године.[7] Опис Хеминговог кода објављен је у „Математичкој теорији комуникације” Клода Шенона[8] и убрзо након тога га је генерализовао Марсел Голај.[9]

Принципи уреди

Све шеме откривања и исправљања грешака додају редандантност[10] (тј. неке додатне податке) у поруку, које примаоци могу користити да провере конзистентност испоручене поруке и да поврате податке за које је утврђено да су оштећени. Схеме откривања и исправљања грешака могу бити систематске или несистематичне. У систематској схеми, пошиљалац шаље оригиналне податке и додаје фиксни број контролних битова (или паритетних података) који су изведени из битова података неким детерминираним алгоритмом.[11][12][13][14][15][16] Ако је потребно само откривање грешака, прималац може једноставно да примени исти алгоритам на примљене битове података и упореди свој излаз са примљеним контролним битовима; ако се вредности не подударају, дошло је до грешке у неком тренутку током преноса. У систему који користи несистематични код, оригинална порука се трансформише у шифрирану поруку која садржи исте информације и која има најмање онолико битова колико и изворна порука.

Добре перформансе контроле грешака захтевају да се схема одабере на основу карактеристика канала комуникације. Уобичајени модели канала укључују моделе без памћења код којих се грешке догађају насумично и са одређеном вероватноћом, и динамичке моделе где се грешке јављају првенствено у налетима. Сходно томе, кодови за откривање и исправљање грешака могу се генерално разликовати између откривања/исправљања случајних грешака и детекције/исправке налета грешака. Неки кодови такође могу бити погодни за мешавину случајних грешака и налета грешака.

Ако се карактеристике канала не могу одредити или су веома променљиве, схема откривања грешака може се комбиновати са системом за поновни пренос података који нису правилно пренети.[17] Ово је познато као аутоматско понављање захтева (енгл. automatic repeat request, АРQ) и често се користи на Интернету. Алтернативни приступ контроли грешке је хибридни аутоматски поновљени захтев (енгл. hybrid automatic repeat request, ХАРQ), који је комбинација АРQ и кодирања исправке грешака.[18]

Референце уреди

  1. ^ Ирвине, Јамес; Харле, Давид (2002). Дата Цоммуницатионс анд Нетwоркс. ИСБН 9780471808725. 
  2. ^ а б „Масорах”. Јеwисх Енцyцлопедиа. 
  3. ^ Пратицо, Гарy D.; Пелт, Милес V. Ван (2009). Басицс оф Библицал Хебреw Граммар: Сецонд Едитион. Зондерван. ИСБН 978-0-310-55882-8. 
  4. ^ Моунце, Wиллиам D. (2007). Греек фор тхе Рест оф Ус: Усинг Греек Тоолс Wитхоут Мастеринг Библицал Лангуагес. Зондерван. стр. 289. ИСБН 978-0-310-28289-1. 
  5. ^ Мисхнех Торах, Тефиллин, Мезузах, анд Сефер Торах, 1:2. Еxампле Енглисх транслатион: Тоугер, Елиyаху. Тхе Рамбам'с Мисхнех Торах. Мознаим Публисхинг Цорпоратион. 
  6. ^ Бриан M. Фаган (5. 12. 1996). „Деад Сеа Сцроллс”. Тхе Оxфорд Цомпанион то Арцхаеологy. Оxфорд Университy Пресс. ИСБН 0195076184. 
  7. ^ Тхомпсон, Тхомас M. (1983), Фром Еррор-Цоррецтинг Цодес тхроугх Спхере Пацкингс то Симпле Гроупс, Тхе Царус Матхематицал Монограпхс (#21), Тхе Матхематицал Ассоциатион оф Америца, стр. вии, ИСБН 0-88385-023-0 
  8. ^ Сханнон, C.Е. (1948), „А Матхематицал Тхеорy оф Цоммуницатион”, Белл Сyстем Тецхницал Јоурнал, п. 418, 27 
  9. ^ Голаy, Марцел Ј. Е. (1949), „Нотес он Дигитал Цодинг”, Проц.I.Р.Е. (I.Е.Е.Е.), п. 657, 37 
  10. ^ МацКаy, Давид Ј.C. (2003). „2.4 Дефинитион оф ентропy анд релатед фунцтионс”. Информатион Тхеорy, Инференце, анд Леарнинг Алгоритхмс. Цамбридге Университy Пресс. стр. 33. ИСБН 0-521-64298-1. „Тхе редунданцy меасурес тхе фрацтионал дифференце бетwеен Х(X) анд итс маxимум поссибле валуе,  ” 
  11. ^ Едwард А. Лее. „Тхе Проблем wитх Тхреадс” (ПДФ). Приступљено 2009-05-29. 
  12. ^ Боццхино Јр., Роберт L.; Адве, Викрам С.; Адве, Сарита V.; Снир, Марц (2009). Параллел Программинг Муст Бе Детерминистиц бy Дефаулт. УСЕНИX Wорксхоп он Хот Топицс ин Параллелисм. 
  13. ^ „Интел Параллел Инспецтор Тхреад Цхецкер”. Приступљено 2009-05-29. 
  14. ^ Лин, Yуан. „Дата Раце анд Деадлоцк Детецтион wитх Сун Студио Тхреад Аналyзер” (ПДФ). Приступљено 2009-05-29. 
  15. ^ Интел. „Интел Параллел Инспецтор”. Приступљено 2009-05-29. 
  16. ^ Wортхингтон, Давид. „Интел аддрессес девелопмент лифе цyцле wитх Параллел Студио”. Архивирано из оригинала 2009-05-28. г. Приступљено 2009-05-26. 
  17. ^ Гупта, Викас; Верма, Цхандеркант (новембар 2012). „Еррор Детецтион анд Цоррецтион: Ан Интродуцтион” (ПДФ). Интернатионал Јоурнал оф Адванцед Ресеарцх ин Цомпутер Сциенце анд Софтwаре Енгинееринг. 2 (11). Архивирано из оригинала (ПДФ) 21. 08. 2019. г. Приступљено 21. 8. 2019. 
  18. ^ Френгер, П.; С. Парквалл; Е. Дахлман (октобар 2001). „Перформанце цомпарисон оф ХАРQ wитх Цхасе цомбининг анд инцрементал редунданцy фор ХСДПА”. Вехицулар Тецхнологy Цонференце, 2001. ВТЦ 2001 Фалл. ИЕЕЕ ВТС 54тх. 3. Писцатаwаy Тоwнсхип, Неw Јерсеy: ИЕЕЕ Оператионс Центер. стр. 1829—1833. ИСБН 0-7803-7005-8. дои:10.1109/ВТЦ.2001.956516. 

Литература уреди

Спољашње везе уреди

 
Детекција и корекција грешака на Викимедијиној остави.
Преузето из „https://sr.wikipedia.org/w/index.php?title=Detekcija_i_korekcija_grešaka&oldid=27675841”