Kombinatorika a grafy I

Kombinatorika a grafy I

Martin Balko

13. pˇredn´ aˇska

21. kvˇetna 2019

Samoopravn´e k´ ody

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u, Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´ey ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u, Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´ey ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u,Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´ey ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u,Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´ey ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u,Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´ey ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u,Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´e y ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u,Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´e y ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u,Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´e y ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u,Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´e y ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u,Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´e y ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula

• Pˇrenos dat, vznikl´e chyby chceme detekovat a opravit.

• Abeceda= mnoˇzina Σs q symboly,slovo d´elky n = uspoˇr´adan´a n-tice symbol˚u,Σⁿ = mnoˇzina slov d´elky n nad Σ.

• Hammingova vzd´alenost slovx = (x₁, . . . ,x_n),y = (y₁, . . . ,y_n)∈Σⁿ je d(x,y)=|{i: xi 6=yi}|.

• K´od= podmnoˇzina C ⊆Σⁿ sk´odov´ymi slovy.

• VC jsme schopni opravit ≤t chyb, pokud pro kaˇzd´e y ∈Σⁿ existuje nanejv´yˇs jednox ∈C s d(x,y)≤t.

• Parametry k´odu: (n,k,d)_q, kde k = log_q|C|a d = minx6=y∈C{d(x,y)}.

• Pˇr´ıklady k´od˚u:

◦ Opakovac´ı k´odC ={1· · ·1,2· · ·2, . . . ,q· · ·q},

◦ k´od z Fanovy roviny C ={charakteristick´e vektory pˇr´ımek},

◦ Hadamard˚uv k´od C ={ˇr´adkyH: H ·H^> =n·I_n} ∪ {ˇr´adky −H}.

Pˇripomenut´ı z minula: line´ arn´ı k´ ody

• Line´arn´ı k´od C je podprostorem vektorov´eho prostoru Kⁿ, kde K'Fq

je koneˇcn´e tˇeleso velikosti q.

• Parametry: [n,k,d]_q, kde k = log_q|C| a d = minx6=y∈C{d(x,y)}.

• V´ıme, ˇze |C|=

F^{dim(Cq )}

=q^k a d = minx∈C\{0}d(x,0).

• Pˇr´ıklady line´arn´ıch k´od˚u:

◦ Opakovac´ı k´od je line´arn´ı,

◦ k´od z Fanovy roviny line´arn´ı nen´ı, ale jeho rozˇs´ıˇren´ı o 1· · ·1 a doplˇnky je,

◦ Hadamard˚uv k´od obecnˇe line´arn´ı nen´ı (ale ten ze Sylvesterovy konstrukce je).

• S line´arn´ımi k´ody um´ıme efektivnˇeji k´odovat i dek´odovat.

Pˇripomenut´ı z minula: line´ arn´ı k´ ody

• Line´arn´ı k´od C je podprostorem vektorov´eho prostoru Kⁿ, kde K'Fq

je koneˇcn´e tˇeleso velikosti q.

• Parametry: [n,k,d]_q, kde k = log_q|C| a d = minx6=y∈C{d(x,y)}.

• V´ıme, ˇze |C|=

F^{dim(Cq )}

=q^k a d = minx∈C\{0}d(x,0).

• Pˇr´ıklady line´arn´ıch k´od˚u:

◦ Opakovac´ı k´od je line´arn´ı,

◦ k´od z Fanovy roviny line´arn´ı nen´ı, ale jeho rozˇs´ıˇren´ı o 1· · ·1 a doplˇnky je,

◦ Hadamard˚uv k´od obecnˇe line´arn´ı nen´ı (ale ten ze Sylvesterovy konstrukce je).

• S line´arn´ımi k´ody um´ıme efektivnˇeji k´odovat i dek´odovat.

Pˇripomenut´ı z minula: line´ arn´ı k´ ody

• Line´arn´ı k´od C je podprostorem vektorov´eho prostoru Kⁿ, kde K'Fq

je koneˇcn´e tˇeleso velikosti q.

