AdamátorZápiskyHlášky

Teorie kódování

PřednášejícíMgr. Jan Volec, Ph.D.
WebWebová stránka předmětu
Semestrléto 2024

Tři série domácích cvičení, vyřešit alespoň jednu v každé sérii. Může se na nich spolupracovat, ale sepsat je máme sami.

Zkouškový test na poslední přednášce

Motivace: Máme konečnou abecedu A (většinou {0,1}) a nad ní chceme postavit kódová slova délky n, tedy w∈An. Kód je nějaká množina možných slov C⊂An.

Kódování pomocí paritního bitu: C={a1⋯an−1s|ai∈{0,1},s=(∑i=1n−1ai)mod2} – lze rozpoznat jednu chybu

Definice Nechť A je konečná abeceda, n∈ℕ a u,w∈An. Potom vzdálenost slov u,w je
dist(u,w)≔#{i|ui≠wi}.
Poznámka Zjevně jde o metriku na množině An.
Definice Nechť A je konečná abeceda a M,n,d∈ℕ. Množina C⊂An,|C|=M je (M,n,d)-kód nad abecedou A, pokud
∀u,w∈C:u≠w⟹dist(u,w)≥d.
Příklad Nechť A={0,1}. Pokud d=2, máme kód, kde dokážeme poznat chybu v jednom bitu. Pokud d=3, máme kód, kde dokážeme opravit jednu chybu.

Ve zkouškovém testu bude za úkol pro dva dané z parametrů M,n,d určit optimální hodnotu třetího.

Komunikace: Odesílatel odešle nějaké slovo w∈C, nepřítel ho nějak změní, příjemce dostane slovo x∈An a má odhadnout původní slovo w. K tomu použije algoritmus dekódování:

x^≔arg minu∈Cdist(u,x).

(V případě, že je víc možností, budeme muset zvolit libovolně.)

Věta oprava chyb Nechť C je (M,n,d)-kód nad A a w∈C,x∈An jsou slova taková, že dist(x,w)≤t≔⌊d−12⌋. Potom x^=w.
Důkaz Triviální pomocí sporu a trojúhelníkové nerovnosti.
Věta Hammingova Nechť C je (M,n,d)-kód nad (0,1) a t≔⌊d−12⌋. Potom platí Hammingova nerovnost:
M∑i=0t(ni)≤2n.
Důkaz Nechť u,w∈C. Podle trojúhelníkové nerovnosti jsou koule Bt(u),Bt(w) disjunktní (kde koule značíme obráceně než Štampach a ještě navíc tím myslíme uzavřené koule, aby to bylo matoucí). Zjevně pro každé slovo je právě ∑i=0t(ni) způsobů, jak v něm změnit nanejvýš t znaků. To je tedy velikost koule kolem každého slova a z toho, že jsou disjunktní, plyne nerovnost.
Poznámka Obecně má-li abeceda q znaků, potom platí analogicky
M∑i=0t(ni)(q−1)i≤qn.
Definice Pokud v Hammingově nerovnosti platí rovnost, kód se nazývá perfektní.
Příklad Pro n=d liché je koktavý/opakovací kód {0n,1n} perfektní.

Lineární kódy

