Základní informace
Sylabus a základní informace viz popis předmětu ve Studijním informačním systému.
Rozvrh (k nalezení též v SISu):
- pondělí 12:20-13:50 v místnosti K3,
- čtvrtek 12:20-13:50 v místnosti K2.
V tomto semestru bude věnována značná pozornost samoopravným kódům také na Semináři z matematiky inspirované kryptografií (NMIB021), který se poprvé koná v úterý 4. října v seminární místnosti Katedry algebry.
Zkouška
Zkouška proběhne v následujících termínech:
- středa 18. ledna od 14:00 v seminární místnosti Katedry algebry (odkaz do SISu),
- pátek 27. ledna od 10:00 v seminární místnosti Katedry algebry (odkaz do SISu),
- pátek 17. února od 10:00 v seminární místnosti Katedry algebry (odkaz do SISu),
Další termíny vypisovat neplánuji. Pokud se Vám z jakéhokoliv důvodu složit zkoušku v těchto termínech nepodaří, kontaktuje mě a domluvím se s Vámi na případném přezkoušení osobně.
Domácí úkoly
- Spočítejte váhové polynomy Hammingova kódu H4 a ternárního Golayova kódu G11 (termín odevzdání: 31.10.)
- Považujte binární zápis svého studentského čísla zarovnaný nulami na 32 bitů za přijaté slovo. Dekódujte toto slovo za použití Reed-Mullerova kódu R(1,5) (termín odevzdání: 14.11.)
- Určete generující polynom a dimenzi cyklického kódu délky 15 nad F2 s generujícími kořeny ξ a ξ3, kde ξ je primitivní patnáctá odmocnicna z jedné (termín odevzdání: 24.11.)
- Uvažujte posloupnost s1, s2, s3, s4 prvků tělesa F11, kde s1 až s4 jsou první čtyři cifry Vašeho studentského čísla (v obyčejném desítkovém zápisu). Aplikujte Berlekampův-Masseyův algoritmus a spočítejte posuvný registr minimální délky, který tuto posloupnost čtyř prvků tělesa F11 generuje (termín odevzdání: 12.12.)
- Dekódujte přijaté slovo, které bylo zakódováno v Reed-Solomonově kódu RS8,5 a při jehož přenosu došlo k jedné chybě. Slovo získáte kliknutím na tento odkaz (termín odevzdání: 5.1.)
Skripta
Níže jsou odkazy na různá skripta ve formátu PDF, ve kterých se najde drtivá většina z toho, co bylo přednášeno. Upozorňuji ale, že obsah zkoušky se bude primárně řídit obsahem přednášky.
- Skripta T. Kaisera ze ZČÚ v Plzni.
-
Skripta A. Drápala, ke stažení po kapitolách:
- Kapitola 1 – Co jsou lineární kódy,
- Kapitola 2 – Hrátky s maticemi,
- Kapitola 3 – Designy a konstrukce Golayova kódu,
- Kapitola 4 – Perfektní a MDS kódy,
- Kapitola C – Cyklické kódy,
- Kapitola 5 – GRS a alternantní kódy,
- Kapitola D – BCH kódy a QR kódy,
- Kapitola 6 – Reed-Mullerovy kódy,
- Kapitola 7 – Hadamardovy matice a kódy, a něco odhadů,
- Kapitola 8 – Asymptotické odhady,
- Kapitola 9 – Teorie informace.
- Skripta L. Barta ke konečným tělesům (pro základ k cyklickým kódům).
Jedno téma, které bohužel v žádných skriptech pokryto není, je otázka dekódování BCH kódů a speciálně pak Berlekampův-Masseyův algoritmus pro syntézu posuvného registru. Zde je dobrým zdrojem Masseyův článek (odkaz je na oficiální verzi, pokud by mimo MFF UK nešla stáhnout, daly se na Googlu najít i kopie jinde):
- J. L. Massey, Shift-Register Synthesis and BCH Decoding, IEEE Transactions of Information Theory, vol. IT-15, no. 1, 1969.
Další téma, které ve výše uvedených skriptech není úplně uspokojivě pokryto, jsou Shannonovy věty. Doplněná a upřesněná verze podle přednášky je k dispozici ke stažení v souboru PDF:
Pro zajímavost uvádím, že mnohem obecnější podoba těchto vět je uvedena v Shannonově původním a velmi pěkném (byť poněkud náročnějším) článku
- C. E. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, vol. 27, pp. 379–423, 1948.
Malý atlas samoopravných kódů
K dispozici je také tato stránka:
- Malý atlas kódů - stručný seznam kódů probíraných v rámci této přednášky.