• Parametry: [n,k,d]_q, kde k = log_q|C| a d = minx6=y∈C{d(x,y)}.

• V´ıme, ˇze |C|=

F^{dim(Cq )}

=q^k a d = minx∈C\{0}d(x,0).

• Pˇr´ıklady line´arn´ıch k´od˚u:

◦ Opakovac´ı k´od je line´arn´ı,

◦ k´od z Fanovy roviny line´arn´ı nen´ı, ale jeho rozˇs´ıˇren´ı o 1· · ·1 a doplˇnky je,

◦ Hadamard˚uv k´od obecnˇe line´arn´ı nen´ı (ale ten ze Sylvesterovy konstrukce je).

• S line´arn´ımi k´ody um´ıme efektivnˇeji k´odovat i dek´odovat.

Pˇripomenut´ı z minula: line´ arn´ı k´ ody

• Line´arn´ı k´od C je podprostorem vektorov´eho prostoru Kⁿ, kde K'Fq

je koneˇcn´e tˇeleso velikosti q.

• Parametry: [n,k,d]_q, kde k = log_q|C| a d = minx6=y∈C{d(x,y)}.

• V´ıme, ˇze |C|=

F^{dim(Cq )}

=q^k a d = minx∈C\{0}d(x,0).

• Pˇr´ıklady line´arn´ıch k´od˚u:

◦ Opakovac´ı k´od je line´arn´ı,

◦ k´od z Fanovy roviny line´arn´ı nen´ı, ale jeho rozˇs´ıˇren´ı o 1· · ·1 a doplˇnky je,

◦ Hadamard˚uv k´od obecnˇe line´arn´ı nen´ı (ale ten ze Sylvesterovy konstrukce je).

• S line´arn´ımi k´ody um´ıme efektivnˇeji k´odovat i dek´odovat.

Pˇripomenut´ı z minula: line´ arn´ı k´ ody

• Line´arn´ı k´od C je podprostorem vektorov´eho prostoru Kⁿ, kde K'Fq

je koneˇcn´e tˇeleso velikosti q.

• Parametry: [n,k,d]_q, kde k = log_q|C| a d = minx6=y∈C{d(x,y)}.

• V´ıme, ˇze |C|=

F^{dim(Cq )}

=q^k a d = minx∈C\{0}d(x,0).

• Pˇr´ıklady line´arn´ıch k´od˚u:

◦ Opakovac´ı k´od je line´arn´ı,

◦ k´od z Fanovy roviny line´arn´ı nen´ı, ale jeho rozˇs´ıˇren´ı o 1· · ·1 a doplˇnky je,

◦ Hadamard˚uv k´od obecnˇe line´arn´ı nen´ı (ale ten ze Sylvesterovy konstrukce je).

• S line´arn´ımi k´ody um´ıme efektivnˇeji k´odovat i dek´odovat.

Pˇripomenut´ı z minula: line´ arn´ı k´ ody

• Line´arn´ı k´od C je podprostorem vektorov´eho prostoru Kⁿ, kde K'Fq

je koneˇcn´e tˇeleso velikosti q.

• Parametry: [n,k,d]_q, kde k = log_q|C| a d = minx6=y∈C{d(x,y)}.

• V´ıme, ˇze |C|=

F^{dim(Cq )}

=q^k a d = minx∈C\{0}d(x,0).

• Pˇr´ıklady line´arn´ıch k´od˚u:

◦ Opakovac´ı k´od je line´arn´ı,

◦ k´od z Fanovy roviny line´arn´ı nen´ı, ale jeho rozˇs´ıˇren´ı o 1· · ·1 a doplˇnky je,

◦ Hadamard˚uv k´od obecnˇe line´arn´ı nen´ı (ale ten ze Sylvesterovy konstrukce je).

• S line´arn´ımi k´ody um´ıme efektivnˇeji k´odovat i dek´odovat.

Pˇripomenut´ı z minula: line´ arn´ı k´ ody

• Line´arn´ı k´od C je podprostorem vektorov´eho prostoru Kⁿ, kde K'Fq

je koneˇcn´e tˇeleso velikosti q.