Definice Je-li T konečné těleso a kód C⊂Tn je lineární podprostor, kód se nazývá lineární.
Poznámka Kód nad ℤ2 je lineární, právě když obsahuje nulové slovo a je uzavřený na sčítání.
Poznámka Je-li kód C⊂Tn lineární, potom M=|T|dimC.
Definice Generující matice lineárního kódu je matice, jejíž řádky tvoří bázi kódu. Značíme G
Definice Kontrolní matice lineárního kódu je matice, jejíž řádky tvoří jádro jeho generující matice.
Příklad Paritní kód je lineární; jeho generující matice je například
G=(100⋯01010⋯01001⋯01⋮⋮⋮⋱⋮⋮000⋯11)
a jeho kontrolní matice je
H=(111⋯11).
Příklad Koktavý kód je lineární; jeho generující matice je
G=(111⋯11)
a jeho kontrolní matice je například
H=(100⋯01010⋯01001⋯01⋮⋮⋮⋱⋮⋮000⋯11).
Tedy paritní a koktavý kód jsou k sobě duální.
Věta Jsou-li G,H generující a kontrolní matice lineárního kódu, potom H⋅G𝖳=0.
Důkaz Víceméně plyne z definice kontrolní matice.
Věta Je-li C lineární kód, H jeho kontrolní matice a w∈Tn, potom w∈C⇔H⋅w=0.
Důkaz Víceméně plyne z definice kontrolní matice.
Definice Váha slova x∈Tn je wt(x)≔dist(x,0).
Věta Je-li C lineární kód, potom d=min{wt(z)|z∈C∖{0}}.
Důkaz Triviální.
Věta Je-li C lineární kód, potom d=min{k∈ℕ+|existuje $k$ lineárně závislých sloupců $H$}.
Poznámka To zní podobně jako hodnost, ale vlastně to s ní nemá moc společného.
Důkaz Označme pravou stranu rovnosti d′. Víme, že existuje x∈C,wt(x)=d. Potom Hx𝖳=0, tudíž nenulové složky x určují lineárně závislé sloupce h. Z toho plyne d′≤d. Zbývá dokázat druhou nerovnost. Jakákoli lineární kombinace méně než d sloupců H jde vyjádřit jako Hy𝖳, kde wt(y)<d, tudíž y∉C∴Hy𝖳≠0 a jde o nenulovou lineární kombinaci. Z toho plyne d′≥d.
Definice Nechť T je konečné těleso velikosti q a m∈ℕ. (q,m)-Hammingův kód je lineární kód, jehož kontrolní matice má jako sloupce právě všechny nenulové vektory z Tm, jejichž první nenulový prvek je 1.
Věta Pro Hammingův kód je d≥3.
Důkaz Podle věty o lineárně závislých sloupcích jednoduché.
Věta Pro Hammingův kód je n=qm−1q−1.
Důkaz Existuje přesně qm−1 nenulových vektorů z Tm a 1q−1 z nich má jako první nenulový prvek jedničku. Nebo se to dá natvrdo spočítat jako součet geometrické řady.
Věta Pro Hammingův kód je k=n−m.
Důkaz Kontrolní matice má m řádků a obsahuje jako sloupce všechny jednotkové vektory, tedy nutně dimH=m. Potom k=dimG=n−dimH=n−m.
Věta Hammingův kód je perfektní.
Důkaz Dosazením t=1 do Hammingovy nerovnosti dostáváme
M(1+n(q−1))≤qn.
Použitím již známých tvrzení dostáváme
qn−m(1+qm−1q−1(q−1))≤qn.
Snadnými úpravami zjistíme, že nastává rovnost, tedy kód je perfektní.
Definice Nechť C1,C2 jsou kódy délky n. C1 je ekvivalentní C2, jestliže existuje permutace π∈𝕊n taková, že
w1⋯wn∈C1⇔wπ(1)⋯wπ(n)∈C2.
Poznámka I někdo z KDAIZ by možná zvládl dokázat, že je to relace ekvivalence.
Definice Lineární kód C⊂Tn dimenze k je systematický, pokud
∀α1,…,αk∈T,∃1αk+1,…,αn:α1⋯αn∈C.
Intuitivně: do prvních k písmen můžeme zakódovat, co chceme, a poté jen správně doplníme.
Věta Nechť C⊂Tn je systematický lineární kód dimenze k. Potom pro generující a kontrolní matici můžeme psát
G=(Ik|F),H=(−F𝖳|In−k),F∈Tk×(n−k).
Důkaz Tvar matice G plyne z definice systematického kódu. Stačí tedy ověřit, že H⋅G𝖳=0.
Věta Každý lineární kód je ekvivalentní nějakému systematickému.
Důkaz Vezmeme nějakou bázi kódu, nastrkáme ji jako řádky do matice a tu upravíme pomocí řádkových úprav do horního trojúhelníkového tvaru. Tím samozřejmě dostaneme bázi toho samého kódu. Teď stačí přeházet sloupce tak, aby prvních k sloupců samo o sobě tvořilo matici s plnou hodností. Tím dostaneme bázi nějakého ekvivalentního kódu. Matici si můžeme doupravit, aby těch prvních k sloupců byla jednotková matice, z čehož je vidět, že jde o systematický kód.
Věta Singletonova nerovnost Nechť C⊂Tn je lineární kód dimenze k s minimální vzdáleností d. Potom n+1≥k+d.
Důkaz Z Frobeniovy věty nebo něčeho takového máme dimC=k=n−h(H). Z definice hodnosti je h(H)+1 minimální číslo takové, že každých tolik sloupců matice H je lineárně závislých. Z toho a z naší věty o lineárně závislých sloupcích zjevně plyne h(H)+1≥d. Odtud už nějak vyčupčíme žádanou nerovnost.
Věta Gilbert-Varshamova mez pro binární kódy Nechť T=ℤ2,r,n,d∈ℕ a platí
∑j=0d−2(n−1j)<2r.
Potom existuje kontrolní matice H∈Tr×n, jejíž kód má minimální vzdálenost alespoň d.
Důkaz Budeme induktivně konstruovat matici H po sloupcích. Nechť již máme i sloupců a chceme přidat (i+1)-tý. Ten musíme vybrat tak, aby to nebyl součet nanejvýš d−2 existujících sloupců. (d−1 už nevadí, protože potom bychom společně s tím nově přidaným měli d lineárně závislých a to je v pořádku.) Takových součtů existuje ∑j=0d−2(ij). Naše nerovnost nám přesně zajistí, že ještě nějaký povolený zbyde.
Definice Pro k,d∈ℕ označme N(k,d) minimální možnou délku lineárního binárního kódu dimenze k s minimální vzdáleností d.
Poznámka Zjevně N(k,1)=k,N(1,d)=d.
Lemma Pro k,d∈ℕ,k≥2 je
N(k,d)≥d+N(k−1,⌈d2⌉).
Důkaz Nechť C je lineární kód délky n≔N(k,d). Víme, že pro nějaké w∈C je wt(w)=d. Bez újmy na obecnosti předpokládejme w=0n−d1d. Generující matice bude mít tvar
G=(0⋯01⋯1⋱⋮⋰⋱⋮⋰⋯G1⋯⋯G2⋯⋰⋮⋱⋰⋮⋱).
Dokážeme, že h(G1)=k−1. Kdyby ne, potom by její řádky byly lineárně závislé, tudíž z nich jde nakombinovat nulové slovo. Pokud nakombinujeme odpovídající řádky původní matice, dostaneme buď nulové slovo, což by znamenalo, že h(G)<k, nebo slovo začínající n−d nulami a následně nenulové, kteréžto má vzdálenost od w menší než d. Každopádně jsme ve sporáku. TBD Nechť C1 je kód délky n−d a dimenze k−1 s generující maticí G1 a d1 je jeho minimální vzdálenost. Dokážeme, že d1≥d2. Vezměme kódové slovo u∈C1,wt(u)=d1 a nějaké další slovo v???
Věta Griesmerova mez
N(k,d)≥∑i=0k−1⌈d2i⌉.
Důkaz Indukcí podle k. Základní případ již máme. Nechť k≥2. Z předchozího lemmatu máme
N(k,d)≥d+N(k−1,⌈d2⌉)≥IPd+∑i=0k−2⌈⌈d2⌉2i⌉≥d+∑i=0k−2⌈d2i+1⌉=d+∑i=1k−1⌈d2i⌉=∑i=0k−1⌈d2i⌉.

