Vytisknout celou knihuVytisknout celou knihu

Bezpečnostní kódování

Stránky: Moodle ZČU
Kurz: KVD/UIN Úvod do informatiky pro vzdělávání - šablona
Kniha: Bezpečnostní kódování
Vytiskl(a): Nepřihlášený host
Datum: neděle, 8. listopadu 2026, 18.10

Obsah

1. Hammingova vzdálenost

Značí se d a jde o počet znaků v nichž se liší dvě kódová slova. Minimální Hammingova vzdálenost se značí d0.

Ukázka pro kód 0010, 1001, 1110:

  • d(0010; 1001) = 3 
  • d0= 2

Detekce je schopnost kódu objevit chybu v přijatém slově.

  • tnásobná chyba může být objevena tehdy, když jet < d0.

Korekce je schopnost opravit chybu v přijatém slově.

  • tnásobná chyba může být opravena tehdy, když je t < d0/2.

Kód s d0 = 3:

  • Detekce dvojnásobné chyby.
  • Korekce jednonásobné chyby.

2. Paritní kódy

Vnější parita spočívá v tom, že se kódová slova doplňují tak, aby obsahovala
sudý či lichý počet jedniček. Rozlišujeme příčnou, podélnou či paritu parit.

Zabezpečení kódu vnější paritou na sudý počet jedníček:

  • 0010|1
  • 1001|0
  • 1110|1
U vnitřní parity má každé kódové slovo v kódu určitý počet jedniček.

Izokód 2 z 5:
  • 00011, 00101, 01001,10001,10010, 10100,11000, 01100, 01010, 00110.

2.1. Cvičení k Hammingově vzdálenosti a paritním kódům

  1. Zabezpečte kódová slova 01, 00, 10, 11 na sudou příčnou paritu.
  2. Zjistěte Hammingovu vzdálenost z kódu z prvního příkladu před a po zabezpečení.

Tipy pro řešení

Podívejte se do předchozích studijních kapitol v této studijní knize.


Návrh řešení

Návrh řešení si prohlédněte, až se pokusíte najít vlastní odpovědi.

 1. Zabezpečte kódová slova 01, 00, 10, 11 na sudou příčnou paritu.

 2. Zjistěte Hammingovu vzdálenost z kódu z prvního příkladu před a po zabezpečení.

3. Lineární kódy

Binární kód K (m, k) nazýváme lineárním, pokud je podprostorem lineárního prostoru {0;1}m.

  • Součet dvou kódových slov je opět kódovým slovem.
  • m – délka kódového slova.
  • k – dimenze podprostoru K. 

3.1. Generující matice

Generující matice je tvořena kódovými slovy, která jsou bází podprostoru kódu.

  • Matice G má m sloupců, k řádků a její hodnost je k.

Systematické lineární kódy

  • Generující matice má na informačních místech jednotkovou submatici.

3.2. Zabezpečení v lineárním kódu

Zabezpečené kódové slovo může vzniknout dvěma způsoby. Prvním z nich je zv = i × G:

  • zv – zabezpečené vyslané kódové slovo.
  • i – nezabezpečené kódové slovo.
  • G – generující matice.

Druhým způsobem je provedení všech možných kombinací součtů kódových slov z generující matice.

V obou případech využijeme sčítání modulo 2:

  • 0 ⨁ 0 = 0
  • 0 ⨁ 1 = 1
  • 1 ⨁ 0 = 1
  • 1 ⨁ 1 = 0


3.3. Cvičení k zabezpečení slov v lineárním kódu

  1. Zabezpečte všechna kódová slova, která může obsahovat lineární kód (5; 3), jehož generující matici G tvoří postupně: 01010, 10011 a 00101, resp. zjistěte všechna kódová slova, která daný kód obsahuje.

Tipy pro řešení

Ideálně si procvičte obě metody a nezapomeňte na zvláštnost u sčítání modulo 2.

Návrh řešení

Návrh řešení si prohlédněte, až se pokusíte najít vlastní odpovědi.

 1. Zabezpečte všechna kódová slova, která může obsahovat lineární kód (5; 3), jehož generující matici G tvoří postupně: 01010, 10011 a 00101.

3.4. Kontrolní matice

Kontrolní matice se značí H a má r řádků a m sloupců.

  • r = m−k
U systematických kódů je tvořena transponovanou submaticí tvořenou zabezpečovací částí doplněnou jednotkovou submaticí.

U nesystematických kódů nejprve G převedeme ekvivalentními úpravami na GS. Po vytvoření HS ji převedeme inverzními ekvivalentními úpravami na H.

3.5. Kontrola přijatého slova

Syndrom s = zp ×HT udává, zda nastala chyba (tedy jestli je s≠0).

  • zp– přijaté slovo.
  • HT– transponovaná kontrolní matice.

Pokud nastala chyba, je evidentní, že zp = zv ⨁ e.

  • e – chybový vektor, který se přidal k zabezpečenému vyslanému slovu zv.

3.6. Hammingovy kódy

