  Sequential decoding, commonly applied to substitution channels, is a
sub-optimal alternative to Viterbi decoding with significantly reduced memory
costs. In this work, a sequential decoder for convolutional codes over channels
that are prone to insertion, deletion, and substitution errors, is described
and analyzed. Our decoder expands the code trellis by a new channel-state
variable, called drift state, as proposed by Davey and MacKay. A suitable
decoding metric on that trellis for sequential decoding is derived,
generalizing the original Fano metric. The decoder is also extended to
facilitate the simultaneous decoding of multiple received sequences that arise
from a single transmitted sequence. Under low-noise environments, our decoding
approach reduces the decoding complexity by a couple orders of magnitude in
comparison to Viterbi's algorithm, albeit at slightly higher bit error rates.
An analytical method to determine the computational cutoff rate is also
suggested. This analysis is supported with numerical evaluations of bit error
rates and computational complexity, which are compared with respect to optimal
Viterbi decoding.