Vraťme se k binárnímu Hammingovu kódu. Definujme standardní tabulku, kde na nultém řádku jsou kódová slova a na i-tém řádku jsou slova, která se liší od kódového slova v i-tém bitu.

Věta U binárního Hammingova kódu pro slova y,z je Hy𝖳=Hz𝖳 právě tehdy, pokud leží ve stejném řádku kontrolní tabulky.
Důkaz Máme y=u+ei,z=v+ej,u,v∈C. Potom Hy𝖳−Hz𝖳=H(u𝖳−v𝖳+ei−ej)=H(ei−ej). Toto se rovná nule právě tehdy, pokud i=j, protože jinak wt(ei−ej)=2, tedy ei−ej∉C.
Definice Nechť C je lineární kód a x je slovo. Potom syndrom x je Hx𝖳.
Poznámka Obecně definujeme standardní tabulku tak, že v každém řádku budou slova se stejným syndromem.
Věta Nechť C je lineární binární kód s minimální vzdáleností d a t≔⌊d−12⌋. Potom v každém řádku standardní tabulky je nanejvýš jedno slovo váhy ≤t.
Důkaz Nechť v i-tém řádku jsou slova a,b s vahou nanejvýš t. Potom H(a𝖳−b𝖳)=Ha𝖳−Hb𝖳=0. Jelikož wt(a−b)≤wt(a)+wt(b)≤2t<d, musí být a−b=0.

Cyklické kódy

Definice Lineární kód C délky n je cyklický, pokud s každým slovem obsahuje i jeho cyklické permutace neboli
∀w0w1⋯wn−1∈C:w1⋯wn−1w0∈C.
Poznámka Množinu slov ℤ2n můžeme reprezentovat jako okruh polynomů ℤ2[x]/(xn−1), kde budeme značit z formální proměnnou splňující zn=1. Potom pro cyklický kód platí w∈C⇔w⋅z∈C.
Důsledek Nechť C je cyklický kód reprezentovaný jako polynomy a a∈ℤ2[x]/(xn−1). Potom w∈C⇔a⋅w∈C.
Příklad Paritní kód délky 4 je cyklický:
C={0000,0011,0101,0110,1001,1010,1100,1111}={0,z2+z3,z+z3,z+z2,1+z3,1+z2,1+z,1+z+z2+z3}.
Všimněme si, že jsou to všechno násobky z+1.
Věta Nechť C je cyklický kód délky n a dimenze k. Potom existuje g∈C stupně n−k takový, že
Důkaz Za g vezměme jakýkoli nenulový polynom v C nejmenšího stupně s. Nechť v∈C. Vydělíme se zbytkem (pro jednoduchost v celém okruhu ℤ[x]):
v=a⋅g+r,str<s.
To samé platí i ve faktorokruhu. Z toho máme
r=v−ag∈C.
Z toho plyne, že r=0 neboli g|v. Zároveň už víme, že a⋅g∈C pro každé a, čímž je dokázán první bod věty. Druhý bod plyne z toho, že zapíšeme-li v=a⋅g, dostáváme tím koeficienty pro lineární kombinaci polynomů zig,i=0,…,n−s−1, tudíž z těchto polynomů dokážeme nakombinovat jakýkoli polynom z C. Zřejmě jsou také lineárně nezávislé, protože těžko nějaký z nich nakombinujeme z ostatních, když mají různé stupně. Zároveň z předpokladu dimC=k plyne, že jich musí být k, tedy s=n−k. Zbývá třetí tvrzení, takže budeme zase dělit se zbytkem:
xn−1=hg+r,str<s.
Ve faktorokruhu to znamená
0=hg+r.
Z toho naprosto analogicky jako předtím plyne r=0, což v původním okruhu znamená r=α(xn−1),α∈ℤ. No a zřejmě α=0.
Definice Polynomy g a h z předchozí věty jsou generující polynom a kontrolní polynom kódu C.

V důsledku předchozí věty se dá určit, kolik existuje cyklických kódů dané délky. Například x5−1=(x−1)(x4+x3+x2+x+1), kde oba polynomy na pravé straně jsou ireducibilní, takže existují jen dva cyklické kódy délky 5 (plus dva triviální). Tudíž by nás zajímalo obecně, na co se rozloží xn−1, a to v nějakém obecném tělese se stejným počtem prvků jako ℤ2[x]/(xn−1). Ukazuje se, že to vyjde hezčeji, když místo něj budeme faktorizovat xn+1−x.

