Навигация
Примитивный элемент поля и циклическая группа
21743
знака
0
таблиц
12
изображений
1.4.1 Примитивный элемент поля и циклическая группа
Основное свойство конечных полей – это связь между собой ненулевых элементов поля 
и возможность их выражения через степень элемента 
, называемого примитивным, это означает, что любой элемент поля можно представить, как степень примитивного элемента, т.е. 
и т.д. Множество 
элементов расширения поля образуют циклическую мультипликативную группу. Это означает, что все элементы расширения находятся в следующем отношении: 
. Таким образом, умножая элемент на себя можно получить любой элемент расширения поля (мультипликативность), но очевидно, что правило умножения должно быть специфическим, иначе, невозможно обеспечить нужную степень полинома и обеспечить цикличность, т.е. после 
умножений начнется повторение.
Правило умножения в расширении поля аналогично правилу умножения многочленов с последующим приведением по модулю некоторого специального полинома 
степени m. Приведение означает деление результата умножения на полином и использованию только остатка от деления, нужно отметить, что при делении сложение производится по правилам для основного поля, т.е. сложение проводится по модулю числа p.
Выше было сказано, что полином должен быть специальным, это означает, что любые операции, выполняемые по модулю должны оставаться обратимыми, иначе система не образует поле. Таким образом, полином должен быть неприводимым в поле GF(p), т.е. его нельзя разложить на множители, используя только многочлены с коэффициентами из поля GF(p). Аналогом неприводимого полинома является простое число. На сегодняшний день не существует систематического способа поиска неприводимых полиномов. Наиболее обширная таблица неприводимых полиномов представлена в книге [1].
Резюме: Расширение поля содержит полиномы степени m-1 и меньше, с коэффициентами из основного поля. Любой элемент расширения поля можно получить, как степень примитивного элемента . Умножение проводится по модулю неприводимого над полем GF(p) полиномом. Описанная выше теория может показаться запутанной, но ниже будет дан пример, который поможет понять изложенные теоретические сведения.
1.4.2 Модульная арифметика и деление полиномов
Рассмотрим, сложение и умножение по модулю некоторого числа p, это означает проведение операции по обычным правилам, а затем деление результата на число p. Например, умножим 7 на 3 по модулю 10. Обозначим проведение операции по модулю, как «mod» 
. 
Теперь получившийся результат, разделим на 10 и возьмем остаток, остаток равен единице, следовательно 
. Но так как, для работы с двоичными циклическими кодами нам понадобится конечное поле GF(2), которое содержит два элемента – нуль и единицу, то рассмотрим сложение по модулю два. Сумма по модулю два обозначается знаком 
.
11 = 0
10 = 1
00 = 0
01 = 1
Нетрудно убедиться, что если сложить две единицы и разделить на два, то остаток от деления будет равен нулю, а если сложить единицу с нулем и разделить на два, то остаток будет равен единице.
Деление полиномов.
Положим, что коэффициенты в полиномах лежат в поле GF(2), следовательно, все операции будут проводиться по модулю два. Рассмотрим деление полинома 
на полином 
. Алгоритм деления аналогичен простому делению многочлена на многочлен в столбик, с той лишь разницей, что вычитание на каждом шаге деления будет заменено суммой по модулю два.
Рассмотрим деление пошагово:
Не трудно убедиться, что на первом шаге делимое можно взять два раза, то есть умножить делимое на 
: 
. Теперь если сложить 
и по модулю два, то так как присутствует в обоих операндах, то эти элементы сокращаются, так как они одинаковые. Итак, результат первого шага деления:
Далее нужно взять делитель один раз, т.е. умножить его на 
и сложить результат по модулю два с результатом предыдущего шага. Таким образом, получим:
Итак, 
- частное от деления, а 
- остаток.
Умножение полиномов.
Умножим полином на полином .
раскроем скобки по обычным правилам: 
, а теперь проведем суммирование по модулю два, то есть те элементы, которые встречаются четное число раз сокращаются: 
Вычитание полиномов аналогично сложению, вычитание заменяется суммированием.
Похожие работы
... , если его длина n=qm-1 над GF(q). Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным. Общее свойство кодовых слов циклического кода - это их делимость без остатка на некоторый многочлен g(x), называемый порождающим. Результатом деления двучлена xn+1 на многочлен g(x) является проверочный многочлен h(x). При декодировании циклических кодов используются ...
... кодов используются так называемые сверточные коды, контрольные биты, в которых формируются непрерывно из информационных и контрольных бит смежных блоков. Выводы Таким образом, в результате написания реферата, пришли к выводу, что коды Боуза-Чоудхури-Хоквингхема – это широкий класс циклических кодов, способных исправлять многократные ошибки. БЧХ-коды играют заметную роль в теории и практике ...
... ? 8. Какими программами можно воспользоваться для устранения проблем и ошибок, обнаруженных программой Sandra? Раздел 3. Автономная и комплексная проверка функционирования и диагностика СВТ, АПС и АПК Некоторые из достаточно интеллектуальных средств вычислительной техники, такие как принтеры, плоттеры, могут иметь режимы автономного тестировании. Так, автономный тест принтера запускается без ...
... мероприятия по обеспечению однородности выпускаемой продукции. Все эти мероприятия можно объединить в четыре группы: 1. совершенствование технологии производства; 2. автоматизация производства; 3. технологические (тренировочные) прогоны; 4. статистическое регулирование качества продукции. 2.10. Проектирование технологических процессов с использованием средств ...
0 комментариев