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

Контроль правильности передачи данных

Проверка
правильности передачи данных может
выполняться с использованием 3-х различных
подходов:

1. Обнаружение
   ошибок.

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

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

Простейшим
способом обнаружения ошибок при
асинхронной
последовательной передаче
является контроль
четности.

При
этом в состав кадра
вводится дополнительный служебный бит
— бит паритета (рис. 1).

Рис. 1.  

Собственно
алгоритм обнаружения ошибок выглядит
следующим образом:

Действия
передатчика

1. Бит
   паритета устанавливается в «0»

2. Подсчитывается
   количество единиц во всех информационных
   битах

3. Значение
   бита паритета устанавливается таким,
   чтобы полученная сумма плюс бит паритета
   была четной

Действия
приемника

1. Подсчитывается
   количество единиц во всех принятых
   информационных битах полюс бит паритета.

2. Если
   полученная сумма является четной,
   данные приняты без искажений, в противном
   случае имела место ошибка.

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

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

Пакетный метод передачи данных по последовательному каналу

При
пакетном методе передачи информация
передается порциями, каждая порция
называется пакетом
(рис. 1).

Рис. 1.  

Пакет
состоит из отдельных символов,
а символ состоит из определенного числа
бит.
В начале пакета находятся стартовые
символы, которые имеют фиксированное
значение. Они определяют момент начала
передачи пакета и позволяют выполнить
синхронизацию приемника
с передатчиком
аналогично варианту асинхронной
передачи. Далее идут информационные
символы, в которых отсутствуют служебные
биты. Далее — контрольные символы,
содержащие информацию, позволяющую
проверить правильность передачи
информационных символов. Стоп-символы
имеют также фиксированное значение и
прием последнего стоп-символа определяет
момент окончания передачи пакета.

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

Управление последовательным каналом при полудуплексной связи

При
полудуплексном
режиме
последовательной
передачи,
передача данных возможна в обоих
направлениях, но не одновременно. Это
означает, что на обоих концах линии
связи установлены и приемник,
и передатчик.
Но так как линия связи одна, она
используется поочередно то одной парой
«приемник-передатчик» (для передачи
в одном направлении), то другой парой
(рис. 1).

Рис. 1.  

Следовательно,
необходима процедура согласования
между двумя парами «приемник-передатчик»
для определения права на занятие линии
связи и недопущения одновременного
занятия линии двумя передатчиками.

Для
решения этой задачи используются два
дополнительных управляющих сигнала:
RTS
(Request To Send — запрос на передачу данных)
и CTS
(Clear To Send — разрешение передачи данных).
Устройство, желающее начать передачу
данных, устанавливает активным сигнал
RTS.
Второе устройство, если оно освободило
линию и готово к приему, устанавливает
в ответ сигнал CTS.
Таким образом, в полудуплексном обмене
передача может начаться только при
получении активного сигнала CTS
от устройства, находящегося на другом
конце линии.

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

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

Кодирование и защита от ошибок

Существует три наиболее распространенных орудия борьбы с ошибками в процессе передачи данных:

• коды обнаружения ошибок;
• коды с коррекцией ошибок, называемые также схемами прямой коррекции ошибок (Forward Error Correction — FEC);
• протоколы с автоматическим запросом повторной передачи (Automatic Repeat Request — ARQ).

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

1) Методы обнаружения ошибок

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

Избыточную служебную информацию принято называть контрольной суммой, или контрольной последовательностью кадра (Frame Check Sequence, FCS). Контрольная сумма вычисляется как функция от основной информации, причем не обязательно путем суммирования. Принимающая сторона повторно вычисляет контрольную сумму кадра по известному алгоритму и в случае ее совпадения с контрольной суммой, вычисленной передающей стороной, делает вывод о том, что данные были переданы через сеть корректно. Рассмотрим несколько распространенных алгоритмов вычисления контрольной суммы, отличающихся вычислительной сложностью и способностью обнаруживать ошибки в данных.

Контроль по паритету представляет собой наиболее простой метод контроля данных. В то же время это наименее мощный алгоритм контроля, так как с его помощью можно обнаружить только одиночные ошибки в проверяемых данных. Метод заключается в суммировании по модулю 2 всех битов контролируемой информации. Нетрудно заметить, что для информации, состоящей из нечетного числа единиц, контрольная сумма всегда равна 1, а при четном числе единиц — 0. Например, для данных 100101011 результатом контрольного суммирования будет значение 1. Результат суммирования также представляет собой один дополнительный бит данных, который пересылается вместе с контролируемой информацией. При искажении в процессе пересылки любого бита исходных данных (или контрольного разряда) результат суммирования будет отличаться от принятого контрольного разряда, что говорит об ошибке.
Однако двойная ошибка, например 110101010, будет неверно принята за корректные данные. Поэтому контроль по паритету применяется к небольшим порциям данных, как правило, к каждому байту, что дает коэффициент избыточности для этого метода 1/8. Метод редко применяется в компьютерных сетях из-за значительной избыточности и невысоких диагностических способностей.

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

Циклический избыточный контроль (Cyclic Redundancy Check — CRC) является в настоящее время наиболее популярным методом контроля в вычислительных сетях (и не только в сетях; в частности, этот метод широко применяется при записи данных на гибкие и жесткие диски). Метод основан на рассмотрении исходных данных в виде одного многоразрядного двоичного числа. Например, кадр стандарта Ethernet, состоящий из 1024 байт, будет рассматриваться как одно число, состоящее из 8192 бит. Контрольной информацией считается остаток от деления этого числа на известный делитель R. Обычно в качестве делителя выбирается семнадцати- или тридцатитрехразрядное число, чтобы остаток от деления имел длину 16 разрядов (2 байт) или 32 разряда (4 байт). При получении кадра данных снова вычисляется остаток от деления на тот же делитель R, но при этом к данным кадра добавляется и содержащаяся в нем контрольная сумма.
Если остаток от деления на R равен нулю, то делается вывод об отсутствии ошибок в полученном кадре, в противном случае кадр считается искаженным.

Этот метод обладает более высокой вычислительной сложностью, но его диагностические возможности гораздо шире, чем у методов контроля по паритету. Метод CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном числе битов. Метод также обладает невысокой степенью избыточности. Например, для кадра Ethernet размером 1024 байта контрольная информация длиной 4 байта составляет только 0,4 %.

2) Методы коррекции ошибок

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

При применении любого избыточного кода не все комбинации кодов являются разрешенными. Например, контроль по паритету делает разрешенными только половину кодов. Если мы контролируем три информационных бита, то разрешенными 4-битными кодами с дополнением до нечетного количества единиц будут:

000 1, 001 0, 010 0, 011 1, 100 0, 101 1, 110 1, 111 0, то есть всего 8 кодов из 16 возможных.

