Модульная арифметика и деление полиномов

Рассмотрим, сложение и умножение по модулю некоторого числа p, это означает проведение операции по обычным правилам, а затем деление результата на число p. Например, умножим 7 на 3 по модулю 10. Обозначим проведение операции по модулю, как «mod» . Теперь получившийся результат, разделим на 10 и возьмем остаток, остаток равен единице, следовательно . Но так как, для работы с двоичными циклическими кодами нам понадобится конечное поле GF(2), которое содержит два элемента – нуль и единицу, то рассмотрим сложение по модулю два. Сумма по модулю два обозначается знаком .

1 1 = 0

1 0 = 1

0 0 = 0

0 1 = 1

Нетрудно убедиться, что если сложить две единицы и разделить на два, то остаток от деления будет равен нулю, а если сложить единицу с нулем и разделить на два, то остаток будет равен единице.

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

Положим, что коэффициенты в полиномах лежат в поле GF(2), следовательно, все операции будут проводиться по модулю два. Рассмотрим деление полинома на полином . Алгоритм деления аналогичен простому делению многочлена на многочлен в столбик, с той лишь разницей, что вычитание на каждом шаге деления будет заменено суммой по модулю два.

Рассмотрим деление пошагово:

Не трудно убедиться, что на первом шаге делимое можно взять два раза, то есть умножить делимое на : . Теперь если сложить и по модулю два, то так как присутствует в обоих операндах, то эти элементы сокращаются, так как они одинаковые. Итак, результат первого шага деления:

Далее нужно взять делитель один раз, т.е. умножить его на и сложить результат по модулю два с результатом предыдущего шага. Таким образом, получим:

Итак, - частное от деления, а - остаток.

Дата добавления: 2015-07-02