In English

EN2500 Informationsteori och källkodning 7,5 hp

Information Theory and Source Coding

Kursen behandlar principer för kodning av tal, ljud, video och grafik vid låg bithastighet. Källkodningsteknik, till exempel skalär- och vektorkvantisering, ortogonala transformer och linjär prediktion presenteras och deras verkningssätt analyseras teoretiskt. De teoretiska begränsningarna för källkodare diskuteras.

  • Utbildningsnivå

    Avancerad nivå

  • Kursnivå (A-D)

    D

  • Huvudområde

  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

VT13 för programstuderande

VT14 för programstuderande

Lärandemål

Att ge en förståelse för de teoretiska grunderna för källkodning.

Kursens huvudsakliga innehåll

Informationsteori av diskreta och kontinuerliga variabler: entropi, Krafts olikhet, relativ entropi, entropitakt, redundans, ömsesidig information, asymptotisk ekvipartition. Estimering av sannolikhetsfunktioner och täthetsfunktioner. Expectation Maximization-algoritmen. Principen om maximal entropi.

Ickedestruktiv kodning: icke-adaptiva koder: Shannon, Huffmann, aritmetiska koder. Universella och adaptiva koder: Ziv-Lempel-koder.

Rate-distortion-teori: rate-distortions-funktionen, Shannons undre gräns, rate-distortion av oberoende variabler, "reverse waterfilling", Blahuts algoritm.

Fin-kvantisering: kvantiering genom begränsning av upplösning och begränsning av entropi. Vektor- och skalärkvantisering. Tillämpad fin-kvantisering: mixture- och gitter-kvantisering, kompandering.

Kvantisering med låg datahastighet: Lloyds algoritm för begränsad upplösning och begränsad entropi. Strukturerad vektorkvantisering (trästruktur, multi-steg, "gain-shape", gitter). Snabba sökmetoder.

Transformer och filterbankar: baser och ramar. Fasta tranformer: DFT, DCT, MLT, Gabor-ramar, Balian-Lows sats. A-priori-adaption: Karhunen-Loeve, a-priori energikoncentrering. A-posteriori adaption: a-posteriori energikoncentrering, sökning efter bästa bas, "matching pursuit".

Linjär prediktion: återkopplad prediktion, brusformning, "analysis-by-synthesis", "spectral flatness", Kolmogorovs formel, redundans, framåt- och bakåt-prediktion.

Behörighet

För fristående kursstudent: 120 hp samt Engelska B eller motsvarande

Rekommenderade förkunskaper

EQ1220 Signalteori eller motsvarande kunskaper.

Litteratur

W.B. Kleijn, A basis for source coding, KTH-S3 (2004).

Examination

  • HEM1 - Hemuppgift, 1,5 hp, betygsskala: P, F
  • TEN1 - Tentamen, 6,0 hp, betygsskala: A, B, C, D, E, FX, F

Krav för slutbetyg

Skriftlig examen.
Hemuppgift.

Ges av

EES/Ljud- och bildbehandling

Kontaktperson

Markus Flierl

Examinator

Markus Flierl <mflierl@kth.se>

Versionsinformation

Kursplan giltig från och med VT09.
Examinationsinformation giltig från och med HT07.