Definice Nechť b∈ℤ2[x]/q, kde q je ireducibilní polynom. Potom minimální polynom prvku b je polynom minimálního stupně s prvky ze ℤ2 takový, že f(b)=0.
Věta Každé b∈ℤ2[x]/q má minimální polynom.
Důkaz ℤ2[x]/q je těleso, takže má multiplikativní grupu. Tato grupa je navíc cyklická, protože je to konečné těleso, tudíž existuje nějaké α∈ℤ2[x]/q takové, že ℤ2[x]/q={αk|k∈ℕ}. Nechť b=αl. Označme m≔degq a dosaďme b do polynomu x2m−1−1:
(αl)2m−1−1=(α2m−1)l−1=1l−1=0.
Druhá rovnost plyne z toho, že multiplikativní grupa má 2m−1 prvků. Akorát je problém s tím, že pokud b=0, tak to nefunguje. To vyřešíme tím, že vezmeme polynom x2m−x, kterýžto má samozřejmě nulu jako kořen. Našli jsme polynom, který má b jako kořen, a sice nemusí být minimální, ale to vyřešíme tím, že ho faktorizujeme.
Poznámka Dokonce jsme našli univerzální polynom, který funguje pro všechna b (i když není minimální). To se bude hodit později.
Příklad Vezměme konečné těleso ℤ2[x]/(x3+x+1). To má 8 prvků – všechny polynomy stupně menšího než 3. Zkusíme pro každý najít minimální polynom, tedy takový polynom, že když do něj za x dosadíme ten daný polynom, dostaneme polynom, který je násobek x3+x+1:
bminimální polynom b
0x
1x+1
zx3+x+1
z+1x3+x2+1
z2x3+x+1
z2+1?
z2+z?
z2+z+1?
Vidíme, že to není úplně jednoduché.
Věta Ke každému prvku b∈ℤ2[x]/q existuje právě jeden minimální polynom f. Ten je ireducibilní nad ℤ2 a dělí každý polynom, který má kořen b, speciálně také x2m+x. Navíc je také kořenem b2.
Důkaz Nechť f,f~ jsou dva různé minimální polynomy b. Potom f−f~ má taky za kořen b a má menší stupeň, protože f i f~ začínají jedničkou. Z minimality tudíž plyne f−f~=0. Kdyby f bylo reducibilní, potom by b bylo kořenem jednoho z jeho faktorů, což je spor s minimalitou. Nechť p je libovolný polynom, který má za kořen b, potom můžeme vydělit se zbytkem p÷f, přičemž zbytek má stupeň menší než f a taky má b za kořen, tudíž je nulový. Nyní si rozepišme, jak vypadá f2:
f(x)2=(∑i=0sfixi)=∑i=0sfi2x2i=∑i=0sfix2i=f(x2).
Speciálně f(b2)=f(b)2=0. Podle již dokázaného tvrzení musí minimální polynom b2 dělit f a jelikož f je ireducibilní, je to jeho minimální polynom.
Věta Je-li q∈ℤ2[x] ireducibilní polynom stupně m, potom x2m−x je součin všech různých minimálních polynomů prvků ℤ2[x]/q.
Důkaz Už jsme si dokázali, že každý minimální polynom dělí x2m−x. Stačí tedy dokázat, že se tam nevyskytuje víckrát. Nechť Π je součin všech různých minimálních polynomů. Víme, že Π|(x2m−x). Zároveň p má za kořeny všechny prvky tělesa, kterých je 2m, tudíž degΠ≥2m, z čehož plyne Π=x2m−x.
Věta Nechť b∈ℤ2[x]/q a α ne nejmenší kladné číslo takové, že b2α=b. Potom minimální polynom b je
f≔∏i=0α−1(x−b2i).
Důkaz Víme, že minimální polynom b má také za kořen b2, tudíž i b4 a tak dále až do b2α−1, tudíž jeho stupeň je alespoň stupeň f. Víme tedy, že pokud f je vůbec platný polynom, potom už musí být minimální k b (protože b je jeho kořen).K tomu musíme ověřit, že koeficienty f jsou ze ℤ2. Máme
f(x)2=∑i=0α−1(x2−b2i+1)=f(x2).
Pokud si to rozepíšeme a porovnáme po členech, máme ∀i:ai=ai2, z čehož plyne ai∈ℤ2.

Takže teď umíme rozložit x2m−x, ale my chceme obecně xn−1. Co s tím? Z technických důvodů budeme s újmou na obecnosti uvažovat jen lichá n.

Věta Nechť n∈ℕ je liché. Potom existují r,m∈ℕ taková, že n⋅r=2m−1.
Důkaz Z Eulerovy-Fermatovy věty máme
2φ(n)≡1(modn).
Z toho přímo plyne tvrzení věty.

Vezměme tedy taková r,m. Z algebry nějak víme, že existuje ireducibilní polynom q stupně m (tudíž ℤ2[x]/q je těleso) a β∈ℤ2[x]/q takové, že βi jsou různé pro i=1,…,2m−1, přičemž pro i=2m=1 je to rovno 1.

Polynomy αi≔βir pro i=1,…,n jsou různé kořeny rovnice xn=1. Z toho plyne, že to musí být všechny kořeny. ??? xn−1 je součin minimálních polynomů prvků b∈ℤ2[x]/q, kde řád b dělí n.

Věta Nechť C je cyklický kód liché délky n. Potom g(x) je součin minimálních polynomů k prvkům αi1,…,αis, kde α je prvek řádu n v nějakém tělese ℤ2[x]/q.
Důkaz Viz výše.
Definice αi1,…,αis z předchozí věty jsou generující kořeny kódu C.

Teď už máme nějaký cyklický kód a chceme vymyslet způsob, jak zakódovat nějakou informaci. Mějme nějaké datové slovo d0⋯dk−1. Definujme polynom a≔∑i=0k−1dixi. Jako kódové slovo stačí vzít a⋅g. To plyne z toho, že tyto výsledky pro různá a právě dávají celý kód.

