UCLA

At short blocklengths, well designed zero-terminated (ZT) and tail-biting (TB) convolutional codes (CCs) concatenated with cyclic redundancy check (CRC) codes have been shown to closely approach the random coding union (RCU) bound for both low rate (rate-1/n) and high rate (rate-(n − 1)/n) codes. The CRC acts as an outer error detection code, verifying that he codeword has been successfully received and decoded, while the CC acts as an inner error correction code, combating channel errors. Maximum likelihood (ML) decoding of such a code can be performed by the serial list Viterbi algorithm (S-LVA), which checks codewords of the inner CC in order of increasing distance from the received word, and returns the firstinner codeword that also passes the CRC. Implementation of the S-LVA for low rate CCs can be done efficiently on the standard Viterbi trellis, while using the dual trellis for high rate CCs can offer significant performance improvements. For some rates, it may be the case that no CRC is available. In that case, we consider a generalization called an expurgating linear function (ELF), which doesn’t enforce the cyclic condition, but similarly serves the function of expurgating low weight codewords, improving the performance of the concatenated code. Both ELFs and CRCs that offer a good distance spectrum metric can be efficiently identified by the list decoding sieve method. Sometimes, it may be desirable to sacrifice ML performance for improved decoding complexity. In such cases, it is possible to leverage the linear nature of CC-CRCs, and in particular, TBCC-CRCs, to reduce the decoding complexity with a small loss to frame error rate (FER) performance. Much of the cost associated with S-LVA of TBCC-CRCs is due to tracebacks of paths that don’t end up meeting the TB condition. Due to the linear nature of the code, we can precompute offsets from any trellis path with a particular ending state difference (ESD), which we can use to quickly search nearby codewords that are guaranteed to meet the TB condition. This has been shown empirically to significantly improve the expected list size required for decoding.