Syklinen koodi

Sykliset koodit kuuluvat lohkosysteemisiin koodeihin, joissa kukin yhdistelmä on koodattu itsenäisesti (lohkon muodossa) siten, että informaatio k ja ohjaussymbolit ovat aina samat.

pukeutua tietyissä paikoissa. Kyky havaita ja korjata lähes kaikki virheet suhteellisen alhaisella redundanssilla verrattuna muihin koodeihin sekä koodaus- ja dekoodauslaitteiden piirien toteutuksen yksinkertaisuus teki näistä koodeista laajalle levinneitä. Syklisten koodien teoria perustuu ryhmäteoriaan ja polynomien algebraan Galois'n kentässä.

Syklinen koodi on koodi, jossa koodiyhdistelmien jakautumisjärjestys suoritetaan siten, että siirryttäessä mistä tahansa yhdistelmästä viereiseen Hamming-koodin etäisyys pysyy joka kerta vakiona.

Sykliset koodit ovat koko perhe virheenkestäviä koodeja, mukaan lukien Hamming-koodit yhtenä lajikkeistaan, mutta yleensä ne tarjoavat enemmän joustavuutta kykyyn toteuttaa koodeja, joilla on tarvittava kyky havaita ja korjata virheet, jotka syntyvät koodiyhdistelmiä lähetettäessä. viestintäkanavan kautta. Syklisillä koodilla tarkoitetaan systemaattisia lohkokoodeja (n, k), joissa ensimmäiset k numeroa edustavat ensisijaisen koodin yhdistelmää ja seuraavat (n ? k) numerot ovat tarkistusnumeroita.

Syklisten koodien rakentaminen perustuu operaatioon, jossa lähetetty koodiyhdistelmä jaetaan generoivalla r-asteen polynomilla. Jaon loppuosaa käytetään tarkistusnumeroiden muodostamiseen. Tässä tapauksessa jakooperaatiota edeltää kertolasku, joka siirtää k-bittistä informaatiokoodiyhdistelmää vasemmalle r bitillä.

Polynomia (polynomia), joka voidaan esittää alempien asteiden polynomien tulona, ​​kutsutaan pelkistäväksi (tietyssä kentässä), muuten redusoitumattomaksi. Pelkistymättömillä polynomeilla on samanlainen rooli kuin alkuluvuilla lukuteoriassa. Pelkistymättömät polynomit P(X) voidaan kirjoittaa desimaali- tai binäärilukuina tai algebrallisena polynomina.

Syklinen koodausprosessi

Syklinen koodaus perustuu pelkistymättömän polynomin P(X) käyttöön, jota syklisten koodien suhteen kutsutaan generaattoriksi, generaattoriksi tai generoivaksi polynomiksi (polynomi).

Kaikkien yhdistelmien binäärikoodien yhdistelmät otetaan informaatiosymboleiksi k syklisten koodien muodostamista varten. Yleisessä tapauksessa, jos annettu koodiyhdistelmä Q(x) kerrotaan generoivalla polynomilla P(x), tuloksena on syklinen koodi, jolla on tietyt korjaavat ominaisuudet riippuen valinnasta P(x). Kuitenkin tässä koodissa ohjaussymbolit m sijaitsevat useissa eri paikoissa koodiyhdistelmässä. Tällainen koodi ei ole systemaattista, mikä tekee sen piirin toteuttamisesta vaikeaa. Tilannetta voidaan yksinkertaistaa merkittävästi, jos ohjaussymbolit lisätään loppuun, eli informaatiosymbolien jälkeen. Tätä tarkoitusta varten on suositeltavaa käyttää seuraavaa menetelmää:

Kerrotaan koodiyhdistelmä G(x), joka täytyy koodata monomilla X m, jolla on sama aste kuin generoivalla polynomilla P(x);

Jaamme tulon G(x)Х m generoivalla polynomilla Р(х m):

missä Q(x) on jaon osamäärä; R(x) - jäännös.

Kerrotaan lauseke (2.1) P(x):llä ja siirretään R(x) yhtälön toiseen osaan etumerkkiä kääntämättä, saadaan:

Siten yhtälön (2.2) mukaan syklinen koodi, eli koodattu sanoma F(x), voidaan muodostaa kahdella tavalla:

Binaarikoodin yhden koodiyhdistelmän kertominen kaikilla yhdistelmillä generoivalla polynomilla P(x);

Kertomalla annettu koodiyhdistelmä G(x) yhdellä polynomilla X m, jolla on sama aste kuin generoivalla polynomilla P(x), lisäämällä jäännös R(x), joka saadaan, kun tulo G(x)X m on jaettu generoidulla polynomi P(X).

Viestin koodaus

On koodattava koodiyhdistelmä 1100, joka vastaa G(x)=x 3 +x 2 käyttäen P(x)=x 3 +x+1.

Kerromme G(x) X m:llä, jolla on kolmas potenssi, saamme:

Jakamalla tulo G(x)Х m generoivalla polynomilla Р(х m) kohdan (2.1) mukaisesti saadaan:

tai binäärivastineena:

Siten tuloksena saadaan osamäärä Q(x), joka on samaa luokkaa kuin G(x):

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

ja loput:

Tämän seurauksena syklisellä koodilla koodattu binäärikoodiyhdistelmä (2.2) mukaisesti saa muotoa:

F(x)=1110 1011=1100010

Koska jokainen sallittu syklinen koodiyhdistelmä edustaa generoivan polynomin G(x) kaikkia mahdollisia summia, niiden on oltava jaollisia P(x):llä ilman jäännöstä. Siksi hyväksytyn koodiyhdistelmän oikeellisuuden tarkistaminen tarkoittaa jäännöksen tunnistamista, kun se jaetaan generoivalla polynomilla.

Saldon vastaanottaminen osoittaa virheen olemassaolon. Loput syklisten koodien jaosta on oireyhtymän roolia.

Esimerkiksi lähetetty koodiyhdistelmä F(x)=1100010, joka on konstruoitu käyttämällä generoivaa polynomia P(x)=1011. Häiriön vaikutuksesta koodiyhdistelmä muutettiin yhdistelmäksi F"(x)=1000010

Jaamme hyväksytyn yhdistelmän generoivalla polynomilla

Jäännöksen R(x)=001 läsnäolo osoittaa virheen. Se ei kuitenkaan suoraan osoita virheen sijaintia yhdistelmässä. Virheen määrittämiseksi on olemassa useita oireyhtymäanalyysiin perustuvia menetelmiä.

Määritetään virheen sijainti jakamalla yksi mielivaltaisella määrällä nollia P(x)=1011:llä.

Elementtinumerossa tapahtui virhe:

Jäännösten lukumäärä -2>4-2=2

Eli virhe on toisessa elementissä.

VALKO-VENÄJÄN VALTION TIETOJEN JA RADIOELEKTRONIIKAN YLIOPISTO

RES-osasto

tiivistelmä aiheesta:

"Sykliset koodit. BCH-koodit"

MINSK, 2009

Sykliset koodit

Jaksokoodi on lineaarinen lohkokoodi (n,k), jolle on tunnusomaista syklisyyden ominaisuus eli syklisyys. minkä tahansa sallitun koodisanan yhden askeleen siirto vasemmalle antaa myös sallitun koodisanan, joka kuuluu samaan koodiin ja jonka koodisanojen joukkoa edustaa joukko polynomeja, joiden aste on (n-1) tai pienempi ja joka on jaollinen jollakin polynomilla g( x) astetta r = n-k, joka on binomiaalin x n +1 tekijä.

Polynomia g(x) kutsutaan generoivaksi.

Kuten määritelmästä seuraa, syklisessä koodissa koodisanat esitetään polynomeina

missä n on koodin pituus; - kertoimet kentästä GF(q).

Jos koodi on rakennettu GF(2)-kentän päälle, kertoimet saavat arvot 0 tai 1 ja koodia kutsutaan binääriksi.
Esimerkki. Jos syklisen koodin koodisana

sitten vastaava polynomi

Esimerkiksi jos koodi rakennetaan kentän GF(q)=GF(2 3) päälle, joka on GF(2):n laajennus modulo, redusoitumaton polynomi f(z)=z 3 +z+1 ja alkiot tämän kentän taulukossa 1 esitetyssä muodossa,

sitten kertoimet

