Компьютерные сети. 6-е изд.

В некоторых случаях две приведенные выше схемы приемлемы на более высоких уровнях, но обычно на канальном уровне широко используется другой, более надежный метод обнаружения ошибок — циклический избыточный код (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, то с его помощью можно обнаружить все ошибки, состоящие из нечетного количества инвертированных битов. Как показывает статистика, уже за счет этого можно обнаружить половину имеющихся ошибок.