Cyklické kódy sa vyznačujú tým, že pri cyklickej permutácii všetkých symbolov kódovej kombinácie daného kódu vzniká ďalšia kódová kombinácia toho istého kódu.

Kombinácia cyklického kódu;

Tiež cyklická kombinácia kódov.

Pri zvažovaní cyklických kódov sú binárne čísla reprezentované ako polynóm, ktorého stupeň ( P - 1), P- dĺžka kombinácie kódov.

Napríklad kombinácia 1001111 ( n= 7) bude reprezentovaný polynómom

S touto reprezentáciou sú operácie s kombináciami kódov zredukované na operácie s polynómami. Tieto operácie sa vykonávajú v súlade s obyčajnou algebrou, okrem toho, že redukcia podobných výrazov sa vykonáva modulo 2.

Detekcia chýb pomocou cyklického kódu je zabezpečená výberom ako povolených kombinácií tých, ktoré sú bezo zvyšku deliteľné nejakým vopred zvoleným polynómom. G(X). Ak prijatá kombinácia obsahuje skreslené znaky, potom delenie polynómom G(X) sa vykonáva so zvyškom. Toto generuje signál označujúci chybu. Polynóm G(X)sa nazýva generovanie.

Konštrukcia kombinácií cyklického kódu je možná vynásobením pôvodnej kombinácie ALE(X) na generujúci polynóm G(X) s redukciou podobných výrazov modulo 2:

• ak najvyšší výkon produktu nepresahuje ( P - 1), potom bude výsledný polynóm predstavovať kombináciu kódov cyklického kódu;
• ak je najvyšší výkon produktu väčší alebo rovný P, potom je súčinový polynóm deliteľný vopred zvoleným polynómom stupňa P a výsledkom násobenia je zvyšok delenia.

Teda všetky polynómy reprezentujúce kombinácie cyklického kódu budú mať stupeň nižšie P.

Ako polynóm, ktorým sa delenie vykonáva, sa často používa polynóm G(X)= +1. Pri takomto vytváraní kombinácií kódov nie je možné vopred určiť polohy informačných a riadiacich symbolov.

Veľkou výhodou cyklických kódov je jednoduchosť konštrukcie kodérov a dekodérov, ktoré svojou štruktúrou predstavujú posuvné registre so spätnou väzbou.

Počet bitov registra je zvolený rovný stupňu generujúceho polynómu.

Spätná väzba je poskytovaná z výstupu registra niektorým čísliciam prostredníctvom sčítačiek, ktorých počet je zvolený o jednu menej ako počet nenulových členov generujúceho polynómu. Sčítačky sú inštalované na vstupoch tých bitov registra, ktoré zodpovedajú nenulovým členom generujúceho polynómu.

Obrázok 17 zobrazuje schému kódovacieho registra na konverziu štvorbitovej kombinácie na sedembitovú kombináciu.

Obrázok 17 - Schéma kódovacieho registra

V tabuľke. 4 je znázornené, ako sa posunutím pôvodnej kombinácie 0101 získa cyklická kódová kombinácia 1010011. n= 7, k=4. Kombinácia 0101, kľúč v polohe 1. Počas prvých štyroch cyklov sa register naplní, potom sa kľúč presunie do polohy 2. Spätná väzba je uzavretá. Pôsobením siedmich cyklov posunu sa vytvorí sedembitový cyklický kód.

Tabuľka 4

Vlastnosti cyklického kódu:

1) cyklický kód deteguje všetky jednotlivé chyby, ak generujúci polynóm obsahuje viac ako jeden člen. Ak G(X)=x+ 1, potom kód detekuje jednotlivé chyby a všetky nepárne;

2) cyklický kód s G(X)= (x+ 1)G(X) detekuje všetky jednoduché, dvojité a trojité chyby;

3) cyklický kód s generujúcim polynómom G(X) stupne r = n - k detekuje všetky skupinové chyby s trvaním r postavy.

testovacie otázky

