Резюме изграждане на генераторния полином на цикличен код от неговите корени (корени от единство) - Bank

по-малко. Използване теорема 1 могат да образуват поредица от свързани елементи, такава последователност се нарича cyclotomic cosets в литературата. Множеството от елементи, включени в съседен клас (конюгатни елементи) могат да бъдат открити по следната формула:

Когато C - клас cyclotomic, S - степен елемент, чиито елементи са конюгат, р - основния компонент на полето, m - броят на елементите на разширяването на полето.

Да разгледаме пример, когато cyclotomic клас за елемента на GF (24). Тук и по-долу, ние ще представлява елемент като неговата степен.

По този начин, е = 1, р = 2, т = 4.

Така елемент да бъдат сдвоени елементи

Ще бъде оценено, че при изграждането на cyclotomic степен член клас може да бъде по-висока от максималната степен, в резултат на изграждането на разширение полета в този случай е необходимо да се разделят на елемент на полином, в който е конструиран полето за разширение и да се остатъка от деление (защото групата е цикличен, по-горе.). Необходимо е също така да се има предвид, че изграждането на cyclotomic клас, някои от елементите могат да бъдат еднакви, а след това елемент присъства в класа в един екземпляр.

Следствие 2 от Теорема 1:

Две конюгат между елемент ще има същата минимална полином.

Теорема 2. Минимална полином на равно

където елементите на конюгатни

Като следствие на теорема 2: Всички елементи на GF (ч) са корените на полиноми.

Ние изграждане на минимален полином елемент на GF (24). намерени горе Сдвоени елементи.

Използването на Теорема 2, можем да запишем минималния полином на общата форма:

Сега е необходимо да се отварят скобите, както обикновено, без да причинява подобни, като се има предвид, че операцията по изваждане се определя от правилата за поле GF (2), и е еквивалентно на действието на допълнение.

Ако един от елементите е с по-висока степен, отколкото максималната степен на елементите в Таблица 1 (циклична група) е означен елемент е необходимо да се разделят на полином в която разширяването и да се остатъка от деление остатъкът ще представлява желания елемент се конструира. Това се постига с това, че мултипликативна група примитивен елемент образува циклична група (вж. По-горе).

Сега е необходимо да се заменят елементи разлагане в елементите на GF (ч), с оглед на гореизложеното, за отваряне на скобите, защото подобни, като не се забравя, че операцията на прибавяне се извършва модул р (в този пример, модул две, тъй като основното поле е избран GF (2)).

Резюме: За да се намери минимума на полинома за един елемент от GF (ч) изисква

Изграждане на разширяването на полето по модул който не може да бъде намален над GF (п) полином.

Construct cyclotomic клас елемент, като се има предвид, че едни и същи елементи в класа записани само веднъж, и че степента на клас елемент може да надвишава максималната степен на разширение на елементите.

Използване теорема 2 запис разлагане минимален полином използване като корени елементи cyclotomic клас.

Оповестяват разпадане скоби, без да дава подобно.

Проверете дали степента на максимална степен надвишава елементи GF (ч) (см. По-горе).

Замяна на елементи от масив елементи.

Отворете скобите, като олово, предвид факта, че сумиране се извършва по модул стр.

Нека разгледаме следствие от Теорема 2 1:

Cyclotomic клас елемент: за тези четири елемента са същите минимални полиноми.

Да разгледаме по-подробно пример за намиране на минимални полиноми за GF (24).

Изграждане на GF (24) по-горе, ние ще използваме готовия резултат.

Таблица 2. Представяне на GF (24).

Нека започнем с елемента. Въз основа на формула 1, може да се напише множество конюгати:

От всички елементи се оказаха еднакви, cyclotomic клас ще се състои от един елемент -.

Използването на Теорема 2 можем да запишем: m0 (A0) = (х - A0), A0 да замени елемент.

Минимална функция за A0 елемент: m0 (А0) = (х + 1)

С помощта на уравнението 1, ние получаваме cyclotomic клас. ,

Използването на Теорема 2, пишем разширяването на минимален полином.

Сега замени поле на елементите, след разширяване и намаляване на подобен полином за получаване на минималните елементи на градуса 1, 2, 4, 8.

Въз основа на теорема 1 и следствие, елементът ще бъде минимално полином е полином за елемента.

Използване на уравнение 1, се пише cyclotomic клас: С =, както се вижда от елемент 24 отсъства в степента на представяне на поле GF на (24). Ако разделите полином, модул, който произвежда изграждане GF (24), ние се получава остатък.

Използването на Теорема 2, пишем разширяването на минимален полином:

m3 (х) = (х - A3) (х - А6) (х - А9) (х - а12).

Сега, скобите отваряне и други подобни привеждане получи m3 полином (х) = x4 + x3 + х2 + x1 + 1.

Поради това е полином за елементи с градуса 3,6,12,9.

