Что собой представляет контроль ошибок

Контроль ошибок

Эта статья — о работе с ошибками в данных при их хранении или передаче. О контроле фактических ошибок в текстах см. Проверка фактов; о проверке знаний и навыков при обучении см. Педагогическое тестирование; о методе обучения нейросети см. Метод коррекции ошибки.

Контроль ошибок — комплекс методов обнаружения и исправления ошибок в данных при их записи и воспроизведении или передаче по линиям связи.

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

В системах связи возможны несколько стратегий борьбы с ошибками:

• обнаружение ошибок в блоках данных и автоматический запрос повторной передачи^[⇨] повреждённых блоков — этот подход применяется, в основном, на канальном и транспортном уровнях;
• обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
• упреждающая коррекция ошибок добавляет к передаваемой информации такие дополнительные данные, которые позволяют исправить ошибки без дополнительного запроса.

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

Современное развитие корректирующих кодов приписывают Ричарду Хэммингу с 1947 года^[1]. Описание кода Хэмминга появилось в статье Клода Шеннона «Математическая теория связи»^[2] и было обобщено Марселем Голеем^[3].

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

Упреждающая коррекция ошибок

Упреждающая коррекция ошибок (также прямая коррекция ошибок, англ. Forward Error Correction, FEC) — техника помехоустойчивого кодирования и декодирования, позволяющая исправлять ошибки методом упреждения. Применяется для исправления сбоев и ошибок при передаче данных путём передачи избыточной служебной информации, на основе которой может быть восстановлено первоначальное содержание. На практике широко используется в сетях передачи данных, телекоммуникационных технологиях. Коды, обеспечивающие прямую коррекцию ошибок, требуют введения большей избыточности в передаваемые данные, чем коды, которые только обнаруживают ошибки.

Например, в спутниковом телевидении при передаче цифрового сигнала с FEC 7/8 передаётся восемь бит информации: 7 бит полезной информации и 1 контрольный бит^[4]; в DVB-S используется всего 5 видов: 1/2, 2/3, 3/4 (наиболее популярен), 5/6 и 7/8. При прочих равных условиях, можно утверждать, что чем ниже значение FEC, тем меньше пакетов допустимо потерять, и, следовательно, выше требуемое качество сигнала.

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

Автоматический запрос повторной передачи

Системы с автоматическим запросом повторной передачи (англ. Automatic Repeat Request, ARQ) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

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

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

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

Сетевое кодирование

Раздел теории информации, изучающий вопрос оптимизации передачи данных по сети с использованием техник изменения пакетов данных на промежуточных узлах называют сетевым кодированием. Для объяснения принципов сетевого кодирования используют пример сети «бабочка», предложенной в первой работе по сетевому кодированию «Network information flow»^[5]. В отличие от статического сетевого кодирования, когда получателю известны все манипуляции, производимые с пакетом, также рассматривается вопрос о случайном сетевом кодировании, когда данная информация неизвестна. Авторство первых работ по данной тематике принадлежит Кёттеру, Кшишангу и Силве^[6]. Также данный подход называют сетевым кодированием со случайными коэффициентами — когда коэффициенты, под которыми начальные пакеты, передаваемые источником, войдут в результирующие пакеты, принимаемые получателем, с неизвестными коэффициентами, которые могут зависеть от текущей структуры сети и даже от случайных решений, принимаемых на промежуточных узлах. Для неслучайного сетевого кодирования можно использовать стандартные способы защиты от помех и искажений, используемых для простой передачи информации по сети.

Энергетический выигрыш

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

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

Примечания

Литература

• Блейхут Р. Теория и практика кодов, контролирующих ошибки = 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.

Ссылки

• Charles Wang, Dean Sklar, and Diana Johnson. Forward Error-Correction Coding. The Aerospace Corporation. — Volume 3, Number 1 (Winter 2001/2002). Дата обращения: 24 мая 2009. Архивировано из оригинала 20 февраля 2005 года. (англ.)
• Charles Wang, Dean Sklar, and Diana Johnson. How Forward Error-Correcting Codes Work (недоступная ссылка — история). The Aerospace Corporation. Дата обращения: 24 мая 2009. Архивировано 25 февраля 2012 года. (англ.)
• Morelos-Zaragoza, Robert The Error Correcting Codes (ECC) Page (недоступная ссылка — история) (2004). Дата обращения: 24 мая 2009. Архивировано 25 февраля 2012 года. (англ.)

Эта страница в последний раз была отредактирована 17 октября 2022 в 07:46.

Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.

Классификация методов контроля достоверности по степени выявления и коррекции ошибок

По степени выявления и коррекции ошибок
контроль делится на:

