Zpracování multimediálních dat (ZMD)/Cvičení/08-Cyklické kódy

Z CS

Přejít na: navigace, hledání

Obsah

Cyklické kódy

Toto cvičení je věnováno cyklickým (známe spíše pod jménem CRC) kódům. Jedná se o podmnožinu kódů lineárních a v počítačové technice mají velké využití při počítání kontrolních součtů. Používají se výhradně jako kódy detekční. Matematická teorie cyklických kódů je založena na popisu vlastností konečných těles. Specifickou vlastností těchto kódů je vlastnost, podle které se nazývají. Tato vlastnost spočívá v tom, že cyklickým posunem platné kódové složky vzniká opět platná kódová složka. Definice cyklických kódů je tak vzhledem k dalekosáhlým důsledkům překvapivě jednoduchá.


Definice cyklických kódů

Lineární kód se nazývá cyklický, jestliže pro každé kódové slovo v0v1...vn-1 je také vn-1v0v1vn-2 kódovým slovem. Kódová slova můžeme zapisovat jako polynomy, přičemž každý polynom je pouze jiným zápisem kódového slova : v_0v_1v_{n-1}=v_0+v_1\cdot x+...+v_{n-1}\cdot x^{n-1}

Příklad 1

Mějme slovo v abecedě {0,1,2}, např. 2010100.

  • napište toto slovo jako polynom
  • cyklickým posunem vytvářejte další kódová slova

Řešení :

  • napište toto slovo jako polynom
    • podle definice uvedené výše můžeme toto slovo napsat jako polynom 2 + x2 + x4
  • cyklickým posunem vytvářejte další kódová slova
    • cyklickým posunem vznikne slovo 0201010
      • tedy vznikne polynom 2x+x^3+x^5=x\cdot (2+x^2+x^4)
      • což je x-násobkem původního polynomu
    • dalším cyklickým posunem vznikne slovo 0020101
      • tedy vznikne polynom 2x^2+x^4+x^6=x^2\cdot (2+x^2+x^4)
      • což je x2-násobkem původního polynomu
    • atd. můžeme pokračovat


Důsledek

Existuje jediné kódové slovo, tzv. generující polynom, které vytváří celý kód, jelikož kódová slova jsou všechny násobky generujícícho polynomu. Z definice generující matice víme, že tyto polynomy tvoří bázi kódu. Pro generující polynom g(z)(n-k) kódů K tedy platí :

  1. stupeň polynomu g(z) je n-k
  2. kód K sestává ze všech násobků polynomu g(z) v prostoru Tn, tedy : K={q(z)\cdot g(z)|q(z)\in T^n}
  3. polynom g(z), z\cdot g(z),...,z^{k-1}\cdot g(z) tvoří bázi kódu K
  4. polynom g(z) dělí polynom zn-1 beze zbytku

U cyklických kodů můžeme kontrolní matici nahradit tzv. kontrolním polynomem h(z)=\frac{z^{n}-1}{g(z)}

Přístupy k cyklickým kódům

Existuji dva základní přístupy k cyklickým kódům :

  • první přístup : kódové slovo vydělíme generujícím polynomem a zbytek po tomto dělení (představující kontrolní znaky) připojíme za informační část kódového slova. Takto vytvořené slovo je posláno příjemci a je dělitelné generujícím polynomem beze zbytku. Pokud je zbytek po dělení roven nule, slovo přišlo nepoškozeno, v opačném případě slovo přišlo poškozeno
  • druhý přístup : kódové slovo vydělíme generujícím polynomem a zbytek po tomto dělení (představující kontrolní znaky) připojíme před informační část kódového slova. Takto vytvořené slovo je posláno příjemci, ten (na základě stupně generujícího polynomu) rozdělí tuto část slova opět na informační a kontrolní část. Informační část je dělena generujícím polynomem a tento zbytek je porovnán s kontrolními znaky. Pokud se tyto kontrolní znaky (zbytky po dělení generujícím polynomem) rovnají, slovo přišlo nepoškozeno, v opačném případě slovo přišlo poškozeno