ottaa tämän kentän elementtien arvot ja siksi ne itse näytetään seuraavan muodon polynomien muodossa
missä m on polynomin aste, jolla kenttälaajennus GF(2) saatiin; a i - kertoimet, jotka ottavat GF(2:n) alkioiden arvon, ts. 0 ja 1. Tällaista koodia kutsutaan q-th.

Syklisen koodin pituutta kutsutaan primitiiviksi ja itse koodia primitiiviksi, jos sen pituus on n=q m -1 GF(q:ssa).

Jos koodin pituus on pienempi kuin primitiivisen koodin pituus, koodia kutsutaan lyhennetyksi tai ei-primitiiviksi.

Kuten määritelmästä seuraa, syklisen koodin koodisanojen yleinen ominaisuus on niiden jaollisuus ilman jäännöstä jollain polynomilla g(x), jota kutsutaan generaattoriksi.

Tulos jakamalla binomi x n +1 polynomilla g(x) on testipolynomi h(x).

Syklisiä koodeja dekoodattaessa käytetään virhepolynomia e(x) ja syndroomapolynomia S(x).

Virhepolynomi, jonka aste on enintään (n-1), määritetään lausekkeesta

missä ovat polynomit, jotka edustavat vastaanotettuja (virheellisiä) ja lähetettyjä koodisanoja, vastaavasti.

Nollasta poikkeavat kertoimet e(x):ssä ovat paikkoja, jotka vastaavat virheitä.

Esimerkki.

Syndrominen polynomi, jota käytetään dekoodattaessa syklistä koodia, määritellään jäännökseksi vastaanotetun koodisanan jakamisesta generoivalla polynomilla, ts.

tai

Näin ollen oireyhtymäpolynomi riippuu suoraan virhepolynomista e(x). Tämä taulukko sisältää luettelon virhepolynomeista ja luettelon vastaavista lausekkeesta määritetyistä oireyhtymistä

(katso taulukko 2).

Dekoodausprosessin aikana vastaanotetusta koodisanasta lasketaan syndrooma, jonka jälkeen taulukosta löydetään vastaava polynomi e(x), jonka summaus vastaanotettuun koodisanaan antaa korjatun koodisanan, ts.

Luetellut polynomit voidaan laskea yhteen, kertoa ja jakaa tunnetuilla algebran säännöillä, mutta tulokseksi annetaan mod 2, ja sitten mod x n +1, jos tuloksen aste ylittää asteen (n-1).

Oletetaan, että koodin pituus on n=7, jolloin esitetään tulos mod x 7 +1.

Muodostettaessa ja dekoodattaessa syklisiä koodeja jakavien polynomien tuloksena ei yleensä tarvitse olla osamäärää, vaan jaon loppuosa.
Siksi suositellaan yksinkertaisempaa jakomenetelmää, jossa ei käytetä polynomeja, vaan vain sen kertoimia (vaihtoehto 2 esimerkissä).

Esimerkki.

Matriisikoodin määritys

Syklinen koodi voidaan määrittää generaattorilla ja tarkistusmatriisilla. Niiden rakentamiseen riittää, että tunnetaan generoiva g(x) ja testauspolynomit h(x). Ei-systeemiselle sykliselle koodille matriisit muodostetaan siirtämällä syklisesti generoivia ja tarkistavia polynomeja, ts. kertomalla ne x:llä

Ja

Matriisia H (n,k) muodostettaessa polynomin h(x) johtava kerroin sijaitsee oikealla.

Esimerkki. Sykliselle (7.4) koodille, jonka generoiva polynomi on g(x)=x 3 +x+1, matriiseilla G (n,k) ja H (n,k) on muoto:

Jossa

Systemaattiselle sykliselle koodille matriisi G (n,k) määritetään lausekkeesta

missä I k on identiteettimatriisi; R k,r on suorakaiteen muotoinen matriisi. Matriisin R k,r rivit määritetään lausekkeista tai missä a i (x) on matriisin I k i:nnen rivin arvo; i on matriisin R k,r rivinumero.

Esimerkki. Matriisi G (n,k) (7.4)-koodille, joka perustuu generoivaan polynomiin g(x)=x 3 +x+1, muodostetaan seuraavassa järjestyksessä

tai

R 4,3 määritetään käyttämällä

koska

