Курс практических занятий по теме «Циклические коды» дисциплины «Передача дискретных сообщений», страница 57

Выполненные преобразования используются при быстром декодировании кодов БЧХ для решения ключевого уравнения по алгоритму Евклида.

4.2.11. Вычислить 2¹⁹ (mod5).

Число 2 является примитивным элементом поля GF(5) и 2⁴=1. число 2¹⁹ может быть представлено: 2¹⁹=2^4·4·2³(mod5)=1⁴·2³ (mod5)=2³(mod5)=3

Ответ: 2¹⁹(mod5)=3.

3. Упражнение 3

4.3.1. Доказать, что многочлен х²+х+1 неприводим над полем GF(2).

Решение:

Для доказательства достаточно показать, что данный многочлен не имеет сомножителей, содержащих х в первой степени, т.е. что х или х+1 не делят  многочлен  x²+x+1 в двоичном поле. Этот результат может быть получен тремя способами:

1. Непосредственным делением – предоставляется выполнить читателю.

2. Подстановкой корней х и х+1 в многочлен х²+х+1.

Действительно: корень х равен 0, корень х+1 равен 1.

Проверяем: f(x=0)=0²+0+1=1, т.е. 0 не является корнем х²+х+1

                     f(x=1)=1²+1+1=1, т.е. 1 также не является корнем х²+х+1.

3. Определением, к какому показателю принадлежит х²+х+1, т.е. определением, какой порядок имеют его корни. Для этого представляем х²+х+1=0, откуда х²=х+1. Умножаем обе части равенства на х: х³=х²+х, но х²=х+1, значит х³=х+1+х=1. Следовательно, корни х²+х+1 являются и корнями х³+1, т.е. х²+х+1 принадлежит показателю 3.

Этот результат не является неожиданным, т.к. многочлен вида хⁿ+x^n-1+x^n-2+…+x+1, содержащий все степени х от n до 0 в качестве слагаемых, является сомножителем двучлена вида хⁿ⁺¹+1,наряду с сомножителем х+1. Кроме того, функция Эйлера позволяет определить число корней х³+1, имеющих порядок 3: φ(3)=2. Значит из трёх корней х³+1 два корня имеют порядок 3, а это корни именно многочлена х²+х+1, т.к. порядок корня многочлена х+1 равен 1.