Determining When the Absolute State Complexity of a Hermitian Code Achieves Its DLP Bound.
Let g be the genus of the Hermitian function field $H/{\mathbb F}_{q^2}$ and let $C_{\cal L}(D,mQ_{\infty})$ be a typical Hermitian code of length n. In [Des. Codes Cryptogr., to appear], we determined the dimension/length profile (DLP) lower bound on the state complexity of $C_{\cal L}(D,mQ_{\infty})$. Here we determine when this lower bound is tight and when it is not. For $m\leq \frac{n-2}{2}$ or $m\geq \frac{n-2}{2}+2g$,  the DLP lower bounds reach Wolf's upper bound on state complexity and thus are trivially tight. We begin by showing that for about half of the remaining values of m the DLP bounds cannot be tight. In these cases, we give a lower bound on the absolute state complexity of $C_{\cal L}(D,mQ_{\infty})$, which improves the DLP lower bound.Next we give a "good" coordinate order for $C_{\cal L}(D,mQ_{\infty})$. With this good order,  the state complexity of $C_{\cal L}(D,mQ_{\infty})$ achieves its DLP bound (whenever this is possible). This coordinate order also provides an upper bound on the absolute state complexity of $C_{\cal L}(D,mQ_{\infty})$ (for those values of $m$ for which the DLP bounds cannot be tight). Our bounds on absolute state complexity do not meet  for some of these values of m, and this leaves open the question whether our coordinate order is best possible in these cases.A straightforward application of these results is that if $C_{\cal L}(D,mQ_{\infty})$ is self-dual, then its state complexity  (with respect to the lexicographic coordinate order) achieves its DLP bound of $\frac {n}{2}-\frac{q^2}{4}$, and, in particular, so does its absolute state complexity.
Introduction
Let C be a linear code of length n. Many soft-decision decoding algorithms for C (such as the
Viterbi algorithm and lower complexity derivatives of it) take place along a minimal trellis for
C. The complexity of trellis decoding algorithms can be measured by various trellis complexities.
The most common one is the state complexity s(C) of C, which varies with the coordinate order
of C. Since the number of operations required for Viterbi decoding of C is proportional to s(C),
it is desirable that s(C) be small. A classical upper bound for s(C) is the Wolf bound
dim(C)g, [9]. It is well-known that if C is a Reed-Solomon code, then
W(C).
Let [C] denote the set of codes equivalent to C by a change of coordinate order. We write s[C] for
the minimum of s(C) over all coordinate orders of C and call it the absolute state complexity of
Research supported by the U. K. Engineering and Physical Sciences Research Council under Grant L88764 at
the Algebraic Coding Research Group, Centre for Communications Research, University of Bristol. Copyright 2000,
Society for Industrial and Applied Mathematics.
C. (We note that state-complexity notation and terminology varies in the literature. For example,
state complexity is called minimal trellis size in [2]; absolute state complexity is called absolute
minimal trellis size in [2] and minimal state complexity in [13].) Finding a coordinate order of C
that achieves s[C] is called the 'art of trellis decoding' in [10] since exhaustive computation of s(C)
over all possible coordinate orders of C is infeasible, even for quite short codes. An important step
towards attaining this goal is determining good lower bounds on s[C].
The dimension/length prole (DLP) of C is a deep property which is equivalent to the generalised
weight hierarchy (GWH) of C. (For a survey of GWH, see [15].) The DLP of C is independent of
the coordinate order of C and provides a natural lower bound r(C) for s[C]. For example, if C is
a Reed-Solomon code, then so that s[C] is as bad as possible and uninteresting.
However, determining when important. An obvious and useful way of doing
this is to nd a coordinate order of C for which In particular this provides one
route to the art of trellis decoding. It is also important to develop methods for determining when
r(C) < s(C), and in these cases to improve on r(C).
Geometric Goppa codes generalise Reed-Solomon codes. Hermitian codes are widely studied geometric
Goppa codes which are longer than Reed-Solomon codes and have very good parameters
for their lengths. Let q be a xed prime power,
we write CL (D; mQ1 ) for a typical Hermitian code of length n dened over F q 2 . In [5], we
determined r(CL (D; mQ1 using some of the GWH of Hermitian codes obtained in [11, 16].
(The complete GWH of Hermitian codes has subsequently appeared in [1].) From [5], we have
s(CL (D; mQ1 so we restrict ourselves to
the interesting Hermitian codes i.e. to CL (D; mQ1
Here we determine precisely when r(CL (D; mQ1 In the process, we exhibit
a good coordinate order which often gives s(CL (D; mQ1 )) < W(CL (D; mQ1 )). We also improve
on the DLP bound (when it is strictly less than the state complexity).
'Points of gain and fall' were introduced in [3, 4, 6, 7] to help determine the state complexity
of certain generalisations of Reed-Muller codes. For these codes, the points of gain and fall had
particularly nice characterisations. For Hermitian codes however, their characterisation is not
quite as nice and so our approach is slightly dierent. We describe a coordinate order giving
and characterise the points of gain and fall of Cm . We also characterise these
points of gain and fall in terms of runs. This has the advantage of greatly reducing (from n to
the number of trellis depths needed to nd s(Cm ).
The paper is arranged as follows. Section 2 contains terminology, notation and some previous
results that will be used throughout the paper. The paper proper begins with Section 3. Here we
show that for m 2 I(n; g), just under half of the Hermitian codes cannot attain their DLP bound.
In these cases we give an improvement of the DLP bound, written r { (CL (D; mQ1 )).
The main goal of Section 4 is to characterise the points of gain and fall of Cm in runs. In Section
5 we determine s(Cm ) using Section 4. We show that s(Cm just over half the
Thus we have determined precisely when the DLP bound for Hermitian codes is tight. Furthermore
{ (Cm ) for around a further quarter (respectively 1=q) of m 2 I(n; g) when q is odd
(respectively even).
In conclusion, we have found s[Cm ] for three quarters (respectively one half) of the m 2 I(n; g)
when q is odd (respectively even). For the remaining m 2 I(n; g), we do not know a better
coordinate order (than that described in Section 4) nor a better bound (than that given in Section
3). Thus, although we have reduced the possible range of s[Cm ], some of its actual values remain
open. Finally, our method of characterising points of gain and fall is essentially the same as the
one used to determine r(CL (D; mQ1 )) in [5] and may be able to be used quite generally in
determining DLP bounds and state complexity.
We would like to thank Paddy Farrell for his continued interest and support of our work. An initial
account of some of these results was given in [8].
The state complexity of Hermitian codes has also been studied in [13]. For a stronger version of
[13, Proposition 1] (an application of Cliord's theorem), see [5, Proposition 3.4]. Also, Example
5.11 below generalizes the main result of [13] to arbitrary self-dual Hermitian codes.
Notation and Background
State complexity. Let C be a linear code of length n and 0  i  n. The state space dimension
of C at depth i is
where C 0g: The state
complexity of C is ng. It is well known that s(C ? simple
upper bound on s(C) (and hence on s[C]) is the Wolf bound dim(C)g.
We write [C] for the set of codes equivalent to C by a change of coordinate order i.e. C
if and only if there exists a permutation (l n) such that C
Cg. Then we dene the absolute state complexity of C to be
The dimension/length prole (DLP) of C is (k
ig. Clearly dim(C
(C). The DLP bound on s i (C) is
and the DLP bound on s(C) is ng. We will use DLP bound to mean
for some C. It is well known that r(C ?
Since r(C) is independent of coordinate order of C, r(C)  s[C]. If we say that C
is DLP-tight; e.g. if then C is DLP-tight.
Hermitian codes. Our terminology and notation for Hermitian codes for the most part follow [14].
We write H=F q 2 for the Hermitian function eld. Thus
over F q 2 and y q is the minimal polynomial of y over F q 2 [x]. The genus of H=F q 2 is
We write PH for the set of places of H=F q 2 and DH for the divisor group of H=F q 2 .
For for the valuation of z at Q. Thus v Q (z) < 0 if and
only if Q is a pole of z and v Q (z) > 0 if and only if Q is a zero of z. Also (z) 2 DH is given by
Q2PH vQ (z)Q and for A 2 DF ,
There are q 3 places of degree one in PH . One of these is the place at innity, which we denote
Q1 . We denote the others as . For the rest of the paper, unless otherwise stated
We put
. For an integer m, L(mQ1
The Hermitian codes over F q 2 are CL (D; mQ1
permutation (l Strictly speaking the code C(D;mQ1 ) depends on the
permutation (l n) and may be better denoted CL (Q l 1
this notation is cumbersome and CL (D; mQ1 ) is standard. Unless otherwise stated, when we write
CL (D; mQ1 ) we have some xed but arbitrary coordinate order in mind.
From the usual expression for the dimension of geometric Goppa codes,
dim(CL (D; mQ1
When m is understood, stated otherwise. The abundance of
CL (D; mQ1 ) is dim(mQ1 D). For m < n, the abundance is 0 and the code is non-abundant.
For
, so we restrict
our attention to m 2 m, the dual of CL (D; mQ1 ) is
be the pole number sequence of Q1 . Also, for
ig. Thus [1; 1) is the set of pole numbers
of Q1 , (r) is the rth pole number and  1 [R 1 g. We note that
From [14, Proposition
VI.4.1] we deduce that
We note that, for m < n,
State complexity of Hermitian codes. For 0  i  n we put D
(where (l xed but arbitrary permutation of We deduce that
In particular
These identities yield s(CL (D; mQ1
Thus we will almost exclusively be interested in m 2 I(n;
In fact, since
restrict our attention
to
deducing results for
It is convenient to put J(n;
Using results of [11, 16], [5, Proposition 5.1] shows
that for m 2 I(n; g),
which is used to prove
Theorem 2.1 ([5, Theorem 5.5]) For
is attained at m 2g
2 cq and equals
min
l um
If CL (D; mQ1 ) is DLP-tight then we just say m is DLP-tight.
3 When the DLP bound is not tight
by [5, Proposition 4.3, Example 4.9], we have
r(CL (D; mQ1
r(CL (D; mQ1
where CL (D; mQ1 ) can have any coordinate order. Such m are therefore DLP-tight and we are
reduced to determining which m 2 I(n; g) are DLP-tight. We note that n 3+ 2g < n, so that the
codes that we are interested in are non-abundant.
In this section we determine the m 2 I(n; g) which are not DLP-tight, i.e with s[CL (D; mQ1 )] >
r(CL (D; mQ1 )): The coordinate order of CL (D; mQ1 ) is arbitrary, so it suces to show that

Table

1: Table of New Notation
xed prime power
r { (CL (D; mQ1 Improved DLP bound for m 2 I(n; g) Denition 3.11
{ (CL (D; mQ1 (Theorem 3.9 and Corollary 3.10)
Finite places of degree one in PH
ab Elements of F q 2 such that  q+1
ac Elements of F q 2 such that  q
Element of P 1
H such that x(Q a;b;c ab and y(Q a;b;c
Cm Element of [CL (D; mQ1 )] with coordinate order given in Section 4
of points of gain and fall of Cm
fall (m) jP gain (m) \ [1; i]j and jP fall (m) \ [1; i]j
by (j;
gain 0; q q2; q depending on M  : dened before Proposition 4.8
fall 0; q+q2
depending on M  : dened before Proposition 4.8
3:
Our approach has three steps.
(i) we prove the key lemma, Lemma 3.2, and indicate how this can be used to show that m is not
DLP-tight (Example 3.3)
(ii) a generalisation of the key lemma (Lemma 3.4) and an application 3.5. We indicate how this
can be used to improve on the DLP bound by more than one (Example 3.6).
(iii) an application of Proposition 3.5 to improve the DLP bound for m 2 I(n; g), Theorem 3.9
and Corollary 3.10.
We conclude Section 3 with a table of the improved DLP bound for small values of q and an
analysis of the proportion of those m 2 I(n; g) for which our bound is strictly better than the DLP
bound (Proposition 3.12).
The key lemma. We begin with a clarication of Equations (3) and (4).
Lemma 3.1 For
dim(mQ1 D
and s i (CL (D; mQ1 only if there is equality in both.
Proof. The rst part follows from [5, Lemma 4.1] and the fact that the gonality sequence of
the pole number sequence of Q1 by [12, Corollary 2.4]). The second part then
follows from (3) and (4). 2
We note that Lemma 3.1 implies that a coordinate order is inecient, in the sense of [9], if and only
if there exists an i, 0
dim(mQ1 D i;+ ). To show the stronger result that s(CL (D; mQ1
require a stronger condition on i, namely that it satises
so that s i (CL (D; mQ1 This stronger condition is clearly more likely to hold
attains or is close to attaining r(CL (D; mQ1 )).
For now, we concentrate on determining when the equalities in (5) cannot hold. For these equalities
to hold, dim(mQ1 D must change with
respectively. We shall see that it is possible for both
(i.e. it is possible that both
are pole numbers of Q1 ).
Lemma 3.2 For m  n 2+g, it is not possible that dim(mQ1 D
and dim(mQ1 D i;+
Proof. We assume that dim(mQ1 D
derive a contradiction. Suppose we have z
is a principal divisor of H=F q 2 (e.g.
as in the proof of [14, Proposition VII.4.2]), say nQ1
and vQ l i
so that by [14,
Lemma I.4.8])
dim((2m n)Q1 +Q l i
Now (2g 2)Q1 is a canonical divisor of H=F q 2 (e.g. by [14, Lemma VI.4.4] or because 2g 2
is the gth pole number of Q1 and [14, Proposition I.6.2]). Thus dim((2m n)Q1
by the Riemann-Roch theorem, so from (6),
Again by the Riemann-Roch
theorem dim((2g so that
and hence L((2g 2 2m+n)Q1 Q l i
giving the
required contradiction. 2
Example 3.3 Let 3. We show is not DLP-tight.
From (2), we have [1; 11. From Theorem 2.1,
r(CL (D; mQ1
and similarly, r 14 (CL (D; mQ1
implies that s i (CL (D; mQ1 3.1 then implies that
dim(mQ1 D 13;
dim(mQ1 D 14;+
and since the coordinate order of CL (D; mQ1 ) is arbitrary, m is not DLP-tight.
We will see in Section 5 that 14 and 15 are DLP-tight.
Generalisation of the key lemma. Since dim(mQ1 D i
dim(mQ1 Lemma 3.2 can be restated
as: for m  n 2+ g, either dim(mQ1 D i
dim(mQ1 D i 1;+ ). This generalises as
Lemma 3.4 For
or (ii) dim(mQ1 D i;+ )  dim(mQ1 D i t;+
Proof. Suppose that dim(mQ1 D
tc. So there are
such that dim(mQ1 D
dim(mQ1 so that, since jfi t
contradicting Lemma 3.2. 2
The following application of Lemmas 3.1, 3.4 is a straightforward consequence of (3),(4).
Proposition 3.5 For
Example 3.6 Let
We have (e.g. by the Riemann-Roch Theorem). From (2), the rst few pole numbers of
Q1 are [1; 16g. From Theorem 2.1, we have r(CL (D; mQ1
so that, from (4),
8g. Thus Proposition 3.5 gives
We shall see in Section 5 that s[CL (D; mQ1
Improvement on the DLP bound. We show how Proposition 3.5 can be used to improve on
the DLP bound generally. First, we introduce some useful notation: q is even and q
if q is odd. For a xed m 2 J(n; g), we put
We easily deduce:
Lemma 3.7 (i) for q odd, 0  M   q 3
We begin by reinterpreting Theorem 2.1 in terms of M  and M  .
Lemma 3.8 For m 2 J(n; g), the DLP bound is attained at
Proof. If u; v are dened as in Theorem 2.1, then
The result now follows from the fact that the DLP bound is attained at m 2g
Next we give our improvement on the DLP bounds for m 2 J(n; g). The size of the improvement
is given by
We note that (m) > 0 if and only if q q2
2 or q M   M   q q 2 .
Theorem 3.9 For
Proof. First assume that q q2
is attained at
We have two subcases.
(a) For q q2
2 we have 0 < t  M  +q 2 . Now, from (2), M
1), so that j 1 [m t, and Proposition 3.5 gives
2:
(b) For q M  M   q 2+q2we have From (2),
2 (N) since M   q 2, so that j 1 [m+i n t+1; m+i
Suppose now that q M   M   q q 2 . From Lemma 3.8, r(CL (D; mQ1 )) is attained at
3.5. Now again we have two subcases.
(a) For q M   M   q M  +1
2 we have 0 < t  M  +1 q 2 . From (2) (M  +1 q
t, and Proposition
3.5 gives s[CL (D; mQ1 )] r(CL (D; mQ1
(b) For q M  M   q q 2 we have M  From (2)
so that j 1 [m so that from Proposition 3.5,
Corollary 3.10 For
Proof. Easy consequence of Theorem 3.9, the denition of (m). 2
Definition 3.11 For m 2 I(n; g), we put r { (CL (D; mQ1
We note that for m 2 I(n; g),
r { (CL (D; mQ1
In

Table

2 we have written r { (m) for r { (CL (D; mQ1 ) and the DLP bound is calculated using
Theorem 2.1. The bold face entries are those for which r { (CL (D; mQ1
(The values of r { (CL (D; mQ1
can of course be deduced from (7).)

Table

2: r { (CL (D; mQ1
r { (m) 3
r { (m) 11 11 11
r { (m) 26 27 27 28 28 28
r { (m) 53 53 54 54 55 56 56 56 56 56
r { (m) 151 151 152 153 153 154 155 156 156 156
r { (m) 157 157 157 158 159 159 159 159 159 159 159
r { (m) 228 229 230 231 231 232 233 234 234 234 235 236 236 236
r { (m) 237 238 238 238 238 239 239 239 239 240 240 240 240 240
We conclude this section by calculating the proportion of m 2 I(n; g) for which (m) > 0.
Proposition 3.12
if q is odd2
Proof. We note rst that jI(n; 1. Recall from the denition of (m) that
Next we note that j 1 (0;
This follows from the denition of (m)
for when q is odd and from n 2+
when q is even. Now,
xing
We note that the restriction M   q 1
does not aect
this. We also note that for q even and M
2 , the restriction of M
Thus the result follows from
is even:Thus, for large q at least, r { (CL (D; mQ1 )) improves on r(CL (D; mQ1 )) for just under half the
We shall see in Section 5 that m is DLP-tight when r { (CL (D; mQ1 )) fails to improve
on r(CL (D; mQ1 )).
4 A Good Coordinate Order
We describe a 'good' coordinate order for Hermitian codes, denoting the code in [CL (D; mQ1 )]
with this coordinate order by Cm . After recalling the notions of points of gain and fall for a linear
code, we give the most natural description of the points of gain and fall of Cm in Propositions 4.2
and 4.4. We conclude by characterising the points of gain and fall of Cm as 'runs' in Theorem 4.10
(which we will use in Section 5 to derive a formula for s(Cm ) .)
The good coordinate order. As noted at the beginning of Section 3, for m  n 2
coordinate orders of CL (D; mQ1 ) are equally bad with regard to state complexity.
Thus we are interested in m 2 I(n; g).
Recall that H=F q 2 has places of degree one viz. Q1 , and the nite places of degree one,
for some xed but arbitrary ordering (Q l 1
H . Thus the order of P 1
H determines the
coordinate order of CL (D; mQ1 ). As in [14], for each (;
there exists a unique
H , such that x(Q
We now describe an order of P 1
H giving Cm 2 [CL (D; mQ1 )]. First we relabel the elements of P 1
as Q a;b;c for certain integers a; b; c. We write f0; Now for each
a 2 F q nf0g there exist  such that  q
for q. Thus for each a 2 F q n f0g, 0  c  q 1 and 0  b  q, there
exists
H , such that x(Q a;b;c
H .
For exist
Thus the remaining q elements of P 1
H , which we write as Q 0;0;c for 0  c  q 1, are such that
We note that Q
When a, b or c takes any of its possible values we write Q ;b;c , Q a;;c or Q a;b; . Note that for a
we have q. Thus there are q places of the form Q 0;;
and for 1  a  q 1 there are q 2 1 places of the form Q a;; .
We rst describe the ordering of P 1
H giving Cm 2 [CL (D; mQ1 )] for m 2 J(n; g). This uses
lexicographic order of t-tuples of integers: (i only if there exists u
such that
is dened by simply using the order
of
H . For q M  1
, Cm is dened by the'Order O2' of P 1
H into
three sets
Then Order O2 of P 1
H is given by putting P 1
3 by Q 1;b;c < Q
2 by Q a;b;c < Q a 0 ;b 0 ;c 0 if (a; b; c) < (a
For
the coordinate order of Cm is dened to be that of Cm ? .
From now on Q i denotes the ith element of P 1
H ordered as above. Thus
The points of gain and fall of Cm . Points of gain and fall were introduced in [3, 6]. For this
paragraph, C is a length n linear code with dimension k. We note that dim(C i; ) (as dened in
Section 2) increases in unit steps from 0 to k and dim(C i;+ ) decreases in unit steps from k to 0 as
i increases from 0 to n. If 0  i  n then
i is a point of gain of C if dim(C i;+
i is a point if fall of C if dim(C
These denitions are motivated by (1). We note that there are k points of gain and k points of fall.
Points of gain and fall describe the local behaviour of a minimal trellis, [6], and being able to give
a succinct characterisation of them for particular families of codes has been useful in calculating
for their state complexity, e.g. [3, 6]. The same proves to be the case here. We note that,
as in [6], i is a point of gain of Cm if and only if i is the 'initial point' of a codeword of Cm i.e. if
and only if there exists z 2 L(mQ1 ) such that
Similarly i is a point of fall of Cm if and only if i is the 'nal point' of a codeword of Cm i.e. if
and only if there exists z 2 L(mQ1 ) such that
We write P gain (C) and P fall (C) for the sets of points of gain and fall of C. With P
fall (C):
We also write P gain (m) := P gain (Cm ) and P fall (m) := P fall (Cm ).
We will need a function  closely related to . Dene
We have [1; Im() from [14]. We note that
and for m < Proposition VII.4.3]. For 0  a  q 1, we put
and
Also we
put
a=0 A(a) and
We will determine the initial and nal points of certain z 2 H=F q 2 of the form
that (x  ab )(Q a 0 ;b only if a =
a only if a = a course, we are interested in
when
Lemma 4.1 If (j; l) 2  1 [0; m],
Proof. We put z Using the facts
that (i) vQ1
fQ1g. Hence (j; l) 2  1 [0; m] implies that z jl 2 L(mQ1 ). 2
Proposition 4.2 (O1 ordering of P 1
1. P gain
2. P fall
Proof. We order the set A by  ab <  a 0 b 0 if and only if (a; b) < (a
and only if Q a;b; < Q a 0 ;b 0 ; . For 0  d  q 2 1, we write  d for the (d 1)st element of A.
Thus
a(d) by
Thus
and
(y  ac
We begin with P gain (m). For (j; l) 2  1 [0; m] we put
We note that jq  (j; l)  m  n 2
which implies that j < q 2 +q 1
that u gain
jl and z gain
jl are well-dened for all (j; l) 2  1 [0; m]. Now u gain
only
Hence the initial point
of z gain
jl is jq Also, by Lemma 4.1, z gain
Finally,
each (j; l) 2  1 [0; m] gives a dierent point of gain of Cm and, since j 1 [0; are
all the points of gain. Similarly for points of fall. 2
We use Proposition 4.2 to determine s(Cm ) for
To do this we use
and so we put
gain
fall
fall (Cm
Example 4.3 If
C 4 is our rst example of a geometric Goppa code with
where the latter is given by Theorem 2.1.)
Proof. The coordinate order of C 4 is Q
In the notation of Proposition 4.2, we have
Now P gain (4) is the set of initial points of z gain
jl , where (j; l) 2  1 [0; 4]. These are given in the table
below. The third column in the table gives the 'initial place' i.e. the Q a;b;c such that Q
where i is the initial point.
(j; l) z gain
jl Initial Place Initial Point
Thus P gain given by the nal points of z fall
jl such that (j; l) 2
(j; l) z fall
jl Final Place Final Point
Thus P fall using (9) we have
gain
giving
For
2:
Proposition 4.4 (O2 ordering of P 1
gain (m) and P fall
fall (m) where
Proof. We recall that P 1
3 were dened in (8). We note that
1 , so that writing
and
for  gain (q
2 and
for  gain (q
3 .
We begin by showing that P 1
gain (m)  P gain (m). For (j; l) 2  1 [0; m] such that 0  j  q and
we exhibit an element of L(mQ1 ) with initial point
Thus v gain
l (Q a;;c only if a = 1, and 0  c  l 1 and u gain (Q a;b; only if
l
(taking
q). Hence the initial point of z gain
jl is 1. Also, from Lemma 4.1,
z gain
gain (m)  P gain (m).
Next we show that P 2
gain (m)  P gain (m). We order A n A(1) by  ab <  a 0 b 0 if and only if (a; b) <
for the (d+1)st element of AnA(1), where 0  d  q 2 q 2. (This is dierent
from the labelling in the proof of Proposition 4.2 since we do not include A(1) in the relabelling.)
We dene a(d) by
writing
set
z gain
We note that jq  (j; l)  m  gain (q which implies that j  q 2 q 2.
Thus
jl and z gain
are well-dened for all (j; l) 2
jl (Qd a(d)c l 1.
Thus
Therefore the
initial point of z gain
is  gain (q
and (z gain
Hence z gain
gain  P gain (m) and
gain (m)  P gain (m).
it remains to show that jP 1
To do this we exhibit a bijection  1 [0; m] !
gain (m). First, for (j; l) 2  1 [0; m] we map (j; l) to l(q
gain (m) if
Now we are left with dening a bijection F :
gain (m) by
F (j;
(j
It is easy to check that F maps into P 2
gain (m) and F is one-to-one since for  gain  l  q 1 and
Finally we prove F is onto.
For
gain (m), such that
(j
(j
It is straightforward to see that (i) (j
This completes the proof for P gain (m). Similarly for the points of fall. 2
Example 4.5 If
{ (CL (D; 13Q1 using Theorem 3.9, but s(C 13
Proof. The coordinate order of C 13 is
We use the notation of the proof of Proposition 4.4. We note that  gain = 1. Thus for 0  j  q
and 0  l   gain 1, jq
gain (13) is the set
of initial points of z gain
which are as follows.
(j; l) z gain
jl Initial Place Initial Point
(3;
Thus
gain (13). Now we have
so that 2. Then P 2
gain (13) is the set of initial points of
z gain
such that (j; l) 2  1 [0; 13  gain (q
giving the following.
Initial Place Initial Point
(0;
(0;
Thus
for P fall (13). We have P gain
From Propositions 4.2 and 4.4 we have, if (i) 0  M   q M  2or (ii) q M  M   q or (iii)
In these cases the
following useful property holds.
Remark 4.6 For a length n code C, if P fall
In particular, for m 2 J(n; g), if (i) q is odd and 0  M   q M  2or q M  M   q
or (ii) q is even and 0  M   q, then s i (Cm n. The same holds for
Proof. The proof is similar to that of [6, Proposition 2.5], and in fact can be modied to hold
for branch complexity as in [6, Proposition 2.5]. We put P i;+
Of course, with
gain (C) and P i;+
fall (C)
for any linear code C. The condition P fall implies that also
fall (C) and P
gain (C):
Thus, from (9), we have
gain (C)
is ordered by O1 then as in the proof of Proposition 4.2
so that
by O2, P gain
Thus O2 is strictly better than O1 for m=14.
If C 2 [CL (D; 15Q1 )] is ordered by O1, then then as in the proof of Proposition 4.2, P gain
But if C is ordered by O2, we get P gain
Thus O1 is strictly better than O2 for m=15.
To summarise, for { (CL (D; mQ1 )). Thus, in these
cases s(Cm and the coordinate order for Cm is optimal with regard to s(Cm ).
In fact, except for
Another characterisation of the points of gain and fall of Cm . We now characterise
gain (m) and P fall (m) as runs i.e. as sequences of non-contiguous intervals of integers. This is
useful since s(Cm ) must be attained at the end of a run of points of gain. Thus to determine
s(Cm ), we only need to nd the maximum of s i (Cm ) over those i that end a run of points of gain,
i.e. over those i such that
We begin by combining Propositions 4.2 and 4.4 for a common development of the cases (i) 0
2 or q M
. First we extend the
denitions of  gain and  fall as follows:
and
Proposition 4.8 For
gain (m) and P fall
fall (m) where
Proof. From the examples above and Remark 4.7, we can assume that q  4. For q M  2
M   q M  +1, the result is just a restatement of Proposition 4.4. Also, for
the result states that P gain
in agreement with Proposition 4.2.
So we are reduced to m such that q M
Rewriting
see that P 1
qg.
We claim that P 2
1g. Firstly, if 0  j  q and
4. Thus we need to show that
If k is in the left-hand side,
(l
In either case, 0  j  q, 0  l  q 1 and l(q that k is in the
right-hand side. The reverse inclusion is similar.
The result now follows from Proposition 4.2 since for q M
gain (m)+1
and
Lemma 4.9 If
2.
Proof. Straightforward using Lemma 3.7. 2
Theorem 4.10 For
1. P gain (m) is the union of
(b) fm 2g  gain
(c) fm 2g  gain
and
2. P fall (m) is the union of
(a) [n m+ 2g
(b) fn m+ 2g
(c) fn m+ 2g
Proof. As in the proof of 4.8, we assume that q  4. We will use the fact that
For convenience we put R 1
e  q
We show that R 1
gain (m)  P gain (m) in two steps. First we note that P 1
since for q  4, 0  j  q and 0  l   gain 1  q 1, (j; l)
Next we show that [ gain (q
gain (m). Now from (10) we have for
and 0  l  q 1:
Also, if 0  j
and 0  l  q 1 then, again using (10),
(j; l)
so that (j; l) 2
gain (m). Next we show that R 2
gain
gain 1. Then, from (10),
and using (10),
gain (m) if (e
that R 2
gain
gain (m). If q 1  gain  e  q 1 and 0  f  q 1 e then
and f   gain , so that R 3
gain
gain (m).
Thus
gain (m)  P gain (m) and it suces to show that j
that jP gain
[
gain (m)
The proof for P fall (m) is similar and we omit the details. 2
5 When the DLP bound is tight
Here we use Theorem 4.10 to determine s(Cm ). We know (from Corollary 3.10 and Proposition
3.12) that s[CL (D; mQ1 )] > r(Cm ) for just under half of the m in the range I(n; g). We show
that for the remaining m in this range, s(Cm As a consequence, we have determined
s[CL (D; mQ1 )] and a coordinate order that achieves s[CL (D; mQ1 )] for such m. For those m
with s(Cm ) > r(CL (D; mQ1 )) we compare the upper bound, s(Cm ), on s[CL (D; m1 )] with the
lower bound r { [(C L (D; mQ1 )] given in Corollary 3.10. When q is odd, these bounds meet for
over three-quarters of those m in I(n; g), but when q is even, the bounds meet for only a little over
one half of those m in I(n; g).
Determining s(Cm ). As discussed in Section 4, it suces to nd the maximum of s i (Cm ) over
those i such that
(m). From Theorem 4.10, there are only q
i. Thus concentrating on these i is signicantly simpler. So we calculate s
values of i (in Proposition 5.5) by determining P
gain (m) and P
fall (m) (in Lemmas 5.1 and 5.4).
We determine which of these i gives the largest s i (Cm ) (in Lemma 5.6). This enables us to write
Theorem 5.7).
Early on we introduce a variable which plays a crucial role in the proofs and statements
of many of the results and we end with a table of s(Cm
8g.
We begin by determining s(Cm We note rst that
were dened just before Proposition 4.8.
As noted above, s i (Cm
From
Theorem 4.10 such i are either (i) of the form m 2g  gain
or (ii) of the form m 2g
Thus putting
we have
From
gain (m); so we wish to determine P
gain (m) and P
fall (m) for
1. The rst of these is straightforward.
Lemma 5.1 For
Proof. Since 1. For 1  e  q 2  gain , Theorem 4.10
gives
e
The rst case follows since
In the
second case,
q e
fall (m) it is convenient to introduce some more notation. For xed m we put
Thus  norm is 0, 1 or 2 depending on whether
Also we put
3:
In Lemma 5.4 and Propositions 5.5 we will see a symmetry between the roles of e in P
gain (m)
and  e in P
fall (m). We will see in Lemma 5.6 that s i e (Cm ) is maximised near and hence
appears naturally in our formula for s(Cm ).
Lemma 5.2 q 1    2q 3.
Proof. First, it follows from Lemma 3.7 that
is even and M  > 0
is even and M
Next, clearly   2q 2, with equality only if M 1. However, from Lemma
2 so that  norm  1. 2
Now, in order to use Theorem 4.10 to calculate P
fall (m), we need to write i e as n m+2g+ fall
preferably non-negative, integer e 0 and 0  f  q 1. We could then determine
an expression for
fall (m) in terms of e 0 and f in a similar way to the proof of Lemma 5.1, except
that f would add complications. This would give us an expression for s i e (Cm ) in terms of e, e 0
and f . To maximise this over 1  e  q 1 we would need to relate e 0 and f to e. Fortunately
these relationships are reasonably simple.
Lemma 5.3 Let m 2 I(n; g) and 1  e  q 1. If we write
then e
e for q 1  gain  e  q 1.
In particular e 0  0. Also if e   q
Proof. For
Now
giving norm )q which implies that
e. Similarly, for q 1  gain  e  q 1 we get
For the second part we have   q 1 (from Lemma 5.2) and f  e (from the rst part). Thus
We show that, for e   q
it is not possible that Firstly implies that e  q 1  gain . Also
imply that e   fall . Thus q 1  gain  e   fall so that,
adding  gain to both sides,
Now, as in (12), implies that either (i)
2 and
Each of these clearly contradicts (13). 2
Lemma 5.4 For
Proof. We as in Lemma 5.3 and work from
Theorem 4.10.
First, if e 0  q, i.e. if e   q, then P
We note also that, for e   q, q
Next, if q 1  fall  e 0  q 1, i.e. if  q
the last equality following from the second part of Lemma 5.3. Finally (since e 0  0 by Lemma
and q  since   q 1 and f  e, by Lemma 5.3. 2
We use the convention that, for b  0, a
In particular
a
a for a  0
0 for a  0,
a
1 for a  0
0 for a < 0,
a
a 1
a 1
where b  1. Lemmas 5.1 and 5.4, together with (9), give
Proposition 5.5 For
Now we determine for which e, 1  e  q 1, s i e (Cm ) is maximised.
Lemma 5.6 For
1. at
2. at
Proof. From Proposition 5.5, with
q e
we have s i e (Cm maximising s i e (Cm ) is equivalent to minimising (e) over 1
e  q 1. Now, for 0  e  q 1,
q e
Thus, since 0  q 2  gain e  1, we have
First, for 0  e   q implies that (e) (e 1)   2q so that (e) is
minimised over 1  e   q + 1 at 1. Thus it is sucient to determine where (e)
is minimised over  q We note that, since   2q 3 (Lemma 5.2),
l m
Similarly, for  q
that if e  b
1. if d e   q
2. if b
e.
This leaves the case b
. In this case, the
above analysis implies that (e) is minimised at either b
d
Also we have
fall  gain
so that (e) is minimised at d e.
Finally we note that if   2q 3 2 fall then   2q so that adding
sides and dividing by 2 gives
l m
and we are in case 1 above. Also if we have d
we are in case 1. Similarly for   2q 6 2 fall we are in case 2 above. 2
Proposition 5.5 and Lemma 5.6 give us
Theorem 5.7 For
Proof. The result follows since
1. for   2q 6 2 fall , q 2  gain b
2. for
3. for   2q 4 2 gain , q 2  gain d
For example,   2q 6 2 fall implies that b
so that
The other equalities and inequalities follow similarly. 2
Of course, Theorem 5.7 essentially gives the values of s(Cm ) for I(n; g) since

Table

Comparing these values of s(Cm )
with the values of r { (CL (D; mQ1 )) given in Table 2 (where r { (CL (D; mQ1 )) is as dened in
Denition 3.11), we have s(Cm { (CL (D; mQ1 )) except for
281g. In particular, s(Cm ) achieves
the DLP bound for Cm for q 2 f2; 3; 4; 5; 7; 8g and m 2 I(n; g) when this is not excluded by
Corollary 3.10 i.e. whenever the entry for m or m ? in Table 2 is not in boldface.

Table

3: s(Cm ) for q 2 f2; 3; 4; 5; 7; 8g and m 2 J(n; g)
28 28 28
Comparing s(Cm ) with r { (CL (D; mQ1 )) We start by reinterpreting r(CL (D; mQ1 )) in terms
of  in Theorem 5.8. We use this to calculate (in Proposition 5.9) and hence to show (in Corollary
5.10) that s(Cm this is not excluded by Corollary 3.10 . This means
that s(Cm ) achieves the DLP bound for Cm for just over half of those m in the range [
We then compare s(Cm ) with r { (CL (D; mQ1 )) in Table 4 and see that s(Cm ) achieves the bound
r { (CL (D; mQ1 )) for approximately a further quarter of those m in [ n 1; n 3+2g] if q is odd but
only for about a further 1=q of those m in [ n 1; n 3+ 2g] if q is even.
Previously we partitioned J(n; g) into three subintervals, according to whether 0  M   q M  2
Now we consider a ner partition and say that
according to whether (A) 0  M   q 2
2 or
We compare s(Cm ) with r { (CL (D; mQ1 )), by reinterpreting Theorems 3.9 and 5.7 using (A){(E).
Theorem 5.8 If m 2 J(n; g), then
r(CL (D; mQ1
Proof. Take u and v as in the statement of Theorem 2.1. It is straightforward to show, using
the characterisation of (u; v) given in the proof of Lemma 3.8, that if m satises (A), (C) or
2. Thus Theorem 2.1 implies that, for m satisfying (A), (C) or (E),
r(CL (D; mQ1
min
and for m satisfying (B) or (D),
r(CL (D; mQ1
min
l m
First, for m satisfying (A), (C) or (E) we have (i) d +1e  q M  1 if  norm 2 f0; 1g or (ii)
2. Also  gain
or (iii) for  . Thus, for m satisfying (A), (C)
or (E), r(CL (D; mQ1 )) is equal to
as required. Similarly, for m satisfying (B) or (D) (so that  norm  1) it is easy to see that
(by considering the cases that
1. Thus, for m satisfying (B) or (D),
r(CL (D; mQ1
as required. 2
Before comparing s(Cm ) with r { (CL (D; mQ1 )), we compare it with r(CL (D; mQ1 )). To do this
we rene (A){(E) as follows: if m satises (C) then we say that m satises (C1), (C2) or (C3) if
Proposition 5.9 For
Proof. Using it is straightforward to see that if
1. if m satises (A), (B), (D) or (C3), then   2q 2 fall 4,
2. if m satises (C1) or (E), then   2q 6  fall or
3. if m satises (C2), then
Also, if
The result then follows from Theorems 5.7 and 5.8 noting that, for cases (B) and (D),  gain
cases (C1) and (E) with M   q 1,
It follows from Proposition 5.9 that s(Cm ) achieves the DLP bound for Cm as often as this is
possible. We state this as
Corollary 5.10 For only if
Proof. Since for
and s(Cm suces to show the result for m 2 J(n; g). It follows from the denition
of (m) for such m that only if (i) m satises (A) or (ii) m satises (C3) or (iii)
q. These are exactly the values of M  for which Proposition 5.9 implies that
Example 5.11 If Cm is self-dual, then r(Cm where Cm has the lexicographic
coordinate order. In particular, s[Cm We know that q is a power of 2,
g). From the
denitions,
4 by Theorem 5.8. The result
now follows since
We remark that the main result of [13] is Example 5.11 with q  4. Corollary 5.10 and Proposition
3.12 imply that r(Cm ) is attained for just over half the m 2 I(n; g). Explicitly, the proportion of
these m for which the DLP bound is attained is 1+ 1
for q odd and 1+ 3q 5
for q even. Of
course Corollary 5.10 implies that if m satises (A), (C3) or M  = q is odd, then
s[CL (D; mQ1
The bounds on s[CL (D; mQ1 )] given by Theorem 3.9 and Proposition 5.9 for all m in J(n; g)
(and hence implicitly also for
are given in Table 4. The lower bound is

Table

4: Table of Bounds on s[CL (D; mQ1
Lower Bound Upper Bound
satises r(CL (D; mQ1))+ r(CL (D; mQ1))+ Range
(D) M  +M
r { (CL (D; mQ1 )) and the upper bound is s(Cm ). The entries for both bounds are the amount by
which they exceed r(CL (D; mQ1 )). The range is the upper bound minus the lower bound.
As well as those m for which s(Cm implies that
{ (CL (D; mQ1
for those m 2 J(n; g) such that
if q is odd
Hence (15) also holds for those
In all these
cases except M   2 and M
s[CL (D; mQ1
For
3 we have
s[CL (D; mQ1 2:
For q odd, this gives q 2 1values of m 2 I(n; g) for which s[CL (D; mQ1 )] is determined but is
strictly greater than r(CL (D; mQ1 )). Thus, for q odd, the total proportion of those m in I(n; g)
for which we have determined s[CL (D; mQ1 )] is2
For q even, it gives q 2 values of m 2 I(n; g) for which s[CL (D; mQ1 )] is determined but is
strictly greater than r(CL (D; mQ1 )). Thus, for q even, the total proportion of those m 2 I(n; g)
for which we have determined s[CL (D; mQ1
Thus we have determined s[CL (D; mQ1 )] for over three quarters of those m in I(n; g) when q is
odd but only for something over one half of those m in I(n; g) when q is even. For q odd, the rst
m for which s[CL (D; mQ1 )] is not determined is (when it is either 56 or 57),
and for q even the rst m for which s[CL (D; mQ1 )] is not determined is
it is either 236 or 237).



--R

The Weight Hierarchy of Hermitian codes.

On the state complexity of some long codes.
On the trellis structure of GRM codes.
Lower bounds on the state complexity of geometric Goppa codes.
On trellis structures for Reed-Muller codes
On a family of abelian codes and their state complexities.
Bounds on the state complexity of geometric Goppa codes.

Foundation and methods of channel encoding.
On the generalized Hamming weights of geometric Goppa codes.
On special divisors and the two variable zeta function of algebraic curves over
Bounds on the State Complexity of Codes from the Hermitian Function Field and its Sub
Algebraic Function Fields and Codes.
Geometric approach to higher weights.
On the weight hierarchy of geometric Goppa codes.
--TR

--CTR
T. Blackmore , G. H. Norton, Lower Bounds on the State Complexity of Geometric Goppa Codes, Designs, Codes and Cryptography, v.25 n.1, p.95-115, January 2002
hermitian code;dimension/length profile bound;state complexity