itthon Összeg. műveltség Nyelvképzés oktatási és módszertani központja avtf kts. Ciklikus kódolási folyamat Ciklikus kód

Nyelvképzés oktatási és módszertani központja avtf kts. Ciklikus kódolási folyamat Ciklikus kód

Ennek a szónak megfelelő formális változóból x. Látható, hogy ez a megfeleltetés nemcsak egy az egyhez, hanem izomorf is. Mivel a "szavak" a mezőből származó betűkből állnak, összeadhatók és szorozhatók (elemenként), és az eredmény ugyanabban a mezőben lesz. A szópár lineáris kombinációjának megfelelő polinom, és egyenlő e szavak polinomjainak lineáris kombinációjával

Ez lehetővé teszi számunkra, hogy a véges mező feletti n hosszúságú szavak halmazát a mező felett legfeljebb n-1 fokos polinomok lineáris terének tekintsük.

Algebrai leírás

Ha a ciklikus eltolással kapott kódszó egy bittel jobbra a szótól, akkor a megfelelő polinom c 1 (x) az előzőből x-szel való szorzással kapjuk:

Kihasználva azt a tényt

Váltás jobbra és balra j kisülések:

Ha egy m(x) egy tetszőleges polinom a mező felett GF(q) és c(x) - ciklikus ( n,k) kódot, akkor m(x)c(x)mod(x n − 1) ennek a kódnak a kódszava is.

Polinom generálása

Meghatározás A ciklus generáló polinomja ( n,k) kód C olyan nem nulla polinomnak nevezzük tól től C, amelynek foka a legkisebb, az együttható pedig a legmagasabb fokon g r = 1 .

1. tétel

Ha egy C- ciklikus ( n,k) kód és g(x) a generáló polinomja, majd a foka g(x) egyenlő r = n − k és minden kódszó egyedileg ábrázolható

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

ahol fokozat m(x) kisebb vagy egyenlő k − 1 .

2. tétel

g(x) a ciklus generáló polinomja ( n,k) a binomiális osztója x n − 1

Következmények:így generáló polinomként bármilyen polinomot, osztót választhatunk x n− 1. A kiválasztott polinom mértéke határozza meg az ellenőrző szimbólumok számát r, szám információs szimbólumok k = n − r .

Generatív mátrix

A polinomok egyébként lineárisan függetlenek m(x)g(x) = 0 nem nullához m(x), ami lehetetlen.

Ez azt jelenti, hogy a kódszavak a lineáris kódokhoz hasonlóan az alábbiak szerint írhatók:

, ahol G van mátrixot generál, m(x) - információs polinom.

Mátrix G szimbolikus formában írható:

Mátrix ellenőrzése

Egy ciklikus kód minden kódszava esetén . Ezért ellenőrző mátrixígy írható:

Kódolás

Rendszertelen

A nem szisztematikus kódolásnál a kódszót egy információs polinom szorzataként kapjuk meg egy generáló polinom által

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

Polinomiális szorzókkal valósítható meg.

Szisztematikus

A szisztematikus kódolással a kódszó információs részblokk és ellenőrzés formájában jön létre

Legyen tehát az információs szó a kódszó legmagasabb hatványa

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

Aztán a feltételből az következik

Ez az egyenlet határozza meg a szisztematikus kódolási szabályt. Megvalósítható többciklusú lineáris szűrőkkel (MLF)

Példák

Bináris (7,4,3) kód

Elválasztóként x 7 − 1 egy harmadfokú generáló polinomot választunk g(x) = x 3 + x + 1 , akkor a kapott kód hosszúságú lesz n= 7 , ellenőrző szimbólumok száma (a generáló polinom foka) r= 3 , információs szimbólumok száma k= 4 , minimális távolság d = 3 .

Generatív mátrix kód:

ahol az első sor egy polinomiális bejegyzés g(x) együtthatók növekvő sorrendben. A fennmaradó sorok az első sor ciklikus eltolódásai.

Ellenőrizze a mátrixot:

ahol az i-edik oszlop a 0-tól kezdve az osztás maradéka x én polinomon g(x) , a hatványok növekvő sorrendjében írva, felülről kezdve.

Így például a 3. oszlop , vagy vektoros jelölésben .

Ezt könnyű ellenőrizni GH T = 0 .

Bináris (15,7,5) BCH kód

Generáló polinomként g(x) két osztó szorzatát választhatja ki 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 .

Ekkor minden kódszó megkapható az információs polinom szorzatával m(x) végzettséggel k– 1 így:

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

Például az információs szó a polinomnak felel meg m(x) = x 6 + x 5 + x 4 + 1 , majd a kódszó 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 , vagy vektoros formában

Lásd még

