Theorem 2.5 can be directly translated into an algorithm that computes G-families. The algorithm simply computes the coset leaders of G-codes in the family, from which the remaining parameters may be easily deduced. This computation scheme has the advantage of being dependent on the co-dimension (i.e. the dimension of the dual code) rather than the dimension or the length alone. Thus, this algorithm is efficient for high-rate codes, and it is presented in Algorithm 2.12.

% latex2html id marker 3488
...emph G}_{\,i}}$\ from the newly computed coset leaders

In Algorithm 2.12 we reuse our earlier notation that ${\Delta_i} = d -
\ensuremath{\operatorname{wt}}(f(\ensuremath{ {\emph G}_{\,i-1}}))$. Note that we assume that the coset leaders of the seed code are known or trivially derivable, as is often the case. The correctness of the algorithm follows immediately from Theorem 2.5. Moreover, we can also compute the running time and space of this algorithm in terms of % latex2html id marker 16605
$ \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16606
$ \left.\vphantom{ m }\right\urcorner$ $ \mbox{$\stackrel{\rm def}{=}$}$ nm - m, the co-dimension of the m-th G-code,

Lemma 2..12   Using an oracle for computing the generating mapping, Algorithm 2.12 runs in space O(2% latex2html id marker 16612
$\scriptstyle \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16613
$\scriptstyle \left.\vphantom{ m }\right\urcorner$) and time O(nm% latex2html id marker 16615
$ \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16616
$ \left.\vphantom{ m }\right\urcorner$2% latex2html id marker 16617
$\scriptstyle \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16618
$\scriptstyle \left.\vphantom{ m }\right\urcorner$).

An oracle is simply a black box that computes a given function in constant time. In this case, we assume the existence of an oracle for computing the generating mapping because the complexity of such a computation can vary greatly among mappings. The proof of Lemma 2.13 follows from a straightforward analysis of the pseudo-code for Algorithm 2.12.

Proof.  At each iteration, Algorithm 2.12 stores the coset leaders of the code $\ensuremath{ {\emph G}_{\,i}}$ which it is computing and the companion of each leader. Thus, the algorithm requires space

% latex2html id marker 4515O(\ensuremath{\char93 \mbox{\te...
...m}}) = O(2^{n_m-m}) = O(2^{\left\ulcorner m \right\urcorner })

where % latex2html id marker 16626
$ \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16627
$ \left.\vphantom{ m }\right\urcorner$ = nm - m denotes the co-dimension and $\ensuremath{\char93 \mbox{\texttt{COSET}}_{m}}$ denotes the number of cosets of $\ensuremath{ {\emph G}_{\,m}}$.

The time bound for this algorithm, on the other hand, is somewhat more complicated. Consider the innermost loop of the algorithm during the computation of the i-th extension. Clearly, based on Theorem 2.5, lines 6-10 are executed at most once for each coset of $\ensuremath{ {\emph G}_{\,i}}$. Moreover, the companion calculation in line 5 is executed once for each coset of $\ensuremath{ {\emph G}_{\,i-1}}$. The companion may be determined with a binary search over coset syndromes; the binary search requires time:

% latex2html id marker 4516O \left( log(\ensuremath{\char9...
...{COSET}}_{i-1}}) \right) = \left\ulcorner i-1 \right\urcorner

Finally, each syndrome calculation used to determine the companion of a coset of $\ensuremath{ {\emph G}_{\,i-1}}$ itself requires time O(ni % latex2html id marker 16648
$ \left\ulcorner\vphantom{ i }\right.$i% latex2html id marker 16649
$ \left.\vphantom{ i }\right\urcorner$), corresponding to matrix-vector multiplications. Recall that our oracle supplies the computation in line 2 of this analysis in constant time.

Putting everything together, we get a running time of

O(2% latex2html id marker 16652
$\scriptstyle \left\ulcorner\vphantom{ i }\right.$i% latex2html id marker 16653
$\scriptstyle \left.\vphantom{ i }\right\urcorner$×% latex2html id marker 16654
$\displaystyle \left[\vphantom{\, \left\ulcorner i-1 \right\urcorner +n_i(\left\ulcorner i \right\urcorner ) }\right.$ % latex2html id marker 16655
$\displaystyle \left\ulcorner\vphantom{ i-1 }\right.$i - 1% latex2html id marker 16656
$\displaystyle \left.\vphantom{ i-1 }\right\urcorner$ + ni(% latex2html id marker 16657
$\displaystyle \left\ulcorner\vphantom{ i }\right.$i% latex2html id marker 16658
$\displaystyle \left.\vphantom{ i }\right\urcorner$)% latex2html id marker 16659
$\displaystyle \left.\vphantom{\, \left\ulcorner i-1 \right\urcorner +n_i(\left\ulcorner i \right\urcorner ) }\right]$)$\displaystyle \subset$O% latex2html id marker 16663
$\displaystyle \left(\vphantom{2^{\left\ulcorner i \right\urcorner } \left\ulcorner i \right\urcorner n_i }\right.$2% latex2html id marker 16664
$\scriptstyle \left\ulcorner\vphantom{ i }\right.$i% latex2html id marker 16665
$\scriptstyle \left.\vphantom{ i }\right\urcorner$% latex2html id marker 16666
$\displaystyle \left\ulcorner\vphantom{ i }\right.$i% latex2html id marker 16667
$\displaystyle \left.\vphantom{ i }\right\urcorner$ni% latex2html id marker 16668
$\displaystyle \left.\vphantom{2^{\left\ulcorner i \right\urcorner } \left\ulcorner i \right\urcorner n_i }\right)$

