Trellis based lower bounds on capacities of channels with synchronization errors

In this paper, we model synchronization error channels as hidden Markov models. Through this model we introduce a rhomboidal trellis for calculating information rates for synchronization error channels. In particular, the introduced trellis is novel due to being synchronized with the channel input sequence, i.e., one trellis section corresponds to one channel input symbol, but (possibly) multiple channel output symbols. By further conditioning on the output sequence length, we construct a finite-length/finite-width trellis, and proceed to provide Monte Carlo methods to evaluate the information rates for Markov channel inputs of any finite order. We also demonstrate how to optimize the Markov process using a generalized Blahut-Arimoto technique to improve on the known lower bounds for the deletion channel.