Ciklični kodovi su tako nazvani jer se u njima neke ili sve kombinacije kodova mogu dobiti cikličkim pomicanjem jedne ili više kombinacija kodova. Ciklični pomak se vrši s desna na lijevo, pri čemu se svaki put krajnji lijevi simbol pomiče na kraj kombinacije. Gotovo svi ciklični kodovi pripadaju sistematskim kodovima, u njima se kontrolni i informacioni bitovi nalaze na strogo određenim mjestima. Pored toga, kodovi su klasifikovani kao blok kodovi. Svaki blok (jedno slovo je poseban slučaj bloka) je kodiran nezavisno.

Ideja konstruisanja cikličkih kodova zasniva se na upotrebi polinoma koji su nesvodivi u polju binarnih brojeva. Nesvodivo nazivaju se polinomi koji se ne mogu predstaviti kao proizvod polinoma nižih stupnjeva sa koeficijentima iz istog polja, kao što se prosti brojevi ne mogu predstaviti kao proizvod drugih brojeva. Drugim riječima, nesvodljivi polinomi su djeljivi bez ostatka samo sa sobom ili jednim.

Nesvodljivi polinomi u teoriji cikličkih kodova igraju ulogu generiranja polinoma. Ako se data kombinacija kodova pomnoži sa odabranim nesvodljivim polinomom, dobijamo ciklički kod čije su mogućnosti korekcije određene nesvodljivim polinomom.

Pretpostavimo da trebate kodirati jednu od četverocifrenih kombinacija binarnog koda. Pretpostavimo i da je ova kombinacija G(x) = x 3 + x 2 + 1 ® 1011. Ne opravdavajući naš izbor, uzimamo iz tabele nesvodljivih polinoma kao generirajući polinom P(x) = x 3 + x + 1 ® 1011. Zatim pomnožite G(x) monomom istog stepena kao i generirajući polinom. Od množenja polinoma monomom stepena n stepen svakog člana polinoma će se povećati za n, što je ekvivalentno dodeljivanju n nule na strani nižeg reda polinoma. Pošto je stepen izabranog nesvodivog polinoma tri, originalna kombinacija informacija se množi monomom od tri stepena

G(x) x n =(x 3 + x 2 + 1) x 3 =x 6 + x 5 + x 3 = 1101000.

Ovo se radi kako bi se kasnije ispravne cifre mogle upisati na mjesto ovih nula.

Vrijednost korektivnih cifara nalazi se iz rezultata dijeljenja G(x)xn on P(x):

x 6 +x 5 +0+x 3 +0+0+0 ½x 3 +x+1

x 6 +0+x 4 +x 3

x 5 +x 4 +0+0 x 3 +x 2 +x+1+ x 5 +0+x 3 +x 2

x 4 + x 3 +x 2 +0

x 4 + 0 +x 2 +x

x 3 +0+x+0

x 3 +0+x+1

dakle,

ili uopšte

Gdje Q(x)¾ količnik, i R(x)¾ ostatak dijeljenja G(x)×xn on P(x).

Budući da je u binarnoj aritmetici 1 Å 1 = 0, a samim tim -1 = 1, pri sabiranju binarnih brojeva moguće je prenijeti članove iz jednog dijela u drugi bez promjene predznaka (ako je prikladno), stoga je jednakost oblika a Å b = 0 se takođe može napisati kao a = b, i kako a - b = 0. Sve tri jednakosti u ovom slučaju znače i to a I b jednaki su 0, ili a I b jednaki su 1, tj. imaju isti paritet.

Dakle, izraz (5.1) se može zapisati kao

F(x)=Q(x) P(x)= G(x) x n +R(x),

što će u slučaju našeg primjera dati

F(x)=(x 3 + x 2 + x + 1) (x 3 + x + 1)= (x 3 + x 2 + 1)x 3 + 1,

F(x)= 1111 1011 = 1101000 + 001 = 1101001.

