Files in this item



application/pdfKirov_Radoslav.pdf (612kB)
(no description provided)PDF


Title:Improved Bounds for Codes and Secret Sharing Schemes from Algebraic Curves
Author(s):Kirov, Radoslav M.
Director of Research:Duursma, Iwan M.
Doctoral Committee Chair(s):Reznick, Bruce
Doctoral Committee Member(s):Duursma, Iwan M.; Schenck, Henry K.; Blahut, Richard E.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):algebraic geometric codes
error-correcting codes
linear secret sharing schemes
hermitian curve
suzuki curve
Abstract:The main goal of this work is to improve algebraic geometric/number theoretic constructions of error-correcting codes and secret sharing schemes. For both objects we define parameters that indicate their effectiveness in applications. We explore infeasibility bounds, showing that objects with relatively high parameters cannot exist. The best upper bounds in the theory of error-correcting codes arise from using linear programming on enumerator vectors. We show that similar linear programming techniques are applicable for obtaining infeasibility results for secret sharing schemes. In 1975, V. Goppa established a remarkable connection: function fields of algebraic curves can be used to construct a large class of error-correcting codes. Such codes are called algebraic geometric (AG) codes. AG codes from divisors supported in only one point on the Hermitian curve produce long codes with excellent parameters. Feng and Rao introduced a modified construction that improves the parameters while still using one-point divisors. Their construction is referred to as improved codes. A separate improvement of the parameters was introduced by Matthews; it uses the classical construction but with two-point divisors. We combine those two approaches to produce an infinite family of codes improving on all previously known families of Hermitian codes. The main topic of the thesis is the improvement of lower bounds for the parameters of error-correcting codes and secret sharing schemes using the geometry of divisors on curves. We recall some of the various methods that have been used to obtain improvements of the Goppa lower bound for the minimum distance of an algebraic geometric code. The most successful method is the order bound, which generalizes the Feng-Rao bound. We provide a significant extension of the bound that improves the order bounds by Beelen and by Duursma and Park. Finally, we address ways to efficiently compute the bounds.
Issue Date:2010-08-20
Rights Information:Copyright 2010 Radoslav M. Kirov
Date Available in IDEALS:2010-08-20
Date Deposited:2010-08

This item appears in the following Collection(s)

Item Statistics