Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria informacji i kodowania
Koordynator przedmiotu:
Andrzej Dąbrowski
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Telekomunikacja
Grupa przedmiotów:
Przedmioty techniczne - zaawansowane
Kod przedmiotu:
TIKO
Semestr nominalny:
3 / rok ak. 2018/2019
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
uczestnictwo w wykładach: 15 x 2h = 30h uczestnictwo w ćwiczeniach: 15h konsultacje związane z wykładem lub projektem: 10h przygotowanie do wykładów: 15h przygotowanie do ćwiczeń: 7h praca nad projektem: 30h zaliczenia projektów: 5h egzamin końcowy: 2h razem: 114h
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
2.5
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
1
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia15h
  • Laboratorium0h
  • Projekt15h
  • Lekcje komputerowe0h
Wymagania wstępne:
PTC (Podstawy Transmisji Cyfrowej) lub podobny na kursie I stopnia
Limit liczby studentów:
60
Cel przedmiotu:
Student zapoznaje się z pojęciami stosowanymi w teorii informacji, a także z wartościami granicznymi w bezstratnym i stratnym kodowaniu źródła i kodowaniu kanałowym. Uczestnik zajęć nabywa praktycznych umiejętności w zakresie technik kodowania bezstratnego (kod Huffmana, kodowanie arytmetyczne, metody słownikowe: LZ77, LZ78, LZW), kodowania stratnego (kwantyzacja skalarna i wektorowa), kodowania kanałowego (kody blokowe, cykliczne, splotowe, turbo-kody). Jest w stanie zastosować odpowiedni schemat kodowania w konkretnej sytuacji.
Treści kształcenia:
WYKŁADY: 1. Wykład wstępny. System telekomunikacyjny i jego komponenty. Zastosowanie teorii informacji w telekomunikacji. Kodowanie bezstratne i stratne. Rodzaje kodów. 2. System telekomunikacyjny w ujęciu teorii informacji. Pojęcie wiadomości i informacji. Miara informacji i jej jednostki. Źródło informacji, ich rodzaje (dyskretne/ciągłe, bez/z pamięcią) i modele. Pojęcie entropii źródła. 3. Kodowanie – rodzaje kodów, kody przedrostkowe. Twierdzenie Krafta-McMillana, twierdzenie Shannona o kodowaniu źródła. 4. Algorytmy kodowania bezstratnego. Kod Huffmana, kodowanie arytmetyczne, metody słownikowe: LZ77, LZ78, LZW. 5. Stratne kodowanie źródła informacji. Wartości graniczne dla kodowania stratnego: RDF (rate distortion function). Kwantyzator wektorowy jako asymptotycznie optymalny koder źródła. 6. Model informacyjny kanału. Kanały dyskretne i analogowe. Pojęcie informacji wzajemnej. Pojemność informacyjna kanału. Twierdzenie Shannona o pojemności informacyjnej kanału i jego interpretacja. 7. Kanał binarny jako szczególny przykład kanału. Model kanału z błędami. Algorytmy decyzyjne i ich klasyfikacja. Odległość Hamminga. 8. Wstęp do teorii kodów nadmiarowych: podstawowe parametry kodów, podział kodów, techniki FEC i ARQ 9. Blokowe kody liniowe: definicja kodu liniowego, macierze G i H, pojęcie syndromu, kody dualne, modyfikacje kodów - kody wydłużone i skrócone, możliwości kodów blokowych - granica Hamminga, Plotkina, Griesmera, Singletona i Gilberta-Varshamova, przykładowe kody blokowe: kody Hamminga, kody Reeda-Mullera. 10. Kody cykliczne: opis wielomianowy, wielomiany generacyjne, kodowanie systematyczne i niesystematyczne, realizacja układowa kodera i dekodera, kody CRC, cykliczne kody Hamminga. 11. Kody BCH i Reeda-Solomona: teoria ciała Galois, algorytm Berlekampa-Masseya. 12. Kody splotowe: podstawowe parametry, diagram stanu, wykres kratowy, pojęcie odległości swobodnej, kody rekursywne, kody katastroficzne, operacja wykluczania bitów, twardo-decyzyjny algorytm Viterbiego. 13. Algorytmy dekodowania miękkodecyzyjnego: definicja pojęcia miękka decyzja, dekoder o największej wiarygodności, algorytm GMD (generalized minimum distance) oraz algorytmy Chase`a dla kodów blokowych, miękkodecyzyjny algorytm Viterbiego oraz jego modyfikacja - alg. SOVA i algorytm BCJR dla kodów splotowych. 14. Turbo kody: podstawowa idea turbokodowania, kody łączone równolegle i szeregowo, turbokody splotowe i blokowe, możliwości korekcyjne turbokodów splotowych a wybór kodera splotowego i dobór układu przeplotu, dekodowanie iteracyjne, wpływ parametrów dekodera na zysk kodowy. 15. Kody LDPC: opis kodów, kody regularne i nieregularne, graf Tannera, różne metody dekodowania - większościowa, bit-flipping, message passing, belief propagation. ĆWICZENIA: Celem ćwiczeń jest praktyczne pokazanie omawianych podczas wykładów metod kodowania i dekodowania, np. kodowanie Huffmana, algorytmy Lempela-Ziva (LZ77, LZ78, LZW), wyliczanie tablicy syndromów, dekodowanie według alg. Viterbiego i SOVA, dekodowanie iteracyjne turbokodów. PROJEKT: Studenci przygotowują wystąpienia na wybrany temat związany z teorią informacji, kodowaniem bezstratnym lub realizacją kodowania nadmiarowego w praktycznych systemach transmisji danych.
Metody oceny:
Egzamin końcowy (EK): max. 70 pkt., projekt (P): max. 30 pkt. Do zaliczenia wymagane min. 30 pkt. z EK i 15 pkt. z P. Ocena końcowa: 51 - 60: 3 ; 61 - 70: 3,5 ; 71 - 80: 4 ; 81 - 90: 4,5 ; 91 - 100: 5 .
Egzamin:
tak
Literatura:
Sayood, Khalid „Kompresja danych – wprowadzenie”, Wydawnictwo RM, Warszawa, 2002 Haykin, Simon „Systemy telekomunikacyjne cz. 2”, WKiŁ, W-wa, 1998 Przelaskowski, Artur "Kompresja danych: podstawy, metody bezstratne, kodery obrazów”, Wydawnictwo BTC, 2005 Cover T., Thomas J. „Elements of Information Theory” 2nd ed., Wiley, 2006 Jones G., Jones J. “Information and Coding Theory”, Springer, 2000 Lin S., Costello D. „Error Control Coding”, Pearson Education, 2004 Moon T. K. „Error Correction Coding”, Wiley Interscience, 2000 Berrou, C. „Codes and Turbo Codes”, Springer, 2010 Biglieri, E. „Coding for Wireless Channels”, Springer, 2005 Sripimanwat, K. „Turbo Code Applications: a Journey from a Paper to realization”, Springer, 2005
Witryna www przedmiotu:
www.tele.pw.edu.pl/tiko
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka W1
Student, który zaliczy przedmiot, zna podstawy teorii informacji i kodowania bezstratnego.
Weryfikacja: analiza wyników egzaminu końcowego, ocena pracy na ćwiczeniach
Powiązane charakterystyki kierunkowe: K_W07, K_W09, K_W10
Powiązane charakterystyki obszarowe: I.P7S_WG
Charakterystyka W2
Student, który zaliczy przedmiot, zna teoretyczne ograniczenia szybkości transmisji.
Weryfikacja: analiza wyników egzaminu końcowego, ocena pracy na ćwiczeniach
Powiązane charakterystyki kierunkowe: K_W10, K_W07, K_W09
Powiązane charakterystyki obszarowe: I.P7S_WG
Charakterystyka W3
Student, który zaliczy przedmiot, umie porównać różne techniki ochrony danych przed błędami.
Weryfikacja: analiza wyników egzaminu końcowego, ocena pracy na ćwiczeniach
Powiązane charakterystyki kierunkowe: K_W07, K_W09, K_W10
Powiązane charakterystyki obszarowe: I.P7S_WG
Charakterystyka W4
Student, który zaliczy przedmiot, umie dobrać metodę kodowania korekcyjnego do rodzaju kanału i parametrów systemu transmisyjnego.
Weryfikacja: analiza wyników egzaminu końcowego, ocena pracy na ćwiczeniach
Powiązane charakterystyki kierunkowe: K_W07, K_W09, K_W10
Powiązane charakterystyki obszarowe: I.P7S_WG

Profil ogólnoakademicki - umiejętności

Charakterystyka U1
Student, który zaliczy przedmiot, potrafi zastosować wybraną bezstratną metodę kompresji dla prostego źródła wiadomości.
Weryfikacja: analiza wyników egzaminu końcowego, ocena pracy na ćwiczeniach
Powiązane charakterystyki kierunkowe: K_U06
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.1.o, III.P7S_UW.3.o
Charakterystyka U2
Student, który zaliczy przedmiot, potrafi znaleźć zakodowany ciąg wyjściowy dla dowolnego kodu blokowego i/lub splotowego.
Weryfikacja: analiza wyników egzaminu końcowego, ocena pracy na ćwiczeniach
Powiązane charakterystyki kierunkowe: K_U06, K_U13
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.1.o, III.P7S_UW.3.o
Charakterystyka U3
Student, który zaliczy przedmiot, na podstawie literatury w języku polskim i angielskim potrafi opracować ustalone zagadnienie, związane z teorią informacji i/lub kodowaniem.
Weryfikacja: ocena artykułu przygotowanego w ramach projektu
Powiązane charakterystyki kierunkowe: K_U01, K_U02, K_U06, K_U15
Powiązane charakterystyki obszarowe: I.P7S_UK, I.P7S_UW, III.P7S_UW.1.o, III.P7S_UW.3.o, I.P7S_UO, III.P7S_UW.2.o, III.P7S_UW.4.o

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka K1
Student, który zaliczy przedmiot, potrafi przekazać zdobytą wiedzę innym w formie krótkiej prezentacji ustnej.
Weryfikacja: ocena zaliczenia projektu w formie prezentacji ustnej
Powiązane charakterystyki kierunkowe: K_K02
Powiązane charakterystyki obszarowe: I.P7S_KK, I.P7S_KR