Просмотр кода страницы Контроль ошибок

{{о|работе с ошибками в данных при их хранении или передаче|контроле фактических ошибок в текстах|Проверка фактов|проверке знаний и навыков при обучении|Педагогическое тестирование|методе обучения нейросети|Метод коррекции ошибки|подходе к работе с ошибками в программах|Обработка исключений}}
'''Контроль ошибок''' — комплекс методов обнаружения и исправления ошибок в [[Данные (вычислительная техника)|данных]] при их записи и воспроизведении или передаче по линиям связи.

Контроль целостности данных и исправление ошибок — важные задачи на многих уровнях работы с информацией (в частности, [[физический уровень|физическом]], [[канальный уровень|канальном]], [[транспортный уровень|транспортном]] уровнях [[Модель OSI|сетевой модели OSI]]) в связи с тем, что в процессе хранения данных и передачи информации по сетям связи неизбежно возникают ошибки. Различные области применения контроля ошибок диктуют различные требования к используемым стратегиям и кодам.

В системах связи возможны несколько стратегий борьбы с ошибками:
* обнаружение ошибок в блоках данных и автоматический запрос повторной передачи{{Переход|Автоматический запрос повторной передачи}} повреждённых блоков — этот подход применяется, в основном, на канальном и транспортном уровнях;
* обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
* упреждающая коррекция ошибок добавляет к передаваемой информации такие дополнительные данные, которые позволяют исправить ошибки без дополнительного запроса.

В контроле ошибок, как правило, используется помехоустойчивое кодирование — кодирование данных при записи или передаче и [[декодирование]] при считывании или получении при помощи [[Корректирующий код|корректирующих кодов]], которые и позволяют обнаружить и, возможно, исправить ошибки в данных. Алгоритмы помехоустойчивого кодирования в различных приложениях могут быть реализованы как программно, так и аппаратно.

