Bounding Decoding Complexity

Figure 4 shows the results of applying Viterbi decoding constraints to $ \mathfrak{G}$-codes. Specifically, it shows the decoding complexity achieved under linear and quadratic decoding bounds. The degradation in code length compared to the standard lexicodes is modest for these examples.

Figure: The effects of bounding the decoding complexity of distance 6 -codes with a linear function (top)and a quadratic function (bottom).
\begin{figure}\centering\hspace*{-0.31in}\epsfig{figure=linbound.eps,width=3.25in}\\
\hspace*{-0.31in}\epsfig{figure=quadbound.eps,width=3.25in}\end{figure}


Table: Parameters of d = 8 codes. We display the following parameters for lexicodes and trellis-oriented $ \mathfrak G$-codes: length, dimension, state complexity and Viterbi decoding complexity with the BCJR trellis.

Dim-

Standard Trellis- Standard Trellis- Standard Trellis-

ension

oriented oriented oriented
Length Length States States 2| E| - | V| + 1 2| E| - | V| + 1

1

8 1 17
2 12 2 35
3 14 3 71
4 15 4 143
5 16 4 195
6 18 5 341
7 19 6 647
8 20 6 779
9 21 7 1,547
10 22 8 2,395
11 23 9 4,219
12 24 9 4,475
13 28 9 4,529
14 30 9 4,777
15 31 9 5,463
16 32 9 5,515
17 34 9 7,645 5,693
18 35 9 12,671 6,143
19 36 9 12,803 6,275
20 37 10 9 24,267 7,691
21 38 10 9 25,115 8,539
22 39 10 9 26,939 10,363
23 40 10 9 27,195 10,619
24 42 10 31,805 17,853
25 43 11 41,791 33,087
26 44 11 41,987 33,283
27 45 12 65,227
28 46 12 67,163
29 47 12 72,571 78,203
30 48 12 72,827 78,459
31 49 50 13 12 135,611 80,317
32 50 51 13 12 169,019 87,103
33 51 52 13 12 248,123 88,643
34 52 53 13 248,507 137,547
35 53 54 14 13 427,579 138,331
36 54 55 14 13 431,419 142,203
37 55 56 14 13 442,171 142,459
38 56 57 14 442,555 274,875
39 58 14 487,997 308,283
40 59 14 628,031 457,019
41 60 14 628,227 460,091
42 62 14 629,197 460,861
43 63 14 631,903 464,703
44 64 14 632,035 464,899
45 65 15 14 1,263,819 581,835
46 66 15 1,287,195 1,053,275