Manuscript submitted to
AIMS’ Journals
Volume X, Number 0X, XX 200X

doi:10.3934/xx.xx.xx.xx
pp. X–XX

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

arXiv:1206.5124v2 [cs.IT] 21 Oct 2015

Irene Márquez-Corbella
INRIA Paris-Rocquencourt, SECRET Project-Team
78153 Le Chesnay Cedex, France.

Edgar Martı́nez-Moro
Mathematics Institute (IMUVa), University of Valladolid, Castilla, Spain.
Vernon Wilson Chair, Eastern Kentucky University.

Emilio Suárez-Canedo
Departament d’Enginyeria de la Informació i de les Comunicacions.
Universitat Autònoma de Barcelona (UAB)

(Communicated by the associate editor name)
Abstract. This article aims to explore the bridge between the algebraic structure of a linear code and the complete decoding process. To this end, we associate a specific binomial ideal I+ (C) to an arbitrary linear code. The binomials
involved in the reduced Gröbner basis of such an ideal relative to a degreecompatible ordering induce a uniquely defined test-set for the code, and this
allows the description of a Hamming metric decoding procedure. Moreover,
the binomials involved in the Graver basis of I+ (C) provide a universal test-set
which turns out to be a set containing the set of codewords of minimal support
of the code.

1. Introduction. In this paper, we associate a binomial ideal I+ (C) to an arbitrary
linear code C over any finite field Fq . Several papers have been already devoted to
the idea of associating the structure of a polynomial ideal to a linear code and
thus, relate the reduction process on the first structure to the challenge of complete
decoding on the second one. See [5, 16] and the references therein. Unfortunately,
so far, this approach has not yet been applied succesfully to the non-binary case.
Recently, some of these techniques were also studied by Aliasgari et al. [1] for
non-binary group block codes, but the developed decoding algorithm was for the
G-norm and not for the Hamming metric, recall that the G-norm is equivalent to
the Hamming distance for q = 2, 3.
Therefore, the main achievement of this article has been to find the right structure
that allows us to perform a complete decoding method as a reduction procedure
for monomials in a polynomial ring. The decoding procedure presented here is
a complete decoding algorithm that is, the procedure always provides the closest
codeword to the received vector. Indeed we are ensured that it will retrieve the
2010 Mathematics Subject Classification. Primary: 94B05, 13P25; Secondary: 13P10.
Key words and phrases. Gröbner bases, Graver bases, Minimal support codewords.
The first two authors are partially supported by Spanish MICINN under project MTM200764704. The research of the first author is also supported by the FSMP postdoctoral program. The
second author is also supported under project MTM2010-21580-C02-02 by Spanish MINCINN.

1

2

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

original sent codeword if the number of errors is smaller or equal to the errorcorrecting capability of the code.
First, in Section 2 we prove that I+ (C) is finitely generated and the generators
are provided by a basis of C and the binomials attached to the additive table of
the base field Fq . Or equivalently, I+ (C) is generated by the binomials given by the
Fq -kernel of an explicit matrix. Note that this approach is a non-trivial extension of
that of [14] to solve linear integer programming problems with modulo arithmetic
conditions, that is, related with matrices over any ring of integers Zs .
Then, in Section 3, we show that a reduced Gröbner basis G of I+ (C) relative to
a degree-compatible ordering give us a complete decoding algorithm. The proposed
procedure has some resemblance with the two gradient descent decoding algorithms
known for binary codes [15, 2], note that both algorithms were unified in [6]. In
our method, the test-set of C is replaced by G and addition is substituted for the
reduction induced by G. However, the idea behind our algorithm can be stated
without the use of Gröbner basis theory as a step by step decoding [18] algorithm,
which is a classical but very useful technique.
Next, in Section 4 we discuss an alternative for the computation of G. A brief
description of this technique as well as a complexity estimation can be found here.
We can not expect that the algorithm runs in polynomial time since the complete
decoding algorithm for general linear codes is an NP-hard problem [4], even if
preprocessing is allowed (see [7]). However, the proposed algorithm is better suited
for our case than the standard Buchberger’s algorithm.
In Section 5, we consider the Graver basis associated to I+ (C) which turns out
to contain the set of codewords of minimal support of C. The interest of this set is
due to its relationship with the complete decoding problem and its applications in
cryptography.
Finally, in Section 6 we apply the above approach to other classes of codes such
as modular codes, codes defined over multiple alphabets or additive codes. The set
of codewords of minimal support for modular codes has already been discussed in
[16, 17] and in [1], where similar ideas are treated for a metric different from the
Hamming.

1.1. Preliminaries. We begin with an introduction of basic definitions and some
known results from coding theory over finite fields. By K, Z, Zs , Fq and F∗q , where
q is a prime power, we denote an arbitrary finite field, the ring of integers, the ring
of integers modulo s, any representation of a finite field with q elements, and the
multiplicative group of nonzero elements of Fq , respectively. For every finite field
Fq the multiplicative group F∗q of nonzero elements of Fq is cyclic. A generator of
the cyclic group F∗q is called a primitive element of Fq . Therefore, Fq consists of 0
and all powers from 1 to q − 1 of that primitive element (see for instance [19]).
An [n, k] linear code C over Fq is a k-dimensional subspace of Fnq . We define a
generator matrix of C to be a k × n matrix G whose row vectors span C, while a
parity check matrix of C is an (n − k) × n matrix H whose null space is C. We
denote by dH (·, ·) and wH (·) the Hamming distance and the Hamming weight on
Fnq , respectively. We write d for the minimum distance of a linear code C and this
is equal to its minimum weight. This
determines the error-correction

 parameter
,
where
⌊x⌋
is the largest integer at most
capability of C which is given by t = d−1
2
x.

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

3

Remark 1. Let t be the error-correction capability of an [n, k, d] code C over Fq .
Then, d = 2t + 1 if d is odd and d = 2t + 2 if d is even.
For a word x ∈ Fnq , its support, denoted by supp(x), is defined as the set of
nonzero coordinate positions, i.e., supp(x) = {i | xi 6= 0}.
The Voronoi region of a codeword c ∈ C, denoted by D(c), is defined as:

D(c) = y ∈ Fnq | dH (y, c) ≤ dH (y, c′ ) for all c′ ∈ C \ {c} .

The union of all Voronoi regions of C is equal to Fnq . However, some points of Fnq
may be contained in several regions. Moreover, note that the Voronoi region of the
all-zero codeword D(0) coincides with the set of coset leaders of C.
A test-set TC for C is a set of codewords such that for every word y ∈ Fnq , either
y lies in the Voronoi region D(0), or there exists an element t ∈ TC such that
wH (y − t) < wH (y).
Recall that the general principle of Gradient Descend Decoding algorithms (GDDA)
is to use a certain set of codewords TC (namely test-set, formally described above)
which has been precomputed and stored in memory in advance. Then the algorithm
can be accomplished by recursively inspecting the test-set for the existence of an
adequate element which is subtracted from the current vector. The following algorithm describes a gradient-like decoding algorithm for binary codes, this algorithm
(for the binary case) appears in [3].
The following version of the GDD algorithm allows to reduce the size of the
test-set for the q-ary case since once a vector is stored we can omit its multiples.
Algorithm 1: Gradient-like decoding
Data: The received word y ∈ Fnq
Result: A codeword c ∈ C that minimized the Hamming distance dH (c, y)
1 Set c = 0; while y ∈
/ D(0) do
2
Look for z ∈ TC such that wH (y − λz) < wH (y) with λ ∈ Fq ;
3
y ←− y − z;
4
c ←− c + z
5 end while
6 Return c = y
In order to achieve complete decoding over a linear code C the aim of this article
is to use a Gradient-like decoding method with the minimal test-set provided by a
reduced Gröbner basis G of the ideal associated to the code I+ (C) with respect to a
degree compatible ordering. As we will see, we do not need to store all the binomials
of such Gröbner basis but the codewords associated to the so-called minimal test-set.
A non-zero codeword m in C is said to be a minimal support codeword if there
are no other codewords c ∈ C such that supp(c) ⊂ supp(m). We denote by MC the
set of codewords of minimal support of C.
2. The ideal associated to a linear code. In this section we associate a binomial
ideal to an arbitrary linear code provided by the rows of a generator matrix and
the relations given by the additive table of the defining field.
Let X denote n vector variables X1 , . . . , Xn such that each variable Xi can be
decomposed into q − 1 components xi,1 , . . . , xi,q−1 with i = 1, . . . , n. A monomial
in X is a product of the form:

4

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

un,1
un,q−1 
u1,1
u1,q−1 
,
· · · xn,1
· · · xn,q−1
Xu = X1u1 · · · Xnun = x1,1
· · · x1,q−1
{z
} |
{z
}
|
un
Xn

u

X1 1

P
Pq−1
n(q−1)
where u ∈ Z≥0
. The total degree of Xu is the sum deg(Xu ) = ni=1 j=1
ui,j .
When u = (0, . . . , 0), note that Xu = 1. Then the polynomial ring K[X] is the set
of all polynomials in X with coefficients in K.
Let α be a primitive element of Fq . We define by RXi the set of all the binomials
on the variable Xi associated to the relations given by the additive table of the field
Fq = αj | j = 1, . . . , q − 1 ∪ {0}, i.e.,

S
{xi,u xi,v − 1 | αu + αv = 0} ,
RXi = {xi,u xi,v − xi,w | αu + αv = αw }

with i = 1, . . . , n. There are 2q different binomials in RXi .
We define RX as the following binomial ideal in K[X]: RX = h∪ni=1 RXi i.
We will use the following characteristic crossing functions. These applications
aim at describing a one-to-one correspondence between the finite field Fq with q
elements and the standard basis of Zq−1 , denoted as Eq = {e1 , . . . , eq−1 } where ei
is the unit vector with a 1 in the i-th coordinate and 0’s elsewhere.
∆:

Fq

−→ Eq ∪ {0} ⊆ Zq−1

and

∇ : Eq ∪ {0} −→ Fq

i

