construcție Rezumat al polinomului generator unui cod ciclic de rădăcinile sale (rădăcini de unitate) - Banca

mai puțin. Folosind Teorema 1 poate forma o secvență de elemente conjugate, o astfel de secvență este numită în cyclotomic claselor literatura de specialitate. Multitudinea de elemente incluse în coset (elemente conjugate) pot fi găsite prin următoarea formulă:

Unde, C - clasa de cyclotomic, s - element grad ale cărui elemente sunt conjugate, p - componenta de bază a câmpului, m - numărul de elemente ale expansiunii câmpului.

Să considerăm un exemplu, atunci când o clasă cyclotomic pentru elementul GF (24). Aici și în continuare, vom reprezenta elementul ca gradul său.

Astfel, s = 1, p = 2, m = 4.

Elemente Astfel, pentru un element care urmează să fie împerecheate

Se va aprecia că în construirea unui grad membru al clasei cyclotomic poate fi mai mare decât limita maximă, rezultând în construcția câmpurilor de extensie, în acest caz, este necesar să se împartă elementul unui polinom, în care câmpul de extensie a fost construit și să ia restul împărțirii (deoarece grupul este ciclic, supra.). De asemenea, este necesar să se aibă în vedere faptul că construcția clasei cyclotomic, unele dintre elementele pot fi identice, atunci un element este prezent în clasa într-un singur exemplar.

Corolar 2 din Teorema 1:

Doi conjugat între un element va avea același polinomul minimal.

Teorema 2. polinom minim de egale

în care elementele conjugate

Un corolar al teoremei 2: Toate elementele GF (pm) sunt rădăcinile polinoamelor.

Noi construim elementul polinomul minimal al GF (24). Elementele Paired a găsit mai sus.

Folosind Teorema 2, putem scrie polinomul minimal de forma generală:

Acum este necesar să se deschidă paranteze, ca de obicei, fără a provoca similare, ținând cont de faptul că operația de scădere este definit de regulile pentru câmpul GF (2), și este echivalentă cu operația de adăugare.

Dacă unul dintre elementele are un grad mai mare decât gradul maxim al elementelor din tabelul 1 (grupă ciclică) este notat un element care este necesar să se împartă polinomului la care extinderea și ia restul împărțirii, reziduul se va constitui elementul dorit a fost construit. Acest lucru se realizează prin faptul că grupul multiplicativ al elementului primitiv formează un grup ciclic (vezi. De mai sus).

Acum, este necesar să se înlocuiască elementele de descompunere în elementele GF (pm), având în vedere cele de mai sus, pentru a deschide paranteze, cauza asemănătoare, fără a uita că operațiunea de adiție este efectuată modulo p (în acest exemplu, modulo doi, deoarece ca domeniu principal este ales GF (2)).

Rezumat: Pentru a găsi minimul polinomului pentru un element al GF (pm) necesită

Construiți extinderea câmpului modulo unele polinom ireductibil peste GF (p).

Construi element de clasa cyclotomic, având în vedere că aceleași elemente din clasa înregistrată doar o singură dată, și că gradul de element de clasă poate depăși gradul maxim de extindere a elementelor.

Folosind Teorema 2 write descompunerea polinom minimal folosind ca elemente de rădăcini clasa cyclotomic.

Dezvăluie paranteze de descompunere, fără a da similare.

Verificați dacă gradul de grad maxim depășește elemente GF (pm) (cm. Mai sus).

Înlocuiți elementele de pe elementele de matrice.

Deschideți parantezele, cum ar fi plumb, dat fiind faptul că însumarea se face modulo p.

Să considerăm o consecință a Teorema 2 1:

Element clasa Cyclotomic: pentru aceste patru elemente sunt aceleași polinoame minime.

Luați în considerare mai în detaliu un exemplu de a găsi polinoamelor minime pentru GF (24).

Construcția de GF (24) menționat mai sus, vom folosi rezultatul final.

Tabelul 2. Reprezentarea GF (24).

Să începem cu elementul. Pe baza formulei 1, putem scrie o multitudine de conjugate:

Din moment ce toate elementele s-au dovedit la fel, clasa cyclotomic va consta dintr-un singur element -.

Folosind Teorema 2 putem scrie: m0 (a0) = (x - a0), a0 pentru a înlocui un element.

Funcția minimă pentru a0 elementului: m0 (a0) = (x + 1)

Folosind ecuația 1, obținem clasa cyclotomic. .

Folosind Teorema 2, vom scrie extinderea polinomului minimal.

Acum înlocuiți un câmp pe elementele după extinderea și reducerea polinomială similar cu obținerea elementelor minime de grade 1, 2, 4, 8.

Pe baza Teorema 1 și corolar, elementul va fi polinom minimal este un polinom pentru elementul.

Folosind ecuația 1, vom scrie clasa de cyclotomic: C =, așa cum se vede din elementul 24 este absent în gradul de reprezentare al GF câmpului (24). Dacă împărțiți un polinom, modulo care produc GF (24) construirea, vom obține un reziduu.

Folosind Teorema 2, vom scrie extinderea polinomului minimal:

m3 (x) = (x - a3) (x - a6) (x - a9) (x - a12).

Acum, consolele de deschidere și cum ar fi aducerea obține m3 polinomul (x) = x4 + x3 + x2 + x1 + 1.

Prin urmare, acesta este un polinom pentru elemente cu grade 3,6,12,9.

polinomul minimal este un polinom ca membru al elementului

