Diskrétní matematika - cvičení 7. týden Lukáš Vokřínek Masarykova univerzita Fakulta informatiky jaro 2020 Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. ■v Řešení 00-10 Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. ■v Řešení 00-10 Príklad Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. Řešení Príklad Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. Řešení Príklad Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. Řešení Jestliže má kód opravovat jednoduché chyby, musí být okolí kódových slov poloměru 1 disjunktní (tj. slova musí mít vzdálensot alespoň 3). Jestliže jsou kódová slova délky £, pak takové okolí obsahuje právě £ + 1 slov. Musí proto být 4(^+1) < 2 £ {7r je počet všech slov délky £), což přímým ověřením neplatí pro £=1,2, 3,4. Jako nejmenší £ tedy v úvahu připadá £ = 5. Ukážeme nyní, jak kódová slova délky 5 lze volit. Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. Řešení První můžeme (bez újmy na obecnosti) volit jako 00000. Protože zjevně každá dvě slova ve vzdálenosti 4 (tj. mající 4 jedničky a 1 nulu) jsou od sebe vzdálena 2 (z oněch 4 jedniček budou vždy přesně 3 společné), musí mít zbylá slova od našeho prvního vzdálenosti 3, 3, 4 (snadno si lze rozmyslet, že v případě 3, 3, 3 by pak tato slova musela být vzájemně vzdálena o 4 a to podle předchozího nelze). Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. Řešení 00111 11111 Príklad Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. Řešení 00111 \. ? 4 00000 ? 11111 11100 Príklad Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. Řešení 00111 \4 4 00000 3 11111 11100 Množinu čtyř slov chceme přenášet binárním kódem opravujícím jednoduché chyby. Jakou nejménší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov. Řešení 00111 11100 Vysvětlete (5,3)-kód nad Z/2 generovaný polynomem x + x + 1. Vypište všechna kódová slova, najděte generující matici a matici kontroly parity. Príklad Vysvětlete (5,3)-kód nad Z/2 generovaný polynomem x2 + x + 1 Vypište všechna kódová slova, najděte generující matici a matici kontroly parity. Rešení Zprávu i kódová slova (pro (5,3)-kód mají zprávy délku 3 a kódová slova délku 5) zapisujeme jako vektory skládající se z 0 a 1 a budeme s nimi tedy počítat modulo 2 (např. 101 + 110 = 011, tj. XOR). Standardně kódové slovo vznikne ze zprávy tím, že k ní přidáme (zleva) tzv. kontrolní bity: například kontrola parity 11001 i-> 1|11001, 10111 i-> 0|10111; tedy kódová slova jsou právě vektory obsahující sudý počet jedniček. Řešení V případě kódu generovaného polynomem p = 1 + x + x2: slova ztotožňujeme s polynomy, konkrétně polynom chápeme jako vektor jeho koeficientů a stále je bereme modulo 2, např. 1 + x2 + x3 odpovídá 10| 110 (koeficienty postupně od x° do x4, aby jich bylo 5). Kódovými slovy jsou právě polynomy dělitelné polynomem p, tj. právě násobky polynomu p 0 1 x X 2 (x + x2) (1 + x + x2) 1 + x + x2 1+x + x2 1+x + x2 1+x + x2 1+x + x2 1+x + x2 1+x + x2 1+x + x2 počítáme modulo 2): = 0 00|000 = 1 + x + x2 11|100 = x + x2+x3 01|110 = l + x3 10|010 = x2 + x3 + x4 00|111 = 1 + x + x3+ x4 11|011 = x + x4 01|001 = 1 + x2 + x4 10 101 OQ.O Lineární kód (např. kontrola parity nebo kód generovaný polynomem) je dán násobením maticí G, která je pro (5,3)-kód rozměrů 5 x 3 a standardně je v následujícím tvaru s tzv. maticí kontroly H (jejíž význam si vysvětlíme později): G = í 1 0 0 ■ •• 0 '-. o 0 1/ H=(E\P) Řešení = 1 + X + X' (1+*) (x + x2) (1 + x + x2) (1 + x + x2) (1 + x + x2) = x + x' = 1 +x- 11|100 10|010 01 001 Kód generovaný polynomem je lineární. V našem případě tedy: 1 1 0 W G ■ 0 0 1 W i o o Řešení /A 1 ° = 1 o 0 w G ■ °\ 0 1 = 0 0/ 1 w 1 0 = 0 1/ 0 w Protože to jsou postupně sloupce matice G, máme tak: G = í1 1 °\ 1 0 1 1 0 0 0 1 0 \o 0 1/ /-/ = Řešení Prvně vysvětlíme algoritmický postup pro p = 1 + xá /i \ o G = 0 Řešení Prvně vysvětlíme algoritmický postup pro p = 1 + x' ( i o \ 0 G = 0 0 \o o Řešení Prvně vysvětlíme algoritmický postup pro p = 1 + x' ( 1 0 0 \ 0 0 G = 0 0 0 0 Prvně vysvětlíme algoritmický postup pro p = 1 + x' G = 0 + 1 = 1 \ 0 + 0 = 0 1 + 1 = 0 0 + 0 = 0 1+0=1/ □ ť5P Prvně vysvětlíme algoritmický postup pro p = 1 + x' G = o+i =nn\ 0 + 0 = 0 1 + 1 = 0 0 + 0 = 0 1 + 0 =[l]J □ rS1 Řešení Nyní ukážeme algoritmický postup pro p — 1 + x + x' /i G = 0 Vo >0 Q,o Řešení Nyní ukážeme algoritmický postup pro p = 1 + x + x' ( 1 0 + 1 = 1 ? \ G = 1+1=0 ? 1+1=0 ? 0 1+0=1 ? \ o 0 + 0 = 0 ?/ Řešení Nyní ukážeme algoritmický postup pro p = 1 + x + x' ( 1 0 + 1 = 1 o\ G = 1+1=0 1 1+1=0 0 0 1+0=1 0 ^0+0=0 1) Řešení Nyní ukážeme algoritmický postup pro p = 1 + x + x' G = 0 + 1 = 1 1 + 1 = 0 1 + 1 = 0 1 + 0 = 1 \Loj o + o =lo Príklad V předchozím kódu zakódujte zprávu 101 Príklad V předchozím kódu zakódujte zprávu 101 Rešení Připomeňme, že kódování se realizuje násobením maticí kódu, tj. v našem případě: /l 1 1 0 1 1 0 0 0 1 0 \o 0 1/ 0 1 0 Príklad V předchozím kódu zakódujte zprávu 101 Rešení Připomeňme, že kódování se realizuje násobením maticí kódu, tj. v našem případě: /l 1 1 0 1 1 0 0 0 1 0 \o 0 1/ 0 1 0 Príklad V předchozím kódu zakódujte zprávu 101 Rešení Připomeňme, že kódování se realizuje násobením maticí kódu, tj. v našem případě: /l 1 1 0 1 1 0 0 0 1 0 \o 0 1/ 0 1 0 Príklad V předchozím kódu zakódujte zprávu 101 Rešení Připomeňme, že kódování se realizuje násobením maticí kódu, tj. v našem případě: /l 1 1 0 1 1 0 0 0 1 0 \o 0 1/ 0 1 0 Príklad V předchozím kódu zakódujte zprávu 101 Rešení Připomeňme, že kódování se realizuje násobením maticí kódu, tj. v našem případě: /l 1 1 0 1 1 0 0 0 1 0 \o 0 1/ 0 1 0 Príklad V předchozím kódu zakódujte zprávu 101 Rešení Připomeňme, že kódování se realizuje násobením maticí kódu, tj. v našem případě: /l 1 1 0 1 1 0 0 0 1 0 \o 0 1/ 0 1 0 Příklad V předchozím kódu zakódujte zprávu 101 Řešení Připomeňme, že kódování se realizuje násobením maticí kódu, tj. v našem případě: /l i 0\ 1 0 1 1 0 0 0 1 0 \o 0 1/ 0 1 0 V každém případě si povšimněme, že všechna kódová slova vzniknou tak, že sečteme některé sloupce matice G. Vysvětlete, jak polynom x + 1 generuje pro všechna n > 1 známý (r? + 1, r?)-kód kontroly parity. Vysvětlete, jak polynom x + 1 generuje pro všechna n > 1 známý (r? + 1, r?)-kód kontroly parity. Řešení Podle předchozího postupu lze snadno sestavit matici kódu G = / 1 0 + 1 = 1 0 + 1 = 1 • • • 0 + 1 = 1 1 1 +1 = 0 1 +1 = 0 • • • 1 +1 = 0 0 1 + 0 = 1 0 + 0 = 0 • • • 0 + 0 = 0 0 0 + 0 = 0 1 + 0 = 1 • • • 0 + 0 = 0 \ 0 0 + 0 = 0 0 + 0 = 0 • • • 1 + 0 = 1 / Řešení O něco přehledněji G = 0 \0 • • • 1/ a tím pádem G ■ o \0 • • • 1/ 1^ /x /ai + --- + an\ w V přičemž evidentně (ai + • • • an) + a\ + • • • + an = 0 (mod 2) a tedy počet jedniček v kódovém slově je vždy sudý. □ ► 4 O" >0 Q,o Uvažujme (7, 3)-kód generovaný polynomem x + x5 + x + 1. Napište jeho generující a kontrolní matice. Metodou vedoucích reprezentantů dekódujte přijatou zprávu 0110010, za předpokladu, že při přenosu došlo k nejmenšímu možnému počtu chyb. Uvažujme (7, 3)-kód generovaný polynomem x + x5 + x + 1. Napište jeho generující a kontrolní matice. Metodou vedoucích reprezentantů dekódujte přijatou zprávu 0110010, za předpokladu, že při přenosu došlo k nejmenšímu možnému počtu chyb. Řešení Podle předchozího postupu lze snadno sestavit matici kódu: / 1 0 + 1 = 1 0 + 1 = 1 \ 1 1 +1 = 0 1 +1 = 0 0 1 + 0 = 1 0 + 0 = 0 1 0 + 1 = 1 1 +1 = 0 1 1 +1 = 0 1 +1 = 0 0 1 + 0 = 1 0 + 0 = 0 \ 0 0 + 0 = 0 1 + 0 = 1 O něco přehledněji G = í1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 \o 0 1/ Budeme-li chvíli předpokládat, že přijaté slovo 0110|010 je kódové, musí se nutně jednat o kódové slovo odpovídající zprávě 010 (ta je obsažena v informačních bitech). Tomu však ve skutečnosti odpovídá jiné kódové slovo: Řešení G ■ (1 1 1\ 1 0 0 0 1 °\ 0 1 0 í°\ 1 1 1 = 110 • 1 = 1 0 0/ 1 0 0 w 0 0 0 1 0 1 1 \0 0 1/ w w I Řešení G ■ í1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 \o 0 1/ 0 1 1 1 1 0 0 0 1 1 w w Mohlo se samozřejmě stát, že vskutku bylo posláno toto kódové slovo a při přenosu došlo k chybě na bitech 1, 2 a 4: Řešení G ■ í1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 \o 0 1/ 0 1 1 1 1 0 0 0 1 1 w w Mohlo se samozřejmě stát, že vskutku bylo posláno toto kódové slovo a při přenosu došlo k chybě na bitech 1, 2 a 4: 1 0 1 1 1 0 0 — 1 + 1 0 0 0 1 1 0 \0 \0 Jiné možnosti dostaneme pozměněním kódového slova přičtením nějakých sloupců matice G. Za každý sloupec přibude chyba v informačním bitu prvně jednotlivé sloupce. První sloupec: i i 0^ o" 1 W 0 1 1 0 1 \\o/ + 1 0 1 1 o + i 0 1 o o \\o/ + 1 0 1 1 o 1 0 1 0 0 + 0 1 1 1 0 W w Druhý sloupec: i i 0^ ô" 1 W 0 1 1 0 1 \\o/ + 0 1 1 0 1 + i 0 1 o o \\o/ + 0 1 1 0 1 0 1 0 1 0 + 0 0 0 0 1 w w Třetí sloupec: i i 0^ o" 1 W 0 1 1 0 1 + 0 0 o o o + //!\ 1 0 1 o o + o o o o o 0 1 1 0 1 + 1 0 0 1 0 w w Řešení Našli jsme čtyři možnosti, zbylé vzniknou přičítáním alespoň dvojice sloupců a odpovídají tedy alespoň dvojnásobným chybám Mezi čtyřmi možnostmi se vyskytuje jednoduchá chyba, je tedy řešením úlohy: 1 i 0 1 i 0 0 — 0 + 0 0 1 1 1 1 0 W w w kde levá strana je přijaté slovo, první vektor napravo je odeslané slovo 0110| 110 a druhý vektor napravo je chyba, ke které došlo při přenosu. K čemu je kontrolní matice H? Předchozí způsob lze také zapisovat takto: K danému obdrženému slovu spočítame tzv. syndrom H 1 1 0 0 1 W A o o Vo 0 o 1 o 0 1 o o o o 0 1 1 1 0 1 1 1\ 0 o 1 o 1 0/ 1 1 o 0 1 w A\ 1 o který je roven kontrolním bitům iniciální chyby (ta s informačními bity nulovými). V lineárním (7,4)-kódu zadaném maticí í° 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 \o 0 0 1/ byly přijaty zprávy 101|0001 a 100|1110. Dekódujte je (tj. nalezněte odesílané zprávy) za předpokladu, že při přenosu každého slova došlo k nejmenšímu možnému počtu chyb. Pro první potenciální zprávu 0001 ze zadání (informační bity přijatého slova) dostáváme kódové slovo í° 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 \o 0 0 1/ o o 1 0 i 1 1 1 i 0 0 0 — 0 + 0 0 0 0 0 0 0 0 0 \1/ V V w w a liší se od přijatého slova. Zjevně se vyplatí přičíst druhý sloupec: 0 1 o o W íí°\ i i o o + /*\\ 1 0^ 0 1 o Vo// + 1 0^ o o o V Vo/ + /*\\ 1 0^ 0 1 o Vo// 0 0 1 0 0 + 0 1 1 0 0 Vi/ Vo/ Přičtením jiných sloupců jedné chyby nedocílíme, přičtením dvou a více vznikne alespoň dovjnásobná chyba. Jedná se tedy o optimální "rozklad" na odeslané slovo a chybu. Řešení Pro druhou potenciální zprávu 1110 ze zadání (informační bity přijatého slova) dostáváme kódové slovo i i 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 \o 0 0 1/ 1 1 W 0 0 0 0 0 0 0 0 1 1 1 — 1 + 0 1 1 1 0 1 1 1 0 w W w w a liší se od přijatého slova. Přičteném žádného sloupce se nepodaří počet chyb snížit oproti výše uvedené možnosti jednoduché chyby. Poslaná slova tedy jsou: 10110101 a 000| 1110 a původní zprávy pak 0101 a 1110.