Hlavné vlastnosti a samotný názov cyklických kódov súvisí s tým, že všetky povolené kombinácie binárnych symbolov v prenášanej správe je možné získať operáciou cyklického posunu niektorého zdrojového slova: Obvykle sú kódové kombinácie cyklického kódu nepovažuje sa za postupnosť núl a jednotiek, ale za polynóm určitého stupňa. Akékoľvek číslo v ľubovoľnom pozičnom číselnom systéme môže byť reprezentované všeobecnými pojmami ako: kde x je základ číselného systému; a - číslice tejto číselnej sústavy; p-1, p-2, ... - ukazovateľ stupňa zvýšenia základne a zároveň poradové čísla, ktoré zaberajú číslice. Pre binárnu sústavu je x=2 a a je buď "0" alebo "1". Napríklad binárnu kombináciu 01001 možno zapísať ako polynóm v argumente x: Pri písaní kombinácie kódov ako polynóm sa jednotka v 1. číslici zapíše ako člen x" a nula sa nezapíše vôbec. kombinácie kódov vo forme polynómov vám umožňujú vytvoriť medzi nimi korešpondenciu jedna ku jednej a zredukovať akcie na kombinácie na akcie na polynómoch. Sčítanie binárnych polynómov sa teda zredukuje na sčítanie modulo 2 koeficientov s rovnakými mocninami premennej.Napríklad násobenie sa vykonáva podľa obvyklého pravidla násobenia mocninových funkcií, avšak výsledné koeficienty v danom stupni sa pripočítajú modulo 2.Napríklad , Delenie sa vykonáva aj ako normálne delenie polynómov v tomto prípade je operácia odčítania nahradená operáciou sčítania modulo 2: Ako je uvedené vyššie, kódy sa nazývajú cyklické, pretože cyklický posun a n ^ a l L,..., a 2 ,a 1 ,a d1 a n1 povolenej kombinácie a n (, a n _ 2 ,...,a 1 , a 0 je tiež povolená kombinácia. Takáto cyklická permutácia pri použití zobrazení vo forme polynómov vzniká ako výsledok vynásobenia tohto polynómu x. ( x + a 0 , potom Y (x) x \u003d an] xn + an 2 xn " 1 + ... + axx 2 + a ^ x. Aby stupeň polynómu neprekročil n-1, výraz x" sa nahradí jednotkou, preto: Máme napr. kombinácia 1101110-> x in + x 5 + x 3 +. xg -1-x. Posuňme to o jeden bit. Dostaneme: Čo je to isté ako vynásobenie pôvodného polynómu na x: Teória konštrukcie cyklických kódov je založená o sekciách vyššej algebry, ktorá študuje vlastnosti binárnych polynómov. Osobitnú úlohu v tejto teórii zohrávajú takzvané ireducibilné polynómy, teda polynómy, ktoré nemožno reprezentovať ako súčin polynómov nižších stupňov. th-člen je deliteľný len sám sebou a jedným. Z vyššej algebry je známe, že binóm x "+1 je bezo zvyšku deliteľný neredukovateľným polynómom. V teórii kódovania sa ireducibilné polynómy nazývajú generujúce polynómy, pretože "tvoria" povolené kombinácie kódov (neredukovateľné polynómy sú tabuľkové, pozri tabuľku 8.4 ) (9). Myšlienka zostrojiť cyklický kód sa scvrkáva na skutočnosť, že polynóm predstavujúci informačnú časť kódovej kombinácie sa musí previesť na polynóm stupňa nie viac ako n-1, ktorý je rozdelený bez zvyšok generujúcim polynómom P(x).V cyklických kódoch majú všetky povolené kombinácie reprezentované ako polynómy jednu vlastnosť: deliteľnosť bezo zvyšku generujúcim polynómom P(x) polynóm O(x) 2. Vynásobte O(x) monomiálny Y a získajte 0(x)xr, tj derivát ide o posun ¿-bitového kódového slova o r bitov. 3. Vydeľte polynóm O(x)x" tvoriacim polynómom P(x), ktorého stupeň sa rovná r. Výsledkom vynásobenia O(x) xr je, že stupeň každého monočlenu zahrnutého v O( x) sa zvýši o r. Pri delení súčinu xr O[x) a tvoriacej priamky polynómu stupňa r dostaneme kvocient C(x) rovnakého stupňa ako 0(x).Výsledky týchto operácií možno znázorniť ako: (8.28) kde Wx) je zvyšok po delení 0(x)x r P(x). Pretože C(x) má rovnaký stupeň ako 0(x), potom C(x) je kombináciou rovnakého ¿-miestneho kódu. Stupeň zvyšku samozrejme nemôže byť väčší ako stupeň generujúceho polynómu, t.j. jeho najvyšší stupeň sa rovná r-1. V dôsledku toho najväčší počet číslic zvyšku nepresahuje r. Vynásobením oboch častí (8.28) P(x) prechádzanie: (8.29) (znamienko odčítania sa nahrádza znakom sčítania modulo 2). Je zrejmé, že F(x) je deliteľné P(x) bezo zvyšku. Polynóm F(x) je povolená kombinácia kódu cyklického kódu. Z (8.29) vyplýva, že povolenú kódovú kombináciu cyklického kódu možno získať dvoma spôsobmi: vynásobením kódovej kombinácie jednoduchého kódu C(x) generovaným polynómom P(x) alebo vynásobením kódovej kombinácie 0 (x) jednoduchého kódu monomílom xr k tomuto súčinu pripočítaním zvyšku P(x) získaného delením súčinu generujúcim polynómom P(x). Pri prvom spôsobe kódovania nie sú informačné a kontrolné bity navzájom oddelené (kód je neoddeliteľný). To komplikuje praktickú implementáciu procesu dekódovania. Pri druhom spôsobe sa získa oddeliteľný kód: informačné číslice obsadzujú vedúce pozície, zvyšných n-až číslic sú testovacie. Táto metóda kódovania je v praxi široko používaná. Príklad 3. Je uvedená kombinácia kódov 0111. Zostrojme cyklický kód s d o = 3. Riešenie. V prvej fáze určíme na základe požadovaného d o = 3 dĺžku kódu l a počet kontrolných prvkov k. Na tento účel použijeme tabuľku 8.6.1. Pre dané štvorbitové kódové slovo N-16. Potom pre d \u003d 3 zo vzťahu 16 (tabuľka 8.3) nájdeme n - 7, respektíve k \u003d n - m - \u003d 7 - 4 \u003d 3. Preto je potrebný kód (7.4). Podľa tabuľky generátorov polynómov (tabuľka 8.4) pre k = 3 určíme P (x) = x 3 + x 2 + 1. Ďalej: 1) pre správu 0111 máme O (x) = x 2 + x + 1; 2) vynásobte 0 (x) x 3 (od r \u003d 3): O (x) x 3 \u003d (x 2 -I- x + 1) x 3 \u003d x 5 + x 4 + x 3; 3) vydeľte (E (x) x 3 pomocou P (x): 4) dostaneme: ^ (x) \u003d O (x) x 3 0 I (x) \u003d x 5 + x 4 + x 3 + 1. Tento polynóm zodpovedá kombinácii kódu: Všetky tieto operácie je možné vykonávať aj s binárnymi číslami: Tabuľka 8.4
4) F(0,1) = O(0,l)x 3 (0,l)©R(0 1 l) = 011100000001= 0111 001. Teraz zostrojme povolené kódové slovo prvým spôsobom: F(x) =C(x)P(x). Urobme násobenie, reprezentujúce polynómy ako binárne čísla: Je vidieť, že vo výslednej kódovej kombinácii nie je možné rozlíšiť informačné a kontrolné bity. Detekcia chýb v cyklickom kódovaní spočíva v delení prijatého kódového slova rovnakým generujúcim polynómom, ktorý bol použitý pri kódovaní (jeho forma musí byť známa na recepcii). Ak v prijatej kódovej kombinácii nie sú žiadne chyby (alebo sú také, že sa daná prenášaná kombinácia kódov prevedie na inú povolenú), tak sa bezo zvyšku vykoná delenie generujúcim polynómom. Ak delením vznikne zvyšok, znamená to chybu. Príklad 4. Ako povolenú kombináciu kódov berieme kombináciu kódov získanú v predchádzajúcom príklade: P (x) \u003d x 5 + x 4 + x 3 + 1 a P (x) \u003d x 3 + x 2 + 1, alebo v binárnom tvare E(0,1) = 0111001; P(0,1) = 1101. Predpokladajme, že chyba nastala v najvýznamnejšej (7.) číslici v informačnej časti (číslice sa počítajú sprava doľava). Prijatá kombinácia kódov vyzerá ako 1111001. Vykonajte operáciu zisťovania chyby: Prítomnosť zvyšku 110 znamená chybu. Cyklické kódy sú široko používané v systémoch prenosu informácií. Napríklad v široko používanom protokole modemu \7.42 sa na kódovanie skupín kódov používa generatívny polynóm d(X) \u003d X 16 + X "-2 + X 5 + 1, čo je ekvivalentné kódu 1 0001 0000 0010 0001, ako aj generatívny polynóm vyššieho rádu d(X) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 1 + X 5 + X4 + X2 + 1. 8.6.

