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 [43], the span of a binary nvector 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 MSGMform using the greedy algorithm in [43]. 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 2.2 computes the lexicographically earliest vector among the cosets represented in .
1. for v = (v_{1}, v_{2}, v_{3},..., v_{n}) do
2. fori from n downto 1
3. if is a 1 then
4. v v + G_{i}
5. store the modified v;
6. among all stored v, return the lexicographically earliest
This method looks for the generators whose leftmost 1bit corresponds to 1bits in vectors vV. Figure 2.4 demonstrates this method with the set = {1010000} on the (7, 4, 3) code described in Figure 2.2. 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. Thus, if generators G_{2} and G_{3} are switched, then Method 2.2 yields 0010010, which is not the lexicographically earliest vector desired.

We will now prove the correctness and complexity bounds of
Method 2.2. In our applications,
will
typically be the set of coset leaders with maximum distance from
,
in which case Method 2.2 computes precisely
.
Proof of Method 2.2. We first show correctness of the method by proving that, for each v, lines 25 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 [43, Thm 6.11 and Lemma 6.7] that the rows of G have the predictable support property:
spanG_{j} = span(G_{j})  (9) 
Now suppose that v_{b}est is the lexicographically earliest vector in the same coset as v, but that instead v_{s}tored is the vector stored on line 5 of the method. Our goal will be to show that the difference between these two vectors, denoted v_{d}iff, is in fact 0.
Clearly v, v_{b}est, and v_{s}tored are necessarily in the same coset of . Moreover, since v and v_{s}tored are in the same coset, v_{d}iff must be a code word of so that we can write (for an appropriate set J_{d}iff):
v_{d}iff = G_{j}  (9) 
Assume (for sake of contradiction) that L(v_{d}iff )= k, meaning that the leftmost 1 bit of v_{d}iff occurs at the kth index. This implies that, starting from the leftmost bit, v_{b}est and v_{s}tored are identical until the kth index, on which they differ. Since, by definition, v_{b}est comes lexicographically before v_{s}tored, it must be that v_{b}est has a 0 and v_{s}tored a 1 at the kth index. However, (2.5) then implies that there must be some generator vector G_{j} whose leftindex is k, contradicting our constructive generation of v_{s}tored. Thus, the leftindex of v_{d}iff could not possibly be at location k, for any k, so that v_{d}iff must be 0 and correctness of the method is proved.
The space bound for this method follows straightforwardly, as at any
point in the algorithm we need to actively store only the
lexicographically earliest vector among those determined on line 5 so
far. The time bound follows from the fact that lines 35 are each
computable in constant time, giving a running time of O(n V) for
lines 15; Line 6 can be computed with constant overhead online, as
each vector is stored.
width4pt depth2pt height6pt
Method 2.2 provides a fast way of computing the lexicographic generating mapping. Appendix A.1 gives computed parameters for many lexicodes that were thus computed. This list is more exhaustive than what is currently available in the literature [9,14].
http://people.bu.edu/trachten