Ciklinis kodas

Cikliniai kodai yra tarp blokinių sisteminių kodų, kuriuose kiekvienas derinys yra užkoduotas atskirai (bloko pavidalu) taip, kad informacija k ir valdymo simboliai visada būtų vienodi.

apsirengti tam tikrose vietose. Galimybė aptikti ir ištaisyti beveik visas klaidas su santykinai mažu dubliavimu, palyginti su kitais kodais, taip pat kodavimo ir dekodavimo įrangos grandinės įgyvendinimo paprastumas padarė šiuos kodus plačiai paplitusius. Ciklinių kodų teorija remiasi grupių teorija ir daugianarių algebra per Galois lauką.

Ciklinis kodas yra kodas, kuriame kodų kombinacijų paskirstymo tvarka vykdoma taip, kad pereinant iš bet kurios kombinacijos į gretimą, kiekvieną kartą Hamingo kodo atstumas išlieka pastovus.

Cikliniai kodai yra visa klaidoms atsparių kodų šeima, įskaitant Hamingo kodus kaip vieną iš jų atmainų, tačiau apskritai suteikia daugiau lankstumo, kad būtų galima įdiegti kodus, turinčius būtiną galimybę aptikti ir ištaisyti klaidas, atsirandančias perduodant kodų derinius. komunikacijos kanalu. Ciklinis kodas reiškia sisteminius blokinius (n, k) kodus, kuriuose pirmieji k skaitmenų reiškia pirminio kodo derinį, o paskesni (n ? k) skaitmenys yra kontroliniai.

Ciklinių kodų konstravimas pagrįstas perduodamo kodo derinio padalijimu iš generuojamo r laipsnio neredukuojamo polinomo. Likusi padalijimo dalis naudojama kontroliniams skaitmenims formuoti. Šiuo atveju prieš dalybos operaciją atliekama daugybos operacija, kuri k bitų informacijos kodo kombinaciją perkelia r bitais į kairę.

Dauginamas (polinomas), kuris gali būti pavaizduotas kaip žemesnių laipsnių daugianario sandauga, vadinamas redukuojamu (tam tikrame lauke), kitu atveju neredukuojamu. Neredukuojami daugianariai atlieka panašų vaidmenį kaip pirminiai skaičiai skaičių teorijoje. Neredukuojamieji daugianariai P(X) gali būti rašomi dešimtaine arba dvejetainiai skaičiai arba algebrinio daugianario pavidalu.

Ciklinis kodavimo procesas

Ciklinis kodavimas pagrįstas neredukuojamo daugianario P(X) naudojimu, kuris ciklinių kodų atžvilgiu vadinamas generatoriumi, generatoriumi arba generuojančiu polinomu (polinomu).

Dvejetainio kodo deriniai visoms kombinacijoms laikomi informaciniais simboliais k cikliniams kodams sudaryti. Bendruoju atveju, jei duotas kodo derinys Q(x) padauginamas iš generuojančio polinomo P(x), gaunamas ciklinis kodas, turintis tam tikras korekcines savybes, priklausomai nuo P(x) pasirinkimo. Tačiau šiame kode valdymo simboliai m bus išdėstyti labai įvairiose kodų kombinacijos vietose. Toks kodas nėra sistemingas, todėl sunku jį įdiegti. Situaciją galima žymiai supaprastinti, jei pabaigoje, ty po informacinių simbolių, pridedami valdymo simboliai. Šiuo tikslu patartina naudoti šį metodą:

Kodo kombinaciją G(x), kurią reikia užkoduoti, padauginame iš monomio X m, turinčio tokį patį laipsnį kaip generuojantis polinomas P(x);

sandaugą G(x)Х m padalijame iš generuojančio daugianario Р(х m):

čia Q(x) yra padalijimo koeficientas; R(x) – liekana.

Padauginus išraišką (2.1) iš P(x) ir perkeliant R(x) į kitą lygybės dalį, nekeičiant ženklo, gauname:

Taigi, pagal lygybę (2.2), ciklinis kodas, tai yra užkoduotas pranešimas F(x), gali būti suformuotas dviem būdais:

Vieno dvejetainio kodo kodo derinio padauginimas iš visų kombinacijų generuojančiu polinomu P(x);

