A ciklikus kód egy lineáris kód, amely az azt alkotó kódvektorok ciklikus eltolásának működése szempontjából zárt véges halmaz. Adott legyen n-dimenziós vektor v = a 0 a 1 …a n-1 koordinátákkal a cél mezőből F. Ciklikus eltolódását vektornak nevezzük v"= a n-1 a 0 a 1... a n -2 .

Fontolgat n-dimenziós aritmetikai tér egy Galois-mező felett GF(2). Mindegyik vektor a 0 a 1 …a n-1 / GF(2) társítható egy-egy polinom a 0 +a 1 x+…+a n -1 x n-1-től származó együtthatókkal GF(2). Két vektor összege a 0 a 1 …a n-1 és b 0 b 1 …b n-1 a hozzájuk tartozó polinomok összege, a mezőelemek szorzata a vektorral - az ennek a vektornak megfelelő polinom elem szorzata.

Tekintsünk néhány polinomot g(x) a leírt lineáris térből. Az ebből az altérből származó összes olyan polinom halmaza, amely maradék nélkül osztható vele g(x) lineáris alteret képez. A lineáris altér valamilyen lineáris kódot határoz meg.

A polinomok egy osztálya által alkotott lineáris kód C(g(x)), valamilyen polinom többszörösei g(x), amelyet generáló polinomnak neveznek, polinomnak nevezzük.

Mutassuk meg, hogyan kapcsolódnak egymáshoz a polinomkódok C(g(x)) és ciklikus kódok. Hadd a = a 0 …a n-1 egy kódszó, és a megfelelő kódpolinom a(x) = a 0 +...+a n -1 x n-1. ciklikus eltolódás a" a kódpolinomnak felel meg a"(x) = a n -1 +a 0 x+…+a n -2 x n -1 , ami az eredetivel fejezhető ki:

Mivel a polinom kódnak oszthatónak kell lennie g(x), majd annak érdekében, hogy ciklikus legyen, a polinom a"(x) oszthatónak kell lennie g(x). Ebből a megfontolásból a következő tételt fogalmazhatjuk meg. Egy polinom kód akkor és csak akkor ciklikus, ha a polinom g(x) a polinom osztója x n-1. Ebben az esetben a polinom g(x) ciklikus kód generáló polinomjának nevezzük.

A kódoláselméletben a következő tétel bizonyítást nyer: ha egy polinom g(x) végzettséggel rendelkezik n–kés osztó x n-1 akkor C(g(x)) lineáris ciklikus ( n, k)-kód.

Polinom x n-1 faktorizálás x n–1 = (x–1)(x n -1 +x n-1 +…+1). Ezért bármelyikhez léteznek ciklikus kódok n. Ciklikusok száma n-bit kódok egyenlő a polinom osztóinak számával x n-1. Ciklikus kódok létrehozásához polinomok felbontásának táblázatait fejlesztették ki x n-1 az irreducibilis polinomokhoz, vagyis azokhoz, amelyek csak 1-gyel és önmagával oszthatók.

Gondoljunk például arra, hogy milyen kódok építhetők fel a polinom alapján x 7-1 a mezőny felett GF(2). Egy polinom irreducibilis tényezőkre való felbontásának van formája

Mivel a polinom hat osztóját képezhetjük x 7–1, az irreducibilis osztók kombinálásával hat bináris ciklikus kód létezik. ( n, k)-kódot először is az érték határozza meg n, másodszor pedig az érték k = n – s, s az osztópolinom foka x n-1 meghatározza a kódot. Az alábbiakban a polinom osztói és a hozzájuk tartozó értékek láthatók 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+x3+x2+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.

A (7, 6)-kódnak csak egy ellenőrző szimbóluma van, a (7, 1)-kódnak pedig csak egy információs szimbóluma. Ezek rendre egy paritás-ellenőrző kód és egy ismétlési kód.

Egy közönséges lineáris kódhoz hasonlóan egy ciklikus kód is megadható generáló mátrixszal. Ezért a feladat egy ilyen mátrix megtalálása, vagyis megtalálása k lineárisan független kódkombinációk alkotják. Ehhez a ciklikus kód bezárásának tulajdonságát használjuk a ciklikus eltolás működéséhez képest. Ne feledje, hogy egy számjeggyel jobbra való ciklikus eltolás egyenértékű a polinom szorzásával g(x) tovább x. Ekkor a generáló mátrix összeállítható úgy, hogy soroknak vesszük a generáló polinomot és k ciklikus eltolódásai:

Most nézzük meg, hogyan, a generáló polinom segítségével g(x) = 1+x+x A 3-at a (7, 4)-kód kódolja. Vegyünk például egy 4 bites szót (0101), amely megfelel a polinomnak f(x) = x + x 3. Ennek a két polinomnak a szorzata

A ciklikus kódok egyfajta lineáris csoportkódok, és a szisztematikus kódokhoz tartoznak. Eredetileg a dekódolási eljárás egyszerűsítésére jöttek létre. Az ilyen kódok nagy hibaészlelési hatékonysága azonban biztosította széles körű gyakorlati alkalmazásukat. Célszerű egy ciklikus kód bináris vektorát nem nullák és egyesek kombinációjának tekinteni, hanem bizonyos fokú polinomnak.

ahol x a számrendszer alapja, kettes számrendszer esetén a halmazhoz tartozó együtthatók.

Példa. Egy bináris vektor polinomként ábrázolható a következőképpen:

A bináris vektorok polinomként való ábrázolása lehetővé teszi, hogy a vektorokon végzett műveleteket polinomokra vonatkozó műveletekre redukáljuk. Ahol:

a polinomok összeadása az együtthatók modulo 2 összegére csökken a változó egyenlő hatványai mellett

a szorzás a hatványfüggvények szorzásának szokásos szabálya szerint történik, azonban az adott fokon kapott együtthatókat modulo 2-vel összeadjuk;

az osztás a hatványfüggvények felosztásának szabályai szerint történik, míg a kivonás műveletét az összegzés modulo 2 váltja fel.

Példa. Keresse meg a polinomok összegét!

Keresse meg a polinomok szorzatát!

Hajtsa végre a polinomiális osztást

A ciklikus kódok fő tulajdonsága a következő: ha egy vektor ciklikus kódhoz tartozik, akkor a vizsgáltból ciklikus eltolások segítségével nyert vektor is a ciklikus kódhoz tartozik.

A ciklikus kódok létrehozásának ötlete az irreducibilis polinom fogalmán alapul. Egy polinomot irreducibilisnek mondunk, ha csak önmagával és 1-gyel osztható, és nem osztható más polinommal. Más szóval, egy irreducibilis polinom nem ábrázolható alacsonyabb fokú polinomok szorzataként. Egy irreducibilis polinom maradék nélkül oszt egy polinomot. Az irreducibilis polinomok polinomokat generálnak a ciklikus kódok elméletében. A különböző fokozatú irreducibilis polinomok típusait az alábbiakban adjuk meg

Példák irreducibilis polinomokra:

A ciklikus kódvektorok a következő szabályok szerint épülnek fel. Legyen valamilyen természetes kód bármely bináris vektora; - fokú monomiális irreducibilis fokú polinom Ekkor egy ciklikus kód tetszőleges vektorát képezzük a reláció segítségével

hol van az osztás maradéka

Így egy ciklikus kód bármely vektora létrehozható a természetes vektor szorzásával bináris kód fokos monomimmal az osztás maradékának hozzáadásával a kapott szorzathoz Ciklikus kódok ily módon történő felépítésekor az információs bitek elhelyezkedése minden kódvektorban szigorúan rendezett - a kódvektor legmagasabb bitjeit foglalják el, a fennmaradó bitek pedig ellenőrző bitek.

Példa. A természetes bináris kódvektor alakja

A vektort polinomként ábrázoljuk

Ha egy polinomot elosztunk egy polinommal, megkapjuk a maradékot. Ezért

A ciklikus kód, mint minden szisztematikus kód, kényelmesen megadható mátrix formában egy ilyen alakú generáló mátrix segítségével.

ahol a formátum transzponált egysége yatrix - az osztás maradéka által alkotott ellenőrző számjegyek mátrixa

Állítsuk be a ciklikus kód generáló mátrixát az információs bitek hosszával és a generáló polinommal .

Nyilvánvaló, hogy a generáló mátrix üres felületének alakja van

A mátrix ellenőrző bitsorainak megtalálásához kiszámítjuk és polinom formájában írjuk az azonosságmátrix minden vektorát

A ciklikus kódvektor hossza tehát

(lásd szkennelés)

Ennek eredményeként megkapjuk a C generáló mátrixot:

Egy ciklikus kód bármely vektorát a generáló mátrix vektorainak összegeként kapjuk meg. Mivel a ciklikus kód csoportkód, a nulla vektor mindig a ciklikus kódhoz van hozzárendelve, mint a csoport azonosító eleme.

13.5. táblázat

Példa. Szerkessze meg a generáló mátrix által adott ciklikus kód összes vektorát

A kód a táblázatban látható. 13.5.

Megjegyzendő, hogy egy adott generáló mátrix által adott minden ciklikus kód többféle változatban is ábrázolható, amelyek hosszában és információbitek számában különböznek egymástól (azonos detektálási képességekkel). Az úgynevezett rövidített ciklikus kódok ezen változatait úgy kapjuk meg, hogy a ciklikus kód generáló mátrixában az utolsó sorokat és ugyanannyi oszlopot töröljük a bal oldalon. Ebben az esetben az ellenőrző számjegyek száma változatlan marad, a kód hossza és információs számjegyeinek száma a generáló mátrix áthúzott sorainak és oszlopainak számával megegyező mértékben csökken.

