Примитивные полиномы
Среди полиномов, которые можно использовать для построения циклического кода длины n, существуют так называемые примитивные полиномы, которые дают число ненулевых синдромов, равное 2 r -1. Именно такие полиномы следует использовать для построения кодов, исправляющих ошибки. Такие полиномы степени (r=23) используются, например, в системах мобильной связи и технологиях xDSL (x 23 +x 5 +1).
Например: Для построения циклического кода (15, 11) можно использовать образующий полином g1(x)=x 4 +x+1, который является примитивным и дает 15 ненулевых остатков, то есть этот код можно использовать для исправления одиночных ошибок. Или можно использовать образующий полином g2(x)=x 4 +x 3 +x 2 +x+1, который не является примитивным, дает только 5 ненулевых остатков, и, поэтому, полученный код можно использовать только в режиме обнаружения ошибок.
Признаком примитивных полиномов является наличие остатка равного 1 только для полиномов x 0 и x n .
Коды crc
Как уже отмечалось, для построения циклического кода длины n можно использовать полиномы, которые входят в разложение, то есть являются делителями полинома x n +1. При больших значениях n делителей степени r=n—k может быть много. Вопрос: какой из этих делителей порождает наилучший код? – не имеет однозначного ответа. Международный союз электросвязи рекомендует пользоваться таблицей наилучших двоичных циклических кодов, которые стандартизованы для различных систем передачи данных. Эта группа циклических кодов получила название CRC-коды (Cyclic redundancy check – контроль ошибок с помощью циклического избыточного кода).
Эти коды обладают следующими свойствами:
Коды имеют кодовое расстояние dmin=4.
Коды обнаруживают все ошибки веса 3 и менее.
Коды обнаруживают все ошибки нечетного веса.
Коды обнаруживают все пакеты ошибок длины l=r или менее.
Перечисленные свойства позволяют эффективно использовать CRC-код в системах передачи данных с автоматическим запросом повторения, то есть в протоколах ARQ.
Образующие полиномы CRC-кодов — g(x)
X 16 +X 12 +X 5 +1
X 32 +X 26 +X 23 +X 22 +X 16 +X 12 +X 11 +X 10 + X 8 +X 7 +X 5 +X 4 +X 2 +X+1
Сетевые адаптеры локальных сетей, контроллеры жестких дисков
Использование crc-кода в технологии атм
(Asynchronous Transfer Mode)
В технологии АТМ данные любой природы передаются пакетами фиксированной длины 53 Байт. Пакеты АТМ получили название ячеек (cell). Из 53-х пять байт составляют заголовок ячейки. Собственно управляющая информация занимает 4 байта, последний байт заголовка называется HEC – Header Error Control, и представляет контрольную последовательность заголовка, полученную при кодировании предыдущих 4-х байт циклическим кодом CRC-8.
Общее управление потоком GFC – Generic Flow Control (4 бита) [UNI] или VPI [NNI]
Идентификатор виртуального пути VPI – Virtual Path Identifier (4 бита)
Идентификатор виртуального канала VCI – Virtual Channel Identifier
Тип полезной нагрузки PTI – Payload Type Identifier (3 бита)
Контрольная сумма заголовка HEC – Header Error Control
48 Байт – информационное поле
CLP (Cell Loss Priority) – приоритет потери ячеек
Образующий полином g(x)=x 8 +x 2 +x+1=(x+1)*(x 7 +x 6 +x 5 +x 4 +x 3 +x 2 +1)
Из стандартного циклического кода с параметрами (127, 120) получен укороченный код (40, 33). Один информационный бит используется для проверки на четность. В результате в стандарте АТМ используется укороченный код (40, 32). Код содержит 2 32 кодовых слов, скорость кода R=0,8 , кодовое расстояние dmin=4 . Вероятность необнаруженной ошибки составляет величину порядка 10 -25 при условии передачи сообщений по дискретному каналу с независимыми ошибками и вероятностью возникновения ошибки в двоичном символе pe=10 -8 (что характерно для передачи по оптоволоконным линиям связи).
Однако это идеализированная ситуация, и в стандарте реализуется алгоритм работы декодера ячеек АТМ для случая работы по дискретному каналу с памятью с двумя состояниями.
Модель передачи ячеек АТМ по каналу с двумя состояниями
Предполагается, что дискретный канал может находиться в двух состояниях – хорошем состоянии и плохом. Этим состояниям соответствуют два режима работы декодера ячеек АТМ.
При получении каждой ячейки вычисляется ее контрольная последовательность и сравнивается с содержимым HEC. Пока ошибки не обнаруживаются (канал находится в хорошем состоянии), декодер остается в режиме исправления одиночных ошибок. При обнаружении ошибок декодер вычисляет число ошибочных бит. При возникновении одиночной ошибки, она исправляется. В случае многократной ошибки ячейка стирается. В любом случае декодер предполагает, что канал перешел в плохое состояние, в котором наиболее вероятно возникновение многократных ошибок (пакетов ошибок), и переходит в режим обнаружения ошибок. В этом режиме все ячейки с обнаруженными ошибками отбрасываются. Попытки исправлять ошибки не предпринимаются. После получения ячейки без ошибок декодер возвращается в режим исправления одиночных ошибок.
При 
вероятность отбрасывания ячеек 
.
Примитивный полином
Поскольку все минимальные многочлены неприводимы , примитивные многочлены также неприводимы.
Примитивный многочлен должен иметь ненулевой постоянный член, в противном случае он делился бы на . Над полем из двух элементов находится примитивный многочлен, а все другие примитивные многочлены имеют нечетное количество членов, так как каждый многочлен по модулю 2 с четным числом членов делится на . Икс <\ displaystyle X>Икс + 1 <\ displaystyle X + 1>Икс + 1
Все нули примитивного многочлена имеют порядок . п м — 1 <\ displaystyle p ^
Приложения
Изображение элементов тела
Примитивные полиномы используются для представления элементов конечного поля . Если существует корень примитивного многочлена , то порядок , т.е. все элементы могут быть представлены как последовательные степени : α ∈ г Ф. ( п м ) <\ Displaystyle \ альфа \ в \ mathrm
Если эти элементы приводятся по модулю , то представление в виде полиномиального базиса всех этих элементов образует твердое тело. Ф. ( Икс )
Генерация псевдослучайных чисел
Примитивные полиномы определяют повторяющееся отношение, которое можно использовать для генерации битов псевдослучайных чисел . Фактически, каждый регистр сдвига с линейной обратной связью с максимальным циклом (это длина 2 lrsr — 1) относится к примитивным полиномам.
Быть z. Б. задан примитивным многочленом . (Engl. Вы начинаете с пользовательскими семенами семян , семян быть, это вовсе не обязательно выбирается случайным образом ). Затем вы берете 10-й, 3-й и 0-й бит , отсчитываемые от младшего значащего бита , объединяете их с помощью XOR и получаете новый бит. Затем начальное число сдвигается влево, и новый бит становится младшим значащим битом начального числа. Это можно повторить для генерации псевдослучайных битов. Для последовательности максимальной длины требуются очень специфические выходы сдвигового регистра. Икс 10 + Икс 3 + 1 <\ displaystyle X ^ <10>+ X ^ <3>+1> 2 10 — 1 знак равно 1023 <\ displaystyle 2 ^ <10>-1 = 1023>
В общем, для примитивного полинома степени этот процесс генерирует псевдослучайные числа перед повторением последовательности. м <\ displaystyle m>2 м — 1 <\ displaystyle 2 ^
Примитивные трехчлены
Примитивные трехчлены — это примитивные многочлены только с тремя ненулевыми членами. Трехчлены очень просты и используются для очень эффективных генераторов случайных чисел. Есть несколько методов идентификации и тестирования примитивных трехчленов. Простой тест работает так: для каждого , поскольку простое число Мерсенна является трехчленом степени, является примитивным тогда и только тогда, когда оно неприводимо. Алгоритмы, недавно разработанные Ричардом П. Брентом , позволили находить примитивные трехчлены высокой степени, такие как: B. . Это позволяет создавать псевдослучайные генераторы с огромным периодом или ок . р <\ displaystyle r>2 р — 1 <\ displaystyle 2 ^
Примитивный многочлен
В разных областях математики примитивный многочлен может означать:
- В теории чисел и теории полей примитивный многочлен — это минимальный многочлен (англ.) примитивного элемента поля
для положительного целого числа m. - В алгебрепримитивный многочлен — это всякий многочлен
![f(x)\in R[x]](https://dic.academic.ru/dic.nsf/ruwiki/c73681c532005617794246d16a13e6d1.png)
, где 
— ассоциативно-коммутативное кольцо с однозначным разложением на множители, коэффициенты которого не имеют нетривиальных общих делителей.
| Список значений слова или словосочетания со ссылками на соответствующие статьи. Если вы попали сюда из другой статьи Википедии, пожалуйста, вернитесь и уточните ссылку так, чтобы она указывала на статью. |
- Многозначные термины
Wikimedia Foundation . 2010 .
Полезное
Смотреть что такое «Примитивный многочлен» в других словарях:
примитивный многочлен — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN primitive polynomial … Справочник технического переводчика
ПРИМИТИВНЫЙ МНОГОЧЛЕН — многочлен , где R ассоциативно коммутативное кольцо с однозначным разложением на множители, коэффициенты к рого не имеют нетривиальных общих делителей. Любой многочлен можно записать в виде g(X)=c(g)f(X), где f(X) П. м., a c(g) наибольший общий… … Математическая энциклопедия
Примитивный многочлен (алгебра) — У этого термина существуют и другие значения, см. Примитивный многочлен. В алгебре примитивный многочлен это всякий многочлен , где ассоциативно коммутативное кольцо с однозначным разложением на множители, коэффициенты которого не имеют… … Википедия
Примитивный многочлен (теория чисел) — У этого термина существуют и другие значения, см. Примитивный многочлен. В теории чисел и теории полей примитивный многочлен над конечным полем это минимальный многочлен (англ.) примитивного элемента поля для положительного целого числа m.… … Википедия
Многочлен над конечным полем — Многочленом над конечным полем называется формальная сумма вида Здесь целое неотрицательное число, называемое степенью многочлена , а элементы алгебры над … Википедия
Примитивный элемент конечного поля — Примитивным элементом конечного поля называется всякий первообразный корень степени , то есть всякий генератор мультипликативной группы этого поля. Свойства Если примитивный элемент поля , то любой другой примитивный элемент может быть получен… … Википедия
Лемма Гаусса — Примитивный многочлен многочлен , где R ассоциативно коммутативное кольцо с однозначным разложением на множители, коэффициенты которого не имеют нетривиальных общих делителей. Любой многочлен можно записать в виде g(x) = cgf(x), где f(x)… … Википедия
Поточный шифр — это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточный шифр реализует другой подход к … Википедия
Linear feedback shift register — (LFSR линейный сдвиговый регистр с обратной связью) один из методов генерации псевдослучайных чисел. Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи. Сдвиговый регистр последовательность … Википедия
Линейный регистр сдвига с обратной связью — Linear feedback shift register (LFSR линейный регистр сдвига с обратной связью) один из методов генерации псевдослучайных чисел. Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи … Википедия
Примитивный многочлен
В рассмотренном выше примере 1.4.3 построения поля расширения по модулю неприводимого многочлена элементом максимального порядка q m — 1 =7 оказался корень а выбранного неприводимого многочлена. Таким образом, элемент а построенного поля расширения примитивен. Поэтому мы можем записать все ненулевые элементы поля в виде степеней элемента а:
Теперь мы можем выполнять умножение в поле расширения, не зная даже таблицы умножения этого поля. Например: а 5 -а 6 = а 11 = а 4 -а 7 = а 4 -1 = а 4 = а 2 + а. Сложение в таком поле выполняется еще проще. Для этого достаточно сложить соответствующие степени примитивного элемента а по законам сложения исходного поля GF(2), то есть по модулю 2: а 5 + а 6 = (а 2 + а + 1) + (а 2 + 1) = а. В обоих случаях не требуется вычислять остаток от деления, а также выполнять поэлементное умножение соответствующих степеней, как в случае умножения в кольце многочленов.
Поскольку любой ненулевой элемент поля в этом случае соответствует некоторой степени элемента а, то для деления элементов в таком поле нет необходимости искать обратные мультипликативные элементы. Достаточно выполнить вычитание степеней, как при арифметическом делении разных степеней одного и того же числа. Например, в поле GF(2 3 ) а 2 -а 3 = а 5 = а 2 + а + 1. Кроме того, так как а^ -1 -1 = 1, то при получении отрицательной степени в результате деления также достаточно просто найти соответствующий элемент положительной степени. Например, в поле GF(2 3 ) а 5 /а 8 = а -3 . Так как в этом случае q m —1 = 7 и а 7 = = 1, то а -3 = 1/а 3 = а 7 /а 3 = а 4 .
Несмотря на то, что процесс деления не требует поиска обратного мультипликативного элемента, такой элемент все же существует для любого элемента и может быть легко найден из равенства а^» 7 — 1 — 1 = 1. Например, обратным мультипликативным элементом элемента а 7 будет элемент а 8 , так как а 15 = 1
и (а 7 ) -1 = 1/а 7 = а 15 /а 7 = а 8 .
Обратный аддитивный элемент любого элемента поля в этом случае всегда равен исходному элементу поля.
Таким образом, мы определили объект, обладающий всеми свойствами поля. При этом полученное поле характеризуется исключительно простыми операциями сложения и умножения.
В примере 1.4.3 построения поля GF(2 3 ) примитивным элементом оказался корень выбранного неприводимого многочлена. Однако это выполняется далеко не для всех неприводимых многочленов над полем GF(2).
Рассмотрим, например, многочлен р(х) = х 4 + х 3 + х 2 + х+’ над GF( 2). Проверив все возможные делители, можно убедиться в том, что этот многочлен делится только сам на себя и на 1 и, следовательно, неприводим в GF(2). Однако, определяя ненулевые элементы поля GF(2 3 ) как степени корня (3 рассматриваемого многочлена, можно получить лишь пять неповторяющихся элементов:
Проверив все возможные комбинации, можно определить, что примитивным в данном случае является элемент (3 + 1: 
то элемент (3 + 1 не является корнем многочлена х* + х* + х 2 + х+’.
Таким образом, можно сделать вывод о том, что поле может быть построено из кольца многочленов по модулю любого неприводимого многочлена. И это поле будет соответствовать рассмотренному в параграфе 1.2 полю многочленов.
Однако при построении поля расширения по степеням примитивного элемента, равного корню неприводимого в простом поле многочлена, требуется дополнительный критерий выбора неприводимого многочлена. Дело в том, что среди неприводимых многочленов существует особый класс многочленов, называемых примитивными многочленами.
Например, в случае многочлена х 3 + х + 1 степени переменной х по модулю указанного многочлена образуют все ненулевые элементы GF(2 3 ) как поля многочленов:
В таком поле примитивный элемент всегда известен заранее.
Следует отметить, что примитивный многочлен должен отвечать еще одному условию. Ниже, в параграфе 1.5, будет показано, что корнями примитивного многочлена степени т над полем GF(q), помимо примитивного элемента поля расширения GF(q m ), являются также т — 1 других элементов поля GF Поэтому разложение примитивного многочлена можно записать следующим образом:
где (3i = а — примитивный элемент поля расширения GF(q m ). Ясно, что элемент а и остальные элементы поля GF(q m ) в разложении многочлена р <х)также будут корнями многочлена а-р(х), где а Ф 0 — произвольный элемент (константа) поля GF(q).
Таким образом, коэффициент at 1 не меняет представление элементов поля расширения, построенного по степеням корня а-р(х), однако усложняет процедуру построения поля. Поэтому к примитивному многочлену предъявляют еще одно условие: коэффициент при старшей степени неопределенной переменной примитивного многочлена должен быть равен единице.
Многочлен, старший коэффициент которого равен единице, называется нормированным многочленом.
Таким образом, примитивный многочленр(х) =x m + pm-rx m_1 + рт-гх т
2 + + . + ргх + ро степени т > 1 — это нормированный неприводимый над полем GF(q) многочлен, корень которого соответствует примитивному элементу расширения GF(q m ) поля GF(q), построенного по модулю р(х).
В предыдущих двух параграфах мы определили способы построения и условия существования полей целых чисел и полей многочленов над полями целых чисел. При этом мы определяли поле многочленов не как поле расширения простого поля, а как некое самостоятельное поле. Теперь же мы можем достаточно просто определить поле как расширение GF(q m ) исходного поля GF(q).
В поле расширения по модулю неприводимого и не примитивного многочлена необходимо определять все элементы и строить таблицы сложения и умножения или каждый раз при необходимости сложить или умножить элементы поля производить довольно непростые вычисления. Кроме того, в случае отсутствия таблицы умножения деление в таком поле связано с поиском обратного мультипликативного элемента при помощи алгоритма Евклида. Даже в полях расширения небольших порядков все это представляет большую сложность.
Полученное в этом параграфе представление поля расширения GF(q m ) является наиболее удобным, и далее мы будем работать именно с таким представлением поля расширения. Поэтому условимся, что далее под полем расширения GF(q m ) будем иметь в виду именно поле, построенное по модулю примитивного многочлена.
Следует все же отметить, что и у этого представления поля есть свои недостатки. А именно — представление степени примитивного элемента в виде суммы степеней, например, для выполнения сложения. К примеру, в поле GF(2 8 ), с которым мы еще не раз встретимся ниже, уже достаточно трудно выполнять сложение. В качестве примера читателю предлагается выполнить сложение элементов а 131 и а 218 и представить результат в виде степени примитивного элемента поля расширения GF(2 8 ). Примитивный многочлен степени 8 над GF(2) в этом случае р<х) = х 8 + х А + х 3 + х 2 + '.