Lexicodes

In order to compute
we will first transform the generator
matrix of the code into a minimal span generator matrix (`MSGM`) form,
in which the sum of the spans of the generators is minimized.
Adapting the notation in [11], the span of a binary *n*-vector
*x* = (*x*_{1}, *x*_{2}, *x*_{3},..., *x*_{n}) is
, where
and
are the rightmost (i.e., largest) and leftmost (i.e., smallest)
index *i*, respectively, such that
*x*_{i} 0. Thus,
the span of the vector
*x* = (0001001100) is
. We
can efficiently transform any matrix into `MSGM` form using the greedy
algorithm in [11]. We note that two vectors of an `MSGM`
cannot have their leftmost or their rightmost index in common, or else
they may be added to produce a generator matrix with shorter span.

Given an `MSGM` for a code and a set of coset representatives
,
Method 1 computes the lexicographically earliest vector among
the cosets represented in
.

1. for eachv= (v_{1},v_{2},v_{3},...,v_{||}) do

2. forifromndown to 1

3. if is a 1 then

4.vv+G_{i}

5. store the modifiedv

6. among all storedv, return the lexicographically earliest

This method looks for the generators whose left-most 1-bit corresponds
to 1-bits in vectors
*v**V*.
Figure 2 demonstrates this method with
the set
= {1010000} on the (7, 4, 3) code described in
Table 1. For this case, the vector 0001011 is the
lexicographically earliest vector in the same coset as 1110000.
Note that the ordering of the
generators in the `MSGM` is significant and that different orderings
might not yield the lexicographically earliest vector.
For example, if generators *G*_{2} and *G*_{3} are switched, then Method 1
yields 0010010, which is
not the lexicographically earliest vector desired.

We will now prove the correctness of Method 1.
In our applications,
will typically be the set of
leaders of cosets with maximum distance from
. These coset leaders
are defined to be the minimum-weight vectors in their corresponding cosets,
so that Method 1 computes precisely
.

Proof of Method 1:
We first show correctness of the method by proving that, for each
*v*, lines 2-5
compute the lexicographically earliest vector in the same coset as *v*.
This way, line 6 in the method will return the
lexicographically earliest vector among all the cosets represented.

We know from [11, Thm 6.11 and Lemma 6.7] that
the rows of *G* have the predictable support property:

spanG_{j} = span(G_{j}) |
(3) |

for every subset

Now suppose that
is the lexicographically earliest vector in the
same coset as *v*, but that instead
is the vector stored on line 5
of the method. Our goal will be to show
that the difference between these two vectors, denoted
,
is in fact 0.

Clearly *v*,
, and
are necessarily in the same coset of
. Moreover, since *v* and
are in the same coset,
must
be a codeword of
so that we can write
(for an appropriate set
):

v_{diff} = G_{j}. |
(4) |

Then, applying the predictable span property of G,

Assume (for sake of contradiction) that
,
meaning that the left-most 1 bit of
occurs at the *k*-th
index. This implies that, starting from the left-most bit,
and
are identical until the *k*-th index, on which they
differ. Since, by definition,
comes lexicographically
before
, it must be that
has a 0 and
a 1 at the *k*-th index. Then (6)
implies that there must be some generator *G*_{j} whose
left-index is *k*; however, the lexicographic ordering of the
generators insures that *G*_{j} would have eliminated any 1 at index
*k* in
, providing a contradiction.
Thus, the left-index of
could not possibly be
at location *k*, for any *k*, so that
must be 0 and
correctness of the method is proved.
The time bound follows straightforwardly, and the space
bound follows from noting that
only the lexicographically earliest vector *v* needs to be stored
in line 5 of the method.

width4pt depth2pt height6pt

Method 1 provides a fast way of computing the lexicographic generating mapping. Appendix .1 gives computed parameters for many lexicodes that were thus computed. This list is more exhaustive than what is currently available in the literature [3,5].