The
construction also enables us to transform a given
code into a similar code with (often) a better trellis complexity.
Theorem 2 assures us that
is a locally optimal method of extending an arbitrary
subcode if we seek to maximize information rate and minimize
decoding complexity. Thus, we have a simple, greedy method in which
we may attempt to improve a given code
.
Specifically, we may arbitrarily delete a generator of
and replace it with a trellisoriented generator. Because of
Theorem 2 we know that the resulting code will have
trellis complexity and code parameters (e.g., length, minimum distance)
no worse than the original code.^{6}
In fact, this method may be applied to several generators: shorten
by deleting k generators; replace the generators with
k trellisoriented generators. This allows us to create
an amalgam of the original code and a trellisoriented code.
Though the resulting code is not guaranteed to match the
decoding performance of our original code,
it often performs much better as we see in the following
example.
Example 1
Consider the length 31, dimension 16, triple errorcorrecting
BCH code generated by the polynomial
g(x) = 1 + x + x^{2} + x^{3} + x^{5} + x^{7} + x^{8} + x^{9} + x^{10} + x^{11} + x^{15}.
It requires
2^{15} = 32, 768 trellis states and
262, 139 steps for Viterbi decoding.
Table
5 shows the dramatic improvement
of this code as more generator vectors are replaced with trellisoriented
generators.
Table 5:
Improving a (31, 16, 7) BCH code by replacing k of its generators
with trellisoriented generators. The trellis state complexity
and Viterbi decoding complexity of the intermediate (31, 16, 7) codes
is noted, as is the time (in minutes) needed to generate them on a
Sun UltraSparc 1.
k  State  Decoding  Generation time 
 complexity  complexity  
1  2^{15}  262,139  26:36 
2  2^{15}  262,139  22:11 
3  2^{13}  94,203  18:30 
4  2^{13}  54,659  24:45 
5  2^{11}  36,355  20:25 
6  2^{12}  43,779  17:17 
7  2^{12}  37,251  14:59 
8  2^{11}  32,333  14:49 
9  2^{12}  39,373  12:50 
10  2^{12}  40,159  11:41 
11  2^{12}  37,647  10:34 
12  2^{11}  26,303  11:22 
13  2^{10}  16,611  10:12 
14  2^{10}  16,147  9:39 
15  2^{10}  13,603  9:41 
16  2^{9}  4,907  1:07 

We note that both the state and decoding complexities
generally decrease as k increases. Moreover, the computation time
also generally decreases because of the decreasing size of the seed code.