• Parametry: [n,k,d]_q, kde k = log_q|C| a d = minx6=y∈C{d(x,y)}.

• V´ıme, ˇze |C|=

F^{dim(Cq )}

=q^k a d = minx∈C\{0}d(x,0).

• Pˇr´ıklady line´arn´ıch k´od˚u:

◦ Opakovac´ı k´od je line´arn´ı,

◦ k´od z Fanovy roviny line´arn´ı nen´ı, ale jeho rozˇs´ıˇren´ı o 1· · ·1 a doplˇnky je,

◦ Hadamard˚uv k´od obecnˇe line´arn´ı nen´ı (ale ten ze Sylvesterovy konstrukce je).

• S line´arn´ımi k´ody um´ıme efektivnˇeji k´odovat i dek´odovat.

Pˇripomenut´ı z minula: line´ arn´ı k´ ody

• Line´arn´ı k´od C je podprostorem vektorov´eho prostoru Kⁿ, kde K'Fq

je koneˇcn´e tˇeleso velikosti q.

• Parametry: [n,k,d]_q, kde k = log_q|C| a d = minx6=y∈C{d(x,y)}.

• V´ıme, ˇze |C|=

F^{dim(Cq )}

=q^k a d = minx∈C\{0}d(x,0).

• Pˇr´ıklady line´arn´ıch k´od˚u:

◦ Opakovac´ı k´od je line´arn´ı,

◦ k´od z Fanovy roviny line´arn´ı nen´ı, ale jeho rozˇs´ıˇren´ı o 1· · ·1 a doplˇnky je,

◦ Hadamard˚uv k´od obecnˇe line´arn´ı nen´ı (ale ten ze Sylvesterovy konstrukce je).

• S line´arn´ımi k´ody um´ıme efektivnˇeji k´odovat i dek´odovat.

Pˇripomenut´ı z minula: line´ arn´ı k´ ody

• Line´arn´ı k´od C je podprostorem vektorov´eho prostoru Kⁿ, kde K'Fq

je koneˇcn´e tˇeleso velikosti q.

• Parametry: [n,k,d]_q, kde k = log_q|C| a d = minx6=y∈C{d(x,y)}.

• V´ıme, ˇze |C|=

F^{dim(Cq )}

=q^k a d = minx∈C\{0}d(x,0).

• Pˇr´ıklady line´arn´ıch k´od˚u:

◦ Opakovac´ı k´od je line´arn´ı,

◦ k´od z Fanovy roviny line´arn´ı nen´ı, ale jeho rozˇs´ıˇren´ı o 1· · ·1 a doplˇnky je,

◦ Hadamard˚uv k´od obecnˇe line´arn´ı nen´ı (ale ten ze Sylvesterovy konstrukce je).

• S line´arn´ımi k´ody um´ıme efektivnˇeji k´odovat i dek´odovat.

K´ od s parametry [7, 4, 3]

z Fanovy roviny

• Z Fanovy roviny:

1100001,0000111,1010100,1001010,0011001,0101100,0110010,1111111 0011110,1111000,0101011,0110101,1100110,1010011,1001101,0000000

• Ekvivalentn´ı k´od: Generuj´ıc´ı matice:

M =









1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0









Kontroln´ı matice: M^⊥ =





1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1





• K´odov´an´ı: z = (1,0,1,1)^>→x =M^>z = (1,0,1,1,1,0,0)^>.

• Dek´odov´an´ı: y = (1,0,0,1,1,0,0)^> →s(y)=M^⊥y = (1,0,1)^>. s⁻¹(s(y)) =s⁻¹((1,0,1)^>) = (0,0,1,0,0,0,0)^> ∈B(0,1)

x =y −s⁻¹(s(y)) = (1,0,0,1,1,0,0)^>−(0,0,1,0,0,0,0)^>

= (1,0,1,1,1,0,0)^> → z = (1,0,1,1)^>

K´ od s parametry [7, 4, 3]

z Fanovy roviny

• Z Fanovy roviny:

1100001,0000111,1010100,1001010,0011001,0101100,0110010,1111111 0011110,1111000,0101011,0110101,1100110,1010011,1001101,0000000

• Ekvivalentn´ı k´od: Generuj´ıc´ı matice:

M =









1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0









Kontroln´ı matice: M^⊥ =





1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1





• K´odov´an´ı: z = (1,0,1,1)^>→x =M^>z = (1,0,1,1,1,0,0)^>.

• Dek´odov´an´ı: y = (1,0,0,1,1,0,0)^> →s(y)=M^⊥y = (1,0,1)^>. s⁻¹(s(y)) =s⁻¹((1,0,1)^>) = (0,0,1,0,0,0,0)^> ∈B(0,1)

x =y −s⁻¹(s(y)) = (1,0,0,1,1,0,0)^>−(0,0,1,0,0,0,0)^>

= (1,0,1,1,1,0,0)^> → z = (1,0,1,1)^>

K´ od s parametry [7, 4, 3]

z Fanovy roviny

• Z Fanovy roviny:

1100001,0000111,1010100,1001010,0011001,0101100,0110010,1111111 0011110,1111000,0101011,0110101,1100110,1010011,1001101,0000000

• Ekvivalentn´ı k´od:

Generuj´ıc´ı matice:

M =









1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0









Kontroln´ı matice:

M^⊥ =





1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1





• K´odov´an´ı: z = (1,0,1,1)^>→x =M^>z = (1,0,1,1,1,0,0)^>.

• Dek´odov´an´ı: y = (1,0,0,1,1,0,0)^> →s(y)=M^⊥y = (1,0,1)^>. s⁻¹(s(y)) =s⁻¹((1,0,1)^>) = (0,0,1,0,0,0,0)^> ∈B(0,1)

x =y −s⁻¹(s(y)) = (1,0,0,1,1,0,0)^>−(0,0,1,0,0,0,0)^>

= (1,0,1,1,1,0,0)^> → z = (1,0,1,1)^>

K´ od s parametry [7, 4, 3]

z Fanovy roviny

• Z Fanovy roviny:

1100001,0000111,1010100,1001010,0011001,0101100,0110010,1111111 0011110,1111000,0101011,0110101,1100110,1010011,1001101,0000000

• Ekvivalentn´ı k´od:

Generuj´ıc´ı matice:

M =









1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0









Kontroln´ı matice:

M^⊥ =





1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1





• K´odov´an´ı: z = (1,0,1,1)^>→x =M^>z = (1,0,1,1,1,0,0)^>.

• Dek´odov´an´ı: y = (1,0,0,1,1,0,0)^> →s(y)=M^⊥y = (1,0,1)^>. s⁻¹(s(y)) =s⁻¹((1,0,1)^>) = (0,0,1,0,0,0,0)^> ∈B(0,1)

x =y −s⁻¹(s(y)) = (1,0,0,1,1,0,0)^>−(0,0,1,0,0,0,0)^>

= (1,0,1,1,1,0,0)^> → z = (1,0,1,1)^>

K´ od s parametry [7, 4, 3]

z Fanovy roviny

• Z Fanovy roviny:

1100001,0000111,1010100,1001010,0011001,0101100,0110010,1111111 0011110,1111000,0101011,0110101,1100110,1010011,1001101,0000000

• Ekvivalentn´ı k´od:

Generuj´ıc´ı matice:

M =









1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0









Kontroln´ı matice:

M^⊥ =





1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1





• K´odov´an´ı: z = (1,0,1,1)^>→x =M^>z = (1,0,1,1,1,0,0)^>.

• Dek´odov´an´ı: y = (1,0,0,1,1,0,0)^> →s(y)=M^⊥y = (1,0,1)^>.

s⁻¹(s(y)) =s⁻¹((1,0,1)^>) = (0,0,1,0,0,0,0)^> ∈B(0,1)

x =y −s⁻¹(s(y)) = (1,0,0,1,1,0,0)^>−(0,0,1,0,0,0,0)^>

= (1,0,1,1,1,0,0)^> → z = (1,0,1,1)^>

