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
Let

$\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.