Trellis-oriented lexicodes

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

There is a unique, minimal [12] trellis for an arbitrary linear block code. Known as the BCJR [1] 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 [8,11]. It is shown in [8,11] 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}$$ (6)

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 [11]:

$$\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. 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, $\ensuremath{{\mathfrak{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 bit-wise reverse ( REV) is lexicographically earliest:

$$\begin{multline} \ensuremath{f_{\mbox{\small trelli}}}(\ensuremath{{\mathbb{C}}}... ... d(w,\ensuremath{{\mathbb{C}}}) < d(v,\ensuremath{{\mathbb{C}}}). \end{multline}$$

For example, if the vectors {1011, 1101, 1110} are at maximum distance from a code $\ensuremath{{\mathbb{C}}}$, then $\ensuremath{f_{\mbox{\small trelli}}}(\ensuremath{{\mathbb{C}}})$ returns the vector 1110. Because of their locally minimal trellis complexity, these codes may be justly called ``trellis-oriented.''

Theorem 2 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.

Theorem 2   Let $\ensuremath{{\mathbb{C}}}$ be a linear code. Among those single-iteration extensions $\ensuremath{ {\mathfrak{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.

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 (3) of the definition of the $\mathfrak{G}$-construction. The generated code $\ensuremath{{\mathbb{C}}}'=\ensuremath{ {\mathfrak{G}}_{1} \left( f,{\mathbb{C}} \right) }$ will have parameters (n' = n + $\Delta$, 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 (7) and (9) 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{multline} \Delta(\mbox{Viterbi complexity}) = (2\vert E'\vert-\vert V'\ve... ...remath{\operatorname{R}}(v)-\nabla n - 1} \vert V_i\vert \right] \end{multline}$$

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$. Other intuitive generating mappings, such as picking lexicographically latest vectors at maximum distance from the code, are not always locally optimal because the lexicographically latest vector need not (and generally does not) have the minimum rightmost index.

Equation 10 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

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

 

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

Method 2   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 O(n| V|) time and O(n) space.

1. for each
v = (v1, v2, v3,..., v|$\mathcal {V}$|)$\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 follows trivially from the proof of Method 1.