February  2007, 1(1): 151-171. doi: 10.3934/amc.2007.1.151

The ubiquity of order domains for the construction of error control codes

1. 

Department of Mathematics and Computer Science, College of the Holy Cross, Worcester, MA 01610, United States

Received  June 2006 Revised  September 2006 Published  January 2007

Order domains are a class of commutative rings introduced by Høholdt, van Lint, and Pellikaan to simplify the theory of error control codes using ideas from algebraic geometry. The definition is largely motivated by the structures utilized in the Berlekamp-Massey-Sakata (BMS) decoding algorithm, with Feng-Rao majority voting for unknown syndromes, applied to one-point geometric Goppa codes constructed from curves. However, order domains are much more general, and O'Sullivan has shown that the BMS algorithm can be used to decode codes constructed from order domains by a suitable generalization of Goppa's construction for curves. In this article we will first discuss the connection between order domains and valuations on function fields over a finite field. Under some mild conditions, we will see that a general projective variety over a finite field has projective models which can be used to construct order domains and Goppa-type codes for which the BMS algorithm is applicable. We will then give a slightly different interpretation of Geil and Pellikaan's extrinsic characterization of order domains via the theory of Gröbner bases, and show that their results are related to the existence of toric deformations of varieties. To illustrate the potential usefulness of these observations, we present a series of new explicit examples of order domains associated to varieties with many rational points over finite fields: Hermitian hypersurfaces, Deligne-Lusztig varieties, Grassmannians, and flag varieties.
Citation: John B. Little. The ubiquity of order domains for the construction of error control codes. Advances in Mathematics of Communications, 2007, 1 (1) : 151-171. doi: 10.3934/amc.2007.1.151
[1]

Jean-Luc Chabert, Ai-Hua Fan, Youssef Fares. Minimal dynamical systems on a discrete valuation domain. Discrete & Continuous Dynamical Systems - A, 2009, 25 (3) : 777-795. doi: 10.3934/dcds.2009.25.777

[2]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889

[3]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83

[4]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149

[5]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[6]

Hancheng Guo, Jie Xiong. A second-order stochastic maximum principle for generalized mean-field singular control problem. Mathematical Control & Related Fields, 2018, 8 (2) : 451-473. doi: 10.3934/mcrf.2018018

[7]

Sanghoon Kwon, Seonhee Lim. Equidistribution with an error rate and Diophantine approximation over a local field of positive characteristic. Discrete & Continuous Dynamical Systems - A, 2018, 38 (1) : 169-186. doi: 10.3934/dcds.2018008

[8]

G. Caginalp, Emre Esenturk. Anisotropic phase field equations of arbitrary order. Discrete & Continuous Dynamical Systems - S, 2011, 4 (2) : 311-350. doi: 10.3934/dcdss.2011.4.311

[9]

Liping Zhang, Soon-Yi Wu, Shu-Cherng Fang. Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium problems. Journal of Industrial & Management Optimization, 2010, 6 (2) : 333-346. doi: 10.3934/jimo.2010.6.333

[10]

Jeremiah Birrell. A posteriori error bounds for two point boundary value problems: A green's function approach. Journal of Computational Dynamics, 2015, 2 (2) : 143-164. doi: 10.3934/jcd.2015001

[11]

Ahmad Ahmad Ali, Klaus Deckelnick, Michael Hinze. Error analysis for global minima of semilinear optimal control problems. Mathematical Control & Related Fields, 2018, 8 (1) : 195-215. doi: 10.3934/mcrf.2018009

[12]

Patrick Henning, Mario Ohlberger. Error control and adaptivity for heterogeneous multiscale approximations of nonlinear monotone problems. Discrete & Continuous Dynamical Systems - S, 2015, 8 (1) : 119-150. doi: 10.3934/dcdss.2015.8.119

[13]

Gilles Carbou, Stéphane Labbé, Emmanuel Trélat. Smooth control of nanowires by means of a magnetic field. Communications on Pure & Applied Analysis, 2009, 8 (3) : 871-879. doi: 10.3934/cpaa.2009.8.871

[14]

Michael Herty, Lorenzo Pareschi, Sonja Steffensen. Mean--field control and Riccati equations. Networks & Heterogeneous Media, 2015, 10 (3) : 699-715. doi: 10.3934/nhm.2015.10.699

[15]

Pierluigi Colli, Gianni Gilardi, Elisabetta Rocca, Jürgen Sprekels. Asymptotic analyses and error estimates for a Cahn-Hilliard type phase field system modelling tumor growth. Discrete & Continuous Dynamical Systems - S, 2017, 10 (1) : 37-54. doi: 10.3934/dcdss.2017002

[16]

Chuang Zheng. Inverse problems for the fourth order Schrödinger equation on a finite domain. Mathematical Control & Related Fields, 2015, 5 (1) : 177-189. doi: 10.3934/mcrf.2015.5.177

[17]

Yulin Zhao, Siming Zhu. Higher order Melnikov function for a quartic hamiltonian with cuspidal loop. Discrete & Continuous Dynamical Systems - A, 2002, 8 (4) : 995-1018. doi: 10.3934/dcds.2002.8.995

[18]

Giovanni Colombo, Thuy T. T. Le. Higher order discrete controllability and the approximation of the minimum time function. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4293-4322. doi: 10.3934/dcds.2015.35.4293

[19]

Ciro D’Apice, Umberto De Maio, Peter I. Kogut. Boundary velocity suboptimal control of incompressible flow in cylindrically perforated domain. Discrete & Continuous Dynamical Systems - B, 2009, 11 (2) : 283-314. doi: 10.3934/dcdsb.2009.11.283

[20]

Suoqin Jin, Fang-Xiang Wu, Xiufen Zou. Domain control of nonlinear networked systems and applications to complex disease networks. Discrete & Continuous Dynamical Systems - B, 2017, 22 (6) : 2169-2206. doi: 10.3934/dcdsb.2017091

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]