A ciklikus előtag hasznos információkat tartalmaz-e. Ciklikus kódok

A ciklikus kódokat azért nevezik el, mert bennük a kódkombinációk egy része vagy az összes kombináció elérhető egy vagy több kódkombináció ciklikus eltolásával. A ciklikus váltás jobbról balra történik, és a bal szélső karakter minden alkalommal a kombináció végére kerül. A ciklikus kódok gyakorlatilag mind szisztematikus kódokra utalnak, bennük a vezérlő és információs számjegyek szigorúan meghatározott helyeken helyezkednek el. Ezenkívül a kódokat blokk kódokként osztályozzák. Minden blokk (egy betű egy blokk speciális esete) függetlenül van kódolva.

A ciklikus kódok felépítésének gondolata a bináris számok területén redukálhatatlan polinomok használatán alapul. Nem csökkenthető olyan polinomokat nevezünk, amelyek nem ábrázolhatók alacsonyabb fokú polinomok szorzataként ugyanazon mező együtthatóival, mint ahogy a prímszámok sem ábrázolhatók más számok szorzatával. Más szavakkal, a redukálhatatlan polinomok maradék nélkül csak önmagukkal vagy egységgel oszthatók meg.

A redukálhatatlan polinomok a ciklikus kódok elméletében a polinomok generátorainak szerepét töltik be. Ha az adott kódkombinációt megszorozzuk a kiválasztott redukálhatatlan polinommal, akkor kapunk egy ciklikus kódot, amelynek korrekciós képességeit a redukálhatatlan polinom határozza meg.

Tegyük fel, hogy a négyjegyű kombinációk egyikét szeretné kódolni bináris kód... Tegyük fel azt is, hogy ez a kombináció G (x) = x 3 + x 2 + 1 ® 1011. Bár nem támasztjuk alá választásunkat, az irreducibilis polinomok táblázatából generáló polinomként veszünk P (x) = x 3 + x + 1 ® 1011. Akkor megszaporodunk G (x) a generáló polinommal azonos fokú monomállal. Attól kezdve, hogy megszorozzuk a polinomot egy fokozat monomállal n az egyes terminusok foka a polinomban nő n, ami egyenértékű a hozzárendeléssel n nulla a polinom legkevésbé jelentős bitjeinek oldalán. Mivel a kiválasztott redukálhatatlan polinom foka egyenlő hárommal, az eredeti információkombinációt három fokos monommal szorozzuk meg

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

Ez úgy történik, hogy később ezeknek a nulláknak a helyén javítási számjegyeket lehessen írni.

A javító számjegyek értéke a felosztás eredményeiből származik G (x) x n a 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

Ily módon

vagy általában

Hol Q (x)¾ privát, és R (x)¾ az osztás fennmaradó része G (x) × x n a P (x).

Mivel a bináris aritmetikában 1 Å 1 = 0, ami -1 = 1-et jelent, bináris számok összeadásakor lehetőség van a fogalmak egyik részről a másikra való átvitelére a jel megváltoztatása nélkül (ha ez kényelmes), ezért egyenlőség a nyomtatvány a Å b = 0 felírható a = b, És hogyan a - b = 0. Mindhárom egyenlőség ebben az esetben azt is jelenti aés b egyenlő 0-val, vagy aés b egyenlőek 1-vel, azaz ugyanolyan paritással rendelkezik.

Így az (5.1) kifejezés így írható

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

ami példánk esetében megadja

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.

Az 1101001 polinom a kívánt kombináció, ahol az 1101 információs rész, a 001 pedig vezérlő karakter. Megjegyezzük, hogy a kívánt kombinációt mind a teljes négyjegyű bináris kód (ebben az esetben 1111) kombinációinak egyikének a generátor polinommal való megszorzásának, mind az adott kombináció azonos fokú monomális szorzatának eredményeként kapnánk meg. mint választott generátor polinom (esetünkben így nyertük az 1101000 kombinációt), majd a kapott termékhez hozzáadtuk a terméknek a generáló polinommal való felosztásának fennmaradó részét (példánkban a maradék alakja 001 ).

És itt a meghatározó szerepet a generáló polinom tulajdonságai töltik be P (x)... A ciklikus kód felépítésének módja olyan, hogy a generátor polinomja részt vesz az egyes kódkombinációk kialakításában, ezért a ciklikus kód bármely polinomját a generátor osztja fel maradék nélkül. De csak azok a polinomok, amelyek tartoznak ezt a kódot, vagyis a generáló polinom lehetővé teszi, hogy az összes lehetséges kombináció közül kiválaszthassa a megengedett kombinációkat. Ha a ciklikus kód generáló polinommal való elosztásakor maradékot kapunk, akkor vagy hiba történt a kódban, vagy valamilyen más kód kombinációja (tiltott kombináció). A fennmaradó részen egy tiltott kombináció jelenlétét észlelik, vagyis hibát észlelnek. A polinomok felosztásából származó maradványok a ciklikus kódok hibafelismerői.

