On a key equation and error evaluation for codes from order domains

John B. Little Department of Mathematics and Computer Science, College of the Holy Cross, Worcester, MA 01610, USA E-mail: little@mathcs.holycross.edu

March 31, 2007

The Berlekamp-Massey decoding algorithm for a Reed-Solomon code can be phrased as a method for solving the key equation

fS ≡ g mod ⟨X^{2t}⟩.  (1)

Here S is the known univariate syndrome polynomial in X, and the error locator f and error evaluator g are unknown polynomials in X.

We identify an algebraic context for related key equations in the theory of Macaulay’s inverse systems, [7, 8], and develop an analog of (1) for codes from order domains ([4, 10, 3, 6]). We also relate O’Sullivan’s general version of the Berlkamp-Massey-Sakata (BMS) algorithm from [11] to the process of solving this equation. The key equation for n-dimensional cyclic codes studied by Chabanne and Norton, [2, 9], is a special case. Althaler and Dür, [1], consider a form of (1) from our point of view. This note is a summary of the results of [5] to which we refer for proofs.

Codes from order domains

A fundamental theorem of Geil and Pellikaan, [3], shows that order domains all have presentations as affine algebras R ≅ 𝔽_{q}[x_{1}, …, x_{s}]/I where I is an ideal generated by a Gröbner basis with a very specific form. We write X_{R} = V(I) for the corresponding algebraic variety. The value semigroup Γ and the weight function ρ : R → Γ are defined using a suitable monomial order. In this note, we will assume that Γ can be put into order-preserving one-to-one correspondence with ℤ_{≥0}. Such Γ are said to be Archimedean because it follows that for all nonconstant f ∈ R and all g ∈ R there is some n ≥ 1 such that ρ(f^{n}) ≻ ρ(g). Let Δ be the ordered “footprint” basis of R with ordering by ρ-value. Let ℓ ∈ ℕ and let V_{ℓ} be the span of the first ℓ elements of Δ. In this way, we obtain evaluation codes Ev_{ℓ} = ev(V_{ℓ}) defined on X_{R}(𝔽_{q}) and dual codes C_{ℓ} = Ev_{ℓ}^{⊥} for all ℓ.

Inverse systems

Let k be a field, let S = k[X_{1}, …, X_{s}] and let T be the formal power series ring k[[X_{1}^{−1}, …, X_{s}^{−1}]] in the inverse variables. T is an S-module under the contraction mapping c : (f, g) ↦ f · g defined as follows. First, given monomials X^{α} in S and X^{−β} in T, X^{α} · X^{−β} is defined to be X^{α−β} if this is in T, and 0 otherwise. We then extend by linearity to define c : S × T → T.

Let Hom_{k}(S, k) be the dual vector space, which is an S-module under qΛ(p) = Λ(qp) for p, q ∈ S. Hom_{k}(S, k) and T are isomorphic as S-modules via Λ ↔ ∑_{β∈ℤ_{≥0}^{s}} Λ(X^{β})X^{−β}; see [8] for more details.

For each ideal I ⊆ S, the annihilator, or inverse system, of I is

I^{⊥} = {Λ ∈ T : Λ(p) = 0, ∀ p ∈ I},

an S-submodule of T. Similarly, given an S-submodule H ⊆ T,

H^{⊥} = {p ∈ S : Λ(p) = 0, ∀ Λ ∈ H},

an ideal in S. The ideals of S and the S-submodules of T are in inclusionreversing bijective correspondence, and for all I, H we have (I^{⊥})^{⊥} = I and (H^{⊥})^{⊥} = H.

Theorem 1 If m_{P} is the maximal ideal of a point in affine space, then (m_{P})^{⊥} is generated by h_{P} = ∑_{u∈ℤ_{≥0}^{s}} P^{u}X^{−u}. For all f ∈ S, f ·h_{P} = f(P)h_{P}, and the submodule (m_{P})^{⊥} is a one-dimensional vector space over k. If I = m_{P_{1}} ∩ ⋯ ∩ m_{P_{ℓ}}, then I^{⊥} = ⊕(m_{P_{i}})^{⊥} is generated by ∑_{i} h_{P_{i}}.

Both S and T are subrings of K = k((X_{1}^{−1}, …, X_{s}^{−1})), the field of fractions of T. The full product fg for f ∈ S and g ∈ T is an element of K.

The contraction product f · g is a projection of fg into T ⊂ K. We can also consider the projection of fg into S_{+} = ⟨X_{1}, …, X_{s}⟩ ⊂ S ⊂ K. We will denote this by (fg)_{+}.

The key equation and the BMS algorithm

Let C_{ℓ} be a dual evaluation code from an order domain R. Consider an error vector e ∈ 𝔽_{q}^{n}. If E is the support of the error, then we define

I_{E} = {f ∈ 𝔽_{q}[X_{1}, …, X_{s}] : f(P) = 0, ∀P ∈ E}.

For each monomial X^{u} ∈ 𝔽_{q}[X_{1}, …, X_{s}], the error syndrome is

E_{u} = ⟨e, ev(X^{u})⟩ = ∑_{P ∈X_{R}(𝔽_{q})}e_{P} P^{u}.  (2)

Generalizing [2], we define the syndrome series

S_{e} = ∑_{u∈ℤ_{≥0}^{s}} E_{u}X^{−u} ∈ T = 𝔽_{q}[[X_{1}^{−1}, …, X_{s}^{−1}]] ≅ Hom_{𝔽_{q}}(S, 𝔽_{q}).

We substitute from (2) for the syndrome E_{u} and change the order of summation to obtain:

