Toric Surface Codes and Minkowski Sums
John B. Little, Hal Schenck · SIAM Journal on Discrete Mathematics · 2006
Toric codes are evaluation codes obtained from an integral convex polytope $P \subset {\mathbb R}^n$ and finite field ${\mathbb F}_q$. They are, in a sense, a natural extension of Reed–Solomon codes, and have been studied recently in [V. Diaz, C. Guevara, and M. Vath, Proceedings of Simu Summer Institute, 2001], [J. Hansen, Appl. Algebra Engrg. Comm. Comput., 13 (2002), pp. 289–300; Coding Theory, Cryptography and Related Areas (Guanajuato, 1998), Springer, Berlin, pp. 132–142], and [D. Joyner, Appl. Algebra Engrg. Comm. Comput., 15 (2004), pp. 63–79]. In this paper, we obtain upper and lower bounds on the minimum distance of a toric code constructed from a polygon $P \subset {\mathbb R}^2$ by examining Minkowski sum decompositions of subpolygons of P. Our results give a simple and unifying explanation of bounds in Hansen’s work and empirical results of Joyner; they also apply to previously unknown cases.