Контрольная сумма, применяемая в интернете, вычисляется с помощью обратного кода или арифметики с дополнением до единицы, а не как сумма по модулю 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 941 без остатка.
Теперь проанализируем возможности этого метода. Какие ошибки он способен обнаружить? Представим, что произошла ошибка при передаче фрейма и вместо многочлена T(x) получатель принял T(x) + E(x). Каждый единичный бит многочлена E(x) соответствует инвертированному биту в пакете. Если в многочлене E(x) k бит равны 1, это значит, что произошло k однобитных ошибок. Отдельный пакет ошибок характеризуется единицей в начале, комбинацией нулей и единиц и конечной единицей; остальные биты равны 0.
Получатель делит принятый фрейм с контрольной суммой на образующий многочлен G(x), то есть вычисляет [T(x) + E(x)]/G(x). T(x)/G(x) равно 0, поэтому результат вычислений равен E(x)/G(x). Ошибки, которые случайно окажутся кратными образующему многочлену G(x), останутся незамеченными, остальные будут обнаружены.
Если происходит однобитная ошибка, то E(x) = xi, где i — номер ошибочного бита. Если образующий многочлен G(x) содержит два или более члена, то E(x) никогда не будет делиться на него без остатка, поэтому будут обнаружены все однобитные ошибки.
В случае двух изолированных однобитных ошибок E(x) = xi + xj, где i > j. Это также можно записать в виде E(x) = xj(xi – j + 1). Предположим, что G(x) не делится на x. Тогда достаточное условие обнаружения всех двойных ошибок — неделимость многочлена xk + 1 на G(x) для любого k от 1 до максимального значения i – j (то есть до максимальной длины фрейма). Известны простые многочлены с небольшими степенями, обеспечивающие защиту для длинных фреймов. Например, многочлен x15 + x14 + 1 не является делителем для xk + 1 для любого k от 1 до 32 768.
Если ошибка затронет нечетное количество битов во фрейме, многочлен E(x) будет содержать нечетное число членов (например, x5 + x2+ 1, но не x2 + 1). Интересно, что в системе арифметических операций по модулю 2 многочлены с нечетным числом членов не делятся на x + 1. Если в качестве образующего выбрать многочлен, который делится на x + 1, то с его помощью можно обнаружить все ошибки, состоящие из нечетного количества инвертированных битов. Как показывает статистика, уже за счет этого можно обнаружить половину имеющихся ошибок.
И наконец, что наиболее важно, полиномиальный код с r контрольными битами будет обнаруживать все пакеты ошибок длиной ≤ r. Пакет ошибок длиной k может быть представлен в виде многочлена xi(xk-1 +…+ 1), где i определяет, насколько далеко от правой границы фрейма располагается пакет ошибок. Если образующий многочлен G(x) содержит член x0, то xi не будет его множителем. Поэтому если степень выражения в скобках меньше степени G(x), то остаток от деления никогда не будет нулевым.
Если длина последовательности ошибок равна r + 1, то остаток от деления будет нулевым, только если последовательность идентична G(x). По определению, первый и последний биты последовательности должны быть равны 1, поэтому ее совпадение с образующим многочленом зависит от r – 1 промежуточных битов. Если все комбинации считать равновероятными, то возможность такой нераспознаваемой ошибки равна (1/2)r–1.
Также следует отметить, что при возникновении пакета ошибок длиннее r + 1 битов или нескольких коротких пакетов вероятность пропуска ошибки составляет (1/2)r при условии, что все комбинации битов равновероятны.
Некоторые образующие многочлены стали международными стандартами. Один из них применяется в IEEE 802 (он основан на многочлене, используемом в Ethernet):
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1.
Помимо других полезных свойств, этот многочлен обладает способностью обнаруживать любые пакеты ошибок длиной не более 32 бит и все пакеты, дающие нечетное число битов. Начиная с 1980-х годов он применяется очень широко. И все же его нельзя назвать наилучшим. Выполнив обстоятельные компьютерные вычисления, Кастаньоли и др. (Castagnoli et al., 1993) и Купман (Koopman, 2002) обнаружили самые эффективные коды CRC. Расстояние Хэмминга, соответствующее сообщениям обычной длины, для них равно 6, в то время как для CRC-32 стандарта IEEE оно равняется всего 4.
Хотя алгоритм вычисления CRC может показаться сложным, Петерсон и Браун (Peterson and Brown, 1961) продемонстрировали, что можно создать простую схему для аппаратной проверки и подсчета CRC на основе схемы с регистром сдвига. В дальнейшем с регулярной периодичностью появлялись более новые и более быстрые реализации (см. работу Митры и Найека; Mitra and Nyack, 2017). CRC до сих пор применяется на практике повсеместно в аппаратном обеспечении. Десятки сетевых стандартов работают на основе кодов CRC, включая почти все LAN (например, Ethernet, 802.11) и линии связи «точка-точка» (пакеты, пересылаемые по SONET).