Másrészről, a maradékokat, ha osztunk egyet nullákkal a generáló polinommal, felhasználjuk ciklikus kódok felépítésére.

Amikor nullával osztunk egyet egy generáló polinommal, emlékeztetni kell arra, hogy a maradék hossza nem lehet kevesebb, mint az ellenőrző számjegyek száma, ezért a maradék számjegyhiánya esetén a szükséges nullák száma a maradéktól jobbra rendelt.

01100 11111+

a nyolcadiktól kezdve a maradékokat megismételjük.

Az osztásból származó maradékokat generáló mátrixok létrehozására használják, amelyeket a derivált kombinációk előállításának egyértelműsége és kényelme miatt széles körben alkalmaznak ciklikus kódok létrehozására. A generátormátrix felépítése egy átültetett egység és egy további mátrix összeállítására redukálódik, amelynek elemei a maradványai annak, ha osztunk egyet nullával a generáló polinommal P (x)... Emlékezzünk arra, hogy az átültetett identitásmátrix egy négyzetmátrix, amelynek minden eleme nulla, kivéve azokat az elemeket, amelyek átlósan helyezkednek el jobbról balra fentről lefelé (egy nem transzponált mátrixban az azonosító elemekkel átlós balról jobbra fentről lefelé). A kiegészítő mátrix elemei az identitás transzponált mátrix jobb oldalán vannak kijelölve. Csak azok a maradékok, amelyek súlya W ³ d 0- 1, ahol d 0 A minimális kódtávolság. A maradékok hosszának legalább az ellenőrző bitek számának kell lennie, a maradékok számának pedig meg kell egyeznie az információs bitek számával.

A generáló mátrix sorai az első kombinációk forráskód... A kód többi kombinációját a modulo 2 összesítő összesítésének eredményeként kapjuk meg a generáló mátrix összes lehetséges kombinációját.

Példa.

Készítsen egy ciklikus kód teljes generáló mátrixát, amely minden egyes és kettős hibát észlel, amikor 10 bites bináris kombinációkat továbbít.

Döntés.

Az 5.12. Táblázat szerint válassza ki a legközelebbi értéket k ³ 10.

5.12. Táblázat - Az információk és az ellenőrző karakterek közötti kapcsolat egy legfeljebb 16 bites kódhoz

n	k	ρ	n	k	ρ

A táblázat szerint ez az érték lesz k = 11, míg r = 4, de

n = 15. A generátor polinomját is megválasztjuk x 4 + x 3 +1.

A teljes generáló mátrix az egységbe transzponált mátrixból épül fel kanonikus formában és egy további mátrixból, amely megfelel az ellenőrző számjegyeknek.

Átültetni a mátrixot a k = A 11. néz ki:

Egy további mátrix felépíthető a kombináció maradék részének felosztásából a nullával rendelkező kombináció formájában (az átültetett azonosság utolsó sora) a kiválasztott generáló polinommal.

A teljes generátor mátrix így fog kinézni:

A mátrixok előállításának fenti módszere nem az egyetlen. A generátor mátrix az identitás mátrix elemeinek a generátor polinommal történő közvetlen szorzásának eredményeként konstruálható. Ez gyakran kényelmesebb, mint megtalálni az osztás fennmaradó részét. Az így kapott kódok semmiben sem különböznek azoktól a kódoktól, amelyek mátrixok generálásából épülnek fel, amelyekben a kiegészítő mátrix abból áll, hogy fennmarad a nullával való elosztás a generáló polinommal.

A generáló mátrix ugyanúgy konstruálható a kombináció ciklikus eltolásával, amelyet a rangú azonossági mátrix sorának szorzása eredményez. k a generátor polinomján.

A ciklikus kódok hibáit a fennmaradó részek segítségével észlelhetjük, ha a kapott kombinációt elosztjuk a generáló polinommal. A felosztás többi része hibaazonosító, de nem közvetlenül jelzi a hiba helyét a ciklikus kódban.

