Последовательность ошибок длиной n + 1 не будет обнаружена, если будут инвертированы первый и последний биты, а все остальные биты останутся неизменными. Если в блоке при передаче возникнет длинная последовательность ошибок или несколько коротких, вероятность того, что четность любого из n столбцов будет верной (или неверной), равна 0,5, поэтому вероятность необнаружения ошибки будет равна 2^-n.

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

Один из примеров контрольной суммы — это 16-битная контрольная сумма, которая используется во всех пакетах протокола IP при пересылке данных в Интернете (Braden и др., 1988). Она представляет собой сумму бит сообщения, поделенного на 16-битные слова. Так как данный метод работает со словами, а не с битами (как при использовании битов четности), то ошибки, при которых четность не меняется, все же изменяют значение суммы, а значит, могут быть обнаружены. Например, если бит младшего разряда в двух разных словах меняется с 0 на 1, то проверка четности этих битов не выявит ошибку. Однако при добавлении к 16-битной контрольной сумме две единицы дадут другой результат, и ошибка станет очевидной.

Контрольная сумма, применяемая в Интернете, вычисляется с помощью обратного кода или арифметики с дополнением до единицы, а не как сумма по модулю 2¹⁶. В арифметике обратного кода отрицательное число представляет собой поразрядное дополнение своего положительного эквивалента. Большинство современных компьютеров работают на арифметике с дополнением до двух, в которой отрицательное число является дополнением до единицы плюс один. На компьютере с арифметикой с дополнением до двух сумма с дополнением до единицы эквивалентна сумме по модулю 2¹⁶, причем любое переполнение старших бит добавляется обратно к младшим битам. Такой алгоритм обеспечивает единообразный охват данных битами контроль

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

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

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

Намного лучшим выбором считается контрольная сумма Флетчера (Fletcher, 1982). Она включает компонент, отвечающий за позицию: произведение значения данных и соответствующей позиции добавляется к текущей сумме. Это обеспечивает лучшие возможности по обнаружению изменений в положении данных.

Хотя две приведенные выше схемы в некоторых случаях могут быть приемлемыми на более высоких уровнях, на практике на канальном уровне широко используется другой, более надежный метод обнаружения ошибок — полиномиальный код, так же известный, как CRC (Cyclic Redundancy Check — циклический избыточный код).

С данными многочленами осуществляются арифметические действия по модулю 2 в соответствии с алгебраической теорией поля. При этом перенос при сложении и заем при вычитании не производится. И сложение, и вычитание эквивалентны исключающему ИЛИ (XOR).

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

При использовании циклического кода отправитель и получатель должны сначала договориться насчет образующего многочлена, G(x). Старший и младший биты образующего многочлена должны быть равны 1. Для вычисления CRC для некоторого кадра из m бит, соответствующего полиному M(x), необходимо, чтобы этот кадр был длиннее образующего многочлена. Идея состоит в добавлении CRC в конец кадра таким образом, чтобы получившийся многочлен делился на образующийся многочлен G(x) без остатка. Получатель, приняв кадр, содержащий контрольную сумму, пытается разделить его на G(x). Ненулевой остаток от деления означает ошибку.

Должно быть очевидно, что многочлен T(x) делится (по модулю 2) на G(x) без остатка. В любом случае, если вы уменьшите делимое на остаток, то результат должен делиться без остатка. Например, в десятичной системе счисления, если разделить 210 278 на 10 941, то остаток от деления будет равен 2399. Если вычесть 2399 из 210 278, то результат (207 879) будет делиться на 10 941 без остатка.

Теперь проанализируем возможности этого метода. Какие ошибки сможет он обнаруживать? Представим, что произошла ошибка при передаче кадра, так что вместо многочлена T(x) получатель принял T(x) + E(x). Каждый единичный бит многочлена E(x) соответствует инвертированному биту в пакете. Если в многочлене E(x) k бит равны 1, это означает, что произошло k единичных ошибок. Единичный пакет ошибок характеризуется первой единицей, смесью нулей и единиц и конечной единицей, а остальные биты равны 0.

  

многочлены с небольшими степенями, обеспечивающие защиту для длинных кадров. Например, многочлен x¹⁵ + x¹⁴ + 1 не является делителем для x^k + 1 для любого k от

1 до 32 768.

Рис. 3.9. Пример вычисления CRC

Если ошибка затронет нечетное количество бит в кадре, многочлен E(x) будет содержать нечетное число членов

. Интересно, что

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

И наконец, что наиболее важно, полиномиальный код с r контрольными битами будет обнаруживать все пакеты ошибок длиной

. Пакет ошибок длиной k может быть представлен в виде многочлена, где i определяет, насколько далеко