Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 68
Текст из файла (страница 68)
Однако в системах, где информация передается по оптоволокну или высококачественному медному проводу, уровень ошибок гораздо ниже, поэтому обнаружениеошибок и повторная передача являются более подходящим методом.Мы рассмотрим три кода с обнаружением ошибок. Все они относятся к линейнымсистематическим блочным кодам:1.
Код с проверкой на четность.2. Код с контрольными суммами.3. Циклический избыточный код.Для того чтобы понять, в каких ситуациях обнаружение ошибок может быть эффективнее исправления, возьмем первый из перечисленных кодов. К отправляемымданным присоединяется единственный бит четности (parity bit), который выбираетсятак, чтобы число единичных битов в кодовом слове было четным (или нечетным). Этоэквивалентно вычислению бита четности в виде суммы по модулю 2 для битов данных(или применению операции исключающего ИЛИ). Например, если отправляетсякодовое слово 1011010 и число единиц должно быть четным, то в конце добавляетсяноль, и последовательность превращается в 10110100.
Если же число единиц должнобыть нечетным, то последовательность устанавливается такая: 10110101. Кодовое рас-234 Глава 3. Канальный уровеньстояние кода с единственным битом четности равно двум, так как любая однобитнаяошибка меняет четность кодового слова на неправильную. Это означает, что данныйкод позволяет распознавать однобитные ошибки.Рассмотрим канал с изолированными ошибками, возникающими с вероятностью10–6 на бит.
Такое значение может показаться очень небольшим, но для длинного кабельного канала, в котором распознавать ошибки довольно сложно, оно в лучшем случае считается допустимым. Типичные локальные сети характеризуются вероятностьюошибки 10–10. Пусть блок данных состоит из 1000 бит. Для создания кода, исправляющего однократные ошибки в 1000-битном блоке, как видно из представленного вышеуравнения (3.1), потребуется 10 контрольных бит.
Для 1 Мбит данных это составит10 000 проверочных бит. Чтобы просто обнаруживать одиночную 1-битовую ошибку,достаточно одного бита четности на блок. На каждые 1000 блоков будет выявлятьсяодна ошибка, и придется переслать повторно еще один блок (1001 бит), чтобы исправить ее. Таким образом, суммарные накладные расходы на обнаружение ошибкии повторную передачу составят всего 2001 бит на 1 Мбит данных против 10 000 бит,необходимых для кода Хэмминга.Проблема данной схемы заключается в том, что если к блоку добавлять всего одинбит четности, то гарантированно распознаваться будет только одна однобитная ошибкав блоке. В случае возникновения последовательности ошибок вероятность обнаружения ошибки будет всего лишь 0,5, что абсолютно неприемлемо.
Этот недостаток можетбыть исправлен, если рассматривать каждый посылаемый блок как прямоугольнуюматрицу n бит шириной и k бит высотой (принцип ее построения был описан выше).Если вычислить и отправить один бит четности для каждой строки, то гарантированнообнаружить можно будет до k однобитных ошибок, при условии, что в каждой строкебудет не большое одной ошибки.Однако можно сделать кое-что еще, чтобы повысить уровень защиты от последовательностей ошибок — биты четности можно вычислять в порядке, отличном от того,в котором данные отправляются.
Этот способ называется чередованием (interleaving).В нашем примере мы будет вычислять бит четности для каждого из n столбцов, нобиты данных отправляться будут в виде k строк, в обычном порядке: сверху внизи слева направо. В последней строке отправим n бит четности. На рис. 3.8 порядокпересылки показан для n = 7 и k = 7.Network10011101100101111010011101111101111111001011010111011110Nclwork10011101100011110110011101111101111111001011010111011110Рис. 3.8.
Чередование битов четности для обнаружения последовательностей ошибок3.2. Обнаружение и исправление ошибок 235Чередование представляет собой общую технику преобразования кода, способногообнаруживать (или исправлять) изолированные ошибки, в код, обнаруживающий(или исправляющий) последовательности ошибок. На рис. 3.8, там, где присутствуетпоследовательность ошибок длиной n = 7, мы видим, что ошибочные биты находятсяв разных столбцах (последовательность ошибок не означает, что все биты в ней неправильные; это всего лишь подразумевает, что, по меньшей мере, первый и последний биты сбойные.
На рис. 3.8 из семи сбойных бит на самом деле изменено значениетолько четырех). В каждом из n столбцов повреждено будет не больше одного бита,поэтому биты четности этих столбцов помогут выявить ошибку. В данном методеn бит четности в блоках из kn битов данных применяются для обнаружения однойпоследовательности ошибок длиной n бит или меньше.Последовательность ошибок длиной n + 1 не будет обнаружена, если будут инвертированы первый и последний биты, а все остальные биты останутся неизменными. Если в блоке при передаче возникнет длинная последовательность ошибокили несколько коротких, вероятность того, что четность любого из n столбцов будетверной (или неверной), равна 0,5, поэтому вероятность необнаружения ошибки будетравна 2–n.Второй тип кода с обнаружением ошибок, код с использованием контрольнойсуммы, весьма напоминает группу кодов, применяющих биты четности. Под «контрольной суммой» часто подразумевают любую группу контрольных бит, связанныхс сообщением, независимо от способа их вычисления.
Группа бит четности — такжеодин из примеров контрольной суммы. Однако существуют и другие, более надежные контрольные суммы, основанные на текущей сумме бит данных в сообщении.Контрольная сумма обычно помещается в конец сообщения, в качестве дополненияфункции суммирования. Таким образом, ошибки можно обнаружить путем суммирования всего полученного кодового слова: бит данных и контрольной суммы.
Еслирезультат равен нулю, значит, ошибок нет.Один из примеров контрольной суммы — это 16-битная контрольная сумма, которая используется во всех пакетах протокола IP при пересылке данных в Интернете(Braden и др., 1988). Она представляет собой сумму бит сообщения, поделенного на16-битные слова. Так как данный метод работает со словами, а не с битами (как прииспользовании битов четности), то ошибки, при которых четность не меняется, всеже изменяют значение суммы, а значит, могут быть обнаружены. Например, если битмладшего разряда в двух разных словах меняется с 0 на 1, то проверка четности этихбитов не выявит ошибку.
Однако при добавлении к 16-битной контрольной сумме двеединицы дадут другой результат, и ошибка станет очевидной.Контрольная сумма, применяемая в Интернете, вычисляется с помощью обратного кода или арифметики с дополнением до единицы, а не как сумма по модулю 216.В арифметике обратного кода отрицательное число представляет собой поразрядноедополнение своего положительного эквивалента. Большинство современных компьютеров работают на арифметике с дополнением до двух, в которой отрицательноечисло является дополнением до единицы плюс один.
На компьютере с арифметикойс дополнением до двух сумма с дополнением до единицы эквивалентна сумме по модулю 216, причем любое переполнение старших бит добавляется обратно к младшимбитам. Такой алгоритм обеспечивает единообразный охват данных битами контроль-236 Глава 3. Канальный уровеньной суммы. В противном случае при сложении двух старших бит переполнение можетбыть утеряно без изменения суммы. Но есть и еще одно преимущество. У дополнениядо единицы может быть два представления нуля: все нули и все единицы. Таким образом, одно значение (например, все нули) указывает, что контрольной суммы нети дополнительное поле для этого не требуется.Десятилетиями существовало мнение, что кадры, для которых вычисляется контрольная сумма, содержат случайные значения бит. Анализ алгоритмов вычисленияконтрольных сумм всегда проводился с учетом именно такого предположения. Изучение фактических данных, выполненное Партриджем и другими в 1995 году, показало, что данное предположение неверно.
Следовательно, нераспознанные ошибкипроскальзывают в некоторых случаях намного чаще, чем полагали раньше.В частности, контрольная сумма для Интернета, несмотря на эффективностьи простоту, в определенных ситуациях слабо защищает от ошибок именно потому, чтоэто простая сумма. Она не позволяет распознать удаление или добавление нулевыхданных, а также случаи, когда части сообщения меняются местами или расщепляются таким образом, что склеенными оказываются части двух разных пакетов. Можетказаться, что подобные ошибки вряд ли произойдут в случайных процессах, но онивполне вероятны в сетях с неправильно работающим оборудованием.Намного лучшим выбором считается контрольная сумма Флетчера (Fletcher,1982).
Она включает компонент, отвечающий за позицию: произведение значенияданных и соответствующей позиции добавляется к текущей сумме. Это обеспечиваетлучшие возможности по обнаружению изменений в положении данных.Хотя две приведенные выше схемы в некоторых случаях могут быть приемлемымина более высоких уровнях, на практике на канальном уровне широко используетсядругой, более надежный метод обнаружения ошибок — полиномиальный код, так жеизвестный, как CRC (Cyclic Redundancy Сheck — циклический избыточный код).В основе полиномиальных кодов лежит представление битовых строк в виде многочленов с коэффициентами, равными только 0 или 1.
Кадр из k бит рассматриваетсякак список коэффициентов многочлена степени k – 1, состоящего из k членов от xk‑1до x0. Старший (самый левый) бит кадра соответствует коэффициенту при xk‑1, следующий бит — коэффициенту при xk‑2 и т. д. Например, число 110001 состоит из 6 бит и,следовательно, представляется в виде многочлена пятой степени с коэффициентами1, 1, 0, 0, 0 и 1: x5 + x4 + x0.С данными многочленами осуществляются арифметические действия по модулю 2в соответствии с алгебраической теорией поля.
При этом перенос при сложении и заемпри вычитании не производится. И сложение, и вычитание эквивалентны исключающему ИЛИ (XOR).+ 10011011 11001010 0101000100110011+ 11001101 11111110 1110000– 10100110 01010110– 01010101 10101111 11111010Деление чисел осуществляется в точности так же, как и деление обычных двоичных чисел, с той разницей, что вычитание производится снова по модулю 2. Говорят,что делитель «уходит» в делимое, если в делимом столько же бит, сколько в делителе.3.2. Обнаружение и исправление ошибок 237При использовании циклического кода отправитель и получатель должны сначаладоговориться насчет образующего многочлена, G(x).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