Példa: Egy ciklikus kódot a generátormátrixa ad meg

Balról húzzuk át az utolsó hat sort és az első hat oszlopot. Megkapjuk a generáló mátrixot

Az eredményül kapott kód jellemzői (hibaészlelés szempontjából) megegyeznek a generátormátrix által képviselt ciklikus kóddal

Ciklikus kódok felépítése -val adott paramétereket az irreducibilis polinom generátorának megválasztásához kapcsolódik. A generáló polinom kiválasztása a következő feltétel alapján történik: a polinom fokának meg kell egyeznie a ciklikus kód ellenőrző bitjeinek számával.

A gyakorlatban gyakran felmerül a probléma egy adott teljesítmény és egy adott detektáló és javító képesség ciklikus kódjának megalkotása.

1. Mivel a ciklikus kód hatványa adott, információs bitjeinek száma a képlet szerint kerül meghatározásra.

2. A ciklikus kód ellenőrző számjegyeinek optimális számát speciális táblázatok határozzák meg.

3. A könyvtárak szerint minden irreducibilis fokszámpolinom megtalálható

4. Az egyik fokszámú nem vezető polinomhoz (olyan polinomot kell választani, amelyben a legtöbb tag szerepel) egy ciklikus kód generáló mátrixát szerkesztjük. Minden kódvektor a képlet alapján kerül kiszámításra

ahol a generáló mátrix információvektorának polinomja; - fok monomiális - osztás maradéka

5. A megszerkesztett generáló mátrixot a következő feltételekkel ellenőrzik:

a) a generáló mátrix bármely vektorának Hamming értelemben vett súlyának ki kell elégítenie azt az összefüggést, ahol a szóban forgó ciklikus kód minimális távolsága Hamming értelmében;

b) az ellenőrző vektor Hamming értelemben vett súlyának, amely a generáló mátrix bármely két ellenőrző vektorának modulo 2 összege, ki kell elégítenie az összefüggést.

6. Ha a ciklikus kód generáló mátrixa az összes fenti feltételt kielégíti, akkor a ciklikus kód összes vektorát kiírjuk és meghatározzuk a lineáris csoportkódokra ismert szabályok szerint. Ha a kód nem felel meg a követelményeknek, akkor másik, azonos fokú generáló polinomot választunk, és a ciklikus kód generálási eljárást megismételjük egy új polinomnál.

Készítsünk egy ciklikus kódot 16-os hatványú és egy javító kódot a kapacitással

Az érték meghatározásához a

3 "A referenciakönyvekből megtaláljuk az összes irreducibilis fokú polinomot. Két ilyen polinom létezik:

4. Generáló polinomnak választjuk A ciklikus kód generáló mátrixának üres alakja

A mátrixból származó minden információs vektort egy polinom képviseli

A képlet segítségével meghatározzuk a generáló mátrix összes vektorát