Except for trivial cases, % latex2html id marker 16670
$ \left\ulcorner\vphantom{ i }\right.$i% latex2html id marker 16671
$ \left.\vphantom{ i }\right\urcorner$ and ni do not decrease with i so that:
$\displaystyle \sum_{{i=1}}^{{m}}$O(2% latex2html id marker 16677
$\scriptstyle \left\ulcorner\vphantom{ i }\right.$i% latex2html id marker 16678
$\scriptstyle \left.\vphantom{ i }\right\urcorner$% latex2html id marker 16679
$\displaystyle \left\ulcorner\vphantom{ i }\right.$i% latex2html id marker 16680
$\displaystyle \left.\vphantom{ i }\right\urcorner$ni) $\displaystyle \subseteq$ O(nm% latex2html id marker 16684
$\displaystyle \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16685
$\displaystyle \left.\vphantom{ m }\right\urcorner$$\displaystyle \sum_{{i=1}}^{{m}}$2% latex2html id marker 16687
$\scriptstyle \left\ulcorner\vphantom{ i }\right.$i% latex2html id marker 16688
$\scriptstyle \left.\vphantom{ i }\right\urcorner$)  
  $\displaystyle \subseteq$ O(nm% latex2html id marker 16692
$\displaystyle \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16693
$\displaystyle \left.\vphantom{ m }\right\urcorner$2% latex2html id marker 16694
$\scriptstyle \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16695
$\scriptstyle \left.\vphantom{ m }\right\urcorner$)  

This proves the lemma.

width4pt depth2pt height6pt

For the specific case of distance 4 lexicodes, this algorithm is particularly fast, since Brualdi and Pless [9, Thm.3.5] show that, under these circumstances:

m = nm - 2 - $\displaystyle \left\lfloor\vphantom{ \log_2 (n_m-1) }\right.$log2(nm - 1)$\displaystyle \left.\vphantom{ \log_2 (n_m-1) }\right\rfloor$ (9)

so that Lemma 2.14 reduces to time O(nm2log(nm)) and space O(nm). This is not surprising given that the distance 4 lexicodes are simply shortenings of the extended Hamming codes [14].

The analysis of Algorithm 2.12 assumes an oracle computation of the generating mapping. For the case of lexicodes and trellis-oriented lexicodes, however, Method 2.2 provides an efficient means of computing this mapping in time $O(n_m \times
\ensuremath{\char93 \mbox{\texttt{COSET}}_{m}})$ and constant space. As in the case of lexicodes and trellis-oriented codes, the overhead of computing $f(\ensuremath{ {\emph G}_{\,i-1}})$ is usually eclipsed by the running time of the remainder of the algorithm.

Corollary 2..13   Algorithm 2.12 requires time O(nm% latex2html id marker 16709
$ \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16710
$ \left.\vphantom{ m }\right\urcorner$2% latex2html id marker 16711
$\scriptstyle \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16712
$\scriptstyle \left.\vphantom{ m }\right\urcorner$) and space O(2% latex2html id marker 16714
$\scriptstyle \left\ulcorner\vphantom{ m }\right.$m% latex2html id marker 16715
$\scriptstyle \left.\vphantom{ m }\right\urcorner$) to compute lexicodes and trellis-oriented lexicodes.

The complexity of Algorithm 2.12 is thus bounded by the co-dimension of the code and by the difficulty of computing the generating mapping. Under practical conditions, we were able to compute lexicodes well beyond length 44 initially reported in [14].

In addition, we were able to construct trellis-oriented codes with code parameters rivaling those of lexicodes, but with much better trellis state complexities. As an example, we generated trellis-oriented G-code with code parameters similar to lexicodes, but with better state complexity than the corresponding BCH codes heuristically minimized in [34]. These result were predicted by [34] and are demonstrated n Figures 2.7 and 2.8.

Figure 2.7: A comparison of the state complexities of the (32, 16, 8) trellis-oriented lexicode (trelli) and the (32, 16, 8) extended BCH code (ext BCH) heuristically minimized in [34]
\begin{figure}\centering\begin{tabular}{\vert l\vert c@{-}c@{-}c@{-}c@{-}c@{-}c@...
...& 8& 9& 8& 9& 8& 7& 6& 7& 6& 5& 4& 3& 2& 1& 0\\ \hline

Figure 2.8: A comparison of the state complexities of the (31, 16, 7) trellis-oriented lexicode (Trelli) and a (31, 16, 7) extended BCH code (BCH) heuristically minimized in [34]
\begin{figure}\centering\begin{tabular}{\vert l\vert c@{-}c@{-}c@{-}c@{-}c@{-}c@...
...& 8& 9& 8& 9& 8& 7& 6& 7& 6& 5& 4& 3& 2& 1& 0\\ \hline

Finally, the trellis state bounded codes that we have computed show improvements, for various code parameters, over the similar codes computed in [67] using different techniques.Figure 2.9 depicts the generator matrix of the (70, 49, 8) trellis-oriented code produced using Algorithm 2.12. Other examples and computations of the various techniques described in this paper are available in Appendix A.

Figure: The (70, 49, 8) trellis-oriented G-code.
11 111 111 ...
...00 000 000 000 000 000 000 000 000 000 \\