Trellis-bounded lexicodes

It is often useful to bound various parameters of a trellis so that decoding can be efficiently handled by a system with complexity constraints, such as a VLSI chip with certain implementation constraints or a mobile device with certain power limits. We consider generating mappings which bound Viterbi decoding complexity and trellis-state complexity. The trellis-state complexity is a strong indicator of the decoding complexity of a code because it asymptotically restricts memory-usage and the number of bifurcations in the trellis.

We may produce
-families which constrain state complexity by simply restricting
the generating mapping to returning only vectors which maintain
state complexity bounds. In order
to duplicate the nice locally optimal properties of
we similarly design the state-constrained generating mapping
to return, among all candidate vectors which maintain the state
complexity bound, the vector of maximum distance from the given
code whose reverse is lexicographically earliest. Formally,
is the same as
with the additional constraint
that the code formed by adding the return vector *v* to
has a
trellis state complexity bounded by *s*.

We may similarly produce
-families which constrain Viterbi
decoding complexity by using the generating mapping
, which
like
restricts its output to producing codes whose Viterbi decoding complexity
is some function *g*(*k*) of the dimension *k* of the
underlying code.

The computations of
and
are
straightforward by-products of the mechanism behind Theorem (in the next section), which drives the computation of codes
in an arbitrary
-family. Specifically, for any such
-code, we may quickly derive an `MSGM` from which all the
necessary trellis properties may be easily gleaned and suitably
constrained. Unfortunately, the worst case (extreme bounding)
computation of either of these generating mappings involves
exhaustively searching through every coset leader in an attempt to
meet the constraint. Appendices .2 and demonstrate the effects of bounding various trellis
properties.