Tomuto slovu odpovídá z formální proměnné X. Je vidět, že tato korespondence není jen jedna ku jedné, ale také izomorfní. Protože se „slova“ skládají z písmen z pole, lze je sčítat a násobit (prvek po prvku) a výsledek bude ve stejném poli. Polynom odpovídající lineární kombinaci dvojice slov a je roven lineární kombinaci polynomů těchto slov

To nám umožňuje považovat množinu slov délky n nad konečným tělesem za lineární prostor polynomů se stupněm nejvýše n-1 nad polem.

Algebraický popis

Pokud kódové slovo získáme cyklickým posunem o jeden bit doprava od slova , pak jeho odpovídající polynom C 1 (X) se získá z předchozího vynásobením x:

Využití toho, že

Posun doprava a doleva j výboje:

Pokud m(X) je libovolný polynom nad polem GF(q) a C(X) - kódové slovo cyklického ( n,k) kód, tedy m(X)C(X)mÓd(X n − 1) také kódové slovo tohoto kódu.

Generování polynomu

Definice Generující polynom cyklického ( n,k) kód C se nazývá takový nenulový polynom z C, jehož stupeň je nejmenší a koeficient nejvyšší G r = 1 .

Věta 1

Pokud C- cyklický ( n,k) kód a G(X) je jeho generující polynom, pak stupeň G(X) je rovný r = n − k a každé kódové slovo může být jednoznačně reprezentováno jako

C(X) = m(X)G(X) ,

kde stupeň m(X) menší nebo rovno k − 1 .

Věta 2

G(X) je generující polynom cyklického ( n,k) kódu je dělitel dvojčlenu X n − 1

Důsledky: jako generující polynom si tedy můžete vybrat libovolný polynom, dělitel X n− 1. Stupeň zvoleného polynomu určí počet kontrolních symbolů r, číslo informační symboly k = n − r .

Generativní matice

Polynomy jsou lineárně nezávislé, jinak m(X)G(X) = 0 pro nenulové m(X), což je nemožné.

To znamená, že kódová slova lze psát, stejně jako lineární kódy, následovně:

, kde G je generování matice, m(X) - informační polynom.

Matice G lze zapsat v symbolické formě:

Kontrola matice

Pro každé kódové slovo cyklického kódu, . Proto kontrolní matice lze napsat jako:

Kódování

Nesystematické

Při nesystematickém kódování se kódové slovo získá jako součin informačního polynomu generujícím polynomem

C(X) = m(X)G(X) .

Lze jej implementovat pomocí polynomiálních multiplikátorů.

Systematický

Při systematickém kódování je kódové slovo tvořeno ve formě informačního dílčího bloku a kontroly

Nechť tedy informační slovo tvoří nejvyšší mocniny kódového slova

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

Pak z podmínky vyplývá

Tato rovnice definuje pravidlo systematického kódování. Lze jej implementovat pomocí vícecyklových lineárních filtrů (MLF)

Příklady

Binární (7,4,3) kód

Jako oddělovač X 7 − 1 zvolíme generující polynom třetího stupně G(X) = X 3 + X + 1 , pak bude mít výsledný kód délku n= 7 , počet kontrolních symbolů (stupeň generujícího polynomu) r= 3 , počet informačních symbolů k= 4 , minimální vzdálenost d = 3 .

Generativní matice kód:

,

kde první řádek je polynomický záznam G(X) koeficienty ve vzestupném pořadí. Zbývající řádky jsou cyklické posuny prvního řádku.

Kontrolní matice:

,

kde i-tý sloupec počínaje 0 je zbytek dělení X i na polynomu G(X), psaný ve vzestupném pořadí mocnin, počínaje shora.

Takže například 3. sloupec je , nebo ve vektorové notaci .

Je snadné si to ověřit GH T = 0 .

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

Jako generující polynom G(X) můžete zvolit součin dvou dělitelů 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 lze každé kódové slovo získat pomocí součinu informačního polynomu m(X) s titulem k− 1 takto:

C(X) = m(X)G(X) .

Například informační slovo odpovídá polynomu m(X) = X 6 + X 5 + X 4 + 1 , pak 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 nebo ve vektorové podobě

viz také

Odkazy

Nadace Wikimedia. 2010 .

Podívejte se, co jsou "Cyklické kódy" v jiných slovnících:

zkrácené cyklické kódy- - [L.G. Sumenko. Anglický ruský slovník informačních technologií. M.: GP TsNIIS, 2003.] Témata Informační technologie obecně EN zkrácené cyklické kódy ...

Nebinární cyklické kódy, které umožňují opravit chyby v datových blocích. Prvky kódového vektoru nejsou bity, ale skupiny bitů (bloky). Velmi běžné jsou kódy Reed Solomon, které pracují s byty (oktety). Kód Reeda Solomona je ... Wikipedie

Golay kódy- Rodina dokonalých lineárních blokových kódů s opravou chyb. Nejužitečnější je binární Golay kód. Známý je také ternární Golayův kód. Golayovy kódy lze považovat za cyklické kódy. … … Technická příručka překladatele

Detekce chyb v komunikační technice je akce zaměřená na sledování integrity dat při záznamu/přehrávání informací nebo při jejich přenosu po komunikačních linkách. Postup opravy chyb (oprava chyb) pro obnovu informací po ... ... Wikipedie

Detekce chyb v komunikační technice je akce zaměřená na sledování integrity dat při záznamu/přehrávání informací nebo při jejich přenosu po komunikačních linkách. Postup opravy chyb (oprava chyb) pro obnovu informací po ... ... Wikipedie

Toto je podtřída lineárních kódů, které mají vlastnost gem, že cyklická permutace symbolů v kódovaném bloku poskytuje další možný kódovaný blok stejného kódu. Cyklické kódy jsou založeny na aplikaci myšlenek algebraické Galoisovy teorie pole1.

Mnoho z nejdůležitějších protihlukových kódů komunikačních systémů, -

zejména cyklické, jsou založeny na konečných aritmetických strukturách

Pole Galois. pole se nazývá množina prvků, které jsou konečným polem

Operační hodnosti jsou v uvozovkách, protože nejsou vždy obecně přijímány. aritmetické operace. Pole má vždy nulový prvek (0) nebo nulu a jeden prvek (1) nebo jedničku. Pokud číslo q prvků pole je omezeno, pak se pole nazývá závěrečné pole nebo konečné Galoisovo pole, a je označeno GF(q) y kde q- polní řád. Nejmenší pole Galois je dvouprvkové pole GF( 2), skládající se pouze ze dvou prvků 1 a 0. Aby

1 Evariste Galois (1811 - 1832) - francouzský matematik, položil základy moderní algebry.

provádění operací na prvcích GF( 2) nevedly k překročení tohoto pole, provádějí se modulo 2 (obecně je to určeno pořadím pole pro jednoduchá pole Galois).

Obor má řadu specifických matematických vlastností. Pro prvky pole jsou definovány operace sčítání a násobení a výsledky těchto operací musí patřit do stejné množiny.

Pro operace sčítání a násobení se dodržují obvyklá pravidla matematické asociativnosti - A + (b + c) = (a + b)+ c, komutativnost - a + b = b + a a A b = b A a distributivita - A (b+ c) = A b + A S.

Pro každý prvek pole A musí existovat inverzní prvek přidáním (-A) a pokud A nerovná se nule, inverzní prvek násobením (th ’).

Pole musí obsahovat aditivní jednotka - prvek 0, takový, že A + 0 = A pro jakýkoli prvek pole A.

Pole musí obsahovat multiplikační jednotka - prvek 1, takový, že aL = a pro jakýkoli prvek pole A.

Existují například pole reálná čísla, racionální čísla, komplexní čísla. Tato pole obsahují nekonečné množství prvků.

Ve skutečnosti všechny množiny tvořené cyklickou permutací kódového slova jsou také kódová slova. Takže například cyklické permutace kombinace 1000101 budou také kombinacemi kódů 0001011, 0010110, 0101100 atd. Tato vlastnost umožňuje výrazně zjednodušit kodér a dekodér, zejména při detekci chyb a opravě jedné chyby. Pozornost cyklickým kódům je dána tím, že jejich vysoké korekční vlastnosti jsou implementovány na základě relativně jednoduchých algebraických metod. Současně pro dekódování libovolného lineárního blokového kódu, tabulkové metody vyžadující velké množství paměti dekodéru.

