: Applications of Groebner Bases to Coding Theory
Translated title
Anvendelser af Groebner Baser til Kodningsteori
Author
Marchetti, Nicola
Term
4. term
Education
Publication year
2010
Pages
71
Abstract
Dette speciale undersøger, hvordan Groebner-baser – især for moduler – kan anvendes i kodningsteori. Efter en introduktion til polynomer, idealer, monomiale ordninger og polynomiel division behandles lineære og cykliske koder, herunder faktorisering af x^n − 1, begrebet nulpunkter og minimumsafstand samt BCH- og Reed–Solomon-koder. Med dette grundlag introduceres kvasi-cykliske koder og deres algebraiske teori, hvor Groebner-baser for moduler bruges til at beskrive deres struktur. Afkodningsaspekter diskuteres for kvasi-cykliske koder i Groebner-basis-form, for restriction-1 1-generator kvasi-cykliske koder samt gennem kendte afkodningsalgoritmer for Reed–Solomon-koder; endvidere behandles afkodning af kvasi-cykliske koder opbygget af RS-blokke. Arbejdet består primært af en re-elaboration af state-of-the-art med supplerende kommentarer, beviser og eksempler, og omfatter illustrative beregninger udført i computeralgebrasystemet Singular.
This thesis explores how Groebner bases—particularly for modules—can be applied in coding theory. After introducing polynomials, ideals, monomial orders, and polynomial division, it reviews linear and cyclic codes, including the factorization of x^n − 1, the notions of zeros and minimum distance, and BCH and Reed–Solomon codes. Building on this, it presents quasi-cyclic codes and their algebraic theory, using Groebner bases of modules to describe their structure. Decoding aspects are discussed for quasi-cyclic codes in Groebner basis form, for restriction-1 1-generator quasi-cyclic codes, and via standard decoding algorithms for Reed–Solomon codes; it also treats decoding of quasi-cyclic codes assembled from RS blocks. The work primarily re-elaborates state-of-the-art material with additional comments, proofs, and examples, and includes illustrative computations performed with the Singular computer algebra system.
[This summary has been generated with the help of AI directly from the project (PDF)]
Documents