Information Theory

Antal poäng: 4.0. Valfri för: D3, E3. Kursansvarig: Thomas Johansson. Prestationsbedömning: Tentamen (5 tim) är skriftlig och av problemlösningstyp.

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, Markovkällor. Universiell källkodning (Willems' algoritm), 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. Källkodning i en fleranvändarsituation (Slepian-Wolf), multiple-accesskanalen (additionskanalen, kollisionskanalen, Aloha, Capetanakis), broadcast-kanalen, reläkanalen, tvåvägskanaler.

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 autentisering.

Litteratur

Johannesson, R.: Informationsteori - grundvalen för (tele-)kommunikation. Studentlitteratur 1988 eller Johannesson, R.; Informationstheorie- Grundlage der (Tele-) Kommunikation, Addison-Wesley och Studentlitteratur, 1992.