1. The map ∆ replaces the element a = α ∈ Fq by the vector ei and 0 ∈ Fq by
the zero vector 0 ∈ Zq−1 .
2. The map ∇ recovers the element αj ∈ Fq from the unit vector ej and the zero
element 0 ∈ Fq from the zero vector 0 ∈ Zq−1 .
These maps will be used with matrices and vectors acting coordinate-wise. Although ∆ is not a linear function. Note that we have
X∆a · X∆b = X∆a+∆b = X∆(a+b) mod RX for all a, b ∈ Fnq .
That is, the characteristic crossing functions induce the following maps:
˜ : Fnq
∆
a

∆

n

−→ (Eq ∪ {0})
7−→
∆a

−→ K[X]/RX
7−→
X∆a

and
˜ : K[X]/RX
∇
Xu

−→
7−→

(Eq ∪ {0})n
u

∇

−→ K[X]
7−→ ∇u

Remark 2. Take into account that Fq contains φ (q − 1) primitive elements, where
φ is the Euler function (or equivalently, the number of integers less than and relative
prime to q − 1). Every primitive element of Fq can serve as a defining element of
the characteristic crossing functions. But they will lead to different permutations
of the components of the vector variable Xi .
Definition 2.1. The monomial Xa is said to be in standard form if the exponents
of each variable xi,j is 0 or 1, and two variables xi,j and xi,l do not appear in the
same
Qn monomial. Therefore, a monomial is in standard form if it can be written as
i=1 xi,ji . Note that, any monomial modulo the additive relations {RXi }i=1,...,n is
in standard form. Or equivalently, Xa is in standard form if and only if there exists
b ∈ Fnq such that Xa = X∆b .

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

5

Moreover, if we multiply standard monomials with disjoint support then, ∆ provides linearity in K[X], i.e. :
X∆a X∆b = X∆(a+b) if supp(a) ∩ supp(b) = ∅
A polynomial f ∈ K[X] is said to be in standard form if each monomial in its
decomposition is in standard form.
Remark 3. The following property is crucial for the results achieved in this article:
If Xa is in standard form, then deg(Xa ) = wH (∇a).
Unless otherwise stated, we simply write C for an [n, k] linear code defined over
the finite field Fq . We define the ideal associated to C as the binomial ideal:

I(C) = X∆a − X∆b | a − b ∈ C ⊆ K[X].

For a fuller discussion of this algebraic structure see [6, 5, 16] and the references
therein.
Given the rows of a generator matrix of C, labelled by {w1 , . . . , wk } ⊆ Fnq , we
define the following ideal:
I+ (C) =

 n

j

X∆(α

wi )

−1

o

S

i=1,...,k
j=1,...,q−1



{RXi }i=1,...,n

⊆ K[X].

Remark 4. Note that we encode all the information of our ideal in the exponents,
thus we can always take K = F2 .
Lemma 2.2. Let f (X) ∈ K[X]. Then,
f (X) ∈ RX


P
f (X) = i∈I X∆ai X∆bi − X∆ci
with ai + bi − ci = 0 in Fnq , ∀i ∈ I

if and only if

Proof. Let f (X) ∈ RX . Thus, f (X) can be written as a finite linear combination
of elements in the set of generators of RX with coefficients in K = F2 , i.e.
f (X) =

n X
X

rjl

j=1 l∈Lj

where {rjl | l ∈ Lj } is a subset of generators of RXj for all j = 1, . . . , n. Following
the definition of RXj , the binomials rjl can take two different forms:
1. rjl = xju xjv − xjw with αu + αv = αw in Fq . Or equivalently,
u

v

w

u

rjl = Xj∆α Xj∆α − Xj∆α = X∆α

ej

v

X∆α

ej

w

− X∆α

ej

2. rjl = xju xjv − 1 with αu + αv = 0 in Fq . Or equivalently,
u

v

u

v

rjl = Xj∆α Xj∆α − 1 = X∆α ej X∆α ej − 1
P
Hence, f (X) = i∈I X∆ai X∆bi −X∆ci with ai +bi −ci = αu ei +αv ei −αw ei = 0
in Fnq for certain indices u, v, w, where {e1 , . . . , en } denotes the standard basis of
Fnq .
To show the converse it suffices to show that each binomial X∆aj X∆bj − X∆cj
in the decomposition of f (X) belongs to RX with
aj +bj −cj = (aj,1 , . . . , aj,n )+(bj,1 , . . . , bj,n )−(cj,1 , . . . , cj,n ) = 0 in Fnq for all j ∈ I

6

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

We have that:
X∆aj X∆bj − X∆cj

n
Y

=

∆aj,i

Xi

∆bj,i

Xi

i=1

=



∆a
∆b
X1 j,1 X1 j,1

−

{z

|

∆c
X1 j,1

n
Y

∆cj,i

Xi

i=1

∆a
∆b
Xi j,i Xi j,i

+

∆c
X1 j,1

} i=2

RX1

=

n
Y

−

n
Y

∆a
∆b
Xi j,i Xi j,i

−

n
Y

∆c
Xi j,i

i=2

i=2

n

Y
∆a
∆b
∆c
∆a
∆b
· · · = X1 j,1 X1 j,1 − X1 j,1
Xi j,i Xi j,i
|
{z
} i=2
RX1

+



∆aj,2

X2

∆bj,2

X2

|

∆cj,2

− X1

{z



n
Y

∆cj,1

X1

RX2

∆aj,i

Xi

∆bj,i

Xi

i=3

}


 n−1
Y ∆c
∆c
∆b
∆a
Xi j,i
+ . . . + Xn j,n Xn j,n − Xn j,n
{z
} i=1
|
RXn

Thus, X∆aj X∆bj − X∆cj ∈ RX for all j ∈ I.
Theorem 2.3. I(C) = I+ (C).

Proof. It is clear that I+ (C) ⊆ I(C) since all binomials in the generating set of I+ (C)
belong to I(C). Indeed:
j

• X∆α wi − 1 ∈ I(C) since αj wi ∈ C for all i = 1, . . . , k and j = 1, . . . , q − 1.
• The set of binomials of RXi are elements of I(C) for all i = 1, . . . , n since each
binomial represents the zero codeword by Lemma 2.2.
To show the converse it suffices to show that each binomial X∆a − X∆b of I(C)
belongs to I+ (C). By the definition of I(C) we have that a − b ∈ C. Hence
a − b = λ1 w1 + · · · + λk wk with λ1 , . . . , λk ∈ Fq .
Note that, if the binomials z1 −1 and z2 −1 belong to the ideal I+ (C) then z1 z2 −1 =
(z1 − 1)z2 + (z2 − 1) also belongs to I+ (C). On account of the previous line, we
have:
!
k
k
Y
Y
∆λi wi
∆λi wi
∆(a−b)
∆λ1 w1
−1
mod RX
X
+
X
−1
X
−1 = X
i=2

i=2



=

X∆λ1 w1 − 1

+

∆λk−1 wk−1

X

k
Y

X∆λi wi + X∆λ2 w2 − 1

X∆λi wi + · · · +

i=3

i=2



k
Y

∆λk wk

−1 X

The last equation forces that
 n
o
j
X∆α wi − 1
X∆(a−b) − 1 ∈

∆λk wk

+ X

i=1,...,k
j=1,...,q−1

−1



∪ RX

We have actually proved that X∆a − X∆b ∈ I+ (C) since


X∆a − X∆b = X∆(a−b) − 1 X∆b mod RX ,

mod RX .


.

!

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

7

which completes the proof.
Example 1. Let us consider the [7, 2] linear code C over F3 with generator matrix


1 0 1 2 1 1 1
G=
∈ F2×7
,
3
0 1 2 2 1 0 2

where the primitive element α = 2 generates the finite field F3 = 0, α = 2, α2 = 1
which gives us the following additive table:
α
α2
0

T+
α
α2

α2
0
α


α + α = α2 , α2 + α = 0, α2 + α2 = α . Therefore, we obOr equivalently,
tain the following binomials associated to the previous rules:

with i = 1, . . . , 7.
RXi = x2i,1 − xi,2 , xi,1 xi,2 − 1, x2i,2 − xi,1

Let us label the rows of G by w1 and w2 . By Theorem 2.3, the ideal associated to
the linear code C may be defined as the following binomial ideal:
o
D n
E
j
i=1,2 S
I+ (C) =
X∆α wi − 1 j=1,2
{RXi }i=1,...,7


x1,2 x3,2 x4,1 x5,2 x6,2 x7,2 − 1, 
+
* 


 S

x1,1 x3,1 x4,2 x5,1 x6,1 x7,1 − 1,
.
{RXi }i=1,...,7
=
x2,2 x3,1 x4,1 x5,2 x7,1 − 1, 





x2,1 x3,2 x4,2 x5,1 x7,2 − 1

Remark 5. Let B ∈ Fm×n
be a matrix, B ⊥ be the matrix whose rows generate
q
the null-space of B and {w1 , . . . , wk } be a set of generators of the row space of the
matrix B. We can define the following binomial ideal:

I(B) = X∆a − X∆b | B ⊥ (a − b)T = 0 .

Therefore, the construction presented above for linear codes can be generalized for
any matrix defined over an arbitrary finite field, i.e. we have actually proved that
I(B) = I+ (C) = I(C). Thus, the definition of I+ (C) is in fact independent of the
choice of the matrix B and just depends on the subspace C, i.e. the subspace
generated by the row-vectors of B.

Let B be a m × n matrix defined over Fq and let Bi denote the i-th column
of the matrix B. Let X denote n vector variables X1 , . . . , Xn such that Xi =
(xi,1 , . . . , xi,q−1 ) for 1 ≤ i ≤ n and Y denote m vector variables Y1 , . . . , Ym such
that Yj = (yj,1 , . . . , yj,q−1 ) for 1 ≤ j ≤ m. Let RYj ⊆ K[Yj ] be the binomial ideal
consisting of all the binomials on the variables Yj = (yj,1 , . . . , yj,q−1 ) associated to
the relations given by the additive table of the field Fq = αj | j = 1, . . . , q − 1 ∪{0}
with 1 ≤ j ≤ m, we define RY = h∪m
i=1 RYi i ⊆ K[Y].
We denote by K[X, Y]STD the set of polynomials in K[X, Y] in standard form,
i.e. f ∈ K[X, Y]STD if each monomial in its decomposition is in standard form.
The ring homomorphism
ΘB : K[X, Y]STD
T

−→ K[Y]

