Quasi-Cyclic Codes Represented by Gröbner Bases
Author
Skjærbæk, Thomas Hassing
Term
4. term
Education
Publication year
2010
Submitted on
2010-06-15
Pages
83
Abstract
This thesis develops an algebraic framework for representing and decoding quasi-cyclic codes using Gröbner bases for modules. It first generalizes Gröbner basis theory from ideals to submodules of polynomial modules by defining monomial orders on R^m, introducing a division algorithm, solving the Submodule Membership Problem, and computing generators of syzygy modules. It then reviews basic theory of linear and cyclic codes—viewing cyclic codes as ideals in a quotient ring—and shows that quasi-cyclic codes of length n = l·m can be represented as submodules of a suitable quotient module; based on this, it proves a theorem describing the structure of their Gröbner bases. The thesis further presents a decoding method for Reed–Solomon codes using module and Gröbner basis techniques, together with an algorithm to convert a Gröbner basis between monomial orders. Finally, it studies decoding of quasi-cyclic codes via their Gröbner basis representation: in the general multi-generator case the method can fail when a block contains too many errors, so the analysis focuses on 1‑generator quasi‑cyclic codes and then on a specific subclass for which a decoding algorithm is given; the algorithm is particularly effective when the received word has many erasures. Computations were carried out with the Singular computer algebra system.
Specialet udvikler en algebraisk ramme for at repræsentere og afkode quasi-cykliske koder ved hjælp af Gröbner baser for moduler. Først generaliseres Gröbner-baseteorien fra idealer til submoduler i polynomiumsmoduler, herunder definition af monomiale ordner på R^m, en divisionsalgoritme, løsning af submodul-medlemskabsproblemet og beregning af generatorer for syzygy-moduler. Dernæst gennemgås grundlæggende teori for lineære og cykliske koder, hvor cykliske koder beskrives som idealer i en kvotientring, og det vises, at quasi-cykliske koder af længde n = l·m kan repræsenteres som submoduler af et passende kvotientmodul; på den baggrund gives en strukturteori for deres Gröbner baser. Specialet præsenterer desuden en afkodningsmetode for Reed–Solomon-koder baseret på modul- og Gröbner-baser, samt en algoritme der konverterer en Gröbner basis mellem monomiale ordner. Afslutningsvis undersøges afkodning af quasi-cykliske koder via deres Gröbner-basis-repræsentation: den generelle metode kan fejle i fler-generator-tilfældet, hvis en blok har for mange fejl, hvorfor fokus indsnævres til 1-generator quasi-cykliske koder og videre til en specifik underklasse, for hvilken der gives en effektiv afkodningsalgoritme; algoritmen er særligt effektiv, når det modtagne ord indeholder mange sletninger. Beregninger er udført i computeralgebrasystemet Singular.
[This apstract has been generated with the help of AI directly from the project full text]