Grafbasert kodeteori

Studiepoeng, omfang

10

Studienivå (studiesyklus)

Bachelor og master

Undervisningssemester

Uregelmessig.

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.

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 https://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.

Hjelpemiddel til eksamen

Enkel kalkulator tillatt, i samsvar med modeller angitt i fakultetets regler

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.

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 studieveileder@ii.uib.no

Administrativt ansvarleg

Det matematisk-naturvitenskapelige fakultet v/ Institutt for informatikk har det administrative ansvaret for emnet og studieprogrammet.