Lineær Netværkskodning: Hvordan man løser et lineært netværkskodningsproblem med Gröbnerbaser

Vestergaard, Thomas

4. semester

Matematik, Kandidat

2012

2012-01-06

79

Specialet undersøger lineær netværkskodning og hvordan algebraiske metoder fra Gröbnerbasisteori kan anvendes til at analysere løselighed og succesrate i netværk, med udgangspunkt i artiklen “Aspects of random network coding” af H. Olav Geil og Casper Thomsen. Efter en introduktion til netværkskodning over endelige felter og repræsentationer via rettede grafer gennemgås centrale begreber i polynomielle ringe, monomielle ordninger og nøgleresultater som Dicksons lemma, Hilberts basissætning samt Buchbergers kriterium og algoritme. Disse værktøjer fører til Fodaftryksgrænsen, der giver et kriterium for, hvornår et lineært netværkskodningsproblem kan løses over et givent felt. Herefter beskrives lineær netværkskodning for multicast, hvordan man kan sikre høj sandsynlighed for, at alle modtagere rekonstruerer informationen ved vilkårlig (random) lineær kodning, og en algoritme præsenteres til at bestemme flows ud fra et givet flowsystem. Begreberne illustreres med beregninger i computeralgebrasystemet Singular og via Butterfly-netværket, og der diskuteres, hvad der yderligere kan siges om sandsynligheden for succes. Specialet er forklarende og samler forbindelsen mellem algebraiske metoder og netværkskodning frem for at præsentere nye empiriske resultater.

This thesis examines linear network coding and how algebraic methods from Gröbner basis theory can be used to analyze solvability and success probability in networks, based on the article “Aspects of random network coding” by H. Olav Geil and Casper Thomsen. After introducing network coding over finite fields and its representation via directed graphs, the thesis reviews key concepts in polynomial rings, monomial orderings, and core results such as Dickson’s Lemma, the Hilbert Basis Theorem, and Buchberger’s Criterion and Algorithm. These tools lead to the Footprint Bound, which provides a criterion for when a linear network coding problem over a given field is solvable. The work then treats linear network coding for multicast, explains how to ensure a high probability that all receivers recover the transmitted information using random linear coding, and presents an algorithm for determining flows from a given flow system. The ideas are illustrated with computations in the computer algebra system Singular and with the Butterfly network, and the probability of success is further discussed. The thesis is expository, clarifying the link between algebraic techniques and network coding rather than reporting new empirical findings.

[Dette resumé er genereret med hjælp fra AI direkte fra projektet (PDF)]

Download
Vis denne rapport i AAU Studenterprojekter