Samoopravné kódy Tomáš Kaiser Katedra matematiky a Institut teoretické informatiky Západočeská univerzita
Seminář pro učitele středních a vysokých škol, Plzeň, 30. března 2012 Tomáš Kaiser
Samoopravné kódy
Samoopravné kódy jsou všude Některé oblasti využití: CD přehrávače mobilní sítě paměti a pevné disky čárové kódy čipové karty kosmický výzkum
Tomáš Kaiser
Samoopravné kódy
Samoopravné kódy jsou všude Některé oblasti využití: CD přehrávače mobilní sítě paměti a pevné disky čárové kódy čipové karty kosmický výzkum
Tomáš Kaiser
Samoopravné kódy
“Otcové zakladatelé”
Richard Hamming (1915–1998)
Claude Shannon (1916–2001)
1950: Error detecting and error correcting codes
1948: A mathematical theory of communication
Tomáš Kaiser
Samoopravné kódy
Detekce chyb
rodné číslo čísla bankovních účtů a kreditních karet IČO síťové protokoly některé paměti RAM
Tomáš Kaiser
Samoopravné kódy
Ilustrační příklad obrázek v 16 stupních šedi, každý bod reprezentován 4 bity například 0000 = černá, 1101 = světle šedá přenos faxem po nekvalitní lince, každý jednotlivý bit se poruší s pravděpodobností p obrazový bod bude přijat správně s pravděpodobností (1 − p)4 takže pro p = 0, 001 bude v průměru 19% bodů chybných Jak zvýšit spolehlivost přenosu? např.: každý bit zopakovat třikrát, přijatou trojici dekódovat podle většiny jen necelé 1% bodů bude chybných, ale cenou je trojnásobný objem dat
Tomáš Kaiser
Samoopravné kódy
Ilustrační příklad obrázek v 16 stupních šedi, každý bod reprezentován 4 bity například 0000 = černá, 1101 = světle šedá přenos faxem po nekvalitní lince, každý jednotlivý bit se poruší s pravděpodobností p obrazový bod bude přijat správně s pravděpodobností (1 − p)4 takže pro p = 0, 001 bude v průměru 19% bodů chybných Jak zvýšit spolehlivost přenosu? např.: každý bit zopakovat třikrát, přijatou trojici dekódovat podle většiny jen necelé 1% bodů bude chybných, ale cenou je trojnásobný objem dat
Tomáš Kaiser
Samoopravné kódy
Hammingův kód obrazový bod (a1 , a2 , a3 , a4 ) zakódujeme do 7-bitového slova (x1 , . . . , x7 ) bity x1 , x2 , x4 jsou kontrolní, ostatní jsou informační do informačních souřadnic zapíšeme a1 , . . . , a4 kontrolní souřadnice dopočítáme (modulo 2) podle rovnic: x4 + x5 + x6 + x7 = 0, x2 + x3 + x6 + x7 = 0, x1 + x3 + x5 + x7 = 0. (v i-té rovnici se objevuje xk , pokud i-tý bit v binárním zápisu čísla k je 1) pro každou čtveřici (a1 , . . . , a4 ) obdržíme kódové slovo: (0 1 1 1) → (0 0 0 1 1 1 1)
Tomáš Kaiser
Samoopravné kódy
Hammingův kód obrazový bod (a1 , a2 , a3 , a4 ) zakódujeme do 7-bitového slova (x1 , . . . , x7 ) bity x1 , x2 , x4 jsou kontrolní, ostatní jsou informační do informačních souřadnic zapíšeme a1 , . . . , a4 kontrolní souřadnice dopočítáme (modulo 2) podle rovnic: x4 + x5 + x6 + x7 = 0, x2 + x3 + x6 + x7 = 0, x1 + x3 + x5 + x7 = 0. (v i-té rovnici se objevuje xk , pokud i-tý bit v binárním zápisu čísla k je 1) pro každou čtveřici (a1 , . . . , a4 ) obdržíme kódové slovo: (0 1 1 1) → (0 0 0 1 1 1 1)
Tomáš Kaiser
Samoopravné kódy
Vlastnosti Hammingova kódu
máme tedy 16 kódových slov délky 7 každá dvě se liší alespoň ve 3 souřadnicích neboli: Hammingova vzdálenost každých dvou slov je ≥ 3) poruší-li se tedy při přenosu nejvýše jeden bit, dokážeme odeslané kódové slovo správně rekonstruovat — kód ‘opravuje jednu chybu’
Tomáš Kaiser
Samoopravné kódy
Maticová formulace Soustavu rovnic, podle které se dopočítávají kontrolní bity, lze zapsat ve tvaru: x1 x2 x3 0 0 , x = A· 4 x5 0 x6 x7 kde
0 0 0 1 1 1 1 A = 0 1 1 0 0 1 1 . 1 0 1 0 1 0 1
Tomáš Kaiser
Samoopravné kódy
Dekódování Hammingova kódu Dejme tomu, že přijaté slovo je y = (y1 , . . . , y7 ). Postup dekódování: pokud Ay T je nulový vektor, ponecháme y beze změny, jinak přečteme Ay T jako binární zápis čísla od 1 do 7 a změníme bit na příslušné souřadnici. Příklad: zdrojová data jsou (0 1 1 1) zakódovali jsme je slovem (0 0 0 1 1 1 1) při přenosu se porušil předposlední bit, výsledkem je slovo (0 0 0 1 1 0 1) součin s maticí A je (1 1 0)T , takže opravíme šestou souřadnici Tomáš Kaiser
Samoopravné kódy
Dekódování Hammingova kódu Dejme tomu, že přijaté slovo je y = (y1 , . . . , y7 ). Postup dekódování: pokud Ay T je nulový vektor, ponecháme y beze změny, jinak přečteme Ay T jako binární zápis čísla od 1 do 7 a změníme bit na příslušné souřadnici. Příklad: zdrojová data jsou (0 1 1 1) zakódovali jsme je slovem (0 0 0 1 1 1 1) při přenosu se porušil předposlední bit, výsledkem je slovo (0 0 0 1 1 0 1) součin s maticí A je (1 1 0)T , takže opravíme šestou souřadnici Tomáš Kaiser
Samoopravné kódy
Ještě k příkladu Při použití Hammingova kódu pro kódování faxové zprávy bude chybných jen 5% bodů (bez kódování to bylo 18%). Jiná situace: je třeba, aby výsledný obrázek byl bezchybný, rozměry jsou 16 × 16 bodů, pravděpodobnost chyby v jednotlivém bitu je 0,1%. Potom: při použití Hammingova kódu (i při ztrojování bitů) je pravděpodobnost úspěchu přes 99%, bez kódování pouze 36%.
Tomáš Kaiser
Samoopravné kódy
Ještě k příkladu Při použití Hammingova kódu pro kódování faxové zprávy bude chybných jen 5% bodů (bez kódování to bylo 18%). Jiná situace: je třeba, aby výsledný obrázek byl bezchybný, rozměry jsou 16 × 16 bodů, pravděpodobnost chyby v jednotlivém bitu je 0,1%. Potom: při použití Hammingova kódu (i při ztrojování bitů) je pravděpodobnost úspěchu přes 99%, bez kódování pouze 36%.
Tomáš Kaiser
Samoopravné kódy
Obecné Hammingovy kódy
analogickou konstrukci lze provést pro každou délku n = 2k − 1 (k ≥ 2) dostáváme kódy délky 2k − 1 s k kontrolními bity a minimální vzdáleností dvou slov ≥ 3 jde o lineární kódy (kódová slova tvoří lineární prostor nad dvouprvkovým tělesem)
Tomáš Kaiser
Samoopravné kódy
Hustota Hammingových kódů Hustota kódu délky n s K slovy: h=
log2 K n
udává zhruba poměr počtu informačních bitů k délce slova hustoty Hammingových kódů: H(3, 1) H(7, 4) H(15, 11) H(31, 26) hustota se blíží jedné jako 1 −
Tomáš Kaiser
0, 333 0, 571 0, 733 0, 839
log n n
Samoopravné kódy
Hammingovy kódy jsou perfektní
Pro kód s délkou 7 a minimální vzdáleností dvou slov ≥ 3 má Hammingův (7, 4)-kód maximální možný počet kódových slov: pro kódové slovo c nechť B(c) je množina všech slov o vzdálenosti ≤ 1 od c pro různá kódová slova c jsou množiny B(c) disjunktní (protože vzdálenost dvou kódových slov je ≥ 3) v každé množině B(c) je 8 slov velikost sjednocení množin B(c) je tedy 8 · 16 = 128, což je přesně počet všech slov délky 7 Podobné kódy se nazývají perfektní, patří mezi ně mj. všechny Hammingovy kódy.
Tomáš Kaiser
Samoopravné kódy
Aplikace Hammingových kódů: disková pole
diskové pole RAID: zařízení obsahující několik synchronizovaných pevných disků řada typů, v původní specifikaci označení Level 0–6 RAID Level 2: ochrana proti výpadku 1 disku pomocí Hammingova kódu příklad konfigurace: 7 disků, z toho 4 informační a 3 kontrolní slovo o 4 bitech se převede na slovo kódu H(7, 4) (délky 7), na každý disk se uloží 1 bit
Tomáš Kaiser
Samoopravné kódy
Hadamardovy kódy a Mariner 9 Mariner 9, první sonda na oběžné dráze kolem jiné planety (Mars, 1971):
Tomáš Kaiser
Samoopravné kódy
Přenos obrázků z Mariner 9
černobílé snímky Marsu s 64 úrovněmi šedi v rozlišení 832 × 700 vlivem kosmického záření a šumu zesilovače mnoho chyb — nutnost kódování za daných podmínek by bylo možné navýšit objem přenášených dat zhruba na pětinásobek (hustota kódu by měla být zhruba 0, 2 nebo více) při odeslání každého bitu 5×: možnost opravy 2 chyb Hadamardův (32, 6)-kód umožnil opravu 7 chyb
Tomáš Kaiser
Samoopravné kódy
Hadamardovy matice Hadamard (1893): Pokud pro prvky komplexní čtvercové matice řádu n platí |aij | ≤ 1, pak |det A| ≤ nn/2 . Hadamardova matice: čtvercová matice H s prvky ±1, kde každé dva řádky se shodují přesně v polovině prvků pro H platí v Hadamardově větě rovnost není těžké dokázat: je-li H řádu n, pak n = 1, 2 nebo násobek 4 Hadamardova hypotéza: pro každý z těchto řádů Hadamardova matice existuje hypotéza dokázána pro n < 668 Tomáš Kaiser
Samoopravné kódy
Hadamardovy matice Hadamard (1893): Pokud pro prvky komplexní čtvercové matice řádu n platí |aij | ≤ 1, pak |det A| ≤ nn/2 . Hadamardova matice: čtvercová matice H s prvky ±1, kde každé dva řádky se shodují přesně v polovině prvků pro H platí v Hadamardově větě rovnost není těžké dokázat: je-li H řádu n, pak n = 1, 2 nebo násobek 4 Hadamardova hypotéza: pro každý z těchto řádů Hadamardova matice existuje hypotéza dokázána pro n < 668 Tomáš Kaiser
Samoopravné kódy
Sylvesterova konstrukce Konstrukce Hadamardových matic řádu 2k : H1 = + + + H2 = + − + + + + + − + − H4 = + + − − + − − +
Hi+1
Hi = Hi
Tomáš Kaiser
Hi −Hi
Samoopravné kódy
Hadamardův (32, 6)-kód Kód použitý pro Mariner 9: H32 = Hadamardova matice řádu 32 (získaná pomocí Sylvesterovy konstrukce) pro každý řádek r provedeme záměnu +
−→
0
−
−→
1
ve vektorech r a −r dostaneme 64 slov délky 32, každé dvě se liší v ≥ 16 souřadnicích výsledný kód opravuje 7 chyb, hustota 6/32 = 0, 188 dostatečná
Tomáš Kaiser
Samoopravné kódy
Reed-Solomonovy kódy
Nechť p je prvočíslo: počítáme modulo p s čísly z množiny Fp = {0, . . . , p − 1} výsledná algebraická struktura je těleso velikosti p pro polynom f (x) s koeficienty z Fp uvažme vektor [f ] = (f (1), f (2), . . . , f (p − 1)) (evaluace polynomu f ) Reed-Solomonův kód RS(p, k) je tvořen všemi slovy [f ], kde f probíhá polynomy stupně < k
Tomáš Kaiser
Samoopravné kódy
Vlastnosti Reed-Solomonových kódů Kód RS(p, k): délka p − 1 p k kódových slov minimální vzdálenost p − k Použití: přehrávače CD a DVD disků (jako součást komplikovanějšího schématu) čtečky čárových kódů dekodéry satelitního vysílání kosmické sondy (Voyager 2 — snímky Saturnu, Uranu a Neptuna)
Tomáš Kaiser
Samoopravné kódy
Vlastnosti Reed-Solomonových kódů Kód RS(p, k): délka p − 1 p k kódových slov minimální vzdálenost p − k Použití: přehrávače CD a DVD disků (jako součást komplikovanějšího schématu) čtečky čárových kódů dekodéry satelitního vysílání kosmické sondy (Voyager 2 — snímky Saturnu, Uranu a Neptuna)
Tomáš Kaiser
Samoopravné kódy
Shannonova věta viděli jsme, že Hammingovy kódy mají sice hustotu rostoucí k 1, ale pravděpodobnost správného dekódování (spolehlivost) klesá k 0 je možné prodlužováním kódu zachovat hustotu a zvyšovat spolehlivost? Shannon (1948): Pro každé p < 1/2 a κ < 1 − H(p) existují kódy s hustotou κ a spolehlivostí libovolně blízkou jedné. pro κ > 1 − H(p) se naopak spolehlivost dlouhých kódů blíží k0
Entropická funkce H(p).
důkazy nekonstruktivní, explicitní konstrukce obtížný problém Tomáš Kaiser
Samoopravné kódy
Shannonova věta viděli jsme, že Hammingovy kódy mají sice hustotu rostoucí k 1, ale pravděpodobnost správného dekódování (spolehlivost) klesá k 0 je možné prodlužováním kódu zachovat hustotu a zvyšovat spolehlivost? Shannon (1948): Pro každé p < 1/2 a κ < 1 − H(p) existují kódy s hustotou κ a spolehlivostí libovolně blízkou jedné. pro κ > 1 − H(p) se naopak spolehlivost dlouhých kódů blíží k0 důkazy nekonstruktivní, explicitní konstrukce obtížný problém Tomáš Kaiser
Entropická funkce H(p). Samoopravné kódy
Literatura
W. Cary Huffman, V. Pless: Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003. J. H. van Lint: Introduction to Coding Theory, Springer, 1998. M. Malek: Coding Theory, poznámky k přednášce na adrese http://www.mcs.csueastbay.edu/~malek/ Class/Hadamard.pdf Wikipedia, hesla Error detection and correction Forward error correction Hamming code
Tomáš Kaiser
Samoopravné kódy
Děkuji za pozornost.
Tomáš Kaiser
Samoopravné kódy