Tomuto slovu zodpovedá z formálnej premennej X. Je vidieť, že táto korešpondencia nie je len jedna k jednej, ale je aj izomorfná. Keďže „slová“ pozostávajú z písmen z poľa, možno ich sčítať a násobiť (prvok po prvku) a výsledok bude v rovnakom poli. Polynóm zodpovedajúci lineárnej kombinácii dvojice slov a rovná sa lineárnej kombinácii polynómov týchto slov

To nám umožňuje považovať množinu slov dĺžky n nad konečným poľom za lineárny priestor polynómov so stupňom najviac n-1 nad poľom.

Algebraický popis

Ak kódové slovo získame cyklickým posunom o jeden bit doprava od slova , potom jeho zodpovedajúci polynóm c 1 (X) sa získa z predchádzajúceho vynásobením x:

Využívajúc skutočnosť, že

Posun doprava a doľava j výboje:

Ak m(X) je ľubovoľný polynóm nad poľom GF(q) A c(X) - kódové slovo cyklického ( n,k) kód, potom m(X)c(X)mod(X n − 1) aj kódové slovo tohto kódu.

Generovanie polynómu

Definícia Generujúci polynóm cyklického ( n,k) kód C sa nazýva takýto nenulový polynóm od C, ktorého stupeň je najmenší a koeficient najvyšší stupeň g r = 1 .

