Convolutional codes for channels with deletion errors

This correspondence studies convolutional codes for channels with deletion errors. We show that the Viterbi decoding algorithm can be modified to correct deletion errors and prove that it is able to find the closest codeword from the received sequence. The computational complexity of the algorithm is comparable to the complexity of the original Viterbi algorithm. We also prove that maximum-likelihood decoding of deletion-correcting trellis codes cannot be achieved using only a forward recursion in the trellis and a single survivor path per state.