Для того чтобы оценить количество дополнительных битов, необходимых для исправления ошибок, нужно знать так называемое расстояние Хемминга между разрешенными комбинациями кода. Расстоянием Хемминга называется минимальное число битовых разрядов, в которых отличается любая пара разрешенных кодов. Для схем контроля по паритету расстояние Хемминга равно 2.

Можно доказать, что если мы сконструировали избыточный код с расстоянием Хемминга, равным n, такой код будет в состоянии распознавать (n-1) -кратные ошибки и исправлять (n-1)/2 -кратные ошибки. Так как коды с контролем по паритету имеют расстояние Хемминга, равное 2, они могут только обнаруживать однократные ошибки и не могут исправлять ошибки.

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

Наиболее часто в современных системах связи применяется тип кодирования, реализуемый сверхточным кодирующим устройством (Сonvolutional coder), потому что такое кодирование несложно реализовать аппаратно с использованием линий задержки (delay) и сумматоров. В отличие от рассмотренного выше кода, который относится к блочным кодам без памяти, сверточный код относится к кодам с конечной памятью (Finite memory code); это означает, что выходная последовательность кодера является функцией не только текущего входного сигнала, но также нескольких из числа последних предшествующих битов. Длина кодового ограничения (Constraint length of a code) показывает, как много выходных элементов выходит из системы в пересчете на один входной. Коды часто характеризуются их эффективной степенью (или коэффициентом) кодирования (Code rate). Вам может встретиться сверточный код с коэффициентом кодирования 1/2.
Этот коэффициент указывает, что на каждый входной бит приходится два выходных. При сравнении кодов обращайте внимание на то, что, хотя коды с более высокой эффективной степенью кодирования позволяют передавать данные с более высокой скоростью, они, соответственно, более чувствительны к шуму.

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

3) Методы автоматического запроса повторной передачи

В простейшем случае защита от ошибок заключается только в их обнаружении. Система должна предупредить передатчик об обнаружении ошибки и необходимости повторной передачи. Такие процедуры защиты от ошибок известны как методы автоматического запроса повторной передачи (Automatic Repeat Request — ARQ). В беспроводных локальных сетях применяется процедура «запрос ARQ с остановками» (stop-and-wait ARQ).

В этом случае источник, пославший кадр, ожидает получения подтверждения (Acknowledgement — ACK), или, как еще его называют, квитанции, от приемника и только после этого посылает следующий кадр. Если же подтверждение не приходит в течение тайм-аута, то кадр (или подтверждение) считается утерянным и его передача повторяется. На
рис.
1.13 видно, что в этом случае производительность обмена данными ниже потенциально возможной; хотя передатчик и мог бы послать следующий кадр сразу же после отправки предыдущего, он обязан ждать прихода подтверждения.

Методы, обеспечивающие надежную доставку цифровых данных по ненадежным каналам связи Устранение ошибок передачи, вызванных атмосферой Земли ( слева), ученые Годдарда применили исправление ошибок Рида – Соломона (справа), которое обычно используется в компакт-дисках и DVD. Типичные ошибки включают отсутствие пикселей (белые) и ложные сигналы (черные). Белая полоса указывает на короткий период, когда передача была приостановлена.

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

Содержание

• 1 Определения
• 2 История
• 3 Введение
• 4 Типы исправления ошибок
  • 4.1 Автоматический повторный запрос (ARQ)
  • 4.2 Прямое исправление ошибок
  • 4.3 Гибридные схемы
• 5 Схемы обнаружения ошибок
  • 5.1 Кодирование на минимальном расстоянии
  • 5.2 Коды повторения
  • 5.3 Бит четности
  • 5.4 Контрольная сумма
  • 5.5 Циклическая проверка избыточности
  • 5.6 Криптографическая хеш-функция
  • 5.7 Ошибка код исправления
• 6 Приложения
  • 6.1 Интернет
  • 6.2 Связь в дальнем космосе
  • 6.3 Спутниковое вещание
  • 6.4 Хранение данных
  • 6.5 Память с исправлением ошибок
• 7 См. также
• 8 Ссылки
• 9 Дополнительная литература
• 10 Внешние ссылки

Определения

Обнаружение ошибок — это обнаружение ошибок, вызванных шумом или другими помехами во время передачи от передатчика к приемнику. Исправление ошибок — это обнаружение ошибок и восстановление исходных безошибочных данных.

История

Современная разработка кодов исправления ошибок приписывается Ричарду Хэммингу в 1947 году. Описание кода Хэмминга появилось в Математической теории коммуникации Клода Шеннона и было быстро обобщено Марселем Дж. Э. Голэем.

Введение

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

Хорошие характеристики контроля ошибок требуют, чтобы схема была выбрана на основе характеристик канала связи. Распространенные модели каналов включают в себя модели без памяти, в которых ошибки возникают случайно и с определенной вероятностью, и динамические модели, в которых ошибки возникают в основном в пакетах . Следовательно, коды обнаружения и исправления ошибок можно в целом различать между обнаружением / исправлением случайных ошибок и обнаружением / исправлением пакетов ошибок. Некоторые коды также могут подходить для сочетания случайных ошибок и пакетных ошибок.

Если характеристики канала не могут быть определены или сильно изменяются, схема обнаружения ошибок может быть объединена с системой для повторных передач ошибочных данных. Это известно как автоматический запрос на повторение (ARQ) и наиболее широко используется в Интернете. Альтернативный подход для контроля ошибок — это гибридный автоматический запрос на повторение (HARQ), который представляет собой комбинацию ARQ и кодирования с исправлением ошибок.

Типы исправления ошибок

Существует три основных типа исправления ошибок.

Автоматический повторный запрос (ARQ)

Автоматический повторный запрос (ARQ) — это метод контроля ошибок для передачи данных, который использует коды обнаружения ошибок, сообщения подтверждения и / или отрицательного подтверждения и тайм-ауты для обеспечения надежной передачи данных. Подтверждение — это сообщение, отправленное получателем, чтобы указать, что он правильно получил кадр данных.

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

Три типа протоколов ARQ: Stop-and-wait ARQ, Go-Back-N ARQ и Selective Repeat ARQ.

ARQ is подходит, если канал связи имеет переменную или неизвестную пропускную способность, например, в случае с Интернетом. Однако ARQ требует наличия обратного канала, что приводит к возможному увеличению задержки из-за повторных передач и требует обслуживания буферов и таймеров для повторных передач, что в случае перегрузка сети может вызвать нагрузку на сервер и общую пропускную способность сети.

Например, ARQ используется на коротковолновых радиоканалах в форме ARQ-E, или в сочетании с мультиплексированием как ARQ-M.

Прямое исправление ошибок

Прямое исправление ошибок (FEC) — это процесс добавления избыточных данных, таких как исправление ошибок code (ECC) в сообщение, чтобы оно могло быть восстановлено получателем, даже если в процессе передачи или при хранении был внесен ряд ошибок (в зависимости от возможностей используемого кода). Так как получатель не должен запрашивать у отправителя повторную передачу данных, обратный канал не требуется при прямом исправлении ошибок, и поэтому он подходит для симплексной связи, например вещание. Коды с исправлением ошибок часто используются в нижнем уровне связи, а также для надежного хранения на таких носителях, как CD, DVD, жесткие диски и RAM.