Ovšem pro pohodlnost by bylo hezké kód přepermutovat, aby byl systematický. To sice umíme pro obecný lineární kód, ale není zaručené, že tím vznikne cyklický kód. Definujme si tentokrát a≔∑i=0n−1dixn−1−i. Vydělíme se zbytkem a=něco⋅g+r. Jako kódové slovo vezmeme a−r. Jelikož r je menšího stupně než g, nepoškodíme si tím bity na konci, ve kterých je zpráva. Tudíž máme kód, který je „obráceně“ systematický. V případě potřeby ho samozřejmě můžeme obrátit a pořád bude cyklický.

Zajímalo by nás, jestli je Hammingův kóď ekvivalentní cyklickému kódu. Ukazuje se, že pro obecné q nemusí být, ale pro binární Hammingův kód to dokážeme. Máme tedy nějaké n, které se rovná 2m−1, a chceme najít cyklický kód se stejnými parametry jako Hammingův, tudíž dimenze n−m.

BCH kódy

Definice BCH kód je kód v tělese 𝔽2m≃ℤ2[x]/q generovaný kořeny α a α3, kde α je prvek řádu n.
Příklad Méjme n≔15,m≔4. Vezmeme ireducibilní polynom q≔x4+x+1. Prvky 𝔽16 jsou všechny polynomy stupně nanejvýš 3, to jest
𝔽16={0,1,z,z+1,z2,z2+1,z2+z,z2+z+1,z3,z3+1,z3+z,z3+z+1,z3+z2,z3+z2+1,z3+z2+z,z3+z2+z+1}.
Jako generátor můžeme vzít například α≔z:
MocninaHodnotaMinimální polynom
α01x+1
α1zx4+x+1
α2z2x4+x+1
α3z3x4+x3+x2+x+1
α4z+1x4+x+1
α5z2+zx2+x+1
α6z3+z2x4+x3+x2+x+1
α7z3+z+1
α8z2+1x4+x+1
α9z3+z
α10z2+z+1x2+x+1
α11z3+z2+z
α12z3+z2+z+1x4+x3+x2+x+1
α13z3+z2+1
α14z3+1
Protože chceme BCH kód, pro generující polynom vezmeme minimální polynomy pro α a α3, tedy máme
g=(x4+x3+x2+x+1)(x4+x+1).
Jelikož zároveň n=14, kontrolní polynom h má stupeň 6, z čehož plyne, že máme 27 kódových slov. Teď by nás zajímalo, jaká je minimální vzdálenost. Spočteme si
g=x8+x7+x6+x4+1.
Z toho plyne, že existuje kódové slovo váhy 5, tudíž d≤5. Pro dané slovo w vyjádřené jako polynom platí
w∈C⇔w(α)=0∧w(α3)=0.
Na základě tohoto poznatku si definujeme něco jako kontrolní matici tak, aby platilo w∈C⇔H~w=0:
H~≔(1αα2α3α4α5α6⋯α141α3α6α9α121α3⋯α12).
Každý prvek matice si vyjádříme jako čtyřsložkový sloupcový vektor odpovídající koeficientům u polynomu:
H≔(10001⋯101001⋯000100⋯000010⋯110001⋯100011⋯100101⋯101111⋯1).
To už je skutečná kontrolní matice. Mějme nějaké slovo u, u kterého se staly dvě chyby, tudíž je ve vzdálenosti 2 od nějakého kódového slova: u=w+e≔w+xi+xj,w∈C,i≠j. Potom Hu=He=Hxi+Hxj. Zároveň
Hu=(u(α)u(α3))=(e(α)e(α3))=(αi+αjα3i+α3j)≕(s1s3).
Jelikož α je generátor, máme αi≠αj a tedy s1≠0. Z binomické věty
s13=α3i+α3j+α2iαj+αiα2j=s3+αiαjs1;
αiαj=s3s1−1+s12.
Zavedeme-li ještě další formální proměnnou λ, můžeme psát
(λ+αi)(λ+αj)=λ2+(αi+αj)λ+αiαj=λ2+s1λ+s3s1−1+s12.
Tudíž pokud umíme řešit takovouto kvadratickou rovnici, můžeme si snadno dopočíst, kde se staly chyby. Uvažujme ještě případ, kdy nastala jen jedna chyba, tedy e=xi. Potom máme s1=αi,s3=α3i a dostaneme přesně tu samou rovnici, akorát s nulou místo xj. Tedy i tento případ dokážeme detekovat. Celkově umíme rozpoznat a opravit až dvě chyby, tudíž d=5.
Věta Davenport Nechť 𝔽q je konečné těleso s q=pm prvky (tedy ℤp/r, kde r je ireducibilní polynom stupně m). Potom existuje primitivní prvek β∈𝔽q takový, že {βpi|i=0,…,m−1} je báze 𝔽q jakožto lineárního prostoru nad ℤp.
Poznámka Toto β vůbec nesouvisí s generátorem cyklické grupy 𝔽q.
Příklad Pro 𝔽16=ℤ2/(x4+x+1) vezměme β≔z3. Máme
β2=(z3)2mod(z4+z+1)=z3+z2;
β4=(z3+z2)2mod(z4+z+1)=z3+z2+z+1;
β8=(z3+z2+z+1)2mod(z4+z+1)=z3+z.
Ve vektorové podobě máme množinu
{(0001),(0011),(1111),(0101)}.
Snadno ověříme, že je to báze.
Lemma Mějme kvadratickou rovnici tvaru aλ2+bλ+c,a,b≠0. Potom bez újmy na obecnosti stačí řešit rovnici tvaru μ2+μ+d.
Důkaz Použijme substituce d≔cab2 a μ≔abλ. Potom rovnice pro μ má tvar
a2b2λ2+abλ+cab2.
Vynásobením b2a dostaneme původní rovnici.
Věta Mějme v tělese 𝔽2m kvadratickou rovnici aλ2+c=0,a≠0, kterou můžeme substitucí d≔ca převést na tvar λ2+d=0. Nechť d=∑i=0m−1diβ2i, kde β je primitivní prvek z Davenportovy věty. Potom řešení rovnice je
λ=∑i=0m−2di+1β2i+d0β2m−1.
Důkaz
λ2=∑i=0m−2(di+1)2(β2i)2+d02(β2m−1)2=∑i=0m−2di+1β2i+1+d0β=d.
Důsledek V konečném tělese charakteristiky 2 má každý prvek odmocninu.
Věta Májme v tělese 𝔽2m kvadratickou rovnici μ2+μ+d=0. Nechť d=∑i=0m−1diβ2i, kde β je primitivní prvek z Davenportovy věty. Potom rovnice má řešení, právě když
∑i=0m−1di≡0(mod2).
V takovém případě jsou dvě řešení ve tvaru
μk≔∑i=0m−1(k+∑j=1idj)β2i,k∈{0,1}.
Důkaz
(⇒)
Nechť μ=∑i=0m−1μiβ2i je nějaké řešení rovnice. Potom
d=μ2+μ=μm−1β+∑i=1m−1μi−1β2i+∑i=0m−1μiβ2i.
Porovnáním po koeficientech a sečtením máme
∑i=0m−1di=2∑i=0m−1μi≡0(mod2).
(⇐)
Pro výraz (μk)2+μk spočteme koeficient u β2i. Pro μ2 to bude ten, který byl původně u β2i−1 (nebo u βm−1, pokud i=0), takže máme pro i>0
k+∑j=1i−1dj+k+∑j=1idj=di
nebo pro i=0
k+∑j=1m−1dj+k=d0.

