Gröbner basis techniques for certain problems in coding and systems theory

 dc.contributor.advisor Fitzpatrick, Patrick dc.contributor.author O'Keeffe, Henry dc.date.accessioned 2012-12-18T17:39:18Z dc.date.available 2012-12-18T17:39:18Z dc.date.issued 2003-10 dc.date.submitted 2003 dc.description.abstract There is much common ground between the areas of coding theory and systems theory. Fitzpatrick has shown that a Göbner basis approach leads to efficient algorithms in the decoding of Reed-Solomon codes and in scalar interpolation and partial realization. This thesis simultaneously generalizes and simplifies that approach and presents applications to discrete-time modeling, multivariable interpolation and list decoding. Gröbner basis theory has come into its own in the context of software and algorithm development. By generalizing the concept of polynomial degree, term orders are provided for multivariable polynomial rings and free modules over polynomial rings. The orders are not, in general, unique and this adds, in no small way, to the power and flexibility of the technique. As well as being generating sets for ideals or modules, Gröbner bases always contain a element which is minimal with respect tot the corresponding term order. Central to this thesis is a general algorithm, valid for any term order, that produces a Gröbner basis for the solution module (or ideal) of elements satisfying a sequence of generalized congruences. These congruences, based on shifts and homomorphisms, are applicable to a wide variety of problems, including key equations and interpolations. At the core of the algorithm is an incremental step. Iterating this step lends a recursive/iterative character to the algorithm. As a consequence, not all of the input to the algorithm need be available from the start and different "paths" can be taken to reach the final solution. The existence of a suitable chain of modules satisfying the criteria of the incremental step is a prerequisite for applying the algorithm. en dc.description.status Not peer reviewed en dc.description.version Accepted Version en dc.format.mimetype application/pdf en dc.identifier.citation O'Keeffe, H. 2003. Gröbner basis techniques for certain problems in coding and systems theory. PhD Thesis, University College Cork. en dc.identifier.uri https://hdl.handle.net/10468/858 dc.language.iso en en dc.publisher University College Cork en dc.rights © 2003, Henry O'Keeffe en dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/ en dc.subject Systems theory en dc.subject Coding theory en dc.subject.lcsh Gröbner bases en dc.title Gröbner basis techniques for certain problems in coding and systems theory en dc.type Doctoral thesis en dc.type.qualificationlevel Doctoral en dc.type.qualificationname PhD (Science) en
Original bundle
Now showing 1 - 1 of 1
Name:
OKeeffeH_PhD2003.pdf
Size:
379.49 KB
Format: