A faster (stack) decoder for systematic convolutional codes

The stack algorithm is a simple sequential-decoding algorithm. The algorithm expands a set of possible subsequences and keeps the currently best N subsolutions in a list. The stack algorithm is usually more efficient than Viterbi decoding (in the general setting), but suboptimal since if N is too small compared to the error the correct sequence might get pushed out of the list and never be found.

High-level description

\mathbf{G}_{i,j} = \begin{cases}\begin{pmatrix}\mathbf{I}_k & \mathbf{Q}_{i} \end{pmatrix} & \quad \text{if } i = j\\ ~\mathbf{R}_{i,j} & \quad \text{if } i \neq j\\ \end{cases}

be a (k,n) systematic block code defined over the binary field \mathbb{F}_2, where \mathbf{I}_k is a k \times k identity matrix and \mathbf{Q}_{i,j} is an arbitary k \times (n-k) matrix. We now define a convolutional code as follows.

\mathbf{G} = \begin{pmatrix} \mathbf{G}_{1,1} & \mathbf{G}_{1,2} & \hdots \\ \mathbf{0} & \mathbf{G}_{2,2} & \hdots \\ \vdots & \ddots & \ddots\end{pmatrix}

In the normal (ZJ) stack decoder, we would enumerate all 2^k possible length-k sequences and compute the first n codeword symbols in the code generated by \mathbf{G}. All such sub-codewords would be put in a list sorted according to their Fano distance from the corresponding received codeword symbols. The best entry in the list would then be expanded with an additional k bits, yielding 2^k more sequences in the list of (length 2k). This process is repeat until the sought codeword is found.

This is fine if k is small, but when k is somewhat larger this quickly becomes cumbersome. Therefore, we introduce the \mathcal{B}-stack decoder.

The idea is to not expand the full set of the 2^k sequences in each step, but only a subset of them. We read the information bits from the systematic part. Let this sequence be \mathbf{u}. Then, we sequentially generate subsets of sequences chosen from the Hamming balls

\{ \mathbf{u}+\mathcal{B}(k,0), \mathbf{u}+\mathcal{B}(k,1), \ldots\}.

The number of errors in the systematic bits is expected to be k \cdot \rho, with \rho being the error rate of the channel. The first guess is

\{\mathbf{u}+\mathcal{B}(k,0)\} = \{\mathbf{u} \}.

Then, we compute the Fano distance from the codeword and sort the list. The entry we expanded from is kept in the list, but now with the information of the radius we have expanded. The next time it is on top of the list, we expand \mathbf{u}+\mathcal{B}(k,1) and so forth.

\blacksquare ~ \textnormal{\textbf{Algorithm}} ~\mathcal{B}-stack decoder
Input: received sequence \mathbf r

\mathcal{L} \leftarrow \emptyset

  1. Sort \mathcal{L} according to Fano distance
  2. Expand top list entry with corresponding radius
  3. \mathbf{if} top list entry is of length n: \quad \mathbf{return}

You can find a C++ implementation of the algorithm here.
Read more about sequential decoding here.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s