Циклические контрольные суммы и Matlab

[vak]

Будем рассматривать двоичные данные как полиномы с коэффициентами 0 или 1. Например, байт 10110111 - это полином x⁷+x⁵+x⁴+x²+x+1.

В качестве операции сложения применим "исключающее или", для умножения - "и". Полиномы можно складывать, вычитать, умножать, делить.

Контрольные суммы

Предположим, мы хотим передать по сети пакет длиной N бит. Для Ethernet, например, N находится в диапазоне от 512 до 12112. Чтобы убедиться, что данные не исказились, будем добавлять к каждому пакету 32 дополнительных проверочных бита. Такое дополнение обычно называют контрольной суммой пакета.

Задача - найти способ вычисления проверочных битов, позволяющий обнаруживать максимальное число ошибок в принятом пакете. Один из способов - так называемые циклические контрольные суммы.

Выберем некоторый полином 32-й степени, например x³²+1. Посчитаем остаток от деления пакета данных (полинома N-й степени) на x³²+1. Получим полином 31-й степени, то есть 32 бита, которые и будут контрольной суммой пакета.

Не всякий полином годятся для контрольной суммы. В Википедии приведён список "хороших" полиномов для самых разных применений.

Вычисления в Matlab

В системе Matlab есть встроенные функции для работы с полиномами GF(2).

Создание полинома с заданными коэффициентами:

p = gf ([1 0 1 1], 1)

Получаем полином x³+x+1:

p = GF(2) array. 
Array elements = 
           1           0           1           1

Умножение полиномов:

a = gf ([1 0 1], 1);
b = gf ([1 1], 1);
c = conv (a, b)

Деление полиномов:

d = deconv (c, b)

Деление с остатком:

[d, r] = deconv (c, b)

Пример

Проверим, что полином 0x1F4ACFB13 раскладывается на множители 0x8011, 0xC85F, 3 и 3.

a = gf ([1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1], 1);
b = gf ([1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1], 1);
c = gf ([1 1], 1);
conv (a, conv (b, conv (c, c)))

Результат:

           1           1           1           1           1           0           1           0           0
           1           0           1           0           1           1           0           0           1
           1           1           1           1           0           1           1           0           0
           0           1           0           0           1           1

Comments

Именно на простой!

[matholimp.livejournal.com]

Тогда как x³²+1 раскладывается на множители.

[vak]

"Хорошие" полиномы часто раскладываются на множители. Например CRC-32C, используемый в iSCSI, делится на x+1.