Määritetty samalla tavalla

Tämä on alaluokka lineaarisia koodeja, joilla on gem-ominaisuus, että symbolien syklinen permutaatio koodatussa lohkossa tuottaa toisen mahdollisen koodatun lohkon samaa koodia. Sykliset koodit perustuvat algebrallisen Galois'n kenttäteorian1 ideoiden soveltamiseen.

Monet viestintäjärjestelmien tärkeimmistä kohinaa kestävistä koodeista ovat

erityisesti syklinen, perustuu äärellisiin rakenteisiin Aritmetiikka

Galoisin kentät. Ala on joukko elementtejä, joilla on äärellinen kenttä

Operaatioiden nimet ovat lainausmerkeissä, koska ne eivät aina ole yleisiä aritmeettisia operaatioita. Kentässä on aina nollaelementti (0) tai nolla ja yksikköelementti (1) tai yksi. Jos numero q kentän elementtejä rajoitetaan, niin kenttää kutsutaan rajallinen kenttä, tai äärellinen Galois-kenttä, ja on merkitty GF(q)y Jossa q- kenttäjärjestys. Pienin Galois-kenttä on kaksielementtinen kenttä GF( 2), joka koostuu vain kahdesta elementistä 1 ja 0. Jotta

1 Evariste Galois (1811 - 1832) - ranskalainen matemaatikko, loi perustan modernille algebralle.