Mivel a ciklikus kódvektor hossza (lásd a generáló mátrix formátumát, akkor

Hasonlóképpen megtaláljuk a generáló mátrix összes többi vektorát is

13.6. táblázat

Az eredmény egy generáló mátrix C? ciklikus kód

5. Az így kapott generáló mátrix minden szükséges feltételnek eleget tesz. Ezért teljesen ciklikus kódot építünk fel (13.6. táblázat). A táblázatból látható, hogy a kód megfelel, azaz kielégíti a feladat követelményeit.

Megjegyzések. Ha irreducibilis polinomot használunk generátorként, olyan kódot kapunk, amely a feladat követelményeit is kielégíti. Generátormátrixának van a formája

A ciklikus kódokkal történő hibaészlelés a következőképpen történik. Egy ciklikus kód bármely vektora osztható egy generáló polinommal maradék nélkül. Ezért a ciklikus kódvektorban a hiba jelenlétének kritériuma a ciklikus kódvektornak a generáló polinommal való elosztásából származó nullától eltérő maradék megjelenése. A nem nulla maradék a hiba azonossága a ciklikus kódvektorban, de megjelenése nem jelzi a hiba helyét a kódvektorban. A hibajavítás a következő algoritmuson alapul:

1. Osszuk fel a kapott kódvektort egy generáló polinomra.

Ha az egységek száma nem haladja meg a kód korrekciós képességét, akkor add hozzá a kapott modulo 2 vektort a kapott maradékkal. Az összegzés eredménye a korrigált kódvektort adja. Ha a maradék egységeinek száma nagyobb, mint a kód korrekciós képessége, akkor hajtsuk végre a torzított vektor ciklikus eltolását egy bittel balra, majd osszuk el egy generáló polinommal. Ha a kapott maradék nem tartalmaz többet, mint a ciklikus kód korrekciós kapacitása, akkor a ciklikusan eltolt vektort összegezzük a maradékkal. Az összegzés eredménye ciklikusan egy számjeggyel jobbra tolódik el. Az eredményül kapott vektor már nem tartalmaz hibákat, és ciklikus kódvektor.

3. Ha az első ciklikus eltolás és az azt követő felosztás után a maradék több egyet tartalmaz, mint a kód korrekciós képessége, akkor ismételje meg az algoritmus eljárását, amíg a maradék a kód korrekciós képességét meg nem haladó számmal meg nem haladja. kapott. Ebben az esetben az utolsó ciklikus eltolás eredményét összeadjuk a maradékkal, és a kapott vektort ciklikusan annyi bittel toljuk el jobbra, amennyivel az eredetileg vett hibás vektor balra tolódott. Az eredmény egy korrigált kódvektor.

Adjuk meg a ciklikus kódot a generáló mátrix С és a generáló polinom, ahol

A kód 3-as, azaz kijavítja a többszörösségi hibákat, legyen a 0001101 vektor helyett a 0011101. A hiba kijavításához a következő műveleteket hajtjuk végre. A kapott vektort polinomként írjuk fel: majd osztunk vele

Az osztás eredményeként kapott maradék három egységet tartalmaz, ami több, mint a kód korrekciós képessége. Ezért a kapott kódvektor egy bitjével ciklikus eltolást végzünk balra. Ennek eredményeként megvan

-el osztunk

Az így kapott maradék két egységet tartalmaz, ami több, mint a kód korrekciós képessége. Ezért a kapott kódvektor egy bitjével még egy ciklikus eltolást végzünk balra. Ennek eredményeként megvan

-el osztunk

A kapott maradék ismét két egységet tartalmaz, így még egy ciklikus eltolást végzünk egy bittel balra, és megkapjuk az Osztás

Lineáris kódok osztálya, amelyek ún Kínai kódok. A név ezeknek a kódoknak a fő tulajdonságából származik: ha valamilyen kódkombináció ciklikus kódhoz tartozik, akkor az eredeti kombináció ciklikus permutációjával kapott kombináció (ciklikus eltolás) is ehhez a kódhoz tartozik:

A ciklikus kódok összes megengedett kombinációjának második tulajdonsága, hogy maradék nélkül oszthatók valamilyen kiválasztott polinommal, amelyet generátornak neveznek.

Ezeket a tulajdonságokat a kódoló és dekódoló kódok felépítésében, valamint a hibaészlelésben és -javításban használják.

A ciklikus kódok a hibajavító kódok egész családját jelentik (amelyek egyik változata a Hamming-kódok), amelyek nagy rugalmasságot biztosítanak a kódkombinációk átvitele során előforduló hibák észlelésének és kijavításának szükséges képességével rendelkező kódok implementálásának lehetőségében. kommunikációs csatornán keresztül. A ciklikus kód szisztematikus blokk (n, &)-kódokra utal, amelyekben Nak nek az első bitek az elsődleges kód és a következő (l - Nak nek) számjegyek tesztek.

A ciklikus kódok felépítése azon a műveleten alapul, hogy a továbbított kódkombinációt elosztjuk a generálható irreducibilis fokszámú polinommal. G. Az osztás fennmaradó részét ellenőrző bitek képzésére használjuk fel. Ebben az esetben az osztási műveletet megelőzi a szorzási művelet, amely a ^ bites információs kódkombinációt balra tolja G kisülések.

A vett n-bites kódkombináció dekódolásakor ismét végbemegy a generáló (előállító, képző) polinomra való felosztás.

A hibaszindróma ezekben a kódokban a kapott kódkombinációnak a generáló polinommal való elosztásából származó maradék jelenléte. Ha a szindróma nulla, akkor úgy tekintjük, hogy nincsenek hibák. Ellenkező esetben a fogadott szindróma segítségével meghatározhatja a kapott kódkombináció bitszámát, amelyben hiba történt, és javíthatja azt.

Nem kizárt azonban a többszörös hiba lehetősége a kódkombinációkban, ami téves korrekciókhoz és (vagy) hibák észlelésének kudarcához vezethet az egyik engedélyezett kombináció másikká alakításakor.

Legyen a blokkban lévő bitek teljes száma i, ebből hasznos információ visz T bit, akkor hiba esetén lehetőség van j bit javítására. 5. függőség PÉs T kódokhoz a táblázatból határozható meg. 2.6.

2.6. táblázat

A kombinációk számjegyeinek teljes számának függősége az információ és a javítható számjegyek számától

A különbség növelése (n - t), nem csak a javítható bitek számát lehet növelni s, hanem több hiba észlelésére is. Az észlelt többszörös hibák százalékos arányát a táblázat tartalmazza. 2.7.

2.7. táblázat

Az észlelt többszörös hiba százalékos aránya

Kényelmes ciklikus kódokat leírni és polinomok (vagy polinomok) segítségével megszerkeszteni. A kombinációs rekord mint polinom arra szolgál, hogy formalizált módon jelenítse meg az eredeti kódszó ciklikus eltolásának műveletét. Tehát a "-elem kódszó leírható a polinommal (P- 1) végzettség:

Ahola„_j =(0, 1), ésa „_, =0 a kombináció nulla elemeinek felel meg, d„_, = 1 - nem nulla;én- a kódkombináció számjegyének száma.

Mutassunk be polinomokat adott 4 elemes kombinációkhoz:

Az összeadási és kivonási műveletek egyenértékűek és asszociatívak, és a 2. modulban hajtódnak végre:

Példák a műveletekre:

Az osztási művelet a polinomok szokásos osztása, de kivonás helyett az összeadás modulo 2 használatos:

A kódkombináció ciklikus eltolása az elemeinek jobbról balra mozgatása a sorrend megzavarása nélkül, így a bal szélső elem veszi át a jobb szélső helyét.

A ciklikus kódok fő tulajdonságai és elnevezése azzal a ténnyel függ össze, hogy az átvitt üzenetben minden megengedett bitkombináció (kódszavak) megszerezhető valamely forráskódszó ciklikus eltolása műveletével.

Tegyük fel, hogy a kezdeti kódkombináció és a megfelelő polinom adott:

Szorozzuk meg Ó) tovább X:

A maximális fokozat óta x hosszúságú kódkombinációban P nem haladja meg az (n - 1) értéket, akkor a kapott kifejezés jobb oldaláról az eredeti polinom megszerzéséhez ki kell vonni Ó"- 1). Kivonás Ó"- 1) a maradékot modulo-nak nevezzük (x p - 1).

Az eredeti kombináció / mérték eltolódása a következőképpen ábrázolható: fejsze)? U - Ó"- 1), azaz szorzás Ó) nah" és a maradék modulo (x" - 1) bevétele. A maradék felvétele akkor szükséges, ha olyan polinomot kapunk, amelynek foka nagyobb vagy egyenlő P.

A ciklikus kódok felépítésének ötlete a felhasználáson alapul irreducibilis polinomok. Az irreducibilis polinom olyan polinom, amely nem ábrázolható alacsonyabb fokú polinomok szorzataként, azaz. csak önmagával vagy 1-gyel osztható, más polinommal nem. Egy binomiális (x" + 1) osztható egy ilyen polinommal maradék nélkül. Az irreducibilis polinomok a ciklikus kódok elméletében polinomokat generálnak.

Visszatérve a ciklikus kód definíciójához, és figyelembe véve a kódkombinációk ciklikus eltolási műveleteinek jelölését, egy ciklikus kód generáló mátrixát a következő formában írhatjuk fel:

AholP(x)- az eredeti kódkombináció, amely alapján az összes többit megkapjuk(T- 1) alapvető kombinációk;

C = 0 vagyCj =1 ("O", ha a polinom eredő fokaP(x)-x'nem haladja meg (l - 1), vagy "1" - ha meghaladja).

Kombináció P(x) generáló (generátor) kombinációnak nevezzük. Ciklikus kód létrehozásához elegendő a helyes választás P(x). Ekkor az összes többi kódkombináció ugyanaz, mint a csoportkódban.

A generáló polinomnak meg kell felelnie a következő követelményeknek:

• P(x) nullától eltérőnek kell lennie;
• súly P(x) nem lehet kisebb, mint a minimális kódtávolság: V(P(x)) > d mm ;
• P(x) kell maximális fokozat k (k - a redundáns elemek száma a kódban);
• P(x) osztójának kell lennie a polinomnak (x" - 1).

Az utolsó feltétel teljesülése ahhoz vezet, hogy a ciklikus kód minden működő kódkombinációja elnyeri az oszthatóság tulajdonságát P(x) nyom nélkül. Ezt szem előtt tartva a ciklikus kód egy másik definíciója is megadható: a ciklikus kód olyan kód, amelynek minden működő kombinációja maradék nélkül osztható egy generáló polinommal.

A generáló polinom mértékének meghatározásához használhatja az r > log 2 kifejezést (és + 1), hol P- az egy időben továbbított csomag mérete, pl. a megszerkesztett ciklikus kód hossza.

A polinomok generálására a táblázatban talál példákat. 2.8.

2.8. táblázat

Példák polinomok generálására

A ciklikus kód megengedett kódkombinációjának egyszerű kód kombinációjából történő kinyerésére szolgáló algoritmus a következő.

Legyen adott a polinom P (x) \u003d a g _ ( x g + a g _ 2 x r ~ 1 + ... + 1, amely meghatározza a kód korrekciós képességét és az ellenőrző számjegyek számát Nak nek, valamint egy egyszerű elemből származó kód és információs bitek eredeti kombinációja polinom formájában A t (x).

Meg kell határozni a ciklikus kód megengedett kódkombinációját (és, Nak nek).

• 1. Az eredeti kódkombinációt polinomként ábrázoljuk A t (x). Az eredeti kódkombináció polinomját megszorozzuk ezzel x z: A t (x) x g. A generáló polinom foka G megegyezik az eredeti kódkombináció legjelentősebb számjegyének értékével.
• 2. Meghatározzuk azokat az ellenőrző biteket, amelyek kiegészítik az eredeti információkombinációt a megengedetthez, mint a generálás által az előző bekezdésben kapott szorzat felosztásának maradékát.

polinom:

A felosztás fennmaradó részét a következővel jelöljük R(x).

3. A ciklikus végül engedélyezett kódszava

kód = = És t (x)? x r + R(x).

A kapott kódkombináció hibáinak meghatározásához elegendő azt egy generáló polinomra felosztani. Ha az elfogadott kombináció megengedett, akkor az osztás maradéka nulla lesz. A nullától eltérő maradék azt jelzi, hogy a kapott kombináció hibákat tartalmaz. A maradék (szindróma) típusa szerint bizonyos esetekben a hiba jellegére és helyére is lehet következtetést levonni és a hibát kijavítani.

A hibaészlelési algoritmus a következő.

Legyen "-elem kombinációk ( n = k + t).

• 1. Feltárjuk a hiba meglétének tényét. A maradékot az elfogadott kombináció elosztásából kapjuk A n - (x) a generáló polinomhoz P(x): A(X)
• --- = Rq(x). Az egyensúly jelenléte R0(x) at (L 0 (x) f 0) tanúskodik P(x)

egy hibáról.

2. Osszuk el a kapott # (x) polinomot! = L„_,(X) 0 Rq (x) a generatrixon R g(h): W-1 = R(x), Ahol R(x)- aktuális egyenleg.

3. Hasonlítsa össze az LDx) és R(x). Ha egyenlők, akkor a hiba a legjelentősebb bitben történt. Ha nem, akkor növelje meg az elfogadott polinom mértékét x-szel, és osszon újra:

4. Hasonlítsa össze a kapott maradékot a Rq(x). Ha egyenlők, akkor a hiba a második bitben történt. Ha nem egyenlők, akkor szorozzuk meg Wx) x 2, és ismételjük ezeket a műveleteket, amíg meg nem kapjuk

R(x) = pokol.

A hiba a fokozat növelésének számának megfelelő kategóriában lesz Wh), plusz 1. Például egyenlőség esetén R(x)és LDh)

A legegyszerűbb c ciklikus kód lehetővé teszi az egyedi hibák és a páratlan többszörösségű hibák észlelését. Ennek a kódnak a generáló polinomja a következő alakú: A dekompozícióban szereplő irreducibilis polinomok közül ez a polinom a legkisebb fokú polinom, így tetszőleges számú információs bithez csak egy ellenőrző bit szükséges. Ennek a bitnek a szimbólumértéke biztosítja az egyesek számának paritását bármely engedélyezett kódkombinációban. Az így kapott ciklikus paritáskód nemcsak egybites hibákat képes észlelni, hanem bármilyen páratlan számú bitben előforduló hibákat is.

Példa. Ciklikus kód szerkesztése a számára Mivel a generáló polinom egy 1. fokú polinom, az ellenőrző számjegyek száma Ezért ciklikus kód létrehozásához generáló mátrixot készítünk

Egy további mátrix felépítéséhez megtaláljuk az egységtranszponált mátrix utolsó, nullákkal kitöltött sorának a kiválasztott polinommal való elosztásából származó maradékokat:

Így a további C, k mátrix alakja

Most felépítjük a generáló mátrixot

Ennek a mátrixnak a sorai a kód első három kombinációja. A többi megengedett kombinációt a mátrixsorok összes lehetséges kombinációjának modulo két összegzésével kaphatjuk meg, az eredményül kapott megsemmisített kódkombinációkat a táblázat tartalmazza. 39.

39. táblázat (lásd beolvasás)

Közismert érdekesség a következő legegyszerűbb kód megfontolása egy másodfokú irreducibilis polinom segítségével

A polinom által alkotott ciklikus kód generáló mátrixának általános nézete a két oszlopból álló további mátrix szerkezetében különbözik.

Könnyen belátható, hogy ha egy adott generáló polinommal osztunk, akkor a karakterláncokat kifejező monomiumok

identitásmátrix (egy további mátrix megtalálásához háromféle maradékot hozunk létre: 11, 01 és 10. Ezért a kapott -kód egyes kombinációinak súlya legalább kettő lesz. Bármely két kombináció közötti minimális kódtávolság is egyenlő kettővel. De a legegyszerűbb kód egy paritásellenőrzéssel, amelyet egy elsőfokú binomiális alkot. Azonban a két kód korrekciós képessége nem azonos.A szóban forgó kód nagy redundanciával rendelkezik, és nem csak a hibák észlelését teszi lehetővé. páratlan sokaság, hanem minden páros szomszédos hiba, valamint minden hiba, amelyet egy torzítatlan elem választ el.

6. Hibák javítása ciklikus kódokkal

A 3. részben megmutattuk, hogy egy helyesen vett kódszó dekódolásához, azaz a megfelelő információs szó megtalálásához elegendő a kapott kódszónak megfelelő polinomot elosztani a kód generáló polinomjával. Ha azonban hibák lépnek fel az átvitel során, akkor ezeket a hibákat ki kell javítani a dekódolási folyamat során.

Mivel a ciklikus kódok lineárisak, a hibafelismerési és -javítási folyamat a vett vektor szindrómájának megtalálásához kapcsolódik. Emlékezzünk vissza, hogy a vektor szindróma u a vektor és a kód transzponált ellenőrző mátrixának szorzataként kerül kiszámításra, azaz. s u= uH T. Ciklikus kód esetén a szindróma egyenlő a megfelelő polinomnak a kód generáló polinomjával való osztásának maradékával, ha az ellenőrző mátrix egy bizonyos módon van felépítve. Más szóval, ha g(x) egy generáló kódpolinom, majd a vektor-szindróma u egyenlő az osztás maradékával u(x) tovább g(x). Ha nem volt hiba, akkor a maradék, és így a kapott vektor szindróma 0.

A hibák kijavításához fel kell építenünk egy táblázatot, amelyben egy oszlopban minden lehetséges hibavektor megtalálható adott kódot korrigálni tudja, és a második oszlopban - a nekik megfelelő szindrómákat. Az összes sorkódra jellemző hibajavítás a következő lesz:

1. A kapott szóhoz megtaláljuk a kapott szónak megfelelő polinomiális szindrómát.

2. Ha a szindróma nem egyenlő 0-val, akkor a kapott szindróma (az osztásból származó maradék) alapján megtaláljuk a táblázatban a megfelelő hibavektort.

3. A kapott szót a modulo 2 hozzáadásával javítjuk a számított hibavektorral.

Az első lépés, amelyet úgy hajtunk végre, hogy a kapott szót megszorozzuk a transzponált ellenőrző mátrixszal, nagyon egyszerű ciklikus kódok esetén, ha a mátrix H a szisztematikus kód ellenőrző mátrixa. Ebben az esetben, j-a transzponált mátrix sora HT megfelel a polinom felosztásának maradékának x n -1- j a kód generáló polinomjával, és a szindróma egyenlő a kapott szónak megfelelő polinomnak a kód generáló polinomjával való osztásának maradékával.

Példa: Tekintsük a polinom által generált ciklikus (7,1)-kódot g(x) = x 6 + x 5 + x 4 + x 3 + x 2 + x+1. A kód két szóból áll: 0000000 és 1111111, és kijavítja a 3 vagy annál kevesebb hiba összes kombinációját. A generátorok mind 7 hosszúságú, 0, 1, 2 és 3 súlyú Boole-vektorok. Az ellenőrző mátrix a ( hányadossal) épül fel x+1) az osztályból x 7 +1 tovább x 6 + x 5 + x 4 + x 3 + x 2 + x+1 és úgy néz ki

Fogadjuk el az 11101101 szót, amely megfelel a polinomnak x 6 + x 5 + x 4 + x 2 + 1. Ennek a polinomnak a generáló kódpolinommal való elosztása után a maradék az x 3 + x. Közvetlen ellenőrzéssel meggyőződhetünk arról, hogy a vektor szorzásakor u= 1110101 transzponált mátrixonként HT, valamint a 0001010 vektor szorozásakor HT megkapjuk a 0001010 vektort, amely megfelel a polinomnak x 3 + x. A polinomnak megfelelő vektor x 3 + x, súlya 2, azaz a coset generátora. A kapott 11101101 vektort a 0001010 generátorral összeadva a 1111111 kódszót kapjuk, vagyis a hiba kijavításra kerül.

Lineáris kódoknál a különböző szindrómák száma 2 n - k, Ahol n-k- az ellenőrző karakterek száma. Ezért a nagy kódszóhosszúságú kódokhoz, azaz elegendő egy nagy szám ellenőrző szimbólumok esetén a szindrómák táblázata nagyon nagy, és sok időbe telik a hibavektor megtalálása. A táblázatban a ciklikus kódok sorainak számának csökkentése érdekében használhatja az ilyen kódok szigorú matematikai szerkezetét. A fő tétel a Megitt-tétel, amely kapcsolatot hoz létre egy vektor ciklikus eltolódásai és a kód generáló polinomjával való osztás utáni maradékai között.

6.1. Tétel. (Meggit). Hadd s- vektor szindróma u hossz n. Ciklikus vektorváltási szindróma u egybeesik a polinomnak megfelelő vektor szindrómával xs(x).

Példa: Tekintsük a (7,4) Hamming-kódot, amely a polinom által generált ciklikus kód g(x) = x 3 + x+ 1. Az 1011000 bináris vektor egy kódszó, mivel a megfelelő polinom x 6 + x 4 + x 3 osztható vele g(x). Tételezzük fel, hogy ennek a kódszónak az átvitele során egy hiba volt a megfelelő bitben x 4, és a szó elfogadásra kerül u= 1001000. Szindróma s a kapott vektor értéke 110, ami a polinomnak felel meg x 2 + x.

Tekintsük a vektor 0010001 ciklikus eltolását u. Ez megfelel a polinomnak x 4 + 1. Közvetlen ellenőrzéssel ellenőrizhető, hogy a polinom osztásának maradéka x 4 + 1 polinomonként x 3 + x+ 1 egyenlő x 2 + x+ 1, azaz a 0010001 vektor szindróma 111. A polinom felosztásának maradéka xs(x) = x 3 + x 2 on x 3 + x+ 1 is egyenlő x 2 + x + 1.

A Megitt-tételt használva csak a legjelentősebb bit hibáinak megfelelő hibavektor-szindrómák tárolhatók a szindrómatáblázatban. A hibajavítási eljárás a következő lépéseket tartalmazza:

1. A kapott vektor szindrómát úgy találjuk meg, hogy a megfelelő polinomot elosztjuk a generáló kódpolinommal. Ha a regiszterben szereplő osztás maradéka 0, akkor nem volt hiba, és az osztás hányadosa a szükséges információs szó. Ellenkező esetben a felosztás fennmaradó részét összehasonlítjuk a táblázatban szereplő összes szindrómával.

2. Ha a maradék egybeesett a táblázat valamelyik szindrómával, akkor a kapott szóhoz hozzáadjuk a megfelelő hibavektort, a kapott szót elosztjuk a kód generáló polinomjával; az osztás hányadosa a kívánt információs szó. Ha a maradék xs(x) nem egyezik a táblázatban szereplő szindrómák egyikével sem, szorozd meg s(x) tovább xés osszuk el a polinomot xs(x) a kód generáló polinomjához.

3. Végezze el a 2. lépést azutánig p a többi lépés nem egyezik a táblázatban szereplő egyik szindrómával. Ezt követően ciklikusan eltoljuk a megfelelő hibavektort p alkalommal adja hozzá a kapott vektort a kapott szóhoz, ossza el a kapott szót a kód generáló polinomjával; az osztás hányadosa a kívánt információs szó.

Példa: Tekintsük a polinom által generált ciklikus (7,4) Hamming-kódot g(x) = x 3 + x+ 1. A megfelelő dekódoló táblázat a szindrómákkal a következő.

és tegyük fel, hogy egy hiba történt a továbbított 0001011 kódszóban, azaz például a 0101011 szó érkezik, amelynek a polinom megfelel x 5 + x 3 + x+ 1. A polinom felosztásának maradéka x 5 + x 3 + x+ 1 generáló kódpolinomonként g(x) = x 3 + x+ 1 egyenlő x 2 + x+ 1, azaz a kapott vektor szindróma eltér 0-tól, és egyenlő 111-gyel. A táblázatban nincs ilyen szindróma, ezért a legjelentősebb bitben nincs hiba. Egy polinom szorzása x 2 + x+ 1, ami a 111-es szindrómának felel meg, tovább xés osszuk el a kapott polinomot x 3 + x 2 + x tovább g(x). Egy polinom felosztásának maradéka x 3 + x 2 + x tovább x 3 + x+ 1 egyenlő x 2 + 1, azaz a 101-es szindróma, amely a maradéknak felel meg, megegyezik a redukált dekódolási táblázatban szereplő szindrómával. Ennek megfelelően a szomszédos osztály 100000 generátorát egy bittel balra toljuk, és a 0100000 vett vektort hozzáadjuk a 0101011 vett vektorhoz. Ennek eredményeként a 0001011 szót kapjuk, amely a továbbított kódszó, azaz a hiba. javítani fogják.

Ez a dekóder egyszerűsíthető. Különösen, ha egy fogadott szót elforgatnak, sok javítható hibaminta többször előfordulhat. Ha ezen szindrómák egyikét eltávolítják, akkor a megfelelő ciklikus eltolással a hiba továbbra is megtalálható. Ezért minden ilyen pár esetében elegendő csak egy szindrómát megjegyezni.