is then defined by ΘB (X∆a ) = Y∆(aB ) for every a ∈ Fnq , and ΘB (Y∆a ) = Y∆a .
j
j
j T
Thus, ΘB (xi,j ) = ΘB (Xi∆α ) = ΘB (X∆(α ei ) ) = Y∆(α Bi ) where {e1 , . . . , en }
n
denotes the standard basis of Fq .

8

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

P
More generally, for every polynomial f =
cv X∆vx Y∆vy ∈ K[X, Y]STD we
have that
X

ΘB (f ) = f (ΘB (X), Y) =
cv ΘB X∆vx Y∆vy

This function can be found in [9].

Remark 6. Note that the restriction of ΘB to RX is the function defined by:
ΘB : RX

−→ RY

This assertion is a direct consequence of Lemma 2.2.
Lemma 2.4. Let us consider the matrix B ∈ Fm×n
and the vectors a ∈ Fnq and
q

m
T
b ∈ Fq . The equality aB = b holds if and only if ΘB X∆a ≡ Y∆b mod RY .
Proof. This lemma is a straightforward consequence of Lemma 2.2.

Another ideal associated to the matrix B ∈ Fm×n
is defined by
q
D
E
S 
RYj j=1,...,m ⊆ K[X, Y].
IB = {ΘB (xi,j ) − xi,j } i=1,...,n
j=1,...,q−1

Lemma 2.5. For a given polynomial f ∈ K[X, Y]STD .
f ∈ IB

ΘB (f ) ≡ 0

if and only if

mod RY .


q

Proof. For each j = 1, . . . , m we have 2 different binomials in RYj . We denote
by rj,l (Yj ) the polynomial at position l with respect to certain order in RYj with
j = 1, . . . , m.
Let f ∈ IB , by representing f with the generators of IB , we have that
q−1
n X
X

f (X, Y) =

λi,j (ΘB (xi,j ) − xi,j ) +

{λi,j }

i=1,...,n
j=1,...,q−1

and

βj,l rj,l (Yj )

j=1 l=1

i=1 j=1

with

(q2)
m X
X

{βj,l } j=1,...,m
l=1,...,(q2)

∈ K[X, Y].

Then,
ΘB (f ) =
=

f (ΘB (X), Y)
q−1
n X
X

ΘB (λi,j ) (ΘB (xi,j ) − ΘB (xi,j )) +

=

ΘB (βj,l )rj,l (Yj )

j=1 l=1

i=1 j=1

(q2)
m X
X

(q2)
m X
X

ΘB (βj,l )rj,l (Yj ) ≡ 0

mod RY .

j=1 l=1

To prove the converse, first note that given any vector a = (a1 , . . . , an ) =
(αj1 , . . . , αjn ) ∈ Fnq the monomial X∆a can be written as:
X1∆a1

· · · Xn∆an

=
=

x1,j1 · · · xn,jn =
n
Y

ΘB (xi,ji ) +

i=1

=

n
Y

ΘB (X∆a ) +

i=1
n
X

(ΘB (xi,ji ) + (xi,ji − ΘB (xi,ji )))
Ci,j (xi,ji − ΘB (xi,ji ))

i=1

n
X
i=1

Ci,j (xi,ji − ΘB (xi,ji ))

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

for some {Ci,j }

i=1,...,n
j=1,...,q−1

9

∈ K[X, Y]. Note that, for all polynomial f ∈ K[X, Y]STD

there exists polynomials gi (Y), h(Y) ∈ K[Y]STD and fi (X) ∈ K[X]STD such that
X
f (X, Y) =
fi (X)gi (Y) + h(Y)
i∈I

We have already show that we can write each fi (X) as fi (ΘB (X))+ fˆi with fˆi ∈ IB .
Thus,
X
X
fˆi gi (Y) ∈ IB
f (X, Y) =
fi (ΘB (X))gi (Y) + h(Y) +
i∈I

i∈I

|

{z

=ΘB (f )∈RY

}

|

{z

∈IB

}

Remark 7. Lemmas 2.5 and 2.4 are technical findings valid for any matrix B. On
the following theorem we applied the above lemmas to a matrix A⊥ where A is a
generator matrix of the linear code C.
Let us recall a well-known property of binomials ideals:
Corollary 1. [10, Corollary 1.3] If I ⊆ K[X1 , . . . , Xn ] is a binomial ideal, then the
elimination ideal I ∩ K[X1 , . . . , Xr ] is a binomial ideal for every r ≤ n.
The following result shows how the ideal associated to the code C can also be
defined as the ideal associated to a parity check matrix of C and also as the kernel of a
polynomial ring homomorphism. Note that the ideals I(A) and IA are independent
of the matrix A, they just depend on the subspace generated by the row-vectors of
matrix A.
Theorem 2.6. I+ (C) = I(A) = IA⊥ ∩ K[X].
Proof. To prove that I+ (C) ⊆ IA⊥ ∩ K[X] it suffices to observe the following:


j
j
⊥ T
• ΘA⊥ X∆(α wi ) − 1 = Y∆(α wi )(A ) −1 is the zero binomial, since A·A⊥ =

0, for j ∈ {1, . . . , q − 1} and i ∈ {1, . . . k}.
• By Remark 6 we have that ΘA⊥ (RX ) ⊆ RY .
Therefore, applying Lemma 2.5 we conclude that the set of generators of I+ (C)
belongs to IA⊥ ∩ K[X].
Conversely, let f = X∆a − X∆b be any binomial of IA⊥ ∩ K[X] with a, b ∈ Fnq .
Note that Corollary 1 allows us taking f as a binomial. Lemma 2.5 implies that
⊥ T T
⊥ T T
ΘA⊥ (f ) = Y∆(A a ) − Y∆(A b ) ≡ 0 mod RY . Hence, by Lemma 2.4 we have
⊥ T
⊥ T
that A a = A b , thus by Theorem 2.3 f ∈ I(A) = I+ (C).
3. Decoding linear codes using a reduced Gröbner basis. In this section we
prove that the reduced Gröbner basis for the ideal I+ (C) w.r.t. a degree compatible
ordering on K[X] (see for example [8] for a definition of such orderings) provides an
algebraic decoding algorithm associated to computing the reduction of a monomial
modulo the binomial ideal I+ (C).
If we fix a term order ≺ then the leading term of a polynomial f with respect to
≺, denoted by LT≺ (f ), is the largest monomial among all monomials which occurs
with non-zero coefficient in the expansion of f . Let I be an ideal in K[X], then the
initial ideal in≺ (I) is the monomial ideal generated by the leading term of all the
polynomials in I, i.e. in≺ (I) = {LT≺ (f ) | f ∈ I} . The monomials which do not lie
in the ideal in≺ (I) are called canonical monomials. The semigroup ideal generated

10

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

by the leading terms of a set of polynomials F ⊆ K[X] w.r.t. ≺ is denoted by
LT≺ (F ).
Definition 3.1. An ordering ≺ on K[X] is said to be degree compatible if
deg(Xu ) < deg(Xv ) implies that Xu ≺ Xv
for all monomials Xu , Xv ∈ K[X].
Definition 3.2. A finite set of nonzero polynomials G = {g1 , . . . , gm } of the ideal
I is a Gröbner basis with respect to the term order ≺ if the leading terms of the
elements of G generate the initial ideal in≺ (I). Moreover G is reduced if
1. gi are monic for all i = 1, . . . , m.
2. If i 6= j then none of the monomials appearing in the expansion of gj is
divisible by LT≺ (gi ).
A well known result is that every non-zero ideal has a unique reduced Gröbner
basis. Let G be a Gröbner basis for an ideal I ⊂ K[X] and let f ∈ K[X]. Then
there is a unique remainder r on the division of f by G called the normal form of
f and denoted by Red(f, G). For a deeper discussion of Gröbner bases we refer the
reader to [8, 20].
Throughout this section, let G = {g1 , . . . , gs } be the reduced Gröbner basis of
the ideal I+ (C) with respect to ≻, where we take ≻ to be any degree compatible
ordering on K[X] with X1 ≺ . . . ≺ Xn .
Let us present some elementary facts about Gröbner basis of binomials ideals.
Proposition 1. [10, Proposition 1.1] Let ≺ be an ordering on K[X], and let I ⊆
K[X] be a binomial ideal:
1. The reduced Gröbner basis G of I with respect to ≺ consists of binomials.
2. The normal form with respecto to ≺ of any term modulo G is again a term.
Lemma 3.3. All the elements of G \ RX are in standard form.
+

−

Proof. Suppose, contrary to our claim, that there exists an element g = Xg − Xg
+
−
in G \ RX such that Xg and/or Xg are not in standard form.
+
j
By definition, there exists i, j such that X∆α wi = Xg Xu . Therefore, if l ∈
+
+
j
supp(Xg ), then l ∈ supp(X∆α wi ). Or equivalently, Xg is in standard form.
−
Now assume that Xg is not in standard form. That is,
−

Xg = Xv xi,j1 xi,j2 with xi,j1 xi,j2 − xi,j3 ∈ RXi for some index j3 .
We distinguish two cases:
• xi,j1 xi,j2 − xi,j3 ∈ G, which contradicts the fact that G is reduced.
/ G. Then we deduce that there exists ĝ 6= g such that
• xi,j1 xi,j2 − xi,j3 ∈
−
xi,j1 xi,j2 is divisible by LT≺ (ĝ), or equivalently, Xg is divisible by LT≺ (ĝ),
again a contradiction.
By the above Lemma, we know that all the elements of G \ RX are in standard
form so, for all gi ∈ G \ RX with i = 1, . . . , s, we define
+

−

gi = X∆gi − X∆gi

with

+

−

X∆gi ≻ X∆gi

and

gi+ − gi− ∈ C.

Remark 8. From the fact that G is a Gröbner basis for I+ (C), then we can deduce
that X∆c1 − X∆c2 ∈ hGi if and only if c1 − c2 ∈ C.

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

11


Theorem 3.4. Let t be the error-correction capability of C. If deg Red≺ (X∆a , G) ≤
t, then the vector e ∈ Fnq verifying that X∆e = Red≺ (X∆a , G) is the error vector
corresponding to the received word a ∈ Fnq . In other words, c = a − e ∈ C is the
closest codeword to a ∈ Fnq . Otherwise a contains more than t errors.
Proof. Following the definition of “reduction of a polynomial with respect to G”;
since X∆e = Red≺ (X∆a , G) there exists polynomials f1 , . . . , fs ∈ K[X] such that
X∆a = f1 g1 + · · · + fs gs + X∆e , or equivalently X∆a − X∆e ∈ hGi .

