Детекција и корекција грешака
У теорији информација и кодирања са применама у рачунарској науци и телекомуникацијама, детекција и корекција грешака или контрола грешака су технике које омогућавају поуздану испоруку дигиталних података преко непоузданих комуникационих канала. Многи канали комуникације су подложни буци канала и тако се могу увести грешке током преноса са извора на пријемник. Технике детекције грешака омогућавају откривање таквих грешака, док исправљање грешака омогућава реконструкцију оригиналних података у многим случајевима.[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]
Референце[уреди | уреди извор]
- ^ Ирвине, Јамес; Харле, Давид (2002). Дата Цоммуницатионс анд Нетwоркс. ИСБН 9780471808725.
- ^ а б „Масорах”. Јеwисх Енцyцлопедиа.
- ^ Пратицо, Гарy D.; Пелт, Милес V. Ван (2009). Басицс оф Библицал Хебреw Граммар: Сецонд Едитион. Зондерван. ИСБН 978-0-310-55882-8.
- ^ Моунце, Wиллиам D. (2007). Греек фор тхе Рест оф Ус: Усинг Греек Тоолс Wитхоут Мастеринг Библицал Лангуагес. Зондерван. стр. 289. ИСБН 978-0-310-28289-1.
- ^ Мисхнех Торах, Тефиллин, Мезузах, анд Сефер Торах, 1:2. Еxампле Енглисх транслатион: Тоугер, Елиyаху. Тхе Рамбам'с Мисхнех Торах. Мознаим Публисхинг Цорпоратион.
- ^ Бриан M. Фаган (5. 12. 1996). „Деад Сеа Сцроллс”. Тхе Оxфорд Цомпанион то Арцхаеологy. Оxфорд Университy Пресс. ИСБН 0195076184.
- ^ Тхомпсон, Тхомас M. (1983), Фром Еррор-Цоррецтинг Цодес тхроугх Спхере Пацкингс то Симпле Гроупс, Тхе Царус Матхематицал Монограпхс (#21), Тхе Матхематицал Ассоциатион оф Америца, стр. вии, ИСБН 0-88385-023-0
- ^ Сханнон, C.Е. (1948), „А Матхематицал Тхеорy оф Цоммуницатион”, Белл Сyстем Тецхницал Јоурнал, п. 418, 27
- ^ Голаy, Марцел Ј. Е. (1949), „Нотес он Дигитал Цодинг”, Проц.I.Р.Е. (I.Е.Е.Е.), п. 657, 37
- ^ МацКаy, Давид Ј.C. (2003). „2.4 Дефинитион оф ентропy анд релатед фунцтионс”. Информатион Тхеорy, Инференце, анд Леарнинг Алгоритхмс. Цамбридге Университy Пресс. стр. 33. ИСБН 0-521-64298-1. „Тхе редунданцy меасурес тхе фрацтионал дифференце бетwеен Х(X) анд итс маxимум поссибле валуе, ”
- ^ Едwард А. Лее. „Тхе Проблем wитх Тхреадс” (ПДФ). Приступљено 2009-05-29.
- ^ Боццхино Јр., Роберт L.; Адве, Викрам С.; Адве, Сарита V.; Снир, Марц (2009). Параллел Программинг Муст Бе Детерминистиц бy Дефаулт. УСЕНИX Wорксхоп он Хот Топицс ин Параллелисм.
- ^ „Интел Параллел Инспецтор Тхреад Цхецкер”. Приступљено 2009-05-29.
- ^ Лин, Yуан. „Дата Раце анд Деадлоцк Детецтион wитх Сун Студио Тхреад Аналyзер” (ПДФ). Приступљено 2009-05-29.
- ^ Интел. „Интел Параллел Инспецтор”. Приступљено 2009-05-29.
- ^ Wортхингтон, Давид. „Интел аддрессес девелопмент лифе цyцле wитх Параллел Студио”. Архивирано из оригинала 2009-05-28. г. Приступљено 2009-05-26.
- ^ Гупта, Викас; Верма, Цхандеркант (новембар 2012). „Еррор Детецтион анд Цоррецтион: Ан Интродуцтион” (ПДФ). Интернатионал Јоурнал оф Адванцед Ресеарцх ин Цомпутер Сциенце анд Софтwаре Енгинееринг. 2 (11). Архивирано из оригинала (ПДФ) 21. 08. 2019. г. Приступљено 21. 8. 2019.
- ^ Френгер, П.; С. Парквалл; Е. Дахлман (октобар 2001). „Перформанце цомпарисон оф ХАРQ wитх Цхасе цомбининг анд инцрементал редунданцy фор ХСДПА”. Вехицулар Тецхнологy Цонференце, 2001. ВТЦ 2001 Фалл. ИЕЕЕ ВТС 54тх. 3. Писцатаwаy Тоwнсхип, Неw Јерсеy: ИЕЕЕ Оператионс Центер. стр. 1829—1833. ИСБН 0-7803-7005-8. дои:10.1109/ВТЦ.2001.956516.
Литература[уреди | уреди извор]
- Лин, Сху; Даниел Ј. Цостелло, Јр. (1983). Еррор Цонтрол Цодинг: Фундаменталс анд Апплицатионс. Прентице Халл. ИСБН 0-13-283796-X.
- Сољанин, Емина; Лиу, Руохенг; Спасојевиц, Предраг (2004). „Хyбрид АРQ wитх Рандом Трансмиссион Ассигнментс”. Адванцес ин нетwорк информатион тхеорy. Провиденце, Рходе Исланд: Америцан Матхематицал Социетy. стр. 321—334. ИСБН 0-8218-3467-3. Приступљено 18. 3. 2009. алсо аваилабле ас препринт.
- Цомрое, Р.; D. Цостелло (јул 1984). „АРQ сцхемес фор дата трансмиссион ин мобиле радио сyстемс”. ИЕЕЕ Јоурнал он Селецтед Ареас ин Цоммуницатионс. 2 (4): 472—481. дои:10.1109/ЈСАЦ.1984.1146084.
- Давида, Георге I.; Судхакар M. Реддy (септембар 1972). „Форwард Еррор Цоррецтион wитх Децисион Феедбацк”. Информатион анд Цонтрол. 21 (2): 117—133. дои:10.1016/С0019-9958(72)90057-5.
- „Рате Матцхинг & ХАРQ (WЦДМА/ХСДПА)”. Рате Матцхинг & ХАРQ (WЦДМА/ХСДПА).[мртва веза]
- Дахлман, Ерик; Парквалл, Стефан; Скöлд, Јохан; Беминг, Пер (2008). 3Г Еволутион - ХСПА анд ЛТЕ фор Мобиле Броадбанд (2 изд.). Ацадемиц Пресс. стр. 119—123. ИСБН 978-0-12-374538-5.
- Елwyн Р. Берлекамп (2014), Алгебраиц Цодинг Тхеорy, Wорлд Сциентифиц Публисхинг (ревисед едитион), ISBN 978-9-81463-589-9.
- MacKay, David J. C.. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, . ISBN 0-521-64298-1. Текст „year” игнорисан (помоћ); Текст „pages” игнорисан (помоћ); Недостаје или је празан параметар
|title=
(помоћ) - Vera Pless (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., ISBN 0-471-08684-3.
- Рандy Yатес, А Цодинг Тхеорy Туториал.
- Тхорпе, С.Ј. (1990). Ецкмиллер, Р.; Хартманн, Г.; Хауске, Г., ур. Параллел процессинг ин неурал сyстемс анд цомпутерс. Нортх-Холланд. ИСБН 978-0-444-88390-2. Приступљено 30. 6. 2013.
- МцГраw, Гарy; Виега, Јохн. „Маке yоур софтwаре бехаве: Плаyинг тхе нумберс: Хоw то цхеат ин онлине гамблинг.”. Архивирано из оригинала 2008-03-13. г. Приступљено 2007-07-02.
- „Детерминисм цатегориес ин тхе Мерцурy программинг лангуаге”. Архивирано из оригинала 2012-07-03. г. Приступљено 2013-02-23.
- „Мерцурy предицате модес”. Архивирано из оригинала 2012-07-03. г. Приступљено 2013-02-25.
- Wиллиамс, Паул L.; Беер, Рандалл D. (2010). „Ноннегативе Децомпоситион оф Мултивариате Информатион”. арXив:1004.2515 [цс.ИТ].
- Гуткнецхт, А. Ј.; Wибрал, M.; Маккех, А. (2021). „Битс анд пиецес: Ундерстандинг информатион децомпоситион фром парт-wхоле релатионсхипс анд формал логиц”. Процеедингс оф тхе Роyал Социетy А: Матхематицал, Пхyсицал анд Енгинееринг Сциенцес. 477 (2251). Бибцоде:2021РСПСА.47710110Г. С2ЦИД 221246282. арXив:2008.09535 . дои:10.1098/рспа.2021.0110.
- Реза, Фазлоллах M. (1994) [1961]. Ан Интродуцтион то Информатион Тхеорy. Неw Yорк: Довер [МцГраw-Хилл]. ИСБН 0-486-68210-2.
- Сцхнеиер, Бруце (1996). Апплиед Црyптограпхy: Протоцолс, Алгоритхмс, анд Соурце Цоде ин C. Неw Yорк: Јохн Wилеy & Сонс, Инц. ИСБН 0-471-12845-7.
- Ауффартх, Б; Лопез-Санцхез, M.; Церqуидес, Ј. (2010). „Цомпарисон оф Редунданцy анд Релеванце Меасурес фор Феатуре Селецтион ин Тиссуе Цлассифицатион оф ЦТ имагес”. Адванцес ин Дата Мининг. Апплицатионс анд Тхеоретицал Аспецтс. Спрингер. стр. 248—262. ЦитеСеерX 10.1.1.170.1528 .
Спољашње везе[уреди | уреди извор]
- The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay
- Compute parameters of linear codes Архивирано на сајту Wayback Machine (11. фебруар 2015)
- ECC Page
- SoftECC: A System for Software Memory Integrity Checking
- A Tunable, Software-based DRAM Error Detection and Correction Library for HPC
- Detection and Correction of Silent Data Corruption for Large-Scale High-Performance Computing