Cyklický kód se nazývá lineární blok (n, k)- kód, který se vyznačuje vlastností cykličnosti, tzn. posunutí libovolného povoleného kódového slova doleva o jeden krok také dává povolené kódové slovo patřící stejnému kódu, pro které je množina kódových slov reprezentována sadou polynomů stupně (P- 1) nebo méně dělitelné generujícím polynomem g(x) stupně r=n-ky což je faktor binomu X n+

V cyklickém kódu jsou kódová slova reprezentována polynomy (polynomy)

kde P - délka kódu; A i - Koeficienty pole Galois (hodnoty kombinace kódů).

Například pro kombinaci kódů 101101 má položka polynomu tvar

Příklady cyklických kódů jsou kódy sudé kontroly, kódy opakování, Hammingovy kódy, PC kódy a turbo kódy.

Hammingův kód. Možnosti opravy chyb v Hammingově kódu souvisí s minimální vzdáleností kódu d0. Všechny chyby násobnosti jsou opraveny q= cnt (d 0- l)/2 (zde cnt znamená "celočíselná část") a jsou zjištěny chyby násobnosti d 0 - 1. Takže s lichou paritou d Q = 2 a jsou detekovány jednotlivé chyby. V Hammingově kódu d 0 = 3. Kromě informačních číslic L= log 2 Q redundantní řídicí bity, kde Q- počet informačních bitů. Parametr L zaokrouhleno nahoru na nejbližší vyšší celé číslo. L-bitový řídicí kód je převráceným výsledkem bitového sčítání (sčítání modulo 2) čísel těch informačních bitů, jejichž hodnoty jsou rovné jedné.

Příklad 7.7

Mějme hlavní kód 100110, tzn. Q= 6. Definujme doplňkový kód.

Řešení

Najdeme to L= 3 a kód doplňku je

kde P je symbol operace bitového sčítání a po inverzi máme 000. Nyní bude dodatečný kód přenesen s hlavním kódem. V přijímači se opět vypočítá doplňkový kód a porovná se s vysílaným. Srovnávací kód je pevný, a pokud se liší od nuly, pak jeho hodnota je číslo chybně přijaté číslice hlavního kódu. Pokud je tedy přijat kód 100010, pak se vypočítaný doplňkový kód rovná převrácené hodnotě 010Ш10 = 100, tzn. 011, což znamená chybu ve 3. číslici.

Zobecněním Hammingových kódů jsou cyklické BCH kódy, které umožňují opravit více chyb v přijatém kódovém slově.

Reed-Solomonovy kódy jsou založeny na Galoisových polích neboli konečných nulách. Aritmetické operace sčítání, odčítání, násobení, dělení atd. přes prvky konečné nuly dávají výsledek, který je také prvkem této nuly. Tyto operace musí nutně provádět kodér nebo dekodér Reed-Solomon. Všechny operace k implementaci kódu vyžadují speciální hardware nebo specializovaný software.

Turbo kódy. Redundantní kódy mohou být použity jak samostatně, tak ve formě nějaké kombinace více kódů, kdy znakové sady jednoho redundantního kódu jsou považovány za elementární informační symboly jiného redundantního kódu. Toto sdružení se stalo známým jako kaskádové kód. Velkou výhodou zřetězených kódů je, že jejich použití umožňuje zjednodušit kodér a zejména dekodér ve srovnání s podobnými zařízeními nekaskádovaných kódů stejné délky a redundance. Kaskádové kódování vedlo k vytvoření turbo kódů. Turbokód nazývaná paralelní signální struktura sestávající ze dvou nebo více systematických kódů. Základním principem jejich konstrukce je použití několika paralelních komponentních kodérů. Jako komponentní kódy lze použít jak blokové, tak konvoluční kódy, Hammingovy kódy, PC kód, BCH atd. Použití perforace (děrování) umožňuje zvýšit relativní rychlost turbo kódu přizpůsobením jeho korekční schopnosti statistickým charakteristikám komunikační kanál. Princip tvorby turbo kódu je následující: vstupní signál X, skládající se z Na bit, přiváděný paralelně k N prokladače. Každý z nich je zařízením, které permutuje prvky v bloku Na bitů v pseudonáhodném pořadí. Výstupní signál z prokládačů - přeuspořádané symboly - je přiváděn do příslušných elementárních kodérů. Binární posloupnosti x p i= 1,2,..., JV, na výstupu kodéru jsou kontrolní symboly, které spolu s informačními bity tvoří jediné kódové slovo. Použití interleaveru umožňuje zabránit výskytu sekvencí korelovaných chyb při dekódování turbo kódů, což je důležité při použití tradičního rekurentního způsobu dekódování při zpracování. V závislosti na volbě kódu komponentu se turbo kódy dělí na konvoluční turbo kódy a blokové kódy produktů.

