Module also offered within study programmes:
General information:
Name:
Block Codes
Course of study:
2019/2020
Code:
AMAT-2-022-MN-s
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Mathematics in Technical and Natural Sciences
Field of study:
Mathematics
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Responsible teacher:
prof. zw. dr hab. Skupień Zdzisław (skupien@agh.edu.pl)
Module summary

Zastosowanie algebry w problemach związanych z kodowaniem, szyfrowaniem, gromadzeniem i przesyłaniem informacji.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Skills: he can
M_U001 Umie stosować metody algebraiczne MAT2A_U10 Examination
M_U002 Umie stosować algebrę liniową MAT2A_U13 Examination
M_U003 Dostrzega obecność struktur algebraicznych w różnych zagadnieniach Examination
Knowledge: he knows and understands
M_W001 Zna głębiej elementy algebry MAT2A_W04 Examination
Number of hours for each form of classes:
Sum (hours)
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
30 30 0 0 0 0 0 0 0 0 0 0
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Skills
M_U001 Umie stosować metody algebraiczne + - - - - - - - - - -
M_U002 Umie stosować algebrę liniową + - - - - - - - - - -
M_U003 Dostrzega obecność struktur algebraicznych w różnych zagadnieniach + - - - - - - - - - -
Knowledge
M_W001 Zna głębiej elementy algebry + - - - - - - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 100 h
Module ECTS credits 4 ECTS
Udział w zajęciach dydaktycznych/praktyka 30 h
Realization of independently performed tasks 63 h
Examination or Final test 2 h
Contact hours 5 h
Module content
Lectures (30h):
Gromadzenie i przesyłanie informacji.

1. Kodowanie kontra szyfrowanie. Gromadzenie i przesyłanie informacji. System PESEL. Kod blokowy. Alfabet. Słowa informacyjne, słowa kodowe, błąd addytywny, słowo otrzymane. Kod powtarzający, kod parzysty. Długość kodu: n. Moc (liczność) kodu. Wymiar k kodu liniowego. Kod binarny. Założenia o kanale przesyłowym, błędy losowe. Niezawodność kanału. Binarny kanał symetryczny. Schemat transmisji z kodowaniem i dekodowaniem. Metryka Hamminga. Waga słowa. Dystans kodu. Sprawność R kodu blokowego. Kontrola parzystości i jej efektywność.
Dekodowanie wg największego prawdopodobieństwa (MLD). Dekodowanie pełne lub nie. Twierdzenia o wykrywaniu lub korygowaniu błędów.

2. Ciała Galois. Ciała reszt. Wielomiany nierozkładalne, ciała wielomianów. Przykłady rozszerzania ciał skończonych. Funkcja µ Möbiusa i zliczanie wielomianów nierozkładalnych.


3. Generowanie kodu liniowego. Ortogonalność słów. Kod dualny. Baza i macierz generująca. Liczba baz kodu liniowego. Elementarne przekształcenia wierszowe i algorytmy znajdowania bazy (macierzy generującej) kodu i/lub kodu dualnego. Macierz kontroli parzystości. Przykłady rachunkowe. Kodowanie za pomocą macierzy generującej. Kod liniowy systematyczny. Kody równoważne. Macierz kontroli parzystości determinuje dystans kodu liniowego.

4. Kod Hamminga binarny [n,k,d] z parametrami n = 2^r – 1 dla r > 2, k = n – r, d = 3. Kody sympleks. Ograniczenie Hamminga (ograniczenie dla upakowania kul). Kody doskonałe. Kody trywialne. Ograniczenie Singletona. Kody MDS. Ograniczenie Gilberta-Varshamova (Warszamowa). Ograniczenie Plotkina.

5. Warstwy kodu (translacje). Słownik kodu. Objaw (syndrom) warstwy. Dekodowanie: standardowa tablica dekodująca (SDA). Przykład: SDA dla kodu Hamminga.

6. Wydłużanie kodu. Kod Golaya jako przedziurawienie wydłużonego kodu Golaya. Samodualność.

7. Kody liniowe cykliczne. Wielomian generujący, jego charakteryzacja. Algorytm Euklidesa. Liczba kodów cyklicznych danej długości. Macierz kontroli parzystości kodu cyklicznego i wielomian generujący jego kod dualny.

8. Wielomiany idempotentne, Funkcja φ Eulera. Faktoryzacja dwumianu binarnego 1 + x^n, znajdowanie wszystkich kodów cyklicznych długości n. Element pierwotny ciała jako generator grupy multiplikatywnej tego ciała. Wielomian pierwotny stopnia m. Ciało Galois z mnożeniem modulo wielomian pierwotny. Ciało słów. Zliczanie wielomianów pierwotnych.

9. Wielomian minimalny elementu ciała. Kody BCH (Bose—Ray-Chaudhuri—Hocquenghem), w szczególności pierwotne i w wąskim sensie. Dystans projektowany i ograniczenie BCH. Kod Hamminga jako kod cykliczny BCH. Kody Reeda-Solomona.

10. Kody Hadamarda. Z_4 –liniowe wersje nieliniowych kodów Kerdocka i Preparata’y. Entropia i twierdzenia Shannona.

Additional information
Teaching methods and techniques:
  • Lectures: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Participation rules in classes:
  • Lectures:
    – Attendance is mandatory: No
    – Participation rules in classes: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
Method of calculating the final grade:
  1. Ocenę końcową OK wyznacza się na podstawie OKZal , oceny uzyskaną z kolokwium zaliczeniowego,
  2. Ocena końcowa OK. jest obliczana według algorytmu:
    Jeżeli OKZal ≥ 4.75, to OK = 5.0 (bdb),
    jeżeli 4.75 > OKZal ≥ 4.25, to OK = 4.5 (db),
    jeżeli 4.25 > OKZal ≥ 3.75, to OK = 4.0 (db),
    jeżeli 3.75 > OKZal ≥ 3.25, to OK = 3.5 (dst),
    jeżeli 3.25 > OKZal ≥ 3.00, to OK = 3.0 (dst).
Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:
  1. D.R. Hankerson et al. (7 co-authors), Coding Theory and Cryptography.
    The Essentials, Marcel Dekker
    , 2nd ed., New York and Basel, 2000.
  1. W.C.Huffman, V. Pless, Fundamentals of Error-Correcting Codes,
    Cambridge Univ. Press, 2003.
  1. G.A. Jones, J.M. Jones, Information and Coding Theory, Springer, 2002.
  1. F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes,
    North-Holland, 1977.
  1. R.M. Roth, Introduction to Coding Theory, Cambridge Univ. Press, 2006.
Scientific publications of module course instructors related to the topic of the module:

1. Skupień, Zdzisław; Majorization and the minimum number of dominating sets; Discrete Appl. Math. 165, 295-302 (2014).

2. Skupień, Zdzisław; Sums of powered characteristic roots count distance-independent circular sets; Discuss. Math., Graph Theory 33, No. 1, 217-229 (2013).

3. Fortuna, Artur; Skupień, Zdzisław; Universal third parts of any complete 2-graph and none of DK 5;
Opusc. Math. 33, No. 4, 685-696 (2013).

4. Euler, Reinhardt; Oleksik, Paweł; Skupień, Zdzisław;
Counting maximal distance-independent sets in grid graphs;
Discuss. Math., Graph Theory 33, No. 3, 531-557 (2013).

5. Meszka, Mariusz; Skupień, Zdzisław; Decompositions of a complete multidigraph into almost arbitrary paths; Discuss. Math., Graph Theory 32, No. 2, 357-372 (2012).

Additional information:

None