Десятилетиями существовало мнение, что фреймы, для которых вычисляется контрольная сумма, содержат случайные значения битов. Анализ алгоритмов вычисления контрольных сумм всегда проводился с учетом именно такого предположения. Изучение фактических данных, выполненное Партриджем и др. (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.