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.⁶

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 + x² + x³ + x⁵ + x⁷ + x⁸ + x⁹ + x¹⁰ + x¹¹ + x¹⁵. It requires 2¹⁵ = 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 Decoding Generation time

complexity complexity

1 2¹⁵ 262,139 26:36

2 2¹⁵ 262,139 22:11

3 2¹³ 94,203 18:30

4 2¹³ 54,659 24:45

5 2¹¹ 36,355 20:25

6 2¹² 43,779 17:17

7 2¹² 37,251 14:59

8 2¹¹ 32,333 14:49

9 2¹² 39,373 12:50

10 2¹² 40,159 11:41

11 2¹² 37,647 10:34

12 2¹¹ 26,303 11:22

13 2¹⁰ 16,611 10:12

14 2¹⁰ 16,147 9:39

15 2¹⁰ 13,603 9:41

16 2⁹ 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.