Padauginus nurodytą kodo derinį G(x) iš vieno daugianario X m, kurio laipsnis yra toks pat kaip generuojantis polinomas P(x), pridedant likutį R(x), gautą padalijus sandaugą G(x)X m iš generavimo daugianario P( X).

Laiškų kodavimas

Reikia užkoduoti kodo kombinaciją 1100, kuri atitinka G(x)=x 3 +x 2, naudojant P(x)=x 3 +x+1.

G(x) padauginame iš X m, kuris turi trečiąją laipsnį, gauname:

Padalinę sandaugą G(x)Х m iš generuojančio daugianario Р(х m), pagal (2.1) gauname:

arba dvejetainiu ekvivalentu:

Taigi, gauname to paties laipsnio, kaip ir G(x), koeficientą Q(x):

Q(x)=x 3 +x 2 +x>1110

o likusi dalis:

Dėl to dvejetainio kodo derinys, užkoduotas cikliniu kodu, pagal (2.2), bus tokia forma:

F(x)=1110 1011=1100010

Kadangi kiekviena leistina ciklinio kodo kombinacija atspindi visas įmanomas generuojančio polinomo G(x) sumas, jos turi dalytis iš P(x) be liekanos. Todėl, norint patikrinti priimto kodo derinio teisingumą, reikia identifikuoti likusią dalį, dalijant ją iš generuojančio daugianario.

Balanso gavimas rodo klaidos buvimą. Likusi ciklinių kodų padalijimo dalis atlieka sindromo vaidmenį.

Pavyzdžiui, perduodamas kodo derinys F(x)=1100010, sudarytas naudojant generuojamąjį polinomą P(x)=1011. Veikiant trukdžiams kodų derinys buvo transformuotas į kombinaciją F"(x)=1000010

Priimtą derinį padalijame iš generuojamojo daugianario

Likutis R(x)=001 rodo klaidą. Tačiau jis tiesiogiai nenurodo derinio klaidos vietos. Norint nustatyti klaidą, yra keli metodai, pagrįsti sindromo analize.

Nustatykime klaidos vietą, kad tai padarytume, padalykite vieną su savavališku nulių skaičiumi iš P(x) = 1011.

Elemento numeriuose įvyko klaida:

Likučių skaičius -2>4-2=2

Tai yra, klaida yra antrame elemente.

Ciklinis kodas yra linijinis kodas, kuris yra baigtinė aibė, kuri yra uždaryta veikiant jį sudarančių kodo vektorių cikliniam poslinkiui. Tegul tai duota n- matmenų vektorius v = a 0 a 1 …a n-1 su koordinatėmis iš galutinio lauko F. Jo ciklinis poslinkis vadinamas vektoriumi v"= a n-1 a 0 a 1… a n -2 .

Pasvarstykime n-dimensinė aritmetinė erdvė virš Galois lauko GF(2). Kiekvienas vektorius a 0 a 1 …a n-1 iš GF(2) galima palyginti daugianarį vienas su vienu a 0 +a 1 x+…+a n -1 x n-1 su koeficientais nuo GF(2). Dviejų vektorių suma a 0 a 1 …a n-1 ir b 0 b 1 …b n-1 derinamas su juos atitinkančių polinomų suma, lauko elementų sandauga iš vektoriaus - daugianario, atitinkančio šį vektorių, sandauga pagal elementą.

Panagrinėkime keletą daugianario g(x) iš aprašytos tiesinės erdvės. Visų šios poerdvės daugianarių, kurie dalijasi iš likučio, rinkinys g(x), sudaro tiesinę poerdvę. Linijinė poerdvė apibrėžia tam tikrą linijinį kodą.

Linijinis kodas, sudarytas iš daugianario klasės C(g(x)), kurio nors daugianario kartotiniai g(x), vadinamas generuojančiu polinomu, vadinamas daugianario.

Parodykime, kaip yra susiję daugianario kodai C(g(x)) ir ciklinius kodus. Leisti a = a 0 …a n-1 yra tam tikras kodo žodis ir atitinkamas kodo polinomas a(x) = a 0 +...+a n -1 x n-1. Ciklinė pavara a“ atitinka kodo daugianarį a"(x) = a n -1 +a 0 x+…+a n -2 x n -1 , kuris gali būti išreikštas originalu:

Kadangi daugianario kodas turi dalytis iš g(x), tada, kad jis būtų cikliškas, daugianario a"(x) turi dalytis iš g(x). Remdamiesi tuo, galime suformuluoti tokią teoremą. Polinomo kodas yra ciklinis tada ir tik tada, kai polinomas g(x) yra daugianario daliklis x n-1. Šiuo atveju daugianomas g(x) vadinamas ciklinio kodo generuojančiu polinomu.

Kodavimo teorijoje įrodyta tokia teorema: jei daugianario g(x) turi diplomą n–k ir yra daliklis x n-1 tada C(g(x)) yra tiesinis ciklinis ( n, k)-kodas.

Polinomas x n–1 faktorius x n–1 = (x–1)(x n -1 +x n-1 +…+1). Todėl cikliniai kodai egzistuoja bet kuriai n. Ciklinių skaičius n-bitų kodai yra lygus daugianario daliklių skaičiui x n-1. Cikliniams kodams sudaryti buvo sukurtos polinominės išplėtimo lentelės x n–1 į neredukuojamus daugianarius, tai yra į tuos, kurie dalijasi tik iš vienybės ir iš savęs.

Panagrinėkime, pavyzdžiui, kokius kodus galima sukurti remiantis polinomu x 7:1 per aikštę GF(2). Polinomo išplėtimas į neredukuojamus veiksnius turi formą

Kadangi galima sudaryti šešis daugianario daliklius x 7–1, jungiant neredukuojamus daliklius, yra šeši dvejetainiai cikliniai kodai. ( n, k)-kodas nustatomas, pirma, pagal reikšmę n ir, antra, vertė k = n – s, s– daliklio daugianario laipsnis x n–1, kuris apibrėžia kodą. Žemiau pateikiami daugianario dalikliai ir atitinkamos jų reikšmės k:

x – 1, s=1, k=6;

x 3 +x 2 +1, s=3, k=4;

x 3 +x+1, s=3, k=4;

(x–1)(x 3 +x 2 +1)=x 4 +x 2 +x+1, s=4, k=3;

(x–1)(x 3 +x+1)=x 4 +x 3 +x 2 +1, s=4, k=3;

(x 3 +x 2 +1)(x 3 +x+1)=x 6 +x 5 +x 4 +x 3 +x 2 +x, s=6, k=1.

Kodas (7, 6) turi tik vieną tikrinimo simbolį, o (7, 1) – tik vieną informacinį simbolį. Jie yra atitinkamai pariteto tikrinimo kodas ir pasikartojimo kodas.

Kaip ir įprastą linijinį kodą, ciklinį kodą galima nurodyti generatoriaus matrica. Todėl užduotis yra rasti tokią matricą, tai yra rasti k jį sudarančios linijiškai nepriklausomos kodų kombinacijos. Šiuo tikslu naudojame ciklinio kodo savybę, kuri yra uždaryta ciklinio poslinkio operacijos atžvilgiu. Atkreipkite dėmesį, kad ciklinis poslinkis į dešinę viena vieta prilygsta daugianario padauginimui g(x) įjungta x. Tada generuojamoji matrica gali būti sudaryta imant generuojantį daugianarį ir k jo cikliniai poslinkiai:

Dabar panagrinėkime, kaip naudoti generuojamąjį daugianarį g(x) = 1+x+x 3, kodavimas atliekamas (7, 4) kodu. Paimkite, pavyzdžiui, 4 bitų žodį (0101), kuris atitinka daugianarį f(x) = x + x 3. Padauginus šiuos du daugianario.

Atitinka šį žodį, iš formalaus kintamojo x. Akivaizdu, kad šis atitikimas yra ne tik vienas su vienu, bet ir izomorfinis. Kadangi „žodžiai“ susideda iš lauko raidžių, juos galima sudėti ir padauginti (elementas po elemento), o rezultatas bus tame pačiame lauke. Polinomas, atitinkantis tiesinį žodžių poros derinį ir lygus šių žodžių polinomų tiesiniam deriniui