Když jsme jako generátor vzali α, dostali jsme Hammingův kód, který umí opravovat jednu chybu. S generátory α,α3 jsme dostali kód, který umí opravovat dvě chyby. Co kdybychom zkusili přidávat další liché mocniny?

Definice Nechť a1,…,ad jsou prvky nějakého tělesa. Potom Vandermondova matice je
V(a1,…,ad)≔(a10⋯ad0⋮⋱⋮a1d−1⋯add−1).
Lemma
detV(a1,…,ad)=detV(a1,…,ad−1)⋅∏i=1d−1(ad−ai).
Důkaz Za domácí úkol.
Věta
detV(a1,…,ad)=∏k=1d∏i=1k−1(ak−ai).
Důkaz Indukcí z předchozího lemmatu.
Definice Nechť d,m∈ℕ a α je prvek řádu n v tělese 𝔽2m. BCH kód pro vzdálenost d je cyklický kód délky n s generujícími kořeny α,α2,…,αd−1.
Poznámka Pro d=5 bychom dostali čtyři generátory α,α2,α3,α4, ale jelikož generující polynomy pro α2,α4 jsou stejné jako pro α,α2, minimální polynom vyjde stejně, jako kdybychom vzali jenom α,α3.
Věta BCH kód pro vzdálenost 2t+1 má skutečně vzdálenost alespoň 2t+t, tedy spravuje t chyb.
Důkaz Kontrolní matice pro BCH kód je z definice
H=(1αα2α3⋯αn−11α2α4α6⋯α2n−21α3α6α9⋯α3n−3⋮⋮⋮⋮⋱⋮1α2tα4tα6t⋯α2tn−2t).
Podle nějaké dávné věty stačí dokázat, že každých 2t sloupců je lineárně nezávislých. Vyberme nějaké sloupce:
M≔(αi1⋯αi2tα2i1⋯α2i2t⋮⋱⋮α2ti1⋯α2ti2t).
To je skoro Vandermondova matice, akorát nezačíná jedničkami, takže při počítání determinantu musíme nejdřív vytknout:
detM=(∏j=12tαij)⋅det(1⋯1αi1⋯αi2t⋮⋱⋮α(2t−1)i1⋯α(2t−1)i2t)=(∏j=12tαij)⋅∏k=12t∏j=1k−1(αik−αij)≠0.

Teď je otázkou, jak nějak efektivně dekódovat BCH kód. Dejme tomu, že bylo vysláno slovo w∈C a přijato slovo v=w+e,wt(e)≤p. Pomocí kontrolní matice snadno spočteme syndrom (s1,…,s2t)𝖳≔He=Hv. Je-li ℐ množina pozic, na kterých se staly chyby, potom z definice H platí

sk=∑i∈ℐαki.

Takže je snadné spočítat syndromy z indexů, ale my chceme udělat přesný opak – známe syndromy a máme určit indexy. Pro ℐ={i1,…,ip} si označme aj≔αij,j∈p^ a definujme lokátor:

f≔∏j=1p(1−apx).

Pokud najdeme kořeny lokátoru x1,…,xp, můžeme spočíst aj=xj−1 a to si potom dohledáme v nějaké tabulce, čímž zjistíme ij. Takže úplně stačí najít kořeny lokátoru, který ale samozřejmě neznáme. Jen víme, že má nějaké koeficienty:

f=∑j=0pfjxj.

Zřejmě f0=1. Spočteme si z obou tvarů formální derivaci:

f′=∑j=1pjfjxj−1=∑j=1⌊p2⌋f2j+1x2j;
f′=∑j=1p−aj1−ajxf=f⋅∑j=1p(−aj∑k=0∞(aj−x)k)=f⋅∑k=1∞xk−1∑j=1pajk=f⋅∑k=1∞xk−1sk.

Porovnáme obě vyjádření:

∑j=1⌊p2⌋f2j+1x2j=(∑j=0pfjxj)⋅∑k=1∞xk−1sk;
f1=s10=s2+f1s1f3=s3+f1s2+f2s10=s4+f1s3+f2s2+f3s1f5=s5+f1s4+f2s3+f3s2+f4s1⋮0=s2p−1+s2p−2s1+⋯+sp−1fp.

Zapíšeme si to do matičkové podoby:

(s1s3s5⋮s2p−1)=(100000⋯0s2s11000⋯0s4s3s2s110⋯0⋮⋱⋮s2p−2s2p−3⋯sp−1)=(f1f2f3⋮fp).

Akorát je tu trochu problém, že neznáme p. Dá se dokázat, což tady dělat nebudeme, že pokud matici pro dané p označíme Mp, potom pro to správné p je Mp regulární, Mp+1 taky a všechny další už ne. Takže podle toho to už najdeme.

Plotkinova mez

Definice Pro n,d∈ℕ označme A(n,d) maximální M takové, že existuje (n,M,d) kód nad ℤ2.
Poznámka Teď už nepožadujeme, aby kód byl lineární!
Lemma Pro každé n,r∈ℕ je A(n,2r−1)=A(n+1,2r).
Důkaz Nechť C je (n,M,2r−1)-kód, kde M≔A(n,2r−1) je maximální možné. Definujme kód, který je stejný, ale s přidaným paritním bitem:
C+≔{w1⋯wn+1|w0⋯wn∈C,wn+1≔∑i=1nwi}.
Dokážeme, že C+ je (n+1,M,2r)-kód. Nechť u+,w+∈C+. Zjevně dist(u,w)≥2r−1. Předpokládejme pro spor, že platí rovnost. V takovém případě mají nutně u,w stejný paritní bit a liší se v 2r−1 „normálních“ bitech, což je liché číslo. Ale to je blbost. Naopak, máme-li (n+1,M′,2r)-kód, kde M′≔A(n+1,2r), umazáním poslední souřadnice z něj vyrobíme (n,M,2r−1)-kód.
Lemma Pro každé n,d∈ℕ je A(n,d)≤2A(n−1,d).
Důkaz Nechť C je (n,M,d)-kód, kde M≔A(n,d). Pro i∈{0,1} definujme
Ci≔{w1⋯wn−1|w1⋯wni∈C}.
Jeden z C0,C1 zjevně musí mít velikost aspoň M2, takže je to alespoň (n−1,M2,d)-kód.
Lemma Nechť n,d∈ℕ,2d>n. Potom
A(n,d)≤2⌊d2d−n⌋.
Důkaz Nechť C je (n,M,d)-kód, kde M≔A(n,d). Zjevně platí
∑u,w∈Cdist(u,w)≥M(M−1)d.
Pro každé j=1,…,n označme αj počet kódových slov, která mají na j-tém bitu jedničku. Potom počet dvojic slov, která se v j-tém bitu liší, je αj(M−αj), z čehož plyne
∑u,w∈Cdist(u,w)=2∑j=1nαj(M−αj).
Porovnáním a vydělením dvěma dostaneme
M(M−1)2d≤∑j=1nαj(M−αj).
Snadno ověříme (třeba pomocí derivace), že αj(M−αj)≤⌊M2⌋⌈M2⌉, takže máme
M(M−1)2d≤n⌊M2⌋⌈M2⌉.
Pro M sudé máme
M(M−1)2d≤M24n,
což snadno upravíme do tvaru
M2≤d2d−n.
Jelikož M2 je sudé číslo, můžeme pravou stranu bez obav zabalit do dolní celé části. Vynásobením dvěma dostaneme kýženou nerovnost. A co pro liché M?
M(M−1)2d≤M2−14n.
Úpravami dostaneme
M≤n2d−n=2d2d−n−1.
Jelikož M∈ℕ, můžeme psát
M≤⌊2d2d−n⌋−1.
Snadno ověříme, že pro libovolné x∈ℝ je ⌊2x⌋≤2⌊x⌋+1. Aplikací tohoto tvrzení dostaneme znění věty.
Věta Plotkinova mez Nechť n,d∈ℕ. Potom:
  1. Je-li d sudé a 2d>n, potom A(n,d)≤2⌊d2d−n⌋.
  2. Je-li d sudé a 2d=n, potom A(n,d)≤4d.
  3. Je-li d liché a 2d+1>n, potom A(n,d)≤2⌊d+12d+1−n⌋.
  4. Je-li d liché a 2d+1=n, potom A(n,d)≤4d+4.
Důkaz Použitím předchozích tří lemmat:
  1. Již dokázáno.
  2. A(2d,d)≤2A(2d−1,d)≤4⌊d2d−(2d−1)⌋=4d
  3. A(n,d)=A(n+1,d+1)≤2⌊d+12(d+1)−(n+1)⌋=2⌊d+12d+1−n⌋
  4. A(2d+1,d)=A(2d+2,d+1)≤4(d+1)
