Grafbasert kodeteori

Mål:

Kodar definerte på grafar gjer det mogleg i praksis å kommunisera påliteleg med nær optimale hastigheiter, definert av Shannon-grensa. Emnet 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.

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.