Theorem 3 can be directly translated into an algorithm
that computes
-families. The algorithm simply computes the coset
leaders of
-codes in the family, from which the remaining
parameters may be easily deduced. This computation scheme has the
advantage of being exponential in the co-dimension (i.e., the dimension
of the dual code) rather than the dimension or the length.
Thus, this algorithm is efficient for high-rate codes, and it is
presented in Algorithm 1.
In Algorithm 1 we reuse our earlier notation that
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 4 follows from a straightforward analysis of the pseudo-code for Algorithm 1.
For the specific case of distance 4 lexicodes, this algorithm is particularly fast, since Brualdi and Pless [3, Thm.3.5] show that, under these circumstances:
m = nm - 2 - ![]() ![]() |
(13) |
The analysis of Algorithm 1 assumes an oracle computation
of the generating mapping. For the case of lexicodes and
trellis-oriented lexicodes, however, Method 1 provides an
efficient means of computing this mapping in time
and O(nm) space, where
represents
the number of cosets in the m-th corresponding
-code.
As in the case of lexicodes and trellis-oriented codes, the overhead
of computing
is usually eclipsed by the running time of
the remainder of the algorithm.
The complexity of Algorithm 1 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 [5].
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 a trellis-oriented
-code
with code parameters similar to lexicodes, but with better state
complexity than the corresponding BCH codes heuristically minimized
in [7]. These result were predicted by [7] and are demonstrated
in Table 4.
|