Definice Hadamardova matice je matice H∈{±1}n×n taková, že HH𝖳=nI.
Poznámka Označíme-li v1,…,vn sloupce H, potom vivjT=nδi,j, neboli řádky musí být na sebe kolmé. Jinými slovy, každé dva řádky se musí lišit ve stejném počtu čísel jako shodovat.
Příklad Pro n=1 je (1) Hadamardova matice. Pro n=2 je (11−11) Hadamardova matice.
Poznámka Existuje domněnka, že Hadamardova matice existuje pro každé n=4k,k∈ℕ.
Lemma Je-li n≥3 a existuje Hadamardova matice velikosi n, potom n je násobek 4.
Důkaz Zjevně pokud v Hadamardově matici vynásobíme nějaký řádek nebo sloupec −1, pořád to bude Hadamardova matice. Vynásobme všechny sloupce tak, aby v prvním řádku byly samé jedničky. Označme:
a≔počet sloupců začínajících (111)𝖳;
b≔počet sloupců začínajících (11−1)𝖳;
c≔počet sloupců začínajících (1−11)𝖳;
d≔počet sloupců začínajících (1−1−1)𝖳.
Zjevně platí a+b+c+d=n. Z kolmosti prvního a druhého řádku plyne a+b−c−d=0. Z kolmosti prvního a třetího řádku plyne a−b+c−d=0. Z kolmosti druhého a třetího řádku plyne a−b−c+d=0. Sečtením těchto rovností dostaneme 4a=n.
Definice Nechť A∈ℝn×n,B∈ℝs×s jsou čtvercové matice. Potom jejich tenzorový součin je
A⊗B≔(A1,1B⋯A1,nB⋮⋱⋮An,1B⋯An,nB).
Poznámka Na TA jsme tomu říkali Kroneckerův součin.
Lemma
(A⊗B)𝖳=A𝖳⊗B𝖳.
Důkaz Rozepsáním.
Lemma
(A⊗B)(C⊗D)=AC⊗BD.
Důkaz Na TA jsme to měli za domácí úkol.
Věta Sylvesterova konstrukce Jsou-li Hn a Hm Hadamardovy matice, potom Hn⊗Hm je Hadamardova matice.
Důkaz Zřejmě Hn⊗Hm∈{±1}mn×mn. Podle předchozích lemmátek máme
(Hn⊗Hm)(Hn⊗Hm)𝖳=(Hn⊗Hm)(HnT⊗HmT)=HnHnT⊗HmHmT=nIn⊗mIm=mnImn.
Důsledek Pro každé n∈ℕ0 existuje Hadamardova matice velikosti 2n×2n.
Důkaz Indukcí: Začneme s maticí (1) a budeme ji postupně tenzořit (111−1).
Definice Nechť C1 je (n1,M1,d1)-kód a C2 je (n2,M2,d2)-kód. Potom C1⊕︎C2 je (n1+n2,min{M1,M2},d1+d2)-kód, který vytvoříme tak, že nějak seřadíme slova v obou kódech a spojíme ta na stejných indexech (pokud má jeden víc slov, přebytečná zahodíme).
Definice Nechť C je (n,M,d)-kód a b∈ℕ. Potom bC≔(C⊕︎⋯⊕︎C)⏟n× je (bn,M,bd)-kód.

Vytvoříme-li kód An, jehož kódová slova budou řádky Hadamardovy matice velikosti n×n (s přemapováním 1↦0,−1↦1), zjevně to bude (n,n,n2)-kód.

Navíc pokud všechny řádky a sloupce vynásobíme tak, aby začínaly jedničkou, můžeme první sloupec beze strachu smazat a dostaneme tím (n−1,n,n2)-kód 𝒜n, který navíc obsahuje nulové slovo.

A pokud z něj vezmeme jen slova začínající nulou a tyto nuly smažeme, dostaneme (n−2,n2,n2)-kód 𝒜n′ (to, že má přesně n2 slov, plyne z toho, že druhý smazaný sloupec byl kolmý na první smazaný sloupec).

Teď se vraťme k An a vytvořme kód Bn tím, že přidáme ke všem slovům jejich negaci. S trochou přemýšlení ověříme, že je to (n,2n,n2)-kód.

Věta Levenštejnova, napsaná podle Volce Plotkin s „=“, když Hadamard dá.
Věta Levenštejnova, napsaná normálně Nechť n,d∈ℕ. Potom
  1. Je-li d sudé a 2d>n a platí Hadamardova domněnka, potom A(n,d)=2⌊d2d−n⌋.
  2. Je-li d sudé, 2d=n a existuje Hadamardova matice velikosti n×n, potom A(n,d)=4d.
  3. Je-li d liché a 2d+1>n a platí Hadamardova domněnka, potom A(n,d)=2⌊d+12d+1−n⌋.
  4. Je-li d liché a 2d+1=n a existuje Hadamardova matice velikosti (n+1)×(n+1), potom A(n,d)=4d+4.
Důkaz Podle jistého lemmatu víme, že stačí uvažovat d sudé. Pro n=2d z kódu Bn vidíme, že A(n,d)≥4d a podle Plotkinovy meze platí rovnost. Nechť n<2d. Definujme k≔⌊d2d−n⌋. Označme a≔dmod(2d−n),b≔(2d−n)−a. Potom z definice dolní celé části platí
k=d−a2d−n,k+1=d+b2d−n.
Odečtením téchto rovností dostaneme
1=a+b2d−1∴a+b=2d−n.
Vynásobením první rovností máme
k(a+b)=d−a.
Trochu si upravíme definici b a dosadíme do ní tuto rovnost:
n=2d−b−a=2(d−a)+a−b=2k(a+b)+a−b.
Ted rozlišíme dva případy:
  • Je-li k sudé, vezměme kód b𝒜2k⊕︎a2𝒜4k+4′. Spočteme si jeho parametry:
    n*=b(2k−1)+a2(4k+2)=n;
    M*=min{2k,4k+42}=2k;
    d*=b2k2+a22k+22=d.
  • Je-li k liché, vezměme kód b2𝒜4k′⊕︎a𝒜2k+2. Spočteme si jeho parametry:
    n*=b2(4k−2)+a(2k+1)=n;
    M*=min{4k2,2k+2}=2k;
    d*=b24k2+a2k+22=d.