Tai leidžia n ilgio žodžių aibę baigtiniame lauke laikyti tiesine erdve polinomų, kurių laipsnis virš lauko ne didesnis kaip n-1

Algebrinis aprašymas

Jei kodinis žodis, gautas cikliškai perkeliant vieną bitą į dešinę nuo žodžio , tada jį atitinkantis polinomas c 1 (x) gaunamas iš ankstesnio, padauginus iš x:

Pasinaudojus tuo,

Perjunkite atitinkamai į dešinę ir į kairę j eilės:

Jeigu m(x) – savavališkas daugianomas per lauką GF(q) Ir c(x) – ciklinio kodo žodis ( n,k) kodą, tada m(x)c(x)mod(x n − 1) taip pat šio kodo kodinis žodis.

Dauginamo generavimas

Apibrėžimas Ciklinio ( n,k) kodas C toks nenulinis daugianomas vadinamas iš C, kurio laipsnis yra mažiausias ir didžiausio laipsnio koeficientas g r = 1 .

1 teorema

Jeigu C- ciklinis ( n,k) kodas ir g(x) yra jo generuojantis daugianario, tada laipsnis g(x) yra lygus r = n − k ir kiekvienas kodo žodis formoje gali būti pavaizduotas vienareikšmiškai

c(x) = m(x)g(x) ,

kur laipsnis m(x) mažesnis arba lygus k − 1 .

2 teorema

g(x) - generuojantis ciklinio ( n,k) kodas yra dvejetainio daliklis x n − 1

Pasekmės: taigi bet kurį daugianarį, daliklį, galima pasirinkti generuojančiu polinomu x n– 1. Testo simbolių skaičių lems pasirinkto daugianario laipsnis r, informacijos simbolių skaičius k = n − r .

Generatoriaus matrica

Polinomai yra tiesiškai nepriklausomi, kitaip m(x)g(x) = 0 ne nuliui m(x), kas neįmanoma.

Tai reiškia, kad kodinius žodžius, kaip ir tiesinius kodus, galima parašyti taip:

, Kur G yra generuojanti matrica, m(x) - informaciniai daugianario.

Matrica G gali būti parašytas simboline forma:

Patikrinkite matricą

Kiekvienam ciklinio kodo kodiniam žodžiui . Štai kodėl patikrinimo matrica gali būti parašytas taip:

Kodavimas

Nesistemingas

Taikant nesisteminį kodavimą, kodo žodis gaunamas informacinio polinomo sandaugos forma generuojančiu polinomu

c(x) = m(x)g(x) .

Jį galima įgyvendinti naudojant polinominius daugiklius.

Sistemingas

Sistemingai koduojant kodo žodis formuojamas informacijos subbloko ir patikros forma

Tegul informacinis žodis sudaro aukštesnes kodinio žodžio galias

c(x) = x r m(x) + s(x),r = n − k

Tada iš tos sąlygos išplaukia

Ši lygtis nustato sisteminio kodavimo taisyklę. Jį galima įdiegti naudojant kelių ciklų linijinius filtrus (MLF)

Pavyzdžiai

Dvejetainis (7,4,3) kodas

Kaip skirstytuvas x 7 − 1 pasirenkame trečiojo laipsnio generuojantį daugianarį g(x) = x 3 + x + 1 , tada gautas kodas bus tokio ilgio n= 7, bandymo simbolių skaičius (generavimo polinomo laipsnis) r= 3, informacijos simbolių skaičius k= 4, mažiausias atstumas d = 3 .

Generatoriaus matrica kodas:

,

kur pirmoji eilutė yra daugianario žymėjimas g(x) koeficientai didėjančia tvarka. Likusios eilutės yra pirmosios eilutės cikliniai poslinkiai.

Patikrinkite matricą:

,

kur i-tas stulpelis, prasidedantis nuo 0, reiškia likusią padalijimo dalį x iį daugianarį g(x) parašytas didėjančia tvarka, pradedant nuo viršaus.

Taigi, pavyzdžiui, gaunamas 3 stulpelis arba vektorinis žymėjimas.

Tai lengva patikrinti GH T = 0 .

Dvejetainis (15,7,5) BCH kodas