Veta 1

Ak C- cyklický ( n,k) kód a g(X) je jeho generujúci polynóm, potom stupeň g(X) rovná sa r = n − k a každé kódové slovo môže byť jednoznačne reprezentované ako

c(X) = m(X)g(X) ,

kde stupeň m(X) menšie alebo rovné k − 1 .

Veta 2

g(X) je generujúci polynóm cyklického ( n,k) kódu je deliteľom dvojčlenu X n − 1

Dôsledky: teda ako generujúci polynóm si môžete zvoliť ľubovoľný polynóm, deliteľa X n− 1. Stupeň zvoleného polynómu určí počet kontrolných symbolov r, počet informačných symbolov k = n − r .

Generatívna matica

Inak sú polynómy lineárne nezávislé m(X)g(X) = 0 pre nenulové m(X), čo je nemožné.

To znamená, že kódové slová možno písať, rovnako ako pre lineárne kódy, takto:

, kde G je generovanie matice, m(X) - informačný polynóm.

Matrix G možno napísať v symbolickej forme:

Kontrola matice

Pre každé kódové slovo cyklického kódu, . Preto kontrolná matica možno napísať ako:

Kódovanie

Nesystematické

Pri nesystematickom kódovaní sa kódové slovo získa ako súčin informačného polynómu pomocou generujúceho polynómu.