(1)

Remark 8 now leads to a − e ∈ C.
Assume that there exists e2 ∈ Fnq such that a − e2 ∈ C and wH (e2 ) < wH (e);
i.e. the total
degree of X∆e2 is strictly smaller than the total degree of X∆e ,

∆e2
< deg X∆e . Then, by Lemma 8, there exists fˆ1 , . . . , fˆs ∈ K[X] such
deg X
∆a
that X = fˆ1 g1 +· · ·+ fˆs gs +X∆e2 , which contradicts the uniqueness of the normal
form.
We have actually proved that the exponent of the normal form of X∆a is in the
Voronoi region of 0. Therefore the normal form of X∆a is the unique solution for
the system (1) if deg(X∆e ) ≤ t. Otherwise a contains more than t errors.
Remark 9. Take notice that we are implicitly assuming that Red≺ (X∆a , G) is a
monomial in standard form which is the case. Indeed, we have shown in Lemma 3.3
that all the elements of G \ RX are in standard form. Thus, even if RX 6⊂ G then,
the normal form of any monomial in standard form modulo G is again a monomial
in standard form.
The following results shows that one of the elements in G provides the errorcorrection bound of C.
Proposition 2. Let t be the error-correction capability of C, then

t = min wH (gi+ ) | gi ∈ G \ {RX } − 1
=

min {deg(gi ) | gi ∈ G \ {RX }} − 1.

Proof. This proposition is analogous to [5, Theorem 3]. Let c be a minimum weight
nonzero codeword of C, i.e. wH (c) = d, where d is the minimum distance of C.
Let X∆c1 and X∆c2 be two monomials in K[X] such that X∆c = X∆c1 X∆c2 ,
supp(c1 ) ∩ supp(c2 ) = ∅ and wH (c1 ) = t + 1, that is to say X∆c1 ≻ X∆c2 .
Then X∆c1 X∆c2 − 1 ∈ I+ (C), or equivalently X∆c1 − X∆−c2 ∈ I+ (C). Note that
wH (c2 ) = wH (−c2 ), thus X∆c1 ≻ X∆−c2 . Therefore, we get that X∆c1 belongs to
the initial ideal in (I+ (C)), so there must exists an index i ∈ {1, . . . , s} such that
the leading term of gi ∈ G divides X∆c1 , and thus, wH (gi+ ) ≤ wH (c1 ) = t + 1.
Now suppose that there exists gj ∈ G \ {RXl }l=1,...,n with j ∈ {1, . . . , s} such
that wH (gj+ ) ≤ t. By definition, gj+ − gj− ∈ C \ {0}, but
wH (gj+ − gj− ) ≤ wH (gj+ ) + wH (gj− ) ≤ 2t < d,
which contradicts the definition of minimum distance of C.
Therefore,
n
o
t < min wH (gj+ ) | gj ∈ G \ {RXl }l=1,...,n ≤ wH (gi+ ) ≤ t + 1,

which provides the result.

Proposition 3. wH (gi+ ) − wH (gi− ) ≤ 1 for all i ∈ {1, . . . , s}.

12

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

Proof. Without loss of generality we assume that i = 1. We can distinguish two
cases:
• The case when supp(g1+ ) ∩ supp(g1− ) = ∅.
Let wH (g1+ − g1− ) = d1 and t1 = ⌊ d12−1 ⌋. Then we will show that either
wH (g1+ ) = t1 or wH (g1+ ) = t1 + 1.

Obviously wH (g1+ ) > t1 , otherwise wH g1+ − g1− ≤ 2t1 < d1 . Now suppose wH (g1+ ) > t1 + 1. Let xi,j be any variable that belongs to the support
+
+
of X∆g1 , i.e. X∆g1 = xi,j X∆w with wH (w) + 1 = wH (g1+ ). Then, there
exists
 an index l ∈ {1, . . . , q − 1} such that xi,j xi,l − 1 ∈ RXi . Therefore,
+

−

xi,l X∆g1 − X∆g1

−

≡ X∆w − xi,l X∆g1 mod RX . Observe that

wH (g1− ) + 1 = d1 − wH (g1+ ) + 1 < t1 + 1

and

wH (w) = wH (g1+ ) − 1 > t1 .

−

As a consequence, X∆w ≻ xi,l X∆g1 and thus X∆w ∈ LT(G \ {g1 }), which
contradicts the fact that G is reduced.
Therefore wH (g1+ ) = t1 +1 and wH (g1− ) = t1 +1 if d1 is even and wH (g1− ) =
t1 , otherwise. In both cases we have that wH (g1+ ) − wH (g1− ) ≤ 1.
• A similar argument applies to the case i ∈ supp(g1+ ) ∩ supp(g1− ).
+
−
In other words, g1 = Xg1 − X∆g1 = xi,j X∆a − xi,l X∆b . There exists an
integer m ∈ {1, . . . , q − 1} such that xi,j xi,m − 1 and xi,l xi,m − xi,v belongs
to RXi . Thus xi,m g1 ≡ X∆a − xi,v X∆b mod RX . Suppose that X∆a ≻
xi,v X∆b , then X∆a ∈ LT(G \{g1 }), is a contradiction. Therefore, wH (b)+1 ≥
wH (a) which establishes the desired formula.
Note that it may happen that l = j. In this case we would have that
wH (b) ≥ wH (a), i.e. wH (gi− ) ≥ wH (gi+ ) which is impossible except for the
case of equality.
Definition 3.5. Let G be the reduced Gröbner basis of the ideal I(C) w.r.t. a
degree compatible ordering ≺ in K[X]. We define “the reduction process →” of any
monomial Xw ∈ X using G as:
′

1. Reduce Xw to its standard form Xw using the relations RX .
′
2. Reduce Xw w.r.t. G \ RX by the usual one step reduction.
This reduction process is well defined since it is confluent and noetherian i.e.: if
Xw ∈ X is an arbitrary term. Then:
i) The reduction process → is noetherian.
ii) If Xw → Xw1 , Xw → Xw2 and Xw1 , Xw2 are irreducible monomials modulo
→, then Xw1 = Xw2 .
Remark 10. The irreducible element corresponding to Xw coincides with the normal form of Xw w.r.t. G, denoted by Red(Xw , G). The above theorem states that
Red(Xw , G) is unique and computable by a typical Buchberger’s reduction process.
Example 2. Continuing with Example 1, note that the code has Hamming distance
5 so it corrects up to 2 errors. A reduced Gröbner basis G for the ideal I+ (C)
w.r.t. the degrevlex order with
x1,1 < x1,2 < x2,1 < x2,2 < · · · < x7,1 < x7,2
| {z }
| {z } | {z }
X1

X2

X7

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

13

has 193 elements. It is easy to check that the binomial G1 = x3,1 x6,2 x7,1 − x1,1 x2,2
and all the generators of the ideal RX are elements of the reduced Gröbner basis.
Let us take the codeword c = (1, 2, 2, 0, 0, 1, 2) and add the error vector e =
(2, 2, 0, 0, 0, 0, 0). Then the received word is y = (0, 1, 2, 0, 0, 1, 2) = c + e which
corresponds to the monomial w = x2,2 x3,1 x6,2 x7,1 . Let us reduce w using G:
x22,2 −x2,1 ∈RX2

G1 =x3,1 x6,2 x7,1 −x1,1 x2,2

w = x2,2 x3,1 x6,2 x7,1 −−−−−−−−−−−−−−−−−→ x1,1 x2,2 x2,2 −−−−−−−−−−→ x1,1 x2,1 .
The normal form of w modulo G is x1,1 x2,1 which has weight 2, then (2, 2, 0, 0, 0, 0, 0)
is the error vector corresponding to w and the closest codeword is x1,2 x2,1 x3,2 x6,2 x7,1 ,
i.e. c = y + e.
Remark 11. In [16] the authors describe another set of generators of the ideal
I(C) when C is a modular code, i.e. codes defined over Zm . In particular for codes
over Fq with q prime, but not for the case pr since Fpr 6∼
= Zpr . In this article the
ideal, denoted by Im (C), is defined by the rows of a generating matrix of the code
and the modular relations of Zm . However, for m 6= 2 such ideal does not allow
complete decoding since the reduction does not provide the minimum Hamming
weight representative in the coset. In the following lines we give an example of
what is discussed in this note.
Example 3. Continuing with the Example 1, now suppose that we consider our
code as a linear code over the alphabet Z3 ∼
= F3 . Then we can define the ideal
associated with C as the ideal generated by the following set of binomials (see [16,
Theorem 3.2] for the definition of this ideal and the references given there)
 


S  3
y1 y3 y42 y5 y6 y7 − 1,
Im (C) =
⊆ K[y1 , . . . , y7 ].
yi − 1 i=1,...,7
y2 y32 y42 y5 y72 − 1
If we compute a reduced Gröbner basis G of Im (C) w.r.t. a degrevlex ordering with
y1 < y2 < · · · < y7 we obtain 62 binomials. The elements
G1 = y32 y6 y72 − y12 y2

and

G2 = y12 y22 − y4 y52 y6

are elements of the reduced Gröbner basis.
Similarly to Example 2, let us take the codeword c = (1, 2, 2, 0, 0, 1, 2) and add the
error e = (2, 2, 0, 0, 0, 0, 0). Then the received word is y = (0, 1, 2, 0, 0, 1, 2) = c + e
which corresponds to the monomial w = y2 y32 y6 y72 . Let us reduce w using G:
w = y2 y32 y6 y72

G1 =y 2 y6 y 2 −y 2 y2

3
7
−−−−−
−−−
−−1−→ y12 y22

G2 =y 2 y 2 −y4 y 2 y6

1 2
−−−−−
−−−−−5−→ y4 y52 y6 .

The normal form of w modulo G is y4 y52 y6 which does not correspond to the error
vector.

Proposition 4. The set T = gi+ − gi− | i = 1, . . . , s is a test-set for C.

