The stack algorithm is a simple sequential-decoding algorithm. The algorithm expands a set of possible subsequences and keeps the currently best subsolutions in a list. The stack algorithm is usually more efficient than Viterbi decoding (in the general setting), but suboptimal since if
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
be a systematic block code defined over the binary field
, where
is a
identity matrix and
is an arbitary
matrix. We now define a convolutional code as follows.
In the normal (ZJ) stack decoder, we would enumerate all possible length-
sequences and compute the first
codeword symbols in the code generated by
. 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
bits, yielding
more sequences in the list of (length
). This process is repeat until the sought codeword is found.
This is fine if is small, but when
is somewhat larger this quickly becomes cumbersome. Therefore, we introduce the
-stack decoder.
The idea is to not expand the full set of the sequences in each step, but only a subset of them. We read the information bits from the systematic part. Let this sequence be
. Then, we sequentially generate subsets of sequences chosen from the Hamming balls
The number of errors in the systematic bits is expected to be , with
being the error rate of the channel. The first guess is
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 and so forth.
-stack decoder
Input: received sequence
:
- Sort
according to Fano distance
- Expand top list entry with corresponding radius
top list entry is of length
You can find a C++ implementation of the algorithm here.
Read more about sequential decoding here.