• обнаруживающий,
  фиксирующий только сам факт наличия
  или отсутствия ошибки;

• локализующий,
  позволяющий определить как факт наличия,
  так и место ошибки (например символ,
  реквизит и т. д.);

• исправляющий,
  выполняющий функции и обнаружения, и
  локализации, и исправления ошибки.

В работах [6, 8] приведен обширный список
методов контроля достоверности информации
(более 100 методов), в том числе методы,
использующие контрольные суммы и
контрольные байты, коды с обнаружением
и автоматическим исправлением ошибок
(корректирующие коды); методы семантического
и балансового контроля, методы
алгоритмического и эвристического
контроля, методы верификации, прямого
и обратного преобразования (передачи)
информации и т. д.

Основные показатели качества контроля достоверности

Функциональные показатели
качества контроля (показатели
его эффективности) должны количественно
определять степень приспособленности
и выполнения контролем поставленных
перед ним задач. В общем случае контроля
такими показателями могут служить
коэффициенты, численно равные условным
вероятностям соответствующих событий
при условии наличия ошибки.

Для обнаруживающего и локализующего
контроля такими коэффициентами являются:

• коэффициент обнаружения ошибок —
  K_обн = N_обн / N_ош = P_обн / P_ош;

• коэффициент необнаружения ошибок —
  K_но = N_но / N_ош = P_но / P_ош;

• коэффициент локализации ошибок К_лок
  для большинства методов локализующего
  контроля равен коэффициенту обнаружения,
  то есть К_лок = К_обн.

Методы контроля, исправляющие ошибки,
характеризуются следующими коэффициентами:

• исправления ошибок
  K_испр = N_испр / N_ош = P_испр / P_ош;

• искажения ошибок K_иск = N_иск / N_ош = P_иск / P_ош;

• обнаружения ошибок K_обн = N_обн / N_ош = P_обн / P_ош;

• не-обнаружения ошибок
  K_но = N_но / N_ош = P_но / P_ош.

В этих соотношениях:

• N — число структурных
  элементов (символов, реквизитов,
  показателей и т. д.) в информационной
  совокупности;

• N_но, N_испр,
  N_иск, N_обн —
  число ошибок, которые в процессе
  контроля, соответственно, не обнаруживаются,
  правильно исправляются, неверно
  исправляются (искажаются), только
  обнаруживаются (факт наличия которых
  просто устанавливается, а сами они не
  исправляются);

• Р_ош, Р_обн,
  Р_но, Р_испр,
  Р_иск —
  вероятности наличия ошибки, обнаружения,
  не-обнаружения, исправления и искажения
  ошибки, соответственно.

Важными показателями качества контроля
являются также:

• коэффициент выявления ошибок
  K_выявл = N_выявл / N_ош,
  характеризующий суммарное относительное
  число выявляемых (N_выявл)
  ошибок в контролируемой информационной
  совокупности;

• коэффициент трансформации ошибок
  K_тр = N_ош.вых / N_ош,
  характеризующий суммарное относительное
  число необнаруженных и вновь внесенных
  при контроле (N_ош.вых)
  ошибок.

Для контроля с
исправлением ошибок:

К_выявл
= К_испр + К_иск
+ К_обн;

К_тр
= К_но + К_иск.

Для контроля с обнаружением ошибок:

К_испр
= К_иск = 0

К_выявл
= К_обн,

К_тр
= К_но

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

• Р_пр —
  вероятность правильного необнаружения
  ошибки, то есть такого события, когда
  не вырабатывается информация о наличии
  ошибки при условии действительного ее
  отсутствия;

• Р_лт —
  вероятность ложного обнаружения ошибки
  (ложной тревоги), то есть такого события,
  когда вырабатывается информация о
  наличии ошибки при реальном ее отсутствии.

Технико-эксплуатационные показатели
контроля:

• алгоритмическая сложность контроля;

• вид и величина используемой избыточности;

• надежность контроля;

• универсальность (возможность использования
  на различных фазах технологического
  процесса, при решении различных задач
  и для различных групп и типов информационных
  ошибок) и др.

Соответствующие коэффициенты
K_пр = P_пр / P_ош,
K_иг = P_иг / P_ош
могут быть существенно больше 1,
поскольку K_пр + K_лт = (1 – P_ош)/P_ош.

Экономические показатели эффективности
контроля — это затраты на контроль:

• единовременные;

• текущие;

• материальные;

• трудовые;

• временные.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Шум или ошибка – основная проблема в сигнале, которая нарушает надежность системы связи. Кодирование с контролем ошибок – это процедура кодирования, выполняемая для контроля появления ошибок. Эти методы помогают в обнаружении ошибок и исправлении ошибок.

