We now consider a different generating mapping for the construction which will generate families of codes oriented towards a reduced decoding trellis.
There is a unique, minimal [12] trellis for an arbitrary linear block code. Known as the BCJR [1] trellis, it has no more edges or vertices at each time index than any other trellis for the code and can be constructed fairly easily [8,11]. It is shown in [8,11] that the minimal span generator matrix (MSGM) for a linear code, in which the sum of the spans of the binary generators is minimized, reflects the properties of the corresponding BCJR trellis. Namely, if G is an MSGM of a code , comprised of the generators G_{1},..., G_{k}, then the number of vertices V_{i} and edges E_{i} in the corresponding BCJR trellis is given by:
p_{i}  =  j : R(G_{j}) i  
For example, if the vectors {1011, 1101, 1110} are at maximum distance from a code , then returns the vector 1110. Because of their locally minimal trellis complexity, these codes may be justly called ``trellisoriented.''
Theorem 2 establishes that locally minimizes trellis complexity among local extensions with optimal code parameters. It is possible to improve Viterbi decoding complexity by using a generating mapping which produces a longer extension, but the information rate of the resulting code will be inferior.
Proof: Suppose that G is an MSGM for the (n, k, d ) code whose past and future subcodes have dimensions p_{i} and f_{i} respectively, and whose trellis has vertices V_{i} and edges E_{i, i + 1} at the ith time interval. Now, consider appending to G the generator v = 1^{} as in Equation (3) of the definition of the construction. The generated code will have parameters (n' = n + , k + 1, d ). Without loss of generality we may assume that the resulting generator matrix of is an MSGM. If we denote the difference in lengths between and by n = n'  n, then a simple analysis shows that will have past and future subcode dimensions:

(7) 
We may then use (7) and (9) at each time unit i to compute the number of vertices and edges (  V'_{i}, E'_{i}) in the BCJR trellis for based on the vertices and edges (  V_{i}, E_{i}) in the BCJR trellis for :

(8) 
It is now a simple matter of algebra to compute the difference in Viterbi decoding complexities between the trellises of and :
Since  E_{i}  V_{i} for all i, minimizing the change in Viterbi decoding complexity depends on minimizing R(v) = R1^{}, which in turn depends on having the 1 bits of as far to the left as possible. On the other hand, cannot have weight less than the covering radius of if it is to produce an extension of shortest length. Thus, the mapping is one of several mappings which meet both criteria for local optimality: minimizing R(v) and having . Other intuitive generating mappings, such as picking lexicographically latest vectors at maximum distance from the code, are not always locally optimal because the lexicographically latest vector need not (and generally does not) have the minimum rightmost index.
Equation 10 also proves that minimizing
is the
appropriate criterion for minimizing state complexity. This is
because larger values of
correspond to doubling more vertices
 V_{i  n} when generating V_{i}'.
Thus,
locally minimizes state complexity as well.
width4pt depth2pt height6pt

1. for each v = (v_{1}, v_{2}, v_{3},..., v_{}) do
2. fori from 1 to n
3. if is a 1 then
4. v v + G_{i}
5. store the modified v;
6. among all stored v, return the lexicographically earliest
The proof of correctness and complexity for Method 2 follows trivially from the proof of Method 1.