c(X) = m(X)g(X) .

Dá sa implementovať pomocou polynomiálnych multiplikátorov.

Systematický

Pri systematickom kódovaní sa kódové slovo tvorí vo forme informačného podbloku a kontroly

Nech teda informačné slovo tvorí najvyššie mocniny kódového slova

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

Potom z podmienky vyplýva

Táto rovnica definuje pravidlo systematického kódovania. Môže byť implementovaný pomocou viaccyklových lineárnych filtrov (MLF)

Príklady

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

Ako rozdeľovač X 7 − 1 zvolíme tvoriaci polynóm tretieho stupňa g(X) = X 3 + X + 1 , potom bude mať výsledný kód dĺžku n= 7 , počet kontrolných symbolov (stupeň generujúceho polynómu) r= 3 , počet informačných symbolov k= 4, minimálna vzdialenosť d = 3 .

Generatívna matica kód:

,

kde prvý riadok je polynóm g(X) koeficienty vo vzostupnom poradí. Zvyšné riadky sú cyklické posuny prvého riadku.

Kontrolná matica:

,

kde i-tý stĺpec začínajúci od 0 je zvyšok delenia X i na polynóme g(X) , písaný vo vzostupnom poradí mocnin, začínajúc zhora.

Takže napríklad 3. stĺpec je , alebo vo vektorovej notácii .

Dá sa to ľahko overiť GH T = 0 .

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

Ako tvoriaci polynóm g(X) si môžete vybrať súčin dvoch deliteľov 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 .

Potom možno každé kódové slovo získať pomocou súčinu informačného polynómu m(X) s titulom k− 1 takto:

c(X) = m(X)g(X) .

Napríklad informačné slovo zodpovedá polynómu m(X) = X 6 + X 5 + X 4 + 1 , potom kódové slovo 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 alebo vo vektorovej forme

pozri tiež

Odkazy

Nadácia Wikimedia. 2010.

Pozrite si, čo sú „Cyklické kódy“ v iných slovníkoch:

skrátené cyklické kódy-- [L.G. Sumenko. Anglický ruský slovník informačných technológií. M .: GP TsNIIS, 2003.] Témy informačné technológie všeobecne EN skrátené cyklické kódy ...

Nebinárne cyklické kódy, ktoré umožňujú opraviť chyby v dátových blokoch. Prvky kódového vektora nie sú bity, ale skupiny bitov (bloky). Kódy Reed Solomon, ktoré pracujú s bajtmi (oktetmi), sú veľmi bežné. Kód Reeda Solomona je ... Wikipedia

Golay kódy- Rodina perfektných lineárnych blokových kódov s korekciou chýb. Najužitočnejší je binárny Golay kód. Známy je aj ternárny Golayov kód. Golayove kódy možno považovať za cyklické kódy. … … Technická príručka prekladateľa

Detekcia chýb v komunikačnej technike je činnosť zameraná na sledovanie integrity údajov počas záznamu / prehrávania informácií alebo počas ich prenosu po komunikačných linkách. Postup opravy chýb (oprava chýb) na obnovenie informácií po ... ... Wikipedia

Detekcia chýb v komunikačnej technike je činnosť zameraná na sledovanie integrity údajov počas záznamu / prehrávania informácií alebo počas ich prenosu po komunikačných linkách. Postup opravy chýb (oprava chýb) na obnovenie informácií po ... ... Wikipedia

Tomuto slovu zodpovedá z formálnej premennej X. Je vidieť, že táto korešpondencia nie je len jedna k jednej, ale je aj izomorfná. Keďže „slová“ pozostávajú z písmen z poľa, možno ich sčítať a násobiť (prvok po prvku) a výsledok bude v rovnakom poli. Polynóm zodpovedajúci lineárnej kombinácii dvojice slov a rovná sa lineárnej kombinácii polynómov týchto slov

To nám umožňuje považovať množinu slov dĺžky n nad konečným poľom za lineárny priestor polynómov so stupňom najviac n-1 nad poľom.