Polinom 1101001 je željena kombinacija, gdje je 1101 informacijski dio, a 001 kontrolni znakovi. Imajte na umu da bismo željenu kombinaciju dobili i kao rezultat množenja jedne od kombinacija kompletnog četverocifrenog binarnog koda (u ovom slučaju 1111) generirajućim polinomom, i množenjem date kombinacije monomom istog stepena kao izabrani generirajući polinom (u našem slučaju je kombinacija 1101000 dobivena na ovaj način, nakon čega je rezultatskom proizvodu dodat ostatak od dijeljenja ovog proizvoda generirajućim polinomom (u našem primjeru ostatak ima oblik 001).

I ovdje svojstva generirajućeg polinoma igraju odlučujuću ulogu P(x). Tehnika konstruisanja cikličkog koda je takva da generatorski polinom učestvuje u formiranju svake kombinacije koda, pa se svaki polinom cikličkog koda deli na generator bez ostatka. Ali samo oni polinomi koji pripadaju datom kodu se dijele bez ostatka, tj. generirajući polinom vam omogućava da odaberete dozvoljene kombinacije od svih mogućih. Ako se pri dijeljenju cikličkog koda generirajućim polinomom dobije ostatak, onda je ili došlo do greške u kodu, ili je u pitanju kombinacija nekog drugog koda (zabranjena kombinacija). Ostatak otkriva prisustvo zabranjene kombinacije, odnosno otkrivena je greška. Ostaci od podjele polinoma su detektori grešaka cikličkih kodova.

S druge strane, ostaci od dijeljenja jedinice sa nulama generirajućim polinomom koriste se za konstruiranje cikličkih kodova.

Prilikom dijeljenja jedinice s nulama generirajućim polinomom, treba imati na umu da dužina ostatka ne smije biti manja od broja kontrolnih znamenki, stoga, ako u ostatku nema dovoljno znamenki, dodaje se potreban broj nula desno od ostatka.

01100 11111+

počevši od osmog, ostali će se ponavljati.

Ostaci podjela koriste se za konstruiranje generirajućih matrica, koje se zbog svoje jasnoće i lakoće dobivanja kombinacija izvedenica široko koriste za konstruiranje cikličkih kodova. Konstrukcija generirajuće matrice svodi se na kompilaciju jedinične transponirane i komplementarne matrice, čiji su elementi ostaci od dijeljenja jedinice sa nulama generirajućim polinomom P(x). Podsjetimo da je jedinična transponirana matrica kvadratna matrica, čiji su svi elementi nuli, osim elemenata koji se nalaze dijagonalno s desna na lijevo od vrha do dna (u netransponiranoj matrici, dijagonala s jediničnim elementima nalazi se od lijevo na desno od vrha do dna). Elementi komplementarne matrice se dodeljuju desno od transponovane matrice identiteta. Samo oni ostaci čija je težina W ³ d 0- 1, gde d 0- minimalna udaljenost koda. Dužina ostataka ne smije biti manja od broja kontrolnih bitova, a broj ostataka mora biti jednak broju bitova informacija.

Redovi generirajuće matrice predstavljaju prve kombinacije izvorni kod. Preostale kombinacije kodova se dobijaju zbrajanjem po modulu 2 svih mogućih kombinacija redova generišuće ​​matrice.

Primjer.

Konstruirajte kompletnu generirajuću matricu cikličkog koda koja detektuje sve pojedinačne i dvostruke greške prilikom prijenosa 10-bitnih binarnih kombinacija.

Rješenje.

Prema tabeli 5.12, izaberite najbližu vrednost k ³ 10.

Tabela 5.12 – Odnosi između informacija i znakova za provjeru za kodove duge do 16 bita

n	k	ρ	n	k	ρ

Prema tabeli, ova vrijednost će biti k = 11, dok r = 4, A

n= 15. Također biramo generirajući polinom x 4 + x 3 +1.

Konstruiramo kompletnu generirajuću matricu iz jedinične transponirane matrice u kanonskom obliku i dodatne matrice koja odgovara kontrolnim bitovima.

Transponovana matrica za k = 11 izgleda ovako:

Dodatna matrica se može konstruisati od ostataka dijeljenja kombinacije u obliku jedan sa nulama (posljednji red jedinične transponirane matrice) odabranim generirajućim polinomom.

Kompletna generirajuća matrica će izgledati ovako:

Gore opisana metoda za konstruiranje generirajućih matrica nije jedina. Generirajuća matrica se može konstruirati direktnim množenjem elemenata matrice identiteta generirajućim polinomom. Ovo je često zgodnije od pronalaženja ostataka od dijeljenja. Rezultirajući kodovi se ne razlikuju od kodova konstruiranih korištenjem generirajućih matrica, u kojima se dodatna matrica sastoji od ostataka od dijeljenja jedinice sa nulama generirajućim polinomom.

Generirajuća matrica se također može konstruirati cikličkim pomicanjem kombinacije dobivene množenjem reda matrice identiteta ranga k na generirajući polinom.

Greške u cikličkim kodovima se otkrivaju korištenjem ostataka od dijeljenja rezultujuće kombinacije generirajućim polinomom. Ostaci podjela su identifikatori greške, ali ne ukazuju direktno na lokaciju greške u cikličkom kodu.

Ideja ispravljanja greške temelji se na činjenici da se pogrešna kombinacija nakon određenog broja cikličkih pomaka „prilagođava“ ostatku na način da zajedno s ostatkom daje ispravljenu kombinaciju koda. Ostatak u ovom slučaju nije ništa drugo do razlika između iskrivljenih i ispravnih simbola, jedinice u ostatku stoje tačno na mjestima iskrivljenih cifara u kombinaciji podešenoj cikličkim pomacima. Iskrivljena kombinacija se prilagođava sve dok broj jedinica u ostatku ne bude jednak broju grešaka u kodu. U ovom slučaju, prirodno, broj jedinica može biti ili jednak broju grešaka s, ispravljeno ovim kodom (kod ispravlja 3 greške i 3 greške u iskrivljenoj kombinaciji), ili manje s(kod ispravlja 3 greške, au prihvaćenoj kombinaciji postoji 1 greška).

Lokacija greške u kombinaciji kodova nije bitna. Ako k³(n/2), tada će nakon određenog broja pomaka sve greške biti u zoni „jednokratnog“ djelovanja generirajućeg polinoma, odnosno dovoljno je dobiti jedan ostatak čija težina W £ s, a to će već biti dovoljno za ispravljanje iskrivljene kombinacije.

Proces ispravljanja grešaka je detaljno razmotren u nastavku koristeći primjere izrade specifičnih kodova.

Najjednostavniji ciklički kod vam omogućava da otkrijete pojedinačne greške i greške neparne višestrukosti. Generirajući polinom ovog koda ima oblik. Među nesvodljivim polinomima uključenim u ekspanziju, ovaj polinom je polinom najmanjeg stepena. Dakle, za bilo koji broj bitova informacija potreban je samo jedan bit za provjeru. Vrijednost simbola ovog bita osigurava jednakost broja jedinica u bilo kojoj dozvoljenoj kombinaciji koda. Rezultirajući ciklički paritetni kod je sposoban da detektuje ne samo pojedinačne greške u pojedinačnim bitovima, već i greške u bilo kom neparnom broju bitova.

Primjer. Konstruirajte ciklički kod za Budući da je generirajući polinom polinom 1. stepena, broj kontrolnih cifara Shodno tome, Da bismo konstruirali ciklički kod, konstruiramo generirajuću matricu

Da bismo konstruirali dodatnu matricu, nalazimo ostatke od dijeljenja posljednjeg reda jedinične transponirane matrice, ispunjene nulama, odabranim polinomom:

Dakle, dodatna matrica C,k ima oblik

Sada gradimo generirajuću matricu

Redovi ove matrice su prve tri kombinacije kodova. Ostale dozvoljene kombinacije mogu se dobiti zbrajanjem po modulu dvije sve moguće kombinacije redova matrice. Rezultirajuće uništene kombinacije kodova date su u tabeli. 39.

Tabela 39 (vidi skeniranje)

Od dobro poznatog interesa je razmatranje sljedećeg najjednostavnijeg koda formiranog korištenjem nereducibilnog polinoma drugog stepena

Opšti pogled Generirajuća matrica cikličkog koda formiranog polinomom razlikuje se po strukturi dodatne matrice koja ima dva stupca.

Lako je provjeriti da kada se dijele datim generirajućim polinomom monomi koji izražavaju nizove

matrica identiteta (da bi se pronašla dodatna matrica, formiraju se tri tipa ostataka: 11, 01 i 10. Posljedično, težina svake kombinacije rezultirajućeg -koda bit će najmanje dva. Minimalna kodna udaljenost između bilo koje dvije kombinacije je također Ali najjednostavniji kod je takođe karakteriziran sa jednom provjerom parnosti koju čini binom prvog stepena moguće je detektovati ne samo greške neparne višestrukosti, već i sve uparene susedne greške, kao i sve greške razdvojene jednim neoštećenim elementom.

Klasa linearnih kodova tzv šaički kodovi. Naziv dolazi od glavnog svojstva ovih kodova: ako određena kombinacija koda pripada cikličkom kodu, onda kombinacija dobivena cikličkom permutacijom originalne kombinacije (ciklički pomak) također pripada ovom kodu:

Drugo svojstvo svih dozvoljenih kombinacija cikličkih kodova je njihova djeljivost bez ostatka nekim odabranim polinomom, koji se naziva generirajućim.

Ova svojstva se koriste u izradi kodova za uređaje za kodiranje i dekodiranje, kao i u otkrivanju i ispravljanju grešaka.

Ciklični kodovi su čitava porodica kodova otpornih na greške (od kojih su jedna od varijanti Hammingovi kodovi), koji pružaju veću fleksibilnost u smislu mogućnosti implementacije kodova uz neophodnu sposobnost otkrivanja i ispravljanja grešaka koje nastaju pri prenošenju kombinacija kodova preko komunikacijski kanal. Ciklični kod se odnosi na sistematske blok (l, &) kodove u kojima To prve cifre predstavljaju kombinaciju primarnog koda, a sljedeće (l - do) cifre su provjera.

Konstrukcija cikličkih kodova zasniva se na operaciji dijeljenja prenesene kombinacije kodova sa generiranjem nesvodljivog polinoma stepena G. Ostatak podjele se koristi za formiranje kontrolnih znamenki. U ovom slučaju, operaciji dijeljenja prethodi operacija množenja, koja pomiče ^-bitnu informacijsku kombinaciju koda ulijevo za G pražnjenja.

Prilikom dekodiranja primljene n-bitne kodne kombinacije, dijeljenje se ponovo vrši generirajućim (generirajućim, formirajućim) polinomom.

Sindrom greške u ovim kodovima je prisustvo ostatka kada se primljena kombinacija kodova podijeli sa generirajućim polinomom. Ako je sindrom nula, onda se smatra da nema grešaka. U suprotnom, koristeći rezultirajući sindrom, možete odrediti broj cifara primljene kombinacije kodova u kojoj je došlo do greške i ispraviti je.

Međutim, ne može se isključiti mogućnost pojavljivanja više grešaka u kombinacijama kodova, što može dovesti do lažnih ispravaka i (ili) neotkrivanja grešaka pri transformaciji jedne dozvoljene kombinacije u drugu.

Neka je ukupan broj bitova u bloku jednak i, od čega korisne informacije nose u sebi T bitova, tada je u slučaju greške moguće ispraviti j bitova. Zavisnost 5 od n I T za šifre se mogu odrediti iz tabele. 2.6.

Tabela 2.6

Ovisnost ukupnog broja bitova kombinacija o broju informacija i ispravljenih bitova

Povećanje razlike (p - t), ne možete samo povećati broj ispravljenih bitova s, ali i za otkrivanje višestrukih grešaka. Procenti otkrivenih višestrukih grešaka dati su u tabeli. 2.7.

Tabela 2.7

Procenti otkrivenih višestrukih grešaka

Pogodno je opisati ciklične kodove i konstruirati ih pomoću polinoma (ili polinoma). Pisanje kombinacije u obliku polinoma koristi se da se na formaliziran način prikaže operacija cikličkog pomaka originalne kodne kombinacije. Dakle, kombinacija koda "-elementa" može se opisati polinomom (str- 1) stepeni:

Gdjea„_j =(0, 1), ia„_, =0 odgovara nultim elementima kombinacije, d„_, = 1 - ne-nula;i- broj cifara kombinacije kodova.

Zamislimo polinome za specifične kombinacije od 4 elementa:

Operacije sabiranja i oduzimanja su ekvivalentne i asocijativne i izvode se po modulu 2:

Primjeri izvođenja operacija:

Operacija dijeljenja je uobičajeno dijeljenje polinoma, ali umjesto oduzimanja koristi se sabiranje po modulu 2:

Ciklično pomeranje kodne kombinacije - pomeranje njenih elemenata s desna na levo bez narušavanja njihovog redosleda, tako da krajnji levi element zauzima mesto krajnjeg desnog.

Glavna svojstva i naziv cikličkih kodova odnose se na činjenicu da se sve dozvoljene kombinacije bitova u poslanoj poruci (kodnih riječi) mogu dobiti cikličkim pomicanjem neke izvorne kodne riječi.

Recimo da su originalna kombinacija koda i odgovarajući polinom dati:

Hajde da se množimo Oh) on X:

Od maksimalnog stepena X u kodnoj kombinaciji dužine n ne prelazi (l - 1), tada je od desne strane rezultujućeg izraza za dobijanje originalnog polinoma potrebno oduzeti Oh"- 1). Oduzimanje Oh"- 1) naziva se uzimanje ostatka po modulu (x n - 1).