Современное развитие [[Корректирующий код|корректирующих кодов]] приписывают [[Ричард Хэмминг|Ричарду Хэммингу]] с [[1947 год]]а<ref name=Thompson>{{citation|first=Thomas M.|last=Thompson|title=From Error-Correcting Codes through Sphere Packings to Simple Groups|publisher=The Mathematical Association of America|year=1983|series=The Carus Mathematical Monographs (#21)|isbn=0-88385-023-0|page=vii}}</ref>. Описание [[Код Хэмминга|кода Хэмминга]] появилось в статье [[Клод Шеннон|Клода Шеннона]] «[[Математическая теория связи]]»<ref>{{citation|first=C.E.|last=Shannon|title=A Mathematical Theory of Communication|journal=Bell System Technical Journal|volume=27|issue=3|pages=379–423|year=1948|location= p. 418|doi=10.1002/j.1538-7305.1948.tb01338.x|pmid=9230594|hdl=10338.dmlcz/101429|hdl-access=free}}</ref> и было обобщено [[Голей, Марсель|Марселем Голеем]]<ref>{{citation|first=Marcel J. E.|last=Golay|title=Notes on Digital Coding|journal=Proc.I.R.E. (I.E.E.E.)|volume=37|year=1949|location= p. 657}}</ref>.

== Стратегии исправления ошибок ==

=== Упреждающая коррекция ошибок ===
{{falseredirect|Прямая коррекция ошибок}}
Упреждающая коррекция ошибок (также ''прямая коррекция ошибок'', {{lang-en|Forward Error Correction, FEC}}) — техника помехоустойчивого кодирования и [[Декодирование|декодирования]], позволяющая исправлять ошибки методом упреждения. Применяется для исправления сбоев и ошибок при передаче данных путём передачи избыточной служебной информации, на основе которой может быть восстановлено первоначальное содержание. На практике широко используется в [[Сеть передачи данных|сетях передачи данных]], телекоммуникационных технологиях. Коды, обеспечивающие прямую коррекцию ошибок, требуют введения большей избыточности в передаваемые данные, чем коды, которые только обнаруживают ошибки.

Например, в [[Спутниковое телевидение|спутниковом телевидении]] при передаче цифрового сигнала с FEC 7/8 передаётся восемь бит информации: 7 бит полезной информации и 1 контрольный бит<ref>{{Cite web |url=https://books.google.ru/books?id=IW-iqhtqYGMC&pg=PA88&dq=%22FEC |title=Understanding Digital Television: An Introduction to Dvb Systems With … — Lars-Ingemar Lundström — Google Книги |access-date=2020-05-19 |archive-date=2021-11-11 |archive-url=https://web.archive.org/web/20211111042249/https://books.google.ru/books?id=IW-iqhtqYGMC&pg=PA88&dq=%22FEC |url-status=live }}</ref>; в [[DVB-S]] используется всего 5 видов: 1/2, 2/3, 3/4 (наиболее популярен), 5/6 и 7/8. При прочих равных условиях, можно утверждать, что чем ниже значение FEC, тем меньше пакетов допустимо потерять, и, следовательно, выше требуемое качество сигнала.

Техника прямой коррекции ошибок широко применяется в различных устройствах хранения данных — жёстких дисках, флеш-памяти, оперативной памяти. В частности, в серверных приложениях применяется [[ECC-память]] — оперативная память, способная распознавать и исправлять спонтанно возникшие ошибки.

=== Автоматический запрос повторной передачи ===
Системы с [[Автоматический запрос повторной передачи|автоматическим запросом повторной передачи]] ({{lang-en|Automatic Repeat Request, ARQ}}) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Идея запроса ARQ с остановками ({{lang-en|stop-and-wait ARQ}}) заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем, как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для [[полудуплекс]]ного канала связи. Его недостатком является низкая скорость из-за высоких накладных расходов на ожидание.

Для метода непрерывного запроса ARQ с возвратом ({{lang-en2|continuous ARQ with pullback}}) необходим [[полный дуплекс|полнодуплексный]] канал. Передача данных от передатчика к приемнику производится одновременно. В случае ошибки передача возобновляется, начиная с ошибочного блока (то есть передается ошибочный блок и все последующие).

При использовании метода непрерывного запроса ARQ с выборочным повторении ({{lang-en2|continuous ARQ with selective repeat}}) осуществляется передача только ошибочно принятых блоков данных.

== Сетевое кодирование ==
{{catmain|Сетевое кодирование}}
Раздел [[теория информации|теории информации]], изучающий вопрос оптимизации передачи данных по сети с использованием техник изменения пакетов данных на промежуточных узлах называют [[Сетевое кодирование|сетевым кодированием]]. Для объяснения принципов сетевого кодирования используют пример сети «бабочка», предложенной в первой работе по сетевому кодированию «Network information flow»<ref>Ahlswede, R.; Ning Cai; Li, S.-Y.R.; Yeung, R.W., «[http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=850663&isnumber=18482 Network information flow]», Information Theory, IEEE Transactions on, vol.46, no.4, pp.1204-1216, Jul 2000</ref>. В отличие от статического сетевого кодирования, когда получателю известны все манипуляции, производимые с пакетом, также рассматривается вопрос о случайном сетевом кодировании, когда данная информация неизвестна. Авторство первых работ по данной тематике принадлежит Кёттеру, Кшишангу и Силве<ref>Статьи:
* Koetter R., Kschischang F.R. Coding for errors and erasures in random network coding// IEEE International Symposium on Information Theory. Proc.ISIT-07.-2007.- P. 791—795.
* Silva D., Kschischang F.R. Using rank-metric codes for error correction in random network coding // IEEE International Symposium on Information Theory. Proc. ISIT-07. — 2007.
* Koetter R., Kschischang F.R. Coding for errors and erasures in random network coding // IEEE Transactions on Information Theory. — 2008- V. IT-54, N.8. — P. 3579-3591.
* Silva D., Kschischang F.R., Koetter R. A Rank-Metric Approach to Error Control in Random Network Coding // IEEE Transactions on Information Theory.- 2008- V. IT-54, N. 9.- P.3951-3967.</ref>. Также данный подход называют сетевым кодированием со случайными коэффициентами — когда коэффициенты, под которыми начальные пакеты, передаваемые источником, войдут в результирующие пакеты, принимаемые получателем, с неизвестными коэффициентами, которые могут зависеть от текущей структуры сети и даже от случайных решений, принимаемых на промежуточных узлах. Для неслучайного сетевого кодирования можно использовать стандартные способы защиты от помех и искажений, используемых для простой передачи информации по сети.

== Энергетический выигрыш ==
При передаче информации по каналу связи вероятность ошибки зависит от [[Отношение сигнал/шум|отношения сигнал/шум]] на входе демодулятора, таким образом, при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определённых системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.

Поскольку помехоустойчивое кодирование позволяет исправлять ошибки, при его применении мощность передатчика можно снизить, оставляя скорость передачи информации неизменной. Энергетический выигрыш определяется как разница отношений с/ш при наличии и отсутствии кодирования.

== Примечания ==
{{примечания}}

== Литература ==
{{викиучебник|Помехоустойчивое кодирование}}
* {{Книга:Блейхут Р.: Теория и практика кодов}}
* Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
* {{Книга:Морелос-Сарагоса Р.: Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение}}
* 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.

== Ссылки ==
* {{cite web
 |last        = 
 |first       = 
 |author-link  = 
 |author   = Charles Wang, Dean Sklar, and Diana Johnson
 |description = Volume 3, Number 1 (Winter 2001/2002)
 |url         = http://www.aero.org/publications/crosslink/winter2002/04.html
 |title       = Forward Error-Correction Coding
 |format      = 
 |publisher   = The Aerospace Corporation
 |access-date  = 2009-05-24
 |archive-url  = https://web.archive.org/web/20050220101349/http://www.aero.org/publications/crosslink/winter2002/04.html
 |archive-date = 2005-02-20
 |url-status    = dead
|lang=en}}
* {{cite web
 |last        = 
 |first       = 
 |author-link  = 
 |author   = Charles Wang, Dean Sklar, and Diana Johnson
 |url         = http://www.aero.org/publications/crosslink/winter2002/04_sidebar1.html
 |title       = How Forward Error-Correcting Codes Work
 |format      = 
 |publisher   = The Aerospace Corporation
 |access-date  = 2009-05-24
 |archive-url  = https://www.webcitation.org/65iNlJg1b?url=http://www.aero.org/publications/crosslink/winter2002/04_sidebar1.html
 |archive-date = 2012-02-25
 |url-status    = dead
|lang=en}}
* {{cite web
 |last        = Morelos-Zaragoza
 |first       = Robert
 |author-link  = 
 |coauthors   = 
 |date        = 2004
 |url         = http://www.eccpage.com/
 |title       = The Error Correcting Codes (ECC) Page
 |format      = 
 |work        = 
 |publisher   = 
 |access-date  = 2009-05-24
 |archive-url  = https://www.webcitation.org/65iNlmFK2?url=http://www.eccpage.com/
 |archive-date = 2012-02-25
 |url-status    = dead
|lang=en}}

[[Категория:Кибернетика]]
[[Категория:Компьютерные ошибки]]
[[Категория:Обнаружение и устранение ошибок]]
[[Категория:Передача данных]]
[[Категория:Теория кодирования]]