College Informatietheorie 1 (2005-2006)

Code:	5JJ40 of 5K020
Trimesters:	5JJ40: EIT, Verplicht (Verkort)  5K020: BIS, Verplicht CSE, Verplicht WSK, Verplicht
Studiepunten (ECTS):	5JJ40 (2,9) 3 SP  5K020 (4,3) 4 SP.
Docent:	Dr.ir. Tj.J. Tjalkens.
Inlichtingen:	Dr.ir. Tj.J. Tjalkens en Dr.ir. F.M.J. Willems .
Voorkennis:	Kansrekening en stochastische processen (2S610).
Studiemateriaal:	Het collegedictaat is beschikbaar in PDF formaat via deze link.  optionele boeken, (zie het collegedictaat voor een lijst) o.a.:  "Elements of Information Theory", T.M. Cover en J.A. Thomas, Wiley, New York, 1991.
Onderwijsvorm:	Hoorcollege; 3 u/week,  instructie 1 u/week.
Tentamenvorm:	Schriftelijk, een maal in de tentamenperiode volgend op het college en een herkansing.
College voortgang:	Hier vind je de wekelijkse voortgang van het college.
Oefenopgaven:	Tijdens het college worden oefenopgaven uitgereikt. De ingeleverde oplossingen worden  nagekeken en tijdens de instructie behandeld. De relevante oefenopgaven worden hier gegeven.  De oefenopgaven kunnen in groepjes van studenten gemaakt worden en volgens een tijdens het college aangegeven rooster ingeleverd worden.  Het "oefencijfer" is het gemiddelde cijfer van de oefenopgaven.   Het oefencijfer kan het tentamencijfer met maximaal 1.5 punt verhogen. Dit geldt enkel voor het  tentamen direkt volgend op het college. De score per student en het behaalde compensatiepunt vindt u op deze pagina.

Collegestof

5JJ40:

Dictaat hoofdstukken 1 t/m 8, behalve hoofdstuk 4.5.4.

5K020:

Alles van 5JJ40 plus hoofdstuk 9 te doen via zelfstudie.

Extra informatie:

Recente oefenexamens zijn in PDF formaat beschikbaar als oefenstof. In aparte documenten worden de antwoorden gegeven. 

Hier vind je nog extra informatie betreffende

• Een lijst van de meest belangrijke begrippen uit Informatietheorie 1. Ook in PDF formaat te downloaden.
• Een korte inleiding in de kansrekening. Ook in PDF formaat te downloaden.

Doel van het college:

Shannon introduceerde in zijn "A Mathematical Theory of Communication" de begrippen informatie, redundantie, entropie en capaciteit. Deze begrippen en Shannon's meest elementaire resultaten komen tijdens dit college uitgebreid aan de orde. De inzichten die zo overgedragen worden, zijn uitermate nuttig wanneer men moderne communicatie processen wil doorgronden.

Het college is zo opgezet dat in het eerste deel de fundamentele begrippen en resultaten uit Shannon's theorie worden gegeven en in het tweede deel de practische codes worden beschreven die de theoretische grenzen benaderen. Ook wordt via het voorbeeld van de cryptologie aangegeven dat de informatietheoretische begrippen op meer dan alleen communicatie situaties toepasbaar zijn.

Korte omschrijving van de inhoud:

broncodering:

basisbegrippen:

entropie, divergentie, divergentieongelijkheid, convexiteit en convexe functies. verzamelingen.

blok-blok codering:

broncoderingstheorema voor blok-blok codering, omkeerstelling voor blok-blok codering.

blok-stroom codering:

eenduidig decodeerbare codes, komma code, prefix code, Kraft ongelijkheid, Mc-Millan's stelling, broncoderingstheorema voor blok-stroom codering, Huffman codes.

stationaire bronnen:

entropie van stationaire bronnen, blok entropie, conditionele entropie, innovatie entropie, kettingregel voor entropie, eenduidige en niet eenduidige Markov bronnen.

rate-distorsie theorie:

distorsiematen, rate-distorsie functie, rate-distorsie stelling.

kanaalcodering:

basisbegrippen:

kanalen zonder geheugen, gemiddelde mutuele informatie, kanaalcapaciteit, equivocatie, de Fano ongelijkheid, het dataverwerkingstheorema, Markov relatie, Shannon's omkeerstelling voor kanaalcodering, convexiteit van de gemiddelde mutuele informatie.

berekening van kanaalcapaciteit:

Kuhn-Tucker theorema, eigenschappen bij capaciteit.

bereikbaarheid van capaciteit:

blokcodes, code-efficiëntie, stochastische codering, drempeldecodering, Hamming afstand en Hamming gewicht.

foutencorrectie:

MAP en ML decodeerregel, corrigeerbare foutenfractie, Hamming code, begrenzing volgens Hamming en Gilbert.

cryptologie:

basisbegrippen:

Substitutie- en transpositie ciphers, perfect secrecy, Key equivocation.

practische gevolgen:

de bijna "onbruikbaarheid" van perfect secrecy, unicity distance, het principe van Diffusion en Confusion.