New codes for the Berlekamp-Massey-Sakata algorithm

DOI10.1006/FFTA.2000.0283MaRDI QIDQ5941621zbMATH OpenOpenAlexFDO

Authors Michael E. O'Sullivan

Publication date 20 August 2001

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/ffta.2000.0283

zbMATH Keywords

algebraic geometry codesBerlekamp-Massey algorithmmonomial orderingsorder functionvaluation ring

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Decoding (94B35)

Review text

It is known that the key concept for generalizing the Berlekamp-Massey algorithm is the existence of an order function which is a map from a ring to the nonnegative integers that determines a filtration of the ring with one-dimensional quotients. In this paper, it is shown that an order function determines a unique valuation on the function field, which has a residue field equal to the base field. Further, the geometry of these valuations for several monomial orderings on a polynomial ring is discussed, and an ordering is constructed which does not correspond to any monomial ordering. The geometric description helps to define order functions on general surfaces and higher-dimensional varieties.

Recommendations

• Evaluation codes and plane valuations
• The key equation for codes from order domains
• Generalized Berlekamp-Massey decoding of algebraic-geometric codes up to half the Feng-Rao bound
• The correction capability of the Berlekamp-Massey-Sakata algorithm with majority voting
• On Berlekamp-Massey and Berlekamp-Massey-Sakata algorithms

Cites work

• Decoding of codes defined by a single point on a curve
• Extension of the Berlekamp-Massey algorithm to N dimensions
• scientific article; zbMATH DE number 4112737 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 1284423 (Why is no real title available?)
• scientific article; zbMATH DE number 3279238 (Why is no real title available?)
• On the theory of graded structures
• Reduction of Singularities of the Differential Equation Ady = Bdx
• The concept of Gröbner algebras
• The minimum distance of codes in an array coming from telescopic semigroups
• Valuations in Function Fields of Surfaces

Cited in

(15)

• On Berlekamp-Massey and Berlekamp-Massey-Sakata algorithms
• Skeleton simplicial evaluation codes
• Algebraic-geometry codes, one-point codes, and evaluation codes
• Evaluation codes defined by finite families of plane valuations at infinity
• Feng-Rao decoding of primary codes
• Reversely well-ordered valuations on rational function fields in two variables
• A fast parallel implementation of a Berlekamp-Massey algorithm for algebraic-geometric codes
• ON THE BERLEKAMP — MASSEY ALGORITHM AND ITS APPLICATION FOR DECODING ALGORITHMS
• Generalized Sudan’s List Decoding for Order Domain Codes
• The key equation for codes from order domains
• Algorithm 810: The SLEIGN2 Sturm-Liouville Code
• On the structure of order domains
• Evaluation codes and plane valuations
• The correction capability of the Berlekamp-Massey-Sakata algorithm with majority voting
• Improved evaluation codes defined by plane valuations

This page was built for publication: New codes for the Berlekamp-Massey-Sakata algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941621)