Pomak originalne kombinacije za / mjere može se predstaviti na sljedeći način: a(x) ? U - Oh"- 1), tj. množenje Oh) x" i uzimajući ostatak po modulu (x" - 1). Uzimanje ostatka je neophodno kada se dobije polinom stepena većeg ili jednakog str.

Ideja izgradnje cikličkih kodova zasniva se na upotrebi nesvodljivi polinomi. Nesvodljivi polinom je polinom koji se ne može predstaviti kao proizvod polinoma nižih stupnjeva, tj. je djeljiv samo sam sa sobom ili jednim, a ne bilo kojim drugim polinomom. Binom (x" + 1) je djeljiv takvim polinomom bez ostatka. Nesvodljivi polinomi u teoriji cikličkih kodova imaju ulogu generiranja polinoma.

Vraćajući se na definiciju cikličkog koda i uzimajući u obzir snimanje operacija cikličkog pomaka kombinacija kodova, možemo napisati matricu generiranja cikličkog koda u sljedećem obliku:

GdjeP(x)- originalnu kombinaciju koda na osnovu koje su izvedeni svi ostali(T- 1) osnovne kombinacije;

C, = 0 iliCj =1 („O“ ako je rezultujući stepen polinomaR(x)-x‘ne prelazi (l - 1), ili “1” - ako prelazi).

Kombinacija P(x) naziva se generirajuća (generatorska) kombinacija. Za konstruiranje cikličkog koda dovoljno je pravilno odabrati P(x). Tada su sve ostale kombinacije kodova iste kao u kodu grupe.

Generirajući polinom mora zadovoljiti sljedeće zahtjeve:

• P(x) mora biti različit od nule;
• težina P(x) ne smije biti manji od minimalne udaljenosti koda: V(P(x)) > d mm ;
• P(x) mora imati maksimalan stepen k (k - broj redundantnih elemenata u kodu);
• P(x) mora biti djelitelj polinoma (x" - 1).

Ispunjenje posljednjeg uvjeta dovodi do činjenice da sve radne kombinacije kodova cikličkog koda stiču svojstvo da su djeljive sa P(x) bez traga. Uzimajući ovo u obzir, možemo dati još jednu definiciju cikličkog koda: ciklički kod je kod čije su sve radne kombinacije djeljive generirajućim polinomom bez ostatka.

Da biste odredili stepen generirajućeg polinoma, možete koristiti izraz r > log 2 (i + 1), gdje n- veličina odaslanog paketa u jednom trenutku, tj. dužina cikličkog koda koji se gradi.

Primjeri generiranja polinoma dati su u tabeli. 2.8.

Tabela 2.8

Primjeri generiranja polinoma

Algoritam za dobijanje dozvoljene ciklične kombinacije kodova iz jednostavne kombinacije kodova je sledeći.

Neka je dat polinom P(x) = a g _ ( x g + a g _ 2 x g ~ 1 + ... + 1, što određuje ispravnu sposobnost koda i broj bitova za provjeru za, kao i originalnu kombinaciju jednostavnog elementarnog koda i informacijskih bitova u obliku polinoma A t(x).

Potrebno je odrediti dozvoljenu cikličku kombinaciju kodova (i, Za).

• 1. Originalnu kombinaciju koda predstavljamo kao polinom A t(x). Pomnožite polinom originalne kombinacije koda sa x g: A t (x) x g. Stepen generirajućeg polinoma G jednak vrijednosti najznačajnijeg bita originalne kombinacije koda.
• 2. Provjerne bitove koji dopunjuju originalnu informacijsku kombinaciju na dozvoljenu definiramo kao ostatak dijeljenja proizvoda dobijenog u prethodnom paragrafu sa generirajućim

polinom:

Ostatak podjele označavamo kao R(x).

3. Konačno riješena ciklička kombinacija koda

kod će biti definiran kao = A t(x)? x r + R(x).

Da bi se utvrdile greške u primljenoj kombinaciji koda, dovoljno je podijeliti je generirajućim polinomom. Ako je prihvaćena kombinacija legalna, tada će ostatak podjele biti nula. Ostatak različit od nule označava da prihvaćena kombinacija sadrži greške. Na osnovu vrste ostatka (sindroma) u nekim slučajevima moguće je izvesti i zaključak o prirodi greške i njenoj lokaciji i ispraviti grešku.

Algoritam detekcije greške je sljedeći.

Neka kombinacije "-elemenata ( n = k + t).

• 1. Identifikujemo činjenicu da postoji greška. Dobijamo ostatak dijeljenja prihvaćene kombinacije A n -(x) na generirajući polinom P(x): A(X)
• --- = Rq(x). Dostupnost balansa R0(x) na (L 0 (x) f 0) označava P(x)

o grešci.

2. Podijelite rezultujući polinom #(x) = L„_,(X) 0 Rq (x) do generatora R g (x): W-1 = R(x), Gdje R(x)- trenutno stanje.

3. Uporedite LDx) i R(x). Ako su jednaki, onda je greška nastala u najznačajnijem bitu. Ako nije, onda povećajte stepen prihvaćenog polinoma za x i ponovo podijelite:

4. Uporedite rezultujući ostatak sa Rq(x). Ako su jednaki, onda je greška nastala u drugoj cifri. Ako nisu jednaki, onda pomnožite shchh) x 2 i ponavljamo ove operacije dok ne dobijemo

R(x) = pakao.

Greška će biti u cifri koja odgovara broju za koji je stepen povećan shchh), plus 1. Na primjer, u slučaju jednakosti R(x) i LDx)