Kaip generuojantis daugianomas g(x) galite pasirinkti dviejų daliklių sandaugą x 15 − 1 ^

g(x) = g 1 (x)g 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Tada kiekvieną kodinį žodį galima gauti naudojant informacinio polinomo sandaugą m(x) su laipsniu k– 1 taigi:

c(x) = m(x)g(x) .

Pavyzdžiui, informacinis žodis atitinka daugianarį m(x) = x 6 + x 5 + x 4 + 1 , tada kodinis žodis c(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 , arba vektorine forma

taip pat žr

Nuorodos

Wikimedia fondas. 2010 m.

• Ciklinės formos muzikoje
• Ciklinės ribinės sąlygos

Pažiūrėkite, kas yra „cikliniai kodai“ kituose žodynuose:

sutrumpinti cikliniai kodai- - [L.G. Sumenko. Anglų-rusų informacinių technologijų žodynas. M.: Valstybės įmonė TsNIIS, 2003.] Temos Informacinės technologijos apskritai EN sutrumpinti cikliniai kodai...

Reed-Saliamon kodai- ne dvejetainiai cikliniai kodai, leidžiantys ištaisyti klaidas duomenų blokuose. Kodo vektoriaus elementai yra ne bitai, o bitų (blokų) grupės. Reed Solomon kodai, veikiantys su baitais (oktetais), yra labai dažni. Reedo Solomono kodas yra... Vikipedija

Golay kodai- Puikių linijinių blokų kodų šeima su klaidų taisymu. Naudingiausias yra Golay dvejetainis kodas. Taip pat žinomas trijų dalių Golay kodas. Golay kodai gali būti laikomi cikliniais kodais. …… Techninis vertėjo vadovas

Klaidos taisant kodus

Klaidų taisymo kodai- Ryšių technologijų klaidų aptikimas, veiksmas, skirtas stebėti duomenų vientisumą įrašant/atkuriant informaciją arba perduodant ją ryšio linijomis. Klaidų taisymo (klaidų taisymo) procedūra atkuriant informaciją po... ... Vikipedija

Klaidos taisant kodus- Ryšių technologijų klaidų aptikimas, veiksmas, skirtas stebėti duomenų vientisumą įrašant/atkuriant informaciją arba perduodant ją ryšio linijomis. Klaidų taisymo (klaidų taisymo) procedūra atkuriant informaciją po... ... Vikipedija

BALTARUSIJOS VALSTYBINIS INFORMATIKOS IR RADIJOELEKTRONIKOS UNIVERSITETAS

AEI departamentas

santrauka šia tema:

„Cikliniai kodai. BCH kodai"

MINSKAS, 2009 m

Cikliniai kodai

Ciklinis kodas – tai tiesinis blokinis (n,k) kodas, kuriam būdinga cikliškumo savybė, t.y. bet kurio leistino kodo žodžio poslinkis į kairę vienu žingsniu taip pat suteikia leistiną kodinį žodį, priklausantį tam pačiam kodui ir kurio kodinių žodžių rinkinys vaizduojamas (n-1) ar mažesnio laipsnio polinomų rinkiniu, dalijamu iš kokio nors daugianario g( x) laipsnio r = n-k , kuris yra dvinario x n +1 koeficientas.

Polinomas g(x) vadinamas generuojančiu.

Kaip matyti iš apibrėžimo, cikliniame kode kodiniai žodžiai pateikiami kaip daugianariai

kur n yra kodo ilgis; - koeficientai iš lauko GF(q).

Jei kodas pastatytas per lauką GF(2), tada koeficientai įgyja reikšmes 0 arba 1 ir kodas vadinamas dvejetainiu.
Pavyzdys. Jei ciklinio kodo kodinis žodis

tada atitinkamas daugianario

Pavyzdžiui, jei kodas yra sukurtas per lauką GF(q)=GF(2 3), kuris yra GF(2) modulo plėtinys, neredukuojamas polinomas f(z)=z 3 +z+1 ir elementai šio lauko formos, pateiktos 1 lentelėje,

tada koeficientai

paimkite šio lauko elementų reikšmes, todėl jie patys rodomi šios formos daugianarių pavidalu
čia m yra daugianario, kuriuo buvo gautas lauko plėtinys GF(2), laipsnis; a i - koeficientai, imant GF(2) elementų reikšmę, t.y. 0 ir 1. Toks kodas vadinamas q-tuoju.

Ciklinio kodo ilgis vadinamas primityviuoju, o pats kodas – primityviuoju, jei jo ilgis n=q m -1 ties GF(q).

Jei kodo ilgis yra mažesnis už primityvaus kodo ilgį, tada kodas vadinamas sutrumpintu arba neprimityviu.

Kaip matyti iš apibrėžimo, bendra ciklinio kodo kodinių žodžių savybė yra jų dalijimasis be liekanos iš tam tikro daugianario g(x), vadinamo generatoriumi.

Binomo x n +1 padalijimo iš daugianario g(x) rezultatas yra bandomasis polinomas h(x).

Dekoduojant ciklinius kodus, naudojamas klaidų polinomas e(x) ir sindromo polinomas S(x).

Iš išraiškos nustatomas paklaidos polinomas, kurio laipsnis ne didesnis kaip (n-1).

kur yra polinomai, atitinkamai nurodantys gautus (su klaida) ir perduotus kodinius žodžius.

Nenuliniai koeficientai e(x) užima pozicijas, atitinkančias klaidas.

Pavyzdys.

Sindrominis polinomas, naudojamas dekoduojant ciklinį kodą, apibrėžiamas kaip gauto kodinio žodžio dalijimosi iš generuojančio polinomo liekana, t.y.

arba

Vadinasi, sindromo polinomas tiesiogiai priklauso nuo klaidos polinomo e(x) Ši nuostata naudojama sudarant dekodavimo procese naudojamų sindromų lentelę. Šioje lentelėje yra klaidų polinomų sąrašas ir atitinkamų sindromų, nustatytų pagal išraišką, sąrašas

(žr. 2 lentelę).

Dekodavimo metu sindromas apskaičiuojamas iš gauto kodinio žodžio, tada lentelėje randamas atitinkamas daugianomas e(x), kurį susumavus su gautu kodiniu žodžiu gaunamas pataisytas kodinis žodis, t.y.

Išvardintus daugianarius galima sudėti, dauginti ir dalyti naudojant žinomas algebros taisykles, tačiau rezultatui duodant mod 2, o tada mod x n +1, jei rezultato laipsnis viršija laipsnį (n-1).

Tarkime, kad kodo ilgis yra n=7, tada pateikiame rezultatą mod x 7 +1.

Konstruojant ir dekoduojant ciklinius kodus dėl skaidymo polinomų, dažniausiai reikia turėti ne koeficientą, o dalybos likutį.
Todėl rekomenduojamas paprastesnis padalijimo būdas, naudojant ne daugianarius, o tik jo koeficientus (pavyzdyje 2 variantas).

Pavyzdys.

Matricos kodo priskyrimas

Ciklinį kodą galima nurodyti generatoriumi ir patikrinimo matrica. Norint juos sukonstruoti, pakanka žinoti generuojančius g(x) ir testuojančius polinomus h(x). Nesisteminiam cikliniam kodui matricos sudaromos cikliškai perkeliant generuojamuosius ir tikrinamuosius polinomus, t.y. padauginus juos iš x

Ir

Konstruojant matricą H (n,k), polinomo h(x) pirmaujantis koeficientas yra dešinėje.

Pavyzdys. Cikliniam (7.4) kodui su generuojančiu polinomu g(x)=x 3 +x+1, matricos G (n,k) ir H (n,k) turi tokią formą:

Kur

Sisteminiam cikliniam kodui matrica G (n,k) nustatoma pagal išraišką

kur I k yra tapatumo matrica; R k,r yra stačiakampė matrica. Matricos R k,r eilutės nustatomos iš išraiškų arba kur a i (x) yra matricos I k i-osios eilutės reikšmė; i yra matricos R k,r eilutės numeris.

Pavyzdys. Matrica G (n,k) (7.4) kodui, pagrįsta generuojančiu polinomu g(x)=x 3 +x+1, sudaroma tokia seka

arba

R 4.3 nustatomas naudojant

nes

Nustatoma panašiai