Kursplan för läsåret 2010/2011
(Genererad 2010-06-28.)
INFORMATIONSTEORIEIT080
Information Theory

Antal högskolepoäng: 7,5. Betygsskala: TH. Nivå: G2 (Grundnivå, fördjupad). Huvudområde: Teknik. Undervisningsspråk: Kursen kan komma att ges på engelska. Valfri för: C4, C4ks, D4, D4ks, E3, E3f, F4, F4ssr, MFOT1, MWIR1, Pi4, Pi4ssr. Kursansvarig: Univ.lektor Stefan Höst, stefan.host@it.lth.se, Inst för elektro- och informationsteknik. Förutsatta förkunskaper: FMS012 Matematisk statistik, allmän kurs. Prestationsbedömning: Tentamen (5 tim) är skriftlig och omfattar normalt fem uppgifter av problemtyp. Hemsida: http://www.eit.lth.se/course/eit080.

Syfte
Kursen skall förmedla kunskap om de grundläggande principerna för lagring och överföring av information och om Claude Shannons insikt att de binära symbolerna, representerade som nollor och ettor, kan tas till grund för all representation av information. Kursen ger en bredd och ett djup som gör att många av de idag förekommande metoderna samt en stor del av morgondagens kan förstås.

Mål

Kunskap och förståelse
För godkänd kurs skall studenten

Färdighet och förmåga
För godkänd kurs skall studenten

Värderingsförmåga och förhållningssätt
För godkänd kurs skall studenten

på egen hand kunna klassificera problemens svårighetsgrad i förhållande till den egna kunskapsnivån

Innehåll
Shannon gav 1948 en kvantitativ definition av information. Med denna definition kan vi ge gränser för antalet meddelanden som kan överföras eller lagras. Såväl perfekta som störda överförings- och minnesmedia behandlas. Vi behandlar först fallet med en källa och en mottagare. Teorin generaliseras därefter till en fleranvändarsituation i vilken vi har ett nätverk med flera källor och/eller mottagare.
Informationsteori – vad är det?

Informationsteorins grunder: Shannons informationsmått, Fanos lemma, data processing lemma.

Tre fundamentala kommunikationssatser: Typiska följder, källkodningssatsen, kanalkodningssatsen, starkt symmetriska och symmetriska kanaler, summakanaler, rate-distortion-satsen.

Källkodning: Prefixfri kodning och Krafts olikhet, Huffmankodning, Tunstallkodning. Universell källkodning (Willems’ algoritm, Ziv-Lempel-kodning), testalgoritmer.

Kanalkodning: Blockfelsannolikhet och avkodningskriterier (maximum a posteriori och maximum likelihood), Bhattacharyyas och Gallagers gränser, Gallagers version av kanalkodningssatsen, träd- och trelliskoder. Fleranvändarkommunikation.

Gausskanalen: Differentiell entropi, tidsdiskret Gausskanal, bandbegränsad Gausskanal, en fundamental gräns.

Kryptering: Grundläggande begrepp, några klassiska system, Shannons teori för sekretess, öppen nyckel-system, Simmons’ teori för autenticering.

Litteratur
* Johannesson R: Informationsteori – grundvalen för (tele-)kommunikation, Studentlitteratur 1988
* Cover T and Thomas J: Elements of Information Theory, 2nd Ed, Wiley, 2006.