Linkek

Wikimédia Alapítvány. 2010 .

Nézze meg, mik a "ciklikus kódok" más szótárakban:

rövidített ciklikus kódok- - [L.G. Sumenko. Angol orosz információs technológiai szótár. M.: GP TsNIIS, 2003.] Témák Információs technológiaáltalában EN rövidített ciklikus kódok ...

Nem bináris ciklikus kódok, amelyek lehetővé teszik az adatblokkok hibáinak javítását. A kódvektor elemei nem bitek, hanem bitcsoportok (blokkok). Nagyon gyakoriak a bájtokkal (oktettekkel) működő Reed Solomon kódok. Reed Solomon kódja ... Wikipédia

Golay kódok- Tökéletes lineáris blokkkódok családja hibajavítással. A leghasznosabb a bináris Golay kód. A hármas Golay-kód is ismert. A Golay kódok ciklikus kódoknak tekinthetők. …… Műszaki fordítói kézikönyv

A kommunikációs technológiában a hibaészlelés olyan művelet, amelynek célja az adatok sértetlenségének ellenőrzése az információ rögzítése / lejátszása vagy kommunikációs vonalakon történő továbbítása során. Hibajavítási (hibajavítási) eljárás az információk helyreállításához ... ... után Wikipédia

Ez a lineáris kódok egy alosztálya, amelyek azzal a gem tulajdonsággal rendelkeznek, hogy a szimbólumok ciklikus permutációja egy kódolt blokkban egy másik lehetséges kódolt blokkot eredményez ugyanabból a kódból. A ciklikus kódok az algebrai Galois-térelmélet1 gondolatainak alkalmazásán alapulnak.

A kommunikációs rendszerek számos legfontosabb zaj-immun kódja, -

különösen a ciklikus, véges aritmetikai struktúrákon alapulnak

Galois mezők. terület véges mezőt alkotó elemek halmazának nevezzük

A műveleti rangok idézőjelben vannak, mert nem mindig általánosan elfogadottak. aritmetikai műveletek. A mezőnek mindig van egy nulla eleme (0) vagy nulla, és egyetlen eleme (1) vagy egy. Ha szám q a mező elemei korlátozottak, akkor a mezőt hívják végső mező, vagy véges Galois mező, és van jelölve GF(q) y ahol q- tereprend. A legkisebb Galois-mező a kételemes mező GF( 2), amely csak két elemből áll, 1 és 0. Annak érdekében, hogy

1 Evariste Galois (1811 - 1832) - francia matematikus, lefektette a modern algebra alapjait.

elemeken végzett műveletek elvégzése GF( 2) nem vezettek ezen a területen túllépéshez, modulo 2-ben hajtják végre (általában ezt a mező sorrendje határozza meg egyszerű Galois mezők).

A mezőnek számos speciális matematikai tulajdonsága van. A mező elemeihez az összeadás és szorzás műveletei vannak definiálva, és e műveletek eredményeinek ugyanabba a halmazba kell tartozniuk.

Az összeadási és szorzási műveleteknél a szokásos matematikai asszociativitási szabályokat kell követni - a + (b + c) = (a + b)+ c, kommutativitás - a + b = b + aés a b = b aés disztribúció - a (b+ c) = a b + a Val vel.

Minden mezőelemhez a kell lennie egy inverz elemnek összeadással (-a)és ha a nem egyenlő nullával, inverz elem szorzással (th ’).

A mezőnek tartalmaznia kell adalék egység - 0 elem, úgy, hogy a + 0 = a bármely mezőelemhez a.

A mezőnek tartalmaznia kell szorzó egység - elem 1, úgy, hogy aL = a bármely mezőelemhez a.

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 egy kódszó ciklikus permutációjával létrehozott összes halmaz egyben kódszó is. Így például az 1000101 kombináció ciklikus permutációi a 0001011, 0010110, 0101100 stb. kódkombinációk is lesznek. Ez a tulajdonság lehetővé teszi a kódoló és a dekódoló nagymértékű egyszerűsítését, különösen a hibaészlelés és az egyszeri hibajavítás terén. A ciklikus kódokra való figyelem annak köszönhető, hogy magas korrekciós tulajdonságaikat viszonylag egyszerű algebrai módszerek alapján valósítják meg. Ugyanakkor egy tetszőleges lineáris blokkkód dekódolásához táblázat módszerek nagy mennyiségű dekódoló memóriát igényel.

A ciklikus kódot lineáris blokknak nevezzük (n, k)- olyan kód, amelyet a ciklikusság tulajdonsága jellemez, pl. bármely engedélyezett kódszó egy lépéssel balra történő eltolása egy engedélyezett kódszót is ad, amely ugyanahhoz a kódhoz tartozik, és amelyhez a kódszavak halmazát fokszámú polinomok halmaza reprezentálja (P- 1) vagy kevésbé osztható a generáló polinommal g(x) fokozat r=n-ky ami egy binomiális tényező x n+