Proof. Let a ∈ Fnq and suppose that a ∈
/ D(0). According to Theorem 3.4 there
exists e ∈ Fnq such that
Red≺ (X∆a , G) = X∆e where wH (e) < wH (a).

(2)

We now apply “the reduction process →′′ . As X∆a − X∆e ∈ I+ (C) with X∆a ≻
X , then X∆a is a multiple of LT≺ (gi ) for some i = 1, . . . , s. Or equivalently
supp ∆gi+ ⊆ supp (∆a), i.e. wH (a − gi+ ) = wH (a) − wH (gi+ ). And consequently,

wH (a − gi+ − gi− ) ≤ wH (a) − wH (gi+ ) + wH (gi− ) ≤ wH (a).
∆e

14

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO
+

−

Note that the second inequality is due to the fact that X∆gi ≻ X∆gi . Note that
+
−
we have actually proved that X∆a −→ X∆a−(gi −gi ) . Repeated applications of
“the reduction process →” enables us to arrive to X∆e .
In case of equality of the above equation, it means that we have not chosen the
right binomial gi ∈ G. Note that by Equation 2 there must exists an element gj ∈ G
such that wH (a) > wH (a − gj+ + gj− ).
4. FGLM technique to compute a Gröbner basis. The aptly-named FGLM
algorithm was developed by Faugère, Gianni, Lazard and Mora in [11]. This algorithm which only applies to zero-dimensional ideals allows to take a Gröbner basis
from a relative easy calculations and convert it to the reduced Gröbner basis for
the same ideal with respect to another monomial ordering.
In this section we present an algorithm to compute a reduced Gröbner basis of
the ideal I+ (C) which is associated to a linear code C defined over the finite field
Fq . This algorithm goes back to the work of Faugère et al. [11] and generalizes that
of [5, 12, 13].
Throughout this section we require some theory of Gröbner Bases for submodules
M ⊆ K[X]r . We define a term t in K[X]r as an element of the form t = Xv ei
where {ei }i=1,...,r denote a standard basis of Kr . A term ordering ≺ on K[X]r is a
total well-ordering such that if t1 ≺ t2 then Xu t1 ≺ Xu t2 for every pair of terms
t1 , t2 ∈ K[X]r and every monomial Xu ∈ K[X]. Let ≺ be any monomial order on
K[X] the following term orderings are natural extensions of ≺ on K[X]r :
• Term-over-position order (TOP order) first compares the monomials by ≺
and then the position within the vectors in K[X]r . That is to say,
Xα ei ≺TOP Xβ ej ⇐⇒ Xα ≺ Xβ

or

Xα = Xβ and i < j .

• Position-over-term order (POT order) which gives priority to the position of
the vector in K[X]r . In other words,
Xα ei ≺POT Xβ ej ⇐⇒ i < j

or

i = j and Xα ≺ Xβ .

Definition 4.1. Let R be a commutative ring. Given a finitely generated R-module
M and a set z1 , . . . , zn of generators, a syzygy of M is an element (g1 , . . . , gn ) ∈ Rn
for which g1 z1 +· · ·+gn zn = 0. The set of all syzygies relative to the given generating
set is a submodule of Rn , called the module of syzygies.
If we fix a generator matrix G ∈ Fqk×n of C whose rows are labelled by {w1 , . . . , wk }
and we consider the following set of binomials:
o
n
j
F = fi,j = X∆α wi − 1 i=1,...,k ⊆ K[X].
j=1,...,q−1

Then, by Theorem 2.3, the set F ∪ {RXi }i=1,...,n generates the ideal I+ (C).
Let r = k(q − 1) + 1. Let M be the syzygy module in K[X]r with generating set
F̂ = {−1, f1,1 , . . . , f1,q−1 , . . . , fk,1 , . . . , fk,q−1 } ,

where the binomials {RXi }i=1,...,n are considered implicit on the operations. Note
that each syzygy corresponds to a solution of the following equation:
−β0 +

q−1
k X
X
i=1 j=1

β(i−1)(q−1)+j fi,j = 0 with βl ∈ K[X] for l = 1, . . . , k(q − 1).

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

15

Hence, the first component of any syzygy of the module M indicates an element of
the ideal generated by F .
The outline of the proposed algorithm consist of three main parts:
1. Initialization: Take a Gröbner basis, namely G1 , of the submodule M ⊆
K[X]r and choose a term ordering ≺2 on K[X]. The set G2 is initially empty
but will become the reduced Gröbner basis of M w.r.t. a TOP ordering induced
by ≺2 .

Remark 12. Consider the set G1 = gij = e1 fi,j + e(i−1)(q−1)+j+1 where el
denotes the unit vector of length r with a one in the l-th position. We claim
that G1 is a basis for M .
Moreover, G1 is a Gröbner basis of M relative to a POT ordering ≺w
induced by an ordering ≺ in K[X] and the weight vector
w = (1, LT≺ (f1,1 ), . . . , LT≺ (fk,q−1 )).
Note that the leading term of gij with respect to ≺w is e(i−1)(q−1)+j+1 .
2. Main Loop: Use the FGLM algorithm running through the terms of K[X]r
using a TOP ordering induced by ≺2 to get the Gröbner basis G2 of M relative
to the new ordering.
Remark 13. It is immediate that the normal form with respect to G1 of
any element is zero except in the first component, that is to say, the linear
combinations that Fitzpatrick’s algorithm [12] look for, take place in this
component.
3. Conclusion: It is easily seen that the first component of the elements of G2
forms a Gröbner basis of I+ (C) w.r.t. ≺2 .
Three structures are used in the algorithm:
• The list List whose elements are of the specific type v = (v[1], v[2]) where
v[2] represents an element in K[X] which can be expressed as
v[2] = v[1] +

q−1
k X
X

λ(i−1)(q−1)+j fi,j with λ1 , . . . , λr−1 ∈ K[X].

i=1 j=1

Thus, the coefficient vector (v[1], λ1 , . . . , λr−1 ) ∈ K[X]r is the associated vector of v[2] on the module M . And v[1] represents the first component of such
vector.
• The list GT which ends up being a reduced Gröbner basis of I+ (C) w.r.t. a
degree compatible ordering ≺T .
• The list N of terms that are reduced with respect to GT , i.e. the set of
standard monomials.
We also require the following subroutines:
• InsertNexts(w, List) inserts the product wx for x ∈ X in List and removes
the duplicates, where the binomials of {RXi }i=1,...,n are considered as implicit
in the computation. Then the elements of List are sorted by increasing
order w.r.t. ≺T in the first component of the pairs and in case of equality by
comparing the second component. Recall that
X = {X1 , . . . , Xn } = {x1,1 , . . . , x1,q−1 , . . . , xn,1 , . . . , xn,q−1 }.
• NextTerm(List) removes the first element from the list List and returns it.
• Member(v,[v1, . . . , vr ]) returns j if v = vj or false otherwise.

16

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