Algebraický popis

Ak kódové slovo získame cyklickým posunom o jeden bit doprava od slova , potom jeho zodpovedajúci polynóm c 1 (X) sa získa z predchádzajúceho vynásobením x:

Využívajúc skutočnosť, že

Posun doprava a doľava j výboje:

Ak m(X) je ľubovoľný polynóm nad poľom GF(q) A c(X) - kódové slovo cyklického ( n,k) kód, potom m(X)c(X)mod(X n − 1) aj kódové slovo tohto kódu.

Generovanie polynómu

Definícia Generujúci polynóm cyklického ( n,k) kód C sa nazýva takýto nenulový polynóm od C, ktorého stupeň je najmenší a koeficient najvyšší stupeň g r = 1 .

Veta 1

Ak C- cyklický ( n,k) kód a g(X) je jeho generujúci polynóm, potom stupeň g(X) rovná sa r = n − k a každé kódové slovo môže byť jednoznačne reprezentované ako

c(X) = m(X)g(X) ,

kde stupeň m(X) menšie alebo rovné k − 1 .

Veta 2

g(X) je generujúci polynóm cyklického ( n,k) kódu je deliteľom dvojčlenu X n − 1

Dôsledky: teda ako generujúci polynóm si môžete zvoliť ľubovoľný polynóm, deliteľa X n− 1. Stupeň zvoleného polynómu určí počet kontrolných symbolov r, počet informačných symbolov k = n − r .

Generatívna matica

Inak sú polynómy lineárne nezávislé m(X)g(X) = 0 pre nenulové m(X), čo je nemožné.

To znamená, že kódové slová možno písať, rovnako ako pre lineárne kódy, takto:

, kde G je generovanie matice, m(X) - informačný polynóm.

Matrix G možno napísať v symbolickej forme:

Kontrola matice

Pre každé kódové slovo cyklického kódu, . Preto kontrolná matica možno napísať ako:

Kódovanie

Nesystematické

Pri nesystematickom kódovaní sa kódové slovo získa ako súčin informačného polynómu pomocou generujúceho polynómu.

c(X) = m(X)g(X) .

Dá sa implementovať pomocou polynomiálnych multiplikátorov.

Systematický

Pri systematickom kódovaní sa kódové slovo tvorí vo forme informačného podbloku a kontroly

Nech teda informačné slovo tvorí najvyššie mocniny kódového slova

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

Potom z podmienky vyplýva

Táto rovnica definuje pravidlo systematického kódovania. Môže byť implementovaný pomocou viaccyklových lineárnych filtrov (MLF)

Príklady

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

Ako rozdeľovač X 7 − 1 zvolíme tvoriaci polynóm tretieho stupňa g(X) = X 3 + X + 1 , potom bude mať výsledný kód dĺžku n= 7 , počet kontrolných symbolov (stupeň generujúceho polynómu) r= 3 , počet informačných symbolov k= 4, minimálna vzdialenosť d = 3 .

Generatívna matica kód:

,

kde prvý riadok je polynóm g(X) koeficienty vo vzostupnom poradí. Zvyšné riadky sú cyklické posuny prvého riadku.

Kontrolná matica:

,

kde i-tý stĺpec začínajúci od 0 je zvyšok delenia X i na polynóme g(X) , písaný vo vzostupnom poradí mocnin, začínajúc zhora.

Takže napríklad 3. stĺpec je , alebo vo vektorovej notácii .

Dá sa to ľahko overiť GH T = 0 .

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

Ako tvoriaci polynóm g(X) si môžete vybrať súčin dvoch deliteľov 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 .

Potom možno každé kódové slovo získať pomocou súčinu informačného polynómu m(X) s titulom k− 1 takto:

c(X) = m(X)g(X) .

Napríklad informačné slovo zodpovedá polynómu m(X) = X 6 + X 5 + X 4 + 1 , potom kódové slovo 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 alebo vo vektorovej forme