Коды с исправлением ошибок обычно различают между сверточными кодами и блочными кодами. :

• Сверточные коды обрабатываются побитно. Они особенно подходят для аппаратной реализации, а декодер Витерби обеспечивает оптимальное декодирование.
• Блочные коды обрабатываются на поблочной основе. Ранними примерами блочных кодов являются коды повторения, коды Хэмминга и многомерные коды контроля четности. За ними последовал ряд эффективных кодов, из которых коды Рида – Соломона являются наиболее известными из-за их широкого распространения в настоящее время. Турбокоды и коды с низкой плотностью проверки четности (LDPC) — это относительно новые конструкции, которые могут обеспечить почти оптимальную эффективность.

Теорема Шеннона — важная теорема при прямом исправлении ошибок и описывает максимальную информационную скорость, на которой возможна надежная связь по каналу, имеющему определенную вероятность ошибки или отношение сигнал / шум (SNR). Этот строгий верхний предел выражается в единицах пропускной способности канала . Более конкретно, в теореме говорится, что существуют такие коды, что с увеличением длины кодирования вероятность ошибки на дискретном канале без памяти может быть сделана сколь угодно малой при условии, что кодовая скорость меньше чем емкость канала. Кодовая скорость определяется как доля k / n из k исходных символов и n кодированных символов.

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

Гибридные схемы

Гибридный ARQ — это комбинация ARQ и прямого исправления ошибок. Существует два основных подхода:

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

Последний подход особенно привлекателен для канала стирания при использовании код бесскоростного стирания.

.

Схемы обнаружения ошибок

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

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

Кодирование с минимальным расстоянием

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

Коды повторения

A код повторения — это схема кодирования, которая повторяет биты по каналу для достижения безошибочной связи. Учитывая поток данных, которые необходимо передать, данные делятся на блоки битов. Каждый блок передается определенное количество раз. Например, чтобы отправить битовую комбинацию «1011», четырехбитовый блок можно повторить три раза, таким образом получая «1011 1011 1011». Если этот двенадцатибитовый шаблон был получен как «1010 1011 1011» — где первый блок не похож на два других, — произошла ошибка.

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

Бит четности

Бит четности — это бит, который добавляется к группе исходные биты, чтобы гарантировать, что количество установленных битов (т. е. битов со значением 1) в результате будет четным или нечетным. Это очень простая схема, которую можно использовать для обнаружения одного или любого другого нечетного числа (т. Е. Трех, пяти и т. Д.) Ошибок в выводе. Четное количество перевернутых битов сделает бит четности правильным, даже если данные ошибочны.

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

Контрольная сумма

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

Схемы контрольных сумм включают биты четности, контрольные цифры и проверки продольным избыточным кодом. Некоторые схемы контрольных сумм, такие как алгоритм Дамма, алгоритм Луна и алгоритм Верхоффа, специально разработаны для обнаружения ошибок, обычно вносимых людьми при записи или запоминание идентификационных номеров.

Проверка циклическим избыточным кодом

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

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

. Бит четности может рассматриваться как 1-битный частный случай. CRC.

Криптографическая хеш-функция

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

Код исправления ошибок

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

Коды с минимальным расстоянием Хэмминга d = 2 являются вырожденными случаями кодов с исправлением ошибок и могут использоваться для обнаружения одиночных ошибок. Бит четности является примером кода обнаружения одиночной ошибки.

Приложения

Приложения, которым требуется низкая задержка (например, телефонные разговоры), не могут использовать автоматический запрос на повторение (ARQ); они должны использовать прямое исправление ошибок (FEC). К тому времени, когда система ARQ обнаружит ошибку и повторно передаст ее, повторно отправленные данные прибудут слишком поздно, чтобы их можно было использовать.

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

Приложения, использующие ARQ, должны иметь канал возврата ; приложения, не имеющие обратного канала, не могут использовать ARQ.

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

Надежность и инженерная проверка также используют теорию кодов исправления ошибок.

Интернет

В типичном стеке TCP / IP ошибка управление осуществляется на нескольких уровнях:

• Каждый кадр Ethernet использует CRC-32 обнаружение ошибок. Фреймы с обнаруженными ошибками отбрасываются оборудованием приемника.
• Заголовок IPv4 содержит контрольную сумму , защищающую содержимое заголовка. Пакеты с неверными контрольными суммами отбрасываются в сети или на приемнике.
• Контрольная сумма не указана в заголовке IPv6, чтобы минимизировать затраты на обработку в сетевой маршрутизации и поскольку предполагается, что текущая технология канального уровня обеспечивает достаточное обнаружение ошибок (см. также RFC 3819 ).
• UDP, имеет дополнительную контрольную сумму, покрывающую полезную нагрузку и информацию об адресации в заголовки UDP и IP. Пакеты с неверными контрольными суммами отбрасываются сетевым стеком . Контрольная сумма не является обязательной для IPv4 и требуется для IPv6. Если не указано, предполагается, что уровень канала передачи данных обеспечивает желаемый уровень защиты от ошибок.
• TCP обеспечивает контрольную сумму для защиты полезной нагрузки и адресной информации в заголовках TCP и IP. Пакеты с неверными контрольными суммами отбрасываются сетевым стеком и в конечном итоге повторно передаются с использованием ARQ либо явно (например, как через тройное подтверждение ) или неявно из-за тайм-аута .

Телекоммуникации в дальнем космосе

Разработка кодов исправления ошибок была тесно связана с историей полетов в дальний космос из-за сильного ослабления мощности сигнала на межпланетных расстояниях и ограниченной мощности на борту космических зондов. В то время как ранние миссии отправляли свои данные в незашифрованном виде, начиная с 1968 года, цифровая коррекция ошибок была реализована в форме (субоптимально декодированных) сверточных кодов и кодов Рида – Маллера. Код Рида-Мюллера хорошо подходил к шуму, которому подвергался космический корабль (примерно соответствуя кривой ), и был реализован для космического корабля Mariner и использовался в миссиях между 1969 и 1977 годами.