Минимална полином е полином, че негов елемент

С помощта на уравнението 1, пишем cyclotomic клас: C =. Тъй като елементите на минута клас, след това класа ще бъде два елемента от С =.

Използването на Теорема 2, пишем разширяването на минимален полином:

М5 (х) = (х - а5) (х - А10) = х2 + х + 1

Минимална полином е полином, че негов елемент

С помощта на уравнението 1, пишем cyclotomic клас: C =. Тъй като след това C =

Използването на Теорема 2, пишем разширяването на минимален полином:

M7 (х) = (х - А7) (х - А14) (х - a11) (х - А13) = x4 + x3 + 1

Лесно е да се види, че за останалите елементи на минималните полиноми вече са намерени по-горе.

2. Цикличните кодове и корените на полинома на генератора по отношение на крайни полета

Трябва да се отбележи, че този раздел ще се счита за описание на циклични кодове по отношение на крайни полета само в мястото на полинома на генератора. Най-яркият пълно разглеждане на циклични кодове по отношение на крайни полета може да се намери в книгата [2].

ТЕОРЕМА 3. цикличен код с дължина п с генераторен полином г (х), ако и само ако г (х) разделя.

Последица от Теорема 3. генераторен полином на цикличен код с дължина п може да се намери чрез разширяване на основните фактори на полинома:

къде е - броят на основните фактори. Продуктът на всяка подгрупа на тези фактори дава генериране полином г (х). Ако г (х) - генераторен полином, тя се разделя, и следователно. В полином г (х) може да се намери чрез намиране на всички свои председатели делители.

Prime делителя е нищо друго от минимума на функцията или минимални полиноми. По този начин, знаейки, корените на минимален полином, лесно можете да намерите полином код за генериране. Въз основа на дискусията в предишните раздели, можем да заключим, че областта се състои само корените на полиноми минимални, и по този начин съдържа корените на полинома на генератора.

Генериране на полином е нищо друго освен продукт на своите председатели фактори.

Да - коренът на полинома. Ако не друго, като минимум за функцията.

С корените на полиноми - делители на грам (X) могат да намерят техните минимални функции, и по този начин да се намери г (х).

съдържа корени г (х).

Така, намирането на генераторния полином в правомощията на корените се редуцира до намирането на минимални полиноми за поле на елементи с съответната степен.

където минималният полином.

2.1 Откриване на корените на генераторния полином от степен последователност

В таблицата на приложение D от [1] съдържа параметри циклични кодове и последователностите на корените градуса. Ние считаме, че само кодовете тривиални дължина. Част от тази таблица в Приложение А на тази статия е в списъка. Таблицата на приложение Б от [1] е посочено несводима полином над GF (2). По-кратко представяне на тази таблица също трябва да допълнение Б на тази статия.

Алгоритъмът за намиране полиномът на генератора:

Въз основа на избраната дължина код, за конструиране поле разширение по модул несводима полином от степен е равна m. Когато m е намерена от следното съотношение :.

За всеки корен изграждане cyclotomic клас.

За всеки корен да намерите минимален полином.

Умножете получените минимални полиноми за правилата за.

Помислете за всяка стъпка по-подробно в примерния код (15,5,7). За такъв код в таблицата на циклични кодове съдържа следната степен корен.

Стъпка 1. Build.

Предварително определена дължина код п равно на 15. Тъй като, т = 4. Ние конструкт. От м = 4, а след това на масата за който не може да бъде принуден да избере полиноми полином от четвърта степен, която ще бъде построена на модула. Как да се изгради разширение на областта, се е считало, в 1.4.3.

Стъпка 2. Изграждане на cyclotomic класове.

Последователността на корените на градуса за кода -. За всеки елемент от последователност се конструира съседен клас, като се използва формулата. Детайли строителни cyclotomic cosets, описани в 1.4.4

За корен на степен 1.

За корен със степен на 3.

За корен степен 5 това.

Стъпка 3. Намиране на минималните полиноми.

Въз основа на теорема 2, за всеки корен намери минимален полином от намиране на минимума на полиномите описани подробно по-горе.

За корен с една степен:

За корен със степен 3: m3 (х) = (х - A3) (х - А6) (х - А9) (х - а12) = x4 + x3 + х2 + x1 + 1.

За корен със степен на 5: М5 (х) = (х - а5) (х - А10) = х2 + х + 1

Стъпка 4: Намирането полинома на генератор.

1.5, което е минималната полином за даден корен, беше установено, че

W. Peterson, Е. Уелдън. "кодове за корекция на грешката": София: Световни, 1976 година.

R. Blahut. "Теория и практика на грешки кодове за коригиране": София: World, 1986 г. - 576s.

Приложение Таблица на който не може да бъде принуден полиноми над GF (2).

Приложение B. Таблица някои циклични двоични кодове тривиално дължина