K´ od s parametry [7, 4, 3]

z Fanovy roviny

• Z Fanovy roviny:

1100001,0000111,1010100,1001010,0011001,0101100,0110010,1111111 0011110,1111000,0101011,0110101,1100110,1010011,1001101,0000000

• Ekvivalentn´ı k´od:

Generuj´ıc´ı matice:

M =









1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0









Kontroln´ı matice:

M^⊥ =





1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1





• K´odov´an´ı: z = (1,0,1,1)^>→x =M^>z = (1,0,1,1,1,0,0)^>.

• Dek´odov´an´ı: y = (1,0,0,1,1,0,0)^> →s(y)=M^⊥y = (1,0,1)^>. s⁻¹(s(y)) =s⁻¹((1,0,1)^>) = (0,0,1,0,0,0,0)^>∈B(0,1)

x =y −s⁻¹(s(y)) = (1,0,0,1,1,0,0)^>−(0,0,1,0,0,0,0)^>

= (1,0,1,1,1,0,0)^> → z = (1,0,1,1)^>

K´ od s parametry [7, 4, 3]

z Fanovy roviny

• Z Fanovy roviny:

1100001,0000111,1010100,1001010,0011001,0101100,0110010,1111111 0011110,1111000,0101011,0110101,1100110,1010011,1001101,0000000

• Ekvivalentn´ı k´od:

Generuj´ıc´ı matice:

M =









1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0









Kontroln´ı matice:

M^⊥ =





1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1





• K´odov´an´ı: z = (1,0,1,1)^>→x =M^>z = (1,0,1,1,1,0,0)^>.

• Dek´odov´an´ı: y = (1,0,0,1,1,0,0)^> →s(y)=M^⊥y = (1,0,1)^>. s⁻¹(s(y)) =s⁻¹((1,0,1)^>) = (0,0,1,0,0,0,0)^>∈B(0,1)

x =y −s⁻¹(s(y)) = (1,0,0,1,1,0,0)^>−(0,0,1,0,0,0,0)^>

= (1,0,1,1,1,0,0)^> → z = (1,0,1,1)^>

Zkouˇsky

• Pr˚ubˇeh zkouˇsky:

◦ Ustn´ı s p´ısemnou pˇr´ıpravou. Maxim´´ alnˇe na 4 hodiny (09:00–13:00 nebo 14:00–18:00).

◦ 5 ot´azek, z toho 3 na ovˇeˇren´ı z´akladn´ıch pojm˚u a jejich aplikace, 1 na ovˇeˇren´ı znalosti d˚ukaz˚u z pˇredn´aˇsky a 1 pˇrehledov´a.

◦ Vzorov´e zad´an´ı je na str´ank´ach pˇredn´aˇsky.

• Term´ıny:

◦ 28.5. – dopoledne + odpoledne

◦ 31.5. – dopoledne + odpoledne

◦ 5.6. – dopoledne + odpoledne

◦ 7.6. – dopoledne + odpoledne

◦ 12.6. – dopoledne + odpoledne

◦ 13.6. – dopoledne + odpoledne

◦ 25.6. – dopoledne

• Rozsah: vˇse, co jsme probrali (viz rozpis jednotliv´ych pˇredn´aˇsek).

Zkouˇsky

• Pr˚ubˇeh zkouˇsky:

◦ Ustn´ı s p´ısemnou pˇr´ıpravou. Maxim´´ alnˇe na 4 hodiny (09:00–13:00 nebo 14:00–18:00).

◦ 5 ot´azek, z toho 3 na ovˇeˇren´ı z´akladn´ıch pojm˚u a jejich aplikace, 1 na ovˇeˇren´ı znalosti d˚ukaz˚u z pˇredn´aˇsky a 1 pˇrehledov´a.

◦ Vzorov´e zad´an´ı je na str´ank´ach pˇredn´aˇsky.

• Term´ıny:

◦ 28.5. – dopoledne + odpoledne

◦ 31.5. – dopoledne + odpoledne

◦ 5.6. – dopoledne + odpoledne