A hibajavítás gondolata azon a tényen alapul, hogy a hibás kombináció bizonyos számú ciklikus eltolódás után úgy van „illesztve” a maradékra, hogy a maradékkal együtt megadja a javított kódszót. A fennmaradó rész ebben az esetben nem más, mint a torz és helyes szimbólumok közötti különbség, a fennmaradó egységek pontosan a torzított bitek helyén állnak a kombinációban, ciklikus eltolásokkal igazítva. A torzított kombinációt addig módosítják, amíg a fennmaradó részek száma meg nem egyezik a kód hibáinak számával. Ebben az esetben természetesen az egyesek száma megegyezhet a hibák számával s, javítva ezzel a kóddal (a kód 3 hibát és 3 hibát torz kombinációban javít), vagy kevesebbet s(a kód kijavít 3 hibát, és az elfogadott kombinációban 1 hibát).

A hiba helye a kódkombinációban nem számít. Ha egy k³ (n / 2), akkor bizonyos eltolódások után minden hiba a generáló polinom „egyszeri” műveletének zónájában lesz, vagyis elegendő egy maradékot megszerezni, amelynek súlya W £ s, és ez már elég lesz a torz kombináció kijavításához.

A hibajavítási folyamatot az alábbiakban részletesen tárgyaljuk az építési kódok példáival.

Ez egy olyan lineáris kódok egy alosztálya, amelyeknek az a tulajdonsága, hogy a kódolt blokkban a szimbólumok ciklikus permutációja ugyanazon kód egy másik lehetséges kódolt blokkját eredményezi. A ciklikus kódok a Galois-mezők algebrai elméletéből származó ötletek alkalmazásán alapulnak.

Számos legfontosabb kommunikációs rendszer zavarásgátló kódja, -

különösen ciklikus, a véges számtan szerkezetein alapul

Galois mezők. A mező mellett nevezzük azon elemek halmazának, amelyek véges mezők

a műveletek neve idézőjelben szerepel, mert nem mindig általánosan elfogadott számtani műveletek. A mező mindig tartalmaz nulla elemet (0) vagy nulla, és egy elemet (1), vagy egyet. Ha a szám q a mező elemei korlátozottak, akkor a mezőt meghívjuk véges mező, vagy véges Galois-mező, és jelölve GF (q) y Hol q - terepi rend. A legkisebb Galois-mező a kételemes iole GF ( 2), csak két elemből áll 1 és 0. Annak érdekében

1 Evariste Galois (1811 - 1832) - francia matematikus, megalapozta a modern algebrát.

elemekkel végzett műveletek GF ( 2) nem vezettek ezen a mezőn túllépéshez, modulo 2-t hajtanak végre (általában ezt a mező sorrendje határozza meg egyszerű Galois-mezők).

A mező számos speciális matematikai tulajdonsággal rendelkezik. A mezőelemek esetében összeadási és szorzási műveletek vannak meghatározva, és ezeknek a műveleteknek ugyanahhoz a halmazhoz kell tartoznia.

Az összeadási és szorzási műveleteknél a szokásos matematikai asszociativitási szabályokat követik - de + (B + c) = (a + B)+ c, kommutálhatóság - a + b = b + aés de b = b deés terjesztés - de (B+ s) = de b + de tól től.

