- Nazwa przedmiotu:
- Kody wykrywające i korygujące błędy
- Koordynator przedmiotu:
- dr Agata Pilitowska
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia II stopnia
- Program:
- Matematyka
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- Semestr nominalny:
- 3 / rok ak. 2009/2010
- Liczba punktów ECTS:
- 5
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład30h
- Ćwiczenia15h
- Laboratorium0h
- Projekt0h
- Lekcje komputerowe0h
- Wymagania wstępne:
- Przed rozpoczęciem nauki przedmiotu student powinien:
- posiadać umiejętność stosowania rachunku zdań i kwantyfikatorów oraz indukcji matematycznej w prowadzeniu rozumowań, w szczególności w dowodzeniu twierdzeń;
- wykazać się znajomością przestrzeni liniowych, ich bazy i wymiaru, przekształceń liniowych, macierzy, wyznaczników oraz rozwiązywania układów równań;
- znać zagadnienia związane z kongruencjami, ideałami pierścieni, pierścieniami ilorazowymi, ze szczególnym uwzględnieniem pierścieni wielomianów:
- posiadać wiedzę na temat konstrukcji i najważniejszych własności ciał skończonych;
- znać podstawowe wiadomości z zakresu teorii liczb, ze szczególnym uwzględnieniem teorii kongruencji;
- znać podstawowe wiadomości z teorii binarnych kodów liniowych a zwłaszcza kodów wielomianowych.
Przedmioty poprzedzające:
1. Algebra i jej zastosowania I
2. Algebra i jej zastosowania II
3. Algebra liniowa z geometrią
4. Elementy logiki i teorii mnogości
- Limit liczby studentów:
- Cel przedmiotu:
- W wyniku zaliczenia przedmiotu student zdobywa wiedzę na temat wybranych metod kodowania i dekodowania liniowego nad dowolnym ciałem skończonym i poznaje jak zaawansowane narzędzia algebraiczne pozwalają rozwiązywać praktyczne problemy w teorii kodowania.
- Treści kształcenia:
- Wykład:
1. Kody liniowe nad dowolnymi ciałami skończonymi. Ogólne metody kodowania i dekodowania. Kody dualne. Wielkość kodów liniowych.
2. Wybrane metody konstrukcji kodów.
3. Ograniczenia na wielkość kodów. Ocena granicznych możliwości kodów. Kody nieliniowe.
4. Kody doskonałe, ich parametry i związki z kombinatoryką. Kody Hamminga i kody Golaya.
5. Kody cykliczne jako ideały w odpowiednich pierścieniach ilorazowych. Zera kodów cyklicznych.
6. Kody BCH - kody poprawiające błędy wielokrotne. Binarne kody BCH i metody ich dekodowania.
7. Niebinarne kody Reeda-Solomona (szczególny przykład kodów BCH).
8. Kody liniowe z maksymalną odległością (rozszerzone kody RS). Cykliczne kody MDS.
9. Kody reszt kwadratowych. Dekodowanie permutacyjne.
10. Kody alternujące (uogólnione kody RS). Kod śladowy.
Ćwiczenia:
Rozwiązywanie zadań i problemów oraz analiza przykładów związanych z treścią wykładu.
- Metody oceny:
- W semestrze przewidziane są na ćwiczeniach dwa kolokwia 45-minutowe. Za każde kolokwium można uzyskać do 20 punktów. Ponadto za aktywność na ćwiczeniach można uzyskać do 20 punktów. Ostateczna ocena zostanie wystawiona na podstawie punktów uzyskanych za kolokwia oraz za aktywność.
Do uzyskania oceny pozytywnej potrzeba w sumie minimum 30 punktów.
Studenci, którzy nie uzyskali oceny pozytywnej, mają prawo do jednego kolokwium poprawkowego.
- Egzamin:
- Literatura:
- 1. N.J.A.Sloane, F.J. MacWilliams, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
2. V.Pless, Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, 1982.
3. J.H. van Lint, Introduction to Coding Theory, Springer, 1999.
4. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa,
5. W. Marzantowicz, P. Zarzycki, Elementarna teoria liczb, PWN, Warszawa, 2006.
6. W.J. Gilbert, W.K. Nicholson, Algebra współczesna z zastosowaniami, WNT, Warszawa, 2008.
7. T. Świrszcz, Algebra liniowa z geometrią analityczną, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa, 1996.
- Witryna www przedmiotu:
- Uwagi:
Efekty uczenia się