Пакеты фреймы обнаружение ошибок

Протоколы сетевого уровня обеспечивают
логическую адресацию и определение
маршрута. Методы логической адресации
зависят от набора протоколов, но основные
принципы остаются одинаковыми. Адреса
сетевого уровня применяются в основном
для указания местонахождения хоста.
Эта задача обычно решается путем
разделения адреса на две части: роле
группы и поле хоста. Вместе эти поля
полностью описывают хост, но лишь в
контексте группы, к которой он относится.
Такое разделение адреса позволяет
каждому хосту учитывать только наличие
других хостов в его группе и применять
для передачи пакетов от одной группы к
другой специализированные устройства,
называемые маршрутизаторами. К числу
широко применяемых протоколов сетевого
уровня относятся IP и IPX.

Уровень 2 – КАНАЛЬНЫЙ

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

Устранение коллизий.

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

Физическая адресация

Все устройства должны иметь физический
адрес. В технологиях локальной сети
таковым обычно является МАС – адрес.
Физический адрес формируется таким
образом, чтобы он мог однозначно
обозначить определенное устройство,
позволяя отличить его от всех прочих
устройств в мире. МАС – адрес (называемый
также адресом Ethernet, адресом
локальной сети, физическим, аппаратным
адресом) представляет собой 48-битовый
адрес, который обычно записывается в
виде 12 шестнадцатеричных цифр, таких
как 01-02-03-АВ-CD-EF.
Первые шесть определяют изготовителя
устройства, а последние шесть – отдельное
устройство, выпущенное этим изготовителем.
Структура МАС адреса показана на рисунке.

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

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

Еще одна функция канального уровня,
обнаружение ошибок, позволяет определить,
не произошло ли искажение пакета во
время передачи. Для этого перед отправкой
пакета на удаленный компьютер к нему
добавляют концевик (так называемое поле
с контрольной суммой в конце пакета) с
последовательностью FCS.
Метод контроля с применением FCS
предусматривает использование
циклического избыточного кода (Cyclic
Redundancy Check
– CRC) для выработки
цифрового значения и размещение этого
значения в концевике пакета. После
прибытия пакета к получателю извлекается
значение FCS и снова
применяется тот же алгоритм, с помощью
которого было вычислено это первоначальное
значение. Если пакет подвергся каким
либо изменениям, прежнее и новое значение
FCS не совпадают, пакет
отбрасывается как ошибочный.

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

Фреймирование.

Термин фреймирование используется для
описания организации элементов в пакете
(пакет, передаваемый по сети, оформляется
в виде фрейма). Эта задача является очень
важной. Чтобы понять, с чем это связано,
необходимо рассмотреть, как происходит
передача данных физическим устройством.
Прежде всего следует учесть, что все
данные, передаваемые по кабелям сети,
являются просто комбинацией битов 0
и 1. Поэтому при получении устройством
цепочки битов, такой как
011010010010010000111000111 и т.д., оно должно
определить, какая часть цепочки
соответствует МАС – адресу, данным или
последовательности FCS.
Для этого требуется ключ. Физический
формат пакета показан на рисунке.

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

Соседние файлы в папке 2 семестр

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

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

Сетевой пакет может состоять из стартовых бит (преамбулы), заголовков (headers), нагрузки (payload или body) и прицепа (trailer или footer). Между пакетами, посылаемыми в сеть, обычно соблюдается межкадровый интервал. Максимальная длина нагрузки называется maximum transmission unit (MTU).

Существует возможность фрагментации пакета — генерация двух сетевых пакетов из одного. Происходит при превышении длины кадра MTU интерфейса через который он в данный момент проходит. Фрагментация (и её запрещение) поддерживается протоколом IP и не предусмотрена в большинстве других протоколов. Если сетевой адаптер обнаруживает кадр длиннее его media MTU, то этот кадр обычно отбрасывается. Такое случается, если на одном хосте разрешены jumbo-кадры, а на другом — нет. Фрагментация IP-пакета увеличивает нагрузку на центральный процессор и снижает скорость передачи полезных данных этого пакета (на 2÷50 % в Ethernet сети в зависимости от длины кадра), поэтому её стараются избегать. При потере любого фрагмента повторно должна быть передана вся последовательность, что является дополнительным риском снижения скорости. Сборка всех частей в исходный пакет производится только адресатом, даже если на каком-то участке сети MTU больше требуемого. Фрагментация пакетов может быть использована в сетевых атаках и зондировании сетей.

Разметка пакета

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

Различные коммуникационные протоколы используют разные соглашения для разделения элементов и для форматирования данных. В протоколе «двоичной синхронной передачи» пакет отформатирован в 8-битных байтах, а для разделения элементов используются специальные символы. В других протоколах, таких как Ethernet, зафиксировано начало заголовка и элементов данных, их расположение относительно начала пакета. Некоторые протоколы форматируют информацию на уровне битов, а не байтов.

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

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

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

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

Хвостовая часть пакета часто содержит данные проверки ошибок, возникших во время передачи пакета по сети.

Адрес хоста

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

Сравнение пакетов и дейтаграмм

Термин пакет распространяется на любое сообщение, форматированное как пакет, тогда как термин дейтаграмма
обычно используется для пакетов «ненадёжных» служб. «Надёжной» является служба, которая уведомляет пользователя, если доставка не удалась, тогда как «ненадёжная» такого уведомления пользователя не делает. Например, IP не обеспечивает надёжный сервис, а TCP и IP вместе его обеспечивают, тогда как UDP с IP надёжный сервис не обеспечивают. Все эти протоколы используют пакеты, но UDP-пакеты, как правило, называют дейтаграммами.

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

Разработчики CYCLADES и ALOHAnet продемонстрировали, что можно построить эффективную компьютерную сеть, не обеспечивая надёжную передачу пакетов. Этот опыт позже был использован конструкторами Ethernet.

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

Пример: IP пакет

IP-пакеты состоят из заголовка и полезной нагрузки. Заголовок пакета IPv4 состоит из:

1. 4 бита содержат версию пакета: IPv4 или IPv6.
2. 4 бита содержат длину интернет-заголовка, которая измеряется отрезками по 4 байта (например, 5 означает 20 байт).
3. 8 бит содержат тип обслуживания, известный также как качество обслуживания (QoS), описывающее приоритеты пакета.
4. 16 бит содержат длину пакета в байтах.
5. 16 бит содержат тег идентификации, помогающие восстановить пакет из нескольких фрагментов.
6. 3 бита содержат нуль, флаг разрешения фрагментации пакета (DF: не фрагментировать), а также флаг разрешения дальнейшей фрагментации (MF: фрагментировать дальше).
7. 13 бит содержат смещение фрагмента, поле для идентификации положение фрагмента в исходном пакете.
8. 8 бит содержат время жизни (TTL), которое определяет количество переходов (через маршрутизаторы, компьютеры и сетевые устройства), разрешённых пройти пакету, прежде чем он исчезнет (например, пакету с TTL 16 разрешено пройти не более 16 маршрутизаторов, чтобы добраться до места назначения).
9. 8 бит содержат протокол (TCP, UDP, ICMP и т. д.).
10. 16 бит содержат контрольную сумму заголовка, используемую при обнаружении ошибок.
11. 32 бит содержат IP-адрес источника.
12. 32 бит содержат адрес назначения.

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

Доставка не гарантируется

Многие сети не гарантируют доставку, отсутствие дубликатов пакетов и порядок их доставки, как например, протокол UDP в сети Интернет. Тем не менее, это можно сделать в верхней части пакета услуг транспортного уровня, который может обеспечить такую защиту. TCP и UDP являются лучшими примерами 4 транспортного уровня, одного из семи уровней сетевой модели OSI.

Заголовок пакета определяет тип данных, номер пакета, общее количество пакетов и IP-адреса отправителя и получателя.

Иногда используется термин «кадр» для обозначения пакетов в точности так, как он используется при передаче сигнала по проводам или радио.

Методы, обеспечивающие надежную доставку цифровых данных по ненадежным каналам связи Устранение ошибок передачи, вызванных атмосферой Земли ( слева), ученые Годдарда применили исправление ошибок Рида – Соломона (справа), которое обычно используется в компакт-дисках и 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.

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

См. также

• Код Бергера
• Пакетный код коррекции ошибок
• Неважный сигнал тревоги
• ECC-память, тип хранения компьютерных данных
• Запрещенный ввод
• Адаптация связи
• Список алгоритмов для обнаружение и исправление ошибок
• Список кодов исправления ошибок
• Список хэш-функций
• Надежность (компьютерные сети)

Ссылки

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

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

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

• Он-лайн учебник: Теория информации, выводы и алгоритмы обучения, Дэвид Дж. К. Маккей, содержит главы по элементарным кодам исправления ошибок; о теоретических пределах исправления ошибок; и на последних современных кодах исправления ошибок, включая коды проверки четности с низкой плотностью, турбокоды и фонтанные коды.
• Compute параметры линейных кодов — оперативный интерфейс для генерации и вычисления параметров (например, минимальное расстояние, радиус покрытия ) линейных кодов с исправлением ошибок.
• Страница ECC
• SoftECC: Система для проверки целостности памяти программного обеспечения
• Настраиваемая программная библиотека обнаружения и исправления ошибок DRAM для HPC
• Обнаружение и исправление скрытого искажения данных для крупномасштабных высокопроизводительных вычислений