MSRI-UP

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. 

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 m 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.

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.

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.

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 .

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.