Ovo je podklasa linearnih kodova koji imaju svojstvo dragulja da ciklička permutacija simbola u kodiranom bloku proizvodi drugi mogući kodirani blok istog koda. Ciklični kodovi se zasnivaju na primeni ideja iz algebarske Galoisove teorije polja1.

Mnogi od najvažnijih kodova komunikacionih sistema otpornih na buku su

posebno ciklički, zasnovan na aritmetici konačnih struktura

Galois polja. Polje je skup elemenata koji imaju konačno polje

Nazivi operacija su pod navodnicima jer nisu uvijek uobičajene aritmetičke operacije. Polje uvijek ima nulti element (0) ili nulu i pojedinačni element(1) ili jedan. Ako je broj q elementi polja su ograničeni, tada se polje poziva konačno polje, ili konačno Galoisovo polje, i označava se GF(q)y Gdje q- terenski red. Najmanje Galois polje je polje sa dva elementa GF( 2), koji se sastoji od samo dva elementa 1 i 0. Da bi

1 Evariste Galois (1811 - 1832) - francuski matematičar, postavio je temelje moderne algebre.

izvođenje operacija nad elementima GF( 2) nisu dovele do izlaska van granica ovog polja, izvode se po modulu 2 (uglavnom to je određeno redosledom polja za jednostavna Galois polja).