Tomuto slovu odpovídá z formální proměnné X. Je vidět, že tato korespondence není jen jedna ku jedné, ale také izomorfní. Protože se „slova“ skládají z písmen z pole, lze je sčítat a násobit (prvek po prvku) a výsledek bude ve stejném poli. Polynom odpovídající lineární kombinaci dvojice slov a je roven lineární kombinaci polynomů těchto slov

To nám umožňuje považovat množinu slov délky n nad konečným tělesem za lineární prostor polynomů se stupněm nejvýše n-1 nad polem.

Algebraický popis

Pokud kódové slovo získáme cyklickým posunem o jeden bit doprava od slova , pak jeho odpovídající polynom C 1 (X) se získá z předchozího vynásobením x:

Využití toho, že

Posun doprava a doleva j výboje:

Pokud m(X) je libovolný polynom nad polem GF(q) a C(X) - kódové slovo cyklického ( n,k) kód, tedy m(X)C(X)mÓd(X n − 1) také kódové slovo tohoto kódu.

Generování polynomu

Definice Generující polynom cyklického ( n,k) kód C se nazývá takový nenulový polynom z C, jehož stupeň je nejmenší a koeficient nejvyšší G r = 1 .

Věta 1

Pokud C- cyklický ( n,k) kód a G(X) je jeho generující polynom, pak stupeň G(X) je rovný r = n − k a každé kódové slovo může být jednoznačně reprezentováno jako

C(X) = m(X)G(X) ,

kde stupeň m(X) menší nebo rovno k − 1 .

Věta 2

G(X) je generující polynom cyklického ( n,k) kódu je dělitel dvojčlenu X n − 1

Důsledky: jako generující polynom si tedy můžete vybrat libovolný polynom, dělitel X n− 1. Stupeň zvoleného polynomu určí počet kontrolních symbolů r, počet informačních symbolů k = n − r .

Generativní matice

Polynomy jsou lineárně nezávislé, jinak m(X)G(X) = 0 pro nenulové m(X), což je nemožné.

To znamená, že kódová slova lze psát, stejně jako lineární kódy, následovně:

, kde G je generování matice, m(X) - informační polynom.

Matice G lze zapsat v symbolické formě:

Kontrola matice

Pro každé kódové slovo cyklického kódu, . Proto kontrolní matice lze napsat jako:

Kódování

Nesystematické

Při nesystematickém kódování se kódové slovo získá jako součin informačního polynomu generujícím polynomem

C(X) = m(X)G(X) .

Lze jej implementovat pomocí polynomiálních multiplikátorů.

Systematický

Při systematickém kódování je kódové slovo tvořeno ve formě informačního dílčího bloku a kontroly

Nechť tedy informační slovo tvoří nejvyšší mocniny kódového slova

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

Pak z podmínky vyplývá

Tato rovnice definuje pravidlo systematického kódování. Lze jej implementovat pomocí vícecyklových lineárních filtrů (MLF)

Příklady

Binární (7,4,3) kód

Jako oddělovač X 7 − 1 zvolíme generující polynom třetího stupně G(X) = X 3 + X + 1 , pak bude mít výsledný kód délku n= 7 , počet kontrolních symbolů (stupeň generujícího polynomu) r= 3 , počet informačních symbolů k= 4 , minimální vzdálenost d = 3 .

Generativní matice kód:

,

kde první řádek je polynomický záznam G(X) koeficienty ve vzestupném pořadí. Zbývající řádky jsou cyklické posuny prvního řádku.

Kontrolní matice:

,

kde i-tý sloupec počínaje 0 je zbytek dělení X i na polynomu G(X), psaný ve vzestupném pořadí mocnin, počínaje shora.

Takže například 3. sloupec je , nebo ve vektorové notaci .

Je snadné si to ověřit GH T = 0 .

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

Jako generující polynom G(X) můžete zvolit součin dvou dělitelů 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 lze každé kódové slovo získat pomocí součinu informačního polynomu m(X) s titulem k− 1 takto:

C(X) = m(X)G(X) .