Миссии «Вояджер-1 » и «Вояджер-2 «, начатые в 1977 году, были разработаны для доставки цветных изображений и научной информации с Юпитера и Сатурна. Это привело к повышенным требованиям к кодированию, и, таким образом, космический аппарат поддерживался (оптимально Витерби-декодированный ) сверточными кодами, которые могли быть сцеплены с внешним Голеем (24,12, код. Корабль «Вояджер-2» дополнительно поддерживал реализацию кода Рида-Соломона. Конкатенированный код Рида – Соломона – Витерби (RSV) позволил произвести очень мощную коррекцию ошибок и позволил космическому кораблю совершить длительное путешествие к Урану и Нептуну. После модернизации системы ECC в 1989 году оба корабля использовали кодирование V2 RSV.

Консультативный комитет по космическим информационным системам в настоящее время рекомендует использовать коды исправления ошибок, как минимум, аналогичные RSV-коду Voyager 2. Составные коды все больше теряют популярность в космических миссиях и заменяются более мощными кодами, такими как Турбо-коды или LDPC-коды.

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

Спутниковое вещание

Спрос на пропускную способность спутникового транспондера продолжает расти, чему способствует желание предоставлять телевидение (включая новые каналы и телевидение высокой четкости ) и данные IP. Доступность транспондеров и ограничения полосы пропускания ограничили этот рост. Емкость транспондера определяется выбранной схемой модуляции и долей мощности, потребляемой FEC.

Хранение данных

Коды обнаружения и исправления ошибок часто используются для повышения надежности носителей данных. «Дорожка четности» присутствовала на первом устройстве хранения данных на магнитной ленте в 1951 году. «Оптимальный прямоугольный код», используемый в записи с групповым кодированием, не только обнаруживает, но и корректирует однобитовые записи. ошибки. Некоторые форматы файлов, особенно архивные форматы, включают контрольную сумму (чаще всего CRC32 ) для обнаружения повреждений и усечения и могут использовать избыточность и / или четность files для восстановления поврежденных данных. Коды Рида-Соломона используются в компакт-дисках для исправления ошибок, вызванных царапинами.

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

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

Память DRAM может обеспечить более надежную защиту от программных ошибок, полагаясь на коды исправления ошибок. Такая память с исправлением ошибок, известная как память с защитой ECC или EDAC, особенно желательна для критически важных приложений, таких как научные вычисления, финансы, медицина и т. Д., А также для приложений дальнего космоса из-за повышенное излучение в космосе.

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

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

Помимо оборудования, обеспечивающего функции, необходимые для работы памяти ECC, операционные системы обычно содержат соответствующие средства отчетности, которые используются для предоставления уведомлений при прозрачном восстановлении программных ошибок. Увеличение количества программных ошибок может указывать на то, что модуль DIMM нуждается в замене, и такая обратная связь не была бы легко доступна без соответствующих возможностей отчетности. Одним из примеров является подсистема EDAC ядра Linux (ранее известная как Bluesmoke), которая собирает данные из компонентов компьютерной системы, поддерживающих проверку ошибок; Помимо сбора и отправки отчетов о событиях, связанных с памятью ECC, он также поддерживает другие ошибки контрольного суммирования, в том числе обнаруженные на шине PCI.

Некоторые системы также поддерживают очистку памяти.

См. также

Ссылки

Дополнительная литература

• Шу Линь; Дэниел Дж. Костелло младший (1983). Кодирование с контролем ошибок: основы и приложения. Прентис Холл. ISBN 0-13-283796-X.

Внешние ссылки

1.11 Методы контроля правильности передачи информации
При передаче информации по некачественным каналам связи возможно появление ошибок, то есть искажений передаваемой информа-
40
ции. Эти ошибки необходимо выявлять и исправлять. Контроль принимаемой информации может быть побайтным и пакетным.
Побайтный метод предполагает, что каждый передаваемый байт
дополняется битом четности (или нечетности), то есть в случае, когда
количество единиц в передаваемом информационном байте четное, то
бит равен 0, а если нечетное – то 1. Метод может применяться как при
байтовой, так и при пакетной передаче. Вероятность того, что ошибка
не будет обнаружена, довольно велика. К этому может привести наличие четного количества ошибок в информационных битах, а также одновременное искажение информационного и контрольного битов.
Пакетный метод сводится к тому, что в конце каждого передаваемого пакета добавляется контрольная сумма (длиной 8, 16 или 32 бита),
которая включает в себя информацию обо всех информационных битах
пакета. Метод подсчета контрольной суммы выбирается так, чтобы, с
одной стороны, ее просто было вычислить, а с другой стороны, чтобы
она достаточно надежно выявляла ошибки. Обычно используются контрольные суммы трех видов.
1. Сумма по модулю 2 всех байтов (или слов) пакета. Вычисление
идет по правилам: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0. При этом однократные
ошибки (то есть одна ошибка на пакет) обнаруживаются с вероятностью 100%, двукратные (две ошибки на пакет) – с вероятностью 7/8
(так как в случае, когда две ошибки попадают в один и тот же разряд,
они не могут быть обнаружены). Надо также учесть, что случаются искажения нескольких битов, которые данным методом выявляются довольно плохо. Этот вид контрольной суммы легко и быстро считается
программным путем, так как соответствующая команда вычисления
суммы по модулю 2 имеется практически у всех микропроцессоров.
2. Арифметическая сумма всех байтов (или слов) пакета. При
ее вычислении отбрасываются старшие разряды для сохранения заданной разрядности контрольной суммы (обычно 8 или 16). Однократные
41
ошибки обнаруживаются с вероятностью 100%. Вероятность необнаружения двукратных ошибок в наихудшем случае составляет
1/8 · 1/4 = 1/32. Такая наихудшая ситуация наблюдается, когда в каждом из 8 разрядов всех байт пакета или в каждом из 16 разрядов всех
слов пакета присутствует половина логических единиц и половина логических нулей. При этом двукратные ошибки не выявляются, когда в
одном разряде один из битов из 0 переходит вследствие ошибки в 1, а
другой бит в этом же разряде из 1 переходит в 0, что не изменяет общей
суммы.
3. Циклическая контрольная сумма (или циклический контроль по
избыточности, CRC – Cyclic Redundancy Check). Применение циклической контрольной суммы вызвано стремлением повысить качество контроля, то есть увеличить вероятность обнаружения ошибок. Циклическая контрольная сумма существенно сложнее в вычислении, однако
надежность данного метода контроля неизмеримо выше. При вычислении циклической контрольной суммы весь пакет рассматривается как
N-разрядное двоичное число, где N – количество бит в пакете. Для вычисления контрольной суммы это число делится по модулю 2 на некоторое постоянное простое число. Частное от этого деления отбрасывается, а остаток используется в качестве контрольной суммы. Данный
метод выявляет однократные ошибки с вероятностью 100%, а любое
другое количество ошибок с вероятностью p ≈ 1 − 2 − n , где n – количество разрядов контрольной суммы (формула верна при условии, что
N>>n). Разрядность полинома берется на единицу большая, чем требуемая разрядность контрольной суммы (остатка от деления).
42
2 АРХИТЕКТУРА TCP/IP
TCP/IP является одним из самых популярных стеков коммуникационных протоколов. Стек TCP/IP появился до появления модели взаимодействия открытых систем, и соответствие уровня стека TCP/IP уровням модели OSI достаточно условно.
Протоколы TCP/IP делятся на 4 уровня. Самый нижний (4 уровень)
называется уровнем межсетевых интерфейсов и соответствует физическому и канальному уровням модели OSI. Функции этого уровня включают в себя:
•
отображение IP-адресов в физические адреса сети;
• инкапсуляция IP-дейтаграмм в кадры для передачи по физическому каналу и извлечение дейтаграмм из кадров. Контроль безошибочности передачи не требуется;
•
определение метода доступа к среде передач;
•
определение представления данных в физической среде;
• прием и пересылка кадров.
Этот уровень не регламентируется в протоколах TCP/IP, но поддерживает все популярные стандарты физического и канального уровней.
Третий уровень, называемый уровнем межсетевого взаимодействия,
отвечает за передачу дейтаграмм с использованием различных локальных сетей, территориальных сетей и линий специальных связей. Этот
уровень соответствует третьему уровню модели OSI. В качестве основного протокола этого уровня используется протокол IP. Протокол IP
изначально создавался как протокол передачи пакетов в составных се43
тях, состоящих из большого количества локальных сетей, объединенных между собой. Поэтому протокол IP хорошо работает в сетях со
сложной структурой. К третьему уровню также относятся все протоколы, связанные с составлением ими модификации и таблиц с маршрутизацией, т.е. такие протоколы RIP (Routing Internet Protocol), OSPF(Оpen
Shortest Path First) – протоколы сбора маршрутной информации, ICMP
(Internet Control Message Protocol) – протокол межсетевых управляющих сообщений.
Протоколы ICMP служат для обеспечения обратной связи, т.е. сообщение об ошибках при передаче, например, между двумя компьютерами, шлюзом и маршрутизатором.
На втором уровне работают протоколы TCP и UDP. Этот уровень
называется основным. TCP – протокол управления передачи. UDP –
протокол пользовательских дейтаграмм. Протокол TCP обеспечивает
устойчивое виртуальное соединение между удаленными сетевыми процессами, а протокол UDP – передачу прикладных пакетов методом дейтаграмм, т.е. без установления соединений. Протокол UDP требует
меньше накладных расходов, чем протокол TCP.
Протоколы UDP практически не выполняют никаких особых функций дополнительно к функциям межсетевого уровня. Протокол UDP
используется в двух основных случаях:
•
при пересылке коротких сообщений, т.е. когда накладные рас-
ходы на установление соединения и проверку успешной доставки данных выше расходов на повторную передачу сообщений;
•
если сам процесс приложения обеспечивает установление со-
единения и проверку доставки пакетов (NFS, TFTP, DNS).
Верхний уровень называется прикладным и обеспечивает взаимодействие с пользователем. За время своего использования стек TCP/IP
накопил большое количество протоколов и сервисов прикладного
уровня: FTP, TFTP, HTTP, SMTP, POP3, Telnet и т.д.
44
2.1 Протокол IP. Адресация
Функции протокола IP определены в стандарте RFC-791 и заключаются в том, что протокол IP обеспечивает передачу блоков данных,
называемых дейтаграммами, от отправителя к получателю, где отправители и получатели являются компьютерами, идентифицируемыми
адресами фиксированной длины (IP-адресами). Протокол IP обеспечивает также при необходимости фрагментацию и сборку дейтаграмм для
передачи данных через сети с малым размером пакетов.
Протокол IP не подтверждает доставку данных, не контролирует
целостность данных и не производит операции обмена служебными
сообщениями, подтверждающими установление соединения с узлом
назначения и его готовность к приему данных. Протокол IP обрабатывает каждую дейтаграмму как не имеющую связи с другими дейтаграммами сети. После отправки дейтаграммы она никак не контролируется отправителем на уровне протокола IP. Если дейтаграмма не может
быть доставлена, то она уничтожается, а узел, уничтоживший дейтаграмму, может отправить отправителю специальное ICMP-сообщение,
содержащее информацию о причине сбоя. Гарантию правильной передачи данных предоставляют протоколы вышестоящего уровня. Протоколом IP осуществляется маршрутизация дейтаграмм, т.е. определение
пути следования дейтаграммы от одного узла сети к другому на основании адреса получателя.
IP-адрес является некоторым числом, выраженным в двоичной системе. Этот адрес содержит 4 байта или 32 двоичных разряда. Принято
каждый байт адресной последовательности записывать в виде десятичного числа.
Каждое из этих чисел содержит определённую адресную информацию: адрес сети и номер хоста.
Существует 5 классов IP-адресов, которые описываются количеством разрядов в сетевом номере и номере хост-ЭВМ. Класс адреса опре45
деляется значением его первого байта. В табл. 2.1 и 2.2 приведены существующие классы IP-адресов и их сравнение.
Т а б л и ц а 2.1. Классы IP-адресов
Разряд
адреса
A
B
1
1
2
3
4
5
6
7
8
15
номер сети (7 бит)
16
1
1
D
1
1
1
E
1
1
1
1
24
31
номер хоста (24 бита)
номер сети (7 бит)
C
23
номер хоста (16 бит)
номер
хоста
(8 бит)
номер сети (7 бит)
групповой адрес (28 бит)
зарезервировано
Т а б л и ц а 2.2. Сравнение классов IP-адресов
Класс
Диапазон
значений
первого
байта
адреса
Возможное
количество
сетей
Максимальное
количество
хостов в сети
A
1÷126
126
16 777 214
B
128÷191
16 382
65 534
C
192÷223
2 097 150
254
D
224÷239
—
—
Групповые
обращения
E
240÷247
—
—
Зарезервировано
Предназначение
Распределение
IP-адресов
в зависимости
от размеров сетей
Адреса класса A предназначены для использования в больших сетях,
содержащих более чем 216 хост-машин. Адреса класса B предназначены
для сетей среднего размера, содержащих от 28 до 216 хост-машин. Адреса класса C применяются в сетях с небольшим количеством ПЭВМ
46
(до 254), например, в ЛВС. Адреса класса D предназначены для обращения к группам хост-машин. Адреса класса E были зарезервированы
на будущее.
В настоящее время международные организации, занимающиеся
распределением адресного пространства, отказались от применения
классов адресов, так как в случае выделения адресного пространства
малым по объёму сетям (16, 32, 64 хоста) слишком много адресного
пространства расходуется впустую.
Рассмотрим некоторые особенности адресации в Internet.
Согласно принятому в Internet правилу хост-ЭВМ нельзя присваивать номер 0 (он описывает всю сеть в целом) и 255 — адрес широковещательной передачи. Кроме того, IP-адрес, первый байт которого равен 127, используется для тестирования программ и взаимодействия
процессов в рамках одной хост-ЭВМ, поэтому запрещается присваивать хостам номера, начинающиеся со 127.
Помимо этого существует ряд адресов, которые используются для
организации частных сетей, то есть локальных сетей, осуществляющих
обмен данными по протоколам TCP/IP. Применение таких адресов также позволяет легко интегрировать подобную локальную сеть в Internet
при помощи только одного «реального» IP-адреса, выделенного маршрутизатору сети. Все пакеты, проходящие через этот маршрутизатор,
автоматически получают в качестве адреса отправителя адрес маршрутизатора и, таким образом, могут быть корректно обработаны другими
маршрутизаторами сети. При этом маршрутизатор, занимающийся преобразованием адресов, ведёт специальную таблицу, в которой записывается с какого адреса «внутренней» сети на какой адрес «внешней»
сети был послан запрос (а также ряд других сведений). При получении
от «внешнего» сервера ответа (пакета с некоторыми данными), маршрутизатор сверяется с таблицей и если находит тот адрес, который
запросил пакет, то перенаправляет его получателю. В противном случае пакет уничтожается и противоположная сторона информируется об
47
этом по протоколу ICMP. Данный подход может быть также полезен
для защиты от несанкционированного доступа как «снаружи» сети, так
и «изнутри» (имеется в виду несанкционированная передача некой информации из сети «наружу»). В соответствии с RFC 1918 это диапазоны 10.0.0.0 ÷ 10.255.255.255, 172.16.0.0 ÷ 172.31.255.255 и 192.168.0.0 ÷
192.168.255.255.
2.2 Доменная система адресов
На начальном этапе создания сети Internet составлялся полный список, куда включались имена всех хостов, подключаемых к сети. Однако
вследствие развития Internet, а также частого изменения её топологии,
оказалось невозможным постоянно обновлять такой список. Это привело к созданию доменной системы адресов (имён): DNS (Domain Name
System). Эта система адресации разделяет все адреса по иерархическому принципу, объединяя их в домены (от английского domain – область). Каждый домен представляет определённую группу хостов, объединенных по географическому или тематическому признаку. Полный
доменный адрес обозначается как FQDN (Fully Qualified Domain Name)
и читается в обратном порядке относительно цифрового адреса: если
IP-адрес начинается с номера сети, то доменный адрес начинается с
имени хост-машины. Например, адрес вида
hostname.lab.university.ru
означает: хост hostname сети lab, входящей в домен university, который,
в свою очередь, входит в состав домена верхнего (первого) уровня ru.
Домен ru означает Российскую Федерацию. Существуют домены верхнего уровня, выделенные по географическим и тематическим признакам:
− аrра – обратный (reverse) DNS;
− com – коммерческие организации;
48
− edu – образовательные учреждения и университеты;
− gov – невоенные правительственные учреждения;
− info – информационные ресурсы;
− mil – военные правительственные учреждения;
− net – сети (крупные сети, входящие в сеть Интернет);
− org – некоммерческие организации;
− двухбуквенные обозначения стран (ru, uk, cn и т.д.).
Для обработки траектории поиска в отдельных доменах имеются
специальные серверы имен, которые обеспечивают преобразование адресов доменной системы имен в цифровую.
Возможны случаи, когда один IP-адрес соответствует двум доменным именам. Это характерно, например, для web-серверов, предоставляющих услуги хостинга. В некоторых случаях несколько IP-адресов
могут ассоциироваться с одним доменным именем. Однако наличие
доменного имени не является обязательным в отличие от цифрового IPадреса, без которого хост-машина не может подключиться к сети.
49

In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.

Definitions[edit]

Error detection is the detection of errors caused by noise or other impairments during transmission from the transmitter to the receiver.

Error correction is the detection of errors and reconstruction of the original, error-free data.

History[edit]

In classical antiquity, copyists of the Hebrew Bible were paid for their work according to the number of stichs (lines of verse). As the prose books of the Bible were hardly ever written in stichs, the copyists, in order to estimate the amount of work, had to count the letters.^[1] This also helped ensure accuracy in the transmission of the text with the production of subsequent copies.^[2][3] Between the 7th and 10th centuries CE a group of Jewish scribes formalized and expanded this to create the Numerical Masorah to ensure accurate reproduction of the sacred text. It included counts of the number of words in a line, section, book and groups of books, noting the middle stich of a book, word use statistics, and commentary.^[1] Standards became such that a deviation in even a single letter in a Torah scroll was considered unacceptable.^[4] The effectiveness of their error correction method was verified by the accuracy of copying through the centuries demonstrated by discovery of the Dead Sea Scrolls in 1947–1956, dating from c. 150 BCE-75 CE.^[5]

The modern development of error correction codes is credited to Richard Hamming in 1947.^[6] A description of Hamming’s code appeared in Claude Shannon’s A Mathematical Theory of Communication^[7] and was quickly generalized by Marcel J. E. Golay.^[8]

Principles[edit]

All error-detection and correction schemes add some redundancy (i.e., some extra data) to a message, which receivers can use to check consistency of the delivered message and to recover data that has been determined to be corrupted. Error detection and correction schemes can be either systematic or non-systematic. In a systematic scheme, the transmitter sends the original (error-free) data and attaches a fixed number of check bits (or parity data), which are derived from the data bits by some encoding algorithm. If error detection is required, a receiver can simply apply the same algorithm to the received data bits and compare its output with the received check bits; if the values do not match, an error has occurred at some point during the transmission. If error correction is required, a receiver can apply the decoding algorithm to the received data bits and the received check bits to recover the original error-free data. In a system that uses a non-systematic code, the original message is transformed into an encoded message carrying the same information and that has at least as many bits as the original message.

Good error control performance requires the scheme to be selected based on the characteristics of the communication channel. Common channel models include memoryless models where errors occur randomly and with a certain probability, and dynamic models where errors occur primarily in bursts. Consequently, error-detecting and correcting codes can be generally distinguished between random-error-detecting/correcting and burst-error-detecting/correcting. Some codes can also be suitable for a mixture of random errors and burst errors.

If the channel characteristics cannot be determined, or are highly variable, an error-detection scheme may be combined with a system for retransmissions of erroneous data. This is known as automatic repeat request (ARQ), and is most notably used in the Internet. An alternate approach for error control is hybrid automatic repeat request (HARQ), which is a combination of ARQ and error-correction coding.

Types of error correction[edit]

There are three major types of error correction:^[9]

Automatic repeat request[edit]

Automatic repeat request (ARQ) is an error control method for data transmission that makes use of error-detection codes, acknowledgment and/or negative acknowledgment messages, and timeouts to achieve reliable data transmission. An acknowledgment is a message sent by the receiver to indicate that it has correctly received a data frame.

Usually, when the transmitter does not receive the acknowledgment before the timeout occurs (i.e., within a reasonable amount of time after sending the data frame), it retransmits the frame until it is either correctly received or the error persists beyond a predetermined number of retransmissions.

Three types of ARQ protocols are Stop-and-wait ARQ, Go-Back-N ARQ, and Selective Repeat ARQ.

ARQ is appropriate if the communication channel has varying or unknown capacity, such as is the case on the Internet. However, ARQ requires the availability of a back channel, results in possibly increased latency due to retransmissions, and requires the maintenance of buffers and timers for retransmissions, which in the case of network congestion can put a strain on the server and overall network capacity.^[10]

For example, ARQ is used on shortwave radio data links in the form of ARQ-E, or combined with multiplexing as ARQ-M.

Forward error correction[edit]

Forward error correction (FEC) is a process of adding redundant data such as an error-correcting code (ECC) to a message so that it can be recovered by a receiver even when a number of errors (up to the capability of the code being used) are introduced, either during the process of transmission or on storage. Since the receiver does not have to ask the sender for retransmission of the data, a backchannel is not required in forward error correction. Error-correcting codes are used in lower-layer communication such as cellular network, high-speed fiber-optic communication and Wi-Fi,^[11][12] as well as for reliable storage in media such as flash memory, hard disk and RAM.^[13]

Error-correcting codes are usually distinguished between convolutional codes and block codes:

• Convolutional codes are processed on a bit-by-bit basis. They are particularly suitable for implementation in hardware, and the Viterbi decoder allows optimal decoding.
• Block codes are processed on a block-by-block basis. Early examples of block codes are repetition codes, Hamming codes and multidimensional parity-check codes. They were followed by a number of efficient codes, Reed–Solomon codes being the most notable due to their current widespread use. Turbo codes and low-density parity-check codes (LDPC) are relatively new constructions that can provide almost optimal efficiency.

Shannon’s theorem is an important theorem in forward error correction, and describes the maximum information rate at which reliable communication is possible over a channel that has a certain error probability or signal-to-noise ratio (SNR). This strict upper limit is expressed in terms of the channel capacity. More specifically, the theorem says that there exist codes such that with increasing encoding length the probability of error on a discrete memoryless channel can be made arbitrarily small, provided that the code rate is smaller than the channel capacity. The code rate is defined as the fraction k/n of k source symbols and n encoded symbols.

The actual maximum code rate allowed depends on the error-correcting code used, and may be lower. This is because Shannon’s proof was only of existential nature, and did not show how to construct codes that are both optimal and have efficient encoding and decoding algorithms.

Hybrid schemes[edit]

Hybrid ARQ is a combination of ARQ and forward error correction. There are two basic approaches:^[10]

• Messages are always transmitted with FEC parity data (and error-detection redundancy). A receiver decodes a message using the parity information and requests retransmission using ARQ only if the parity data was not sufficient for successful decoding (identified through a failed integrity check).
• Messages are transmitted without parity data (only with error-detection information). If a receiver detects an error, it requests FEC information from the transmitter using ARQ and uses it to reconstruct the original message.

The latter approach is particularly attractive on an erasure channel when using a rateless erasure code.

Types of error detection[edit]

Error detection is most commonly realized using a suitable hash function (or specifically, a checksum, cyclic redundancy check or other algorithm). A hash function adds a fixed-length tag to a message, which enables receivers to verify the delivered message by recomputing the tag and comparing it with the one provided.

There exists a vast variety of different hash function designs. However, some are of particularly widespread use because of either their simplicity or their suitability for detecting certain kinds of errors (e.g., the cyclic redundancy check’s performance in detecting burst errors).

Minimum distance coding[edit]

A random-error-correcting code based on minimum distance coding can provide a strict guarantee on the number of detectable errors, but it may not protect against a preimage attack.

Repetition codes[edit]

A repetition code is a coding scheme that repeats the bits across a channel to achieve error-free communication. Given a stream of data to be transmitted, the data are divided into blocks of bits. Each block is transmitted some predetermined number of times. For example, to send the bit pattern 1011, the four-bit block can be repeated three times, thus producing 1011 1011 1011. If this twelve-bit pattern was received as 1010 1011 1011 – where the first block is unlike the other two – an error has occurred.

A repetition code is very inefficient and can be susceptible to problems if the error occurs in exactly the same place for each group (e.g., 1010 1010 1010 in the previous example would be detected as correct). The advantage of repetition codes is that they are extremely simple, and are in fact used in some transmissions of numbers stations.^[14][15]

Parity bit[edit]

A parity bit is a bit that is added to a group of source bits to ensure that the number of set bits (i.e., bits with value 1) in the outcome is even or odd. It is a very simple scheme that can be used to detect single or any other odd number (i.e., three, five, etc.) of errors in the output. An even number of flipped bits will make the parity bit appear correct even though the data is erroneous.

Parity bits added to each word sent are called transverse redundancy checks, while those added at the end of a stream of words are called longitudinal redundancy checks. For example, if each of a series of m-bit words has a parity bit added, showing whether there were an odd or even number of ones in that word, any word with a single error in it will be detected. It will not be known where in the word the error is, however. If, in addition, after each stream of n words a parity sum is sent, each bit of which shows whether there were an odd or even number of ones at that bit-position sent in the most recent group, the exact position of the error can be determined and the error corrected. This method is only guaranteed to be effective, however, if there are no more than 1 error in every group of n words. With more error correction bits, more errors can be detected and in some cases corrected.

There are also other bit-grouping techniques.

Checksum[edit]

A checksum of a message is a modular arithmetic sum of message code words of a fixed word length (e.g., byte values). The sum may be negated by means of a ones’-complement operation prior to transmission to detect unintentional all-zero messages.

Checksum schemes include parity bits, check digits, and longitudinal redundancy checks. Some checksum schemes, such as the Damm algorithm, the Luhn algorithm, and the Verhoeff algorithm, are specifically designed to detect errors commonly introduced by humans in writing down or remembering identification numbers.

Cyclic redundancy check[edit]

A cyclic redundancy check (CRC) is a non-secure hash function designed to detect accidental changes to digital data in computer networks. It is not suitable for detecting maliciously introduced errors. It is characterized by specification of a generator polynomial, which is used as the divisor in a polynomial long division over a finite field, taking the input data as the dividend. The remainder becomes the result.

A CRC has properties that make it well suited for detecting burst errors. CRCs are particularly easy to implement in hardware and are therefore commonly used in computer networks and storage devices such as hard disk drives.

The parity bit can be seen as a special-case 1-bit CRC.

Cryptographic hash function[edit]

The output of a cryptographic hash function, also known as a message digest, can provide strong assurances about data integrity, whether changes of the data are accidental (e.g., due to transmission errors) or maliciously introduced. Any modification to the data will likely be detected through a mismatching hash value. Furthermore, given some hash value, it is typically infeasible to find some input data (other than the one given) that will yield the same hash value. If an attacker can change not only the message but also the hash value, then a keyed hash or message authentication code (MAC) can be used for additional security. Without knowing the key, it is not possible for the attacker to easily or conveniently calculate the correct keyed hash value for a modified message.

Error correction code[edit]

Any error-correcting code can be used for error detection. A code with minimum Hamming distance, d, can detect up to d − 1 errors in a code word. Using minimum-distance-based error-correcting codes for error detection can be suitable if a strict limit on the minimum number of errors to be detected is desired.

Codes with minimum Hamming distance d = 2 are degenerate cases of error-correcting codes and can be used to detect single errors. The parity bit is an example of a single-error-detecting code.

Applications[edit]

Applications that require low latency (such as telephone conversations) cannot use automatic repeat request (ARQ); they must use forward error correction (FEC). By the time an ARQ system discovers an error and re-transmits it, the re-sent data will arrive too late to be usable.

Applications where the transmitter immediately forgets the information as soon as it is sent (such as most television cameras) cannot use ARQ; they must use FEC because when an error occurs, the original data is no longer available.

Applications that use ARQ must have a return channel; applications having no return channel cannot use ARQ.

Applications that require extremely low error rates (such as digital money transfers) must use ARQ due to the possibility of uncorrectable errors with FEC.

Reliability and inspection engineering also make use of the theory of error-correcting codes.^[16]

Internet[edit]

In a typical TCP/IP stack, error control is performed at multiple levels:

• Each Ethernet frame uses CRC-32 error detection. Frames with detected errors are discarded by the receiver hardware.
• The IPv4 header contains a checksum protecting the contents of the header. Packets with incorrect checksums are dropped within the network or at the receiver.
• The checksum was omitted from the IPv6 header in order to minimize processing costs in network routing and because current link layer technology is assumed to provide sufficient error detection (see also RFC 3819).
• UDP has an optional checksum covering the payload and addressing information in the UDP and IP headers. Packets with incorrect checksums are discarded by the network stack. The checksum is optional under IPv4, and required under IPv6. When omitted, it is assumed the data-link layer provides the desired level of error protection.
• TCP provides a checksum for protecting the payload and addressing information in the TCP and IP headers. Packets with incorrect checksums are discarded by the network stack and eventually get retransmitted using ARQ, either explicitly (such as through three-way handshake) or implicitly due to a timeout.

Deep-space telecommunications[edit]

The development of error-correction codes was tightly coupled with the history of deep-space missions due to the extreme dilution of signal power over interplanetary distances, and the limited power availability aboard space probes. Whereas early missions sent their data uncoded, starting in 1968, digital error correction was implemented in the form of (sub-optimally decoded) convolutional codes and Reed–Muller codes.^[17] The Reed–Muller code was well suited to the noise the spacecraft was subject to (approximately matching a bell curve), and was implemented for the Mariner spacecraft and used on missions between 1969 and 1977.

The Voyager 1 and Voyager 2 missions, which started in 1977, were designed to deliver color imaging and scientific information from Jupiter and Saturn.^[18] This resulted in increased coding requirements, and thus, the spacecraft were supported by (optimally Viterbi-decoded) convolutional codes that could be concatenated with an outer Golay (24,12,8) code. The Voyager 2 craft additionally supported an implementation of a Reed–Solomon code. The concatenated Reed–Solomon–Viterbi (RSV) code allowed for very powerful error correction, and enabled the spacecraft’s extended journey to Uranus and Neptune. After ECC system upgrades in 1989, both crafts used V2 RSV coding.

The Consultative Committee for Space Data Systems currently recommends usage of error correction codes with performance similar to the Voyager 2 RSV code as a minimum. Concatenated codes are increasingly falling out of favor with space missions, and are replaced by more powerful codes such as Turbo codes or LDPC codes.

The different kinds of deep space and orbital missions that are conducted suggest that trying to find a one-size-fits-all error correction system will be an ongoing problem. For missions close to Earth, the nature of the noise in the communication channel is different from that which a spacecraft on an interplanetary mission experiences. Additionally, as a spacecraft increases its distance from Earth, the problem of correcting for noise becomes more difficult.

Satellite broadcasting[edit]

The demand for satellite transponder bandwidth continues to grow, fueled by the desire to deliver television (including new channels and high-definition television) and IP data. Transponder availability and bandwidth constraints have limited this growth. Transponder capacity is determined by the selected modulation scheme and the proportion of capacity consumed by FEC.

Data storage[edit]

Error detection and correction codes are often used to improve the reliability of data storage media.^[19] A parity track capable of detecting single-bit errors was present on the first magnetic tape data storage in 1951. The optimal rectangular code used in group coded recording tapes not only detects but also corrects single-bit errors. Some file formats, particularly archive formats, include a checksum (most often CRC32) to detect corruption and truncation and can employ redundancy or parity files to recover portions of corrupted data. Reed-Solomon codes are used in compact discs to correct errors caused by scratches.

Modern hard drives use Reed–Solomon codes to detect and correct minor errors in sector reads, and to recover corrupted data from failing sectors and store that data in the spare sectors.^[20] RAID systems use a variety of error correction techniques to recover data when a hard drive completely fails. Filesystems such as ZFS or Btrfs, as well as some RAID implementations, support data scrubbing and resilvering, which allows bad blocks to be detected and (hopefully) recovered before they are used.^[21] The recovered data may be re-written to exactly the same physical location, to spare blocks elsewhere on the same piece of hardware, or the data may be rewritten onto replacement hardware.

Error-correcting memory[edit]

Dynamic random-access memory (DRAM) may provide stronger protection against soft errors by relying on error-correcting codes. Such error-correcting memory, known as ECC or EDAC-protected memory, is particularly desirable for mission-critical applications, such as scientific computing, financial, medical, etc. as well as extraterrestrial applications due to the increased radiation in space.

Error-correcting memory controllers traditionally use Hamming codes, although some use triple modular redundancy. Interleaving allows distributing the effect of a single cosmic ray potentially upsetting multiple physically neighboring bits across multiple words by associating neighboring bits to different words. As long as a single-event upset (SEU) does not exceed the error threshold (e.g., a single error) in any particular word between accesses, it can be corrected (e.g., by a single-bit error-correcting code), and the illusion of an error-free memory system may be maintained.^[22]

In addition to hardware providing features required for ECC memory to operate, operating systems usually contain related reporting facilities that are used to provide notifications when soft errors are transparently recovered. One example is the Linux kernel’s EDAC subsystem (previously known as Bluesmoke), which collects the data from error-checking-enabled components inside a computer system; besides collecting and reporting back the events related to ECC memory, it also supports other checksumming errors, including those detected on the PCI bus.^[23][24][25] A few systems^[specify] also support memory scrubbing to catch and correct errors early before they become unrecoverable.

See also[edit]

• Berger code
• Burst error-correcting code
• ECC memory, a type of computer data storage
• Link adaptation
• List of algorithms § Error detection and correction
• List of hash functions

References[edit]

Further reading[edit]

• Shu Lin; Daniel J. Costello, Jr. (1983). Error Control Coding: Fundamentals and Applications. Prentice Hall. ISBN 0-13-283796-X.
• 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

External links[edit]

• The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, contains chapters on elementary error-correcting codes; on the theoretical limits of error-correction; and on the latest state-of-the-art error-correcting codes, including low-density parity-check codes, turbo codes, and fountain codes.
• ECC Page — implementations of popular ECC encoding and decoding routines