![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
vakБудем рассматривать двоичные данные как полиномы с коэффициентами 0 или 1. Например, байт 10110111 - это полином x7+x5+x4+x2+x+1.
В качестве операции сложения применим "исключающее или", для умножения - "и". Полиномы можно складывать, вычитать, умножать, делить.
Контрольные суммы
Предположим, мы хотим передать по сети пакет длиной N бит. Для Ethernet, например, N находится в диапазоне от 512 до 12112. Чтобы убедиться, что данные не исказились, будем добавлять к каждому пакету 32 дополнительных проверочных бита. Такое дополнение обычно называют контрольной суммой пакета.
Задача - найти способ вычисления проверочных битов, позволяющий обнаруживать максимальное число ошибок в принятом пакете. Один из способов - так называемые циклические контрольные суммы.
Выберем некоторый полином 32-й степени, например x32+1. Посчитаем остаток от деления пакета данных (полинома N-й степени) на x32+1. Получим полином 31-й степени, то есть 32 бита, которые и будут контрольной суммой пакета.
Не всякий полином годятся для контрольной суммы. В Википедии приведён список "хороших" полиномов для самых разных применений.
Вычисления в Matlab
В системе Matlab есть встроенные функции для работы с полиномами GF(2).
Создание полинома с заданными коэффициентами:
Получаем полином x3+x+1:
Умножение полиномов:
Деление полиномов:
Деление с остатком:
Пример
Проверим, что полином 0x1F4ACFB13 раскладывается на множители 0x8011, 0xC85F, 3 и 3.
Результат:
В качестве операции сложения применим "исключающее или", для умножения - "и". Полиномы можно складывать, вычитать, умножать, делить.
Контрольные суммы
Предположим, мы хотим передать по сети пакет длиной N бит. Для Ethernet, например, N находится в диапазоне от 512 до 12112. Чтобы убедиться, что данные не исказились, будем добавлять к каждому пакету 32 дополнительных проверочных бита. Такое дополнение обычно называют контрольной суммой пакета.
Задача - найти способ вычисления проверочных битов, позволяющий обнаруживать максимальное число ошибок в принятом пакете. Один из способов - так называемые циклические контрольные суммы.
Выберем некоторый полином 32-й степени, например x32+1. Посчитаем остаток от деления пакета данных (полинома N-й степени) на x32+1. Получим полином 31-й степени, то есть 32 бита, которые и будут контрольной суммой пакета.
Не всякий полином годятся для контрольной суммы. В Википедии приведён список "хороших" полиномов для самых разных применений.
Вычисления в Matlab
В системе Matlab есть встроенные функции для работы с полиномами GF(2).
Создание полинома с заданными коэффициентами:
p = gf ([1 0 1 1], 1)
Получаем полином x3+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
