Grafbasert kodeteori
Masteremne
- Studiepoeng
- 10
- Undervisningssemester
- Haust, Vår
- Emnekode
- INF244
- Talet på semester
- 1
- Undervisningsspråk
- Engelsk
- Ressursar
- Timeplan
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
Studienivå (studiesyklus)
Undervisningssemester
Krav til forkunnskapar
Tilrådde forkunnskapar
Studiepoengsreduksjon
Krav til studierett
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
Karakterskala
Vurderingssemester
Litteraturliste
Litteraturlista vil vere klar innan 01.07. for haustsemesteret og 01.12. for vårsemesteret.