Cyklický (n,k) kód

Cyklický (n,k) kód je kód, jehož kódové složky lze vyjádřit mnohočleny stupně n-1 a méně, jež jsou dělitelné beze zbytku generujícím (vytvářejícím) mnohočlenem G(X)stupně r=n-k. Dále dvojčlen xn+1 musí být dělitelny G(x) beze zbytku.

Označme I(x) mnohočlen, jenž reprezentuje přenášenou informaci s k prvky. Postup zabezpečení je pak následující :

  • každý mnohočlen I(x) vyjadřující nebezpečnou informaci se nejprve násobí členem xr, tj. I(x)=I(x)\cdot x^r, čímž se stupeň každého členu polynomu I(x) zvýší o r. To je ekvivalentní připsáni r nul na konec kódové složky [I]. Potom se I'(x) dělí polynomem G(x) :
\frac{I'(x)}{G(x)}=\frac{I(x)\cdot x^r}{G(x)}=Q(x)\oplus\frac{R(x)}{G(x)}


  • dělením vznikne podíl Q(x) a zbytek R(x), který může být nejvýše stupně r-1. Úpravou dostáváme :
I(x)\cdot x^r=Q(x)\cdot G(x)\oplus R(x), nebo také I(x)\cdot x^r\oplus R(x)=Q(x)\cdot G(x)


  • v aritmetice modulo 2 se odčítání shoduje se sčítáním. Pravá strana výše uvedeného vztahu zajišťuje dělitelnost I(x)\cdot x^r\oplus R(x) beze zbytku. Levá strana tvoří zabezpečenou složku n-prvkového kódu :
V(x)=I(x)\cdot x^r\oplus R(x). Zbytek po dělení R(x) tedy určuje zabezpečující prvky.


Generující polynomy cyklického (n,k) kódu

V odvození generujících a kontrolních polynomů cyklických kódů bychom mohli pokračovat, ale to je nad rámec tohoto předmětu. Přes algebru polynomů a faktorové okruhy bychom se postupně dostávali k zavedení generujícícho a kontrolního polynomu cyklického kódu. Dále se tedy budeme zabývat praktickým užitím cyklických (CRC) kódů, a budeme předpokládat, že generujícíc polynomy jsou již dány, například následujcí tabulkou :

Generující mnohočlen     r     (n,k)-kód
G1(x) = x + 1 1 (7,6)
G2(x) = x3 + x + 1 3 (7,4)
G3(x) = x3 + x2 + 1 3 (7,4)
G_4(x)=(x+1)\cdot(x^3+x+1) 4 (7,3)
G_5(x)=(x+1)\cdot(x^3+x^2+1) 4 (7,3)
G_6(x)=(x^3+x+1)\cdot(x^3+x^2+1) 6 (7,1)

Příklad 2

Pro (7,4)-kód ověřte příjem zprávy a učiňte závěr. Použijte prvního přístupu k cyklickým kódům. Výsledek ověřte také použitím generující a kontrolní matice Hammingova kódu.

  • 0001
  • 1111
  • vysvětlete, jakým způsobem se detekuje chyba v přijaté zprávě (prvním přístupem k cyklickým kódům)


Praktické využití CRC při přenosu dat

Příklad 3

Pro zprávu 10000101 vypočtěte CRC-16 kód. Použijte druhého přístupu k cyklickým kódům. Vypočtěte :

  • d(x) - informační část kódu
  • c(x) - kontrolní část kódu
  • v(x) - výsledné zabezpečené slovo
  • vysvětlete, jakým způsobem se detekuje chyba v přijaté zprávě (druhým přístupem k cyklickým kódům)
  • zdůvodněte, proč CRC kódy v praxi využívají druhého přístupu k cyklickým kódům


Podrobnější princip a řešení příkladu (druhy CRC kódů, hardwarová a softwarová implementace, výpočet CRC kódů, ověření kontrolního součtu) je uveden v následujícím článku CRC kódy.

Osobní nástroje
předměty