Samoopravné kódy – princip, Hammingova metrika, geometrická interpretace, kódová vzdálenost, systematický a nesystematický lineární kód, kontrolní a generující matice, syndrom chyby, uvést příklad kódu včetně konstrukce

Samoopravné kódy – princip, Hammingova metrika, geometrická interpretace, kódová vzdálenost, systematický a nesystematický lineární kód, kontrolní a generující matice, syndrom chyby, uvést příklad kódu včetně konstrukce

Bezpečnostní kódy jsou v zásadě dvojího typu:

Detekční kódy – error-detection codes, které umožňují pouze rozpoznat(detekovat), že přijatý znak je chybný

Korekční kódy – resp. Samoopravné kódy – self-correcting codes, které kromě detekce chyby umožňují i opravu chybně přeneseného znaku, takže jej není nutné přenášet znovu (což u detekčního kódu obecně nutné je)

Hammingova vzdálenost

Hammingova vzdálenost δ_H dvou slov v ₁v₂ …v_n a w₁ w₂ …w_n je definována jako počet odlišných znaků těchto slov, tj. velikost množiny .

VÁHA w kódové složky je dána počtem jedniček v kódové složce. Nejvyšší vahou je pak myšlen jedničkový bit umístěný nejvíce vlevo.

MINIMÁLNÍ (KÓDOVÁ) VZDÁLENOST d, blokového kódu K, je spočtena jako minimální Hammingova vzdálenost mezi dvěma různými kódovými složkami. Kódová vzdálenost je důležitou charakteristikou kódu z hlediska jeho zabezpečující schopnosti proti chybám. S rostoucím D se zvyšuje zabezpe ovací schopnost kódu, bohužel roste též jeho redundance.

Příklad: Výpočet Hammingovy vzdálenosti

10110 11001100

01110 01010101

11000 -> 2 10011001 -> 4

K výpočtu byla užita operace sčítání modulo 2, označovaná jako „“. Tato operace je ekvivalentní odčítání modulo 2. Pro praktickou realizaci je použita logická operace XOR.

Hammingovu vzdálenost dvou kódových složek můžeme geometricky interpretovat jako počet hran krychle kterými je třeba projít na cestě vedoucí od jedné složky ke druhé.

Hammingova vzdálenost je metrikou na množině Tⁿ všech slov délky n.

Blokový kód minimální vzdálenosti d objevuje t-násobné chyby pro všechna t < d, ale není schopen objevit všechny d-násobné chyby. To znamená, že pokud v kódovém slově změníme t znaků, potom:

a) nevznikne kódové slovo, jestliže t ≤ d-1,

b) může vzniknout kódové slovo, jestliže t = d.

Geometrická reprezentace kódu

Uspořádanou posloupnost prvků kódové složky můžeme považovat za souřadnice bodu v n-rozměrném euklidovském prostoru. Danou kódovou složku můžeme tedy znázornit jako bod v prostoru. Např. tříprvkový binární kód lze znázornit pomocí trojrozměrné krychle o hraně jednotkové délky (viz Obr.1).

Obr. 1 Geometrické znázornění 3-prvkového dvojkového kódu

A = (a1, a2, a3 )

Kódová vzdálenost

Vzdálenost d (Ai, Aj) dvou kódových složek je dána počtem míst, ve kterých se obě složky Ai, Aj liší. Z hlediska geometrického modelu je vzdálenost kódových složek Ai a Aj dána počtem hran krychle, kterými je třeba projít na cestě z vrcholu Ai do vrchu Aj. Váha w kódové složky je dána počtem jedniček v kódové složce. Pravidla pro sčítání a odčítání modulo 2 jsou na Obr. 2:

Obr. 2: Princip detekce chyb kontrolu kvality signálu

kde symbol označuje operaci sčítání modulo 2, symbol označuje operaci odčítání modulo 2.

Je vidět, že není rozdíl ve výsledku mezi sčítáním a odečítáním u operaci modulo 2. Tady rozdíl dvou kódových složek dává stejný výsledek jako jejich součet. Vzdálenost dvou kódových složek zjistíme podle:

d(Ai, Aj) = w (Ai Aj) = w (Ai Aj)

Např. d(A1, A2) podle obrázku 1: d(A1, A2) = w (001 010) = w(011) = 2

Úplný obraz o vzdálenostech mezi kódovými složkami daného kódu poskytuje matice vzdálenosti. Např. tříprvkový binární kód se složkami A1 = 001, A2 = 010, A3 = 100, A4 = 111 má matici vzdálenosti:

Nejmenší vzdálenost vyskytující se mezi kódovými složkami daného kódu se nazývá kódová vzdálenost D:

D = min d (Ai, Aj),

Která je důležitou charakteristikou kódu z hlediska jeho zabezpečující schopnosti proti chybám. Čím je D větší, tím mohou být vlastnosti bezpečnostního kódu lepší.

Systematický a nesystematický lineární kód

Systematický kódy jsou ty lineární kódy, které mají generující matici tvaru:

G = [ E | B

kde E je jednotková matice řádu k, a platí:

Kontrolní matice

Definice (kontrolní matice): Kontrolní matice lineárního kódu K je taková matice H z prvků

abecedy T, pro kterou platí:

slovo v = v₁ v₂ … v_n (v Tⁿ ) je kódové, právě když splňuje následující podmínku.

Věta: Lineární kód s generující maticí G = [E_k | B] má kontrolní matici H = [-B^T | E'_n-k ],

kde B^T je transponovaná matice B a E'_n-k je jednotková matice.

Generující matice

Lineární (n, k)-kód má celkem q^k kódových slov, protože kódová slova můžeme vyjádřit k souřadnicemi ve zvolené bázi a každá souřadnice má q možných hodnot. Kód je q- znakový,

jestliže abeceda T (těleso) má počet znaků q.

Lineární (n, k)-kód s k ≠ 0 je určen svojí (libovolnou) bází b₁ ,b₂ ,…,b_k . Pokud napíšeme těchto

k slov (bází) pod sebe, vznikne tzv. generující matice daného kódu G.

G = [b₁ b₂ . . . b_k ] ^T

Matice G typu (n,k) je generující maticí lineárního kódu, jestliže:

• každý její řádek je kódovým slovem,
• každé kódové slovo je lineární kombinací řádků,
• řádky jsou lineárně nezávislé, takže hodnost matice G je rovna k.

Příklad: Binární kód celkové kontroly parity v délce n=4, má následující generující matici:

Syndrom chyby

Bezpečnostní kódování informace odpovídá vztahu:

dále tedy vyslaný zabezpečený kód: [ V ] = [ I ] [ G ],

[ I ] – informace,

[ G ] – generující matice kódu

Přijatý kód s možnou chybou: [ P ] = [ V ] [ E_rr ]

Musí platit, že

,

pokud ne, je pravá strana označována jako tzv. syndrom chyby [ S ], protože platí:

[ S ] ^T = [ H ] [ P ]^T = [ H ] ([ V ]^T [ E ]^T) = [ H ] [ V ]^T [ H ] [ E ]^T = [ H ] . [ E ] ^T

Syndrom [ S ] udává svými prvky, chápanými jako zápis čísla ve dvojkové soustavě, polohu chybného místa v kódové složce.

Příklad:

(7, 4)-kód, přijaté slovo 1010111

Matice

-> opravíme tedy šestý znak!