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 g1,..., gk, then the number of vertices Vi and edges Ei in the corresponding BCJR trellis is given by:

\begin{displaymath}\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}\end{displaymath} (9)

where pi and fi 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]:

pi = |$\displaystyle \left\{\vphantom{j : \ensuremath{\operatorname{R}}(g_j) \leq i }\right.$j : R(gj) $\displaystyle \leq$ i$\displaystyle \left.\vphantom{j : \ensuremath{\operatorname{R}}(g_j) \leq i }\right\}$|  
$\displaystyle f_i$ $\textstyle =$ $\displaystyle \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 pi and fi respectively, and whose trellis has vertices Vi and edges Ei, 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$\scriptstyle \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:

p'i=  $\displaystyle \left\{\vphantom{ \begin{array}{ll} 0 & \text{if } 0 \leq i \leq ...
...) \\  p_{i- \nabla n} + 1 & \text{if } R(v) \leq i \leq n' \end{array} }\right.$$\displaystyle \begin{array}{ll} 0 & \text{if } 0 \leq i \leq \nabla n \\  p_{i-...
...< i < R(v) \\  p_{i- \nabla n} + 1 & \text{if } R(v) \leq i \leq n' \end{array}$
  
f'i=  $\displaystyle \left\{\vphantom{ \begin{array}{ll} k+1 & \text{if } i = 0 \\  k ...
...bla n\\  f_{i- \nabla n} & \text{if } \nabla n < i \leq n' \end{array} }\right.$$\displaystyle \begin{array}{ll} k+1 & \text{if } i = 0 \\  k & \text{if } 0 < i \leq \nabla n\\  f_{i- \nabla n} & \text{if } \nabla n < i \leq n' \end{array}$
(9)

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 ( | Vi|,| Ei|) in the BCJR trellis for $\ensuremath{\mathbb{C}}$:

(| V'i|,| E'i|)= $\displaystyle \left\{\vphantom{ \begin{array}{ll} (1,2) & \text{if } i=0 \\  (2...
...vert E_{i-\nabla n}\vert) & \text{if } R(v) \leq i \leq n' \end{array} }\right.$$\displaystyle \begin{array}{ll} (1,2) & \text{if } i=0 \\  (2,2) & \text{if } 0...
...}\vert, \vert E_{i-\nabla n}\vert) & \text{if } R(v) \leq i \leq n' \end{array}$
(9)

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{displaymath}\begin{split}\Delta(Viterbi decoding complexity) &= (2\vert E...
...torname{R}}(v)-\nabla n - 1} \vert V_i\vert \right] \end{split}\end{displaymath} (9)

Since | Ei| $ \geq$ | Vi| for all i, minimizing the change in Viterbi decoding complexity depends on minimizing R(v) = R$ \left(\vphantom{1^\Delta \vert \lambda }\right.$1$\scriptstyle \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 | Vi-$\scriptstyle \nabla$n| when generating Vi'. 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.
\begin{figure}\begin{center}
\begin{tabular}{\vert r\vert} \hline
0000\textbf{1...
...1}111000 \\
\hline
\end{tabular}$\,$\vspace{-1ex}
\par\end{center}\end{figure}

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.

http://people.bu.edu/trachten