◦ 7.6. – dopoledne + odpoledne

◦ 12.6. – dopoledne + odpoledne

◦ 13.6. – dopoledne + odpoledne

◦ 25.6. – dopoledne

• Rozsah: vˇse, co jsme probrali (viz rozpis jednotliv´ych pˇredn´aˇsek).

Zkouˇsky

• Pr˚ubˇeh zkouˇsky:

◦ Ustn´ı s p´ısemnou pˇr´ıpravou. Maxim´´ alnˇe na 4 hodiny (09:00–13:00 nebo 14:00–18:00).

◦ 5 ot´azek, z toho 3 na ovˇeˇren´ı z´akladn´ıch pojm˚u a jejich aplikace, 1 na ovˇeˇren´ı znalosti d˚ukaz˚u z pˇredn´aˇsky a 1 pˇrehledov´a.

◦ Vzorov´e zad´an´ı je na str´ank´ach pˇredn´aˇsky.

• Term´ıny:

◦ 28.5. – dopoledne + odpoledne

◦ 31.5. – dopoledne + odpoledne

◦ 5.6. – dopoledne + odpoledne

◦ 7.6. – dopoledne + odpoledne

◦ 12.6. – dopoledne + odpoledne

◦ 13.6. – dopoledne + odpoledne

◦ 25.6. – dopoledne

• Rozsah: vˇse, co jsme probrali (viz rozpis jednotliv´ych pˇredn´aˇsek).

Zkouˇsky

• Pr˚ubˇeh zkouˇsky:

◦ Ustn´ı s p´ısemnou pˇr´ıpravou. Maxim´´ alnˇe na 4 hodiny (09:00–13:00 nebo 14:00–18:00).

◦ 5 ot´azek, z toho 3 na ovˇeˇren´ı z´akladn´ıch pojm˚u a jejich aplikace, 1 na ovˇeˇren´ı znalosti d˚ukaz˚u z pˇredn´aˇsky a 1 pˇrehledov´a.

◦ Vzorov´e zad´an´ı je na str´ank´ach pˇredn´aˇsky.

• Term´ıny:

◦ 28.5. – dopoledne + odpoledne

◦ 31.5. – dopoledne + odpoledne

◦ 5.6. – dopoledne + odpoledne

◦ 7.6. – dopoledne + odpoledne

◦ 12.6. – dopoledne + odpoledne

◦ 13.6. – dopoledne + odpoledne

◦ 25.6. – dopoledne

• Rozsah: vˇse, co jsme probrali (viz rozpis jednotliv´ych pˇredn´aˇsek).

Zkouˇsky

• Pr˚ubˇeh zkouˇsky:

◦ Ustn´ı s p´ısemnou pˇr´ıpravou. Maxim´´ alnˇe na 4 hodiny (09:00–13:00 nebo 14:00–18:00).

◦ 5 ot´azek, z toho 3 na ovˇeˇren´ı z´akladn´ıch pojm˚u a jejich aplikace, 1 na ovˇeˇren´ı znalosti d˚ukaz˚u z pˇredn´aˇsky a 1 pˇrehledov´a.

◦ Vzorov´e zad´an´ı je na str´ank´ach pˇredn´aˇsky.

• Term´ıny:

◦ 28.5. – dopoledne + odpoledne

◦ 31.5. – dopoledne + odpoledne

◦ 5.6. – dopoledne + odpoledne

◦ 7.6. – dopoledne + odpoledne

◦ 12.6. – dopoledne + odpoledne

◦ 13.6. – dopoledne + odpoledne

◦ 25.6. – dopoledne

• Rozsah: vˇse, co jsme probrali (viz rozpis jednotliv´ych pˇredn´aˇsek).

Dˇekuji za pozornost a pˇreji hodnˇe ˇstˇest´ı u zkouˇsek.

Dˇekuji za pozornost a pˇreji hodnˇe ˇstˇest´ı u zkouˇsek.

Dˇekuji za pozornost a pˇreji hodnˇe ˇstˇest´ı u zkouˇsek.