Uvažujte Reed-Salomonův (4,7)-kód nad tělesem F11 v bodech 0,...,6. Dorazila zpráva (1,2,3,4,5,6,10). Co byla původní zpráva? Napište ji jako posloupnost čísel a,b,c,d, která reprezentují polynom a+bx+cx^2+dx^3.
1,1,0,0
Z prvních šesti hodnot je jasně vidět, že jde o polynom x+1, chyba nastala pouze na posledním políčku.
Ten kód opravuje jednu chybu, čili pokud se v Hammingově vzdálenosti 1 (tj. po změně jedné hodnoty) vyskytuje posloupnost hodnot nějakého polynomu stupně <4, musí být původní zprávou ten polynom. Pokud se tam taková posloupnost nevyskytuje, nastalo víc chyb než jedna a opravit to nejde.


Uvažujte Reed-Salomonův (k,256)-kód nad tělesem F256. Jaké největší k musíme zvolit, aby nám tento kód opravoval aspoň 10 chyb v každé sekvenci 256 písmen? (Písmenem zde rozumíme jeden prvek F256.)
236
Kód opravuje aspoň (n-k)/2 chyb, takže rozdíl musí být aspoň 20, takže k nejvýše 236


Na závodech se sešli sportovci z pěti kontinentů, z každého kontinentu po jednom zástupci v každé z pěti disciplín. Existuje nějaké rozestavení sportovců do čvterce 5×5, kde v každém řádku a každém sloupci bude po jednom sportovci z každého kontinentu a každé disciplíny, a zároveň na diagonále budou samí Evropani?
ano
Latinské čtverce budou dány vzorcem a_{i,j}=i+kj mod 5, pro dvě různá k. Pokud vezmete pro kontinenty k=-1 a za Evropu zvolíte 0, na diagonále budou Evropani.



*** Q&A ***

Q: Moc nerozumím, proč se ve skriptech udávají liché verze toho k pro Reed-Salomonův kod. Tedy pro F256 volíme n=255, protože pak by bylo nejvyšší takové k (ze zadání 2 otázky v tomto kvízu) 235.
A: Pokud nás nezajímá složitost výpočtu, ale pouze schopnost opravovat chyby, můžeme volit n=256 a interpolujeme ve všech bodech tělesa. Pokud nás složitost zajímá, chceme použít rychlou Fourierovu transformaci, ale ta umí vyhodnocovat/interpolovat pouze v nenulových bodech a těch je pouze 255. V praxi se používá ten případ n=255, ale úloha dává smysl i tak, jak jsem ji zadal.


Q: V tvrzení 8.6, proč jsme přepisovali m(alpha)=sum(...) equiv sum(...) = m(alpha) equiv 0? Co značí ty mezikroky? (proč ne rovnou m(alpha) equiv 0?)
A: Nejdřív musím spočítat hodnotu polynomu m po dosazení prvku alfa. To není polynom m(alfa), ten vůbec není prvkem faktorokruhu T[alfa]/(m(alfa), tam jsou jen polynomy menšího stupně! Čili počítám pečlivě každou mocninu alfa^i modulo m(alfa), z nich je ovšem netriviální modulo jen u alfa^n, a tak to nakonec vyjde nula. Ve skriptech to bylo napsané dost nešťastně, přepsal jsem to.