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´etn´ı line´ arn´ı algebra.
Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
1/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Minul´ e pˇredn´ aˇsky 1
Detekce a oprava chyb v line´arn´ıch k´ odech.
2
Hamming˚ uv (7, 4)-k´ od.
Dneˇsn´ı pˇredn´ aˇska 1
K´ody perfektn´ı pro opravu t chyb.
2
Obecn´e Hammingovy k´ ody.
3
Jako aplikaci teorie k´ od˚ u vyˇreˇs´ıme Hat Problem (nepovinn´e).
Dalˇs´ı moˇ zn´ e doplˇ nuj´ıc´ı informace 1
J. Ad´amek, 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
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
2/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Definice (perfektn´ı k´ od pro t chyb) ˇ Rekneme, ˇze line´arn´ı k´ od W d´elky n nad Zp je perfektn´ı pro t chyb, pokud pro kaˇzd´e v ze (Zp )n existuje pr´avˇe jedno w z W tak, ˇze dH (w, v) ≤ t. Pozn´ amky 1 K´ od W je perfektn´ı pro t chyb pr´avˇ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´yt disjunktn´ımi koulemi se stˇredy v k´ odov´ych slovech a polomˇerem t. Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
3/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Pozn´ amky (pokraˇ c.) 2
Poˇcet prvk˚ u jedn´e 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´ybˇ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´ybˇer liˇs´ıc´ıch se posic
Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
4/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Pozn´ amky (pokraˇ c.) 3
K´od W je perfektn´ı pro t chyb pr´avˇ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´a dimensi k, lze tuto rovnost ps´at jako t X n n−k · (p − 1)i p = i i=0
protoˇze takov´e W obsahuje pˇresnˇe p k slov. 4
Pro obecn´y line´arn´ı 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´e se ˇr´ık´a sphere-packing bound. Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
5/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Pozn´ amky 1
Klasifikace perfektn´ıch k´ od˚ u nad Zp existuje, jde vˇsak o tˇeˇzk´y a hlubok´y v´ysledek. 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´ych Hammingov´ych k´ od˚ u.
3
Vesm´ırn´y program NASA pouˇz´ıv´a perfektn´ı k´ody 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).
Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
6/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Definice (Hamming˚ uv k´ od) Hamming˚ uv k´od je k´od nad Z2 d´elky n = 2m − 1 s kontroln´ı matic´ı HT , kter´a m´a m ˇr´adk˚ u a sloupce matice HT pˇresnˇe odpov´ıdaj´ı bin´arn´ım z´apis˚ um vˇsech ˇc´ısel 1, . . . , 2m − 1, kde m ≥ 1 je pˇrirozen´e ˇc´ıslo. Pˇr´ıklady Kontroln´ı matice Hammingova k´ odu pro m = 1: T H = (1)
1
0 1
D´elka tohoto k´odu je 1, dimense 0.a Inf. rate = Kontroln´ı matice Hammingova k´ odu 0 1 HT = 1 0
2
pro m = 2: 1 1
D´elka tohoto k´odu je 3, dimense 1. Inf. rate = a
= 0.
1 3
= 0.33 . . .
Jde tedy o trivi´ aln´ı k´ od (Z2 )0 = {o}, kter´y nen´ı pˇr´ıliˇs pouˇziteln´y. Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
7/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
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´elka tohoto k´odu 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´elka tohoto k´odu je 15, dimense 11. Inf. rate =
11 15
HT =
5
4 7
1 1 1 0
1 1 1 1
= 0.73 . . .
Pro obecn´e m ≥ 1 je d´elka pˇr´ısluˇsn´eho Hammingova k´odu 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
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
8/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Tvrzen´ı At’ W je Hamming˚ uv k´ od d´elky n = 2m − 1, m ≥ 2. Potom W je perfektn´ı pro 1 chybu. D˚ ukaz. Chceme uk´azat 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
Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
9/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
The Hat Problem (Todd Ebert, 1998) Skupina vˇezˇ n˚ u hraje n´asleduj´ıc´ı hru o svobodu: 1 Kaˇ zd´y vˇezeˇ n dostane bud’ ˇcern´y nebo b´ıl´y klobouk (klobouky se rozd´av´aj´ı n´ahodnˇe s pravdˇepodobnost´ı 1/2). 2 Kaˇ zd´y vid´ı barvy klobouk˚ u ostatn´ıch, barvu sv´eho klobouku nevid´ı nikdo. 3 Skupina hraje jako t´ ym. Vyhraj´ı, pokud alespoˇ n jeden uhodne spr´avnˇe barvu sv´eho klobouku a nikdo ze skupiny neh´ad´a ˇspatnˇe. 4 Pˇ red zaˇc´atkem hry se vˇezni na strategii domlouvat mohou, po zaˇc´atku hry spolu komunikovat nesm´ı. Simple-minded strategie: h´adejme n´ahodnˇe, pravdˇepodobnost v´yhry 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´y Hamming˚ uv k´ od. Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
10/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Optim´ aln´ı vyhr´ avac´ı strategie pro Hat Problem Oznaˇcme jako W Hamming˚ uv k´ od d´elky n = 2m − 1, kde m ≥ 2. n Slova v ze (Z2 ) budeme povaˇzovat za distribuci klobouk˚ u: 1
0 v i-t´e poloˇzce slova v znamen´a: vˇezeˇ n i m´a ˇcern´y klobouk.
2
1 v i-t´e poloˇzce slova v znamen´a: vˇezeˇ n i m´a b´ıl´y klobouk.
Pro zadanou distribuci v definujme slovo vi jako distribuci, kter´a m´a shodn´e poloˇzky se slovem v, kromˇe i-t´e poloˇzky, kde je 0.a Plat´ı rovnost v = vi + ai ei , kde ai ∈ Z2 je pevn´e. Strategie i-t´eho vˇeznˇe: 1
Jesliˇze vi + bi ei 6∈ W pro jak´ekoli bi ze Z2 , vˇezeˇ n i mlˇc´ı.
2
Jesliˇze vi + bi ei ∈ W pro nˇejak´e bi ze Z2 , vˇezeˇ n i prohl´as´ı, ˇze m´a klobouk barvy 1 + bi .
a Slovo vi je tedy definov´ ano jako distribuce, kterou i-t´y vˇezeˇ n skuteˇcnˇe vid´ı a kter´y pˇredpokl´ ad´ a, ˇze m´ a ˇcern´y klobouk.
Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
11/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Optim´ aln´ı vyhr´ avac´ı strategie pro Hat Problem (pokraˇ c.) Strategie je dobˇre definovan´a: 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´e, protoˇze syndrom ei je i-t´y sloupec kontroln´ı matice HT a ten je nenulov´y.a Jestliˇze v nen´ı ve W , strategie d´av´a v´ıtˇezstv´ı.
1
Pokud v nen´ı ve W , existuje jedin´e j tak, ˇze v + ej je ve W . Hamming˚ uv k´od je totiˇz perfektn´ı pro 1 chybu. Vˇezeˇ n j tedy spr´avnˇe uhodl barvu sv´eho klobouku. Nav´ıc vˇsichni ostatn´ı vˇezni museli mlˇcet: pro i 6= j by v opaˇcn´em pˇr´ıpadˇe muselo platit vi + bi ei ∈ W pro nˇejak´e bi . a
Pˇripomenut´ı: kontroln´ı matice Hammingova k´ odu m´ a ve sloupc´ıch bin´ arn´ı z´ apisy nenulov´ych ˇc´ısel 1, . . . , 2m − 1. Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
12/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
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´y, to je spor. 2
Jesliˇze v je ve W , kaˇzd´y h´ad´a ˇspatnˇe. Opravdu: pro kaˇzd´e i plat´ı v = vi + ai ei ∈ W a i-t´y vˇezeˇ n tedy prohl´as´ı, ˇze m´a klobouk barvy 1 + ai , aˇckoli m´a ve skuteˇcnosti klobouk barvy ai .
Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
13/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Optim´ aln´ı vyhr´ avac´ı strategie pro Hat Problem (pokraˇ c.) To znamen´a, ˇze pravdˇepodobnost v´yhry pˇri t´eto 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´yhry 3/4 = 0.75.a
2
Pro m = 3 (tj. pro n = 23 − 1 = 7 vˇezˇ n˚ u) je pravdˇepodobnost v´yhry 7/8 = 0.875.
3
Pro m = 4 (tj. pro n = 24 − 1 = 15 vˇezˇ n˚ u) je pravdˇepodobnost v´yhry 15/16 = 0.9375.
4
Pro m = 5 (tj. pro n = 25 − 1 = 31 vˇezˇ n˚ u) je pravdˇepodobnost v´yhry 31/32 = 0.96875.
5
Atd.
To je vˇzdy lepˇs´ı v´ysledek neˇz simple-minded strategie (kter´a d´av´a vˇzdy pravdˇepodobnost 1/2). a
Je uˇziteˇcn´ym cviˇcen´ım si optim´ aln´ı strategii pro m = 2 vyzkouˇset. Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
14/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
D˚ uleˇ zit´ e upozornˇ en´ı V teorii line´arn´ıch k´od˚ u je zvykem ps´at vektory z Fn do ˇr´adku (na rozd´ıl od B6B01LAG). Co t´ım ztr´ac´ıme a co t´ım z´ısk´av´ame? 1 Vycviˇ ceni dosavadn´ım pr˚ ubˇehem t´eto pˇredn´aˇsky, ztr´ac´ıme okamˇzit´y geometrick´y pˇrehled o tom, co se pˇri k´odov´an´ı skuteˇcnˇe dˇeje. Pro z´ajemce: ve skuteˇcnosti geometrick´y pˇrehled neztr´ac´ıme; pracujeme jen s kovektory m´ısto s vektory, viz kapitolu 3.5 skript. To znamen´a, ˇze k´ odov´an´ı m´a jasnou geometrickou interpretaci v du´aln´ım prostoru. Z´ısk´av´ame kompatibilitu s rozs´ahlou literaturou o k´odov´an´ı. Protoˇze n´am ˇslo jen o velmi kr´atk´y u ´vod do line´arn´ıch k´od˚ u, psali jsme vektory nad´ale do sloupc˚ u. Kdo bude ˇc´ıst jinou literaturu z k´odov´an´ı, bude velmi pravdˇepodobnˇe muset vˇsechny matice a maticov´e rovnice z teorie k´ od˚ u transponovat. 2
Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
15/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Kter´ a line´ arn´ı algebra je tedy ta spr´ avn´ a“? ” n 1 Psan´ ı vektor˚ u z F do sloupc˚ u n´am umoˇznilo ch´apat souˇcin A · x jako funkˇcn´ı hodnotu line´arn´ıho zobrazen´ı A v bodˇe x. Ch´ap´an´ı souˇcinu A · x jako funkˇcn´ı hodnoty vedlo k pˇrirozen´e geometrick´e interpretaci maticov´ych v´ypoˇ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´apeme jako funkˇcn´ı hodnotu funkce f v bodˇe x. 2
Pˇri psan´ı vektor˚ u z Fn do ˇr´adku bychom museli hodnotu line´arn´ıho zobrazen´ı A v bodˇe x znaˇcit x · A. Tento zp˚ usob uvaˇzov´an´ı o maticov´em souˇcinu je ve shodˇe s (menˇsinov´ym) n´azorem, ˇze funkˇcn´ı hodnotu funkce f v bodˇe x bychom mˇeli znaˇcit (x)f . Takov´emu znaˇcen´ı funkˇcn´ıch hodnot se ˇr´ık´a reverse Polish notation (RPN). Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
16/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Proˇ c jsme v pˇredn´ aˇsce zvolili sloupcovou“ line´ arn´ı algebru? ” 1 Protoˇ ze na RPN nejsme zvykl´ı, zvolili jsme sloupcovou“ ” line´arn´ı algebru. Je totiˇz ve shodˇe s t´ım, jak uvaˇzujeme ve zbytku matematiky. ˇ adkov´a“ line´arn´ı algebra nav´ıc nen´ı ve sv´em znaˇcen´ı u 2 R´ ´plnˇe ” d˚ usledn´a. Doch´az´ı tak k absurdit´am:a napˇr´ıklad soustava rovnic 2 −1 3 4 7 11 ze sloupcov´e“ line´arn´ı algebry by se v ˇr´adkov´e“ line´arn´ı ” ” algebˇre mˇela spr´avnˇe zapisovat 2 4 −1 7 3 11 ˇ ale nedˇeje se tak. R´adkov´a“ line´arn´ı algebra pro soustavy ” rovnic pˇreb´ır´a z´apis sloupcov´e“ line´arn´ı algebry! ” a Vzpomeˇ nte si, kolikr´ at se v textech z ˇr´ adkov´e“ line´ arn´ı algebry objevuje ” rˇcen´ı: . . . jednotliv´e vektory nyn´ı nap´ıˇseme do sloupc˚ u matice. . .“ ” Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
17/18
Perfektn´ı line´ arn´ı k´ ody Hammingovy k´ ody Z´ avˇ ereˇ cn´ e pozn´ amky
Z´ avˇ ereˇ cn´ e pozn´ amky 1
2
Posledn´ı ˇctyˇri pˇredn´aˇsky byly pouze nahl´ednut´ım do teorie k´od˚ u. Skuteˇcn´e studium teorie k´ od˚ u vyˇzaduje zvl´adnut´ı 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´e (tj. nepovinn´e) literatuˇre.
Jiˇr´ı Velebil: B6B01LAG
18.5.2016: Perfektn´ı line´ arn´ı k´ ody
18/18