suorittaa toimintoja elementeille GF( 2) eivät johtaneet tämän kentän rajojen ylittämiseen, ne suoritetaan modulo 2 (yleensä tämä määräytyy kentän järjestyksen mukaan yksinkertaiset Galois'n kentät).

Kentällä on useita erityisiä matemaattisia ominaisuuksia. Kenttäelementeille on määritelty yhteen- ja kertolaskuoperaatiot, ja näiden operaatioiden tulosten tulee kuulua samaan joukkoon.

Yhteen- ja kertolaskuoperaatioissa noudatetaan tavallisia assosiatiivisuuden matemaattisia sääntöjä - A + (b + c) = (a + b)+ c, kommutatiivisuus - a + b = b + a Ja A b = b A ja jakelu - A (b+ c) = A b + A Kanssa.

Jokaiselle kenttäelementille A lisättäväksi tulee olla käänteinen elementti (-A) ja jos A ei ole yhtä suuri kuin nolla, kertolaskujen käänteinen elementti (th').

Kentän tulee sisältää lisäaineyksikkö - elementti 0 siten, että A + 0 = A mille tahansa kenttäelementille A.

Kentän tulee sisältää kertova yksikkö - elementti 1, niin että aL = a mille tahansa kenttäelementille A.

Siellä on esimerkiksi reaalilukujen, rationaalilukujen ja kompleksilukujen kenttiä. Nämä kentät sisältävät äärettömän määrän elementtejä.

Itse asiassa kaikki koodisanan syklisellä permutaatiolla muodostetut joukot ovat myös koodisanoja. Joten esimerkiksi yhdistelmän 1000101 sykliset permutaatiot ovat myös koodiyhdistelmiä 0001011, 0010110, 0101100 jne. Tämä ominaisuus mahdollistaa koodaus- ja dekoodauslaitteiden huomattavan yksinkertaistamisen, erityisesti kun havaitaan virheitä ja korjataan yksittäinen virhe. Kiinnitys syklisiin koodeihin johtuu siitä, että niille luontaiset korkeat korjausominaisuudet on toteutettu suhteellisen yksinkertaisten algebrallisten menetelmien pohjalta. Samaan aikaan mielivaltaisen lineaarisen lohkokoodin dekoodaamiseen käytetään useammin taulukkomenetelmiä, jotka vaativat suuren määrän dekooderin muistia.

Syklinen koodi on lineaarinen lohkokoodi. (n, k)- koodi, jolle on tunnusomaista syklisyyden ominaisuus, ts. siirtämällä vasemmalle yhden askeleen mikä tahansa sallittu koodisana antaa myös sallitun koodisanan, joka kuuluu samaan koodiin ja jonka koodisanojen joukkoa edustaa joukko asteisia polynomeja (s- 1) tai vähemmän, jaollinen generoivalla polynomilla g(x) astetta r = n-k y joka on binomiaalin tekijä X n+

Syklisessä koodissa koodisanat esitetään polynomeilla (polynomeilla)

Jossa p - koodin pituus; A i - Galois-kentän kertoimet (koodiyhdistelmän arvot).

Esimerkiksi koodiyhdistelmälle 101101 polynomimerkinnän muoto on

Esimerkkejä syklisistä koodeista ovat tasatarkistuskoodit, toistokoodit, Hamming-koodit, PC-koodit ja turbokoodit.

Hamming-koodi. Mahdollisuus korjata Hamming-koodin virheitä liittyy minimikoodietäisyyteen d0. Kaikki monikertavirheet korjataan q= cnt (d 0- l)/2 (tässä cnt tarkoittaa "kokonaislukuosaa") ja monikertavirheet havaitaan d 0 - 1. Joten, kun tarkistetaan pariton pariteetti d Q = 2 ja yksittäiset virheet havaitaan. Hamming-koodissa d 0 = 3. Tietoluokkien lisäksi se esitellään L= log 2 Q ylimääräistä ohjausbittiä, missä Q- tietobittien määrä. Parametri L pyöristetty lähimpään korkeampaan kokonaislukuarvoon. L-bittinen ohjauskoodi on käänteinen tulos niiden informaatiobittien lukumäärästä, joiden arvot ovat yhtä kuin yksi, lisäämällä bittikohtaisesti (addition modulo 2).

Esimerkki 7.7

Olkoon pääkoodi 100110, ts. Q= 6. Määritellään lisäkoodi.

Ratkaisu

Löydämme sen L= 3 ja komplementtikoodi on

jossa P on bittikohtaisen summauksen symboli ja inversion jälkeen meillä on 000. Nyt lisäkoodi lähetetään pääkoodin mukana. Vastaanottimessa lisäkoodi lasketaan jälleen ja sitä verrataan lähetettyyn koodiin. Vertailukoodi tallennetaan, ja jos se on eri kuin nolla, niin sen arvo on pääkoodin virheellisesti vastaanotetun bitin numero. Joten jos koodi 100010 hyväksytään, laskettu lisäkoodi on yhtä suuri kuin inversio 010Ш10 = 100, ts. 011, mikä tarkoittaa virhettä 3. numerossa.

Hamming-koodien yleistys ovat syklisiä BCH-koodeja, jotka mahdollistavat useiden virheiden korjaamisen valitussa koodiyhdistelmässä.

Reed-Solomon koodit perustuvat Galois-kenttiin tai äärellisiin nolliin. Aritmeettiset operaatiot yhteen-, vähennys-, kerto-, jakolasku- jne. lopullisen nollan elementtien yli antaa tuloksen, joka on myös tämän nollan elementti. Reed-Solomon-kooderin tai dekooderin on suoritettava nämä toiminnot. Kaikki toiminnot koodin toteuttamiseksi vaativat erikoislaitteiston tai erikoisohjelmiston.

Turbo koodit. Redundantteja koodeja voidaan käyttää joko itsenäisesti tai useiden koodien yhdistelmänä, kun yhden redundantin koodin symbolijoukkoja pidetään toisen redundantin koodin perustietosymboleina. Tätä yhdistystä alettiin kutsua peräkkäin koodi. Yhdistettyjen koodien valtava etu on, että niiden käyttö mahdollistaa kooderin ja erityisesti dekooderin yksinkertaistamisen verrattuna vastaaviin laitteisiin, joissa on samanpituisia ja redundanssisia ei-ketjutettuja koodeja. Kaskadikoodaus johti turbokoodien luomiseen. Turbo koodi kutsua rinnakkaista signaalirakennetta, joka koostuu kahdesta tai useammasta systemaattisesta koodista. Niiden rakentamisen perusperiaate on useiden rinnakkaisten komponenttianturien käyttö. Komponenttikoodeina voit käyttää sekä lohko- että konvoluutiokoodeja, Hamming-koodeja, PC-koodia, BCH:ta jne. Rei'itys (puhkaisu) mahdollistaa turbokoodin suhteellisen nopeuden lisäämisen sovittamalla sen korjauskykyä tilastollisiin ominaisuuksiin viestintäkanavasta. Turbokoodin generoinnin periaate on seuraava: tulosignaali X, koostuu TO bitti, syötetään rinnakkain N lomittajat. Jokainen jälkimmäisistä on laite, joka järjestää elementit uudelleen lohkoon TO bittejä näennäissatunnaisessa järjestyksessä. Lomittimien lähtösignaali - symbolit muuttuneella järjestyksellä - lähetetään vastaaville peruskoodereille. Binäärisekvenssit x p i= 1,2,..., JV, kooderin lähdössä ovat tarkistussymbolit, jotka yhdessä informaatiobittien kanssa muodostavat yhden koodisanan. Lomittajan käyttö mahdollistaa korrelaatiovirheiden sekvenssien syntymisen turbokoodeja dekoodattaessa, mikä on tärkeää käytettäessä prosessoinnissa perinteistä toistuvaa dekoodausmenetelmää. Komponenttikoodin valinnasta riippuen turbokoodit jaetaan konvoluutioturbokoodeiksi ja lohkotuotekoodeiksi.

Syklinen koodi on lineaarinen koodi, joka on äärellinen joukko, joka on suljettu sen muodostavien koodivektoreiden syklisen siirron vaikutuksesta. Antaa sen olla annettu n-ulotteinen vektori v = a 0 a 1 …a n-1 koordinaatit lopullisesta kentästä F. Sen syklistä siirtymää kutsutaan vektoriksi v"=a n-1 a 0 a 1… a n -2 .

Harkitsemme n-ulotteinen aritmeettinen avaruus Galois-kentän päällä GF(2). Jokainen vektori a 0 a 1 …a n-1 / GF(2) voidaan verrata polynomia yksi yhteen a 0 +a 1 x+…+a n -1 x n-1 kertoimella alkaen GF(2). Kahden vektorin summa a 0 a 1 …a n-1 ja b 0 b 1 …b n-1 asetetaan vastaamaan niitä vastaavien polynomien summaa, kenttäalkioiden tulo vektorilla - tätä vektoria vastaavan polynomin tulo elementillä.

Tarkastellaanpa jotain polynomia g(x) kuvatusta lineaarisesta avaruudesta. Joukko kaikista tämän aliavaruuden polynomeista, jotka ovat jaollisia ilman jäännöstä g(x), muodostaa lineaarisen aliavaruuden. Lineaarinen aliavaruus määrittelee jonkin lineaarisen koodin.

Polynomiluokan muodostama lineaarinen koodi C(g(x)), jonkin polynomin kerrannaisia g(x), jota kutsutaan generoivaksi polynomiksi, kutsutaan polynomiksi.

Osoitetaan kuinka polynomikoodit liittyvät toisiinsa C(g(x)) ja sykliset koodit. Anna a = a 0 …a n-1 on jokin koodisana ja sitä vastaava koodipolynomi a(x) = a 0 +...+a n -1 x n-1. Syklinen vaihto a" vastaa koodipolynomia a"(x) = a n -1 +a 0 x+…+a n -2 x n -1 , joka voidaan ilmaista alkuperäisenä:

Koska polynomikoodin on oltava jaollinen g(x), niin polynomi, jotta se olisi syklinen a"(x) on oltava jaollinen g(x). Tämän tarkastelun perusteella voimme muotoilla seuraavan lauseen. Polynomikoodi on syklinen silloin ja vain, jos polynomi g(x) on polynomin jakaja x n–1. Tässä tapauksessa polynomi g(x) kutsutaan syklisen koodin generoivaksi polynomiksi.

Koodausteoriassa seuraava lause on todistettu: jos polynomi g(x) on tutkinto n–k ja on jakaja x n-1 siis C(g(x)) on lineaarinen syklinen ( n, k)-koodi.

Polynomi x n–1 tekijä x n–1 = (x–1)(x n -1 +x n-1 +…+1). Siksi sykliset koodit ovat olemassa mille tahansa n. Syklien lukumäärä n-bittiset koodit, jotka vastaavat polynomin jakajien lukumäärää x n–1. Polynomilaajennustaulukoita on kehitetty syklisten koodien muodostamiseen x n–1 pelkistymättömiksi polynomeiksi, eli sellaisiksi, jotka ovat jaollisia vain yksiköllä ja itsestään.

Tarkastellaan esimerkiksi, mitä koodeja voidaan rakentaa polynomin perusteella x 7-1 yli kentän GF(2). Polynomin laajentumisella redusoitumattomiksi tekijöiksi on muoto

Koska on mahdollista muodostaa kuusi polynomin jakajaa x 7-1, joka yhdistää redusoitumattomia jakajia, on kuusi binaarista syklistä koodia. ( n, k)-koodi määräytyy ensinnäkin arvon perusteella n ja toiseksi arvo k = n – s, s– jakajapolynomin aste x n–1, joka määrittää koodin. Alla on polynomijakajat ja niitä vastaavat arvot 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.

Koodissa (7, 6) on vain yksi tarkistussymboli ja (7, 1) koodissa vain yksi tietosymboli. Ne ovat vastaavasti pariteettitarkistuskoodi ja toistokoodi.

Kuten tavallinen lineaarinen koodi, syklinen koodi voidaan määrittää generaattorimatriisilla. Siksi tehtävänä on löytää tällainen matriisi, eli löytää k sen muodostavat lineaarisesti riippumattomat koodiyhdistelmät. Tätä tarkoitusta varten käytämme syklisen koodin ominaisuutta suljettuna suhteessa sykliseen siirtoon. Huomaa, että syklinen siirto oikealle yhdellä paikalla vastaa polynomin kertomista g(x) päällä x. Sitten generoiva matriisi voidaan muodostaa ottamalla generoiva polynomi ja k sen sykliset muutokset:

Tarkastellaan nyt kuinka generointipolynomin avulla g(x) = 1+x+x 3-koodaus suoritetaan (7, 4)-koodilla. Otetaan esimerkiksi 4-bittinen sana (0101), joka vastaa polynomia f(x) = x + x 3. Kerrotaan nämä kaksi polynomia.

Vastaa tätä sanaa muodollisesta muuttujasta x. Voidaan nähdä, että tämä vastaavuus ei ole vain yksittäinen, vaan myös isomorfinen. Koska "sanat" koostuvat kentän kirjaimista, ne voidaan lisätä ja kertoa (elementti kerrallaan), jolloin tulos on samassa kentässä. Polynomi, joka vastaa sanaparin lineaarista yhdistelmää ja on yhtä suuri kuin näiden sanojen polynomien lineaariyhdistelmä

Tämä mahdollistaa sen, että voimme pitää n-pituisten sanojen joukkoa äärellisen kentän yli polynomien lineaarisena avaruutena, joiden aste on enintään n-1 kentän yli

Algebrallinen kuvaus

Jos koodisana, joka saadaan siirtämällä syklisesti bitti oikealle sanasta , niin sitä vastaava polynomi c 1 (x) saadaan edellisestä kertomalla x:llä:

Hyödyntämällä sitä tosiasiaa

Siirrä oikealle ja vasemmalle vastaavasti j riveissä:

Jos m(x) - mielivaltainen polynomi kentän päällä GF(q) Ja c(x) - syklisen koodisana ( n,k) koodi, sitten m(x)c(x)mod(x n − 1) myös tämän koodin koodisana.

Luodaan polynomia

Määritelmä Syklisen ( n,k) koodi C tällaista nollasta poikkeavaa polynomia kutsutaan alkaen C, jonka aste on pienin ja korkeimman asteen kerroin g r = 1 .

Lause 1

Jos C- syklinen ( n,k) koodi ja g(x) on sen generoiva polynomi, sitten aste g(x) on yhtä suuri kuin r = n − k ja jokainen koodisana voidaan esittää yksilöllisesti muodossa

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

missä on tutkinto m(x) pienempi tai yhtä suuri kuin k − 1 .

Lause 2

g(x) - generoiva polynomi syklistä ( n,k) -koodi on binomiaalin jakaja x n − 1

Seuraukset: siten mikä tahansa polynomi, jakaja, voidaan valita generoivaksi polynomiksi x n− 1. Valitun polynomin aste määrittää testisymbolien määrän r, tietosymbolien määrä k = n − r .

Generaattorin matriisi

Muuten polynomit ovat lineaarisesti riippumattomia m(x)g(x) = 0 ei-nollalle m(x), mikä on mahdotonta.

Tämä tarkoittaa, että koodisanoja voidaan kirjoittaa, kuten lineaarisille koodeille, seuraavasti:

, Missä G on generoiva matriisi, m(x) - informatiivinen polynomi.

Matrix G voidaan kirjoittaa symbolisessa muodossa:

Tarkista matriisi

Kullekin syklisen koodin koodisanalle . Siksi tarkista matriisi voidaan kirjoittaa näin:

Koodaus

Ei-järjestelmällinen

Ei-systeemisessä koodauksessa koodisana saadaan informaatiopolynomin tulon muodossa generoivalla polynomilla

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

Se voidaan toteuttaa käyttämällä polynomikertoimia.

Systemaattinen

Systemaattisella koodauksella koodisana muodostetaan informaation alilohkon ja vahvistuksen muodossa

Muodostakoon tietosana sitten koodisanan korkeampia tehoja

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

Ehdosta se sitten seuraa

Tämä yhtälö asettaa säännön systemaattiselle koodaukselle. Se voidaan toteuttaa käyttämällä monisyklisiä lineaarisia suodattimia (MLF)

Esimerkkejä

Binäärikoodi (7,4,3).

Jakajana x 7 − 1 valitaan kolmannen asteen generoiva polynomi g(x) = x 3 + x + 1 , niin tuloksena olevalla koodilla on pituus n= 7, testisymbolien määrä (generoivan polynomin aste) r= 3, tietosymbolien lukumäärä k= 4, vähimmäisetäisyys d = 3 .

Generaattorin matriisi koodi:

,

jossa ensimmäinen rivi on polynomin merkintä g(x) kertoimet kasvavassa järjestyksessä. Loput rivit ovat ensimmäisen rivin syklisiä siirtymiä.

Tarkista matriisi:

,

jossa i:s sarake, alkaen 0:sta, edustaa jaon loppuosaa x i polynomiksi g(x) kirjoitettu nousevassa järjestyksessä alkaen ylhäältä.

Joten esimerkiksi saadaan 3. sarake tai vektorimuodossa.

Se on helppo varmistaa GH T = 0 .

Binäärinen (15,7,5) BCH-koodi

Generoivana polynomina g(x) voit valita kahden jakajan tulon 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 .

Sitten jokainen koodisana voidaan saada käyttämällä informaatiopolynomin tuloa m(x) tutkinnon kanssa k− 1 eli näin:

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

Esimerkiksi tietosana vastaa polynomia m(x) = x 6 + x 5 + x 4 + 1 , sitten koodisana 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 tai vektorimuodossa

Katso myös

Linkit

Wikimedia Foundation.

• 2010.
• Sykliset muodot musiikissa

Sykliset rajaehdot

Katso, mitä "sykliset koodit" ovat muissa sanakirjoissa: lyhennetyt sykliset koodit

- [L.G. Sumenko. Englanti-venäläinen tietotekniikan sanakirja. M.: Valtionlaitos TsNIIS, 2003.] Aiheet tietotekniikka yleisesti FI lyhennetyt sykliset koodit ... Reed-Solomon koodit

- ei-binaariset sykliset koodit, joiden avulla voit korjata tietolohkojen virheet. Koodivektorin elementit eivät ole bittejä, vaan bittiryhmiä (lohkoja). Reed Solomon -koodit, jotka toimivat tavujen (oktettien) kanssa, ovat hyvin yleisiä. Reed Solomonin koodi on... Wikipedia Golay koodit - Perhe täydellisiä lineaarisia lohkokoodeja virheenkorjauksella. Hyödyllisin on Golay-binäärikoodi. Kolmiosainen Golay-koodi tunnetaan myös. Golay-koodeja voidaan pitää syklisinä koodeina. ……

Teknisen kääntäjän opas

Virhekoodien korjaaminen Virheenkorjauskoodit

- Viestintätekniikan virheiden havaitseminen, toimenpide, jonka tarkoituksena on valvoa tietojen eheyttä tallennettaessa/toistettaessa tai siirrettäessä sitä tietoliikennelinjoja pitkin. Virheenkorjaus (virheenkorjaus) -menettely tietojen palauttamiseksi... ... Wikipedia jälkeen Virheenkorjauskoodit