S_{e} = ∑_{u∈ℤ_{≥0}^{n}} E_{u}X^{−u} = ∑_{P ∈X_{R}(𝔽_{q})}e_{P} ∑_{u∈ℤ_{≥0}^{n}} P^{u}X^{−u} = ∑_{P ∈X_{R}(𝔽_{q})}e_{P} h_{P} , (3)

where h_{P} is the generator of (m_{P})^{⊥} from Theorem 1.

Theorem 2 For each e with supp(e) = E, I_{E} = ⟨S_{e}⟩^{⊥}.

In other words, f ∈ I_{E} if and only if f · S_{e} = 0 for all error vectors e with supp(e) = E. This result is a restatement of the standard fact that the error locators give recurrences on the syndromes. Let f = ∑_{m} f_{m}X^{m} ∈ S. Then

f · S_{e} = (∑_{m} f_{m}X^{m}) · ( ∑_{u∈ℤ_{≥0}^{s}} E_{u}X^{−u}) = ∑_{r∈ℤ_{≥0}^{s}}(∑_{m} f_{m}E_{m+r})X^{−r}.

Hence f · S_{e} = 0 ⇔ ∑_{m} f_{m}E_{m+r} = 0 for all r ≥ 0.

The equation f · S_{e} = 0 for f ∈ I_{E} will be called the general key equation. In [5] it is shown how this relates to known key equations for various classes of codes. Truncating S_{e}, we could obtain a congruence similar to (1) involving only known syndromes (see the discussion following (4) below). The way to obtain error evaluators in this situation is to consider the “purely positive parts” (fS_{e})_{+} for certain solutions f of our key equation.

To relate solutions of our key equation and the BMS algorithm, we refer to the “Basic Algorithm” from §3 of [11], in which all needed syndromes are assumed known and no stopping criteria are specified. The syndrome mapping is defined by Syn_{e}(f) = ∑_{P ∈E} e_{P} f(P) where f ∈ R. The proof of our Theorem 2 also shows f ∈ I_{E} ⇔ Syn_{e}(fg) = 0, ∀g ∈ R.

From Geil and Pellikaan’s presentation theorem, we have the ordered monomial basis Δ = {X^{α(j)} : j ∈ ℕ} of R. The V_{ℓ} = Span{X^{α(j)} : j ≤ ℓ} exhaust R, so for f ≠ 0 ∈ R, we may define o(f) = min{ℓ : f ∈ V_{ℓ}}. This induces a (nonstandard) semigroup operation on ℕ defined by i ⊕ j = k ⇔ o(X^{α(i)}X^{α(j)}) = k. Given f ∈ R, one defines

span(f) = min{ℓ : ∃g ∈ V_{ℓ} s.t. Syn_{e}(fg) ≠ 0}
fail(f) = o(f) ⊕ span(f),

so f ∈ I_{E} ⇔ span(f) = fail(f) = ∞.

The mth iteration of the BMS algorithm produces a collection of polynomials F_{m} satisfying fail(f) > m.

Theorem 3 With all notation as above, suppose f ∈ R satisfies o(f) = s, fail(f) > m. Then

f · S_{e} ≡ 0 mod W_{s,m},

where W_{s,m} = Span{X^{−α(j)} : s ⊕ j > m} ⊂ T.

The subspace W_{s,m} depends on s = o(f). In our situation, though, note that if s′ = max{o(f) : f ∈ F_{m}}, then Theorem 3 implies

f · S_{e} ≡ 0 mod W_{s′,m}  (4)

for all f = f_{m}(s) in F_{m}. Moreover, only finitely many terms from S_{e} enter into any one of these congruences, so (4) is, in effect, a sort of general analog of (1). Moreover, as is well-known, BMS produces a Gröbner basis for I_{E}.

In [5] it is shown that univariate error locators and evaluators can be produced as in [2]. Moreover, O’Sullivan has shown in [12] that, for codes from curves, the BMS algorithm can be slightly modified to compute more useful error locators and error evaluators simultaneously. We conjecture that the same is true in our general setting.

References

[1] J. Althaler and A. Dür, Finite linear recurring sequences and homogeneous ideals, Appl. Algebra. Engrg. Comm. Comput. 7 (1996), 377-390.

[2] H. Chabanne and G. Norton, The n-dimensional key equation and a decoding application, IEEE Trans. Inform Theory 40 (1994), 200-203.

[3] O. Geil and R. Pellikaan, On the Structure of Order Domains, Finite Fields Appl. 8 (2002), 369-396.

[4] T. Høholdt, R. Pellikaan, and J. van Lint, Algebraic Geometry Codes, in: Handbook of Coding Theory, W. Huffman and V. Pless, eds. (Elsevier, Amsterdam, 1998), 871-962.

[5] J. Little, A key equation and the computation of error values for codes from order domains, preprint, ArXiv: math.AC/0303299.

[6] J. Little, The Ubiquity of Order Domains for the Construction of Error Control Codes, Advances in Mathematics of Communications 1 (2007), 151-171.

[7] F.S. Macaulay, Algebraic Theory of Modular Systems, Cambridge Tracts in Mathematics and Mathematical Physics, v. 19, (Cambridge University Press, Cambridge, UK, 1916)

[8] D.G. Northcott, Injective envelopes and inverse polynomials, J. London Math. Soc. (2) 8 (1974), 290-296.

[9] G.H. Norton, On n-dimensional Sequences. I, II, J. Symbolic Comput. 20 (1995), 71-92, 769-770.

[10] M. O’Sullivan, New Codes for the Berlekamp-Massey-Sakata Algorithm, Finite Fields Appl. 7 (2001), 293-317.

[11] M. O’Sullivan, A Generalization of the Berlekamp-Massey-Sakata Algorithm, preprint, 2001.

[12] M. O’Sullivan, The key equation for one-point codes and efficient error evaluation, J. Pure Appl. Algebra 169 (2002), 295-320.