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.
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.
Input: received sequence
- Sort according to Fano distance
- Expand top list entry with corresponding radius
- top list entry is of length