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 $\mathfrak{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 $\ensuremath{f_{\mbox{\small trelli}}}$ we similarly design the state-constrained generating mapping $\ensuremath{f_{\mbox{\small state}}}$ 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, $\ensuremath{f_{\mbox{\small state}}}(s,\ensuremath{{\mathbb{C}}})$ is the same as $\ensuremath{f_{\mbox{\small trelli}}}(\ensuremath{{\mathbb{C}}})$ with the additional constraint that the code formed by adding the return vector v to $\mathbb {C}$ has a trellis state complexity bounded by s.

We may similarly produce $\mathfrak{G}$-families which constrain Viterbi decoding complexity by using the generating mapping $\ensuremath{f_{\mbox{\small decoding}}}$, which like $\ensuremath{f_{\mbox{\small state}}}$ 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 $\ensuremath{f_{\mbox{\small state}}}$ and $\ensuremath{f_{\mbox{\small decoding}}}$ are straightforward by-products of the mechanism behind Theorem  (in the next section), which drives the computation of codes in an arbitrary $\ensuremath{{\mathfrak{G}}}$-family. Specifically, for any such $\ensuremath{{\mathfrak{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. Appendices .2 and  demonstrate the effects of bounding various trellis properties.