Coding for the Operator Channel
Author
Thomsen, Henning
Term
4. term
Education
Publication year
2012
Submitted on
2012-06-01
Pages
102
Abstract
Dette speciale undersøger, hvordan man kan overføre data pålideligt i netværk, hvor knuder blander datapakker som lineære kombinationer (tilfældig lineær netværkskodning). Vi bruger en kanalmodel kaldet operatorkanalen og fokuserer på underrumskoder, som repræsenterer information som underrum i et vektorrum. Først studerer vi Koetter–Kschischang (KK)-koder, der er modstykket til Reed–Solomon-koder i denne sammenhæng. Vi beskriver deres egenskaber og viser, at de asymptotisk nærmer sig Singleton-grænsen, som er en grundlæggende grænse for afvejningen mellem informationsmængde og fejlbeskyttelse. Vi undersøger også afkodningsalgoritmer for KK-koder. Dernæst behandler vi listeafkodning for underrumskoder, hvor afkoderen kan returnere en lille liste af mulige beskeder for at håndtere flere fejl. Vi præsenterer Mahdavifar–Vardy (MV)-koder og dokumenterer deres evne til listeafkodning samt korrektheden af afkodningsproceduren. Endelig viser vi, hvordan værktøjer fra abstrakt algebra, især modulteori, kan bruges til at analysere og udvikle afkodningsmetoder.
This thesis examines how to transmit data reliably in networks where nodes mix packets using random linear combinations (random linear network coding). We use a channel model known as the operator channel and focus on subspace codes, which represent information as subspaces of a vector space. First, we study Koetter–Kschischang (KK) codes, the counterpart of Reed–Solomon codes in this setting. We describe their properties and show that, as the code length grows, they approach the Singleton bound, a fundamental limit on the trade-off between information rate and error protection. We also examine decoding algorithms for KK codes. Next, we consider list decoding for subspace codes, where the decoder may return a small list of candidate messages to cope with more errors. We present Mahdavifar–Vardy (MV) codes and establish their list-decoding capabilities and the correctness of the decoding procedure. Finally, we explore how tools from abstract algebra, in particular module theory, can be used to analyze and design decoding methods.
[This abstract was generated with the help of AI]
Documents