A ciklikus kódban a kódszavakat polinomok (polinomok) képviselik.

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

Például az 101101 kódkombinációnál a polinom bejegyzés alakja a következő

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

Hamming kód. A Hamming-kód hibajavító képességei a minimális kódtávolsághoz kapcsolódnak d0. Minden többszörös hiba kijavításra kerül q= cnt (d 0- l)/2 (itt a cnt jelentése "egész rész") és multiplicitási hibákat észlel d 0 - 1. Szóval, páratlan paritással d Q = 2 és egyszeri hibákat észlel. Hamming kódban d 0 = 3. Az információs számjegyeken kívül L= log 2 Q redundáns vezérlőbit, ahol K- információs bitek száma. Paraméter L felfelé kerekítve a következő magasabb egész értékre. Az L-bites vezérlőkód azon információs bitek számának bitenkénti összeadásának (modulo 2 összeadás) fordított eredménye, amelyek értéke eggyel egyenlő.

Példa 7.7

Legyen az 100110 fő kód, azaz. Q= 6. Adjunk meg egy további kódot.

Megoldás

Azt találjuk L= 3 és a komplement kód az

ahol P a bitenkénti összeadás művelet szimbóluma, és az inverzió után 000-at kapunk. Most a kiegészítő kerül továbbításra a fő kóddal. A vevőben a kiegészítő kód ismét kiszámításra kerül, és összehasonlításra kerül a továbbított kóddal. Az összehasonlító kód fix, és ha eltér nullától, akkor értéke a főkód hibásan fogadott számjegyének a száma. Tehát, ha a 100010 kód érkezik, akkor a kiszámított kiegészítő kód megegyezik a 010Ш10 = 100 inverzével, azaz. 011, ami hibát jelent a 3. számjegyben.

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

Reed-Solomon kódok Galois-mezőkön vagy véges nullákon alapulnak. Aritmetikai műveletek összeadás, kivonás, szorzás, osztás stb. véges nulla elemei fölött olyan eredményt adunk, amely egyben ennek a nullának az eleme is. A Reed-Solomon kódolónak vagy dekódernek feltétlenül végre kell hajtania ezeket a műveleteket. A kód megvalósításához szükséges összes művelet speciális hardvert vagy speciális szoftvert igényel.

Turbó kódok. A redundáns kódok önállóan és több kód valamilyen kombinációjaként is használhatók, amikor egy redundáns kód karakterkészleteit egy másik redundáns kód elemi információs szimbólumainak tekintjük. Ez az egyesület néven vált ismertté lépcsőzetes kód. Az összefűzött kódok nagy előnye, hogy használatuk lehetővé teszi a kódoló és különösen a dekódoló egyszerűsítését az azonos hosszúságú és redundanciájú, nem kaszkádos kódokat tartalmazó hasonló eszközökhöz képest. A lépcsőzetes kódolás turbókódok létrehozásához vezetett. Turbókód két vagy több szisztematikus kódból álló párhuzamos jelszerkezetnek nevezzük. Felépítésük alapelve több párhuzamos komponens kódoló alkalmazása. Komponens kódként használhatók blokk- és konvolúciós kódok, Hamming-kódok, PC-kódok, BCH stb.. A perforáció (punkció) alkalmazása lehetővé teszi a turbókód relatív sebességének növelését azáltal, hogy korrekciós képességét a rendszer statisztikai jellemzőihez igazítja. kommunikációs csatorna. A turbókód kialakításának elve a következő: a bemeneti jel X, a következőket tartalmazza Nak nek bit, párhuzamosan táplálva N interleaverek. Az utóbbiak mindegyike olyan eszköz, amely egy blokk elemeit permuálja Nak nek bitek pszeudo-véletlen sorrendben. Az interleaverekből származó kimeneti jel - átrendezett szimbólumok - a megfelelő elemi kódolókhoz kerül. Bináris sorozatok 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 interleaver használata lehetővé teszi a korrelált hibasorozatok előfordulását a turbókódok dekódolásakor, ami fontos a hagyományos ismétlődő dekódolási módszer alkalmazásakor a feldolgozás során. Az alkatrészkód megválasztásától függően a turbókódok konvolúciós turbókódokra és blokktermékkódokra vannak osztva.

Ez lehetővé teszi számunkra, hogy a véges mező feletti n hosszúságú szavak halmazát a mező felett legfeljebb n-1 fokos polinomok lineáris terének tekintsük.