A mező minden eleméhez de inverz összeadásnak léteznie kell (-de)és ha de nem nulla, inverz szorzótag (th ').

A mezőnek tartalmaznia kell adalék egység - 0 elem olyan, hogy de + 0 = de bármely mezőelemre de.

A mezőnek tartalmaznia kell szorzó egység - 1. elem olyan, hogy aL = a bármely mezőelemre de.

Például vannak mezők valós számok, racionális számok, komplex számok. Ezek a mezők végtelen számú elemet tartalmaznak.

Valójában a kódszó ciklikus permutációjával létrehozott összes halmaz kódszó is. Tehát például az 1000101 kombináció ciklikus permutációi szintén kódkombinációk lesznek: 0001011, 0010110, 0101100 stb. Ez a tulajdonság lehetővé teszi a kódoló és a dekóder jelentős egyszerűsítését, különösen a hibák észlelésekor és egyetlen hiba kijavításakor. A ciklikus kódokra való figyelem abból adódik, hogy a bennük rejlő magas korrekciós tulajdonságok viszonylag egyszerű algebrai módszerek alapján valósulnak meg. Ugyanakkor egy tetszőleges lineáris blokk kód dekódolásához gyakran táblázatos módszereket alkalmaznak, amelyek nagy mennyiségű dekóder memóriát igényelnek.

A ciklikus kódot lineáris blokknak nevezzük (n, k) - kód, amely ciklikus, azaz bármely megengedett kódszó egylépéses bal eltolása szintén megengedi a megengedettet kódszó ugyanahhoz a kódhoz tartozó, és amelyben a kódszavak halmazát fokú polinomok halmaza képviseli (P- 1) vagy kevésbé osztható a generáló polinommal g (x) fokozat r = n-k y binomiális x n +

Ciklikus kódban a kódszavakat polinomok (polinomok) képviselik

Hol P - kód hossza; A i - Galois mező-együtthatók (kódkombinációs értékek).

Például a 101101 kódkombináció esetében a polinom jelölésnek formája van

A ciklikus kódokra példák a páros ellenőrző kódok, az ismétlődési kódok, a Hamming-kódok, a PC-kódok és a turbókódok.

Hamming-kód... A Hamming-kód hibajavítási képességei a minimális kódolási távolsághoz vannak társítva d 0. Minden multiplicitási hiba javítva van q= cnt (d 0- l) / 2 (itt a cnt jelentése "egész rész") és a multiplicitási hibákat észlelik d 0 - 1. Tehát, ha ellenőrizzük a furcsaságot d Q = 2 és egyetlen hibát észlelnek. A Hamming-kódban d 0 = 3. Az információs számjegyeken kívül a L = log 2 Q redundáns vezérlőbit, ahol Q - az információs bitek száma. Paraméter L a legközelebbi nagyobb egész számra kerekítve. Az L-bites vezérlőkód annak az információ-bitnek a számához tartozó bit bitenkénti összeadásának (modulo 2 összeadás) fordított eredménye, amelyek értéke egyenlő.

7.7. Példa

Tegyük fel, hogy megvan a 100110 fő kód, azaz Q = 6. Adjunk meg egy további kódot.

Döntés

Megtaláljuk L= 3 és a kiegészítő kód:

ahol P a bitenkénti összeadási művelet szimbóluma, és invertálás után 000-vel rendelkezünk. Most a kiegészítő kódot továbbítjuk a fő kóddal. A vevőnél a kiegészítő kódot újra kiszámítják és összehasonlítják az átvitt kóddal. Az összehasonlító kód rögzített, és ha különbözik a nullától, akkor az értéke a hibásan vett főkód bitjeinek száma. Tehát, ha az 100010 kódot kapjuk, akkor a kiszámított kiegészítő kód megegyezik a 010SH10 = 100 inverzióval, azaz 011, ami hibát jelent a 3. számjegyből.

A Hamming-kódok általánosítása ciklikus BCH-kódok, amelyek lehetővé teszik a fogadott kódszó több hibájának kijavítását.

Reed - Salamon kódok Galois mezőkön vagy záró nullákon alapulnak. Az aritmetikai műveletek az összeadás, kivonás, szorzás, osztás stb. a lemaradó nulla elemei felett olyan eredményt kapunk, amely szintén ennek a nulla egyik eleme. Ezeket a műveleteket egy Reed-Salamon kódolónak vagy dekódolónak kell végrehajtania. A kód végrehajtásához szükséges összes művelet megköveteli különleges felszerelés vagy speciális szoftver.

Turbókódok. A redundáns kódok mind önállóan, mind több kód valamilyen kombinációjaként használhatók, amikor egy redundáns kód szimbólumkészleteit egy másik redundáns kód elemi információs szimbólumának tekintjük. Ilyen uniót kezdtek hívni lépcsőzetes kód. A összefűzött kódok hatalmas előnye, hogy használatuk lehetővé teszi a kódoló és különösen a dekóder egyszerűsítését az azonos hosszúságú és redundanciájú nem összefűzött kódok hasonló eszközeivel szemben. Az összefűzött kódolás turbókódok létrehozásához vezetett. Turbocode párhuzamos jelszerkezetnek nevezzük, amely kettőből vagy több szisztematikus kódok. Felépítésük alapelve több párhuzamosan működő komponens kódoló használata. Komponensként használhat mind blokk-, mind konvolúciós kódokat, Hamming-kódokat, PC-kódokat, BCH-kat stb. A perforáció (lyukasztás) lehetővé teszi a turbo-kód relatív sebességének növelését, korrekciós képességének hozzáigazítását a kód statisztikai jellemzőihez. kommunikációs csatorna. A turbókód kialakításának elve a következő: bemeneti jel x, a következőket tartalmazza NAK NEK bit, párhuzamosan táplálva N közbeiktatók. Ez utóbbiak mindegyike olyan eszköz, amely az elemeket áthatja egy blokkban NAK NEK bitek véletlenszerű sorrendben. Az interleaverek kimeneti jele - az átrendezett szimbólumok - a megfelelő elemi kódolókhoz kerül. Bináris szekvenciák x p i= 1,2, ..., JV, a kódoló kimenetén ellenőrző szimbólumok vannak, amelyek az információs bitekkel együtt egyetlen kódszót alkotnak. Az összeszövő használata lehetővé teszi a korrelált hibák megjelenését a turbókódok dekódolásakor, ami fontos a feldolgozás során hagyományos visszatérő dekódolási módszer alkalmazásakor. Az alkatrészkód választásától függően a turbókódok konvolúciós turbókódokra és blokktermék-kódokra vannak felosztva.

A ciklikus kódok egyfajta lineáris csoportkódok, és szisztematikus kódokként vannak besorolva. Eredetileg a dekódolási eljárások egyszerűsítése céljából hozták létre. Az ilyen kódok hibájának felderítésében mutatott nagy hatékonyság azonban biztosította széleskörű alkalmazását a gyakorlatban. Kényelmes egy ciklikus kód bináris vektorát nem nullák és egyek kombinációjának tekinteni, hanem bizonyos fokú polinomnak

ahol x a számrendszer alapja, az eset halmazához tartozó együtthatók kettes számrendszer leszámolás.

Példa. A bináris vektor polinomként ábrázolható az alábbiak szerint:

A bináris vektorok polinomok formájában történő ábrázolása lehetővé teszi, hogy a vektorokon végzett műveletet a polinomokra visszavezetjük. Ahol:

a polinomok hozzáadása a változó egyenlő hatványaihoz tartozó együtthatók modulo 2 összegére csökken

a szorzást a teljesítményfüggvények szorzásának szokásos szabálya szerint hajtjuk végre, azonban a kapott együtthatókat egy adott fokhoz hozzáadjuk modulo 2-vel;

az osztást a teljesítményfüggvények felosztásának szabályai szerint hajtják végre, míg a kivonási műveletet a modulo 2 összegzés váltja fel.

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

Keresse meg a polinomok szorzatát

Oszd meg a polinomokat

A ciklikus kódok fő tulajdonsága a következő: ha egy vektor ciklikus kódhoz tartozik, akkor bármelyik vektor, amelyet az adottból ciklikus eltolásokkal kapunk, szintén a ciklikus kódhoz tartozik.

A ciklikus kódok felépítésének gondolata egy redukálhatatlan polinom koncepcióján alapszik. A polinomot akkor lehet nem redukálhatónak tekinteni, ha csak önmagával és egyével osztható, és nem osztható egyetlen más polinommal sem. Más szavakkal, egy redukálhatatlan polinom nem ábrázolható alacsonyabb fokú polinomok szorzataként. A polinom osztható egy nem redukálható polinommal, maradék nélkül. A ciklikus kódok elméletében az irreducibilis polinomok játszják a polinomgenerátorok szerepét. A különböző fokú irreducibilis polinomok típusait a

Példák irreducibilis polinomokra:

A ciklikus kód vektorokat a következő szabályok szerint építjük fel. Legyen bármely természetes kód bármely bináris vektora; fokozatú monomális, fokozatú redukálhatatlan polinom. Ezután a ciklikus kód bármelyik vektora létrejön a reláció segítségével

hol van a felosztás hátralévő része

Így a ciklikus kódok bármelyik vektorát úgy lehet létrehozni, hogy a természetes bináris kód egyes vektorait megszorozzuk egy fokú monomállal, az osztás fennmaradó részének hozzáadásával a kapott termékhez. Ha ilyen módon építünk ciklikus kódokat, Az információs bitek száma minden kódvektorban szigorúan rendezett - ezek foglalják el a kódvektor legjelentősebb bitjeit, és a többi számjegy ellenőrzi.

Példa. A természetes bináris kód vektorának ciklikus kódvektor létrehozása van egy négerből, feltéve, hogy a generáló polinom formája

A vektort polinomként képviseljük

A polinomnak a polinommal való elosztásának eredményeként megkapjuk a maradékot. ebből kifolyólag

A ciklikus kód, mint bármely szisztematikus kód, kényelmesen megadható mátrix formában egy generáló mátrix felhasználásával

hol van a formátum transzponált egységmátrixa - az osztás fennmaradó része által alkotott ellenőrző számjegyek mátrixa

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

Nyilvánvaló, hogy a generáló mátrix üres formája

A mátrix ellenőrző bitjeinek sorainak megtalálásához kiszámítjuk és polinom formájában megírjuk az identitásmátrix minden vektorát

A ciklikus kód vektor hossza tehát

(lásd beolvasás)

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

A ciklikus kód bármelyik vektorát létrehozó mátrixának vektorainak mod összegeként kapjuk meg. Mivel a ciklikus kód egy csoportkód, a nulla vektor mindig a ciklikus kódhoz tartozik, mint a csoport egysége "

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 található. 13.5.

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

Például a ciklikus kódot a generátor mátrixa adja

Húzza ki balról az utolsó hat sort és az első hat oszlopot. Megkapjuk a generáló mátrixot

A vett kód jellemzői (hibadetektálás szempontjából) megegyeznek a generáló mátrix által képviselt ciklikus kód jellemzőivel

A megadott paraméterekkel rendelkező ciklikus kódok létrehozása egy generálható redukálhatatlan polinom megválasztásával jár együtt. A generáló polinom kiválasztása a következő feltétel alapján történik: a polinom mértékének 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, valamint egy adott detektáló és korrigáló képesség ciklikus kódjának elkészítésével.

1. Mivel a ciklikus kód ereje meg van adva, annak információbitjeinek számát a képlet alapján határozzuk meg

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

3. A kézikönyvek megtalálják az összes redukálhatatlan fokú polinomot

4. A fokozat egyik nem vezető polinomjának (a terminusok maximális számával rendelkező polinomot kell választani) a ciklikus kódot generáló mátrixot alkotják. Minden kódvektort a képlet kiszámít

hol van a generáló mátrix információs vektorának polinomja; - fokozat monomálisa - az osztás fennmaradó része

5. A felépített generáló mátrixot a következő feltételekkel ellenőrizzük:

a) a generáló mátrix bármely vektorának Hamming-értelemben vett súlyának meg kell felelnie annak a kapcsolatnak, ahol a vizsgált ciklikus kód Hamming-értelemben vett legkisebb távolsága van;

