01405 Algebraiske Fejlrettende Koder

2024/2025

Kursusinformation
Algebraic Error-Correcting Codes
Engelsk
5
Kandidat
Kurset udbydes som enkeltfag
Retningsspecifikt kursus (MSc), Communication Technologies and System Design
Retningsspecifikt kursus (MSc), Mathematical Modelling and Computation
Teknologisk specialisering (MSc), Communication Technologies and System Design
Teknologisk specialisering (MSc), Mathematical Modelling and Computation
F4B (fre 8-12)
Campus Lyngby
Kurset består af forelæsninger, grupperegninger og projektarbejde i grupper.
13-uger
F4B
Mundtlig eksamen og bedømmelse af rapport(er)
Projekt(er) udføres i små grupper (2-3 studerende) med afsluttende rapport(er). Afsluttende, individuel mundtlig eksamen.
:

Karakteren for kurset vil være en helhedsvurdering ud fra projekter og den mundtlige eksamen.

7-trins skala , ekstern censur
01018 , Forståelse af grundbegreber fra algebra: lineær algebra, endelige legemer, kvotientringe, isomorfisætningen, polynomiumsringe. Lidt erfaring med programmering.
Maria Montanucci , Lyngby Campus, Bygning 303B, Tlf. (+45) 4525 3047 , marimo@dtu.dk
Peter Beelen , Lyngby Campus, Bygning 303B, Tlf. (+45) 4525 3022 , pabe@dtu.dk
01 Institut for Matematik og Computer Science
I studieplanlæggeren
Overordnede kursusmål
Dette er et matematik-kursus der udspringer fra ingeniør-anvendelsen Fejlrettende Koder. De faglige værktøjer vi beskæftiger os med er diskret matematik, algebra og algebra.

Fejlrettende Koder handler ikke om programmering men derimod om repræsentation af digital information således at det bliver robust overfor fejl. Disse bliver brugt overalt: fx på en BluRay der stadig kan spille selvom den har en ridse, eller sattelit-tv der stadig fungerer i stormvejr på trods af atmosfærisk støj, eller højhastigheds internet og mobiltelefoni. Det er ikke overdrevet at sige, at informationsalderen var umulig uden Fejlrettende Koder.

Mange af de bedste fejlrettende koder vi kender udspringer fra dybsindig algebra. Dette kursus er en introduktion til den fundamentale matematiske model i kodningsteori og til matematikken bag disse algebraiske koder. For at modtageren kan rette fejl der måtte opstå har han brug for effektive algoritmer til at jonglere med de algebraiske objekter; vi vil beskæftige os med både teoretisk algebra og med et computer-algebra system.

Kort sagt: vi vil bruge algebra og udvikle algebraiske værktøjer til at finde gode løsninger på matematiske problemstillinger, der er inspireret af anvendelser af Fejlrettende Koder.
Læringsmål
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
  • Forklare den matematiske model i fejlrettende koder og dens relevans i kommunikation.
  • Udlede, med en konstruktiv metode, at der eksisterer koder med gode parameter.
  • Give en (eksponentialtids) algoritme til maximum likelihood afkodning.
  • Definere Reed-Solomon koder ved hjælp af polynomier i én variabel og udlede deres grundlæggende parametre.
  • Bevise matematisk korrektheden af en afkodningsalgoritme for Reed-Solomon-koder, og forstå hvordan man implementerer denne i et computer-algebra system.
  • Definere hvorledes en transmission kan fejle og estimere sandsynligheden for disse hændelser i en simpel fejl-model.
  • Definere Reed-Muller koder ved hjælp af polynomier i flere variable og udlede deres grundlæggende parametre.
  • Bevise Bézout's sætning om skæringspunkter af algebraiske kurver, og forklare dens rolle i Algebraisk Geometri-koder.
  • Definere Algebraiske Geometri-koder ved hjælp af algebraiske kurver, udlede deres grundlæggende parametre, og beskrive en afkodningsalgoritme for dem.
  • Udføre et projekt om algebraiske koder og evaluer deres effektivitet.
  • Arbejde effektivt i en gruppe på et projekt med en matematisk og algoritmisk kerne.
  • Skrive en rapport om et emne i algebraiske fejlrettende koder.
Kursusindhold
Kurset forløber med forelæsninger og grupperegninger. Vi lægger ud med at introducere den matematiske model indenfor lineær algebra over endelige legemer, og vi undersøger de overordnede rammer indenfor den: Gilbert-Varshamov grænsen og eksponentialtids-afkodning. Dernæst introduceres væsentlige algebraiske koder, Reed-Solomon-koder, hvor univariate polynomier benyttes som algebraisk værktøj. Vi ser på en effektiv afkodningsalgoritme til disse koder, samt hvordan den kan implementeres i et computer-algebra-system. Dernæst generaliserer vi til Reed-Muller-koderne vha. multivariate polynomier. Dette motiverer brugen af algebraiske kurver som fører til Algebraiske-Geometri koder, hvor Bézouts sætning er et væsentligt værktøj til analyse.
Litteraturhenvisninger
Lærebog udarbejdet af forelæserne (elektronisk, gratis tilgængelig)
Bemærkninger
Se også Algebra-forskningsgruppens hjemmeside: http:/​/​algebra.compute.dtu.dk
Sidst opdateret
02. maj, 2024