Grafbasert kodeteori

Masteremne

Emnebeskrivelse

Mål og innhald

Mål:

Kodar definerte på grafar gjer det mogleg i praksis å kommunisera påliteleg med nær optimale hastigheiter, definert av Shannon-grensa. INF244 har som mål å læra studentane korleis slike kodar er utforma og analyserte, og om korleis ei tilnærming med bruk av grafar tillet effektiv og korrekt dekoding.

Innhald:

Emnet tek opp algoritmar som brukar meldingar sende på grafar, spesielt i samanhang med kodingsteori. Tema i emnet inkluderar grafteori, trelliskodar, Viterbi-algoritmen, og iterativ meldingsbasert dekoding på grafar. Vidare vil vi sjå på moderne kodar med ytelse nær Shannon-terskelen, inkludert turbokoder, polarkoder, LDPC-koder, og særleg «spatially coupled» kodar. «Spatially coupled» kodar er definerte på ein spesiell type grafar, og det er vist at desse kodane oppnår kapasiteten til ein binær minnefri kanal. Det same gjeld polarkoder som no er del av 5G-standarden.

Emnet vil diskutera metodar for å analysera bruk av slike kodar, inkludert EXIT-analyse, ensemble-analyse og feilgulv-analyse. Det vil óg bli diskutert korleis meldingar på grafar i samanhang med F4-additive kodar, og korleis ein bruker lokal komplementering på meldingar som vert sende på dynamiske grafar. Studentane skal skrive programvare for å realisera meldingsutvekslande algoritmar i ei rekke forskjellige kodeanvendingar.

 

 

Læringsutbyte

Studenten skal ved avslutta emne ha følgjande læringsutbyte definert i kunnskapar, ferdigheiter og generell kompetanse:

Kunnskap

Studenten

  • Er kjent med moderne grafbaserte kodar som beskrivne i emnet, og om korleis dei verkar på kommunikasjonskanalar
  • forstår korleis statistisk inferens verkar på grafbaserte system
  • forstår grensane for kommunikasjon som følgjar av Shannon sitt kanalteorem, og prinsippa for utforming av kodar med ytelse som nærmar seg Shannon-terskelen

 

Ferdigheiter

Studenten

  • kan vurdere ytelsen til ein gitt kode, med ein gitt dekodar, på ein gitt kanal og kan skriva programvare for å implementera algoritmar basert på utveksling av meldingar
  • kan skriva programvare for å generere pseudotilfeldig støy med ein gitt sannsynstetthet
  • kan manipulera statistisk informasjon og sannsynlegheiter, spesielt i samanhang med kodingsteori

 

Generell kompetanse

Studenten

  • er kjent med nye idear og innovasjonsprosesser,
  • kan utveksle meiningar med andre med relevant bakgrunn og delta i diskusjonar om utvikling av god praksis.

Studiepoeng, omfang

10

Studienivå (studiesyklus)

Bachelor og master

Undervisningssemester

Uregelmessig.
Krav til forkunnskapar
Ingen
Tilrådde forkunnskapar
INF240, MNF130, INF100, MAT121 er sterkt tilrådd. I tillegg er INF101, INF142 anbefalt.
Studiepoengsreduksjon
I243: 5 SP
Krav til studierett
For oppstart på emnet er det krav om ein studierett knytt til Det matematisk-naturvitskaplege fakultet www.uib.no/matnat/52646/opptak-ved-mn-fakultetet
Arbeids- og undervisningsformer

Undervisninga gjevast i form av førelesningar og gruppeøvingar

Førelesningar / 4 timar pr. veke

Førelesningar / 13 veker

Øvelser: 2 timer i uken

Obligatorisk undervisningsaktivitet

Godkjende obligatoriske oppgåver.

Obligatoriske aktiviteter er gyldige i to semester, det semesteret aktiviteten godkjennes samt det påfølgjande semesteret.

Vurderingsformer
Skriftleg eksamen eller Digital skriftleg eksamen (3 timar). Det er høve til å gi karakter på obligatoriske oppgåver som kan inngå i sluttkarakteren.
Karakterskala
Ved sensur vert karakterskalaen A-F nytta.
Vurderingssemester
Det er ordinær eksamen kvart semester. I semesteret utan undervisning er eksamen tidleg i semesteret.
Litteraturliste
Litteraturlista vil vere klar innan 01.06. for haustsemesteret og 01.12. for vårsemesteret.
Emneevaluering
Studentane skal evaluere undervisninga i tråd med UiB og instituttet sitt kvalitetssikringssystem.
Hjelpemiddel til eksamen
Enkel kalkulator tillatt, i samsvar med modeller angitt i fakultetets regler
Programansvarleg
Programstyret har ansvar for fagleg innhald og oppbygging av studiet og for kvaliteten på studieprogrammet og alle emna der.
Emneansvarleg
Emneansvarleg og administrativ kontaktperson finn du på Mitt UiB, kontakt eventuelt studierettleiar
Administrativt ansvarleg
Det matematisk-naturvitenskapelige fakultet v/ Institutt for informatikk har det administrative ansvaret for emnet og studieprogrammet.