Hammingovy kódy Jsou sestaveny tak, aby syndrom s, pokud není nulový, udával svými prvky polohu chybného místa v kódovém slově, pokud v něm došlo k jednonásobné chybě.

  • Prvky vektoru s jsou chápány jako zápis čísla ve dvojkové soustavě.

Pro hodnoty m a r u nich platí navíc vztah 2r = m + 1.

Kontrolní matice H se sestavuje tak, aby její sloupce byly postupně tvořeny posloupností cifer začínající 1, které jsou převedeny do dvojkové soustavy na r bitů.

3.7. Cvičení k Hammingovým kódům

  1. Zjistěte, zda došlo při přijetí slova 0110111 v Hammingově kódu (7; 4) k jednonásobné chybě. Pokud ano, opravte ji.

Tipy pro řešení

Vzpomeňte si, že kontrolní matice má sloupce v podobě binárních kódů jejich pořadí a následně využijte vzorec s = zp × HT. 


Návrh řešení

Návrh řešení si prohlédněte, až se pokusíte najít vlastní odpovědi.

 1. Zjistěte, zda došlo při přijetí slova 0110111 v Hammingově kódu (7; 4) k jednonásobné chybě. Pokud ano, opravte ji.

3.8. Shrnutí

Zdroje

  • ADÁMEK, J. Kódování a teorie informace. Praha: ČVUT, 1991.
  • JIROUŠEK, R. a kol. Principy digitální komunikace. Voznice: Leda, 2006. 309 s.
    ISBN 80-7335-084-X
  • KOCOUREK, P. a J. NOVÁK. Přenos informace. Praha: ČVUT, 2004. 164 s.
    ISBN 80-01-02892-5

4. Typové příklady ke druhému testu z bezpečnostních kódů

  1. Zjistěte všechna kódová slova lineárního kódu zadaného generující maticí a napište, o jaký kód se jedná:
    G = \left[ \begin{matrix} 1 & 0&0&0& 0&1 \\0&1& 0& 0& 1& 0 \\0&0&1& 0&1& 1 \\0& 0& 0& 1& 0& 1\end{matrix} \right]
  2. Zjistěte s pomocí kontrolní matice Hammingova kódu (15; 11), u kterého bitu v přijatém slově došlo k chybě, pokud při přenosu vznikla jednonásobná chyba: zp = 101101101101101

Tipy pro řešení

Podívejte se do odpovídajících předchozích studijních kapitol a cvičení.

U prvního příkladu nezapomeňte určit i m, k a typ kódu. 

U druhého příkladu je třeba sestavit správnou kontrolní matici. 

Pokud se rozhodnete pro řešení v MS Excel, můžete s výhodou využít funkce SOUČIN.MATIC(), MOD() a BIN2DEC().

Návrh řešení

Postup řešení tentokrát cíleně nenabízíme, abyste nebyli neustále zbytečně ovlivňováni. Pokud byste si zvoleným postupem nebyli jisti, samozřejmě kontaktujte vyučujícího (tutora). Po kliknutí zjistíte pro kontrolu alespoň výsledky, ale podívejte se na ně, až po pokusu o vlastní řešení.

5. Cyklické kódy

Cyklické kódy jsou samostatným druhém lineárních (m;k) kódů, v nichž se
kódová slova se od sebe liší v cyklickém posuvu vždy o jeden bit vpravo.

  • – 1011, 1101.

Pro vyjádření kódového slova používáme mnohočlen.

  • 1011 – x0⊕x2⊕x3
Používají se pro schopnost odhalovat shluky chyb (i v síťovém provozu).

5.1. Generující polynom

Cyklické kódy jsou dán g(x) – generujícím polynomem:

  • Musí být dělitelem xm⊕1.
  • Je stupně m-k.
  • Kódová slova jsou jeho násobky.

Např. u kódu (6;4)

  • x6⊕1 = (x2⊕1)∙(x4⊕x2⊕1)
  • g(x) = 101000= x0⊕x2
Zjištění slov u (6; 4):
  • Bázi tvoří x0 × g(x) až xk-1×g(x):101000,010100, 001010,000101.
  • Nulové slovo:000000
  • Násobení g(x) všemi polynomy, které lze vytvořit kombinací členů od x0 po xk-1:111100,100010, 101101,011110, 010001, 001111,110110, 111001, 100111, 011011, 110011.

5.2. Zabezpečení a kontrola

Zabezpečení kódového slova i(x):

  • Děleními(x) × xm-k/g(x)vyjde zbytekr(x), který připojíme na konec i(x), čímž vznikne zv(x).
Kontrola přijatého slova zp(x):
  • Provedeme dělení zp(x)/g(x).
  • Bezezbytku: zp(x) = zv(x).
  • Se zbytkem: zp(x) = zv(x)⊕e(x).

5.3. Shrnutí

Zdroje
  • ADÁMEK, J. Kódování a teorie informace. Praha : ČVUT, 1991.
  • JIROUŠEK, R. a kol. Principy digitální komunikace. Voznice : Leda, 2006. 309 s.
    ISBN 80-7335-084-X
  • KOCOUREK, P., NOVÁK, J. Přenos informace. Praha : ČVUT, 2004. 164 s.
    ISBN 80-01-02892-5