b) az ellenőrző vektor Hamming értelmében vett tömegének, amely a generáló mátrix bármely két ellenőrző vektorának modulo 2 összege, meg kell felelnie az összefüggésnek

6. Ha a ciklikus kód generáló mátrixa megfelel a fenti feltételeknek, akkor a ciklikus kód összes vektorát kiírják és meghatározzák a lineáris csoportkódokra jól ismert szabályok szerint. Ha a kód nem felel meg a követelményeknek, akkor egy másik azonos fokú generátorpolinomot választunk, és a ciklusos kód előállításának eljárását megismételjük egy új polinom esetében.

Készítsünk egy ciklikus kódot, amelynek teljesítménye 16 és korrekciós kód

Mert mi határozzuk meg az értéket

3 »A referenciakönyvek segítségével minden redukálhatatlan fokú polinomot találunk. Két ilyen polinom létezik:

4. Generátorként a polinomot választjuk, a ciklikus kódot létrehozó mátrix blankja formájú

A mátrix minden információs vektorát polinom képviseli

Határozza meg teljesen a generáló mátrix összes vektorát a képlet segítségével

A ciklikus kód vektor hossza óta (lásd akkor a generáló mátrix formátumát

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

13.6. Táblázat

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

5. A kapott generáló mátrix minden szükséges feltételnek megfelel. Ezért teljesen elkészítjük a ciklikus kódot (13.6. Táblázat). A táblázatból következik, hogy a kód megfelel, vagyis kielégíti a probléma követelményeit.

Megjegyzések. Ha nem redukálható polinomot használunk generátorként, akkor egy olyan kódot kapunk, amely a probléma követelményeinek is megfelel. Generáló mátrixának formája van

A ciklikus kódok segítségével történő hibadetektálás a következőképpen történik. A ciklikus kód bármelyik vektora osztható a generáló polinommal maradék nélkül. Ezért a ciklikus kódvektorban való hiba jelenlétének kritériuma egy nem nulla maradvány megjelenése, miután elosztjuk a ciklikus kódvektort a generáló polinommal. A nem nulla maradék hibát azonosít 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 el a kapott kódvektort a generáló polinommal.

Ha az egységek száma nem haladja meg a kód korrekciós képességét, adjuk hozzá a kapott modulo 2 vektort a kapott maradékkal. Az összegzés eredménye megadja a javított kódvektort. Ha a fennmaradó egységek száma nagyobb, mint a kód korrekciós képessége, akkor hajtsa végre a torzított vektor ciklikus eltolását balra egy bittel, majd ossza el a generáló polinommal. Ha az eredményül kapott maradék nem tartalmaz többet, mint a ciklikus kód korrekciós képessége, akkor a maradékkal adjuk hozzá a ciklikusan eltolt vektort. Tegye ciklikusan az összeadási eredményt egy kicsit jobbra. Az így kapott vektor már nem tartalmaz hibákat, és ciklikus kódvektor.

3. Ha az első ciklusos eltolás és az azt követő osztás után a maradék többet tartalmaz, mint a kód korrekciós képessége, akkor ismételje meg az algoritmus eljárását, amíg egy maradékot nem kapunk, a számok száma nem haladja meg a kód javító képességét. Ebben az esetben az utolsó ciklikus eltolódás eredményét hozzáadjuk a maradékhoz, és a kapott vektort ciklikusan annyi bittel toljuk jobbra, amennyire az eredeti hibával kapott vektort balra toljuk. Az eredmény egy javított kódvektor.

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

A kód értéke 3, vagyis kijavítja a multiplicitási hibákat .. Vegyük a 0011101 vektort a 0001101 vektor helyett. A hiba kijavításához hajtsa végre a következő műveleteket. A kapott vektort polinomként írjuk: akkor osztjuk fel

Az osztás eredményeként kapott maradék háromat tartalmaz, ami több, mint a kód javító képessége. Ezért egy ciklikus bal eltolást hajtunk végre a vett kódvektor egy bitjével. Ennek eredményeként megvan

Felosztást végzünk

Az így kapott maradék két egységet tartalmaz, ami több, mint a kód javító képessége. Ezért egy újabb ciklikus bal eltolást hajtunk végre a vett kódvektor egyik bitjével. Ennek eredményeként megvan

Felosztást végzünk

Az így kapott maradék ismét kettőt tartalmaz, tehát egy ciklikus elmozdulást hajtunk végre balra egy számjeggyel, és megkapjuk a

BELORUSSZIA ÁLLAMI INFORMATIKAI ÉS RÁDIÓ ELEKTRONIKAI EGYETEM

RES osztály

absztrakt a témáról:

„Ciklikus kódok. BChH kódok "

MINSK, 2009

Ciklikus kódok

A ciklikus kód egy lineáris blokk (n, k) -kód, amelyet a ciklikus tulajdonság jellemez, azaz bármely megengedett kódszó balra tolása egy lépésben megad egy megengedett kódszót, amely ugyanahhoz a kódhoz tartozik, és amelyben a kódszavak halmazát egy (n-1) fokú és annál kisebb polinom halmaz képviseli, amely osztható valamilyen g ( x) r = nk fokozat, amely az xn +1 binomiál tényezője.

A g (x) polinomot generálónak nevezzük.

A definícióból következően egy ciklikus kódban a kódszavak polinomként vannak ábrázolva

ahol n a kód hossza; a GF (q) mező együtthatói.

Ha a kód a GF (2) mező fölé épül, akkor az együtthatók 0 vagy 1 értéket vesznek fel, és a kódot binárisnak hívják.
Példa. Ha a ciklikus kódszó

akkor a megfelelő polinom

Például, ha a kódot a GF (q) = GF (2 3) mező fölé építjük, amely a GF (2) modulo kiterjesztése, az f (z) = z 3 + z + 1 redukálhatatlan polinom és az elemek ennek a mezőnek az 1. táblázatban bemutatott formája van,

akkor az együtthatók

vegye fel ennek a mezőnek az elemeit, és ezért ők maguk a következő alak polinomjaiként jelennek meg
ahol m a GF (2) mező kiterjesztésének megszerzéséhez használt polinom mértéke; a i - a GF (2) elemeinek értékét felvevő együtthatók, azaz 0 és 1. Egy ilyen kódot qth-nak nevezünk.

A ciklikus kód hosszát primitívnek, magát a kódot pedig primitívnek nevezzük, ha hossza n = q m -1 a GF (q) -on.

Ha a kód hossza kisebb, mint a primitív kód hossza, akkor a kódot csonkának vagy nem primitívnek nevezzük.

A definícióból következik köztulajdon A ciklikus kód kódszavainak megoszlása ​​maradék nélkül valamilyen g (x) polinommal, amelyet generátornak nevezünk.

Az x n +1 binomiál g (x) polinommal való elosztásának eredménye a h (x) ellenőrző polinom.

A ciklikus kódok dekódolásakor az e (x) hibapolimont és az szindróma S (x) polinomot használjuk.

Legfeljebb a fok (n-1) hiba polinomját a kifejezés alapján határozzuk meg

hol vannak a fogadott (hibával) és a továbbított kódszavakat képviselő polinomok.

Az e (x) -ben szereplő nulla együtthatók elfoglalják a hibának megfelelő pozíciókat.

Példa.

A ciklikus kód dekódolásakor használt szindrómás polinomot úgy definiáljuk, mint a fennmaradó részt, amikor a vett kódszót elosztjuk a generáló polinommal, azaz

vagy

Következésképpen a szindrómás polinom közvetlenül függ az e (x) hibapolinomtól. Ezt a pozíciót használjuk a dekódolási folyamatban használt szindrómák táblázatának összeállításához. Ez a táblázat tartalmazza a hiba polinomok listáját és a kifejezésből meghatározott megfelelő szindrómák listáját

(lásd a 2. táblázatot).

A dekódolás során a szindrómát a kapott kódszóból számoljuk ki, majd a megfelelő e (x) polinom megtalálható a táblázatban, amelynek összegzése a vett kódszóval a javított kódszót, azaz.

A felsorolt ​​polinomok összeadhatók, szorozhatók és eloszthatók az algebra jól ismert szabályai szerint, de az eredmény csökkentésével mod 2, majd mod xn +1, ha az eredmény mértéke meghaladja az (n-1) fokot .

Tegyük fel, hogy a kód hossza n = 7, akkor az eredmény mod x 7 +1.

A ciklikus kódok konstruálásakor és dekódolásakor a polinomok felosztása eredményeként általában nem az osztás, hanem a maradék része szükséges.
Ezért egyszerűbb osztási módszert ajánlunk, amely nem polinomokat, hanem csak annak együtthatóit használja (a példában a 2. lehetőség).

Példa.

A kódok mátrix hozzárendelése

A ciklikus kódot a generátor és a paritásmátrixok adhatják meg. Megalkotásukhoz elég a g (x) generátor és a h (x) ellenőrző polinom ismerete. Egy nem szisztematikus ciklikus kód esetében a mátrixokat a generátor és az ellenőrző polinomok ciklikus eltolásával építjük fel, azaz szorozva őket x-szel

és

A H (n, k) mátrix felépítésekor a h (x) polinom vezető együtthatója a jobb oldalon helyezkedik el.

Példa. A generáló g (x) = x 3 + x + 1 polinomot tartalmazó ciklikus (7,4) kód esetén a G (n, k) és H (n, k) mátrixok formája:

Hol

Szisztematikus ciklikus kód esetén a G (n, k) mátrixot a kifejezés alapján határozzuk meg

ahol I k az identitásmátrix; R k, r téglalap alakú mátrix. Az R k, r mátrix sorait a kifejezések alapján határozzuk meg, vagy ahol a i (x) az I k mátrix i-edik sorának értéke; i az R k, r mátrix sorszáma.

Példa. A generáló g (x) = x 3 + x + 1 polinom alapján a (7,4) -kód G (n, k) mátrixát a következő sorrendben állítjuk össze

vagy

Határozzuk meg az R 4,3 alkalmazását

mint

Hasonló módon,

A legegyszerűbb ciklikus kód lehetővé teszi az egyes hibák és a páratlan sokaságú hibák detektálását. Ennek a kódnak a generáló polinomja a következő formában van: A bővítésben szereplő redukálhatatlan polinomok közül ez a polinom a legkisebb fokú polinom, így tetszőleges számú információ bithez csak egy ellenőrző bitre van szükség. A bit karakterének értéke biztosítja az engedélyezett kódkombinációk számainak paritását. Az így kapott ciklikus paritásellenőrző kód nemcsak az egyes bitek egyetlen hibáit, hanem bármilyen páratlan számú bit hibáit is képes felismerni.

Példa. Ciklikus kód szerkesztése a Mivel a generáló polinom 1. fokú polinom, az ellenőrző bitek száma Következésképpen, A ciklikus kód felépítéséhez létrehozunk egy generáló mátrixot

Egy további mátrix elkészítéséhez meg kell találni a maradékokat, ha az egység transzponált mátrix nullákkal párnázott utolsó sorát elosztjuk a kiválasztott polinommal:

Így a további C, k mátrixnak formája van

Most elkészítjük a generáló mátrixot

Ennek a mátrixnak a vonalai az első három kódkombináció. A többi megengedett kombináció úgy érhető el, hogy a mátrixsorok összes lehetséges kombinációjából a modulo kettőt összegezzük. 39.

39. táblázat (lásd a beolvasást)

Ismert érdeklődés a következő legegyszerűbb kód figyelembe vétele a másodfokú irreducibilis polinomból

Általános forma A polinom által létrehozott ciklikus kód generáló mátrixa különbözik a két oszlopot tartalmazó további mátrix felépítésében.

Könnyű ellenőrizni, hogy egy adott generátorral elosztva a sorokat kifejező monomák polinomja

az identitásmátrix (egy további mátrix megtalálásához háromféle maradvány képződik: 11, 01 és 10. Ezért a kapott kód minden egyes kombinációjának súlya legalább kettő lesz. A két kombináció közötti minimális kódtávolság kettő is. De a legegyszerűbb kód egy paritásellenőrzéssel, amelyet egy első fokú binomiál alkot. Mindkét kód korrekciós képessége nem azonos. A figyelembe vett kód nagy redundanciával rendelkezik, és lehetővé teszi nemcsak a páratlan sokaságú hibák észlelését , hanem minden párosított szomszédos hibát, valamint az összes hibát, amelyet egy torzítatlan elem választ el.