Обнаружение ошибок: CRC и контроль целостности

Урок о том, как деление «в столбик» по особым правилам даёт короткий код, ловящий целые пачки искажённых бит.

CRC (Cyclic Redundancy Check, циклический избыточный код) — метод контроля целостности, при котором контрольное значение это остаток от деления данных (как двоичного многочлена) на заранее выбранный многочлен-делитель.

Зачем это нужно

Контрольная сумма из первого урока слаба: она легко «не замечает» некоторые ошибки. Например, если в одном байте прибавилось 1, а в другом убавилось 1, общая сумма не изменится — и искажение пройдёт незаметно. А в реальных каналах помеха часто бьёт не по одному биту, а по целой пачке подряд (burst error): царапина на диске, импульс в проводе, потерянный фрагмент радиосигнала. Для таких пакетных ошибок нужен код понадёжнее — и это CRC. Он используется буквально везде: кадры Ethernet и Wi-Fi, архивы ZIP/RAR/PNG, сектора жёстких дисков, протоколы USB.

Идея: данные как многочлен

CRC смотрит на цепочку бит как на коэффициенты двоичного многочлена. Бит-строка $1101$ это многочлен

$$ x^3 + x^2 + 1 $$

(там, где бит равен 1, член присутствует; где 0 — отсутствует). Выбирают фиксированный порождающий многочлен $G(x)$ степени $r$. Сообщение $M(x)$ дополняют $r$ нулями справа (это умножение на $x^r$) и делят на $G(x)$ — но по правилам двоичной арифметики, где вместо вычитания используется XOR, а переносов нет. Остаток от этого деления и есть CRC длиной $r$ бит. Его приписывают к данным:

$$ \text{CRC} = \left( M(x) \cdot x^r \right) \bmod G(x) $$

В итоге передаваемое слово нацело делится на $G(x)$. Приёмник делит принятое слово на тот же $G(x)$: остаток ноль — данные целы, остаток ненулевой — была ошибка.

Как это работает: деление в столбик через XOR

Разберём упрощённый пример. Сообщение $M = 1101$, делитель $G = 1011$ (степень $r=3$, потому что старший член $x^3$). Дописываем к сообщению 3 нуля: $1101\,000$. Теперь делим в столбик, но «вычитание» на каждом шаге это XOR с делителем, выровненным по старшему биту остатка. Деление продолжаем, пока остаток не станет короче делителя.

  1101000   :1011
  1011          XOR
  ----
  0110000
   1011         XOR (делитель сдвинут к старшей 1)
   ----
   0011100
     1011       XOR
     ----
     0001010
        1011    XOR
        ----
        0000001 -> остаток 001 (последние 3 бита)

Остаток получился 001. Значит CRC = 001, и в канал уходит сообщение вместе с ним: $1101\,001$. Приёмник поделит $1101001$ на $1011$ — если ничего не испортилось, остаток будет $000$.

Проверим эти выкладки честным Python. XOR двух бит-строк делаем поразрядно, а само деление повторяет школьный столбик.

def crc_remainder(message, divisor):
    r = len(divisor) - 1            # длина CRC = степень делителя
    bits = list(message) + ['0'] * r   # дописываем r нулей
    d = list(divisor)
    # делим в столбик: XOR там, где старший бит остатка = 1
    for i in range(len(message)):
        if bits[i] == '1':
            for j in range(len(d)):
                # XOR разряда с делителем
                bits[i + j] = '0' if bits[i + j] == d[j] else '1'
    return ''.join(bits[-r:])       # остаток -- последние r бит

msg = '1101'
gen = '1011'
crc = crc_remainder(msg, gen)
print("Сообщение:", msg, " делитель:", gen)
print("CRC (остаток):", crc)
print("В канал уходит:", msg + crc)

# Приёмник: делит принятое слово на тот же делитель
received = msg + crc
check = crc_remainder(received, gen)[-(len(gen)-1):]
print("Остаток у приёмника:", check, "-- ноль значит данные целы")

Вывод:

Сообщение: 1101  делитель: 1011
CRC (остаток): 001
В канал уходит: 1101001
Остаток у приёмника: 000 -- ноль значит данные целы

Почему CRC ловит пакетные ошибки

Ошибка — это набор перевёрнутых бит, который можно записать как многочлен ошибки $E(x)$. Принятое слово равно $T(x) \oplus E(x)$, где $T(x)$ делится на $G(x)$ нацело. Приёмник заметит ошибку тогда и только тогда, когда $E(x)$ не делится на $G(x)$. Грамотно подобранный $G(x)$ гарантирует:

• обнаружение всех одиночных ошибок;
• обнаружение любого пакета ошибок длиной не больше $r$ (степени делителя) — а именно пакеты и встречаются в реальных каналах;
• обнаружение всех ошибок нечётной кратности, если у $G(x)$ есть множитель $(x+1)$.

Поэтому 32-битный CRC (например, CRC-32 в Ethernet и ZIP) ловит подавляющее большинство искажений: любые пакеты длиной до 32 бит — наверняка, а более длинные — с вероятностью пропуска около $2^{-32}$, то есть примерно один случай на четыре миллиарда. Это несравнимо надёжнее простой контрольной суммы.

Где применяется

Частые ошибки

• Считать CRC шифрованием или защитой от подделки. CRC обнаруживает случайные искажения, но злоумышленник может подделать данные так, чтобы CRC сошёлся. От подмены защищают криптографические хеши (SHA-256) и подписи, а не CRC.
• Использовать обычное вычитание вместо XOR. В арифметике CRC нет переносов; «минус» это XOR. Деление в столбик «по-школьному» с заёмами даст неверный остаток.
• Забывать дописать r нулей к сообщению. Перед делением сообщение умножают на $x^r$ (дописывают $r$ нулей), иначе остаток будет вычислен не от того многочлена.
• Путать CRC с исправлением. CRC только обнаруживает ошибки. Исправляют их другие коды (как Хэмминг) или повторная передача пакета.

Итоги

• CRC трактует биты как двоичный многочлен и берёт остаток от деления на порождающий многочлен $G(x)$.
• Контрольное значение — это $(M(x)\cdot x^r)\bmod G(x)$; вся передаваемая строка делится на $G(x)$ нацело.
• Деление ведётся в двоичной арифметике без переносов: вместо вычитания — XOR.
• Хорошо подобранный $G(x)$ гарантированно ловит все пакетные ошибки длиной до степени делителя — поэтому CRC так надёжен в сетях и архивах.
• CRC обнаруживает, но не исправляет ошибки, и не защищает от намеренной подмены — для этого нужны криптографические хеши.