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