pozri tiež

Odkazy

Nadácia Wikimedia. 2010.

• Cyklické formy v hudbe
• Cyklické okrajové podmienky

Pozrite si, čo sú „Cyklické kódy“ v iných slovníkoch:

skrátené cyklické kódy-- [L.G. Sumenko. Anglický ruský slovník informačných technológií. M .: GP TsNIIS, 2003.] Témy informačné technológie všeobecne EN skrátené cyklické kódy ...

Reed-Solomonove kódy- nebinárne cyklické kódy, ktoré umožňujú opraviť chyby v dátových blokoch. Prvky kódového vektora nie sú bity, ale skupiny bitov (bloky). Kódy Reed Solomon, ktoré pracujú s bajtmi (oktetmi), sú veľmi bežné. Kód Reeda Solomona je ... Wikipedia

Golay kódy- Rodina perfektných lineárnych blokových kódov s korekciou chýb. Najužitočnejší je binárny Golay kód. Známy je aj ternárny Golayov kód. Golayove kódy možno považovať za cyklické kódy. … … Technická príručka prekladateľa

Kódy na opravu chýb

Kódy na opravu chýb- Detekcia chýb v komunikačnej technike je činnosť zameraná na sledovanie integrity údajov pri zaznamenávaní/prehrávaní informácií alebo pri ich prenose po komunikačných linkách. Postup opravy chýb (oprava chýb) na obnovenie informácií po ... ... Wikipedia

Kódy na opravu chýb- Detekcia chýb v komunikačnej technike je činnosť zameraná na sledovanie integrity údajov pri zaznamenávaní/prehrávaní informácií alebo pri ich prenose po komunikačných linkách. Postup opravy chýb (oprava chýb) na obnovenie informácií po ... ... Wikipedia

Cyklický kód

Cyklické kódy patria medzi blokové systematické kódy, v ktorých je každá kombinácia kódovaná nezávisle (vo forme bloku) tak, že sa vždy nájde informácia k a kontrolné t znaky.

obliekať sa na určitých miestach. Možnosť detekcie a opravy prakticky akýchkoľvek chýb s relatívne malou redundanciou v porovnaní s inými kódmi, ako aj jednoduchosť obvodovej implementácie kódovacieho a dekódovacieho zariadenia spôsobili, že tieto kódy sa rozšírili. Teória cyklických kódov je založená na teórii grúp a polynomiálnej algebre nad Galoisovým poľom.

Cyklický kód je kód, v ktorom sa poradie distribúcie kombinácií kódov vykonáva takým spôsobom, že pri prechode z akejkoľvek kombinácie do susednej zostáva vzdialenosť Hammingovho kódu zakaždým konštantná.

Cyklické kódy predstavujú celú rodinu kódov na opravu chýb, vrátane Hammingových kódov ako jednej z odrôd, ale vo všeobecnosti poskytujú väčšiu flexibilitu, pokiaľ ide o možnosť implementácie kódov s potrebnou schopnosťou odhaliť a opraviť chyby, ktoré sa vyskytujú pri prenose kombinácií kódov. cez komunikačný kanál. Cyklický kód sa týka systematických blokových (n, k) kódov, v ktorých prvých k bitov je kombináciou primárneho kódu a nasledujúcich (n x k) bitov sú kontrolné bity.

Konštrukcia cyklických kódov je založená na operácii delenia prenášaného kódového slova generujúcim neredukovateľným polynómom stupňa r. Zvyšok delenia sa používa pri vytváraní kontrolných bitov. V tomto prípade operácii delenia predchádza operácia násobenia, ktorá posúva kombináciu k-bitového informačného kódu doľava o r bitov.

Polynóm (polynóm), ktorý možno znázorniť ako súčin polynómov nižších stupňov, sa nazýva redukovateľný (v danom obore), inak je neredukovateľný. Neredukovateľné polynómy hrajú v teórii čísel podobnú úlohu ako prvočísla. Neredukovateľné polynómy P(X) možno zapísať ako desiatkové alebo binárne čísla alebo ako algebraický polynóm.

