Improved Bounds for Codes and Secret Sharing Schemes from Algebraic Curves

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2010

Author dc:creator

• Kirov, Radoslav M.

Contributors dc:contributor

• Duursma, Iwan M.
• Reznick, Bruce
• Schenck, Henry K.
• Blahut, Richard E.

• algebraic geometric codes
• error-correcting codes
• linear secret sharing schemes
• hermitian curve
• suzuki curve

Statement dc:rights

• Copyright 2010 Radoslav M. Kirov

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/16738

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/16738