Девятая часть тут.
Ни одна среда передачи данных не может считаться совершенной. Если среда передачи является общей, как радиочастота (RF), существует возможность возникновения помех или даже столкновений дейтаграмм. Это когда несколько отправителей пытаются передать информацию одновременно. Результатом является искаженное сообщение, которое не может быть понято предполагаемым получателем. Даже специализированная среда, такая как подводный оптический кабель типа point-to-point (световолновой), может испытывать ошибки из—за деградации кабеля или точечных событий-даже, казалось бы, безумных событий, таких как солнечные вспышки, вызывающие излучение, которое, в свою очередь, мешает передаче данных по медному кабелю.
Существует два ключевых вопроса, на которые сетевой транспорт должен ответить в области ошибок:
- Как можно обнаружить ошибки при передаче данных?
- Что должна делать сеть с ошибками при передаче данных?
Далее рассматриваются некоторые из возможных ответов на эти вопросы.
Обнаружение ошибок
Первый шаг в работе с ошибками, независимо от того, вызваны ли они отказом носителя передачи, повреждением памяти в коммутационном устройстве вдоль пути или любой другой причиной, заключается в обнаружении ошибки. Проблема, конечно, в том, что когда получатель изучает данные, которые он получает, нет ничего, с чем можно было бы сравнить эти данные, чтобы обнаружить ошибку.
Проверка четности — это самый простой механизм обнаружения. Существуют два взаимодополняющих алгоритма проверки четности. При четной проверке четности к каждому блоку данных добавляется один дополнительный бит. Если сумма битов в блоке данных четная—то есть если в блоке данных имеется четное число битов 1, то дополнительный бит устанавливается равным 0. Это сохраняет четное состояние четности блока. Если сумма битов нечетна, то дополнительный бит устанавливается равным 1, что переводит весь блок в состояние четной четности. Нечетная четность использует ту же самую дополнительную битную стратегию, но она требует, чтобы блок имел нечетную четность (нечетное число 1 бит). В качестве примера вычислите четную и нечетную четность для этих четырех октетов данных:
00110011 00111000 00110101 00110001
Простой подсчет цифр показывает, что в этих данных есть 14 «1» и 18 «0». Чтобы обеспечить обнаружение ошибок с помощью проверки четности, вы добавляете один бит к данным, либо делая общее число «1» в недавно увеличенном наборе битов четным для четной четности, либо нечетным для нечетной четности. Например, если вы хотите добавить четный бит четности в этом случае, дополнительный бит должен быть установлен в «0». Это происходит потому, что число «1» уже является четным числом. Установка дополнительного бита четности на «0» не добавит еще один «1» и, следовательно, не изменит, является ли общее число «1» четным или нечетным. Таким образом, для четной четности конечный набор битов равен:
00110011 00111000 00110101 00110001 0
С другой стороны, если вы хотите добавить один бит нечетной четности к этому набору битов, вам нужно будет сделать дополнительный бит четности «1», так что теперь есть 15 «1», а не 14. Для нечетной четности конечный набор битов равен:
00110011 00111000 00110101 00110001 1
Чтобы проверить, были ли данные повреждены или изменены при передаче, получатель может просто отметить, используется ли четная или нечетная четность, добавить число «1» и отбросить бит четности. Если число «1» не соответствует используемому виду четности (четное или нечетное), данные повреждены; в противном случае данные кажутся такими же, как и первоначально переданные.
Этот новый бит, конечно, передается вместе с оригинальными битами. Что произойдет, если сам бит четности каким-то образом поврежден? Это на самом деле нормально - предположим, что даже проверка четности на месте, и передатчик посылает
00110011 00111000 00110101 00110001 0
Приемник, однако, получает
00110011 00111000 00110101 00110001 1
Сам бит четности был изменен с 0 на 1. Приемник будет считать «1», определяя, что их 15. Поскольку даже проверка четности используется, полученные данные будут помечены как имеющие ошибку, даже если это не так. Проверка на четность потенциально слишком чувствительна к сбоям, но в случае обнаружения ошибок лучше ошибиться в начале.
Есть одна проблема с проверкой четности: она может обнаружить только один бит в передаваемом сигнале. Например, если даже четность используется, и передатчик отправляет
00110011 00111000 00110101 00110001 0
Приемник, однако, получает
00110010 00111000 00110101 00110000 0
Приемник подсчитает число «1» и обнаружит, что оно равно 12. Поскольку система использует четную четность, приемник будет считать данные правильными и обработает их в обычном режиме. Однако оба бита, выделенные жирным шрифтом, были повреждены. Если изменяется четное число битов в любой комбинации, проверка четности не может обнаружить изменение; только когда изменение включает нечетное число битов, проверка четности может обнаружить изменение данных.
Циклическая проверка избыточности (Cyclic Redundancy Check - CRC) может обнаруживать более широкий диапазон изменений в передаваемых данных, используя деление (а не сложение) в циклах по всему набору данных, по одной небольшой части за раз. Работа с примером - лучший способ понять, как рассчитывается CRC. Расчет CRC начинается с полинома, как показано на рисунке 1.
На рис. 1 трехчленный многочлен x3 + x2 + 1 расширен, чтобы включить все члены, включая члены, предшествующие 0 (и, следовательно, не влияют на результат вычисления независимо от значения x). Затем эти четыре коэффициента используются в качестве двоичного калькулятора, который будет использоваться для вычисления CRC.
Чтобы выполнить CRC, начните с исходного двоичного набора данных и добавьте три дополнительных бита (поскольку исходный полином без коэффициентов имеет три члена; следовательно, это называется трехбитной проверкой CRC), как показано здесь:
10110011 00111001 (оригинальные данные) 10110011 00111001 000 (с добавленными битами CRC)
Эти три бита необходимы для обеспечения того, чтобы все биты в исходных данных были включены в CRC; поскольку CRC перемещается слева направо по исходным данным, последние биты в исходных данных будут включены только в том случае, если эти заполняющие биты включены. Теперь начните с четырех битов слева (потому что четыре коэффициента представлены в виде четырех битов). Используйте операцию Exclusive OR (XOR) для сравнения крайних левых битов с битами CRC и сохраните результат, как показано здесь:
10110011 00111001 000 (дополненные данные) 1101 (Контрольные биты CRC) ---- 01100011 00111001 000 (результат XOR)
XOR'инг двух двоичных цифр приводит к 0, если эти две цифры совпадают, и 1, если они не совпадают. Контрольные биты, называемые делителем, перемещаются на один бит вправо (некоторые шаги здесь можно пропустить), и операция повторяется до тех пор, пока не будет достигнут конец числа:
10110011 00111001 000
1101
01100011 00111001 000
1101
00001011 00111001 000
1101
00000110 00111001 000
110 1
00000000 10111001 000
1101
00000000 01101001 000
1101
00000000 00000001 000
1 101
00000000 00000000 101
CRC находится в последних трех битах, которые были первоначально добавлены в качестве заполнения; это "остаток" процесса разделения перемещения по исходным данным плюс исходное заполнение. Получателю несложно определить, были ли данные изменены, оставив биты CRC на месте (в данном случае 101) и используя исходный делитель поперек данных, как показано здесь:
10110011 00111001 101
1101
01100011 00111001 101
1101
00001011 00111001 101
1101
00000110 00111001 101
110 1
00000000 10111001 101
1101
00000000 01101001 101
1101
00000000 00000001 101
1 101
00000000 00000000 000
Если данные не были изменены, то результат этой операции всегда должен быть равен 0. Если бит был изменен, результат не будет равен 0, как показано здесь:
10110011 00111000 000
1101
01100011 00111000 000
1101
00001011 00111000 000
1101
00000110 00111000 000
110 1
00000000 10111000 000
1101
00000000 01101000 000
1101
00000000 00000000 000
1 101
00000000 00000001 000
CRC может показаться сложной операцией, но она играет на сильных сторонах компьютера—бинарных операциях конечной длины. Если длина CRC задается такой же, как у стандартного небольшого регистра в обычных процессорах, скажем, восемь бит, вычисление CRC-это довольно простой и быстрый процесс. Проверка CRC имеет то преимущество, что она устойчива к многобитовым изменениям, в отличие от проверки четности, описанной ранее.
Исправление ошибок
Однако обнаружение ошибки — это только половина проблемы. Как только ошибка обнаружена, что должна делать транспортная система? Есть, по существу, три варианта.
Транспортная система может просто выбросить данные. В этом случае транспорт фактически переносит ответственность за ошибки на протоколы более высокого уровня или, возможно, само приложение. Поскольку некоторым приложениям может потребоваться полный набор данных без ошибок (например, система передачи файлов или финансовая транзакция), у них, вероятно, будет какой-то способ обнаружить любые пропущенные данные и повторно передать их. Приложения, которые не заботятся о небольших объемах отсутствующих данных (например, о голосовом потоке), могут просто игнорировать отсутствующие данные, восстанавливая информацию в приемнике, насколько это возможно, с учетом отсутствующей информации.
Транспортная система может подать сигнал передатчику, что произошла ошибка, и позволить передатчику решить, что делать с этой информацией (как правило, данные при ошибке будут повторно переданы).
Транспортная система может выйти за рамки отбрасывания данных, включив достаточное количество информации в исходную передачу, определить, где находится ошибка, и попытаться исправить ее. Это называется Прямой коррекцией ошибок (Forward Error Correction - FEC). Коды Хэмминга, один из первых разработанных механизмов FEC, также является одним из самых простых для объяснения.
Код Хэмминга лучше всего объяснить на примере - для иллюстрации будет использована таблица 1.
В Таблице № 1:
- Каждый бит в 12-битном пространстве, представляющий собой степень двух (1, 2, 4, 6, 8 и т. д.) и первый бит, устанавливается в качестве битов четности.
- 8-битное число, которое должно быть защищено с помощью FEC, 10110011, распределено по оставшимся битам в 12-битном пространстве.
- Каждый бит четности устанавливается равным 0, а затем четность вычисляется для каждого бита четности путем добавления числа «1» в позиции, где двоичный бит имеет тот же бит, что и бит четности. В частности:
- P1 имеет набор крайних правых битов в своем битовом номере; другие биты в числовом пространстве, которые также имеют набор крайних правых битов, включены в расчет четности (см. вторую строку таблицы, чтобы найти все позиции битов в номере с набором крайних правых битов). Они указаны в таблице с X в строке P1. Общее число «1»-нечетное число, 3, поэтому бит P1 устанавливается равным 1 (в этом примере используется четная четность).
- P2 имеет второй бит из правого набора; другие биты в числовом пространстве, которые имеют второй из правого набора битов, включены в расчет четности, как указано с помощью X в строке P2 таблицы. Общее число «1»-четное число, 4, поэтому бит P2 установлен в 0.
- P4 имеет третий бит из правого набора, поэтому другие биты, которые имеют третий бит из правого набора, имеют свои номера позиций, как указано с помощью X в строке P3. В отмеченных столбцах есть нечетное число «1», поэтому бит четности P4 установлен на 1.
Чтобы определить, изменилась ли какая-либо информация, получатель может проверить биты четности таким же образом, как их вычислял отправитель; общее число 1s в любом наборе должно быть четным числом, включая бит четности. Если один из битов данных был перевернут, приемник никогда не должен найти ни одной ошибки четности, потому что каждая из битовых позиций в данных покрыта несколькими битами четности. Чтобы определить, какой бит данных является неправильным, приемник добавляет позиции битов четности, которые находятся в ошибке; результатом является положение бита, которое было перевернуто. Например, если бит в позиции 9, который является пятым битом данных, перевернут, то биты четности P1 и P8 будут ошибочными. В этом случае 8 + 1 = 9, так что бит в позиции 9 находится в ошибке, и его переворачивание исправит данные. Если один бит четности находится в ошибке—например, P1 или P8—то это тот бит четности, который был перевернут, и сами данные верны.
В то время как код Хэмминга гениален, есть много битовых шаблонов-перевертышей, которые он не может обнаружить. Более современный код, такой как Reed-Solomon, может обнаруживать и исправлять более широкий диапазон условий ошибки, добавляя меньше дополнительной информации в поток данных.
Существует большое количество различных видов CRC и кодов исправления ошибок, используемых во всем мире связи. Проверки CRC классифицируются по количеству битов, используемых в проверке (количество битов заполнения или, точнее, длины полинома), а в некоторых случаях - по конкретному применению. Например, универсальная последовательная шина использует 5-битный CRC (CRC-5-USB); Глобальная система мобильной связи (GSM), широко используемый стандарт сотовой связи, использует CRC-3-GSM; Мультидоступ с кодовым разделением каналов (CDMA), другой широко используемый стандарт сотовой связи, использует CRC-6-CDMA2000A, CRC-6-CDMA2000B и CRC-30; и некоторые автомобильные сети (CAN), используемые для соединения различных компонентов в автомобиле, используют CRC-17-CAN и CRC-21-CAN. Некоторые из этих различных функций CRC являются не единственной функцией, а скорее классом или семейством функций со многими различными кодами и опциями внутри них.
