Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Teorie kódování - Kapitola 4 Kódy opravující chyby Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 12. dubna 2023 Kódování a odhady Ekvivalence kódů Hlavní problém TK Obsah Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy O Kódování a odhady qK ' ;'H • Základní pojmy ^ , • Vzdálenost a váha ™ ^ • Opravení x určení o Maximální kódy w Cyklické kódy d Fkvivalpnrp kódů a W Marinerův kód a Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Fl Připomeňme si následující předpoklady pro kódování. Zdroj vytváří zprávu, která sestává z posloupnosti zdrojových symbolů a tato zpráva je přenesena k příjemci přes kanál s možnou chybou. Přitom lze bez újmy na obecnosti předpokládat, že kanál má stejnou abecedu Z jak na vstupu tak na výstupu. Kód C nad abecedou Z je soubor posloupností symbolů ze Z, prvky z C se nazývají kódová slova. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Fl Připomeňme si následující předpoklady pro kódování. Zdroj vytváří zprávu, která sestává z posloupnosti zdrojových symbolů a tato zpráva je přenesena k příjemci přes kanál s možnou chybou. Přitom lze bez újmy na obecnosti předpokládat, že kanál má stejnou abecedu Z jak na vstupu tak na výstupu. Kód C nad abecedou Z je soubor posloupností symbolů ze Z, prvky z C se nazývají kódová slova. Budeme předpokládat, že všechna kódová slova mají stejnou délku. Takovéto kódy se nazývají blokové kódy a při jejich použití je dekódování podstatně snazší. Pokud mají kódová slova z C délku na\Z\ = q, pak mluvíme o q-árním kódu délky n (binárním kódu, pokud q = 2). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Zakladni P°Jmy 3 Vzdálenost a váha Opravení x určení Maximální kódy Základní pojmy Zakódování zdrojové zprávy není nic jiného než přiřazení každé /c-dlouhé sekvenci znaků nad zdrojovou abecedou Z jedno kódové slovo z C. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Zakódování zdrojové zprávy není nic jiného než přiřazení každé /c-dlouhé sekvenci znaků nad zdrojovou abecedou Z jedno kódové slovo z C. Během samotného dekódování se přijatá sekvence rozčlení na bloky délky n a každý se zpracovává samostatně. Jelikož přijaté n-bloky mohou mít díky chybám při přenosu obecně jinou podobu než vysílaná kódová slova, musí dekodér rozhodovat, které slovo bylo vysláno. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Zakódování zdrojové zprávy není nic jiného než přiřazení každé /c-dlouhé sekvenci znaků nad zdrojovou abecedou Z jedno kódové slovo z C. Během samotného dekódování se přijatá sekvence rozčlení na bloky délky n a každý se zpracovává samostatně. Jelikož přijaté n-bloky mohou mít díky chybám při přenosu obecně jinou podobu než vysílaná kódová slova, musí dekodér rozhodovat, které slovo bylo vysláno. Pokud je kód dobře navržen, je pravěpodobnost špatného rozhodnutí mnohem menší než pravděpodobnost, že libovolný kódový znak je chybně přenesen. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Proces rozhodování může být definován pomocí dekódovací tabulky. Kódová slova tvoří první řádek tabulky. Pokud jsme obdrželi kódové slovo, je logické předpokládat, že i stejné slovo bylo vysláno. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Proces rozhodování může být definován pomocí dekódovací tabulky. Kódová slova tvoří první řádek tabulky. Pokud jsme obdrželi kódové slovo, je logické předpokládat, že i stejné slovo bylo vysláno. Rozhodovací pravidlo pro zbylá možně přijatá slova je dáno rozdělením těchto slov do seznamů pod každým kódovým slovem, podle kterého se tato přijatá slova budou dekódovat. Tedy, každé slovo délky n nad abecedou Z se objeví v tabulce právě jednou. Kódovaní a odhady Hranice Aa (n, d) Dalsi kody ^ ■ ^ r-. ■ , . . i - r. ui- Zakadni pojmy Opraveni x určeni Ekvivalence kodu Lineárni kody Problémy w ... , . Hlavní problém TK Cyklické kódy Vzdálenost a vana Maximální kody Základní pojmy - Blokové kódování /c-bitů A7-bÍtŮ A7-bÍtŮ A7-bÍtŮ /c-bitů /c-bitů A7-bÍtŮ A7-bÍtŮ A7-bÍtŮ /c-bitů zdrojová data (zakódování) zakódovaná zpráva (přenos) obdržená zpráva (oprava chyb) opravená zpráva (dekódování) obdržená data po dekódování Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy zakódovaná zpráva prenos kanálem obdržená zpráva obdržená data po opravě a dekódování Obrázek 1: Komunikační kanál Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Definition 1.1 Buď u, v přirozená čísla. Řekneme, že kód C určí u chyb, jestliže, pokud každé kódové slovo změníme alespoň na jednom a ne více než u místech, nebude výsledný řetězec kódové slovo. Řekneme, že kód C určí právě u chyb, jestliže určí u chyb a neurčí u + 1 chyb. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Definition 1.1 Buď u, v přirozená čísla. Řekneme, že kód C určí u chyb, jestliže, pokud každé kódové slovo změníme alespoň na jednom a ne více než u místech, nebude výsledný řetězec kódové slovo. Řekneme, že kód C určí právě u chyb, jestliže určí u chyb a neurčí u + 1 chyb. Řekneme, že kód C opraviv chyb, jestliže, pokud použijeme pravidlo minimální vzdálenosti, jsme schopni opravit alespoň v chyb a v případě, kdy se nebudeme moci rozhodnout, dostaneme na výstupu chybu v dekódování. Řekneme, že kód C opraví právě v chyb, jestliže opraví v chyb a neopraví v + 1 chyb. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Dále budeme předpokládat, že abychom byli schopni zjistit chyby při přenosu, bude příjemce schopen zkontrolovat přijatý řetězec proti seznamu všech kódových slov. Pokud řetězec nebude na seznamu, příjemce ví, že nastala alespoň jedna chyba, ale není schopen zjistit, kolik chyb skutečně nastalo. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Dále budeme předpokládat, že abychom byli schopni zjistit chyby při přenosu, bude příjemce schopen zkontrolovat přijatý řetězec proti seznamu všech kódových slov. Pokud řetězec nebude na seznamu, příjemce ví, že nastala alespoň jedna chyba, ale není schopen zjistit, kolik chyb skutečně nastalo. Zároveň by mělo být jasné, že pokud obdržené slovo nebude kódové slovo, bude podle pravidla minimální vzdálenosti zpátky dekódováno, ale příjemce neví, zda se skutečně jedná o odeslané slovo. Příjemce pouze ví, že pokud nenastane, v případě kódu opravujícího v chyb, více než v chyb, pak dekódovací proces bude úspěšný tj. pomocí pravidla minimální vzdálenosti získáme odeslané kódové slovo. Další kódy Problémy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Kódování a odhady Ekvivalence kódů Hlavní problém TK Příklad Příklad 1.2 Hranice Aq(n, d) Lineární kódy Cyklické kódy Chceme vysílat čtyři znaky: a, b,c,d a zpráva bude přenášena pomocí binárního blokového kódu délky 5. Musíme tedy zvolit čtyři kódová slova, např. 11000 pro a, 00110 pro b, 10011 pro c a 01101 pro d. Dekódování musí zahrnout všech 25 = 32 binárních slov délky 5. Jedno takové dekódovací pravidlo je na (obr.2). 11000 00110 10011 01101 11001 00111 10010 01100 11010 00100 10001 01111 11100 00010 10111 01001 10000 01110 11011 00101 01000 10110 00011 11101 11110 00000 01011 10101 01010 10100 11111 00001 Obrázek 2: Příklad kódové tabulky pro binární blokový kód délky 5. 0 0,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Příklad Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Konstrukce kódu a dekódovacího schématu z příkladu 1.2 opravuje ne více než jednu chybu. V tabulce je to vždy prvních 5 slov v seznamu pod kódovým slovem. Kódování a odhady Ekvivalence kódů Hlavní problém TK Příklad Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Zé Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Konstrukce kódu a dekódovacího schématu z příkladu 1.2 opravuje ne více než jednu chybu. V tabulce je to vždy prvních 5 slov v seznamu pod kódovým slovem. U více chyb už nemáme jistotu, že dekódování proběhne správně. Například pokud by při přenosu bloku 11000 vznikly dvě chyby vedoucí k přijetí slova 11110 na výstupu kanálu, pak toto schéma chyby odstraní. Ovšem při obdržení 11011 bude toto slovo dekódováno chybně jako 10011. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy ákladní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Hammingova vzdálenost a váha Označme dále Vn(T) množinu všech posloupností délky n nad abecedou Z a nazývejme prvky ze Vn(T) slova nebo vektory. Někdy budeme psát místo Vn(T) také Vn(q), pokud q = cardZ. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy ákladní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Hammingova vzdálenost a váha Označme dále Vn(T) množinu všech posloupností délky n nad abecedou Z a nazývejme prvky ze Vn(T) slova nebo vektory. Někdy budeme psát místo Vn(T) také Vn(q), pokud q = cardZ. Podobně jako v binárním případě je Hammingova vzdálenost d(x, y) mezi vektory x a y počet míst, ve kterých se x a y liší. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy ákladní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Hammingova vzdálenost a váha Označme dále Vn(T) množinu všech posloupností délky n nad abecedou Z a nazývejme prvky ze Vn(T) slova nebo vektory. Někdy budeme psát místo Vn(T) také Vn(q), pokud q = cardZ. Podobně jako v binárním případě je Hammingova vzdálenost d(x, y) mezi vektory x a y počet míst, ve kterých se x a y liší. V případě, že q = cardZ je mocnina prvočísla, můžeme považovat abecedu Z za těleso ¥q, které má nulový prvek 0. Množinově můžeme ztotožnit ¥q s Zq, přirozené operace na Zq ale nemusí odpovídat operacím na ¥q. Váha slova x = x^x2 • • • xn je pak počet nenulových znaků slova x, tj. wt(x) = d(x, 0), kde 0 je slovo z n nul. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy ákladní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Hammingova vzdálenost a váha Kódová slova 0 Poškozená kódová slova s jednou až t chybami Obrázek 3: Použití Hammingovy vzdálenosti pro opravu až t chyb. < □ gP ► < -ě: = -i -0 0,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Hammingova vzdálenost a váha ákladní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Nechť Vn(Z) je množina všech posloupností délky n nad abecedou Z . Potom funkce Hammingovy vzdálenosti oř(-, -): Vn(T) x Vn(Y.) N má následující vlastnosti. Pro všechna x, y, z g Vn(T), (pozitivní definitivita) d(x, y) >0, a d(x, y) = 0 právě tehdy když x (symetrie) d(x,y) = Gř(y,x) (trojúhelníková nerovnost) d(x,y) < d(x,z) + d(z,y). Tedy, dvojice (Vn(T),d(-,-)) je metrický prostor. = x, Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy ákladní pojmy Opravení x určení zdálenost a váha Maximální kódy Hammingova vzdálenost a váha Definice 1 Buď x g Z", p > 0. Sférou S"r(x) v Z" se středem x a poloměrem p rozumíme množinu S7(x) = {yeZ?:d(x,y) 0. Sférou S"r(x) v Z" se středem x a poloměrem p rozumíme množinu Sn/(x) = {yeZ"r:d(x,y) 0. Sférou S"r(x) v Z" se středem x a poloměrem p rozumíme množinu Sn/(x) = {yeZ"r:d(x,y)u + J\ (d(C) > 2v + 1). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Detekce chyb podle pravidla minimální vzdálenosti Věta 1.7 Buďte u, v přirozená čísla. Pak kódC určí u (opraviv) chyb právě tehdy když d(C) >u+J\ (d(C) > 2v + 1). První část tvrzení je jednoduché přeformulování definice kódu určujících u chyb. Pro druhou část tvrzení jsme ukázali ve větě 1.6 implikaci zprava doleva. Předpokládejme nyní, že C je kód opravující v chyb a že existují dvě různá kódová slova c a d tak, že d(c,d) = d(C)<2\/. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Detekce chyb podle pravidla minimální vzdálenosti Věta 1.7 Buďte u, v přirozená čísla. Pak kódC určíu (opraviv) chyb právě tehdy, když d(C) >u+J\ (d(C) > 2v + 1). První část tvrzení je jednoduché přeformulování definice kódu určujících u chyb. Pro druhou část tvrzení jsme ukázali ve větě 1.6 implikaci zprava doleva. Předpokládejme nyní, že C je kód opravující v chyb a že existují dvě různá kódová slova c a d tak, že d(c,d) = d(C)<2\/. Budeme chtít dokázat, že za předpokladu, že jsme odeslali kódové slovo c a nastalo nejvýše v chyb, je přesto možné, abychom podle pravidla minimální vzdálenosti obdrželi buď chybové hlášení nebo dekódovali obdržené slovo nesprávně jako d. To pak bude spor s tím, že C opravuje v chyb. I Kódovaní a odhady Hranice Aa(n, d) Dalsi kody _ ,-, . , . . i - r. ui- Zakadni pojmy Opraveni x určeni Ekvivalence kodu Lineárni kody Problémy w ... , ,.K . Hlavní problém TK Cyklické kódy ^^^^^^ Vzdálenost a vaha Maximální kody Detekce chyb podle pravidla minimální vzdálenosti Pokračování důkazu Věty 1.7. Nejdříve si uvědomme, že d(c, d) = d(C) > v + 1. Jinak bychom totiž mohli převést c na d při nejvýše v chybách, které by zůstaly neopraveny. Můžeme pak předpokládat, že se c a d liší na prvních k = d(C) místech, přičemž v + 1 < k <2v (jinak provedeme permutaci souřadnic). 0 0,0 Kódovaní a odhady Hranice Aa(n, d) Dalsi kody _ ,-, . , . . i - r. ui- Zakadni pojmy Opraveni x určeni Ekvivalence kodu Lineárni kody Problémy w ... , . Hlavní problém TK Cyklické kódy ^^^^^^ Vzdálenost a vaha Maximální kody Detekce chyb podle pravidla minimální vzdálenosti Pokračování důkazu Věty 1.7. Nejdříve si uvědomme, že d(c, d) = d(C) > v + 1. Jinak bychom totiž mohli převést c na d při nejvýše v chybách, které by zůstaly neopraveny. Můžeme pak předpokládat, že se c a d liší na prvních k = d(C) místech, přičemž v + 1 < k <2v (jinak provedeme permutaci souřadnic). Uvažme nyní obdržené slovo x, které se shoduje se slovem c na prvních k - v pozicích, dále se shoduje se slovem d na dalších v pozicích a shoduje se s oběma slovy c a d na posledních n-k pozicích, tj. x = Xi......Xk_v Xk_v+1......Xfc Xfr+1......xn. S-v-/S-v-/S-v-' shoduje se s c shoduje se s d shoduje se s oběma 0 0,0 Kódovaní a odhady Hranice Aa(n, d) Dalsi kody _ ,-, . , . . i - r. ui- Zakadni pojmy Opraveni x určeni Ekvivalence kodu Lineárni kody Problémy w ... , ,.K . Hlavní problém TK Cyklické kódy ^^^^^^ Vzdálenost a vaha Maximální kody Detekce chyb podle pravidla minimální vzdálenosti Pokračování důkazu Věty 1.7. Protože nutně d(c, x) = v, d(d, x) = k - v < v, je buďto d(c,x) = d(d,x) (v tomto případě obdržíme chybové hlášení) nebo d(c, x) > d(d, x) (v tomto případě je x dekódované nesprávně jako d). I Kódovaní a odhady Hranice Aa(n, d) Dalsi kody _ ,-, . , . . i - r. ui- Zakadni pojmy Opraveni x určeni Ekvivalence kodu Lineárni kody Problémy w ... , ,.K . Hlavní problém TK Cyklické kódy ^^^^^^ Vzdálenost a vaha Maximální kody Detekce chyb podle pravidla minimální vzdálenosti Pokračování důkazu Věty 1.7. Protože nutně d(c, x) = v, d(d, x) = k - v < v, je buďto d(c,x) = d(d,x) (v tomto případě obdržíme chybové hlášení) nebo d(c, x) > d(d, x) (v tomto případě je x dekódované nesprávně jako d). I Definition 1.8 Pokud má blokový kód C právě M kódových slov délky n a má minimální vzdálenost d, mluvíme o (n, M, d)-kódu. Kódovaní a odhady Hranice Aa(n, d) Dalsi kody _ ,-, . , . . i - r. ui- Zakadni pojmy Opraveni x určeni Ekvivalence kodu Lineárni kody Problémy w ... , . Hlavní problém TK Cyklické kódy ^^^^^^ Vzdálenost a vaha Maximální kody Detekce chyb podle pravidla minimální vzdálenosti Pokračování důkazu Věty 1.7. Protože nutně d(c, x) = v, d(d, x) = k - v < v, je buďto d(c,x) = d(d,x) (v tomto případě obdržíme chybové hlášení) nebo d(c, x) > d(d, x) (v tomto případě je x dekódované nesprávně jako d). I Definition 1.8 Pokud má blokový kód C právě M kódových slov délky n a má minimální vzdálenost d, mluvíme o (n, M, d)-kódu. Pro pevné n působí parametry M ad navzájem proti sobě tak, že zvětšení M způsobí zmenšení d a naopak. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti Máme pak následující důsledek. Důsledek 1.9 O (n, M, d)-kódC opraví právě v chyb tehdy a jen tehdy když d = 2v + 1 nebo d = 2v + 2. O Kód C má minimální vzdálenost d = d(C) tehdy a jen tehdy 1 2 když opraví právě [Ud-*\ )J chyb. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti Máme pak následující důsledek. O (n, M, d)-kódC opraví právě v chyb tehdy a jen tehdy když d = 2v + 1 nebo d = 2v + 2. O Kód C má minimální vzdálenost d = d(C) tehdy a jen tehdy když opraví právě \_\(d -1i )J chyb. Poznamenejme nyní, že určení chyby a její oprava jdou proti sobě, takže nemůžeme naráz dosáhnout jejich maximální úrovně. Uveďme si to na jednoduchém příkladě. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti Příklad 1.10 Předpokládejme nyní, že kód C má minimální vzdálenost d. Je to tedy kód určující d - 1 chyb a opravující v = [±(d - 1 )J chyb. Pokud použijeme C pouze pro určení chyb, je schopen určit až d - 1 chyb. Z druhé strany, pokud chceme na C opravit chybu, kdykoliv je to možné, pak je schopen opravit až v chyb, ale není schopen určit situaci, kdy nastalo více než v a méně než d chyb. Totiž, pokud nastalo více než v chyb, můžeme podle pravidla minimální vzdálenosti "opraviť přijatý řetězec na špatné kódové slovo a pak bude chyba nedetekovatelná. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti Zkusme nyní podrobněji rozebrat případ, kdy kvalita detekování chyb kódu se sudou minimální vzdáleností závisí na tom, zda je či není kód použit pouze pro detekci chyb nebo zároveň jak pro detekci tak pro opravu chyb. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti Zkusme nyní podrobněji rozebrat případ, kdy kvalita detekování chyb kódu se sudou minimální vzdáleností závisí na tom, zda je či není kód použit pouze pro detekci chyb nebo zároveň jak pro detekci tak pro opravu chyb. Předpokládejme, že C je (n, M, d), kde d = 2t + 2. Jakožto pouze detekující kód dokáže C detekovat až d - 1 = 2ŕ + 1 chyb. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti Zkusme nyní podrobněji rozebrat případ, kdy kvalita detekování chyb kódu se sudou minimální vzdáleností závisí na tom, zda je či není kód použit pouze pro detekci chyb nebo zároveň jak pro detekci tak pro opravu chyb. Předpokládejme, že C je (n, M, d), kde d = 2t + 2. Jakožto pouze detekující kód dokáže C detekovat až d - 1 = 2ŕ + 1 chyb. Na druhou stranu předpokládejme, že chceme použít C současně pro opravu chyb a detekci chyb. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti Zkusme nyní podrobněji rozebrat případ, kdy kvalita detekování chyb kódu se sudou minimální vzdáleností závisí na tom, zda je či není kód použit pouze pro detekci chyb nebo zároveň jak pro detekci tak pro opravu chyb. Předpokládejme, že C je (n, M, d), kde d = 2t + 2. Jakožto pouze detekující kód dokáže C detekovat až d - 1 = 2ŕ + 1 chyb. Na druhou stranu předpokládejme, že chceme použít C současně pro opravu chyb a detekci chyb. Protože C opraví přesně ř-chyb, pak pokud chceme maximalizovat možnosti opravy chyb, musíme „dovolit", aby se opravilo jakýchkoliv t chyb. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti To znamená, že pokud obdržíme slovo x a pokud existuje kódové slovo c, pro které oř(c, x) < ř, pak předpokládáme, že došlo k nejvýše t chybám, a opravíme x na c. Pokud žádné takové kódové slovo c neexistuje, pak můžeme prohlásit, že se vyskytly některé chyby. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti To znamená, že pokud obdržíme slovo x a pokud existuje kódové slovo c, pro které oř(c, x) < ř, pak předpokládáme, že došlo k nejvýše t chybám, a opravíme x na c. Pokud žádné takové kódové slovo c neexistuje, pak můžeme prohlásit, že se vyskytly některé chyby. Nyní, pokud při přenosu kódového slova c došlo k přesně t + 1 chybám, pak přijaté slovo x nemůže být ve vzdálednosti nejvýše t od žádného kódového slova d. Kdyby tomu tak bylo, pak by platilo d(c, d) < cř(c, x) + cř(x, d) < ř + 1 + ř = 2t + 1 < d. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti To znamená, že pokud obdržíme slovo x a pokud existuje kódové slovo c, pro které oř(c, x) < ř, pak předpokládáme, že došlo k nejvýše t chybám, a opravíme x na c. Pokud žádné takové kódové slovo c neexistuje, pak můžeme prohlásit, že se vyskytly některé chyby. Nyní, pokud při přenosu kódového slova c došlo k přesně t + 1 chybám, pak přijaté slovo x nemůže být ve vzdálednosti nejvýše t od žádného kódového slova d. Kdyby tomu tak bylo, pak by platilo d(c, d) < cř(c, x) + cř(x, d) < ř + 1 + ř = 2t + 1 < d. Naše strategie vyžaduje, abychom detekovali, že došlo k chybám, a C dokáže detekovat t + 1 chyb. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti Pokud by však došlo k t + 2 chybám, pak protože d = 2t + 2, v alespoň jednom případě bude mít přijaté slovo x vzdálenost t od špatného kódového slova a přijaté slovo „opravíme" nesprávně aniž budeme detekovat chyby. Proto C ne vždy detekuje t + 2 chyb. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti Pokud by však došlo k t + 2 chybám, pak protože d = 2t + 2, v alespoň jednom případě bude mít přijaté slovo x vzdálenost t od špatného kódového slova a přijaté slovo „opravíme" nesprávně aniž budeme detekovat chyby. Proto C ne vždy detekuje t + 2 chyb. Předcházející úvahy lze zformulovat do následující věty. Věta 1.11 Pokud je (n, M, d)-kódC, d = 2 ŕ + 2, použit pouze pro detekci chyb, pak odhalí právě (2t + 1) chyb. Na druhou stranu, pokud je C použit pro opravu co největšího počtu chyb a zároveň pro odhalení chyb, pak C opraví právě t chyb a dokáže současně detekovat t + 1 chyb, ale nemůže vždy detekovat více než t + 1 chyb. O1 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Oprava chyb podle pravidla minimální vzdálenosti Máme pak následující definici. Definice 2 Uvažme následující strategii pro opravu/u rčení chyby. Buď u, v přirozená čísla. Obdržíme-li slovo x a pokud má nejbližší kódové slovo c ke slovu x vzdálenost nejvýše v a existuje-li pouze jediné takové kódové slovo, budeme dekódovat x jako kódové slovo c. Pokud existuje více než jedno kódové slovo se stejnou minimální vzdáleností k x nebo má nejbližší kódové slovo vzdálenost větší než v, obdržíme na výstupu chybové hlášení. Řekneme, že kód C zároveň opraví v chyb a určí u chyb, jestliže nastala alespoň jedna a nejvýše v chyb, výše popsaná strategie opraví tyto chyby a kdykoliv nastane alespoň v + 1 a nejvýše u + v chyb, výše popsaná strategie nahlásí chybu. 00,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Opravení v chyb a určení u chyb Věta 1.12 Kód C zároveň opraviv chyb a určí u chyb právě tehdy, když d(C) >2v + u+\. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Opravení v chyb a určení u chyb Věta 1.12 Kód C zároveň opraviv chyb a určí u chyb právě tehdy, když d(C) >2v + u+\. Důkaz. Předpokládejme nejprve, že d(C) > 2v + u + 1. Obdržíme-li slovo x a pokud má nejbližší kódové slovo c ke slovu x vzdálenost nejvýše v a existuje-li alespoň jedno další takové kódové slovo d, máme 2v + u + *\ < d(c, d) < d(c, x) + d(x, d) < 2v, což je spor. Nutně tedy máme, že pokud obdržíme slovo x a nejbližší kódové slovo c ke slovu x má vzdálenost nejvýše v, je toto kódové slovo jediné s touto vlastností a podle pravidla minimální vzdálenosti budeme správně dekódovat. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Opravení v chyb a určení u chyb Pokračování důkazu Věty 1.12. Obdržíme-li slovo x a pokud má nejbližší kódové slovo c ke slovu x vzdálenost alespoň v + 1 a nejvýše u + v, při použití výše uvedené strategie dostaneme chybové hlášení. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Opravení v chyb a určení u chyb Pokračování důkazu Věty 1.12. Obdržíme-li slovo x a pokud má nejbližší kódové slovo c ke slovu x vzdálenost alespoň v + 1 a nejvýše u + v, při použití výše uvedené strategie dostaneme chybové hlášení. Předpokládejme nyní, že C je kód opravující v chyb a určující u chyb. Nechť dále d(C) <2v + u. Nutně pak 2v + 1 < d(C). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Opravení v chyb a určení u chyb Pokračování důkazu Věty 1.12. Obdržíme-li slovo x a pokud má nejbližší kódové slovo c ke slovu x vzdálenost alespoň v + 1 a nejvýše u + v, při použití výše uvedené strategie dostaneme chybové hlášení. Předpokládejme nyní, že C je kód opravující v chyb a určující u chyb. Nechť dále d(C) <2v + u. Nutně pak 2v + 1 < d(C). Víme, že existují dvě různá kódová slova c a d tak, že k = d (c, d) = d(C). Můžeme pak předpokládat, že se c a d liší na prvních k = d(C) místech, přičemž 2v + 1 < k <2v + u (jinak provedeme permutaci souřadnic). I Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Základní pojmy Opravení x určení Vzdálenost a váha Maximální kódy Opravení v chyb a určení u chyb Pokračování důkazu Věty 1.12. Uvažme nyní obdržené slovo x, které se shoduje se slovem c na prvních v pozicích, dále se shoduje se slovem d na dalších k - v pozicích a shoduje se s oběma slovy c a d na posledních n - k pozicích, tj. x — X"| ... Xy . . . Xfc X/c-|-1 • • • Xfi . shoduje se s c shoduje se s d shoduje se s oběma 0 0,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Opravení v chyb a určení u chyb Pokračování důkazu Věty 1.12. Uvažme nyní obdržené slovo x, které se shoduje se slovem c na prvních v pozicích, dále se shoduje se slovem d na dalších k - v pozicích a shoduje se s oběma slovy c a d na posledních n - k pozicích, tj. x — X"| ... Xy . . . Xfc X/c-|-1 • • • Xfi . shoduje se s c shoduje se s d shoduje se s oběma Nutně pak d(c, x) = k - v, d(d, x) = v, v +1 d C se nazývá maximální, pokud není obsažen v žádném větším kódu se stejnou minimální vzdáleností tj. není obsažen v žádném (n, M + 1, d)-kódu. Je zřejmé, že pro každý kód C můžeme vždy najít maximální kód C, který jej obsahuje. Přitom platí Věta 1.14 (n, M, d)-kódC je maximální právě tehdy, když pro všechna slova x existuje kódové slovo c s vlastností d(x, c) < d. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Maximální kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Důkaz Věty 1.14. (n, M, c/)-kč>d C je maximální právě tehdy, když není obsažen v žádném (n, M + 1, d)-kódu. Předpokládejme, že existuje slovo x tak, že pro všechna kódová slova c platí d(x, c) > d. Položíme-li C = C u {x}, je pak evidentně C (n, M + 1, cř)-kód obsahující kód C. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Maximální kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Důkaz Věty 1.14. (n, M, c/)-kč>d C je maximální právě tehdy, když není obsažen v žádném (n, M + 1, d)-kódu. Předpokládejme, že existuje slovo x tak, že pro všechna kódová slova c platí d(x, c) > d. Položíme-li C = C u {x}, je pak evidentně C (n, M + 1, cř)-kód obsahující kód C. Obráceně, nechť pro všechna slova x existuje kódové slovo c s vlastností d(x,c) < d. Předpokládejme, že kód C není maximální tj. existuje (n, M + 1, c/)-kód obsahující kód C. Vyberme slovo x g C - C. Pak ale existuje kódové slovo c g C c C tak, že d(C') < d(x, c) < d, spor. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Maximální kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Poznamenejme, že pokud (n, M, d)-kód C není maximální, mohou nastat jak výhodné tak nevýhodné situace při jeho rozšíření na maximální kód C. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Maximální kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Poznamenejme, že pokud (n, M, d)-kód C není maximální, mohou nastat jak výhodné tak nevýhodné situace při jeho rozšíření na maximální kód C. Víme, že kód C rovněž opraví [\{d - 1 )J chyb, což je dobré a přitom C může zakódovat více zdrojových symbolů, což je rovněž dobré. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Maximální kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Poznamenejme, že pokud (n, M, d)-kód C není maximální, mohou nastat jak výhodné tak nevýhodné situace při jeho rozšíření na maximální kód C. Víme, že kód C rovněž opraví [\{d - 1 )J chyb, což je dobré a přitom C může zakódovat více zdrojových symbolů, což je rovněž dobré. Ale zatímco C může být případně schopen opravit více než [\{d - 1 )J chyb, kód C nebude nikdy schopen opravit více než Li(cf-1)j chyb. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Maximální kódy Příklad 1.15 Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Uvažme kód C = {00000,11000}, který má minimální vzdálenost 2. Tento kód opravuje jednu chybu, ale je přitom schopen opravit další jiné chyby Například, pokud bylo odesláno slovo 00000 a přijato slovo 00111, bude toto slovo správně dekódováno (totiž c/(00000,00111 ) = 3, oř(11000,00111) = 5), ačkoliv při přenosu nastaly tři chyby Pokud ale doplníme C do maximálního kódu, bude dekódování chybné. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Maximální kódy Příklad 1.15 Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Uvažme kód C = {00000,11000}, který má minimální vzdálenost 2. Tento kód opravuje jednu chybu, ale je přitom schopen opravit další jiné chyby Například, pokud bylo odesláno slovo 00000 a přijato slovo 00111, bude toto slovo správně dekódováno (totiž c/(00000,00111 ) = 3, oř(11000,00111) = 5), ačkoliv při přenosu nastaly tři chyby Pokud ale doplníme C do maximálního kódu, bude dekódování chybné. Z výše uvedeného příkladu vyplývá, že maximální kódy jsou nejlepší, pokud nás u kódu pouze zajímá předem určená schopnost opravení chyby. Je tedy daleko obtížnější zkoumat pravděpodobnost chyby při dekódování u kódů, které nejsou maximální. Pro maximální kódy je to jednoc^čí^ = Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Maximální kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Věta 1.16 Buď C (n, M, d)-kód. Pak pro binární symetrický kanál s pravděpodobností chyby p je při použití dekódovacího pravidla minimální vzdálenosti P(nastala chyba při dekódování) < 1 — í ^ JP^O ~ P) k=0 ^ ' n-k Je-li navíc kód C maximální, je n ( ^ jPk0 ~P)n~k < P(nastala chyba při dekódování). k=d Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Maximální kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Důkaz Věty 1.16. Každý (n, M, d)-kóä C opravuje evidentně [\{d - 1 )J chyb. Je tedy pravděpodobnost správného dekódování alespoň tak velká jako je pravděpodobnost, že nastane nejvýše [\{d - 1 )J chyb tj. P(správné dekódování) > í ^ jp^O — P) k=0 ^ ' n-k 0 0,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Maximální kódy Důkaz Věty 1.16. Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Každý (n, M, d)-kóä C opravuje evidentně [\{d - 1 )J chyb. Je tedy pravděpodobnost správného dekódování alespoň tak velká jako je pravděpodobnost, že nastane nejvýše [\{d - 1 )J chyb tj. li(d-i)J n-k P(správné dekódování) > í ^ jp^O ~ P) k=0 ^ ' Máme pak P(nastala chyba při dekódování) = 1 — P(správné dekódování) < i - sítr,J (i Vo - prk- 0 0,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Maximální kódy Pokračování Důkazu Věty 1.16, Buď dále (n, M, c/)-kód C maximální. Pak, je-li přeneseno slovo c a nastane-li d nebo více chyb, tj. d(c,x) > d, bude nutně x bližší k jinému kódovému slovu d^ca tedy při použití pravidla minimální vzdálenosti nastane dekódovací chyba. 0 0,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vzdálenost a váha Opravení x určení Maximální kódy Maximální kódy Pokračování Důkazu Věty 1.16, Buď dále (n, M, c/)-kód C maximální. Pak, je-li přeneseno slovo c a nastane-li d nebo více chyb, tj. d(c,x) > d, bude nutně x bližší k jinému kódovému slovu d^ca tedy při použití pravidla minimální vzdálenosti nastane dekódovací chyba. Protože pravděpodobnost, že nastane právě k chyb při průchodem binárním symetrickým kanálem, je nk)pk0-P) n-k obdržíme následující dolní hranici pro pravěpodobnost dekódovací chyby n ( 1 jPk0 ~P)n~k < P(nastala chyba při dekódování) k=d Kódování a odhady Ekvivalence kódů Hlavní problém TK Obsah Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Q Ekvivalence kódů a konstrukce nových kódů • Základní pojmy • Vlastnosti ekvivalentních kódů • Konstrukce kódů Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vlastnosti Konstrukce Fl Užitečným prostředkem pro redukci množství práce při nalezení dobrých kódů je pojem ekvivalence kódů. Předpokládejme, že máme (n, M, d)-kóá C. Přirozeným způsobem jeho prezentace je pomocí matice o rozměrech M x n, přičemž řádky jsou různá kódová slova. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vlastnosti Konstrukce Fl Užitečným prostředkem pro redukci množství práce při nalezení dobrých kódů je pojem ekvivalence kódů. Předpokládejme, že máme (n, M, d)-kóá C. Přirozeným způsobem jeho prezentace je pomocí matice o rozměrech M x n, přičemž řádky jsou různá kódová slova. Předpokládejme nyní, že tt je permutace množiny {1,2, ..., n} a pro každé kódové slovo c e C budeme aplikovat transformaci 7f: C C definovanou předpisem ťť(c) = (c^-i),..., c7r(A?)). Takovou transformaci nazýváme poziční permutací. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vlastnosti Konstrukce Podobně, je-li tv permutace množiny Z, pak pro každý index /, 1 < i < n můžeme aplikovat transformaci tt, : C -> C definovanou předpisem ř.ícv_í CJ pokud / ^ j \ 7r(c/) pokud i = j. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vlastnosti Konstrukce Podobně, je-li tv permutace množiny Z, pak pro každý index /, 1 < i < n můžeme aplikovat transformaci tt, : C -> C definovanou předpisem ř.ícv_í CJ pokud / ^ j \ 7r(c/) pokud i = j. Mluvíme pak o symbolové permutací. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Zé Základní pojmy Vlastnosti Konstrukce Podobně, je-li tv permutace množiny Z, pak pro každý index /, 1 < i < n můžeme aplikovat transformaci tt, : C -> C definovanou předpisem ř.ícv_í CJ pokud / ^ j \ 7r(c/) pokud i = j. Mluvíme pak o symbolové permutací. Lze-li kód C získat z kódu C pomocí konečné posloupnosti pozičních nebo symbolových permutací, říkáme že kód C je ekvivalentní kódu C. Další kódy Problémy Zé Základní pojmy Vlastnosti Konstrukce Kódování a odhady Ekvivalence kódů Hlavní problém TK Příklady Příklad 2.1 Hranice Aq(n, d) Lineární kódy Cyklické kódy Předpokládejme, že máme kód C délky 5 nad abecedou Z = {a, b, c] s kódovými slovy c-i, c2, c3 a c4 tak, že a b c a c " b a b a b b c c b a c b a c a _ Aplikujeme-li permutaci (1^2,2^3,... ,5^1), obdržíme poziční permutaci a k n í odpovídající ekvivalentní kód je c a b c a " b b a b a a b c c b a c b a c Kódování a odhady Ekvivalence kódů Hlavní problém TK Příklady Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Zé Základní pojmy Vlastnosti Konstrukce Příklad 2.1 (Pokračování) Podobně, aplikujeme-li permutaci (a h> b,b h> c, c h> a) na první sloupec kódu C, obdržíme symbolovou permutaci a k ní odpovídající ekvivalentní kód je C" = a a b c a c b a b a b b c c b _ b c b a c Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Zé \/\ ákladní pojmy Vlastnosti Konstrukce Vlastnosti ekvivalentních kódů Lemma 2.2 Jsou-li C a C ekvivalentní kódy, jsou množiny vzdáleností kódových slov z C a C stejné. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Další kódy Lineární kódy Problémy Cyklické kódy Vlastn ;vivalentních kódů akladni pojmy astnosti Konstrukce Lemma 2.2 Jsou-li C a C ekvivalentní kódy, jsou množiny vzdáleností kódových slov z C a C stejné. Důkaz. Protože jak poziční tak symbolová permutace zachovávají vzdálenost permutovaných slov, platí totéž i pro takovouto posloupnost permutací. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Zé \/\ ákladní pojmy Vlastnosti Konstrukce Vlastnosti ekvivalentních kódů Lemma 2.3 Je-li C kód délky n au vektor délky n nad stejnou abecedou, pak existuje kódC, který je ekvivalentní s C a obsahuje vektor u. Důkaz. První kódové slovo c-i lze převést na u pomocí nejvýše n symbolových permutací. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Konstrukce kódu Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Definition 2.4 Buď x, y binární slova délky n. Průnik x n y binárních slov x a y je binární řetězec délky n, který má jedničku přesně na těch místech, na kterých ji mají obě slova x a y. Všude jinde má pak nuly. Jinak řečeno, xny = x1 • x2 • yz • • Xn • Yn- Platí pak následující jednoduché lemma. Lemma 2.5 Jsou-li x a y binární řetězce délky n, pak c/(x, y) = wt(x) + wt(y) - 2wt(x n y). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Konstrukce kódů - rozšíření kódu Základní pojmy Vlastnosti Konstrukce Důkaz Věty 2.5. Položme A|-| = {/ : 1 < / < n,x, = y, = 1}, a-n = card(/\11), >Aio = {/: 1 Aio = {/: 1 < t > , t > t c-i c2... cn0 pokud wt(c) je sudá, c-i c2... cn1 pokud wt(c) je lichá. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineárni kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce ^^^^^^ :e kódu - koni trola parity Totiž, protože všechna kódová slova v C mají sudou váhu, bude vzdálenost mezi každými dvěma slovy sudé číslo (to plyne z lemmatu 2.5). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - kontrola parity Totiž, protože všechna kódová slova v C mají sudou váhu, bude vzdálenost mezi každými dvěma slovy sudé číslo (to plyne z lemmatu 2.5). Je tedy i minimální vzdálenost kódu Č sudé číslo. Nutně pak dostáváme, že, je-li d(C) = d sudé číslo a nastává pro pro slova c, d, pak nutně mají obě slova stejnou paritu a tedy nutně platí d(c, d) = d(č, ď). Je tedy d(C) = d(Č). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - kontrola parity Totiž, protože všechna kódová slova v C mají sudou váhu, bude vzdálenost mezi každými dvěma slovy sudé číslo (to plyne z lemmatu 2.5). Je tedy i minimální vzdálenost kódu Č sudé číslo. Nutně pak dostáváme, že, je-li d(C) = d sudé číslo a nastává pro pro slova c, d, pak nutně mají obě slova stejnou paritu a tedy nutně platí d(c, d) = d(č, ď). Je tedy d(C) = d(Č). Nechť je minimální vzdálenost kódu C liché číslo a nastává pro pro slova c, d, pak nutně má jedno ze slov sudou paritu (například c) a druhé lichou paritu (d). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - kontrola parity Pak wt(c) = wt(c), w(d) + 1 = w(d), w(c n d) = w(c n d). Tedy d(C) + 1 = d(Č). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - kontrola parity Pak wt(c) = wt(c), w(d) + 1 = w(d), w(c n d) = w(c n d). Tedy d(C) + 1 = d(Č). V obou případech pak máme L^(d(C)-1)J = ^(d(Č)-1)j. Kódování a odhady Hranice Aq(n, d) Další kódy 7ák|adní ■ Konstrukt ,—, . , , . ,< , . , . , , r-i i_i ' £-dl\lclvJill UU lily r\UiloLíUl\utJ Ekvivalence kodu Lineami kody Problémy r J 3 Hlavní problém TK Cyklické kódy Konstrukce kódů - kontrola parity Vlastnosti Pak wt(c) = wt(c), w(d) + 1 = w(d), w(c n d) = w(c n d). Tedy d(C) + 1 = d(Č). V obou případech pak máme L^(d(C)-1)J = L^(d(Č)-1)J. Z toho pak plyne, že se nám při použití kontroly parity nezvýší schopnost opravit chybu. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - kontrola parity Pak wt(c) = wt(c), w(d) + 1 = w(d), w(c n d) = w(c n d). Tedy d(C) + 1 = d(Č). V obou případech pak máme L^(d(C)-1)j = ^(d(Č)-1)j. Z toho pak plyne, že se nám při použití kontroly parity nezvýší schopnost opravit chybu. Obecně pak, máme-li kódovou abecedu vybránu tak, že nám tvoří konečné pole, řekněme Zp, kde p je prvočíslo, nebo obecně ¥q, můžeme definovat kontrolu parityjako n C = Ci p2 • • • , kde Cn+-| = — ^ Cj. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - zkrácení kódu Definice 4 Postup, při kterém odebereme ta kódová slova z daného kódu, která se liší na určené pozici i od určeného symbolu s, a ze zbývajících slov tuto pozici odstraníme, a tedy zkrátíme délku kódu, se nazývá zkrácení kódu typu x, = s. Je-li pak C (n, M, c/)-kód, má zkrácený kód Ce délku n - 1 a minimální vzdálenost alespoň d. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - zkrácení kódu Definice 4 Postup, při kterém odebereme ta kódová slova z daného kódu, která se liší na určené pozici i od určeného symbolu s, a ze zbývajících slov tuto pozici odstraníme, a tedy zkrátíme délku kódu, se nazývá zkrácení kódu typu x, = s. Je-li pak C (n, M, c/)-kód, má zkrácený kód Ce délku n - 1 a minimální vzdálenost alespoň d. Opravdu, zkrácení kódu může mít za důsledek podstatné zvětšení minimální vzdálenosti tedy i schopnosti opravit nového kódu, protože můžeme odstranit ta kódová slova, která se "špatně chovají vzhledem ke vzdálenosti". Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - zkrácení kódu Definice 4 Postup, při kterém odebereme ta kódová slova z daného kódu, která se liší na určené pozici i od určeného symbolu s, a ze zbývajících slov tuto pozici odstraníme, a tedy zkrátíme délku kódu, se nazývá zkrácení kódu typu x, = s. Je-li pak C (n, M, c/)-kód, má zkrácený kód Ce délku n - 1 a minimální vzdálenost alespoň d. Opravdu, zkrácení kódu může mít za důsledek podstatné zvětšení minimální vzdálenosti tedy i schopnosti opravit nového kódu, protože můžeme odstranit ta kódová slova, která se "špatně chovají vzhledem ke vzdálenosti". Samozřejmě ale zkrácením kódu se nám zmenší i počet kódových slov, což není zrovna lákavé. ><1><1> t Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - zkrácení kódu Věta 2.6 Buď d liché přirozené číslo. Pak existuje binární (n, M, d)-kód právě tehdy, když existuje binární (n+J\,M,d+J\ )-kód. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - zkrácení kódu Věta 2.6 Buď d liché přirozené číslo. Pak existuje binární (n, M, d)-kód právě tehdy, když existuje binární(n + 1, M, oř + 1 )-kód. Důkaz. Pokud existuje binární {n + 1, M, d + 1 )-kód C, můžeme snadno zkonstruovat binární (n, M, d)-kód. Jednoduše vybereme dvě kódová slova c a d tak, že d(c, d) = d + 1, najděme pozici, na které se liší a odebereme tuto pozici z každého kódového slova. Nový kód označíme C. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - zkrácení kódu Věta 2.6 Buď d liché přirozené číslo. Pak existuje binární (n, M, d)-kód právě tehdy, když existuje binární(n + 1, M, oř + 1 )-kód. Důkaz. Pokud existuje binární (n + 1, M, d + 1 )-kód C, můžeme snadno zkonstruovat binární (n, M, c/)-kód. Jednoduše vybereme dvě kódová slova c a d tak, že d(c, d) = d + 1, najděme pozici, na které se liší a odebereme tuto pozici z každého kódového slova. Nový kód označíme C. Nutně pak mají nová zkrácená slova ď a d; vzdálenost d(c;, d;) = d a žádná jiná dvě zkrácená slova nemají od sebe menší vzdálenost než d. Celkem je tedy C binární (n,M,cř)-kód. I o°<(y Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní pojmy Vlastnosti Konstrukce Konstrukce kódů - zkrácení kódu Pokračování důkazu Věty 2.6. Obráceně, předpokládejme, že máme binární (n, M, d)-kód V (d liché). Kód V, který vznikl jako kód kontroly parity z V, má délku n + 1, velikost M a minimální vzdálenost d + 1. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Obsah Hranice Aq(n, d) Lineární kódy Cyklické kódy Zá Další kódy Problémy Základní odhady Vlastnosti x r Q Hlavní problém teorie kódování • Základní odhady • Vlastnosti maximálních kódů o i r i 1^ | I I 1 » 1, i \ji i v i u 11 i w vy iv Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní odhady Vlastnosti Hlavní problém teorie kódování Definice 5 Fl Buď dána přirozená čísla d, n, q. Položme Aq(n, d) jakožto maximální M takové, že existuje q-ární(n, M, d)-kód. Každý takový q-ární(n, M, d)-kód nazýváme optimální. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní odhady Vlastnosti Hlavní problém teorie kódování Definice 5 Fl Buď dána přirozená čísla d, n, q. Položme Aq(n, d) jakožto maximální M takové, že existuje q-ární(n, M, d)-kód. Každý takový q-ární(n, M, d)-kód nazýváme optimální. Čísla Aq(n, d) hrají ústřední roli v teorii kódování a na jejich nalezení bylo vynaloženo velké úsilí. Často se mluví o hlavním problému teorie kódování. V dalším pro ilustraci určíme jisté hodnoty Aq(n, d) pro malé hodnoty nad a dokážeme obecná tvrzení o těchto číslech. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní odhady Vlastnosti Hlavní problém teorie kódování Definice 5 Fl Buď dána přirozená čísla d, n, q. Položme Aq(n, d) jakožto maximální M takové, že existuje q-ární(n, M, d)-kód. Každý takový q-ární(n, M, d)-kód nazýváme optimální. Čísla Aq(n, d) hrají ústřední roli v teorii kódování a na jejich nalezení bylo vynaloženo velké úsilí. Často se mluví o hlavním problému teorie kódování. V dalším pro ilustraci určíme jisté hodnoty Aq(n, d) pro malé hodnoty nad a dokážeme obecná tvrzení o těchto číslech. Poznamenejme, že abychom dokázali, že Aq(n, d) = K pro jisté přirozené číslo K, stačí ověřit, že Aq(n, d) < K a následně najít vhodný g-ární (n, K, ď)-kód C, kde d < ď. Pak totiž Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Základní odhady Vlastnosti Hlavní problém teorie kódování Věta 3.1 Je-li d sudé číslo, je A2{n, d) = A2(n - 1, d - 1). Důkaz. Plyne okamžité z vety 2.6. Totiž pak nutné platí A2(n, d) < A2(n - 1, d - 1) a A2(n, d) > A2(n - 1, d - 1). I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní odhady Vlastnosti Hlavní problém teorie kódování Věta 3.1 Je-li d sudé číslo, je A2{n, d) = A2{n - 1, d - 1). Důkaz. Plyne okamžité z vety 2.6. Totiž pak nutné platí A2(n, d) < A2(n - 1, d - 1) a A2(n, d) > A2(n - 1, d - 1). I Důsledek 3.2 Je-li d sudé číslo a existuje binární (n, M, d)-kód, pak existuje binární (n, M, d)-kód, ve kterém mají všechna kódová slova sudou váhu. Důkaz. Dle Věty 3.1 nutně existuje binární kód (n - 1, M, d - 1 )-kód a pomocí operace kontroly parity existuje binární (n, M, d)-kód, ve kterém mají všechna kódová slova sudou váhu. ■ I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní odhady Vlastnosti Hlavní problém teorie kódování Následující dva snadné výsledky nám budou ilustrovat, jakým způsobem můžeme určit hodnoty A2(n, d) pro malé hodnoty n a d. Použijeme přitom lemma 2.3, ze kterého plyne, že pro daný (n, M, c/)-kč>d C existuje ekvivalentní (n, M, d)-kóá C, který obsahuje nulové slovo (samozřejmě za předpokladu, že kódová abeceda obsahuje 0 - jinak ji lze dodat záměnou za jiný symbol). Můžeme tedy v dalším předpokládat, že naše kódy obsahují nulové slovo. Věta 3.3 PlatíA2(4,3) = 2. Kódování a odhady Ekvivalence kódů Hlavní problém TK 4>(4,3) = Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní odhady Vlastnosti Důkaz. Buď C nějaký (4, M,3)-kód. Můžeme bez újmy na obecnosti předpokládat, že 0 = 0000 e C. Protože d(C) = 3, libovolné další kódové slovo c z C musí splňovat d(c, 0) > 3 a tedy musí obsahovat alespoň tři jedničky. Máme tedy celkem pět možností pro nenulová slova ležící v C, a to 1110,1101,1011,0111,1111. Ale každá takováto dvě slova mají vzdálenost nejvýše 2. Proto pouze jedno z nich může být obsaženo v C. Platí tedy A>(4,3) < 2. Dále platí, protože C = {0000,1110} je (4,2,3)-kód, máme /A2(4,3) > 2 a tedy celkem /A2(4,3) = 2. I Kódování a odhady Ekvivalence kódů Hlavní problém TK 4>(5,3) = Hranice Aq(n, d) Lineární kódy Cyklické kódy Věta 3.4 Další kódy Problémy Základní odhady Vlastnosti Platí A2{5,3) = 4. ] Důkaz. Buď C nějaký (5, M, 3)-kód. Můžeme bez újmy na obecnosti předpokládat, že 0 = 00000 e C a přitom pro vhodné c z C platí d(0, c) = 3, Ci = 0. Uvažme nyní zkrácení C® typu x-\ = 0. Víme pak, že 0®, c® e C® a d(0®, c°) = 3. Dále víme, že A2(4,3) = 2. Tedy i card(C®) = 2. Definujme nyní zkrácený kód C® jakožto zkrácení typu typu x^=J\. Pak buďto card(Ce) = 1 nebo card(Ce) > 1 a d(Ce) = 3. V posledním případě pak card(Ce) < /A2(4,3) = 2. Celkem tedy card(Ce) + card(C°) = card(C) < 4. Platí tedy A2(5,3) < 4. Dále platí, protože C = {00000,11100,00111,11011} je (5,4,3)-kód, máme A2{5,3) > 4 a tedy celkem A2(5,3) = 4. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní odhady Vlastnosti Vlastnosti maximálních kódu Platí následující: O Aq(n,d) < qn pro všechna 1 < d < n; O Aq(n,J\) = qn; O Aq(n, rí) = q. Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy kladní odhady Vlastnosti Vlastnosti maximálních kódů 1 Věta 3.5_ _ Platí následující: O Aq(n, d) < qn pro všechna 1 < d < n; Q Aq(n, 1) = qn; O Aq(n, n) = q. ' Důkaz. 1 První tvrzení platí, protože pro každý kód C je C c Vn{q) tj. card(C) < qn. 0 0,0 Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy kladní odhady Vlastnosti Vlastnosti maximálních kódů 1 Věta 3.5_ _ Platí následující: O Aq(n, d) < qn pro všechna 1 < d < n; Q Aq(n, 1) = qn; O Aq(n, n) = q. ' Důkaz. 1 První tvrzení platí, protože pro každý kód C je C c Vn{q) tj. card(C) < qn. Druhé tvrzení plyne z toho, že uvážíme-li C = Vn(q), máme d(Vn(q)) = l. 0 0,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní odhady Vlastnosti Vlastnosti maximálních kódu Platí následující: O Aq(n, d) < qn pro všechna 1 < d < n; O Aq(n, 1) = qn; O Aq(n, n) = q. Důkaz. První tvrzení platí, protože pro každý kód C je C c Vn(q) tj. card(C) < qn. Druhé tvrzení plyne z toho, že uvážíme-li C = Vn(q), máme d(Vn(q)) = ^. Třetí část plyne z toho, že se kódová slova musí lišit na všech pozicích a takových kódových slov můžeme vybrat nejvýše q. Ale máme, pro kód V = {0,..., q-1}, že V je (n, g, n)-kód. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní odhady Vlastnosti Vlastnosti maximálních kódu Už pro malé hodnoty q,n ad není velikost Aq(n, d) známa. Následující tabulka shrnuje většinu našich znalostí o A2(n, d) n d = 3 d = 5 d=7 5 4 2 - 6 8 2 - 7 16 2 2 8 20 4 2 9 40 6 2 10 72-79 12 2 11 144-158 24 4 12 256 32 4 13 512 64 8 14 1024 128 16 15 2048 256 32 16 2560-3276 256-340 36-37 < = ► 4 = ► Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy vlastnosti n mmsĚ I kladní odhady Vlastnosti Poznamenejme, že problém určení A2(n, d) je problémem konečných geometrií. □ s Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Základní odhady Vlastnosti Vlastnosti maximálních kódu Poznamenejme, že problém určení A2{n, d) je problémem konečných geometrií. Pro odhad Aq(n, d) platí následující jednoduché tvrzení._ Věta 3.6 Pro všechna n>2, Aq(n1d)2, Aq{n,d) < qAq{n-Ji,d). (3.1) Důkaz. Buď C kód realizující hodnotu Aq(n, d). Uvažme nyní zkrácení Cj typu xn = y. Pak nutně card(Cy) < Aq(n- 1, oř) (mohou totiž nastat pouze dva případy: card(Cy) = 1, což evidentně platí, a K = card(Cy) > 1, kde pak q je (n - 1, /C, ď)-kód, ď > d a tedy tvrzení rovněž platí). Celkem pak C = U/=o ci *]■ Mn> d) = Ej=o card(Cy) < qAq(n - 1, oř). I Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy kladní odhady Vlastnosti Vlastnosti maximálních kódů 1 Cvičení 3.7 Kódování a odhady Ekvivalence kódů Hlavní problém TK Obsah Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Dolní hranice Horní hranice Perfektní kódy Další hranice • Horní hranice • Perfektní kódy • Další hranice r r ' ° I r I Q Dolní a horní hranice Reed-Mullerovy kódy Aq(n, d)\ perfektní kódy o Dolní hranice O Problémy Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Dc olní hranice Horní hranice Perfektní kódy Další hranice Dolní a horní hranice Aq(n, d) Fl Určeme nejprve horní hranici (sphere-packing upper bound) čísla Aq(n, d). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Dc olní hranice Horní hranice Perfektní kódy Další hranice Dolní a horní hranice Aq(n, d) Fl Určeme nejprve horní hranici (sphere-packing upper bound) čísla Aq(n, d). Lemma 4.1 Nechť e= [Ud - 1 )J. Pak platí Aq(n,d)J2(nk)(q-Vk qn k=0 ^ ' Perfektní kódy Další hranice (4.3) Důkaz. Buď C (n, M, c/)-kód s maximálním počtem kódových slov. Pak zcela jistě neexistuje vektor z Vn(q) - C, jehož vzdálenost od všech kódových slov je alespoň d, jinak by totiž M nebyl maximální počet kódových slov. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy olni hranice rní hranice Dolní a horní hráni Podobně platí Lemma 4.2 i (Gilbert-Varshamovova hranice) Aq(n,d)J2(nk)(q-i)k>qn k=0 ^ ' Perfektní kódy Další hranice (4.3) Důkaz. Buď C (n, M, c/)-kód s maximálním počtem kódových slov. Pak zcela jistě neexistuje vektor z Vn(q) - C, jehož vzdálenost od všech kódových slov je alespoň d, jinak by totiž M nebyl maximální počet kódových slov. Jinak řečeno, koule o poloměru d musí pokrývat celý prostor Vn(q). Ale to je přesně podmínka (4.3). I 0 0,0 Kódování a odhady Hranice Aq(n d) Další kódy Do|n( hranice Perfektní kód/ Ekvivalence kodu Linearni kody Problémy Homí hranice Další hranice Hlavni problém TK_Cyklické kody_ Poloměr pokrytí blokového kódu Definice 6 Poloměr pokrytí blokového kódu C je nejmenšípoloměr p takový, že ceC Dále pro každé f e FJJ klademe d(f, C) = minCec d(c, f). Kódovaní a odhady Hranice Aa(n, d) Dalsi kody ^ ,-, . . . . ,o .. r. ui- Dolní hranice Perfektní kody Ekvivalence kodu Lineami kody Problémy ..... ~ . Hlavní problém TK Cyklické kódy Horní hranice Dals. hranice Poloměr pokrytí blokového kódu Definice 6 Poloměr pokrytí blokového kódu C je nejmenšípoloměr p takový, že W"qc{J sp(c). ceC Dále pro každé f g klademe d(f, C) = minCGc d(c, f). Polomer pokrytí je další charakterizací kódu, nemá však tak hojné uplatnění jako minimální vzdálenost. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Poloměr pokrytí blokového kódu Dc olní hranice Horní hranice Perfektní kódy Další hranice Věta 4.3 Nechť C je blokový kód délky n. Pak p je poloměr pokrytí kódu C právě tehdy když platí p = max min d(c, f). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Poloměr pokrytí blokového kódu Dc olní hranice Horní hranice Perfektní kódy Další hranice Věta 4.3 Nechť C je blokový kód délky n. Pak p je poloměr pokrytí kódu C právě tehdy když platí p — max min d(c, f). Důkaz Věty 4.3. Nechť ¥nq c \JceC Sp(c), kde p je minimální. Pak pro každé f £ Fg existuje c e C takové, že d(c,f) < p, a současně existují ť e ¥nq a ď e C splňující d(ď, ť) = p. S -f) <\cy Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Poloměr pokrytí blokového kódu Dc olní hranice Horní hranice Perfektní kódy Další hranice Věta 4.3 Nechť C je blokový kód délky n. Pak p je poloměr pokrytí kódu C právě tehdy když platí p — max min d(c, f). Důkaz Věty 4.3. Nechť F£ c |JceC Sp(c), kde p je minimální. Pak pro každé f e F£ existuje c e C takové, že d(c,f) < p, a současně existují f e Fg a c' g C splňující d(c',ť) = p. Z minimality p plyne, že p = maxf€Fn d(f, C) = maxfeFn minC6C d(c, f). I Kódovaní a odhady Hranice Aa(n, d) Dalsi kody ^ ,-, . . . . ,o .. r. ui- Dolní hranice Perfektní kody Ekvivalence kodu Lineami kody Problémy ..... ~ . Hlavní problém TK Cyklické kódy Horní hranice Dals. hranice Poloměr pokrytí blokového kódu Pokračování důkazu Věty 4.3. Naopak, nechť p = maxfGFj7 minCGed(c,f) = maxfGFj7 d(f,C). Pak pro všechna f e platí p > d(f, C) a existují f e F£ a ď g C splňující rovnost p = d(c', ť) a pro všechna c g C je P d(f, C) a existují f e F£ a ď g C splňující rovnost p = d(c', ť) a pro všechna c g C je P s, takové, že každé f g F£J je prvkem množiny {x g | d(c, x) < s} pro nějaké c g C. To je ale spor s existencí slov ť a ď, a tedy p je poloměr pokrytí kódu C. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Perfektní kódy Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Dolní hranice Horní hranice Perfektní kódy Další hranice Ideální situace z ekonomického pohledu je najít kód C nad Vn(q) tak, že pro jisté kladné t > 0 jsou všechny prvky z Vn(q) obsaženy v disjunktním sjednocení koulí, jejichž středy jsou navzájem různá kódová slova. Takový kód se pak nazývá perfektní. Z jeho definice je zřejmé, že perfektní kód dokáže pomocí pravidla minimální vzdálenosti opravit až t chyb, a nedokáže opravit t + 1 chyb. Ideální situace z ekonomického pohledu je najít kód C nad Vn(q) tak, že pro jisté kladné t > 0 jsou všechny prvky z Vn(q) obsaženy v disjunktním sjednocení koulí, jejichž středy jsou navzájem různá kódová slova. Takový kód se pak nazývá perfektní. Z jeho definice je zřejmé, že perfektní kód dokáže pomocí pravidla minimální vzdálenosti opravit až t chyb, a nedokáže opravit t + 1 chyb. Je tedy nutná podmínka pro to, aby (n, M, d)-kóá byl perfektní, že d je liché číslo. Celkem tedy je (n, M, oř)-kód perfektní právě tehdy, když M = Aq(n, d) a (4.4) Kódování a odhady Ekvivalence kódů Hlavní problém TK Perfektní kódy Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Dolní hranice Horní hranice Perfektní kódy Další hranice Příklad 4.4 Zřejmým příkladem perfektního kódu je O každý kód s právě jedním kódovým slovem, O každý binární kód s právě dvěma slovy lichých délek, např. 00...0a11 ...1. Tyto kódy se nazývají triviální perfektní kódy. Kódování a odhady Ekvivalence kódů Hlavní problém TK Perfektní kódy Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Dolní hranice Horní hranice Perfektní kódy Další hranice Obrázek 4: Perfektní kód s minimální vzdáleností 1. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Další kódy Lineární kódy Problémy Cyklické kódy Dolní hranice Perfektní kódy Horní hranice Další hranice Další hráni ce - Singletonova hranice r Věta 4.5_ 1 (Singletonova hranice) Platí Aq(n,d)• N definovaná jako f{k) = k(M - k) nabývá svého maxima pro M2 — I "o puKuu ivi je suue, _ ■ k=< . ař(/c) = pokud A/fje liché. M±Jl pokud M je liché, 4 M2-1 pokud M je sudé, Důkaz. Důkaz okamžitě plyne ze vztahu V a • b < \{a + b) a z průběhu funkce f. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Dolní hranice Horní hranice Perfektní kódy Další hranice Další hranice - Plotkinova hranice Lemma 4.6 Buď M přirozené číslo. Pak funkce ř:{0,...,M}-^N definovaná jako f(k) = k(M - k) nabývá svého maxima pro M2 — I ~2 poKuu ivi je suue, _ i k = < ... . a^(^) = pokud M je liché. M±Jl pokud M je liché, 4 M2-1 pokud M je sudé, Důkaz. I Důkaz okamžitě plyne ze vztahu V a • b < \{a + b) a z průběhu funkce f. I Věta 4.7 (Plotkinova hranice) Je-li n < 2d, máme A2{n,d)<2[ d 2d-n (4.6) 0 0,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Dolní hranice Horní hranice Perfektní kódy Další hranice Další hranice - Plotkinova hranice Důkaz. MA Buď C = fa,..., cM} nějaký (n, M, cř)-kód. Uvažme součet S = J2icy M 2 (4.7) Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Dolní hranice Horní hranice Perfektní kódy Další hranice Další hranice - Plotkinova hranice Důkaz. MA Buď c = {c-i,..., cM} nějaký (n, M, oř)-kód. Uvažme součet S = Yjícf Pokusme se nyní spočítat S tím, že se podíváme na každou pozici zvlášť. Uvažme tedy kódová slova ve tvaru (4.7) Cl c2 Ci 1 Ci 2 • • • Ci n P21 c22 • • • C2n Kódovaní a odhady Hranice Aain, d) Dalsi kody ^ ,-, . . . , ,o .. r. ui- Dolní hranice Perfektní kody Ekvivalence kodu Lineami kody Problémy ..... ~ . Hlavní problém TK Cyklické kódy Horní hranice Dals. hranice Další hranice - Plotkinova hranice Důkaz. Máme pak, pro všechna /, 1 0 °>3) < 93- O Ukažte, že pro všechna přirozená čísla q > parametry n = (qr - 1)/(q- 1), M = qn~r, d = 3, kde r je nějaké přirozené číslo > 2, splňují podmínku (4.4) proto, aby se jednalo o perfektní kód. Poznamenejme, že ačkoliv tyto parametry splňují (4.4) pro každé přirozené číslo q, byla vyslovena hypotéza, že příslušné perfektní kódy existují právě tehdy, když je q mocnina prvočísla. Kódování a odhady Ekvivalence kódů Hlavní problém TK Obsah Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy G( Generující matice Použití Vzdálenost Hamming I CL r i o • Generující matice • Použití lineárních kódů • Pravidlo minimální vzdálenosti pro lineární kódy • Binární Hammingovy kódy o Da hl Ě\ t 1/ i Q Lineární kódy UUIUIkIga ► < ► < ► < ► = ^)q,o Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Fl Předpokládejme, že C je kód s minimální vzdáleností d = 2e + 1 a lze tedy pomocí metody nejbližšího kódového slova opravit až e chyb. Má-li kód C málo prvků, jedná se o velmi praktickou metodu. V případě, že číslo \C\ bude velké, bude tato metoda opravdu velmi časově náročná, protože musíme srovnávat přijatý vektor y s velkým množstvím kódových slov. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Fl Předpokládejme, že C je kód s minimální vzdáleností d = 2e + 1 a lze tedy pomocí metody nejbližšího kódového slova opravit až e chyb. Má-li kód C málo prvků, jedná se o velmi praktickou metodu. V případě, že číslo \C\ bude velké, bude tato metoda opravdu velmi časově náročná, protože musíme srovnávat přijatý vektor y s velkým množstvím kódových slov. To je důvod pro studium více strukturovaných kódů, jako jsou např. lineární kódy. Předpokládejme tedy, že počet prvků q naší abecedy je prvočíselná mocnina pm. Můžeme tedy považovat Z za těleso FQ o g-prvcích. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Buď dále Vn{q) vektorový prostor dimenze n nad tělesem F< Typický prvek tohoto vektorového prostoru budeme psát jakožto x = (x-i,..., xn), občas pak zkráceně jakožto x = x-i ... xn, kde Xj e ¥a. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Buď dále Vn{q) vektorový prostor dimenze n nad tělesem Fq. Typický prvek tohoto vektorového prostoru budeme psát jakožto x = (x-i,..., xn), občas pak zkráceně jakožto x = x-i ... xn, kde Xj e ¥q. Lineární kód C nad Z je definován jakožto podprostor prostoru Vn(q). Má-li tento podprostor dimenzi k, mluvíme o [n, /c]-kódu nebo, chceme-li specifikovat minimální vzdálenost, mluvíme o [n, k, c/]-kč>du. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Buď dále Vn{q) vektorový prostor dimenze n nad tělesem Fq. Typický prvek tohoto vektorového prostoru budeme psát jakožto x = (x-i,..., xn), občas pak zkráceně jakožto x = x-i ... xn, kde Xj e ¥q. Lineární kód C nad Z je definován jakožto podprostor prostoru Vn(q). Má-li tento podprostor dimenzi k, mluvíme o [n, /c]-kódu nebo, chceme-li specifikovat minimální vzdálenost, mluvíme o [n, k, c/]-kč>du. Protože každý /c-dimenzionální podprostor nad ¥q má qk prvků, máme: Každý [n, k, d]-kód nad ¥q je (n, qk, d)-kód. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Výhoda lineárních kódů je to, že pomocí k kódových slov délky n můžeme zcela popsat kód s právě qk kódovými slovy délky n. Tím dosáhneme obrovské úspory paměti. Totiž každý podprostor dimenze k je úplně popsán k lineárně nezávislými vektory. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Výhoda lineárních kódů je to, že pomocí k kódových slov délky n můžeme zcela popsat kód s právě qk kódovými slovy délky n. Tím dosáhneme obrovské úspory paměti. Totiž každý podprostor dimenze k je úplně popsán k lineárně nezávislými vektory. Definujeme pak generující matici pro lineární [n, /c]-kód C jakožto libovolnou matici rozměru híi, jejíž řádky tvoří k lineárně nezávislých kódových slov z C. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Předpokládejme nyní, že G je generující matice kódu C a G je matice, kterou můžeme obdržet z G pomocí konečné posloupnosti permutací následujícího typu: O záměna řádků, O násobení řádku nenulovým skalárem, Q přičtení k řádku skalární násobek jiného řádku, O záměna sloupců, 0 násobení sloupce nenulovým skalárem. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pak lze snadno ukázat následující tvrzení. G je generující matice kódu C, který je ekvivalentní s kódem C. Důkaz. Stačí ukázat, že každá z operací (1)-(5) odpovídá vytvoření generující matice G kódu C, který je ekvivalentní s kódem C. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pak lze snadno ukázat následující tvrzení. Lemma 5.1 G je generující matice kódu C, který je ekvivalentní s kódem C. Důkaz. Stačí ukázat, že každá z operací (1)-(5) odpovídá vytvoření generující matice G kódu C, který je ekvivalentní s kódem C. Evidentně, záměna řádků, vynásobení řádku nenulovým skalárem a přičtení řádků jsou operace takové, že dokonce kód C je totožný s kódem C. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pak lze snadno ukázat následující tvrzení. Lemma 5.1 G je generující matice kódu C, který je ekvivalentní s kódem C. Důkaz. Stačí ukázat, že každá z operací (1)-(5) odpovídá vytvoření generující matice G kódu C, který je ekvivalentní s kódem C. Evidentně, záměna řádků, vynásobení řádku nenulovým skalárem a přičtení řádků jsou operace takové, že dokonce kód C je totožný s kódem C. Záměna sloupců v matici G znamená, že provedeme poziční permutaci určenou transpozicí sloupců. Vynásobení sloupce nenulovým skalárem je symbolová permutace tohoto sloupce (pracujeme nad tělesem a pak je množina nenulových skalárů grupou). Jsou tedy odpovídající kódy ekvivalentní s kódem C. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Lemma 5.2 Buď G matice typu k x n jejíž řádky jsou lineárně nezávislé; pak, aplikujeme-li posloupnost operací typu (1)-(5) na G, je možné G převést na matici G' = [Ek, A], kde Ek je jednotková matice typu k x k. Důkaz je veden indukcí vzhledem ke k. Pokud k = 1, je tvrzení evidentní. Lze bez újmy na obecnosti předpokládat, že prvek gin je nenulový (to lze vždy zajistit záměnou sloupců). Stačí pak vynásobit řádek matice G prvkem inverzním k prvku g^. Předpokládejme, že tvrzení platí pro k a chceme jej dokázat pro k +1. Protože hodnost matice G je k + 1 existuje v matici G /c+1 nezávislých sloupců. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pokračování důkazu Lemmatu 5.2 Pomocí operace typu (4) tyto sloupce dostaneme na prvních k + 1 sloupců nové matice G. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pokračování důkazu Lemmatu 5.2 Pomocí operace typu (4) tyto sloupce dostaneme na prvních k + 1 sloupců nové matice Gř. Na prvních k nezávislých řádků matice G lze pak aplikovat indukční předpoklad a obdržíme matici, která má na prvních k řádcích submatici typu [Ek,A]. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pokračování důkazu Lemmatu 5.2 Pomocí operace typu (4) tyto sloupce dostaneme na prvních k + 1 sloupců nové matice Gř. Na prvních k nezávislých řádků matice G lze pak aplikovat indukční předpoklad a obdržíme matici, která má na prvních k řádcích submatici typu [Ek,A]. Pomocí řádkových úprav pak zajistíme, že (k + 1 )-ní řádek bude mít na prvních k pozicích nulové prvky. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pokračování důkazu Lemmatu 5.2 Pomocí operace typu (4) tyto sloupce dostaneme na prvních k + 1 sloupců nové matice Gř. Na prvních k nezávislých řádků matice G lze pak aplikovat indukční předpoklad a obdržíme matici, která má na prvních k řádcích submatici typu [Ek,A]. Pomocí řádkových úprav pak zajistíme, že (k + 1 )-ní řádek bude mít na prvních k pozicích nulové prvky. Protože všechny naše úpravy zachovávají hodnost, bude v (k + 1)-ním sloupci v (k + 1)-ním řádku nenulový prvek. Stačí pak vynásobit (k + 1 )-ní řádek inverzním prvkem k tomuto prvku. ■ Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Generující matice Vzdálenost Použití Hamming Pokračování důkazu Lemmatu 5.2 Pomocí operace typu (4) tyto sloupce dostaneme na prvních k + 1 sloupců nové matice G. Na prvních k nezávislých řádků matice G lze pak aplikovat indukční předpoklad a obdržíme matici, která má na prvních k řádcích submatici typu [Ek,A]. Pomocí řádkových úprav pak zajistíme, že (k + 1 )-ní řádek bude mít na prvních k pozicích nulové prvky. Protože všechny naše úpravy zachovávají hodnost, bude v (k + 1)-ním sloupci v (k + 1)-ním řádku nenulový prvek. Stačí pak vynásobit (k + 1 )-ní řádek inverzním prvkem k tomuto prvku. ■ V důsledku 5.2 můžeme bez újmy na obecnosti pracovat s generujícími maticemi ve výše uvedené standardní formě. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Lineární kódy - minimální vzdálenost Jinou užitečnou vlastností lineárních kódů je, že jejich minimální vzdálenost lze najít mnohem snáze, než v případu obecných kódů. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Lineární kódy - minimální vzdálenost Jinou užitečnou vlastností lineárních kódů je, že jejich minimální vzdálenost lze najít mnohem snáze, než v případu obecných kódů. Máme pak následující výsledek Věta 5.3 Minimální vzdálenost d lineárního kódu C je minimální váha w všech nenulových vektorů z C. Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Generující matice Vzdálenost Použití Hamming Lineární kódy - minimální vzdálenost Jinou užitečnou vlastností lineárních kódů je, že jejich minimální vzdálenost lze najít mnohem snáze, než v případu obecných kódů. Máme pak následující výsledek Věta 5.3 Minimální vzdálenost d lineárního kódu C je minimální váha w všech nenulových vektorů z C. Důkaz. Buď d minimální vzdálenost lineárního kódu C a předpokládejme, že x, y e C tak, že d(x, y) = d. Pak x - y e C, w(x - y) = d > w = w(z) = d(z, 0) > d pro vhodný vektor z g C. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy - použití Další kódy Problémy Generující matice Použití Vzdálenost Hamming Fl Předpokládejme, že C je lineární [n, k]-kód nad ¥q = Z a že má generující matice G tvaru G = ľ2 ľ/c = [Ek,A], kde r j jsou vektory délky n nad ¥q a A je matice typu k x (n- k). Kódová slova kódu C jsou vektory délky n tvaru a/r,-, a,- e Fq. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy - použití Další kódy Problémy Generující matice Použití Vzdálenost Hamming Základní myšlenka zakódování je následující. Pokud je zpráva braná jako posloupnost s = (s-i,..., Sk), zakódujeme s pomocí kódového slova c = (c-i,..., cn), kde c, jsou určena předpisem [C-|, . . . . Cn] — [S-l, . . . , sk] [Ek, A], (5.1) tj. Cj = Si pro 1 < i < k m Příklad 5.4 Předpokládejme, že kód C nad tělesem F3 (což je těleso zbytkových tříd po dělení 3) má generující matici G tvaru G = "10 0 12 0" 0 10 0 1 1 0 0 1 2 0 1 • Další kódy Problémy Generující matice Použití Vzdálenost Hamming Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy - použití Příklad 5.4 (Pokračování) Je-li vstupní zpráva ze zdroje tvaru 102101210122... rozdělíme ji nejprve do bloků délky tři a obdržíme 102|101|210|122 a pak zakódujeme zdrojová slova jakožto 102 i—^ r1 +2r3 = 102222, 101 ^ n + r3 = 101021 201 +r3 = 210221, 122 ^^ + 2r2 + 2r3 = 122211 Dostaneme tedy posloupnost 102 | 222 | 101 | 021 | 210 | 221 | 122 | 211 | ... Tedy jsme, při zdvojení délky zprávy, zpomalili rychlost přenosu na >olovic. Zvýšili isme ale spolehlivost. o Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy - použití Další kódy Problémy Generující matice Použití Vzdálenost Hamming Poznamenejme, že vztah (5.1) je ekvivalentní s rovnicí -AT,En_k\ [d ,..., cn]' =0. T (5.2) Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy - použití Další kódy Problémy Generující matice Použití Vzdálenost Hamming Poznamenejme, že vztah (5.1) je ekvivalentní s rovnicí -AT,En_k\ [d ,..., cn]' =0. T (5.2) Matice H = [-AT, En_k] se nazývá matice kontroly parity kódu C. Zejména tedy platí, že z e C právě tehdy, když H[z1,...,zf7]T = 0. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy - použití Další kódy Problémy Generující matice Použití Vzdálenost Hamming Poznamenejme, že vztah (5.1) je ekvivalentní s rovnicí -AT, En_k [d,..., cn]' =0. T (5.2) Matice H = [-AT, En_k] se nazývá matice kontroly parity kódu C. Zejména tedy platí, že z g C právě tehdy, když H[z1,...,zn]T = 0. Přitom matice H kontroly parity definuje jak vlastní kód C tak i příslušnou generující matici G. Název matice kontroly parity znamená, že na jistých kontrolních místech jsou přidány jisté kontrolní součty, které zkontrolují naše kódová slova. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy - použití Další kódy Problémy Generující matice Použití Vzdálenost Hamming Občas budeme pro [n, /c]-kód říkat, že prvních k složek kódového slova je nazýváno informačními znaky a zbývajících n - k složek jsou symboly kontroly parity {kontrolníznaky). Příklad 5.5 Určeme nyní matici H kontroly parity z příkladu 5.4. Ta má tvar H = -1 0 -2100 -2-1 0 0 10 0 -1-10 0 1 2 0 110 0 1 2 0 0 1 0 0 2 2 0 0 1 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy - použití Další kódy Problémy Generující matice Použití Vzdálenost Hamming Příklad 5.5 (Pokračování) Kódové slovo 102222 sestává ze zprávových čísel 102 a symbolů kontroly parity 222. Evidentně, rovnost (5.2) je pro toto kódové slovo (a všechna zbývající) splněna. Obecně musí tedy kódová slova splnit systém rovnic 2^+c3 + c4 = 0 ^+2c2 + c5 = 0 2c2 + 2c3 + c6 = 0. (5.3) Základní idea pro metodu opravování chyb je vidět na tomto příkladě. Předpokládejme, že naše obdržené slovo nesplňuje první a třetí rovnici (5.3) v rovnicích kontroly parity. Pak můžeme dedukovat, že chybná číslice zprávy je číslice c3, protože to je jediná číslice, která se vyskytuje v obou rovnicích. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Lineární kódy - použití Další kódy Problémy Generující matice Použití Vzdálenost Hamming Věta 5.6 Je-li H matice kontroly parity kódu C délky n, pak kód C má minimální vzdálenost d tehdy a jen tehdy když každých d - 1 sloupců matice H je nezávislých, ale některých d sloupců je lineárně závislých. Důkaz. Označme po řadě sloupce matice H jako h1,..., hn. Připomeňme, že pro každý řádkový vektor [c-i,..., cn] máme n [C-i, . . . , Cn]HT = ^ C/h- T /=1 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Pokračování důkazu Věty 5.6 G( enerujici matice Použití Vzdálenost Hamming Předpokládejme, že d je minimální počet lineárně závislých sloupců matice H. Pak existují skaláry c-i,..., cn, z nichž je právě d nenulových tak, že [C-|, . . . , Cn]HT = O7". Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Pokračování důkazu Věty 5.6 G( enerujici matice Použití Vzdálenost Hamming Předpokládejme, že d je minimální počet lineárně závislých sloupců matice H. Pak existují skaláry c-i,..., cn, z nichž je právě d nenulových tak, že [C-|, . . . , Cn]HT = O7". Ale to neříká nic jiného, že c = c-i ... cn e C. Protože wt(c) = d, máme d(C) < wt(c) = d. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Pokračování důkazu Věty 5.6 G( enerujici matice Použití Vzdálenost Hamming Předpokládejme, že d je minimální počet lineárně závislých sloupců matice H. Pak existují skaláry c-i,..., cn, z nichž je právě d nenulových tak, že [C-|, . . . , Cn]HT = O7". Ale to neříká nic jiného, že c = c-i ... cn e C. Protože wt(c) = d, máme d(C) < wt(c) = d. Obráceně, je-li c = c-i ... cn e C kódové slovo minimální délky, pak nutně [c-i,..., cn]HT = 0T a tedy je d(C) sloupců z H odpovídajícím d nenulovým prvkům lineárně závislých. Je tedy d < d(C) tj. d = d(C). i Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Fl Uvažme problém dekódování pro lineární kódy. Je-li C [n, k]-kóä nad abecedou Z = ¥q, pak C obsahuje qk kódových slov délky n a počet možných obdržených vektorů je qn. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Fl Uvažme problém dekódování pro lineární kódy. Je-li C [n, k]-kóä nad abecedou Z = ¥q, pak C obsahuje qk kódových slov délky n a počet možných obdržených vektorů je qn. Prohlížecí tabulka, která by pro každý možný obdržený vektor obsahovala "nejbližší" kódové slovo by zabírala příliš velké množství paměti, dokonce pro malá n a k. Jednou z hlavních výhod používání lineárních kódů je, že existuje elegantní způsob vyhnutí se výše uvedenému problému. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Fl Uvažme problém dekódování pro lineární kódy. Je-li C [n, k]-kóä nad abecedou Z = ¥q, pak C obsahuje qk kódových slov délky n a počet možných obdržených vektorů je qn. Prohlížecí tabulka, která by pro každý možný obdržený vektor obsahovala "nejbližší" kódové slovo by zabírala příliš velké množství paměti, dokonce pro malá n a k. Jednou z hlavních výhod používání lineárních kódů je, že existuje elegantní způsob vyhnutí se výše uvedenému problému. Tento postup popíšeme pouze v binárním případě. Rozšíření na jiné abecedy mohutnosti q = pm, kde p je prvočíslo je bezprostřední i když technicky náročnější. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Předpokládejme, že C je [n, /c]-binární kód. Protože je C podprostor vektorového prostoru Vn binárních vektorů délky n, musí být C podgrupa aditivní grupy Vn. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Předpokládejme, že C je [n, /c]-binární kód. Protože je C podprostor vektorového prostoru Vn binárních vektorů délky n, musí být C podgrupa aditivní grupy Vn. Připomeňme, že řád konečné grupy G je definovaný jako mohutnost \ G\ nosné množiny G, tj. počet prvků G a index [G : S] podgrupy S c G je počet \ G/S\ různých (levých) tříd rozkladu G podle S. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Předpokládejme, že C je [n, /c]-binární kód. Protože je C podprostor vektorového prostoru Vn binárních vektorů délky n, musí být C podgrupa aditivní grupy Vn. Připomeňme, že řád konečné grupy G je definovaný jako mohutnost |G| nosné množiny G, tj. počet prvků G a index [G : S] podgrupy S c G je počet \ G/S\ různých (levých) tříd rozkladu G podle S. Přitom (levá) třída určená prvkem a g G má tvar Sa = {sa : s g S}. Speciálně je přiřazení a h> Sa surjektivní homomorfismus G -> G/S. Přitom dvě třídy Sa, Sb jsou totožné právě tehdy, když a = s0b pro některé s0 g S. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Předpokládejme, že C je [n, /c]-binární kód. Protože je C podprostor vektorového prostoru Vn binárních vektorů délky n, musí být C podgrupa aditivní grupy Vn. Připomeňme, že řád konečné grupy G je definovaný jako mohutnost |G| nosné množiny G, tj. počet prvků G a index [G : S] podgrupy S c G je počet \ G/S\ různých (levých) tříd rozkladu G podle S. Přitom (levá) třída určená prvkem a g G má tvar Sa = {sa : s g S}. Speciálně je přiřazení a h> Sa surjektivní homomorfismus G -> G/S. Přitom dvě třídy Sa, Sb jsou totožné právě tehdy, když a = s0b pro některé s0 g S. Pravé násobení prvkem a je bijekce S Sa a proto má každá (levá) třída rozkladu stejný počet prvků jako podgrupa S. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Protože G je sjednocení příslušných levých tříd rozkladu, je počet prvků celé grupy G stejný jako počet tříd rozkladu krát počet prvků v S: \G\ = \G/S\ • |S|. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Protože G je sjednocení příslušných levých tříd rozkladu, je počet prvků celé grupy G stejný jako počet tříd rozkladu krát počet prvků v S: \G\ = \G/S\ • |S|. Zejména tedy kód C určuje soubor levých tříd {kosetů) podprostoru Vn a libovolný vektor a e Vn určuje jediný koset a + C = {b : b = a + c pro vhodný vektor c g C}. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Protože G je sjednocení příslušných levých tříd rozkladu, je počet prvků celé grupy G stejný jako počet tříd rozkladu krát počet prvků v S: |G| = \G/S\ • |S|. Zejména tedy kód C určuje soubor levých tříd {kosetů) podprostoru Vn a libovolný vektor a e Vn určuje jediný koset a + C = {b : b = a + c pro vhodný vektor c e C}. Předpokládejme tedy, že y je obdržený vektor v tom případě, že jisté kódové slovo bylo přeneseno kanálem. Řekneme, že vektor e je možný chybový vektor vektoru y, pokud existuje kódové slovo c e C tak, že Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Speciálně je tedy interpretace následující: vektor e je chybový vektor přidružený k obdrženému vektoru, jestliže je schopen reprezentovat jistou možnou posloupnost chyb při přenosu. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Speciálně je tedy interpretace následující: vektor e je chybový vektor přidružený k obdrženému vektoru, jestliže je schopen reprezentovat jistou možnou posloupnost chyb při přenosu. Následující triviální pozorování je klíčové. Lemma 5.7 Je-li y obdržený vektor, je množina možných chybových vektorů ten koset množiny C, který obsahuje vektory. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti Speciálně je tedy interpretace následující: vektor e je chybový vektor přidružený k obdrženému vektoru, jestliže je schopen reprezentovat jistou možnou posloupnost chyb při přenosu. Následující triviální pozorování je klíčové. Lemma 5.7 Je-li y obdržený vektor, je množina možných chybových vektorů ten koset množiny C, který obsahuje vektory. Důkaz. Bylo-li obdrženo slovo y, je vektor e chybový vektor právě tehdy, když existuje kódové slovo c e C tak, že y - c = e. Ale C je podprostor; tedy i -c e C, tj. e = y + c' a e e y + C. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti - dekódování Co to je dekódování podle pravidla minimální vzdálenosti? To není nic jiného, než nalezení chybového vektoru s minimální vahou. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti - dekódování Co to je dekódování podle pravidla minimální vzdálenosti? To není nic jiného, než nalezení chybového vektoru s minimální vahou. Známe-li tedy pro každý koset jeho prvek minimální váhy, pak máme základ pro dekódování podle pravidla minimální vzdálenosti. Řekneme pak, že vektor e je reprezentant kosetu H, jestliže má nejmenší váhu ze všech vektorů obsažených v H = e + C. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Pravidlo minimální vzdálenosti - dekódování Co to je dekódování podle pravidla minimální vzdálenosti? To není nic jiného, než nalezení chybového vektoru s minimální vahou. Známe-li tedy pro každý koset jeho prvek minimální váhy, pak máme základ pro dekódování podle pravidla minimální vzdálenosti. Řekneme pak, že vektor e je reprezentant kosetu H, jestliže má nejmenší váhu ze všech vektorů obsažených v H = e + C. Zdůrazněme, že takovýto reprezentant nemusí být vybrán jednoznačně. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming A!goritmus I - dekódování Krok 1: Po přijetí vektoru y najdeme reprezentanta z0 kosetu y - C. Krok 2: Vektor y pak dekódujeme jakožto kódové slovo y-zo- Evidentně, Krok 1 může být velmi časově náročný. Urychlíme jej použitím následující vlastností lineárních kódů. Lemma 5.8 Dva vektory y-, a y2 leží v temže kosetu právě tehdy, když HyJ = Hyl Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy A!goritmus I - dekódování Další kódy Problémy Generující matice Použití Vzdálenost Hamming Dva vektory y-, a y2 leží v temže kosetu právě tehdy, když existuje kódové slovo c e C tak, že Yi = y2 + c Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy A!goritmus I - dekódování Další kódy Problémy Generující matice Použití Vzdálenost Hamming Dva vektory y-, a y2 leží v temže kosetu práve tehdy, když existuje kódové slovo c e C tak, že Yi = y2 + c tj- HcT = H(Y1 - y2)T = 0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy A!goritmus I - dekódování Další kódy Problémy Generující matice Použití Vzdálenost Hamming Dva vektory y-, a y2 leží v temže kosetu práve tehdy, když existuje kódové slovo c e C tak, že yi = y2 + c tj- HcT = H(Y1 - y2)T = 0 tj- HyJ = HyJ. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy A!goritmus I - dekódování Další kódy Problémy Generující matice Použití Vzdálenost Hamming Dva vektory y-, a y2 leží v temže kosetu právě tehdy, když existuje kódové slovo c e C tak, že Yi = y2 + c tj- HcT = H(Y1 - y2)T = 0 tj- HyJ = HyJ. I__ Definujme syndrom kosetu H = a + C jakožto vektor HaT délky k. Evidentně, je tato definice korektní. Máme tedy pro každý koset H jeho syndrom a jeho reprezenjant^ kosetu, t ^ Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Generující matice Vzdálenost Použití Hamming poloeficientní - dekódování Máme-li tedy předem vypočtenou tabulku, ve které je pro každý syndrom určen příslušný reprezentant, můžeme urychlit výše uvedný algoritmus následovně: Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Generující matice Vzdálenost Použití Hamming poloeficientní - dekódování Máme-li tedy předem vypočtenou tabulku, ve které je pro každý syndrom určen příslušný reprezentant, můžeme urychlit výše uvedný algoritmus následovně: Krok 1a: Po přijetí vektoru y najdeme syndrom HyT. Krok 1b: Z výše uvedené tabulky najdeme odpovídajícího reprezentanta z0 kosetu y - C. Krok 2: Vektor y pak dekódujeme jakožto kódové slovo y-zo- Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Algoritmus II - poloeficientní - dekódování Věta 5.9 Algoritmus II pracuje jakožto dekódovací pravidlo podle minimální vzdálenosti pro lineární kódC. Důkaz. Poznamenejme nejprve, že každé obdržené slovo y můžeme dekódovat jakožto kódové slovo. To je z toho důvodu, že y a z0 jsou ve stejném kosetu a tedy y - z0 e C. 0 0,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Algoritmus II - poloeficientní - dekódování Věta 5.9 Algoritmus II pracuje jakožto dekódovací pravidlo podle minimální vzdálenosti pro lineární kódC. Důkaz. Poznamenejme nejprve, že každé obdržené slovo y můžeme dekódovat jakožto kódové slovo. To je z toho důvodu, že y a z0 jsou ve stejném kosetu a tedy y - z0 e C. Předpokládejme, že existuje kódové slovo c tak, že d(y,y-z0) >d(y,c). 0 0,0 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Algoritmus II - poloeficientní - dekódování Věta 5.9 Algoritmus II pracuje jakožto dekódovací pravidlo podle minimální vzdálenosti pro lineární kódC. Poznamenejme nejprve, že každé obdržené slovo y můžeme dekódovat jakožto kódové slovo. To je z toho důvodu, že y a z0 jsou ve stejném kosetu a tedy y - z0 e C. Předpokládejme, že existuje kódové slovo c tak, že d(y,y-z0) >d(y,c). To je ekvivalentní s tím, že d(0,z0)>d(y-c,0). Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Generující matice Vzdálenost Použití Hamming poloeficientní - dekódování Pokračování důkazu Věty 5.9 . d(0,Zo) >d(y-c,0) právě tehdy, když w(z0) > w(y - c). Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Generující matice Vzdálenost Použití Hamming poloeficientní - dekódování Pokračování důkazu Věty 5.9 . d(0,z0)>d(y-c,0) právě tehdy, když w(z0) > w(y - c). Ale pak H(y - c)T = HyT - HcT = HyT, protože c je kódové slovo. Zejména tedy má y - c stejný syndrom jako y, leží ve stejném kosetu a a má váhu ostře menší než je váha reprezentanta kosetu z0, což je spor. I Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Generující matice Vzdálenost Použití Hamming poloeficientní - dekódování V dalším budeme předpokládat, že kódování a dekódování pro lineární [n, /c]-kód C = {c-i,..., c^}, Ci = 0 při přenosu binárním symetrickým kanálem s pravděpodobností chyby p bude probíhat pomocí následující tabulky 0 c2 c3 • • • C/W f2 f 2 + C2 f2 + C3 • • • f3 Í3 + C2 • • • ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ fs *s + C2 fs + c3 • • • 1s + CM Dále předpokládejme, že každý reprezentant f, příslušného kosetu má váhu wř(f,-). Platí pak následující tvrzení. Označme, pro 1 3. Že je to právě 3, plyne okamžitě z Věty 5.6, protože najdeme 3 sloupce matice H, které jsou lineárně závislé (binární reprezentanty čísel 1, 2 a 3). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Důkaz Věty 5.12 - pokračování Protože pracujeme s binárními kódy, je nutně h, = hy, což není možné. Je tedy d(C) > 3. Že je to právě 3, plyne okamžitě z Věty 5.6, protože najdeme 3 sloupce matice H, které jsou lineárně závislé (binární reprezentanty čísel 1, 2 a 3). Ukažme, že C je perfektní. Poznamenejme, že každá 1-koule kolem kódového slova bude obsahovat právě 1 + n = 2r vektorů délky n = 2r - 1. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Důkaz Věty 5.12 - pokračování Protože pracujeme s binárními kódy, je nutně h, = hy, což není možné. Je tedy d(C) > 3. Že je to právě 3, plyne okamžitě z Věty 5.6, protože najdeme 3 sloupce matice H, které jsou lineárně závislé (binární reprezentanty čísel 1, 2 a 3). Ukažme, že C je perfektní. Poznamenejme, že každá 1-koule kolem kódového slova bude obsahovat právě 1 + n = 2r vektorů délky n = 2r - 1. Protože C obsahuje právě 2k = 2n~r kódových slov, disjunktní sjednocení těchto 1-koulí je právě celá množina Vn vektorů délky n, jichž je právě 2n = 2n~r • 2r. m Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Binární Hammingovy kódy Důležitým důsledkem perfektnosti Hammingových kódů je, že O Pro Hammingův [n, /c]-kód jsou reprezentanti kosetů vektory z Vn váhy < 1. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Binární Hammingovy kódy Důležitým důsledkem perfektnosti Hammingových kódů je, že O Pro Hammingův [n, /c]-kód jsou reprezentanti kosetů vektory z Vn váhy < 1. To vede k následujícímu elegantnímu dekódovacímu algoritmu pro Hammingovy kódu. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Binární Hammingovy kódy Důležitým důsledkem perfektnosti Hammingových kódů je, že Pro Hammingův [n, /c]-kód jsou reprezentanti kosetů vektory z Vn váhy < 1. To vede k následujícímu elegantnímu dekódovacímu algoritmu pro Hammingovy kódu. Nejprve poznamenejme: Sloupce matice H lze přemístit tak, že y-tý sloupec matice H je právě binární reprezentace čísla y. Je-li obdržen vektor y, spočtěme jeho syndrom Hy-1 a předpokládejme, že reprezentuje číslo y. Předpokládáme-li pouze jednu chybu, pravidlo minimální vzdálenosti (=pravidlo maximální pravděpodobnosti) nám dává: O Pokud j = Hy^ = 0, pak nepředpokládáme žádnou chybu a y je kódové slovo. © Pokud j = Hy^ ^ 0, pak předpokládáme chybu v y-té pozici a dekódujeme y jeho změnou v y-té pozici. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Binární Hammingovy kódy Příklad 5.13 Hammingův [7, 4]-kód má matici kontroly parity H = 0 0 0 1 1 1 1 0 110 0 11 10 10 10 1 Předpokládejme, že jsme obdrželi vektor y = (1,0,1,0,1,1,0). Pak HyT = (001). Tedy za předpokladu, že nenastala více nezjedná chyba, předpokládáme, že se chyba vyskytla na prvním místě a dekódujeme pak y jakožto y*, y* = (0,0,1,0,1,1,0). Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Generující matice Použití Vzdálenost Hamming Binární Hammingovy kódy Cvičení 5.14 Napište matici kontroly parity binárního [15,11,3] -kódu. Jak bychom dekódovali obdržené vektory: O (100000000000000), O (111111111111111)? Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy ES sal i Q Cyklické kódy • Cyklické kódy S1 Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Fl Diskutujme nyní důležitou skupinu lineárních kódů. Kód C se nazývá cyklický, jestliže platí následující podmínky: O C je lineární, O pokud vektor w=(^,...,^)gC, pak i vektor Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Fl Diskutujme nyní důležitou skupinu lineárních kódů. Kód C se nazývá cyklický, jestliže platí následující podmínky: O C je lineární, O pokud vektor w=(^,...,^)gC, pak i vektor w' = (wn,wi,...,wn-i) eC. Tyto kódy mají atraktivní algebraické vlastnosti a můžeme je snadno sestrojit pomocí lineárních posouvacích registrů. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Fl Diskutujme nyní důležitou skupinu lineárních kódů. Kód C se nazývá cyklický, jestliže platí následující podmínky: O C je lineární, O pokud vektor w=(^,...,^)gC, pak i vektor w' = (wn,wi,...,wn-i) eC. Tyto kódy mají atraktivní algebraické vlastnosti a můžeme je snadno sestrojit pomocí lineárních posouvacích registrů. Budeme dále pracovat pouze v binárním případě a během tohoto paragrafu budeme identifikovat vektor w = (^ir..,^) s polynomem w(x) = i/i/i+ w2x + w3x2 h-----h wnx n-1 Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Dále budeme počítat pouze v okruhu Rn binárních polynomů stupně nejvýše n - 1 modulo polynom xn - 1. Tedy Rn se skládá z polynomů stupně < n - 1 s koeficienty 0 a 1 tak, že platí následující pravidla pro sčítání a násobení polynomů: a(x) + b(x) = Eľ=o1 (a/+ a(x) • b(x) = a(x)b(x) mod (x11 - 1). Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Dále budeme počítat pouze v okruhu Rn binárních polynomů stupně nejvýše n - 1 modulo polynom xn - 1. Tedy Rn se skládá z polynomů stupně < n - 1 s koeficienty 0 a 1 tak, že platí následující pravidla pro sčítání a násobení polynomů: a(x) + b(x) = Etoiai + biW a(x) • b(x) = a(x)b(x) mod (x11 - 1). Základním pozorováním je následující skutečnost: posunu v kódovém slově odpovídá násobení odpovídajícího polynomu monomem x v okruhu Rn. Dále budeme počítat pouze v okruhu Rn binárních polynomů stupně nejvýše n - 1 modulo polynom xn - 1. Tedy Rn se skládá z polynomů stupně < n - 1 s koeficienty 0 a 1 tak, že platí následující pravidla pro sčítání a násobení polynomů: Základním pozorováním je následující skutečnost: posunu v kódovém slově odpovídá násobení odpovídajícího polynomu monomem x v okruhu Rn. Totiž w(x) • x = w^x + w2x2 + w3x3 H-----h \Nn_^xn~A + wnxn mod (x11 - 1) = w^x + w2x2 + w3x3 H-----h \Nn_^xn~A + wnx° = wn + w^x + w2x2 + W3X3 H-----h \Nn_\Xn~A. a{x) + b{x) a(x) • b(x) Ei=o (a/ + W a(x)£>(x) mod (xn - 1). □ - = Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Platí pak následující lemma Lemma 6.1 Je-li w(x) polynomiální reprezentace kódového slova wgC, je i w(x)f(x) kódové slovo pro každý polynom f stupně nejvýše n-J\. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Platí pak následující lemma Lemma 6.1 Je-li w(x) polynomiální reprezentace kódového slova wgC, je i w(x)f(x) kódové slovo pro každý polynom f stupně nejvýše n-J\. Důkaz. Protože w(x) e C, je i xw(x) e C (posunutí o 1 místo doprava). Nutně tedy pro každé přirozené číslo k platí, že xkw(x) e C. Ale protože je C lineární kód, je i libovolná lineární kombinace kódových slov tvaru xkw(x) opět v C, zejména tedy je polynom f(x)w{x)vC. I Kódování a odhady Ekvivalence kódů Hlavní problém TK Cyklické kódy Lemma 6.2 Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Je-li g(x) nenulový polynom minimálního stupně vC, pak g{x) generuje kód C v tom smyslu, že každé kódové slovo w(x) e C je tvaru w^ = f(x)g(x) pro vhodný polynom f(x). Kódování a odhady Ekvivalence kódů Hlavní problém TK Cyklické kódy Lemma 6.2 Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Je-li g(x) nenulový polynom minimálního stupně vC, pak g{x) generuje kód C v tom smyslu, že každé kódové slovo w(x) e C je tvaru w^ = f(x)g(x) pro vhodný polynom f(x). Důkaz. Předpokládejme, že existuje w(x) e C, které nelze napsat ve výše uvedeném tvaru. Pak lze psát w(x) = q(x)g(x) + r(x), kde r(x) je zbytek po dělení polynomem g(x) tj. jeho stupeň je menší než stupeň polynomu g(x). Kódování a odhady Ekvivalence kódů Hlavní problém TK Cyklické kódy Lemma 6.2 Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Je-li g{x) nenulový polynom minimálního stupně vC, pak g{x) generuje kód C v tom smyslu, že každé kódové slovo w(x) e C je tvaru w^ = f(x)g(x) pro vhodný polynom f(x). Důkaz. Předpokládejme, že existuje w(x) e C, které nelze napsat ve výše uvedeném tvaru. Pak lze psát w(x) = q(x)g(x) + r(x), kde r(x) je zbytek po dělení polynomem g(x) tj. jeho stupeň je menší než stupeň polynomu g(x). Ale q(x)g(x), w(x) e C, tj. r (x) g C tj. nutně je r (x) nulový polynom, spor. Tedy je každý polynom z C násobkem g (x). I Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Mluvíme pak o polynomu g(x) jakožto o generujícím polynomu kódu C. Tím pak dostaneme velmi dobrou reprezentaci kódu C. Připomeňme dále, že cyklický kód není nic jiného než ideál v okruhu polynomu a 6.2 plyne bezprostředně z toho, že každý ideál v okruhu polynomů je hlavní ideál. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Mluvíme pak o polynomu g(x) jakožto o generujícím polynomu kódu C. Tím pak dostaneme velmi dobrou reprezentaci kódu C. Připomeňme dále, že cyklický kód není nic jiného než ideál v okruhu polynomu a 6.2 plyne bezprostředně z toho, že každý ideál v okruhu polynomů je hlavní ideál. Příklad 6.3 Předpokládejme, že n = 3 a násobení je prováděno modulo polynom x3 - 1. Pak kód C = {0,1 +x,x + x2,1 +x2} je cyklický a generován polynomem 1 + x. Standardní reprezentace kódu C sestává z vektorů {(0,0,0), (1,1,0), (0,1,1), (1,0,1)}. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Lemma 6.4 Je-li C cyklický kód délky n s generujícím polynomem g[x) = g-i + g2x h-----h gk*k~A, pak jeho generující matice typu (n - k + 1) x n má tvar G = 01 92 93 0 9^ 92 0 0 9^ 9k 0 0 flh-1 9k 0 9k-2 9k-\ 9k 0 0 o 0 0 9k-2 flfc-l 9k Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Důkaz Lemmatu 6.4 Evidentně, řádky matice Gjsou lineárně nezávislé. Ukažme, že každé kódové slovo lze reprezentovat pomocí těchto řádků. Je-li tedy c = (c0, c-i,..., cn_i) kódové slovo, je odpovídající polynom n-1 tvaru C(x) = C0 + CiXH-----h cn^x c(x) = g{x)f(x) (mod(xn - 1)) pro jistý polynom f stupně nejvýše < n - 1. Ale to neznamená nic jiného, než že n-1 C(x) = ^g{x) (mod(xn - 1)). Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Důkaz Lemmatu 6.4 Položíme-li g('\x) = x'g(x) a je-li g(/) odpovídající reprezentace polynomu g('\x) (i + 1 -ní řádek matice G), máme /=o Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Lemma 6.5 Je-li g generující polynom cyklického kódu C délky n, pak g dělí polynom (xn - 1). Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Lemma 6.5 Je-li g generující polynom cyklického kódu C délky n, pak g dělí polynom (xn - 1). Důkaz. Předpokládejme, že tomu tak není. Můžeme pak psát xn - 1 = g(x)q(x) + r(x), kde r(x) je nenulový polynom se stupněm menším než je stupeň g. Protože q(x)g(x) e C a r = -qg v tomto okruhu, plyne z linearity, že i r je kódové slovo, tj. se nemůže jednat o polynom minimálního stupně a tedy r = 0, spor. I Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Lemma 6.6 Je-li dán polynom p stupně < n, pak množina všech polynomů C = {gp(mod(xn - 1)) : q je polynom stupně < n} je cyklický kód délky n. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Cyklické kódy Lemma 6.6 Je-li dán polynom p stupne < n, pak množina všech polynomů C = {gp(mod(xn - 1)) : q je polynom stupně < n} je cyklický kód délky n. Důkaz. Evidentně, C je lineární kód. Zároveň, je-li qp e C, je i xqp e C tj. C je cyklický kód. I Hranice Aq(n, d) Lineárni kódy Cyklické kódy Další kódy Problémy Lemma 6.7 Je-li g generující polynom stupně k cyklického kódu délky n C, pak polynom p stupně menšího než n je kódové slovo tehdy a jen tehdy když p(x)h(x) = 0 (mod(xn- 1)), kde h je polynom stupně n-k splňujícíg{x)h{x) = (xn - 1) z Lemmatu 6.5. Polynom h pak nazýváme kontrolní polynom kódu C. Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Důkaz Lemmatu 6.7 Je-li c(x) kódové slovo, pak dle Lemmatu 6.2 platí c(x) = f(x)g(x) pro vhodný polynom f(x). Tudíž c(x)/?(x) = f{x)g(x)h(x) = f(x)(xn - 1)) = 0 (mod(xn - 1)). Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Důkaz Lemmatu 6.7 Je-li c(x) kódové slovo, pak dle Lemmatu 6.2 platí c(x) = f(x)g(x) pro vhodný polynom f(x). Tudíž c(x)/?(x) = f{x)g(x)h(x) = f(x)(xn - 1)) = 0 (mod(xn - 1)). Obráceně, předpokládejme, že p je nenulový polynom splňující p(x)h(x) = 0 (mod(xn - 1)). Pak p musí být stupně alespoň k. Nechť p(x) = flf(x)g(x) + r(x), kde r(x) je polynom se stupněm menším než je stupeň g. Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Důkaz Lemmatu 6.7 Je-li c(x) kódové slovo, pak dle Lemmatu 6.2 platí c(x) = f(x)g(x) pro vhodný polynom f(x). Tudíž c{x)h{x) = f{x)g{x)h{x) = f{x){xn - 1)) = 0 (mod(xn - 1)). Obráceně, předpokládejme, že p je nenulový polynom splňující p(x)h(x) = 0 (mod(xn - 1)). Pak p musí být stupně alespoň k. Nechť p(x) = flf(x)g(x) + r(x), kde r(x) je polynom se stupněm menším než je stupeň g. Protože p(x)h(x) = 0 (mod(xn - 1)) a tedy g(x)q(x)h(x) = 0 (mod(xn - 1)), musí být i r(x)/7(x) = 0 (mod(xn- 1)). Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Důkaz Lemmatu 6.7 Je-li c(x) kódové slovo, pak dle Lemmatu 6.2 platí c(x) = f(x)g(x) pro vhodný polynom f(x). Tudíž c{x)h{x) = f{x)g{x)h{x) = f{x){xn - 1)) = 0 (mod(xn - 1)). Obráceně, předpokládejme, že p je nenulový polynom splňující p(x)h(x) = 0 (mod(xn - 1)). Pak p musí být stupně alespoň k. Nechť p(x) = flf(x)g(x) + r(x), kde r(x) je polynom se stupněm menším než je stupeň g. Protože p(x)h(x) = 0 (mod(xn - 1)) a tedy g(x)q(x)h(x) = 0 (mod(xn - 1)), musí být i r(x)h(x) = 0 (mod(xn - 1)). Ale stupeň r(x)h(x) je menší než n. Tedy r(x)h(x) = 0 tj. i r(x) = 0. Je tedy i p(x) = g(x)q(x) e Cm Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Cvičení 6.8 O Ukažte, že existují právě čtyři binární kódy délky 3 a najděte jejich generující polynom. Hranice Aq(n, d) Lineárni kódy Cyklické kódy Další kódy Problémy Cvičení 6.8 O Ukažte, že existují právě čtyři binární kódy délky 3 a najděte jejich generující polynom. O Dokažte, že Hammingovo kódování s parametry n = 7, k = 4ad = 3je cyklický kód s kontrolním polynomem x4 + x2 + x + 1. Jak vypadá jeho generující polynom? Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Obsa damardovy kódy Reed-Muller r r Q Marinerův kód a Reed-Mullerovy kódy * Hadamardovy kódy • Reed-Mullerovo kódování Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Hadamardovy kódy Reed-Muller Fl V tomto odstavci se budeme věnovat dalším dvěma příkladům, kdy pomocí klasické moderní algebry byly zkonstruovány a vyvinuty nové třídy kódů. Kódování fí(1,5) použité v roce 1969 kosmickým korábem Mariner 9 pro přenos fotografií z Marsu je speciálním případem následujících obecných kódů. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Další kódy Problémy Hadamardovy kódy Reed-Muller Fl V tomto odstavci se budeme věnovat dalším dvěma příkladům, kdy pomocí klasické moderní algebry byly zkonstruovány a vyvinuty nové třídy kódů. Kódování fí(1,5) použité v roce 1969 kosmickým korábem Mariner 9 pro přenos fotografií z Marsu je speciálním případem následujících obecných kódů. Nejprve si připomeňme některé pojmy z moderní algebry. Hadamardova matice je matice H typu n x n, jejíž koeficienty jsou buď +1 nebo -1 tak, že HHT = nEn, (7.1) kde En je jednotková matice typu n x n. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Hadamardovy kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Jsou-li dále A a B čtvercové matice typu m x m a n x n, definujeme jejich Kroneckerův součin jako matici A® B typu mn x mn A® B = dí\\B a\2.B &m\ B am2 B 3 mm B (7.2) Přímým výpočtem pak snadno dokážeme: Lemma 7.1 Jsou-li H-i a H2 Hadamardovy matice, je jejich Kroneckerův součin H-i ® H2 Hadamardova matice. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hadamardovy kódy Reed-Muller Hlavní problém TK Cyklické kódy Hadamardovy kódy - Důkaz Lemmatu 7.1 MA Počítejme G = (H, H2)(Hi ® H2)T. Pak gih i = 1 + n ■ (/ - 1), j = j + n ■ (y - 1). Zejména g,} = E™ 1 3?,a-,(ELi l>ikbjk). Pokud / = j, je nutně / = y a / = j a tedy i 9a = E£i %%(ELi ^A)- Ale ELi k/A = " a tedv 5// = E™ 1 3?/%" =™. Nechť tedy / ^ y. Pak buď / ^ y nebo / ^ y. Nechť například / ^ y. Pak 9íj = (E" 15/^,)(ELi bikb]k) = 0(ELi ^V) = °-Nechť tedy / ^ y. Podobně, m n m 9a = (E a//a//)(E = (Ľ ^z3//)0 = °- /=1 /c=1 /=1 Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Hadamardovy kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Fl Začneme-li tedy s nejmenší netriviální Hadamardovou maticí 1 1 1 -1 můžeme postupně iterovat Kroneckerovým součinem, abychom obdrželi posloupnost Hadamardových matic s exponenciálně rostoucím typem. Chceme-li pak tuto posloupnost použít pro účely kódování, předpokládejme, že H je Hadamardova matice rozměru n x n, přičemž n je sudé. Definujme pak A jakožto matici typu 2n x n Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Hadamardovy kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Pak definujme M jakožto matici, kterou získáme z matice A tak, že nahradíme každý výskyt -1 v A číslem 0. Snadno se ověří následující tvrzení Lemma 7.2 Hadamardovo kódování O Jsou-li x a y dva různé řádky matice M, je pak vzdálenost oř(x, y) vektorů x a y rovna číslu % nebo n. O Řádky matice M tvoří binární {n, 2n, %)-kód. Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Hadamardovy kódy Reed-Muller Hadamardovy kódy - Důkaz Lemmatu 7.2 Vezmeme-li 2 různé řádky vzniklé z H, nutně je počet míst, kde se řádky liší, roven počtu míst, kde jsou oba řádky stejné, tj. d(x,y) = íj. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hadamardovy kódy Reed-Muller Hlavní problém TK Cyklické kódy Hadamardovy kódy - Důkaz Lemmatu 7.2 Vezmeme-li 2 různé řádky vzniklé z H, nutně je počet míst, kde se řádky liší, roven počtu míst, kde jsou oba řádky stejné, tj. d(x,y) = íj. Podobně, vezmeme-li 2 různé řádky, z nichž jeden vznikl z H a druhý z —H a zároveň oba z různých vektorů z H, je nutně opět počet míst, kde se řádky liší, roven počtu míst, kde jsou oba řádky stejné, tj. opět d(x,y) = 5. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hadamardovy kódy Reed-Muller Hlavní problém TK Cyklické kódy Hadamardovy kódy - Důkaz Lemmatu 7.2 Vezmeme-li 2 různé řádky vzniklé z H, nutně je počet míst, kde se řádky liší, roven počtu míst, kde jsou oba řádky stejné, tj. d(x,y) = íj. Podobně, vezmeme-li 2 různé řádky, z nichž jeden vznikl z H a druhý z —H a zároveň oba z různých vektorů z H, je nutně opět počet míst, kde se řádky liší, roven počtu míst, kde jsou oba řádky stejné, tj. opět d(x,y) = 5. Případ, kdy oba řádky vznikly ze stejného vektoru, nám dává vzdálenost rovnu n. Poslední případ, kdy oba řádky vznikly z -H, se převede na první případ. Zbývající část tvrzení je triviální. ■ Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Hadamardovy kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Provedeme-li výše uvedené pětkrát za sebou na matici H2, obdržíme n = 32 a to je přesně kódování použité Marinerem. Kódy získané výše uvedeným postupem se nazývají Hadamardovy kódy. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Reed-Mullerovo kódování Fl Tato prakticky důležitá třída kódů byla objevena LS. Reedern a D.E. Mullerem v roce 1954. Abychom mohli popsat tyto kódy, budeme nejprve prezentovat jednoduchý způsob zkonstruování nových kódování ze starých původních. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Reed-Mullerovo kódování Lemma 7.3 Jsou-li dány (n, , oři) binární kódování^ a jiné (n, M2, d2) binární kódováníC2j můžeme pak definovat třetí binární kódováníC3 = C-i *C2 jakožto C3 = {(u, U + v):UGCi,VG C2}. Přitom C3 je (2/7, MA M2, d3)-kód, kde d3 = min{2d^d2}. (7.3) Jsou-li navíc C\ a C2 lineární kódy je iC3 lineární kód. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hadamardovy kódy Reed-Muller Hlavní problém TK Cyklické kódy Reed-Mullerovo kódování - Důkaz Lemmatu 7.3 Délka kódových slov v C3 je nutně 2n a snadno se ověří, že jich je právě M1M2. To plyne z toho, že pokud (u-i, u-i + v-i) = (u2, u2 + v2) je nutně = u2 a tedy i v1 = v2. Takovýchto uspořádaných dvojic (u, v) je právě M1M2. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hadamardovy kódy Reed-Muller Hlavní problém TK Cyklické kódy Reed-Mullerovo kódování - Důkaz Lemmatu 7.3 Délka kódových slov v C3 je nutně 2n a snadno se ověří, že jich je právě M1M2. To plyne z toho, že pokud (u-i, u-i + v-i) = (u2, u2 + v2) je nutně Ui = u2 a tedy i v1 = v2. Takovýchto uspořádaných dvojic (u, v) je právě M1M2. Zbývá ověřit, že minimální délka kódování C3, kterou značíme d3, je rovna min{2d1, d2}. To je ale zřejmé. Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Hadamardovy kódy Reed-Muller Reed-Mullerovo kód ování - Důkaz Lemmatu 7.3 Délka kódových slov v C3 je nutně 2n a snadno se ověří, že jich je právě M1M2. To plyne z toho, že pokud (u-i, u-i + v-i) = (u2, u2 + v2) je nutně Ui = u2 a tedy i v1 = v2. Takovýchto uspořádaných dvojic (u, v) je právě M1M2. Zbývá ověřit, že minimální délka kódování C3, kterou značíme č/3, je rovna min{2d1, d2}. To je ale zřejmé. Totiž, je-li (u-i, + v-i) ^ (u2, u2 + v2), pak mohou nastat následující případy O = u2: pak d(v1, v2) = d((ui, + v1), (u2j u2 + v2)) > d2. Kódování a odhady Hranice Aq(r?, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Hadamardovy kódy Reed-Muller Reed-Mullerovo kód ování - Důkaz Lemmatu 7.3 Délka kódových slov v C3 je nutně 2n a snadno se ověří, že jich je právě M1M2. To plyne z toho, že pokud (u-i, u-i + v-i) = (u2, u2 + v2) je nutně Ui = u2 a tedy i v1 = v2. Takovýchto uspořádaných dvojic (u, v) je právě M1M2. Zbývá ověřit, že minimální délka kódování C3, kterou značíme č/3, je rovna min{2d1, d2}. To je ale zřejmé. Totiž, je-li (u-i, + v-i) ^ (u2, u2 + v2), pak mohou nastat následující případy O = u2: pak d(v1, v2) = d((ui, + v1), (u2j u2 + v2)) > d2. @ v1 = v2: pak d(ui, u2) + d(ui, u2) = d((ui, + v1), (u2, u2 + v2)) > 2gT1 . Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hadamardovy kódy Reed-Muller Hlavní problém TK Cyklické kódy Reed-Mullerovo kódování - Důkaz Lemmatu 7.3 O Ui ^ u2 a Ví ^ v2: pak označíme-li ln = {/' : TTj(U-\) ^ TTj(U2)}, le = V ■ 7T/(Wl) = 7T/(í^)}, Jn = {/ : 7T/(^ ) ^ 7T/(V2)}, Je = {/' : 717(1^ ) = 7T/( V2)}> je d((Ui,Ui +V1),(U2,U2 + V2)) = \ln\ + \Jer)ln\ + |Jn H /e| |J„| +2|Jen /n| > d2. Přitom v prvním a druhém případě může pro vhodně vybrané dvojice nastat rovnost, tj. tvrzení platí. Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hadamardovy kódy Reed-Muller Hlavní problém TK Cyklické kódy Reed-Mullerovo kódování - Důkaz Lemmatu 7.3 O Ui ^ u2 a Ví ^ v2: pak označíme-li ln = {/' : TTj(U-\) ^ 7Ti(U2)}, le = V ■ 7T/(Wl) = 7T/(í^)}, Jn = {/ : 7T/(^ ) ^ 7T/(V2)}, Je = {/' : 717(1^ ) = 7T/( V2)}> je d((Ui,Ui +V1),(U2,U2 + V2)) = \ln\ + \Jer)ln\ + |Jn H /e| = |J„| +2|Jen ln\ > d2. Přitom v prvním a druhém případě může pro vhodně vybrané dvojice nastat rovnost, tj. tvrzení platí. Buď C| a C2 lineární kódy. Evidentně, 02n = (0n,0„) e C3. Nechť , u2 e C1 av1,v2 eC2. Pak u-i + u2 e Ci, v-i + v2 e C2 a (Ui>Ui+V1) + (U2,U2+V2) = (U1+U2,(U1+U2) + (V1+V2)) GC3. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Reed-Mullerovo kódování Definujme nyní rekurzivně Reed-Mullerův kód C(r, m) předpisem: Pro všechna nezáporná celá čísla mar taková, že 0 < r < m, definujeme C(r, m) jakožto kód délky n = 2m takový, že C(0,a77) = {0,1}, (7.4) kde 0 = (0,0,..., 0) a 1 = (1,1,..., 1), C(m, m) je množina všech binárních vektorů délky n = 2m tj. C{m, m) = 22™ a C(r + 1, m + 1) = C(r + 1, m) * C(r, m) (7.5) pro r < m. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Reed-Mullerovo kódování Můžeme pak tyto kódy konstruovat následovně m=1 C(0,1) = {00,11} C(1,1) = {00,01,10,11} Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Reed-Mullerovo kódování Můžeme pak tyto kódy konstruovat následovně: m=1 c(0,1) = {00,11} C(1,1) = {00,01,10,11} m = 2 C(0,2) = {0000,1111} co,2) = C(1,1)*C(0,1) = {0000,0011,0101,0110, 1001,1010,1100,1111} C(2,2) = C(1,2) U {1000,0100,0010, 0001,1110,1101,1011,0111} atd. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Reed-Mullerovo kódování Aplikujeme-li nyní lemma 7.3, obdržíme následující větu: Věta 7.4 Pro všechna nezáporná celá čísla m ar taková, že0 < r < m je Reed-MullerůvC(r, m) lineární binární kód charakteristiky (nn Mn dr), kde • H = 2«.**a = £JU(7)=1 + (7)+-+(7). O nr = 2m, O dr = 2m~r. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Důkaz věty 7.4 Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Důkaz povedeme indukcí vzhledem k definici C(r, m). Totiž pro C(0, m) = {0,1} je počet slov M0 roven dvěma a protože zároveň nutně a = 1, první část tvrzení pro C(0, m) platí. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Důkaz věty 7.4 Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Důkaz povedeme indukcí vzhledem k definici C(r, m). Totiž pro C(0, m) = {0,1} je počet slov M0 roven dvěma a protože zároveň nutně a = 1, první část tvrzení pro C(0, m) platí. Protože délka nr vektorů je dle definice 2m, platí druhá část tvrzení. Protože kód obsahuje pouze dva vektory, které se liší na nr = 2m místech, je vzdálenost kódu rovna nr = 2m~° = dr. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Důkaz věty 7.4 Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Důkaz povedeme indukcí vzhledem k definici C(r, m). Totiž pro C(0, m) = {0,1} je počet slov M0 roven dvěma a protože zároveň nutně a = 1, první část tvrzení pro C(0, m) platí. Protože délka nr vektorů je dle definice 2m, platí druhá část tvrzení. Protože kód obsahuje pouze dva vektory, které se liší na nr = 2m místech, je vzdálenost kódu rovna nr = 2m~° = dr. Uvažme nyní kód C(m, m), což je množina všech binárních vektorů délky n = 2m = nm. Je tedy v našem případě a = n a tedy i = 2a.Vzdálenost kódu je pak nutně 1 = 2m~m. Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Důkaz věty 7.4 - pokračování Věnujme se nyní případu C(r + 1, m + 1) = C(r + 1, m) * C(r, m). Z indukčního předpokladu a lemmatu 7.3 víme, že C(r + 1, m) a C(r, rn) jsou lineární, tedy i C(r + 1, m + 1) je lineární, a Kódování a odhady Ekvivalence kódů Hlavní problém TK Hranice Aq(n, d) Lineární kódy Cyklické kódy Ha Další kódy Problémy Hadamardovy kódy Reed-Muller Důkaz věty 7.4 - pokračování Věnujme se nyní případu C(r + 1, m + 1) = C(r + 1, m) * C(r, m). Z indukčního předpokladu a lemmatu 7.3 víme, že C(r + 1, m) a C(r, rn) jsou lineární, tedy i C(r + 1, m + 1) je lineární, a Dále víme, že = 2 • 2m = 2A7?+1 a = min{2 • 2A7?-r-1, 2m~r} = 2^-^ = 2A7?+1-(r+1). Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hadamardovy kódy Reed-Muller Hlavní problém TK Cyklické kódy Reed-Mullerovo kódování s délkou 8 Generující matice: C(0,3) : [1 1 1 1 1 1 1 1 C(2,3) 1 1 0 0 0 0 0 0' 10 10 0 0 0 0 10 0 0 10 0 0 11110 0 0 0 110 0 110 0 10 10 10 10 11111111 co,3) C(3,3) "1 1 1 1 0 0 0 0" 110 0 110 0 10 10 10 10 11111111 1 0 0 0 0 0 0 0" 110 0 0 0 0 0 10 10 0 0 0 0 10 0 0 10 0 0 11110 0 0 0 110 0 110 0 10 10 10 10 11111111 Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Obsa i r i Q Problémy Kódování a odhady Hranice Aq(n, d) Další kódy Ekvivalence kódů Lineární kódy Problémy Hlavní problém TK Cyklické kódy Problémy k řešení O Ukažte, že pokud platí 6-2 0 a? — 1 / <2n, pak existuje binární lineární [n, k] -kód s minimální vzdáleností alespoň d. Tudíž odvoďte, že O 2k