Folosind ecuația 1, vom scrie clasa de cyclotomic: C =. Deoarece elementele meciului de clasă, atunci clasa va fi de două elemente de C =.

Folosind Teorema 2, vom scrie extinderea polinomului minimal:

m5 (x) = (x - a5) (x - a10) = x2 + x + 1

polinomul minimal este un polinom ca membru al elementului

Folosind ecuația 1, vom scrie clasa de cyclotomic: C =. Deoarece, atunci C =

Folosind Teorema 2, vom scrie extinderea polinomului minimal:

m7 (x) = (x - a7) (x - a14) (x - a11) (x - a13) = x4 + x3 + 1

Este ușor de observat că pentru elementele rămase ale polinoame minime deja constatate mai sus.

2. Codurile ciclici și rădăcinile polinomului generatorului în termeni de câmpuri finite

Trebuie remarcat faptul că această secțiune va fi considerată o descriere a codurilor ciclice în termeni de câmpuri finite numai în locația polinomul generatorului. Cea mai clară considerare completă a codurilor ciclice în termeni de câmpuri finite pot fi găsite în cartea [2].

TEOREMA 3. Un cod ciclic de lungime n cu polinomului generator g (x) dacă și numai dacă g (x) se divide.

Consecință teoremei 3. polinomului generator al codului ciclic de lungime n poate fi găsit prin extinderea factorii principali ai polinomului:

în cazul în care s - numărul de factori de prim. Produsul oricărui subset al acestor factori conferă un generator de polinom g (x). Dacă g (x) - un polinom generator, se divide, și de aceea. Polinomul g (x) poate fi găsit prin găsirea tuturor divizorilor sai prim.

divizori Prime nu este nimic altceva decât minimul funcției sau polinoame minime. Astfel, cunoscând rădăcinile polinomului minimal, puteți găsi cu ușurință polinomul generator de cod. Pe baza discuțiilor în secțiunile anterioare, putem concluziona că domeniul cuprinde doar rădăcinile polinoamelor minimale, și conține, astfel, rădăcinile polinomului generatorului.

Generarea polinomial nu este altceva decât produsul dintre factorii principali.

Să - rădăcina polinomului. Dacă nimic altceva, cel puțin pentru funcția.

Cu rădăcinile polinoamelor - divizori de g (x) pot găsi funcțiile lor minime, și, astfel, pentru a găsi g (x).

cuprinde rădăcini g (x).

Astfel, găsirea polinomul generator de la puteri de rădăcinile sale se reduce la găsirea polinoamelor minime pentru un câmp de elemente cu un grad corespunzător.

în cazul în care polinomul minimal.

2.1 Găsirea rădăcinile polinomului generator secvenței grad

În tabelul din Anexa D din [1] conține parametri de coduri ciclice și secvențele de rădăcini de grade. Considerăm că numai codurile de lungime triviale. O parte din acest tabel este listat în Anexa A a acestui document. Tabelul din anexa B [1] specificat polinom ireductibil peste GF (2). Prezentarea scurtă a acestui tabel, de asemenea, Anexa B a lucrării de față.

Algoritmul pentru identificarea polinomul generator de:

Pe baza lungimii codului selectat, pentru a construi un câmp de extensie modulo un polinom ireductibil de grad este egal cu m. În cazul în care m este găsit din următoarea relație :.

Pentru fiecare rădăcină a construi clasa cyclotomic.

Pentru fiecare rădăcină pentru a găsi polinomului minimal.

Înmulțiți rezultate polinoame minime cu privire la regulile de.

Luați în considerare fiecare pas mai în detaliu în exemplul de cod (15,5,7). Pentru un astfel de cod din tabelul de coduri ciclice conțin următorul nivel de rădăcină.

Pasul 1. Build.

Lungimea codului predeterminata n egal cu 15. Deoarece, m = 4. Construim. Deoarece m = 4, apoi din tabelul polinoamelor ireductibile alege un polinom de gradul al patrulea, care va fi construit pe modul. Cum de a construi o extindere a domeniului, a fost luată în considerare în 1.4.3.

Etapa 2. Construcția claselor cyclotomic.

Secvența de rădăcini de grade pentru codul -. Pentru fiecare element al unei secvențe de a construi o coset, folosind formula următoare. Detalii de construcție descris în cyclotomic claselor 1.4.4

Pentru o rădăcină de gradul 1 este.

Pentru o rădăcină cu un grad de 3 este.

Pentru un grad de rădăcină de 5 asta.

Pasul 3. Găsirea polinoame minime.

Bazat pe Teorema 2, pentru fiecare rădăcină găsi polinom minimal prin găsirea minimul polinoamele descrise în detaliu mai sus.

Pentru root cu 1 grad:

Pentru o rădăcină cu un grad de 3: m3 (x) = (x - a3) (x - a6) (x - a9) (x - a12) = x4 + x3 + x2 + x1 + 1.

Pentru o rădăcină având un grad de 5: m5 (x) = (x - a5) (x - a10) = x2 + x + 1

Pasul 4: Găsirea unui polinom generator de.

1.5, care este polinomul minimal pentru o anumită rădăcină, sa constatat că

W. Peterson, E. Weldon. "codurilor corectoare de eroare": București: World, 1976.

R. Blahut. „Teoria și practica codurilor corectoare de erori“: București: World, 1986. - 576s.

Tabel Apendice ireductibile polinoame peste GF (2).

Anexa B. Tabel anumite coduri binare ciclice lungime trivială