Код с контрольными суммами

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

3. Циклический избыточный (полиномиальный) код
В основе полиномиальных кодов лежит представление битовых строк в виде многочленов с коэффициентами, равными только 0 или 1. Кадр из k бит рассматривается как список коэффициентов многочлена степени k – 1, состоящего из k членов от xk-1 до x0. Старший (самый левый) бит кадра соответствует коэффициенту при xk-1, следу- ющий бит — коэффициенту при xk-2 и т. д. Например, число 110001 состоит из 6 бит и, следовательно, представляется в виде многочлена пятой степени с коэффициентами 1, 1, 0, 0, 0 и 1: x5 + x4 + x0.

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

Алгоритм вычисления CRC:

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

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

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