Odpřednesenou látku naleznete v dodatku A skript Abstraktní a konkrétní lineární algebra

Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky

Perfektn´ı line´ arn´ı k´ ody

Odpˇrednesenou l´ atku naleznete v dodatku A skript Abstraktn´ı a konkrétn´ı line´ arn´ı algebra.

Jiˇr´ı Velebil: B6B01LAG

18.5.2016: Perfektn´ı line´ arn´ı k´ ody

1/18


Minul´ e pˇredn´ aˇsky 1

Detekce a oprava chyb v lineárn´ıch k´ odech.

2

Hamming˚ uv (7, 4)-k´ od.

Dneˇsn´ı pˇredn´ aˇska 1

Kódy perfektn´ı pro opravu t chyb.

2

Obecné Hammingovy k´ ody.

3

Jako aplikaci teorie k´ od˚ u vyˇreˇs´ıme Hat Problem (nepovinné).

Dalˇs´ı moˇ zn´ e doplˇ nuj´ıc´ı informace 1

J. Adámek, Foundations of coding , John Wiley & Sons, 1991

2

D. J. C. MacKay, Information theory, inference and learning algorithms, Cambridge Univ. Press, 2003 Jiˇr´ı Velebil: B6B01LAG


2/18


Definice (perfektn´ı k´ od pro t chyb) ˇ Rekneme, ˇze lineárn´ı k´ od W délky n nad Zp je perfektn´ı pro t chyb, pokud pro kaˇzdé v ze (Zp )n existuje právˇe jedno w z W tak, ˇze dH (w, v) ≤ t. Pozn´ amky 1 K´ od W je perfektn´ı pro t chyb právˇe tehdy, kdyˇz plat´ı [ (Zp )n = Ballt (w) w∈W

kde

Ballt (w) = {v ∈ (Zp )n | dH (w, v) ≤ t} je koule v (Zp )n se stˇredem ve w a polomˇerem t. Toto sjednocen´ı je nav´ıc disjunktn´ı.a Je-li W perfektn´ı pro t chyb, pak dist(W ) = 2t + 1. Takˇze W opravuje t chyb. a Slogan: k´ od W je perfektn´ı pro t chyb pr´ avˇe tehdy, kdyˇz (Zp )n lze pokrýt disjunktn´ımi koulemi se stˇredy v k´ odových slovech a polomˇerem t. Jiˇr´ı Velebil: B6B01LAG


3/18


Pozn´ amky (pokraˇ c.) 2

Poˇcet prvk˚ u jedné koule

Ballt (w) = {v | dH (w, v) = 0} ∪ {v | dH (w, v) = 1} ∪ . . . · · · ∪ {v | dH (w, v) = t − 1} ∪ {v | dH (w, v) = t} je roven souˇctu výbˇer liˇs´ıc´ıch se znak˚ u

z }| { t X n · (p − 1)i , i i=0 | {z }

n n! kde = . i! · (n − i)! i

výbˇer liˇs´ıc´ıch se posic



4/18


Pozn´ amky (pokraˇ c.) 3

Kód W je perfektn´ı pro t chyb právˇe tehdy, kdyˇz plat´ı rovnost t X n n p = (poˇcet slov ve W ) · · (p − 1)i i i=0

V´ıme-li nav´ıc, ˇze W má dimensi k, lze tuto rovnost psát jako t X n n−k · (p − 1)i p = i i=0

protoˇze takové W obsahuje pˇresnˇe p k slov. 4

Pro obecný lineárn´ı k´ od W dimense k opravuj´ıc´ı t chyb plat´ı pouze nerovnost t X n n−k p ≥ · (p − 1)i i i=0

které se ˇr´ıká sphere-packing bound. Jiˇr´ı Velebil: B6B01LAG


5/18


Pozn´ amky 1

Klasifikace perfektn´ıch k´ od˚ u nad Zp existuje, jde vˇsak o tˇeˇzký a hluboký výsledek. Viz napˇr´ıklad knihu W. C. Huffman a V. Pless, Fundamentals of error-correcting codes, Cambridge Univ. Press, 2003

2

Uvid´ıme pˇr´ıklad tˇr´ıdy k´ od˚ u, perfektn´ıch pro 1 chybu. Jde o tˇr´ıdu takzvaných Hammingových k´ od˚ u.

3

Vesm´ırný program NASA pouˇz´ıvá perfektn´ı kódy pro pˇrenos fotografi´ı z druˇzic. Napˇr´ıklad sondy Voyager 1 a Voyager 2 pouˇz´ıvaly pro pˇrenos fotografi´ı Jupitera a Saturnu perfektn´ı k´ od (Golay (24,12,8) code).



6/18


Definice (Hamming˚ uv k´ od) Hamming˚ uv kód je kód nad Z2 délky n = 2m − 1 s kontroln´ı matic´ı HT , která má m ˇrádk˚ u a sloupce matice HT pˇresnˇe odpov´ıdaj´ı binárn´ım zápis˚ um vˇsech ˇc´ısel 1, . . . , 2m − 1, kde m ≥ 1 je pˇrirozené ˇc´ıslo. Pˇr´ıklady Kontroln´ı matice Hammingova k´ odu pro m = 1: T H = (1)

1

0 1

Délka tohoto kódu je 1, dimense 0.a Inf. rate = Kontroln´ı matice Hammingova k´ odu 0 1 HT = 1 0

2

pro m = 2: 1 1

Délka tohoto kódu je 3, dimense 1. Inf. rate = a

= 0.

1 3

= 0.33 . . .

Jde tedy o trivi´ aln´ı k´ od (Z2 )0 = {o}, který nen´ı pˇr´ıliˇs pouˇzitelný. Jiˇr´ı Velebil: B6B01LAG


7/18


Pˇr´ıklady (pokraˇ c.) 3

Kontroln´ı matice Hammingova (7, 4)-k´ odu (zde je m = 3): ! HT =

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Délka tohoto kódu je 7, dimense 4. Inf. rate = 4

Kontroln´ı matice Hammingova k´ odu pro m = 4:  0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

= 0.57 . . .

1 1 0 0

1 1 0 1

Délka tohoto kódu je 15, dimense 11. Inf. rate =

11 15

 HT = 

5

4 7

1 1 1 0

1 1 1 1

  

= 0.73 . . .

Pro obecné m ≥ 1 je délka pˇr´ısluˇsného Hammingova kódu 2m − 1, dimense je rovna 2m − 1 − m a inf. rate je roven 2m − 1 − m m =1− m m 2 −1 2 −1 Jiˇr´ı Velebil: B6B01LAG


8/18


Tvrzen´ı At’ W je Hamming˚ uv k´ od délky n = 2m − 1, m ≥ 2. Potom W je perfektn´ı pro 1 chybu. D˚ ukaz. Chceme ukázat rovnost p n−k =

t X n i=0

i

· (p − 1)i

2m

kde p = 2, t = 1, n = − 1 a k = 2m − 1 − m. Opravdu, plat´ı: m m 2 −1 2 −1 + = 1 + 2m − 1 = 2m = 2n−k 0 1 | {z } | {z } =1

=2m −1



9/18


The Hat Problem (Todd Ebert, 1998) Skupina vˇezˇ n˚ u hraje následuj´ıc´ı hru o svobodu: 1 Kaˇ zdý vˇezeˇ n dostane bud’ ˇcerný nebo b´ılý klobouk (klobouky se rozdáváj´ı náhodnˇe s pravdˇepodobnost´ı 1/2). 2 Kaˇ zdý vid´ı barvy klobouk˚ u ostatn´ıch, barvu svého klobouku nevid´ı nikdo. 3 Skupina hraje jako t´ ym. Vyhraj´ı, pokud alespoˇ n jeden uhodne správnˇe barvu svého klobouku a nikdo ze skupiny nehádá ˇspatnˇe. 4 Pˇ red zaˇcátkem hry se vˇezni na strategii domlouvat mohou, po zaˇcátku hry spolu komunikovat nesm´ı. Simple-minded strategie: hádejme náhodnˇe, pravdˇepodobnost výhry je pak 1/2. Existuje stategie lepˇs´ı? Ano: je-li m ≥ 2, pak pro skupinu n = 2m − 1 vˇezˇ n˚ u pom˚ uˇze pˇr´ısluˇsný Hamming˚ uv k´ od. Jiˇr´ı Velebil: B6B01LAG


10/18


Optim´ aln´ı vyhr´ avac´ı strategie pro Hat Problem Oznaˇcme jako W Hamming˚ uv k´ od délky n = 2m − 1, kde m ≥ 2. n Slova v ze (Z2 ) budeme povaˇzovat za distribuci klobouk˚ u: 1

0 v i-té poloˇzce slova v znamená: vˇezeˇ n i má ˇcerný klobouk.

2

1 v i-té poloˇzce slova v znamená: vˇezeˇ n i má b´ılý klobouk.

Pro zadanou distribuci v definujme slovo vi jako distribuci, která má shodné poloˇzky se slovem v, kromˇe i-té poloˇzky, kde je 0.a Plat´ı rovnost v = vi + ai ei , kde ai ∈ Z2 je pevné. Strategie i-tého vˇeznˇe: 1

Jesliˇze vi + bi ei 6∈ W pro jakékoli bi ze Z2 , vˇezeˇ n i mlˇc´ı.

2

Jesliˇze vi + bi ei ∈ W pro nˇejaké bi ze Z2 , vˇezeˇ n i prohlás´ı, ˇze má klobouk barvy 1 + bi .

a Slovo vi je tedy definov´ ano jako distribuce, kterou i-tý vˇezeˇ n skuteˇcnˇe vid´ı a který pˇredpokl´ ad´ a, ˇze m´ a ˇcerný klobouk.



11/18


Optim´ aln´ı vyhr´ avac´ı strategie pro Hat Problem (pokraˇ c.) Strategie je dobˇre definovaná: nem˚ uˇze souˇcasnˇe platit vi + 0 · ei ∈ W a vi + 1 · ei ∈ W . Kdyby platilo vi + 0 · ei ∈ W a vi + 1 · ei ∈ W , pak souˇcet (vi + 0 · ei ) + (vi + 1 · ei ) = ei leˇz´ı ve W . To nen´ı moˇzné, protoˇze syndrom ei je i-tý sloupec kontroln´ı matice HT a ten je nenulový.a Jestliˇze v nen´ı ve W , strategie dává v´ıtˇezstv´ı.

1

Pokud v nen´ı ve W , existuje jediné j tak, ˇze v + ej je ve W . Hamming˚ uv kód je totiˇz perfektn´ı pro 1 chybu. Vˇezeˇ n j tedy správnˇe uhodl barvu svého klobouku. Nav´ıc vˇsichni ostatn´ı vˇezni museli mlˇcet: pro i 6= j by v opaˇcném pˇr´ıpadˇe muselo platit vi + bi ei ∈ W pro nˇejaké bi . a

Pˇripomenut´ı: kontroln´ı matice Hammingova k´ odu m´ a ve sloupc´ıch bin´ arn´ı z´ apisy nenulových ˇc´ısel 1, . . . , 2m − 1. Jiˇr´ı Velebil: B6B01LAG


12/18


Optim´ aln´ı vyhr´ avac´ı strategie pro Hat Problem (pokraˇ c.) Protoˇze v + ej = vi + ai ei + ej ∈ W a vi + bi ei ∈ W , plat´ı (vi + ai ei + ej ) + (vi + bi ei ) = (ai + bi )ei + ej ∈ W . Syndrom slova (ai + bi )ei + ej je ale nenulový, to je spor. 2

Jesliˇze v je ve W , kaˇzdý hádá ˇspatnˇe. Opravdu: pro kaˇzdé i plat´ı v = vi + ai ei ∈ W a i-tý vˇezeˇ n tedy prohlás´ı, ˇze má klobouk barvy 1 + ai , aˇckoli má ve skuteˇcnosti klobouk barvy ai .



13/18


Optim´ aln´ı vyhr´ avac´ı strategie pro Hat Problem (pokraˇ c.) To znamená, ˇze pravdˇepodobnost výhry pˇri této strategii je pˇresnˇe m

poˇcet slov ve W 22 −1−m 1 1− = 1 − =1− m m −1 n 2 poˇcet slov v (Z2 ) 2 2 1

Napˇr´ıklad pro m = 2 (tedy pro skupinu n = 22 − 1 = 3 vˇezˇ n˚ u) je pravdˇepodobnost výhry 3/4 = 0.75.a

2

Pro m = 3 (tj. pro n = 23 − 1 = 7 vˇezˇ n˚ u) je pravdˇepodobnost výhry 7/8 = 0.875.

3


4


5

Atd.

To je vˇzdy lepˇs´ı výsledek neˇz simple-minded strategie (která dává vˇzdy pravdˇepodobnost 1/2). a

Je uˇziteˇcným cviˇcen´ım si optim´ aln´ı strategii pro m = 2 vyzkouˇset. Jiˇr´ı Velebil: B6B01LAG


14/18


D˚ uleˇ zit´ e upozornˇ en´ı V teorii lineárn´ıch kód˚ u je zvykem psát vektory z Fn do ˇrádku (na rozd´ıl od B6B01LAG). Co t´ım ztrác´ıme a co t´ım z´ıskáváme? 1 Vycviˇ ceni dosavadn´ım pr˚ ubˇehem této pˇrednáˇsky, ztrác´ıme okamˇzitý geometrický pˇrehled o tom, co se pˇri kódován´ı skuteˇcnˇe dˇeje. Pro zájemce: ve skuteˇcnosti geometrický pˇrehled neztrác´ıme; pracujeme jen s kovektory m´ısto s vektory, viz kapitolu 3.5 skript. To znamená, ˇze k´ odován´ı má jasnou geometrickou interpretaci v duáln´ım prostoru. Z´ıskáváme kompatibilitu s rozsáhlou literaturou o kódován´ı. Protoˇze nám ˇslo jen o velmi krátký u ´vod do lineárn´ıch kód˚ u, psali jsme vektory nadále do sloupc˚ u. Kdo bude ˇc´ıst jinou literaturu z kódován´ı, bude velmi pravdˇepodobnˇe muset vˇsechny matice a maticové rovnice z teorie k´ od˚ u transponovat. 2



15/18


Kter´ a line´ arn´ı algebra je tedy ta spr´ avn´ a“? ” n 1 Psan´ ı vektor˚ u z F do sloupc˚ u nám umoˇznilo chápat souˇcin A · x jako funkˇcn´ı hodnotu lineárn´ıho zobrazen´ı A v bodˇe x. Chápán´ı souˇcinu A · x jako funkˇcn´ı hodnoty vedlo k pˇrirozené geometrické interpretaci maticových výpoˇct˚ u. To je ve shodˇe s t´ım, jak znaˇc´ıme funkˇcn´ı hodnoty ve zbytku matematiky: znaˇcku f (x) chápeme jako funkˇcn´ı hodnotu funkce f v bodˇe x. 2

Pˇri psan´ı vektor˚ u z Fn do ˇrádku bychom museli hodnotu lineárn´ıho zobrazen´ı A v bodˇe x znaˇcit x · A. Tento zp˚ usob uvaˇzován´ı o maticovém souˇcinu je ve shodˇe s (menˇsinovým) názorem, ˇze funkˇcn´ı hodnotu funkce f v bodˇe x bychom mˇeli znaˇcit (x)f . Takovému znaˇcen´ı funkˇcn´ıch hodnot se ˇr´ıká reverse Polish notation (RPN). Jiˇr´ı Velebil: B6B01LAG


16/18


Proˇ c jsme v pˇredn´ aˇsce zvolili sloupcovou“ line´ arn´ı algebru? ” 1 Protoˇ ze na RPN nejsme zvykl´ı, zvolili jsme sloupcovou“ ” lineárn´ı algebru. Je totiˇz ve shodˇe s t´ım, jak uvaˇzujeme ve zbytku matematiky. ˇ adková“ lineárn´ı algebra nav´ıc nen´ı ve svém znaˇcen´ı u 2 R´ ´plnˇe ” d˚ usledná. Docház´ı tak k absurditám:a napˇr´ıklad soustava rovnic 2 −1 3 4 7 11 ze sloupcové“ lineárn´ı algebry by se v ˇrádkové“ lineárn´ı ” ” algebˇre mˇela správnˇe zapisovat   2 4  −1 7  3 11 ˇ ale nedˇeje se tak. Rádková“ lineárn´ı algebra pro soustavy ” rovnic pˇreb´ırá zápis sloupcové“ lineárn´ı algebry! ” a Vzpomeˇ nte si, kolikr´ at se v textech z ˇr´ adkové“ line´ arn´ı algebry objevuje ” rˇcen´ı: . . . jednotlivé vektory nyn´ı nap´ıˇseme do sloupc˚ u matice. . .“ ” Jiˇr´ı Velebil: B6B01LAG


17/18


Z´ avˇ ereˇ cn´ e pozn´ amky 1

2

Posledn´ı ˇctyˇri pˇrednáˇsky byly pouze nahlédnut´ım do teorie kód˚ u. Skuteˇcné studium teorie k´ od˚ u vyˇzaduje zvládnut´ı dalˇs´ıch parti´ı matematiky: 1 2 3 4

Teorie informace. Teorie pravdˇepodobnosti. Teorie grup. A dalˇs´ıch. . .

V´ıce se lze dozvˇedˇet v doporuˇcené (tj. nepovinné) literatuˇre.



18/18

Odpřednesenou látku naleznete v dodatku A skript Abstraktní a konkrétní lineární algebra

Recommend Documents