Sequential Decoding of Convolutional Codes for Synchronization Errors

In this work, a sequential decoder for convolutional codes over channels that are vulnerable to insertion, deletion, and substitution errors, is described and analyzed. The decoder expands the code trellis by introducing a new channel state variable, called drift state, as proposed by Davey-MacKay. A suitable decoding metric on that trellis for sequential decoding is derived, in a manner that generalizes the original Fano metric. Under low-noise environments, this approach reduces the decoding complexity by a couple orders of magnitude in comparison to Viterbi's algorithm, albeit at relatively higher frame error rates. An analytical method to determine the computational cutoff rate is also suggested. This analysis is supported with numerical evaluations of frame error rates and computational complexity, which are compared with respect to optimal Viterbi decoding.