Ovo polje ima niz specifičnih matematičkih svojstava. Za elemente polja definirane su operacije sabiranja i množenja, a rezultati tih operacija moraju pripadati istom skupu.

Za operacije sabiranja i množenja, poštuju se uobičajena matematička pravila asocijativnosti - A + (b + c) = (a + b)+ c, komutativnost - a + b = b + a I A b = b A i distributivnost - A (b+ c) = A b + A With.

Za svaki element polja A mora postojati inverzni element sabiranju (-A) i ako A nije jednak nuli, inverzni element množenja (th').

Polje mora sadržavati jedinica aditiva - element 0 takav da A + 0 = A za bilo koji element polja A.

Polje mora sadržavati multiplikativna jedinica - element 1, tako da aL = a za bilo koji element polja A.

Na primjer, postoje polja realnih brojeva, racionalnih brojeva i kompleksnih brojeva. Ova polja sadrže beskonačan broj elemenata.

U stvari, svi skupovi formirani cikličkom permutacijom kodne riječi su također kodne riječi. Tako će, na primjer, cikličke permutacije kombinacije 1000101 također biti kombinacije kodova 0001011, 0010110, 0101100, itd. Ovo svojstvo omogućava uvelike pojednostavljenje uređaja za kodiranje i dekodiranje, posebno pri otkrivanju grešaka i ispravljanju jedne greške. Pažnja na cikličke kodove je zbog činjenice da se njihova inherentna visoka korektivna svojstva implementiraju na osnovu relativno jednostavnih algebarske metode. Istovremeno, za dekodiranje proizvoljnog linearnog blok koda češće se koriste tablične metode koje zahtijevaju veliku količinu memorije dekodera.

Ciklični kod je linearni blok kod. (n, k)- kod koji karakteriše svojstvo cikličnosti, tj. pomicanje ulijevo za jedan korak bilo koje dozvoljene kodne riječi također daje dozvoljenu kodnu riječ koja pripada istom kodu, a za koju je skup kodnih riječi predstavljen skupom polinoma stepena (str- 1) ili manje, djeljivo sa generirajućim polinomom g(x) stepeni r=n-k yšto je faktor binoma X n+

U cikličnom kodu, kodne riječi su predstavljene polinomima (polinomima)

Gdje p - dužina koda; A i - koeficijenti polja Galois (vrijednosti kombinacije kodova).

Na primjer, za kombinaciju koda 101101 unos polinoma ima oblik

Primjeri cikličkih kodova su kodovi za parnu provjeru, kodovi ponavljanja, Hamingovi kodovi, PC kodovi i turbo kodovi.

Hamingov kod. Sposobnost ispravljanja grešaka u Hamingovom kodu povezana je s minimalnom udaljenosti koda d0. Sve greške višestrukosti su ispravljene q= cnt (d 0- l)/2 (ovdje cnt znači “cijeli dio”) i detektovane su greške višestrukosti d 0 - 1. Dakle, prilikom provjere neparnog pariteta d Q = 2 i otkrivene su pojedinačne greške. U Hamingovom kodu d 0 = 3. Pored kategorija informacija, uvodi se L= log 2 Q viška kontrolnih bitova, gdje Q- broj bitova informacija. Parametar L zaokruženo na najbliži veći cijeli broj. L-bitni kontrolni kod je obrnuti rezultat pobitnog sabiranja (zbrajanja po modulu 2) brojeva onih bitova informacija čije su vrijednosti jednake jedan.

Primjer 7.7

Neka nam je glavni kod 100110, tj. Q = 6. Hajde da definišemo dodatni kod.

Rješenje

Nalazimo to L= 3 i kod komplementa je

gdje je P simbol operacije sabiranja po bitu, a nakon inverzije imamo 000. Sada će se dodatni kod prenijeti zajedno sa glavnim kodom. Na prijemniku se dodatni kod ponovo izračunava i upoređuje sa odaslanim. Kod za poređenje se snima, a ako se razlikuje od nule, tada je njegova vrijednost broj pogrešno primljenog bita glavnog koda. Dakle, ako se prihvati šifra 100010, izračunati dodatni kod je jednak inverziji 010Š10 = 100, tj. 011, što znači grešku u 3. znamenki.

Generalizacija Hamingovih kodova su ciklički BCH kodovi, koji omogućavaju ispravljanje višestrukih grešaka u usvojenoj kombinaciji kodova.

Reed-Solomon kodovi baziraju se na Galois poljima, ili konačnim nulama. Aritmetičke operacije sabiranje, oduzimanje, množenje, dijeljenje itd. nad elementima konačne nule dati rezultat koji je također element te nule. Reed-Solomon koder ili dekoder mora nužno izvršiti ove operacije. Sve operacije za implementaciju koda zahtijevaju specijalna oprema ili specijalizovani softver.

Turbo kodovi. Redundantni kodovi se mogu koristiti samostalno ili u obliku neke kombinacije više kodova, kada se skupovi simbola jednog redundantnog koda smatraju elementarnim informacijskim simbolima drugog redundantnog koda. Ovo udruženje je dobilo naziv kaskadno kod. Ogromna prednost spojenih kodova je u tome što njihova upotreba omogućava pojednostavljenje enkodera, a posebno dekodera u poređenju sa sličnim uređajima nekonkateniranih kodova iste dužine i redundancije. Kaskadno kodiranje dovelo je do stvaranja turbo kodova. Turbo kod naziva se paralelna signalna struktura koja se sastoji od dva ili više sistematski kodovi. Osnovni princip njihove konstrukcije je upotreba više paralelnih radnih komponentnih enkodera. Kao komponentne kodove, možete koristiti i blok i konvolucione kodove, Hamingove kodove, PC kod, BCH, itd. Upotreba perforacije (probijanja) omogućava vam da povećate relativnu brzinu turbo koda, prilagođavajući njegovu sposobnost korekcije statističke karakteristike komunikacioni kanal. Princip generisanja turbo koda je sledeći: ulazni signal X, koji se sastoji od TO bit, hranjen paralelno sa N interleavers. Svaki od potonjih je uređaj koji preuređuje elemente u blok TO bitovi u pseudo-slučajnom redoslijedu. Izlazni signal iz interleaver-a - simbola sa promijenjenim redoslijedom - šalje se odgovarajućim elementarnim enkoderima. Binarne sekvence x p i= 1,2,..., JV, na izlazu enkodera nalaze se kontrolni simboli, koji zajedno sa informacijskim bitovima čine jednu kodnu riječ. Upotreba interleaver-a omogućava da se spriječi pojava nizova koreliranih grešaka pri dekodiranju turbo kodova, što je važno kada se u obradi koristi tradicionalni rekurentni metod dekodiranja. Ovisno o izboru koda komponente, turbo kodovi se dijele na konvolucione turbo kodove i blok kodove proizvoda.

Odgovara ovoj riječi, iz formalne varijable x. Može se vidjeti da ova korespondencija nije samo jedan prema jedan, već je i izomorfna. Pošto se „riječi“ sastoje od slova iz polja, mogu se sabirati i množiti (element po element), a rezultat će biti u istom polju. Polinom koji odgovara linearnoj kombinaciji para riječi i jednak je linearnoj kombinaciji polinoma ovih riječi

Ovo nam omogućava da skup riječi dužine n nad konačnim poljem razmotrimo kao linearni prostor polinoma sa stepenom najviše n-1 nad poljem

Algebarski opis

Ako je kodna riječ dobivena cikličkim pomicanjem jednog bita udesno od riječi , tada njen odgovarajući polinom c 1 (x) se dobija iz prethodnog množenjem sa x:

Iskoristivši činjenicu da

Pomak desno i lijevo za j rangovi:

Ako m(x) - proizvoljan polinom nad poljem GF(q) I c(x) - kodna riječ cikličkog ( n,k) onda kod m(x)c(x)mod(x n − 1) također kodnu riječ za ovaj kod.

Generisanje polinoma

Definicija Generirajući polinom cikličkog ( n,k) kod C takav polinom različit od nule naziva se od C, čiji je stepen najmanji, a koeficijent najvišeg stepena g r = 1 .

Teorema 1

Ako C- ciklično ( n,k) kod i g(x) je njegov generirajući polinom, zatim stepen g(x) je jednako r = n − k i svaka kodna riječ može biti jedinstveno predstavljena u obliku

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

gdje je stepen m(x) manje ili jednako k − 1 .

Teorema 2

g(x) - generiranje polinoma cikličkog ( n,k) kod je djelitelj binoma x n − 1

Posljedice: tako, bilo koji polinom, djelitelj, može biti izabran kao generirajući polinom x n− 1 . Stepen izabranog polinoma će odrediti broj testnih simbola r, broj informacioni simboli k = n − r .

Generatorska matrica

Polinomi su, inače, linearno nezavisni m(x)g(x) = 0 za različitu od nule m(x) što je nemoguće.

To znači da se kodne riječi mogu pisati, kao i za linearne kodove, na sljedeći način:

, Gdje G je generirajuća matrica, m(x) - informativni polinom.

Matrix G može se napisati u simboličkom obliku:

Provjerite matricu

Za svaku kodnu riječ cikličkog koda, . Zato provjerite matricu može se napisati kao:

Kodiranje

Nesistematično

Kod nesistematskog kodiranja, kodna riječ se dobiva u obliku produkta informacijskog polinoma i polinoma koji generira

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

Može se implementirati korištenjem polinomskih množitelja.

Sistematično

Kod sistematskog kodiranja, kodna riječ se formira u obliku informacijskog podbloka i verifikacije

Neka informaciona reč formira veće snage kodne reči

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

Zatim iz uslova sledi

Ova jednačina postavlja pravilo za sistematsko kodiranje. Može se implementirati pomoću višeciklusnih linearnih filtera (MLF)

Primjeri

Binarni (7,4,3) kod

Kao razdjelnik x 7 − 1 biramo generirajući polinom trećeg stepena g(x) = x 3 + x + 1 , tada će rezultujući kod imati dužinu n= 7, broj testnih simbola (stepen generisanja polinoma) r= 3, broj simbola informacija k= 4, minimalna udaljenost d = 3 .

Generatorska matrica kod:

,

gdje je prvi red zapis polinoma g(x) koeficijenti u rastućem redoslijedu. Preostale linije su ciklički pomaci prvog reda.

Provjerite matricu:

,

gdje i-ti stupac, počevši od 0, predstavlja ostatak podjele x i na polinom g(x) napisano uzlaznim redoslijedom, počevši od vrha.

Tako se, na primjer, dobija 3. stupac, ili u vektorskoj notaciji.

Lako je to provjeriti GH T = 0 .

Binarni (15,7,5) BCH kod

Kao generirajući polinom g(x) možete odabrati proizvod dva djelitelja 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 se svaka kodna riječ može dobiti korištenjem proizvoda informacijskog polinoma m(x) sa diplomom k− 1 ovako:

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

Na primjer, informativna riječ odgovara polinomu m(x) = x 6 + x 5 + x 4 + 1 , zatim kodnu riječ 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 , ili u vektorskom obliku

Vidi također

Linkovi

Wikimedia Foundation.

• 2010.
• Ciklične forme u muzici

Pogledajte šta su "ciklički kodovi" u drugim rječnicima:

skraćeni ciklički kodovi- - [L.G. Englesko-ruski rječnik informacionih tehnologija. M.: Državno preduzeće TsNIIS, 2003.] Teme informacione tehnologije općenito EN skraćeni ciklički kodovi...

Reed-Solomon kodovi- nebinarni ciklički kodovi koji vam omogućavaju da ispravite greške u blokovima podataka. Elementi kodnog vektora nisu bitovi, već grupe bitova (blokova). Reed Solomon kodovi koji rade sa bajtovima (oktetima) su vrlo česti. Šifra Reeda Solomona je... Wikipedia

Golay kodovi- Porodica savršenih linearnih blok kodova sa ispravljanjem grešaka. Najkorisnije je binarni kod Golay. Poznat je i ternarni Golay kod. Golay kodovi se mogu smatrati cikličkim kodovima. … … Vodič za tehnički prevodilac

Kodovi za ispravljanje grešaka

Kodovi za ispravljanje grešaka- Otkrivanje grešaka u komunikacijskoj tehnologiji, radnja usmjerena na praćenje integriteta podataka pri snimanju/reproduciranju informacija ili pri njihovom prijenosu preko komunikacijskih linija. Ispravka greške (ispravka greške) procedura za vraćanje informacija nakon... ... Wikipedia

Kodovi za ispravljanje grešaka- Otkrivanje grešaka u komunikacijskoj tehnologiji, radnja usmjerena na praćenje integriteta podataka pri snimanju/reproduciranju informacija ili pri njihovom prijenosu preko komunikacijskih linija. Ispravka greške (ispravka greške) procedura za vraćanje informacija nakon... ... Wikipedia

Počni