Například informační slovo odpovídá polynomu m(X) = X 6 + X 5 + X 4 + 1 , pak 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 nebo ve vektorové podobě

viz také

Odkazy

Nadace Wikimedia. 2010 .

• Cyklické formy v hudbě
• Cyklické okrajové podmínky

Podívejte se, co jsou "Cyklické kódy" v jiných slovnících:

zkrácené cyklické kódy- - [L.G. Sumenko. Anglický ruský slovník informačních technologií. M .: GP TsNIIS, 2003.] Témata informační technologie obecně EN zkrácené cyklické kódy ...

Reed-Solomonovy kódy- nebinární cyklické kódy, které umožňují opravit chyby v datových blocích. Prvky kódového vektoru nejsou bity, ale skupiny bitů (bloky). Velmi běžné jsou kódy Reed Solomon, které pracují s byty (oktety). Kód Reeda Solomona je ... Wikipedie

Golay kódy- Rodina dokonalých lineárních blokových kódů s opravou chyb. Nejužitečnější je binární Golay kód. Známý je také ternární Golayův kód. Golayovy kódy lze považovat za cyklické kódy. … … Technická příručka překladatele

Kódy pro opravu chyb

Kódy pro opravu chyb- Detekce chyb v komunikační technice je akce zaměřená na sledování integrity dat při záznamu / přehrávání informací nebo při jejich přenosu po komunikačních linkách. Postup opravy chyb (oprava chyb) pro obnovu informací po ... ... Wikipedie

Kódy pro opravu chyb- Detekce chyb v komunikační technice je akce zaměřená na sledování integrity dat při záznamu / přehrávání informací nebo při jejich přenosu po komunikačních linkách. Postup opravy chyb (oprava chyb) pro obnovu informací po ... ... Wikipedie