Remark 14. Note that the computation of Xa xi,j modulo the ideal RX , with
a ∈ Zn(q−1) , acts like the operation ∇a+αj ei in the finite field Fnq where {e1 , . . . , en }
denotes a standard basis of Fnq .
Algorithm 2: Adapted FGLM algorithm for I+ (C)
Data: The rows {w1 , . . . , wk } ⊆ Fnq of a generator matrix of an [n, k] linear
code C defined over Fq and a degree compatible ordering ≺T on K[X].
Result: A" reduced Gröbner basis GT of #
the ideal I+ (C) w.r.t. ≺T .
o
n
∆αj wi
) i=1,...,k ;
1 List ←− (1, 1), (1, X
j=1,...,q−1

2
3

4
5
6
7
8
9
10
11
12
13
14
15
16

GT ←− ∅; N ←− ∅; r ←− 0;
while List 6= ∅ do
w ←− NextTerm(List);
if w[1] ∈
/ LT≺T (GT ) then
j = Member(w[2], [v1 [2], . . . , vr [2]]);
if j 6= false then
GT ←− GT ∪ {w[1] − vj [1]};
else
r ←− r + 1;
vr ←− w;
N ←− N ∪ {vr [1]};
List = InsertNexts(w, List);
end if
end if
end while

Theorem 4.2. Algorithm 2 computes a reduced Gröbner basis of the ideal associated
to a given linear code C of parameters [n, k] defined over Fq .
Proof. The proof of the algorithm is an extension of that in [12, Algorithm2.1] and
therefore, is also a generalization of the FGLM algorithm [11]. Let G ∈ Fqk×n be a
generator matrix of C. We label the rows of G by {w1 , . . . , wk } ⊆ Fnq .
By Theorem 2.3 the ideal associated to the linear code C may be defined as the
following binomial ideal:

 n
o
S
j
{RXi }i=1,...,n
X∆α wi − 1 i=1,...,k
I+ (C) =
j=1,...,q−1

=

D

{fi,j }

i=1,...,k
j=1,...,q−1

S

{RXi }i=1,...,n

E

.

We first show that GT is a subset of binomials of the ideal I+ (C). The proof is
based on the following observation: Xa − Xb ∈ GT if and only if it corresponds to
the first component of a syzygy in the module M . In other words,
Xa − Xb ≡

q−1
k X
X

λ(i−1)(q−1)+j fi,j

i=1 j=1

or equivalently, Xa − Xb ∈ I+ (C).

mod RX with λ1 , . . . , λr−1 ∈ K[X],

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

17

Moreover, we claim that the initial ideal of I+ (C) w.r.t. ≺T is generated by the
leading terms of polynomials in GT . Indeed, by Theorem 2.3, any binomial f (X) of
I+ (C) can be written uniquely as a linear combination of elements in the generator
set F = {fi,j } i=1,...,k modulo the ideal RX , i.e.
j=1,...,q−1

f (X) =

q−1
k X
X

λ(i−1)(q−1)+j fi,j

mod RX with λ1 , . . . , λr−1 ∈ K[X].

i=1 j=1

Therefore, LT≺T (f (X)) is a multiple of the leading term of an element of F
that appears on its decomposition. But LT≺T (fi,j (X)) cannot be in N for all
i = 1, . . . , k and j = 1, . . . , q − 1. To see this, note that the first element introduced
in the set N is always 1 and


j
j
1 = X∆α wi − fi,j i.e. Red≺T X∆α wi , F = 1,
j

which implies that X∆α wi − 1 ∈ GT .
By definition, GT is reduced since we only consider on the algorithm terms which
are not divisible by any leading term of the Gröbner basis.
Finally, since I+ (C) has finite dimension, then the number of terms in N is
bounded. Note that at each iteration of the main loop either the size of List
decreases or the size of N increases, thus there are only a finite number of iterations.
This completes the proof of the algorithm.
Remark 15. Recall that the dimension of the quotient vector space Fnq /C is n − k.
Moreover, if C can correct up to t errors, then every word e of weight wH (e) ≤ t
is the unique coset leader (vectors of minimal weight in their cosets) of its coset
modulo C. In other words, all monomials of degree less than t modulo the ideal RX
should be standard monomials for GT .
Note that the writing rules given by the ideal RX implies that “the exponent of
each variable xi,j is 0 or 1” and “two different variables xi,j and xi,l can not appear
in a monomial”. Thus, the number of standard monomials of a t-error correcting
code is at least
 
t
X
n
.
(3)
M=
(q − 1)l
l
l=1

n−k

Accordingly, if q
= M , then all cosets have a unique coset leader of weight
smaller or equal to t. Codes that achieve this equality are the so-called perfect codes.
Also for perfect codes, their Voronoi regions are disjoints. Otherwise, there must
appear some cosets leaders of weight at most ρ(C), where ρ(C) denotes the covering
radius of C, but never as the unique leader, or equivalently there exists standard
monomials of degree up to ρ(C). Recall that ρ(C) coincide with the largest weight
among all the cosets leaders of C, so ρ(C) = t if C is a perfect code.
By Proposition 3 in the worst case, a minimal generator of the initial ideal
in< (I+ (C)) has degree ρ(C) + 1 where < is a degree compatible ordering.
Theorem 4.3. Let C be a linear code over Fq of length n and covering radius ρ(C).
If the basis field operations
 need an unit time, then Algorithm 2 needs a total time
of O Dn2 (q − 1) log(q) , where
 
ρ(C)+1
X
n
(q − 1)i
.
D=
i
i=1

18

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

Proof. The main time of the algorithm is devoted to the management of InsertNexts.
In each main loop iteration this function first introduces n(q − 1) new elements to
the list List, then compares all the elements and finally eliminates redundancy.
Note that comparing two monomials in K[X] is equivalent to comparing vectors
in Fnq , thus we need O(n log(q)) field operations.
At iteration i, after inserting the new elements in the list List we would have at
most Di elements where
Di =

+
(q − 1)k
| {z }
Elements that
initialized List

i (n(q − 1)) − i
.
|
{z
}
At each iteration
the first element is removed
and we add n(q-1)new elements

By Remark 15 we have an upper bound D for the number of times that InsertNexts
should be called. This gives a total time of

O (n log(q) ((q − 1)k + D (n(q − 1)) − D)) ∼ O Dn2 (q − 1) log(q) .
Algorithm 3: Algorithm for computing a minimal Gröbner test-set for C
Data: The rows {w1 , . . . , wk } ⊆ Fnq of a generator matrix of the code C and a
degree compatible ordering ≺T on K[X].
Result: A minimal Gröbner test-set T for C.
// For each binomial g = Xa − Xb we define g := ∇a − ∇b ∈ Fnq
// Add the following lines after Step 7 of Algorithm 2.
1 g ←− w[1] − vj [1];
2 if supp(g) 6⊃ supp(gi ) for all gi ∈ GT \ {g} then
3
T ←− T ∪ {g}
4 end if

By Proposition 4, the set of codewords related with the exponents of a reduced
Gröbner basis of the ideal associated with a linear code C with respect to a degree
compatible ordering induces a test-set T for C. However, not all the codewords of
this test-set are codewords of minimal support, i.e. this set is somehow redundant.
We can reduce the number of codewords to the set T ∩ MC , which is still a test-set
for the code C, using Algorithm 3. Moreover, once a vector is stored we can omit
its multiples as proposed Algorithm 1. The obtained test-set is called a minimal
Gröbner test-set.
On the following example we compared the cost storage of the proposed GDDA
with Complete Syndrome Decoding.
Example 4. Consider C an

1
G= 0
0

[9, 3, 3] ternary code with generator matrix

0 0 0 0 1 0 2 0
1 0 0 1 1 1 0 1  ∈ F3×9
3
0 1 1 2 2 1 1 0

This code has 33 = 27 codewords. If we compute a reduced Gröbner basis G of I+ (C)
we obtained a test-set consisting of 24 codewords. But for decoding we just need a
minimal test-set (we can eliminate those elements which are multiples and those

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

19

codewords which are not of minimal support). That is, if we apply GDDA we just
need to save in memory 12 elements:
(1, 2, 1, 1, 1, 2, 0, 0, 2)
(0, 1, 1, 1, 0, 0, 2, 1, 1)
(1, 2, 0, 0, 2, 0, 2, 2, 2)
(1, 1, 1, 1, 0, 1, 2, 0, 1)

(0, 1, 2, 2, 2, 2, 0, 2, 1)
(0, 0, 1, 1, 2, 2, 1, 1, 0)
(1, 1, 0, 0, 1, 2, 1, 2, 1)
(1, 0, 1, 1, 2, 0, 1, 0, 0)

(1, 1, 2, 2, 2, 0, 0, 1, 1)
(0, 1, 0, 0, 1, 1, 1, 0, 1)
(2, 0, 0, 0, 0, 2, 0, 1, 0)
n−k

−1
= 364
But if we apply Complete Syndrome Decoding we need to store q (q−1)
coset leaders (we use here the same trick, neither the zero vector nor the multiples
of a coset leader are stored).

Our experimental results are in good agreement with the following conjecture.
Conjecture 1. Given an [n, k] linear code C over Fq . Let TG be a test-set for C
induced by a reduced Gröbner basis G of the ideal I(C) w.r.t. a degree compatible
ordering. Then,
q n−k − 1
|TG | <
(q − 1)
That is, the cost storage of GDDA is smaller than Complete Syndrome Decoding.
5. Set of codewords of minimal support. We define the Universal Gröbner
basis of I+ (C), denoted by UC , to be the union of all reduced Gröbner Bases G≺ of
I+ (C) as ≺ runs over all terms orders of K[X]. A binomial Xu1 − Xu2 in I+ (C) is
called primitive if there exists no other binomial Xv1 − Xv2 ∈ I+ (C) such that Xv1
divides Xu1 and Xv2 divides Xu2 .
Lemma 5.1. Every binomial in UC is primitive.
Proof. It is a straightforward generalization of [20, Lemma 4.6]. Let us fix an
arbitrary term ordering ≺ in K[X], and let G≺ be the reduced Gröbner basis of
I+ (C) w.r.t. ≺. By definition, for any binomial Xu1 − Xu2 in G≺ with Xu1 ≻ Xu2 ,
Xu1 is a minimal generator of the initial ideal in≺ (I+ (C)) and Xu2 is a canonical
monomial. Now suppose that Xu1 − Xu2 is not primitive, or equivalently there
exists another binomial Xv1 − Xv2 in I+ (C) such that Xv1 divides Xu1 and Xv2
divides Xu2 . We distinguish two cases:
• If Xv1 ≻ Xv2 , then Xu1 is not a minimal generator of the initial ideal
in≺ (I+ (C)).
• If Xv1 ≺ Xv2 , then Xu2 is not in canonical form.
Both cases contradicts our assumption.
We call the set of all primitive binomials of I+ (C) the Graver basis of I+ (C) and
denote it by GrC .
Corollary 2. UC ⊆ GrC .
Proof. The result is a direct consequence of Lemma 5.1.
The following theorem suggests an algorithm for computing the Graver basis of
the ideal I+ (C). For this purpose we describe the Lawrence lifting of the ideal I+ (C).
Definition 5.2. We define the Lawrence lifting of the ideal I+ (C) as the ideal

IΛ(C) = X∆w1 Z∆w2 − X∆w2 Z∆w1 | w1 − w2 ∈ C
in the polynomial ring K[X, Z] where X and Z denote n(q − 1) variables each.

20

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

Theorem 5.3. The Graver basis of IΛ(C) coincides with any reduced Gröbner basis
of IΛ(C) .
Proof. The proof starts with the observation that a binomial X∆u1 − X∆u2 is primitive in the ideal I+ (C) if and only if the corresponding binomial X∆u1 Z∆u2 −
X∆u2 Z∆u1 in the lifting ideal IΛ(C) is primitive. Therefore, between the Graver
basis of the ideals I+ (C) and IΛ(C) there exists the following relation:

GrΛ(C) = X∆u1 Z∆u2 − X∆u2 Z∆u1 | X∆u1 − X∆u2 ∈ GrC .
Now, take any element g = X∆u1 Z∆u2 − X∆u2 Z∆u1 in GrΛ(C) . Let B be the set
of all binomials in IΛ(C) except g and assume that B generates the ideal IΛ(C) .
Therefore g can be written as a linear combination of the elements of B. In other
words, there exists a binomial X∆v1 Z∆v2 − X∆v2 Z∆v1 in B such that one of its
terms divides the leading term of g. Replacing v = (v1 , v2 ) by −v = (−v1 , −v2 )
in Fnq if necessary, we may assume that X∆v1 Z∆v2 divides X∆u1 Z∆u2 , contrary to
the fact that X∆u1 − X∆u2 is primitive in I+ (C). So some non-zero scalar multiple
of g must appear in any reduced Gröbner basis of IΛ(C) which is also a minimal
generating set of IΛ(C) .

This theorem gives us an algorithm to compute a Graver basis of the ideal I+ (C),
exposed as Algorithm 4. Note that Step 3 of Algorithm 4 can be executed by
applying Algorithm 2. Later in Theorem 5.4 we will give a set of generators of the
lawrence lifting ideal IΛ(C) which will facilitate the implementation of this algorithm.
Algorithm 4: Algorithm for computing the Graver basis of I+ (C)
Data: An [n, k] linear code C defined over Fq .
Result: The Graver basis of the ideal I+ (C), GrC .
1 Choose any term order ≺ on K[X, Z];
2 Compute the Lawrence lifting ideal IΛ(C) ;
3 Compute a reduced Gröbner basis of IΛ(C) w.r.t. ≺;
4 Substitute the variable Z by 1;
Here is another way of defining the ideal IΛ(C) .
Theorem 5.4. Let C be an [n, k] linear code defined over Fq and {w1 , . . . , wk } be
the rows of a generator matrix of C. We define the ideal:

 n
o
S
∆αj wi
∆αj wi
}
,
R
{R
−
Z
X
Zi i=1,...,n
Xi
.
I3 =
i=1,...,k
j=1,...,q−1

Then IΛ(C) = I3 .

Proof. The following result may be proved in the same way as Theorem 2.3. It
is easily seen that all the binomials of the generating set of I3 belongs to IΛ(C) .
Indeed, the exponents of all the binomials of the sets RXi and RZi correspond to
the codeword 0 ∈ C.
Conversely, we need to show that each binomial X∆a Z∆b − X∆b Z∆a in IΛ(C)
belongs to I3 . Applying the definition of the ideal IΛ(C) we can rewrite a − b ∈ C as
a − b = λ1 w1 + · · · + λk wk with λ1 , . . . , λk ∈ Fq .

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

21

We have that
X∆(a−b) Z∆(b−a) − 1

=



+

k
Y
X∆λi wi Z∆−λi wi
X∆λ1 w1 Z∆−λ1 w1 − 1
i=2

k
Y

X

∆λi wi

∆−λi wi

Z

!

−1

i=2

=



+



+
+




mod {RX , RZ }

k
Y
X∆λ1 w1 Z∆−λ1 w1 − 1
X∆λi wi Z∆−λi wi +
i=2

X∆λ2 w2 Z∆−λ2 w2

k
Y
X∆λi wi Z∆−λi wi + · · · +
−1
i=3

X

∆λk−1 wk−1

∆−λk−1 wk−1

Z


X∆λk wk Z∆−λk wk − 1


− 1 X∆λk wk Z∆−λk wk

mod {RX , RZ } .

The last equation forces that
*
o
n
j
j
X∆(a−b) Z∆(b−a) − 1 ∈
X∆α wi Z∆−α wi − 1

i=1,...,k
j=1,...,q−1

+

∪ {RX , RZ } .

Note that we have actually proved that
X∆a Z∆b − X∆b Z∆a
which completes the proof.



mod hRX , RZ i = X∆(a−b) Z∆(b−a) − 1 ∈ I3 ,

The following result suggests an algorithm to compute the set MC . Note that
given the set MC we could deduce the minimum distance of C.
Theorem 5.5. The set of codewords of minimal support of the code C is a subset
of the vectors related to the Graver basis of the ideal associated to C.
Proof. Let m ∈ MC . Suppose the theorem is false, then no binomial of type
X∆a − X∆b ∈ I+ (C) with a − b = m would be primitive.
We can always choose a binomial representation X∆a − X∆b (among all the
possible) such that the following condition hold, labelled as necessary condition:


• If xi,r ∈ supp X∆a and xi,s ∈ supp X∆b , then xi,r xi,s − 1 ∈
/ RXi . Other∆a
∆b
∈ I+ (C), with i = 1, . . . , n, instead.
wise we take xi,s X − X
Let X∆v1 − X∆v2 be a primitive binomial of I+ (C) such that X∆v1 divides X∆a
and X∆v2 divides X∆b , or equivalently,
supp(∆v1 ) ⊂ supp(∆a)

and

supp(∆v2 ) ⊂ supp(∆b)

The necessary conditions defined above guarantee that if there exists a nonzero
coordinate i ∈ supp(a) ∩ supp(b) then i ∈ supp(a − b). Therefore, we found
v1 − v2 ∈ C \ {m} such that supp(v1 − v2 ) ⊂ supp(m), which contradicts the
minimality of m.
Remark 16. We could get rid of the leftover codewords from the set obtained by
the above theorem using Algorithm 3.

22

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

Corollary 3. The set of codewords of minimal support of any linear code C can be
computed from the ideal

 n
o
S
j
j
{RXi , RZi }i=1,...,n .
X∆α wi − Z∆α wi i=1,...,k
I3 =
j=1,...,q−1

Proof. This result follows directly from Theorems 5.4 and 5.5.

Algorithm 5 describes step by step how to compute the set of codewords of
minimal support of a linear code. Note that Step 2 of Algorithm 5 can be executed
by applying Algorithm 2. Moreover, Algorithm 5 performs an incremental technique
thus we can stop before the end, obtaining a partial result as for example a minimal
codeword (with weight the minimum distance of the code).
Algorithm 5: Algorithm for computing MC
Data: An [n, k] linear code C defined over Fq .
Result: The set of codewords of minimal support of C, MC
1 Choose any term order ≺ on K[X, Z];
2 Compute a reduced Gröbner basis of I3 (defined in Theorem 5.4) w.r.t. ≺;
// Recall that I3 = IΛ(C) , i.e. the Lawrence lifting ideal of I+ (C). In other
words, if we compute a reduced Gröbner basis of I3 we are obtain the
Graver basis of I+ (C)
3 Substitute the variable Z by 1;
4 Get rid of the leftover codewords using Algorithm 3.

In the following example we will see how to use Algorithm 5 to obtain the set of
codewords of minimal support of a linear code.
Example 5. Consider C the [6, 3] ternary

1 0 0 2
GC =  0 1 0 1
0 0 1 1

This code has 33 = 27 codewords.

code with generator matrix

2 0
1 0  ∈ F3×6
.
3
2 1

• The zero codeword.
• 16 codewords of minimal support. It is easy to check that if a codeword c is a
minimal support codeword, then all its multiples are also codewords of minimal
support. So these 16 codewords represent 8 different supports.
1.
2.
3.
4.

(1, 0, 0, 2, 2, 0)
(0, 1, 0, 1, 1, 0)
(1, 1, 0, 0, 0, 0)
(0, 0, 1, 1, 2, 1)

(2, 0, 0, 1, 1, 0)
(0, 2, 0, 2, 2, 0)
(2, 2, 0, 0, 0, 0)
(0, 0, 2, 2, 1, 2)

5.
6.
7.
8.

(1, 0, 1, 0, 1, 1)
(2, 0, 1, 2, 0, 1)
(0, 1, 1, 2, 0, 1)
(0, 2, 1, 0, 1, 1)

(2, 0, 2, 0, 2, 2)
(1, 0, 2, 1, 0, 2)
(0, 2, 2, 1, 0, 2)
(0, 1, 2, 0, 2, 2)

• Another 10 codewords which do not have minimal support.
(2, 1, 0, 2, 2, 0) (1, 2, 0, 1, 1, 0)
(1, 2, 1, 2, 0, 1) (2, 1, 2, 1, 0, 2)
(2, 2, 1, 1, 2, 1) (1, 1, 2, 2, 1, 2)

(2, 1, 1, 0, 1, 1) (1, 2, 2, 0, 2, 2)
(1, 1, 1, 1, 2, 1) (2, 2, 2, 2, 1, 2)

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

23

Let α = 2 be a primitive element of F3 and let us label the rows of G by w1 , w2
and w3 . By Theorem 2.3, the ideal associated to C may be defined as the following
ideal:

 n
o
S
j
{RXi }i=1,...,6 ,
X∆(α wi ) − 1 i=1,...,3
j=1,2

where RXi consists of the following binomials

RXi = x2i,1 − xi,2 , xi,1 xi,2 − 1, x2i,2 − xi,1

with i = 1, . . . , 6.

If we compute a Gröbner basis of I+ (C) w.r.t. a degrev ordering we get 41
binomials representing the following set of 10 codewords:
(0, 2, 2, 1, 0, 2) (0, 1, 1, 2, 0, 1)
(0, 2, 0, 2, 2, 0) (0, 1, 0, 1, 1, 0)
(2, 2, 0, 0, 0, 0) (1, 1, 0, 0, 0, 0)

(0, 1, 2, 0, 2, 2) (0, 2, 1, 0, 1, 1)
(0, 0, 2, 2, 1, 2) (0, 0, 1, 1, 2, 1)

From those 10 codewords we can remove vectors which are scalar multiples of
another in the set, obtaining the following minimal test-set:
(1, 1, 0, 0, 0, 0), (0, 0, 1, 1, 2, 1), (0, 1, 0, 1, 1, 0), (0, 1, 2, 0, 2, 2), (0, 1, 1, 2, 0, 1)
Again if we compare with Complete Syndrome Decoding (CSD) the cost storage of
n−k
GDDA is much smaller. Indeed, for CSD we need to store 3 2 −1 = 13 coset
leaders.
Note that all nonzero codewords are codewords of minimal support but not all
codewords of minimal support are represented in the above set.
Traditionally, if we compute a Graver basis of I+ (C) we obtain 4212 binomials (following the techniques of [20]). However, Algorithm 5 returns directly the
following set of codewords:
(2, 1, 2, 1, 0, 2)
(1, 0, 2, 1, 0, 2)
(0, 2, 2, 1, 0, 2)
(0, 0, 2, 2, 1, 2)
(2, 0, 0, 1, 1, 0)
(1, 1, 0, 0, 0, 0)

(1, 2, 1, 2, 0, 1)
(2, 0, 1, 2, 0, 1)
(0, 1, 1, 2, 0, 1)
(0, 0, 1, 1, 2, 1)
(1, 0, 0, 2, 2, 0)
(2, 2, 0, 0, 0, 0)

(1, 2, 2, 0, 2, 2)
(2, 0, 2, 0, 2, 2)
(0, 1, 2, 0, 2, 2)
(2, 1, 0, 2, 2, 0)
(0, 1, 0, 1, 1, 0)
(0, 0, 0, 0, 0, 0)

(2, 1, 1, 0, 1, 1)
(1, 0, 1, 0, 1, 1)
(0, 2, 1, 0, 1, 1)
(1, 2, 0, 1, 1, 0)
(0, 2, 0, 2, 2, 0)

Observe that the set MC is contained in the previous set.
Conjecture 2. Example 5 is just a toy example, but the difference between exhaustive search in the whole set of codewords and the set of codewords resulting
from Algorithm 5 will be higher if C is chosen among a class of codes with a strong
algebraic structure as for example: cyclic codes, Generalized Reed-Solomon codes ...
6. Applications to other types of codes. We will show that the results presented on this article could be generalized to other classes of codes such as modular
codes, codes defined over multiple alphabets or additive codes. Modular codes were
already discussed in [16] but this new approach allows the computation of a test-set
for decoding.
Other metrics could be more useful when dealing with group codes or codes over
rings such as the Lee norm and G norm (see [1]) since they give us (via the Gray
map isometry) nice descriptions of non-linear binary codes.

24

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

6.1. Modular codes. In [16] the authors were devoted to the study of modular
codes C defined over the ring Zs . In other words, submodules of (Zns , +). The
important point in that article was the fact that a Graver basis of the lattice ideal
associated with a modular code provides the set of codewords of minimal support
of the code. Recall that the reduced Gröbner basis of the lattice ideal (defined as
in [16]) does not allow decoding, see Example 5.
However, we can adapt the ideas presented above for linear codes to modular
codes. We will use the following characteristic crossing functions.
∆s : Zs

−→ Es ∪ {0} ⊆ Zs−1

and

∇s : Es ∪ {0} −→ Zs

These applications aim at describing a one-to-one correspondence between the
ring Zs and the standard basis of Zs−1 , denoted as Es = {e1 , . . . , es−1 } where ei
denotes the unit vector with a 1 in the i-th coordinate and 0’s elsewhere.
1. The map ∆s replaces the element i ∈ Zs by the vector ei and 0 ∈ Zs by the
zero vector 0 ∈ Zs−1 .
2. The map ∇ recovers the element j ∈ Zs from the unit vector ej and the zero
element 0 ∈ Zs from the zero vector 0 ∈ Zs−1 .
Now let X denote n vector variables X1 , . . . , Xn such that each variable Xi can
be decomposed into s− 1 components xi,1 , . . . , xi,s−1 with i = 1, . . . , n, representing
the nonzero elements of Zs .
Remark 17. Note that the degree of a monomial of type X∆s a with a ∈ Zns is
defined as the weight of the vector a.
Given the rows of a generator matrix of the modular code C, labelled by w1 , . . . , wk
in Zns , we define the ideal associated to C as the binomial ideal
E
D 
S
{RXi }i=1,...,n ,
X∆s wi − 1 i=1,...,k
I+ (C) =

where RXi consists of all the binomials on the variable Xi associated to the relations
given by the additive table of the ring Zs , i.e.


{xi,u xi,v − xi,w | u + v ≡ w mod s}
RXi =
with i = 1, . . . , n.
{xi,u xi,v − 1 | u + v ≡ 0 mod s}
Remark 18. Note that the main difference of the set of generators describing the
ideal associated with a modular code, respect to the set of generators of the ideal
related with a Fq -linear code, is its cardinality. That is, for linear codes we need
to add all the multiples in Fq of each row wi , while for modular codes this is not
necessary. Moreover, the previous result can be extended for codes over Fp with p
prime since Fp ∼
= Zp .
Taking into account the new definition of the ideal associated to a modular code
we can apply all the results of this article to these types of codes. Therefore, now we
are not only able to compute the set of codewords of minimal support of modular
codes but also we provide a complete decoding algorithm for these codes.
6.2. Multiple Alphabets. Let C be a submodule of dimension k over the multiple
alphabets Zs1 × · · · × Zsn . For simplicity of notation we write es1 , . . . , ess−1 for
the canonical basis of Zs−1 .
Let X stand for n vector variables X1 , . . . , Xn such that each variable Xi can be
decomposed into si − 1 components xi,1 , . . . , xi,si −1 with i = 1, . . . , n representing

ON THE IDEAL ASSOCIATED TO A LINEAR CODE

25

the non zero element of Zsi . Let a = (a1 , . . . , an ) ∈ Zs1 × · · · × Zsn . We will adopt
the following notation:
∆ s 1 a1

X∆a = X1

∆

· · · X n sn

an

= (x1,1 · · · x1,s1 −1 )

∆ s 1 a1

· · · (xn,1 · · · xn,sn −1 )

∆ s n an

.

Similar to the modular case, given the rows of a generator matrix of C, labelled by
w1 , . . . , wk , we may define the ideal associated to C as the following binomial ideal:
I+ (C) =

D 

X∆wi − 1

i=1,...,k

S

{RXi }i=1,...,n

E

.

Remark 19. The main difference with the modular case is that the relations RXi
could be different for each i ∈ {1, . . . , n}.
With this new definition, all the results of this article are valid for these types of
codes.
6.3. Additive codes. Let Fq1 be an algebraic extension of Fq2 , i.e. q1 = pr1 and
q2 = pr2 where p is a prime number and r2 divides r1 . An Fq2 -additive code C of
parameters [n, k] over Fq1 is an Fq2 -linear subspace of Fnq1 .
In other words, given the rows of a generator matrix of C labelled by w1 , . . . , wk ∈
Fnq1 , the set of codewords of C may be defined as:
{α1 w1 + · · · + αk wk | αi ∈ Fq2 for i = 1, . . . , k} .
Let α be a primitive element of Fq2 . We check at once that the binomial ideal
associated to C is defined by the following binomial ideal

 n
o
S
j
{RXi }i=1,...,n ,
X∆α wi − 1 i=1,...,k
I+ (C) =
j=1,...,q2 −1

where RXi consist of all the binomials on the variable Xi associated to the relations
given by the additive table of the field Fq1 . Of course, the results obtained for Fq linear codes could be adapted to additive codes.
Conclusions. Complete decoding for an arbitrary linear code is proved to be NPhard. That is, from a computational point of view, our description could not provide
a polynomial time algorithm. However, we present a new complete decoding algorithm using the concept of Gröbner basis. This proposal was already presented
for the binary case before but the generalization to the non-binary case was not
possible with the previous approach.
It is outside the scope of this article but we are hopeful to achieve efficient
methods using this approach for special types of codes like cyclic codes or some
subclasses of cyclic codes such as Reed-Solomon codes and BCH codes since these
codes have a rich algebraic structure and we can take advantage of existing efficient
method to solve polynomial systems whose equations are left invariant by the action
of a finite group.
We would like to notice that during the (Google Summer of code of 2013) the
student Verónica Suaste (CIMAT, México) implemented Algorithm 2 and also a
decoding algorithm using a minimal test-set for inclusion in Sage. The code is
published at http://trac.sagemath.org/ticket/14973 and it will be included in next
releases of Sage. Note that in the project conclusions, there are some examples in
which the new decoding algorithm is faster than the classical syndrome decoding of
Sage.

26

I. MÁRQUEZ-CORBELLA, E. MARTÍNEZ-MORO AND E. SUÁREZ-CANEDO

REFERENCES
[1] M. Aliasgari, M.R. Sadeghi, and D. Panario. Gröbner Bases for Lattices and an Algebraic
Decoding Algorithm. IEEE Transaction on Communications, 61(4):1222–1230, 2013.
[2] A. Ashikhmin and A. Barg. Minimal vectors in linear codes. IEEE Trans. Inform. Theory,
44(5):2010–2017, 1998.
[3] A. Barg. Complexity issues in coding theory. In Handbook of coding theory, Vol. I, II, pages
649–754. North-Holland, Amsterdam, 1998.
[4] E. R. Berlekamp, R. J. McEliece, and Henk C. A. Van Tilborg. On the inherent intractability
of certain coding problems. IEEE Trans. Inform. Theory, IT-24(3):384–386, 1978.
[5] M. Borges-Quintana, M. A. Borges-Trenard, P. Fitzpatrick, and E. Martı́nez-Moro. Gröbner
bases and combinatorics for binary codes. Appl. Algebra Engrg. Comm. Comput., 19(5):393–
411, 2008.
[6] M. Borges-Quintana, M.A. Borges-Trenard, I. Márquez-Corbella, and E. Martı́nez-Moro. An
algebraic view to gradient descent decoding. In IEEE Information Theory Workshop (ITW),
pages 1 –4, 30 2010-sept. 3 2010.
[7] J. Bruck and M. Naor. The hardness of decoding linear codes with preprocessing. IEEE Trans.
Inform. Theory, 36(2):381–385, 1990.
[8] D.A. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms: An Introduction to
Computational Algebraic Geometry and Commutative Algebra. Number v. 10 in Undergraduate Texts in Mathematics. Springer, 2007.
[9] F. Di Biase and R. Urbanke. An Algorithm to Calculate the Kernel of Certain Polynomial
Ring Homomorphisms. Experimental Mathematics, 4(3):227–234, 1995.
[10] D. Eisenbud and B. Sturmfels. Binomial ideals. Duke Mathematical Journal, 84(1):1–45, 1996.
[11] J. C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero-dimensional
Gröbner bases by change of ordering. J. Symbolic Comput., 16(4):329–344, 1993.
[12] P. Fitzpatrick. Solving a multivariable congruence by change of term order. J. Symbolic Comput., 24(5):575–589, 1997.
[13] P. Fitzpatrick and J. Flynn. A Gröbner basis technique for Padé approximation. J. Symbolic
Comput., 13(2):133–138, 1992.
[14] D. Ikegami and Y. Kaji. Maximum Likelihood Decoding for Linear Block Codes using Grobner
Bases. IEICE Trans. Fund. Electron. Commun. Comput. Sci., E86-A(3):643–651, 2003.
[15] R. A. Liebler. Implementing gradient descent decoding. Michigan Math. J., 58(1):285–291,
2009.
[16] I. Márquez-Corbella and E. Martı́nez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Adv. Math. Commun., 5(2):233–244, 2011.
[17] I. Márquez-Corbella and E. Martı́nez-Moro. Decomposition of Modular Codes for Computing
Test Sets and Graver Basis. Mathematics in Computer Science, 6:147–165, 2012.
[18] E. Prange. Step-by-step decoding in groups with weight function. part 1. Air Force Cambridge
Research Labs Hanscom AFB MA, 1961.
[19] P. Samuel. Algebraic Theory of Numbers: Translated from the French by Allan J. Silberger.
Dover Books on Mathematics. Dover Publications, 2013.
[20] B. Sturmfels. Gröbner bases and convex polytopes, volume 8 of University Lecture Series.
American Mathematical Society, Providence, RI, 1996.

Received xxxx 20xx; revised xxxx 20xx.
E-mail address: irene.marquez-corbella@inria.fr
E-mail address: edgar@maf.uva.es
E-mail address: emilio.suarez@deic.uab.cat