Существует много различных кодов, исправляющих ошибки, в зависимости от применяемых к ним математических принципов. Но исторически эти коды были классифицированы на линейные блочные коды и коды свертки .

Линейные Блочные Коды

В линейных блочных кодах биты четности и биты сообщения имеют линейную комбинацию, что означает, что результирующее кодовое слово является линейной комбинацией любых двух кодовых слов.

Рассмотрим некоторые блоки данных, которые содержат k битов в каждом блоке. Эти биты отображаются с блоками, которые имеют n битов в каждом блоке. Здесь n больше, чем k . Передатчик добавляет избыточные биты, которые являются (nk) битами. Отношение k / n является скоростью кода . Обозначается через r, а значение r равно r <1 .

Добавленные здесь биты (nk) являются битами четности . Биты четности помогают в обнаружении и исправлении ошибок, а также в поиске данных. В передаваемых данных самые левые биты кодового слова соответствуют битам сообщения, а самые правые биты кодового слова соответствуют битам четности.

Систематический код

Любой линейный блочный код может быть систематическим кодом, пока он не будет изменен. Следовательно, неизмененный блочный код называется систематическим кодом .

Ниже приведено представление структуры кодовых слов в соответствии с их распределением.

Если сообщение не изменено, оно называется систематическим кодом. Это означает, что шифрование данных не должно изменять данные.

Сверточные коды

До сих пор в линейных кодах мы обсуждали, что систематический неизмененный код является предпочтительным. Здесь данные из общего числа n битов, если переданы, k битов являются битами сообщения и (nk) битами являются биты четности.

В процессе кодирования биты четности вычитаются из целых данных, а биты сообщения кодируются. Теперь биты четности снова добавляются, и все данные снова кодируются.

На следующем рисунке приведены примеры блоков данных и потоков данных, используемых для передачи информации.

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

Этот недостаток устраняется в сверточных кодах. Где весь поток данных назначается символам, а затем передается. Поскольку данные представляют собой поток битов, для хранения не требуется буфер.

Коды Хэмминга

Свойство линейности кодового слова состоит в том, что сумма двух кодовых слов также является кодовым словом. Коды Хэмминга – это тип линейных кодов, исправляющих ошибки , которые могут обнаруживать до двухбитовых ошибок или исправлять однобитовые ошибки без обнаружения неисправленных ошибок.

При использовании кодов Хэмминга дополнительные биты четности используются для идентификации ошибки одного бита. Чтобы перейти от одного бита к другому, в данных нужно изменить несколько битов. Такое количество битов можно назвать расстоянием Хэмминга . Если четность имеет расстояние 2, может быть обнаружен однобитовый переворот. Но это не может быть исправлено. Кроме того, любые два бита не могут быть обнаружены.

Тем не менее, код Хэмминга – лучшая процедура, чем обсуждаемые ранее при обнаружении и исправлении ошибок.

Коды BCH

Коды БЧХ названы в честь изобретателей B ose, C haudari и H ocquenghem. Во время разработки кода BCH существует контроль количества символов, которые должны быть исправлены, и, следовательно, возможна множественная битовая коррекция. Коды БЧХ – это мощный метод исправления ошибок.

Для любых натуральных чисел m ≥ 3 и t <2 ^m-1 существует двоичный код BCH. Ниже приведены параметры такого кода.

Длина блока n = 2 ^м -1

Количество проверочных цифр n – k ≤ mt

Минимальное расстояние d _min ≥ 2t + 1

Этот код может называться кодом BCH с коррекцией ошибок .

Циклические коды

Циклическое свойство кодовых слов заключается в том, что любой циклический сдвиг кодового слова также является кодовым словом. Циклические коды следуют этому циклическому свойству.

Для линейного кода C , если каждое кодовое слово, т. Е. C = (C1, C2, …… Cn) из C, имеет циклический сдвиг вправо компонентов, оно становится кодовым словом. Этот сдвиг вправо равен n-1 циклическим сдвигам влево. Следовательно, он инвариантен при любом сдвиге. Таким образом, линейный код C , поскольку он инвариантен при любом сдвиге, можно назвать циклическим кодом .

Циклические коды используются для исправления ошибок. Они в основном используются для исправления двойных ошибок и пакетных ошибок.

Следовательно, это несколько кодов с исправлением ошибок, которые должны быть обнаружены в приемнике. Эти коды предотвращают появление ошибок и нарушают связь. Они также предотвращают прослушивание сигнала нежелательными приемниками. Для этого существует класс методов сигнализации, которые обсуждаются в следующей главе.