Hlavní vlastnosti a samotný název cyklických kódů souvisí s tím, že všechny povolené kombinace binárních symbolů v přenášené zprávě lze získat operací cyklického posunu některého zdrojového slova: Obvykle se kódové kombinace cyklického kódu nepovažují za jako posloupnost nul a jedniček, ale jako polynom určitého stupně . Jakékoli číslo v libovolné poziční číselné soustavě lze v obecných termínech reprezentovat jako: kde x je základ číselné soustavy; a - číslice této číselné soustavy; p-1, p-2, ... - ukazatel stupně zvednutí základny a zároveň pořadová čísla, které obsazují řady. Pro binární systém je x=2 a a je buď "0" nebo "1". Například binární kombinace 01001 může být zapsána jako polynom v argumentu x: Při zápisu kódové kombinace jako polynom se jednotka v 1. číslici zapíše jako člen x" a nula se nezapíše vůbec. kombinace kódů ve formě polynomů vám umožňuje vytvořit mezi nimi vzájemnou korespondenci a omezit akce na kombinace na akce na polynomy. Sčítání binárních polynomů je tedy redukováno na modul sčítání 2 koeficientů se stejnou mocninou. proměnné.Například násobení se provádí podle obvyklého pravidla násobení mocninných funkcí, výsledné koeficienty se však v daném stupni přičtou modulo 2.Například , Dělení se také provádí jako normální dělení polynomů ; v tomto případě je operace odčítání nahrazena operací sčítání modulo 2: Jak bylo uvedeno výše, kódy se nazývají cyklické, protože cyklický posun a n ^ a l L,..., a 2 ,a 1 ,a d1 a n1 povolené kombinace a n (, a n _ 2 ,...,a 1 , a 0 je také povolená kombinace. Taková cyklická permutace při použití reprezentací ve formě polynomů vzniká jako výsledek vynásobení tohoto polynomu x. ( x + a 0 , pak Y (x) x \u003d a n] x n + a n 2 x n " 1 + ... + a x x 2 + a ^ x. Aby stupeň polynomu nepřesáhl n-1, nahradí se člen x" jedničkou, proto: Máme například kód kombinace 1101110-> x v + x 5 + x 3 +. x g -1-x. Posuňme to o jednu číslici. Dostaneme: Což je stejné jako vynásobení původního polynomu na x: Teorie konstruování cyklických kódů je založena o úsecích vyšší algebry, která studuje vlastnosti binárních polynomů. Zvláštní roli v této teorii hrají tzv. ireducibilní polynomy, tj. polynomy, které nelze reprezentovat jako součin polynomů nižších stupňů. th-člen je dělitelný pouze sám sebou a jedním. Z vyšší algebry je známo, že binom x "+1 je beze zbytku dělitelný ireducibilním polynomem. V teorii kódování se ireducibilní polynomy nazývají generující polynomy, protože "vytvářejí" ​​povolené kombinace kódů (neredukovatelné polynomy jsou tabelovány, viz tabulka 8.4). ) (9). Myšlenka konstrukce cyklického kódu spočívá v tom, že polynom představuje informační část kombinaci kódu, musíte převést na polynom stupně ne více než n-1, který je beze zbytku dělitelný generujícím polynomem P (x). Je podstatné, aby stupeň posledně jmenovaného odpovídal počtu číslic kontrolní části kódového slova. V cyklických kódech mají všechny povolené kombinace, reprezentované jako polynomy, jednu vlastnost: dělitelnost beze zbytku generujícím polynomem P(x). Konstrukce povolené kódové kombinace je následující: 1. Informační část kódové kombinace délky k reprezentujeme jako polynom O(x). 2. Vynásobíme O(x) monomiálním Y a dostaneme 0(x)x r, tj. posuneme kombinaci ¿-bitového kódu o r bitů. 3. Vydělte polynom O(x)x“ generujícím polynomem P(x), jehož stupeň je roven r. Výsledkem vynásobení O(x) x r je stupeň každého monočlenu zahrnutého v O( x) se zvětší o r. Při dělení součinu x r O[x) a tvořící přímku polynomu stupně r získáme kvocient C(x) stejného stupně jako 0(x). Výsledky těchto operací lze znázornit tak jako: (8.28) kde Wx) je zbytek po dělení 0(x)x r P(x). Protože C(x) má stejný stupeň jako 0(x), pak C(x) je kódová kombinace stejného ¿-místného kódu. Stupeň zbytku zjevně nemůže být větší než stupeň generujícího polynomu, tj. nejvyšší stupeň se rovná r-1. Tudíž, největší početčíslice zbytku nepřesahují r. Vynásobením obou stran (8,28) P(x), procházení: (8.29) (znaménko odčítání se nahrazuje znaménkem sčítání modulo 2). Je zřejmé, že F(x) je dělitelné P(x) beze zbytku. Polynom F(x) je povolená kódová kombinace cyklického kódu. Z (8.29) vyplývá, že povolenou kódovou kombinaci cyklického kódu lze získat dvěma způsoby: vynásobením kombinace kódů jednoduchý kód C(x) generujícím polynomem P(x) nebo vynásobením kódové kombinace 0(x) jednoduchého kódu monočlenem x r a přičtením k tomuto součinu zbytku P(x) získaného dělením součinu generujícím polynomem. P(x). U prvního způsobu kódování nejsou informační a kontrolní bity od sebe odděleny (kód je neoddělitelný). To komplikuje praktickou implementaci procesu dekódování. Při druhém způsobu se získá oddělitelný kód: informační číslice obsazují vedoucí pozice, zbývajících n-k číslic jsou testovací. Tato metoda kódování je v praxi široce používána. Příklad 3. Je uvedena kombinace kódů 0111. Sestavme cyklický kód s d o = 3. Řešení. V první fázi určíme na základě požadovaného d o = 3 délku kódu l a počet kontrolních prvků k. K tomu použijeme tabulku 8.6.1. Pro dané čtyřbitové kódové slovo N-16. Pak pro d \u003d 3 ze vztahu 16 (tabulka 8.3) najdeme n - 7, respektive k \u003d n - m - \u003d 7 - 4 \u003d 3. Proto je potřeba kód (7.4). Podle tabulky generátorů polynomů (tab. 8.4) pro k = 3 určíme P (x) = x 3 + x 2 + 1. Dále: 1) pro zprá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) dělení (E (x) x 3 P (x): 4) dostaneme: ^ (x) \u003d O (x) x 3 0 I (x) \u003d x 5 + x 4 + x 3 + 1. Tento polynom odpovídá kombinaci kódu: Všechny tyto operace lze provádět binární čísla: Tabulka 8.4
4) F(0,1) = O(0,l)x 3 (0,l)©R(0 1 l) = 011100000001= 0111 001. Nyní sestrojme povolené kódové slovo prvním způsobem: F(x) =C(x)P(x). Udělejme násobení, reprezentující polynomy jako binární čísla: Je vidět, že ve výsledné kódové kombinaci nelze rozlišit informační a kontrolní bity. Detekce chyb v cyklickém kódování spočívá v dělení přijatého kódového slova stejným generujícím polynomem, který byl použit při kódování (jeho tvar musí být znám na příjmu). Pokud v přijaté kódové kombinaci nejsou žádné chyby (nebo jsou takové, že se daná přenášená kódová kombinace převede na jinou povolenou), pak se beze zbytku provede dělení generujícím polynomem. Pokud dělení vytvoří zbytek, znamená to chybu. Příklad 4. Jako povolenou kombinaci kódů bereme kombinaci kódů získanou v předchozím příkladu: P (x) \u003d x 5 + x 4 + x 3 + 1 a P (x) \u003d x 3 + x 2 + 1, nebo v binárním tvaru E(0,1) = 0111001; P(0,1) = 1101. Předpokládejme, že došlo k chybě v nejvýznamnější (7.) číslici v informační části (číslice se počítají zprava doleva). Přijatá kombinace kódů vypadá jako 1111001. Proveďme operaci detekce chyb: Přítomnost zbytku 110 znamená chybu. Cyklické kódy jsou široce používány v systémech přenosu informací. Například v široce používaném modemovém protokolu \7.42 se pro kódování skupin kódů používá generující polynom q (X) = X 16 + X "-2 + X 5 + 1, což je ekvivalentní kódu 1 0001 0000 0010 0001, stejně jako generující polynom vyššího řá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 + X 4 + X 2 + 1. 8.6.