Proces cyklického kódovania

Cyklické kódovanie je založené na použití ireducibilného polynómu P(X), ktorý sa vo vzťahu k cyklickým kódom nazýva generujúci, generujúci alebo generujúci polynóm (polynóm).

Ako informačné symboly k pre konštrukciu cyklických kódov sa berú kombinácie binárneho kódu pre všetky kombinácie. Vo všeobecnom prípade, ak sa daná kombinácia kódov Q(x) vynásobí generujúcim polynómom P(x), dostaneme cyklický kód, ktorý má určité korekčné vlastnosti v závislosti od voľby P(x). Avšak v tomto kóde budú riadiace symboly m umiestnené na rôznych miestach v kódovom slove. Takýto kód nie je systematický, čo sťažuje jeho implementáciu v obvodoch. Situáciu možno značne zjednodušiť, ak sa riadiace znaky priradia na konci, teda až za informačnými znakmi. Na tento účel sa odporúča použiť nasledujúcu metódu:

Vynásobte kódové slovo G(x), ktoré sa má zakódovať, jednočlenom Xm, ktorý má rovnaký stupeň ako mnohočlen P(x);

Súčin G(x)X m delíme generovaným polynómom P(x m):

kde Q(x) je podiel delenia; R(x) - zvyšok.

Vynásobením výrazu (2.1) Р(х) a prenesením R(x) na druhú časť rovnosti bez opačného znamienka dostaneme:

Takže podľa rovnosti (2.2) môže byť cyklický kód, teda zakódovaná správa F(x), vytvorený dvoma spôsobmi:

Násobenie jednej kódovej kombinácie binárneho kódu pre všetky kombinácie generovaným polynómom P(x);

Vynásobením danej kódovej kombinácie G(x) jediným polynómom X m, ktorý má rovnaký stupeň ako generujúci polynóm P(x), s pripočítaním zvyšku R(x) získaného po delení súčinu G(x)X m generovaním polynómu P( X).

Kódovanie správ

Je potrebné zakódovať kódové slovo 1100, ktoré zodpovedá G(x)=x 3 +x 2 s P(x)=x 3 +x+1.

Vynásobíme G (x) X m, ktorý má tretí stupeň, dostaneme:

Delením súčinu G(x)X m generovaným polynómom P(x m) podľa (2.1) dostaneme:

alebo v binárnom ekvivalente:

Výsledkom je, že dostaneme kvocient Q(x) rovnakého stupňa ako G(x):

Q(x)=x3+x2+x>1110

a zvyšok:

Výsledkom je, že kombinácia binárneho kódu zakódovaná cyklickým kódom podľa (2.2) bude mať tvar:

F(x)=1110 1011=1100010

Keďže každá povolená kódová kombinácia cyklického kódu predstavuje všetky možné súčty generujúceho polynómu G(x), musia byť bezo zvyšku deliteľné P(x). Preto sa kontrola správnosti prijatej kombinácie kódov redukuje na identifikáciu zvyšku pri jeho delení generujúcim polynómom.

Prijatie zvyšku indikuje prítomnosť chyby. Zvyšok delenia v cyklických kódoch hrá úlohu syndrómu.

Napríklad prenášaná kódová kombinácia F(x)=1100010, vytvorená pomocou generujúceho polynómu P(x)=1011. Pod vplyvom rušenia sa kombinácia kódov zmenila na kombináciu F "(x) = 1000010

Prijatú kombináciu vydelíme tvoriacim polynómom

Prítomnosť zvyšku R(x)=001 označuje chybu. Neoznačuje však priamo miesto chyby v kombinácii. Na určenie chyby existuje niekoľko metód založených na analýze syndrómu.

Určme miesto chyby, na to jednotku s ľubovoľným počtom núl vydelíme P(x)=1011.

Vyskytla sa chyba v čísle prvku:

Počet zvyškov -2>4-2=2

To znamená, že chyba je v druhom prvku.