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 layering constraints or for mobile communications 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 G-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.

We may similarly produce G-families which constrain Viterbi
decoding complexity by using the generating mapping
,
which bounds the Viterbi decoding complexity of an extended
code by 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 *G*-family. Specifically, for any such
*G*-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. Appendix A.2 and demonstrate the effects of bounding various trellis
properties.

http://people.bu.edu/trachten