Mezi efektivní kódy, které detekují jednotlivé, vícenásobné chyby a shluky chyb cyklické kódy(CRC - Cyclic Redundance Code). Jsou vysoce spolehlivé a lze je použít pro blokovou synchronizaci, ve které by byl výběr např. lichého bitu obtížný.

Jednou z variant cyklického kódování je násobení zdrojový kód pomocí generátorového polynomu g(x), a dekódování - v dělení g(x). Pokud zbytek dělení není nula, došlo k chybě. Do vysílače je odeslán chybový signál, který způsobí opakované vysílání.

Generující polynom je binární reprezentace jeden z jednoduchých faktorů, na který se rozkládá číslo Xn-1, kde Xn označuje jednotku v n-tém bitu, n je rovno počtu bitů kódové skupiny. Pokud tedy n \u003d 10 a X \u003d 2, pak X n -1 \u003d 1023 \u003d 11 * 93, a pokud g (X) \u003d 11 nebo in binární kód 1011, pak příklady cyklických kódů A i *g(X) čísel A i v kódové skupině s tímto generujícím polynomem jsou vidět v následující tabulce. 3.1.

Základní možnost V praxi široce používaný cyklický kód se od předchozího liší tím, že operace dělení generujícím polynomem je nahrazena následujícím algoritmem: 1) K původnímu zakódovanému číslu A je přiřazeno K nul, kde K je počet bitů v generující polynom, zmenšený o jednu; 2) na přijatém čísle A * (2 K) se provede operace O, která se od dělení liší tím, že v každém kroku operace se místo odečítání provede bitová operace "výhradní NEBO": 3) výsledný zbytek B je CRC - redundantní K-bitový kód, který v zakódovaném čísle C nahrazuje nuly přiřazené zprava ke K, tzn.

C \u003d A * (2 K) + B.

Na přijímacím konci se na kódu C provede operace O. Pokud se zbytek nerovná nule, pak během přenosu došlo k chybě a je vyžadováno opětovné vysílání kódu A.

PŘÍKLAD Nechť A = 1001 1101 tvoří polynom 11001.

Od K \u003d 4, pak A * (2 K) \u003d 100111010000. Provedení operace O pro výpočet cyklického kódu je znázorněno na Obr. 3.2.

Tabulka 3.1

Číslo	Cyklický kód	Číslo	Cyklický kód
0	0000000000.	13	0010001111
1	0000001011	14	0010011010
2	0000010110	15	0010100101
3	0000100001	16	0011000110
5	0000110111	18	0011000110
6	0001000010	19	0011010001
.....	........	.......	.......

Pozitivní vlastnosti cyklických kódů jsou nízká pravděpodobnost neodhalení chyby a relativně malý počet nadbytečných bitů.

Rýže. 3.2. Příklad získání cyklického kódu