/ /

MSRI-UP 2009: Research Projects

MSRI-UP 2009: Coding Theory

Home Research Topic People Research Projects Pictures

View full reports (PDF, 1.5 MB)

Algebraic structure of (generalized) toric codes

Warren Chancellor, Morehouse College
Jonathon Henry, California State Polytechnic University, Pomona
Ellen Lê, Pomona College 

Building on the recent work surrounding toric codes, introduced in 2000 by J. Hansen, we further investigate the properties of this interesting class of error correcting cyclic codes. A toric code C is generated by creating monomials from a set of lattice points P in dimension m, and evaluating each of those monomials over all m-tuples of non-zero elements in a finite field of size q. Just as “ordinary” cyclic codes can be studied via properties of polynomials in one variable, we show that toric codes, which are m-dimensional cyclic codes, can be studied via m-variable polynomials. We aim in our work to generalize explicitly what the algebraic structure is for toric codes. In particular, we give formulas for finding the roots of (generalized) toric codes and their dual codes, and from these roots we derive a formula for an idempotent polynomial that generates the toric code.

A Systematic Census of Generalized Toric Codes over F4, F5 and F16

James Amaya, The College of New Jersey April
Harry, Xavier University of Louisiana
Brian Vega, California State Polytechnic University, Pomona 

Toric codes are a specific class of linear codes, originally introduced by J. Hansen. In this report, we study generalized toric codes, which are generated by a set of points in Z q−1. The orbits of these sets of points determine equivalent codes. In order to find and distinguish the codes for a given blocklength and dimension, we used various Magma processes to compute minimum distances and weight distributions of codes. There is an online table that contains much of the existing knowledge about the minimum distances of linear codes with certain dimensions at http://www.codetables.de. In our analysis of codes, we sought to find codes over F4 and F5 that would have minimum distances that exceed the lower bound listed in the online table, and thus would be the best known codes in existence for given parameters. In the process, we also noticed an interesting property about the average weights of words in toric codes and found codes from F5 and F16 that we believe to be interesting.

A census of two-dimensional toric codes over Galois fields of sizes 7, 8 and 9 

Alejandro Carbonara, California Institute of Technology
Juan Pablo Murillo, Sonoma State University
Abner Ortiz, University of Puerto Rico at Humacao

J. Hansen introduced toric codes using the geometry of polygons in R 2 and the convex polytopes P in R m more generally. But collections of points more general than the sets P ∩Z m can also be used to define generalized toric codes. In our research using the Magma computer algebra system, we search to find the generalized toric codes with the best parameters for some dimensions over the Galois fields of size 7, 8 and 9.

Indecomposable polyhedra and toric codes 

Aileen Gaudinez, Chapman University
Cheryl Outing, Spelman College
Rachel Vega, Concordia College

In this report we describe and classify indecomposable lattice polytopes in R 3 . This paper explores some indecomposable polyhedra not yet considered, and also introduces an idea of “family”. We investigate the toric codes over the Galois Field F8 that are constructed by these polyhedra, following the original method of constructing toric codes from polytopes by Hansen. In addition, we conjecture equivalence relations between the members of a determined family and subsequently the toric codes they generate.

Multivariate Vandermonde determinants and toric codes

Leyda Almodóvar, University of Puerto Rico at Mayagüez
Eugene Cody, Phoenix College
Lourdes Morales, University of Puerto Rico at Río Piedras

The minimum distances of toric codes has been studied extensively for various forms of polytopes. In [2], the authors determine bounds for the minimum distance of toric codes for some polytopes P ⊆ R m including the simplices of the form conv(0, `e1, . . . , `en) using Vandermonde determinants. In this paper, we will derive lower and upper bounds to prove the exact minimum distance of some toric codes associated to the special polytopes P = conv(0, `e1, 2`e2, 3`e3) ⊂ R 3 .

List Decoding algorithms for Reed-Solomon codes and their maximum decoding radii

Kimberly Heu, University of Hawaii at Manoa
Caitlyn Parmelee, Nazareth College of Rochester

Reed-Solomon codes are linear, cyclic codes that can be used to ensure that a correct message is received provided that there are at most a specific number of errors. One of the methods to deal with the decoding of received messages is the Guruswami-Sudan list decoding algorithm. This paper will present several of the properties of list decoding, including a detailed analysis of list decoding with lists of size one and the optimal benefits of list decoding.