Trellis-oriented lexicodes

We now consider a different generating mapping for the G-construction which will generate families of codes oriented towards a reduced decoding trellis.

There is a unique, minimal [45], trellis for an arbitrary linear block code. Known as the BCJR  [3] 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 [35,43]. It is shown in [35,43] 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 $\ensuremath{\mathbb{C}}$, comprised of the generators g₁,..., g_k, then the number of vertices V_i and edges E_i in the corresponding BCJR trellis is given by:

$$\begin{split}\vert V_i\vert &= 2^{k-p_i-f_i} \\ Vert E_{i,i+1}\vert &= 2^{k-p_i-f_{i+1}} \end{split}$$ (9)

where p_i and f_i are the dimensions of the past and future subcodes for the i-th index of $\ensuremath{\mathbb{C}}$. These dimensions may be computed for i = 0, 1,..., n as follows [43]:

$$\left\{\vphantom{j : \ensuremath{\operatorname{R}}(g_j) \leq i }\right. \leq \left.\vphantom{j : \ensuremath{\operatorname{R}}(g_j) \leq i }\right\}$$ p_i =

$$f_i = \vert\left\{j : \ensuremath{\operatorname{L}}(g_j) \geq i+1 \right\}\vert$$

As before, $\ensuremath{\operatorname{R}}(\cdot)$ and $\ensuremath{\operatorname{L}}(\cdot)$ refer to the rightmost and leftmost non-zero indices of a vector, respectively. Since 2| E| - | V| + 1 steps are required for Viterbi decoding using a trellis [43], the optimal Viterbi decoding complexity for a code can be easily gleaned from its MSGM.

With a minor modification of the lexicographic construction we may exploit the above relations to locally minimize two measures of trellis complexity: state complexity, which is the maximum number of states at any time interval of the trellis, and Viterbi decoding complexity. Specifically, $G(\ensuremath{f_{\mbox{\small trelli}}},\ensuremath{\mathbb{C}})$ is such a family of codes, and it locally minimizes trellis complexity if $\ensuremath{f_{\mbox{\small trelli}}}(\ensuremath{\mathbb{C}})$ returns the vector with maximum distance from $\ensuremath{\mathbb{C}}$ whose bitwise reverse is lexicographically earliest. For example, if the vectors {1011, 1101, 1110} are at maximum distance from a code $\mathbb {K}$, then $\ensuremath{f_{\mbox{\small trelli}}}(\mathbb{K})$ returns the vector 1110. Because of their locally minimal trellis complexity, these codes may be justly called ``trellis-oriented.''

Theorem 2..3   Let $\ensuremath{\mathbb{C}}$ be a linear code. Among those single-iteration extensions $\ensuremath{ {\emph G}_{\,1} \left( f,\mathbb{\ensuremath{\mathbb{C}}} \right) }$ with shortest length, the generator mapping $f(\cdot)=\ensuremath{f_{\mbox{\small trelli}}}(\cdot)$ minimizes the Viterbi decoding complexity and trellis state complexity.

Theorem 2.3 establishes that $\ensuremath{f_{\mbox{\small trelli}}}(\cdot)$ 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 $\ensuremath{\mathbb{C}}$ 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 i-th time interval. Now, consider appending to G the generator v = $\left\langle\vphantom{1^\Delta \vert \lambda }\right.$1^$\Delta$|$\lambda$$\left.\vphantom{1^\Delta \vert \lambda }\right\rangle$ as in Equation (2.2) of the definition of the G-construction. The generated code $\ensuremath{\mathbb{C}}'=\ensuremath{ {\emph G}_{\,1} \left( f,\mathbb{\ensuremath{\mathbb{C}}} \right) }$ will have parameters $(n'=n+d-\ensuremath{\operatorname{wt}}(\lambda),k+1,d)$. Without loss of generality we may assume that the resulting generator matrix of $\ensuremath{\mathbb{C}}'$ is an MSGM. If we denote the difference in lengths between $\ensuremath{\mathbb{C}}'$ and $\ensuremath{\mathbb{C}}$ by $\nabla$n = n' - n, then a simple analysis shows that $\ensuremath{\mathbb{C}}'$ will have past and future subcode dimensions:

We may then use (2.6) and (2.7) at each time unit i to compute the number of vertices and edges ( | V'_i|,| E'_i|) in the BCJR trellis for $\ensuremath{\mathbb{C}}'$ based on the vertices and edges ( | V_i|,| E_i|) in the BCJR trellis for $\ensuremath{\mathbb{C}}$:

It is now a simple matter of algebra to compute the difference in Viterbi decoding complexities between the trellises of $\ensuremath{\mathbb{C}}'$ and $\ensuremath{\mathbb{C}}$:

$$\begin{split}\Delta(Viterbi decoding complexity) &= (2\vert E... ...torname{R}}(v)-\nabla n - 1} \vert V_i\vert \right] \end{split}$$ (9)

Since | E_i| $\geq$ | V_i| for all i, minimizing the change in Viterbi decoding complexity depends on minimizing R(v) = R$\left(\vphantom{1^\Delta \vert \lambda }\right.$1^$\Delta$|$\lambda$$\left.\vphantom{1^\Delta \vert \lambda }\right)$, which in turn depends on having the 1 bits of $\lambda$ as far to the left as possible. On the other hand, $\lambda$ cannot have weight less than the covering radius $\rho$ of $\ensuremath{\mathbb{C}}$ if it is to produce an extension of shortest length. Thus, the mapping $\ensuremath{f_{\mbox{\small trelli}}}(\cdot)$ is one of several mappings which meet both criteria for local optimality: minimizing R(v) and having $\ensuremath{\operatorname{wt}}(\lambda)=\rho$. On the other hand, other intuitive generating mappings, such as picking lexicographically latest vectors at maximum distance from the code, are not always locally optimal.

Equation 2.8 also proves that minimizing $\ensuremath{\operatorname{R}}(v)$ is the appropriate criterion for minimizing state complexity. This is because larger values of $\ensuremath{\operatorname{R}}(v)$ correspond to doubling more vertices | V_i-$\nabla$n| when generating V_i'. Thus, $\ensuremath{f_{\mbox{\small trelli}}}(\cdot)$ locally minimizes state complexity as well.

width4pt depth2pt height6pt

Note that (2.8) and (2.9) provides us with a simple alternate method for computing the Viterbi decoding complexity or state complexity of any trivially-seeded G-code given its MSGM.

Figure: Generator matrix for the dimension 4 minimum distance 3 trellis-oriented G-code. The generator padding for each iteration is marked in bold.

Figure 2.5 depicts the (7, 4, 3) trellis-oriented G-code that was generated similarly to the code in Figure 2.2. In fact, Method 2.2 can be trivially reversed to compute $\ensuremath{f_{\mbox{\small trelli}}}(\cdot)$, without affecting the running time or space:

Method 2..4   Consider a set of vectors $\mathcal {V}$, and a code $\mathbb {C}$ with MSGM G whose generators are in lexicographically increasing order. The following greedy method computes the lexicographically earliest bitwise reversed vector among the represented cosets in time O(n| V|) and space O(1).

1. for
v = (v1, v2, v3,..., vn)$\mbox{$\,\inn\,$}$$\mathcal {V}$ do


2. 		 		fori from 1 to n


3. 		 		 		if 
$v_{\ensuremath{\operatorname{R}}(G_i)}$ is a 1 then


4. 		 		 		 		
v $\leftarrow$ v + Gi


5. 		 		store the modified v;


6. 		 among all stored v, return the lexicographically earliest

The proof of correctness and complexity for Method 2.4 follows trivially from the proof of Method 2.2.