Компьютерные сети. 6-е изд. - Эндрю Таненбаум

n бит или меньше.

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

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

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

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

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

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

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

В некоторых случаях две приведенные выше схемы приемлемы на более высоких уровнях, но обычно на канальном уровне широко используется другой, более надежный метод обнаружения ошибок — циклический избыточный код (Cyclic Redundancy Сheck, CRC), также известный как полиномиальный код. В основе полиномиальных кодов лежит представление битовых строк в виде многочленов с коэффициентами, равными только 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. Например:

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

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

Алгоритм вычисления CRC выглядит следующим образом:

1. Пусть r — степень многочлена G(x). Добавим r нулевых битов в конец фрейма так, чтобы он содержал m + r бит и соответствовал многочлену xrM(x).

2. Разделим по модулю 2 битовую строку, соответствующую многочлену xrM(x), на битовую строку, соответствующую образующему многочлену G(x).

3. Вычтем по модулю 2 остаток от деления (он должен быть не более r бит) из битовой строки, соответствующей многочлену xrM(x). Результат и будет передаваемым фреймом, который мы назовем многочленом T(x).

На илл. 3.9 показаны вычисления для фрейма 1101011111 и образующего многочлена G(x) = x4 + x + 1.

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

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