Code improvement

The $ \mathfrak{G}$-construction also enables us to transform a given code into a similar code with (often) a better trellis complexity. Theorem 2 assures us that $\ensuremath{f_{\mbox{\small trelli}}}(\cdot)$ 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 $ \mathbb {C}$.

Specifically, we may arbitrarily delete a generator of $ \mathbb {C}$ and replace it with a trellis-oriented 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 $ \mathbb {C}$ by deleting k generators; replace the generators with k trellis-oriented generators. This allows us to create an amalgam of the original code and a trellis-oriented 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 error-correcting BCH code generated by the polynomial g(x) = 1 + x + x2 + x3 + x5 + x7 + x8 + x9 + x10 + x11 + x15. It requires 215 = 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 trellis-oriented generators.

Table 5: Improving a (31, 16, 7) BCH code by replacing k of its generators with trellis-oriented 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 Ultra-Sparc 1.
k State DecodingGeneration time
complexitycomplexity
1 215 262,139 26:36
2 215 262,139 22:11
3 213 94,203 18:30
4 213 54,659 24:45
5 211 36,355 20:25
6 212 43,779 17:17
7 212 37,251 14:59
8 211 32,333 14:49
9 212 39,373 12:50
10 212 40,159 11:41
11 212 37,647 10:34
12 211 26,303 11:22
13 210 16,611 10:12
14 210 16,147 9:39
15 210 13,603 9:41
16 29 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.